DE102011006000B4

DE102011006000B4 - Signaturaktualisierung durch Codetransformation

Info

Publication number: DE102011006000B4
Application number: DE102011006000.6A
Authority: DE
Inventors: Dr. Mangard Stefan; Dr. Gammel Berndt
Original assignee: Infineon Technologies AG
Current assignee: Infineon Technologies AG
Priority date: 2011-03-23
Filing date: 2011-03-23
Publication date: 2015-01-15
Anticipated expiration: 2031-03-24
Also published as: US9323604B2; DE102011006000A1; CN102722422A; CN102722422B; FR2973130B1; US20120246452A1; FR2973130A1

Abstract

Verfahren zur Erzeugung einer Instruktionsfolge (404') für eine Recheneinheit, die von einem zumindest die Instruktionsfolge umfassenden Programm gesteuert werden kann, wobei zur Laufzeit des Programms Signaturwerte (SIG'P2) als Instruktionssignaturen durch Aufsummieren der ausgeführten Instruktionen (I1', I2', In') in eine Prüfsumme berechnet und mit Referenzwerten verglichen werden, das Verfahren umfassend: Bestimmen eines Zielsignaturwerts (SIGP1) für eine Zielsignatur an einem Programmpunkt (P); Bestimmen einer initialen Instruktionsfolge (404) für einen zu dem Programmpunkt (P) führenden Programmabschnitt, Prüfen, ob das Ausführen der initialen Instruktionsfolge (404) ausgehend von einem Anfangssignaturwert die Berechnung eines initialen Signaturwerts (SIGP2) für die Zielsignatur zur Folge hätte, der von dem Zielsignaturwert (SIGP1) verschieden wäre; und falls der initiale Signaturwert (SIGP2) von dem Zielsignaturwert (SIGP1) verschieden wäre: Bestimmen einer Modifikation der initialen Instruktionsfolge (404) zur Erlangung einer modifizierten Instruktionsfolge (404'), so dass das Ausführen der modifizierten Instruktionsfolge (404') die Berechnung eines Signaturwerts (SIG'P2) zur Folge hat, der dem Zielsignaturwert (SIGP1) entspricht, und ein Ergebnis einer Verarbeitung von Nutzdaten durch die modifizierte Instruktionsfolge (404') einem Ergebnis einer Verarbeitung der Nutzdaten durch die initiale Instruktionsfolge (404) an dem Programmpunkt (P) entspricht, wobei alle Instruktionen der modifizierten Instruktionsfolge nach dem gleichen Verfahren in die Signaturberechnung eingehen.

Description

Ausführungsbeispiele der vorliegenden Erfindung schaffen ein Verfahren zur Erzeugung einer Instruktionsfolge für eine Recheneinheit, die von einem zumindest die Instruktionsfolge umfassenden Programm gesteuert werden kann. Ausführungsbeispiele der vorliegenden Erfindung schaffen weiterhin ein Verfahren zum Ausführen eines Programms auf einer programmgesteuerten Recheneinheit, wobei das Programm zumindest eine Instruktionsfolge umfasst, die von dem zuerst genannten Verfahren erzeugt wurde. Weitere Ausführungsbeispiele der vorliegenden Erfindung schaffen ein Computerprogramm mit einem Programmcode zur Durchführung des erstgenannten Verfahrens und einen Kompilierer zum Erstellen eines Computerprogramms, der das Verfahren zur Erzeugung einer Instruktionsfolge anwendet.
Das Grundprinzip von Instruktionssignaturen ist, zur Laufzeit eines Programms die ausgeführten Instruktionen in einer Prüfsumme (Signatur) aufzusummieren und an vorgegebenen Stellen gegen Referenzwerte zu prüfen. Kommt es im Programmflussgraph, der als grafische Abbildung des Programmablaufs angesehen werden, zu Verzweigungen, können Signaturaktualisierungen eingesetzt werden, um die Signaturen in zwei oder mehr parallelen Pfaden des Programmflussgraphen zu vereinheitlichen.
Wenn ein Programm (Software) auf einer Recheneinheit (Hardware) ausgeführt wird, so wird in der Regel erwartet, dass das Programm auch tatsächlich so ausgeführt wird, wie es vom Kompilierer zur Kompilierzeit vorgesehen war. In der Realität kann die Ausführung eines Programms bzw. eines Codes jedoch von dem ursprünglich geplanten Programmablauf abweichen. Verantwortlich hierfür sind beispielsweise Fehler in der Hardware, Störsignale oder auch gezielte, mutwillige Manipulationen an der Recheneinheit. Fehler in der Hardware können beispielsweise auf ungewollte Leitungskurzschlüsse, Leitungsunterbrechungen oder hängende Schaltelemente (sog. „stuck-at faults”) zurückgeführt werden, um einige häufig auftretende Arten von Hardwarefehlern zu nennen. Störsignale können während des Betriebs der Recheneinheit beispielsweise durch elektromagnetische Felder oder auch in Form von extremen Temperaturen, die außerhalb des für die Recheneinheit vorgesehenen Temperaturbereichs liegen, auftreten. Mutwillige Manipulationen der Hardware können beispielsweise durch Kurzschließen von ausgewählten Kontakten, Leitungsunterbrechungen oder Laserbestrahlung der Recheneinheit und/oder eines an die Recheneinheit angeschlossenen Speichers erfolgen. Die genannten Fehlerarten können beispielsweise innerhalb der Recheneinheit selbst, innerhalb eines Speichers, in dem das Programm gespeichert ist, innerhalb weiterer Komponenten eines Systems, welches die Recheneinheit umfasst, oder in elektrischen Verbindungen zwischen den Komponenten des Rechnersystems auftreten. Um derartige Fehler während der Ausführung des Programms zu detektieren, kann eine Instruktionsflusskontrolle durchgeführt werden.
Für die Zwecke der Instruktionsflusskontrolle wird in der Regel während der Programmerstellung ein Prüfwert (die Signatur) berechnet, der sich aus den Instruktionen des Programms an die Recheneinheit ergibt. Beispielsweise können die Operationscodes (Opcodes) der Instruktionen aufaddiert werden, um auf diese Weise eine Prüfsumme zu bilden. Bei einem linearen Programm, welches in der Regel vom Programmbeginn bis Programmende einschließlich aller dazwischenliegenden Instruktionen ausgeführt wird, kann somit eine einzige Prüfsumme (bzw. allgemeiner: Prüfwert) berechnet werden, die am Programmende oder nach dem Programmende geprüft werden kann. Für diese Überprüfung wird parallel zur Ausführung einer jeden Instruktion durch die Recheneinheit der Wert dieser Instruktion (beispielsweise in Form des als Bitmuster vorliegenden Opcodes) mit dem Inhalt eines speziellen Registers verrechnet, z. B. zu dem Registerinhalt addiert oder mit dem Registerinhalt bitweise Exklusiv-Oder (XOR) verknüpft. Sobald alle Instruktionswerte auf diese Weise in dem speziellen Register berücksichtigt wurden, kann der sich ergebende Wert des speziellen Registers mit einem Referenz-Prüfwert verglichen werden, um festzustellen, ob eine Übereinstimmung zwischen beiden Werten vorliegt. Sofern eine Übereinstimmung vorliegt, kann in der Regel von einer ordnungsgemäßen Ausführung des Programms ausgegangen werden, d. h. das Programm wurde tatsächlich so ausgeführt, wie es zum Zeitpunkt der Programmerstellung geplant war. Der Referenz-Prüfwert kann beispielsweise als Konstante im Programmcode abgelegt sein. Je nachdem, auf welche Weise und mit welcher Programmiersprache das Programm erstellt wurde, kann der Referenz-Prüfwert von einem Kompilierer („Compiler”) berechnet und in den Programmcode hineingeschrieben werden. Der wissenschaftlichen Artikel „Control Flow Checking by Software Signatures” von Nahmsuk Oh u. a. (Technical Report of the Center for Reliable Computing, Stanford University, CRC TR 00-04, Apr. 2000) beschreibt z. B. ein Software-Verfahren, das den Kontrollfluss eines Programms mittels zugewiesener Signaturen prüft. Der wissenschaftliche Artikel „Control Flow Monitoring for a Time-Triggered Communication Controller” von Thomas Galla u. a. (10th European Workshop an Dependable Computing (EWDC-10), Mai 1999) beschreibt z. B. ein Kontrollfluss-Überwachungsschema für die Architektur einer Protokollkontrolleinheit eines zeitgetriggerten Kommunikationssystems.
Häufig weisen Programme Verzweigungen im Programmfluss auf, die auch als „bedingte Sprünge” angesehen werden können. Nach einer Verzweigung kann das Programm auf zumindest zwei Pfaden fortgesetzt werden, wobei sich die Entscheidung darüber, welcher der zwei oder mehr möglichen Pfade gewählt wird, erst zur Laufzeit des Programms durch die Auswertung einer Bedingung ergibt. Man beachte, dass sich Verzweigungspunkte mit mehr als zwei möglichen Verzweigungspfaden in der Regel in elementare Verzweigungspunkte zerlegen lassen, d. h. in Verzweigungspunkte, die jeweils nur zwei mögliche Verzweigungspfade aufweisen. Für den Wert, der während der Laufzeit des Programms berechnet wird, bedeutet dies, dass er davon abhängt, welche Pfade wie oft durchlaufen wurden. Damit beispielsweise gegen Ende des Programms oder an einem anderen Punkt innerhalb des Programmablaufs ein Vergleich zwischen dem aktuellen Prüfwert und einem für diesen Punkt definierten Referenz-Prüfwert durchgeführt werden kann, besteht die Möglichkeit, den Prüfwert innerhalb der verschiedenen Pfade, die durchlaufen werden können, aneinander auszurichten. Dies kann in der Form erfolgen, dass der Kompilierer in einen Pfad eine oder mehrere für den Programmablauf an sich überflüssige Instruktion(en) einbaut, die den Prüfwert derart verändern, dass der besagte Pfad an einem Zusammenführungspunkt mit einem anderen Pfad den gleichen Prüfwert wie dieser andere Pfad hat. Typischerweise ist dabei vorgesehen, dass spezielle Aktualisierungen anhand bestimmter Bitmuster erkannt und aus dem normalen Instruktionsfluss herausgefiltert werden, um auf spezielle Weise zur Aktualisierung verwendet zu werden.
Die hierin offenbarte technische Lehre betrifft gemäß dem zuvor Gesagten ein Verfahren zur Durchführung von Impliziten Signaturaktualisierungen mittels Codetransformation für Instruktionssignaturverfahren.
Ausführungsbeispiele der hierin offenbarten technischen Lehre schaffen ein Verfahren zur Erzeugung einer Instruktionsfolge für eine Recheneinheit, die von einem zumindest die Instruktionsfolge umfassenden Programm gesteuert werden kann. Dabei werden zur Laufzeit des Programms z. B. durch ein Signaturmodul Signaturwerte als Instruktionssignaturen durch Aufsummieren der von der Recheneinheit ausgeführten Instruktionen in eine Prüfsumme berechnet und mit Referenzwerten verglichen werden. Das Verfahren umfasst: Bestimmen eines Zielsignaturwerts für eine Zielsignatur an einem Programmpunkt; Bestimmen einer initialen Instruktionsfolge für einen zu dem Programmpunkt führenden Programmabschnitt; Prüfen, ob das Ausführen der initialen Instruktionsfolge ausgehend von einem Anfangssignaturwert die Berechnung eines initialen Signaturwerts zur Folge hätte, der von dem Zielsignaturwert verschieden wäre; und, falls der initiale Signaturwert von dem Zielsignaturwert verschieden wäre: Bestimmen einer Modifikation der initialen Instruktionsfolge zur Erlangung einer modifizierten Instruktionsfolge. Durch das Bestimmen der modifizierten Instruktionsfolge wird erreicht, dass das Ausführen der modifizierten Instruktionsfolge die Berechnung des Zielsignaturwerts zur Folge hat. Ein Ergebnis einer Verarbeitung von Nutzdaten durch die modifizierte Instruktionsfolge entspricht einem Ergebnis einer Verarbeitung der Nutzdaten durch die initiale Instruktionsfolge an dem Programmpunkt, wobei alle Instruktionen der modifizierten Instruktionsfolge nach dem gleichen Verfahren in die Signaturberechnung eingehen.
Gemäß dem Verfahren nach der offenbarten technischen Lehre kann somit auf explizite Instruktionen zur Signaturaktualisierung verzichtet werden, da die Signaturaktualisierung inhärent von der modifizierten Instruktionsfolge durchgeführt wird. Im Zusammenhang mit einem Signaturmodul kann somit auf explizite Schreibzugriffe auf das Signaturregister des Signaturmoduls verzichtet werden, welche bei einigen Instruktionssignaturverfahren verwendet werden, um die Signatur in einem Programmpfad an die Signatur in einem parallelen Programmpfad anzugleichen. Die Signaturberechnung zur Laufzeit behandelt alle Instruktionen gleich, d. h. alle Instruktionen gehen nach dem gleichen Verfahren bzw. der gleichen Berechnungsvorschrift in die Signaturberechnung ein. Somit müssen die für die Signaturaktualisierung vorgesehenen Instruktionen zur Laufzeit nicht herausgefiltert werden. Ohnehin übernehmen zumindest einige Instruktionen der modifizierten Instruktionsfolge eine Doppelfunktion, nämlich die Verarbeitung der Nutzdaten und die Aktualisierung der Signatur in der vorgesehenen Weise, so dass für diese Instruktionen keine Unterscheidung nach normalen Instruktionen und Aktualisierungsinstruktionen sinnvoll wäre. Explizite Instruktionen zur Signaturaktualisierung sind gemäß der hierin offenbarten Lehre nicht notwendig, obwohl diese nichtsdestotrotz weiterhin möglich sind.
Die vorgeschlagene Art der Signaturaktualisierung unterscheidet sich somit von anderen Methoden der Signaturaktualisierung, bei denen ein Aktualisierungsbefehl auf andere Weise in die Signaturberechnung eingeht, z. B. durch explizites Addieren eines bestimmten Werts zu dem gegenwärtigen Signaturwert. Zu diesem Zweck weisen Signaturmodule, die derartige andere Methoden der Signaturaktualisierung unterstützen, typischerweise zumindest zwei Schnittstellen auf: Über eine erste Schnittstelle werden dem Signaturmodul die Operationscodes von normalen Instruktionen zugeführt, die somit in die normale Signaturberechnung eingehen. Über eine zweite Schnittstelle werden die expliziten Aktualisierungsanweisungen an das Signaturmodul übermittelt. Diese expliziten Aktualisierungsanweisungen werden typischerweise nicht mit in die Hashsumme eingerechnet, gehen also nicht in die normale Signaturberechnung ein. Gemäß der offenbarten technischen Lehre muss ein Signaturmodul die zweite Schnittstelle nicht unbedingt aufweisen. Ebenso ist es nicht erforderlich, dass das Signaturmodul zwischen „normalen” Instruktionen und Aktualisierungsinstruktionen unterscheidet.
Gemäß der offenbarten Lehre können z. B. alle Instruktionen oder Werte im Rahmen einer Hashwertberechnung berücksichtigt („mitgehasht”) werden oder ein ganzer Befehl wird addiert (anstelle nur des Arguments, das in einem Additionsbefehl spezifiziert ist).
Der Anfangssignaturwert ist einem Punkt am Anfang oder vor der Instruktionsfolge zugeordnet. Durch die Signaturberechnung wird dieser Anfangssignaturwert umgeformt zu einem Endsignaturwert, der einem Punkt am Ende der Instruktionsfolge oder einem Punkt nach dieser zugeordnet ist. Der initiale Signaturwert ist der Wert am Ende der initialen Instruktionsfolge (oder an einem Punkt danach), der sich aus der initialen Instruktionsfolge ergibt. Der Zielsignaturwert ist der Wert am Ende der modifizierten Instruktionsfolge.
Das Modifizieren der Instruktionsfolge kann z. B. auch darin bestehen, dass nicht benutzte Bits in einem Befehl geändert werden, um die Signatur zu ändern. Auf diese Weise können gezielt Bits in der Signatur geändert werden.
In Ausführungsbeispielen kann das Bestimmen der Modifikation eine Änderung der Reihenfolge von zwei oder mehr Instruktionen umfassen, eine Einfügung einer Instruktion umfassen, eine Ersetzung einer Instruktion umfassen und/oder eine Aufteilung einer Instruktion in zwei oder mehr Teilinstruktionen umfasst.
In weiteren Ausführungsbeispielen kann das Bestimmen der Modifikation eine Zuweisung eines konstanten Werts auf ein Register oder ein Speicherelement (Speicheraddresse) der Recheneinheit umfasst, ohne dass der konstante Wert nach der Zuweisung für die Verarbeitung der Nutzdaten verwendet wird. Typischerweise ist das Register oder das Speicherelement, an der konstante Wert geschrieben wird, nicht das Signaturregister, sondern ein für Nutzdaten vorgesehenes Register bzw. Speicherelement.
Weiterhin kann das Bestimmen der Modifikation umfassen: Vergleichen der Differenz mit zumindest einem Signaturmodifizierungswert für zumindest eine Modifizierungsoption; Auswählen einer Modifizierungsoption; Bestimmen einer Restdifferenz; und, falls die Restdifferenz ungleich Null ist: Wiederholen der Schritte des Vergleichens, des Auswählens und des Bestimmens der Restdifferenz. Durch eine iterative Durchführung von mehreren Modifizierungen der initialen Instruktionsfolge können auch Zielsignaturwerte für die Signatur erreicht werden, die nicht mit einer einzigen Modifizierung erzeugt werden können. Die initiale Instruktionsfolge kann unter Umständen wenige Freiheitsgrade aufweisen, so dass eine geeignete Modifizierung möglicherweise schwierig zu finden ist.
Gemäß weiterer Ausführungsbeispiele kann das Bestimmen der Modifizierung eine Auswahl einer gewählten Modifizierungsoption aus einer Vielzahl von Modifizierungsoptionen umfassen, wobei die gemäß der gewählten Modifizierungsoption modifizierte Instruktionsfolge einen geringeren Verarbeitungsmehraufwand gegenüber der initialen Instruktionsfolge aufweist, als andere Modifizierungsoptionen. Durch eine Auswertung einer Kostenfunktion bezüglich des Rechenaufwands können Modifizierungsoptionen herausgefiltert werden, die die gewünschte Signaturaktualisierung mit möglichst geringem zusätzlichem Rechenaufwand für die Recheneinheit erreichen.
Die Auswahl der gewählten Modifizierungsoption kann weiterhin eine Abfrage einer Datenbank umfassen, in der Modifizierungsvorschriften für die Vielzahl der Modifizierungsoptionen gespeichert sind, mittels der die Vielzahl der Modifizierungsoptionen für den Programmabschnitt ermittelt werden können. Die Modifizierungsvorschriften können auch zu erfüllende Bedingungen spezifizieren, die angeben, ob und auf welche Weise eine bestimmte Instruktion oder Instruktionsgruppe modifiziert werden kann. In diese Auswertung kann insbesondere eine Datenabhängigkeitsanalyse eingehen.
Gemäß weiteren Ausführungsbeispielen kann das Bestimmen des Zielinstruktionswerts das Ermitteln eines Instruktionswerts für einen gegenüber dem Programmabschnitt alternativen Programmpfad zu dem Programmpunkt umfassen.
Das Bestimmen der Modifikation kann ferner umfassen: ein Identifizieren einer aufteilbaren Instruktion in dem Programmabschnitt, ein Zerlegen eines Arguments der aufteilbaren Instruktion in zumindest zwei Teilargumente und ein Ersetzen der aufteilbaren Instruktion durch zumindest zwei Teilinstruktionen mit jeweils einem der zumindest zwei Teilargumente.
Nach weiteren Ausführungsbeispielen kann beim Bestimmen der Modifikation der initialen Instruktionsfolge versucht werden, eine Modifikation zu bewirken, die keine Verlängerung der Instruktionsfolge bewirkt. Wenn eine solche Modifikation (mit vertretbarem Aufwand) nicht gefunden werden kann, kann das Verfahren zumindest eine der folgenden Aktionen aufweisen:
Bestimmen einer Modifikation, die eine Verlängerung der Instruktionsfolge bewirkt;
Einfügen einer Anweisung für eine explizite Codeaktualisierung; und
Ändern des Zielsignaturwerts und/oder der initialen Signatur.
Hinsichtlich der Option „Ändern des Zielsignaturwerts und/oder der initialen Signatur” sei darauf hingewiesen, dass die gewünschte Zielsignatur sozusagen eine zusätzliche Randbedingung bei der Optimierung darstellen kann. Die Möglichkeit, den Zielsignaturwert und/oder die initiale Signatur zu ändern, bietet einen zusätzlichen Freiheitsgrad für die Modifizierung. Eine Änderung des Zielsignaturwerts und/oder der initialen Signatur kann unter Umständen bedeuten, dass auch in einem parallelen Programmpfad die Instruktionsfolge modifiziert werden muss.
Alternative Ausführungsbeispiele der Erfindung schaffen ein Verfahren zum Ausführen eines Programms auf einer programmgesteuerten Recheneinheit, wobei das Programm zumindest eine Instruktionsfolge umfasst, die von dem Verfahren zur Erzeugung einer Instruktionsfolge für eine Recheneinheit erzeugt wurde. Während der Ausführung des Programms kommt zur typischerweise zu einer Signaturberechnung für jede von der Recheneinheit ausgeführten Signatur und, an dafür vorgesehen Stellen im Programmfluss des Programms, zu einer Überprüfung des zur Laufzeit berechneten Signaturwerts mit einem Referenzwert. Da es keine expliziten Instruktionen für das Aktualisieren des Signaturregisters bzw. -werts gibt, sind beispielsweise mutwillige Manipulationen an dem Signaturregister für einen potentiellen Angreifer schwieriger durchzuführen.
Ein weiteres Ausführungsbeispiel der offenbarten technischen Lehre schafft ein Computerprogramm mit einem Programmcode zur Durchführung des oben beschriebenen Verfahrens zur Erzeugung einer Instruktionsfolge, wenn das Computerprogramm auf einem Computer abläuft.
Ein weiteres Ausführungsbeispiel der offenbarten technischen Lehre schafft einen Kompilierer zum Erstellen eines solchen Computerprogramms.
Ein weiteres Ausführungsbeispiel schafft eine Vorrichtung zur Erzeugung einer Instruktionsfolge für eine Recheneinheit, die von einem zumindest die Instruktionsfolge umfassenden Programm gesteuert werden kann. Zur Laufzeit des Programms werden Signaturwerte als Instruktionssignaturen durch Aufsummieren der ausgeführten Instruktionen in eine Prüfsumme berechnet und mit Referenzwerten verglichen. Die Vorrichtung umfasst: eine Zielsignaturbestimmung zum Bestimmen eines Zielsignaturwerts an einem Programmpunkt; eine Instruktionsfolgebestimmung zum Bestimmen einer initialen Instruktionsfolge für einen zu dem Programmpunkt führenden Programmabschnitt; eine Signaturermittlung zum Ermitteln eines initialen Signaturwerts, der dem Programmpunkt zugeordnet ist, auf der Basis der initialen Instruktionsfolge; und eine Modifikationsbestimmung zum Bestimmen einer Modifikation der initialen Instruktionsfolge, falls der initiale Signaturwert von dem Zielsignaturwert verschieden ist, zur Erlangung einer modifizierten Instruktionsfolge auf der Grundlage des Zielsignaturwerts und des initialen Signaturwerts. Das Ausführen der modifizierten Instruktionsfolge hat die Berechnung des Zielsignaturwerts zur Folge, und ein Ergebnis einer Verarbeitung von Nutzdaten durch die modifizierte Instruktionsfolge einem Ergebnis einer Verarbeitung der Nutzdaten durch die initiale Instruktionsfolge an dem Programmpunkt entspricht, wobei die Modifikation der initialen Instruktionsfolge zu einer unterschiedlichen zeitlichen Abfolge der Abarbeitung von Instruktionen, die Nutzdaten betreffen, innerhalb des Programmabschnitts führt.
Bei bisherigen Instruktionssignaturverfahren werden die Signaturaktualisierungen oder „Updates” durch explizite Instruktionen oder explizite Speicherzugriffe durchgeführt. Dies bringt einen Mehraufwand bei der Abarbeitung des Programms mit sich. Unter Umständen sind auch architekturelle Änderungen im System notwendig für die Unterstützung expliziter Aktualisierungs-Instruktionen bzw. von expliziten Registern.
Gemäß der offenbarten technischen Lehre kann der Programmcode so transformiert werden, dass durch eine Codetransformation eine gezielte (vorgegebene) Aktualisierung der Instruktionssignatur durchgeführt werden kann.
Ausführungsbeispiele der vorliegenden Erfindung werden im Folgenden anhand der beiliegenden Figuren näher beschrieben.
Es zeigen:
1 eine Veranschaulichung einer Codetransformation mittels Transposition;
2 eine Veranschaulichung einer Codetransformation mittels Einfügung;
3 eine Veranschaulichung eine Codetransformation mittels Ersetzung;
4 einen Ausschnitt aus einem schematischen Flussdiagramm einer initialen Instruktionsfolge und einer modifizierten Instruktionsfolge, welche die initiale Instruktionsfolge ersetzen kann;
5 ein Flussdiagram eines Verfahrens zur Erzeugung einer Instruktionsfolge gemäß einem Ausführungsbeispiel der hierin offenbarten technischen Lehre;
6 ein Flussdiagram eines Details des Verfahrens zur Erzeugung einer Instruktionsfolge gemäß einem weiteren Ausführungsbeispiel der hierein offenbarten technischen Lehre; und
7 ein schematisches Blockschaltbild einer Vorrichtung zur Erzeugung einer Instruktionsfolge für eine Recheneinheit gemäß einem Ausführungsbeispiel der hierin offenbarten technischen Lehre.
Bevor im Folgenden Ausführungsbeispiele anhand der beiliegenden Figuren erläutert werden, wird darauf hingewiesen, dass gleiche Elemente oder Elemente gleicher Funktion mit denselben oder ähnlichen Bezugszeichen versehen sind und dass auf eine wiederholte Beschreibung dieser Elemente verzichtet wird. Beschreibungen von Elementen mit gleichen oder ähnlichen Bezugszeichen sind daher untereinander austauschbar.
In bisherigen Instruktionssignaturverfahren werden die Aktualisierungen der Signatur durch explizite Instruktionen oder Speicherzugriffe durchgeführt. Die Aktualisierungen können jedoch auch ohne Änderung der Hardwarestruktur effizient durch Codetransformationen durchgeführt werden. Um eine gewisse Funktion auf einem Prozessor zu implementieren gibt es meist mehrere Möglichkeiten. Insbesondere wenn man bereit ist, zumindest eine Zusatzinstruktion (es können auch mehrere sein) im Vergleich zum optimalen Code zu erlauben, gibt es eine Vielzahl von Möglichkeiten, den Code zu schreiben. Diese Vielzahl kann genutzt werden, um durch geeignete Wahl des Programmcodes implizit eine Aktualisierung durchzuführen.
Durch eine Änderung des Programmcodes, die das Ergebnis des Programms nicht ändert, kann die Signatur an einem anderen Punkt als dem, an dem die Änderung stattfindet, auf einen gewünschten Zielsignaturwert gebracht werden.
Das Auffinden von Codetransformationen, die die logische Funktion eines Programms unangetastet lassen, ist Fachleuten gut bekannt und bedarf hierin keiner weiteren Erläuterung. Bei Ausführungsbeispielen wird bei einem Kontrollflusssignaturverfahren gezielt eine invariante Transformation aus der riesigen Menge möglicher Transformationen ausgewählt, so dass die Signatur auf einen vorgegebenen Wert transformiert wird.
Letztendlich erzeugt jeder Compiler unterschiedliche Codetransformationen, wobei bei unterschiedlichen Optimierungsstufen unterschiedlicher, aber funktional identischer Code erzeugt wird. Bei Ausführungsbeispielen der Erfindung wird eine der Transformationen genutzt, die eine gewünschte Signatur zur Folge hat.
Bei Ausführungsbeispielen der Erfindung können Transformationen des Codes, die auf die gewünschte Zielsignatur führen, von dem gewählten vorgegebenen Signaturalgorithmus abhängen, wobei für unterschiedliche Signaturalgorithmen unterschiedliche Transformationen zur Zielsignatur führen können.
Bei Ausführungsbeispielen der Erfindung ist eine Anfangs- und eine Zielsignatur vorgegeben und es wird eine entsprechende Code-Transformation gesucht. Für den Fall, dass Instruktionen eingefügt werden, kann es auch mehrere Lösungen geben. Bei Ausführungsbeispielen der Erfindung werden jedoch keine Instruktionen eingefügt, sondern vorhandene Instruktionen vertauscht, um den Code-Overhead gering zu halten.
Ausführungsbeispiele der Erfindung können ein Ändern der Anfangssignatur oder Zielsignatur aufweisen, wenn die zur Verfügung stehenden Freiheitsgrade der Transformation nicht ausreichen, um eine mit gegebenen Randbedingungen (z. B. gegebene Codelänge) verträgliche Transformation zu finden.
Bei Ausführungsbeispielen der Erfindung wird versucht, eine solche Transformation durchzuführen, dass der transformierte Programmcode, z. B. pro Elementarblock (basic block), nicht länger wird, z. B. durch reines Vertauschen von Instruktionen. Falls eine solche Lösung nicht gefunden wird, kann bei Ausführungsbeispielen entweder a) eine Anweisung zur expliziten Signaturaktualisierung eingefügt werden, b) eine zusätzliche Operation eingefügt werden, wie z. B. zwei Additionen statt einer Addition, oder c) eine Änderung von Anfangssignatur und/oder Zielsignatur vorgenommen werden.
Bei Ausführungsbeispielen der Erfindung kann eine Modifikation der initialen Instruktionsfolge eine oder mehrere der folgenden Transformationen aufweisen, wobei dies jedoch keine abschließende Liste darstellt:

– Änderung einer Reihenfolge von zwei oder mehr Instruktionen;
– Einfügung einer oder mehrerer Instruktionen;
– Ersetzen einer oder mehrerer Instruktionen;
– Aufteilung einer Instruktion in zwei oder mehr Teilinstruktionen;
– Zuweisung eines konstanten Werts auf ein Register oder ein Speicherelement der Recheneinheit, ohne dass der konstante Wert nach der Zuweisung für die Verarbeitung der Nutzdaten verwendet wird;
– Durchführen einer Registerpermutation, beispielsweise durch Vertauschen der benutzten Prozessorregister (wie z. B. von R1, R2, R3 in R2, R1, R3 oder R3, R2, R1. Hierbei muss berücksichtigt werden, dass die Register in abhängigen bzw. nachfolgenden Basisblöcken auch die richtigen Werte haben, d. h. es muss eine globale Anpassung über den Elementarblock hinaus erfolgen;
– Benutzung freier Register, wobei wiederum eine gobale Analyse und Anpassungen über den Elementarblock hinaus erforderlich sind;
– Füllen von ungenutzten Feldern in Instruktionen mit frei gewählten Bits; und
– Durchführen von Vorzeichenänderungen von Operanden bei einer Addition oder Subtraktion und entsprechendes Vertauschen von Addition und Subtraktion.

Es ist für Fachleute jedoch offensichtlich, dass neben den genannten auch andere Modifikationen bzw. Transformationen möglich sind, die zu einer Zielsignatur führen.
1 zeigt eine erste Option für eine Codetransformation, die darin besteht, die Reihenfolge von zwei oder mehr Instruktionen zu modifizieren, d. h. die Veränderung von Signaturwerten durch Verschiebung von Instruktionen. Diese Option der Modifizierung wird im Rahmen dieser Beschreibung „Transposition” genannt. Die linke Spalte in 1 zeigt den ursprünglichen Code, in welchem die Instruktionen in der Reihenfolge Instr1, Instr2, Instr3, Instr4, ... InstrN ausgeführt werden. Diese Reihenfolge wurde beispielsweise durch einen Kompilierer oder einen Code-Optimierer festgelegt und bewirkt, Nutzdaten auf eine vorgesehene Weise von den Instruktionen verarbeitet werden. Die rechte Spalte zeigt das Ergebnis von zwei durchgeführten Transpositionen. Eine erste Transposition besteht darin, dass die Instruktionen Instr1 und Instr3 die Plätze getauscht haben. Eine zweite Transposition führte zu einem Vertauschen der Plätze der Instruktionen Instr4 und InstrN. In der Regel wird gefordert, dass die Modifizierung eines Programmabschnitts transparent gegenüber der Verarbeitung der Nutzdaten ist. Dies bedeutet, dass nach Ausführung eines modifizierten Programmabschnitts die Nutzdaten im Ergebnis auf identische Weise verarbeitet worden sind, wie es von dem ursprünglichen Programmabschnitt bewirkt worden wäre. Innerhalb des modifizierten Programmabschnitts kann die Verarbeitung der Nutzdaten dagegen von der Verarbeitung abweichen, die im Rahmen des ursprünglichen Programmabschnitts durchgeführt wird. Bei der Transposition wird beispielsweise ausgenutzt, dass die Reihenfolge bestimmter Instruktionen verändert werden kann, ohne die Verarbeitung der Nutzdaten im Ergebnis (d. h. am Ende des modifizierten Programmabschnitts) zu verändern.
Die Codetransformation mittels Transposition kann angewendet werden, wenn die Signaturberechnung nicht kommutativ ist, so dass eine Vertauschung der Reihenfolge der Instruktionen zu unterschiedlichen Signaturwerten führt, wenn also gilt:
Signatur(Instr1, Instr2) ≠ Signatur(Instr2, Instr1).
Hinsichtlich der Nutzdaten sind die Instruktionen Instr1 und Instr2 dagegen typischerweise kommutativ. Auf diese Weise kann die Signatur durch Veränderung der Reihenfolge der Instruktionen beeinflusst werden. Wenn hinsichtlich der Nutzdaten eine große Anzahl von Permutationen der Reihenfolge der Instruktionen möglich ist, hat die Transposition von Instruktionen eine große Anzahl von Freiheitsgraden, so dass die Signatur an viele gewünschte Zielsignaturwerte angepasst werden kann.
2 zeigt eine zweite Option für eine Codetransformation, die darin besteht, eine oder mehrere Instruktionen einzufügen, die in dem ursprünglichen Programmcode nicht enthalten waren. In 2 wird zwischen den Instruktionen Instr2 und Instr3 der ursprünglichen Programmcodes eine zusätzliche Instruktion InstrX eingefügt. Weiterhin wird nachfolgend auf die Instruktion Instr4 eine weitere zusätzliche Instruktion InstrY eingefügt. Die eingefügten Instruktionen InstrX und InstrY können zum Beispiel Instruktion sein, die die Nutzdaten nicht verändern. Denkbar sind hier eine Addition des Wertes Null, das Wiederholen eines Speicherlese- oder -schreibvorgangs (so dass derselbe Wert zweimal gelesen oder geschrieben wird) oder das Laden eines bestimmten Werts in ein zu diesem Zeitpunkt unbenutzes Register des Prozessors.
3 zeigt eine dritte Option für eine Codetransformation, die darin besteht, eine ursprüngliche Instruktion zu ersetzen. In 3 wird die ursprüngliche Instruktion Instr2 durch zwei Instruktionen InstrX und InstrY ersetzt. Es wird eine Zerlegung des Arguments durchgeführt, so dass das Resultat gleich bleibt, aber die Signatur den gewünschten Zielwert erhält. Wie im unteren Teil von 3 dargestellt, kann die Instruktion Instr2 zum Beispiel eine Addition des konstanten Werts 2468 zu dem aktuellen Inhalt im Register R3 sein. Diese Addition kann aufgeteilt werden in zwei Teiladdition, wobei im Rahmen der ersten Teiladdition (InstrX) zunächst der Wert 1330 addiert wird und im Rahmen der zweiten Teiladdition (InstrY) der Wert 1138 addiert wird. Im Ergebnis enthält das Register R3 nach Ausführung der zwei Instruktionen InstrX und InstrY damit den gegenüber seinem vorherigen Inhalt um 2468 erhöhten Wert. Anstelle von zwei Additionen können auch zwei Subtraktionen, mehrere Teiladdition, mehrere Teilsubtraktionen oder eine Kombination von Addition(en) und Subtraktion(en) durchgeführt werden. Diese Option der Codetransformation eröffnet weitreichende und/oder flexible Möglichkeiten, da sich konstante Werte durch viele verschiedene Additions- und Subtraktionskombinationen darstellen lassen. Zum Beispiel kann durch eine Addition eines konstanten Werts und eine nachfolgende Subtraktion desselben Werts im Ergebnis der Wert Null zu einem Register hinzuaddiert werden, was sich im Ergebnis der Nutzdatenverarbeitung nicht auswirkt. Auf die Signaturberechnung hat eine derartige Instruktionskombination dagegen einen Einfluss, der bei gezielter Wahl des konstanten Werts so justiert werden kann, dass eine Signaturaktualisierung erzielt werden kann, die die Signatur an einem bestimmten Programmpunkt auf einen Zielsignaturtwert bringt, sofern im Zusammenhang mit der Recheneinheit während der Laufzeit des Programms kein Fehler bei der Verarbeitung der Instruktionen auftritt, die in die Signaturberechnung eingehen.
3 veranschaulicht somit ein Beispiel für eine Codetransformation, bei der eine Addition in zwei statt in nur einem Schritt berechnet wird. Durch die Wahl der Aufteilung der zwei Schritte kann die Instruktionssignatur so verändert (aktualisiert) werden, dass genau die Funktionalität einer expliziten Signaturaktualisierungsinstruktion implementiert wird.
Als Alternative zu einer Aufteilung der Verarbeitung eines konstanten Werts, wie in 3 gezeigt, kann auch ein Registerwert oder eine Variable in zwei oder mehr Schritten verarbeitet werden. Wenn zum Beispiel der Inhalt eines ersten Registers R1 zu dem Inhalt eines zweiten Registers R2 hinzuaddiert werden soll, so kann zunächst das niedrigstwertige Bit von R1 zum Inhalt von R2 hinzuaddiert werden, dann der Inhalt des ersten Registers R1 durch zwei geteilt werden (allgemein: durch n), z. B. mittels Rechtsverschiebung („right shift”) und anschließend zweimal (allgemein: n-mal) zum zweiten Register hinzuaddiert werden.
Die in 1 bis 3 als Beispiel angegebenen Modifizierungsoptionen sind geeignet, die Signatur gezielt zu beeinflussen, ohne auf den Inhalt eines Signaturregisters der Recheneinheit oder eines verbundenen Signaturmoduls direkt Einfluss zu nehmen, bzw. ohne eine oder mehrere auf den Inhalt des Signaturregisters Einfluss nehmende Instruktion. Andere Beispiele sind die Zuweisung von Konstanten auf Register, die vom Prozessor zumindest zeitweilig nicht genutzt werden.
4 stellt einen Ausschnitt eines Programmablaufplans dar. An einem Programmpunkt P werden zwei Programmpfade bzw. Instruktionsfolgen 402 und 404 wieder vereinigt, die von einem Verzweigungspunkt (nicht gezeigt) ausgehen. Am Ende der Instruktionsfolge 402 hat die Signatur bei korrekter Ausführung der Instruktionen den Wert SIG_P1. Eine initiale Version der zweiten Instruktionsfolge 404 führt dagegen zu einem Signaturwert SIG_P2, der im Allgemeinen unterschiedlich zum Signaturwert SIG_P1 ist um eine Differenz ΔSIG = SIG_P1 – SIG_P2. Bevor die zwei Instruktionsfolgen 402 und 404 am Punkt P vereinigt werden, ist es in der Regel erwünscht, dass die Signaturen in den verschiedenen sich vereinigenden Instruktionsfolgen 402 und 404 denselben Signaturwert aufweisen, sofern ein fehlerfreie Ausführung der Instruktionen in den Instruktionsfolgen erfolgt ist. Zu diesem Zweck wird die Signatur in einer der beiden Instruktionsfolgen 404, 402 an die Signatur der anderen Instruktionsfolge 402, 404 angepasst. In 4 wird die zweite Instruktionsfolge 404 angepasst, so dass aus der initialen Instruktionsfolge 404 eine modifizierte Instruktionsfolge 404' entsteht. Die modifizierte Instruktionsfolge 404' weist am Programmpunkt P einen modifizierten Signaturwert SIG_P2' auf, welcher mit dem Signaturwert SIG_P1 der ersten Instruktionsfolge 402 übereinstimmt. Es gilt: SIG_P2' = SIG_P2 + ΔSIG = SIG_P1. Auf diese Weise kann die Signaturberechnung und -überprüfung nach der Vereinigung der Instruktionsfolgen 402, 404' bei Programmpunkt P fortgesetzt werden, ohne dass es für die Signaturberechnung eine Bedeutung hat, ob die erste Instruktionsfolge 402 oder die (modifizierte) zweite Instruktionsfolge 404' von der Recheneinheit abgearbeitet wurde.
Im Rahmen der modifizierten Instruktionsfolge 404' ist es möglich, die Signatur durch eine explizite Signaturaktualisierung an die Signatur der Instruktionsfolge 402 anzupassen. Gemäß der hierin offenbarten technischen Lehre wird jedoch eine Modifikation der Instruktionsfolge 404 durchgeführt, so dass zumindest einige der ursprünglichen Instruktionen I1, I2, und In modifiziert werden. Die modifizierte Instruktionsfolge 404' weist somit zum Beispiel modifizierte Instruktionen I1', I2' und In' auf. Die Modifizierung der Instruktionen kann in einem Verschieben, Weglassen, Hinzufügen, Ersetzen oder Ändern von Instruktionen bestehen. Insbesondere unterscheidet sich die zeitliche Abfolge der Verarbeitung von Daten innerhalb der initialen Instruktionsfolge 404 von der, die innerhalb der modifizierten Instruktionsfolge 404' durchgeführt wird. Ein Unterschied in der zeitlichen Abfolge wird auch dadurch verursacht, dass z. B. eine Null-Addition an einer bestimmten Stelle der modifizierten Instruktionsfolge 404' eingefügt wird, da dadurch die nachfolgenden Instruktionen mindestens einen Taktzyklus später ausgeführt werden.
Zu den Nutzdaten eines Programms oder eines Programmabschnitts sind typischerweise zumindest solche Daten zu zählen, die eine Eingangs-, Ausgangs- oder Hilfsvariable des Programms bzw. Programmabschnitts darstellen, d. h. Daten, die eine Ausgabe oder ein Ergebnis des Programms bzw. Programmabschnitts beeinflussen. Je nach Definition können weiterhin auch Daten zu den Nutzdaten gehören, die von dem Prozessor verarbeitet werden, die Ausgabe des Programms bzw. Programmabschnitts jedoch nicht beeinflussen. Letztere Daten können zum Beispiel Daten sein, die in ein Register der Recheneinheit geschrieben werden oder aus diesem ausgelesen werden, jedoch nicht mit Eingabevariablen, Hilfsvariablen und/oder Ausgabevariablen des Programms bzw. Programmabschnitts interagieren.
5 zeigt ein schematisches Flussdiagramm eines Verfahrens zur Erzeugung einer Instruktionsfolge für eine Recheneinheit gemäß einem Ausführungsbeispiel der hierin offenbarten technischen Lehre.
Bei Aktion 502 wird ein Zielsignaturwert für einen Programmpunkt P bestimmt. Der Zielsignaturwert kann sich zum Beispiel aus der standardmäßig berechneten Referenzsignatur eines anderen Programmpfads ergeben, der zum Programmpunkt P führt.
Bei 504 wird eine initiale Instruktionsfolge für einen Programmabschnitt bestimmt, der zu dem Programmpunkt P führt. Meist mündet der Programmabschnitt in den Programmpunkt P, obwohl Abweichungen hiervon möglich sind, d. h. der Programmabschnitt endet schon vor dem Programmpunkt P. Die Bestimmung der initialen Instruktionsfolge kann zum Beispiel durch einen Kompilierer erfolgen. Im Rahmen des hierin offenbarten Verfahrens zur Erzeugung einer Instruktionsfolge kann die initiale Instruktionsfolge auch z. B. aus einer Datei oder einem Datenträger ausgelesen werden.
Als optionale Aktion kann bei 506 ein initialer Signaturwert auf der Grundlage der Instruktionen der initialen Instruktionsfolge ermittelt werden. Ebenfalls optional ist die Bestimmung einer Differenz zwischen dem Zielsignaturwert und dem initialen Signaturwert bei 508. Durch die Bestimmung der Differenz kann unter Umständen eine Suche nach möglichen Modifizierungsoptionen erleichtert werden. Die Differenz kann zum Beispiel als Argument in eine Funktion eingehen, mit der ein konstanter Wert berechnet wird, welcher in ein gegenwärtig unbenutztes Register der Recheneinheit geschrieben wird. Diese Registerschreiboperation kann dann eine Änderung der Signatur bewirken, die genau der benötigten Differenz der Signatur entspricht.
Im Rahmen der Aktion 510 wird darin eine Modifikation der initialen Instruktionsfolge 404 bestimmt, die zur modifizierten Instruktionsfolge 404' führt.
In 6 ist ein schematisches Flussdiagramm abgebildet, das einen Aspekt eines Verfahrens zur Erzeugung einer Instruktionsfolge zeigt. Ausgehend von der Aktion 508, in welcher die Differenz zwischen dem Zielsignaturwert und dem initialen Signaturwert bestimmt wird, wird bei 608 die Differenz mit zumindest einem Signaturmodifizierungswert für eine Modifizierungsoption verglichen. Bei 610 wird eine Modifizierungsoption ausgewählt und die entsprechende Modifizierung der Instruktionsfolge durchgeführt. Wenn der Signaturmodifizierungswert für die gewählte Modifizierungsoption mit der festgestellten Differenz übereinstimmt, ist das Ziel der Modifizierung erreicht. Dies wird dadurch festgestellt, dass bei 612 eine Restdifferenz bestimmt wird und diese Restdifferenz bei 614 mit Null verglichen wird. Wenn die Restdifferenz gleich Null ist, endet das Verfahren mit der Ausgabe der modifizierten Instruktionsfolge 616. Wenn dagegen die Restdifferenz ungleich Null ist, springt das Verfahren von der Abfrage 614 zurück zur Aktion 608, wo die Restdifferenz mit den Signaturmodifizierungswerten für eine oder mehrere Modifizierungsoptionen verglichen wird. Auf diese Weise können mehrere Iterationen durchlaufen werden, bis die Restdifferenz gleich Null ist. Bei jeder Iteration wird eine weitere Modifizierungsoption durchgeführt, die jedoch für die Verarbeitung der Nutzdaten im Ergebnis unerheblich, also „transparent” ist.
In der Regel wird für das Verfahren angestrebt werden, mit möglichst wenigen Modifizierungen der initialen Instruktionsfolge auszukommen, da auf diese Weise der durch die Modifizierung häufig verursachte Mehraufwand für die Recheneinheit im Rahmen gehalten werden kann. Während bei Transpositionen, wie sie in 1 gezeigt sind, unter Umständen überhaupt keine Erhöhung des Rechenaufwands entsteht, können Einfügungen von Instruktionen den Rechenaufwand erhöhen. Unterschiedliche Modifizierungsoptionen sind also mit unterschiedlichen Auswirkungen auf den Rechenaufwand verbunden. Diese Information kann zusammen mit den Modifizierungsoptionen gespeichert sein, so dass die Entscheidung für eine spezielle Modifizierungsoption eine eventuelle Erhöhung des Rechenaufwands in Betracht ziehen kann. Eine mögliche Strategie für die Wahl der Modifizierungsoption(en) könnte somit sein, zunächst mögliche Transpositionen von Instruktionen zu prüfen. Erst wenn sich herausstellt, dass der Zielsignaturwert der Signatur ausschließlich mit Transpositionen nicht erreicht werden kann, könnte auf andere Modifizierungsoptionen wie Einfügungen und/oder Ersetzungen ausgewichen werden.
7 zeigt ein schematisches Blockschaltbild einer Vorrichtung 100 zur Erzeugung einer Instruktionsfolge für eine Recheneinheit gemäß der hierin offenbarten technischen Lehre. Die Vorrichtung 100 empfängt beispielsweise von einem Kompilierer Instruktionen als Eingabegröße. Diese Instruktionen liegen meist in Form einer initialen Instruktionsfolge vor. Die Vorrichtung 100 umfasst eine Instruktionsfolgebestimmung 104, die die initiale Instruktionsfolge bestimmt bzw. durch Auslesen einer Datei oder vergleichbare Aktionen der Vorrichtung 100 zur Verfügung stellt.
Die Vorrichtung 100 umfasst ferner eine Zielsignaturwertbestimmung 102. Die Zielsignaturwertbestimmung 102 kann zum Beispiel ausgelegt sein, Programmpunkte zu identifizieren, an denen zwei oder mehrere parallele Programmpfade wieder zusammengeführt werden. An diesen Programmpunkten ist typischerweise vorgesehen, dass in einigen der Programmpfade eine Signaturaktualisierung durchgeführt wird, damit an besagtem Programmpunkt die Signaturen in den verschiedenen Signaturpfaden einander entsprechen. Die Zielsignaturwertbestimmung 102 kann einen der Programmpfade festlegen, der als Referenzpfad für die Zwecke der Signaturbestimmung dienen kann. In dem Referenzpfad wird typischerweise keine Signaturaktualisierung durchgeführt, obwohl dies nicht ausgeschlossen ist. In dem anderen Programmpfad oder den anderen Programmpfaden ist dagegen typischerweise eine Signaturaktualisierung vorgesehen.
Eine Signaturermittlung 106 ist ausgelegt, eine initiale Signatur für die und auf der Grundlage der initialen Instruktionsfolge zu ermitteln. Die ermittelte initiale Signatur wird an eine Differenzbestimmung 108 übermittelt, die als weitere Eingabevariable den Zielsignaturwert empfängt. Eine ermittelte Differenz zwischen dem Zielsignaturwert und der initialen Signatur wird an eine Modifizierungsbestimmung 110 weitergeleitet, die auch die initiale Instruktionsfolge von der Instruktionsfolgebestimmung 104 empfängt. Die Modifizierungsbestimmung 110 gibt eine modifizierte Instruktionsfolge aus, welche auch eine Ausgabe der Vorrichtung zur Erzeugung der Instruktionsfolge darstellt.
Obwohl manche Aspekte im Zusammenhang mit einer Vorrichtung beschrieben wurden, versteht es sich, dass diese Aspekte auch eine Beschreibung des entsprechenden Verfahrens darstellen, sodass ein Block oder ein Bauelement einer Vorrichtung auch als ein entsprechender Verfahrensschritt oder als ein Merkmal eines Verfahrensschrittes zu verstehen ist. Analog dazu stellen Aspekte, die im Zusammenhang mit einem oder als ein Verfahrensschritt beschrieben wurden, auch eine Beschreibung eines entsprechenden Blocks oder Details oder Merkmals einer entsprechenden Vorrichtung dar. Einige oder alle der Verfahrensschritte können durch einen Hardware-Apparat (oder unter Verwendung eines Hardware-Apparats), wie zum Beispiel einen Mikroprozessor, einen programmierbaren Computer oder eine elektronische Schaltung ausgeführt werden. Bei einigen Ausführungsbeispielen können einige oder mehrere der wichtigsten Verfahrensschritte durch einen solchen Apparat ausgeführt werden.
Je nach bestimmten Implementierungsanforderungen können Ausführungsbeispiele der Erfindung in Hardware oder in Software implementiert sein. Die Implementierung kann unter Verwendung eines digitalen Speichermediums, beispielsweise einer Floppy-Disk, einer DVD, einer Blu-ray Disc, einer CD, eines ROM, eines PROM, eines EPROM, eines EEPROM oder eines FLASH-Speichers, einer Festplatte oder eines anderen magnetischen oder optischen Speichers durchgeführt werden, auf dem elektronisch lesbare Steuersignale gespeichert sind, die mit einem programmierbaren Computersystem derart zusammenwirken können oder zusammenwirken, dass das jeweilige Verfahren durchgeführt wird. Deshalb kann das digitale Speichermedium computerlesbar sein.
Manche Ausführungsbeispiele gemäß der Erfindung umfassen also einen Datenträger, der elektronisch lesbare Steuersignale aufweist, die in der Lage sind, mit einem programmierbaren Computersystem derart zusammenzuwirken, dass eines der hierin beschriebenen Verfahren durchgeführt wird.
Allgemein können Ausführungsbeispiele der vorliegenden Erfindung als Computerprogrammprodukt mit einem Programmcode implementiert sein, wobei der Programmcode dahin gehend wirksam ist, eines der Verfahren durchzuführen, wenn das Computerprogrammprodukt auf einem Computer abläuft.
Der Programmcode kann beispielsweise auch auf einem maschinenlesbaren Träger gespeichert sein.
Andere Ausführungsbeispiele umfassen das Computerprogramm zum Durchführen eines der hierin beschriebenen Verfahren, wobei das Computerprogramm auf einem maschinenlesbaren Träger gespeichert ist.
Mit anderen Worten ist ein Ausführungsbeispiel des erfindungsgemäßen Verfahrens somit ein Computerprogramm, das einen Programmcode zum Durchführen eines der hierin beschriebenen Verfahren aufweist, wenn das Computerprogramm auf einem Computer abläuft.
Ein weiteres Ausführungsbeispiel der erfindungsgemäßen Verfahren ist somit ein Datenträger (oder ein digitales Speichermedium oder ein computerlesbares Medium), auf dem das Computerprogramm zum Durchführen eines der hierin beschriebenen Verfahren aufgezeichnet ist.
Ein weiteres Ausführungsbeispiel des erfindungsgemäßen Verfahrens ist somit ein Datenstrom oder eine Sequenz von Signalen, der bzw. die das Computerprogramm zum Durchführen eines der hierin beschriebenen Verfahren darstellt bzw. darstellen. Der Datenstrom oder die Sequenz von Signalen kann bzw. können beispielsweise dahin gehend konfiguriert sein, über eine Datenkommunikationsverbindung, beispielsweise über das Internet, transferiert zu werden.
Ein weiteres Ausführungsbeispiel umfasst eine Verarbeitungseinrichtung, beispielsweise einen Computer oder ein programmierbares Logikbauelement, die dahin gehend konfiguriert oder angepasst ist, eines der hierin beschriebenen Verfahren durchzuführen.
Ein weiteres Ausführungsbeispiel umfasst einen Computer, auf dem das Computerprogramm zum Durchführen eines der hierin beschriebenen Verfahren installiert ist.
Ein weiteres Ausführungsbeispiel gemäß der Erfindung umfasst eine Vorrichtung oder ein System, die bzw. das ausgelegt ist, um ein Computerprogramm zur Durchführung zumindest eines der hierin beschriebenen Verfahren zu einem Empfänger zu übertragen. Die Übertragung kann beispielsweise elektronisch oder optisch erfolgen. Der Empfänger kann beispielsweise ein Computer, ein Mobilgerät, ein Speichergerät oder eine ähnliche Vorrichtung sein. Die Vorrichtung oder das System kann beispielsweise einen Datei-Server zur Übertragung des Computerprogramms zu dem Empfänger umfassen.
Bei manchen Ausführungsbeispielen kann ein programmierbares Logikbauelement (beispielsweise ein feldprogrammierbares Gatterarray, ein FPGA) dazu verwendet werden, manche oder alle Funktionalitäten der hierin beschriebenen Verfahren durchzuführen. Bei manchen Ausführungsbeispielen kann ein feldprogrammierbares Gatterarray mit einem Mikroprozessor zusammenwirken, um eines der hierin beschriebenen Verfahren durchzuführen. Allgemein werden die Verfahren bei einigen Ausführungsbeispielen seitens einer beliebigen Hardwarevorrichtung durchgeführt. Diese kann eine universell einsetzbare Hardware wie ein Computerprozessor (CPU) sein oder für das Verfahren spezifische Hardware, wie beispielsweise ein ASIC.
Die oben beschriebenen Ausführungsbeispiele stellen lediglich eine Veranschaulichung der Prinzipien der vorliegenden Erfindung dar. Es versteht sich, dass Modifikationen und Variationen der hierin beschriebenen Anordnungen und Einzelheiten anderen Fachleuten einleuchten werden. Deshalb ist beabsichtigt, dass die Erfindung lediglich durch den Schutzumfang der nachstehenden Patentansprüche und nicht durch die spezifischen Einzelheiten, die anhand der Beschreibung und der Erläuterung der Ausführungsbeispiele hierin präsentiert wurden, beschränkt sei.

Claims

Verfahren zur Erzeugung einer Instruktionsfolge (404') für eine Recheneinheit, die von einem zumindest die Instruktionsfolge umfassenden Programm gesteuert werden kann, wobei zur Laufzeit des Programms Signaturwerte (SIG'_P2) als Instruktionssignaturen durch Aufsummieren der ausgeführten Instruktionen (I₁', I₂', I_n') in eine Prüfsumme berechnet und mit Referenzwerten verglichen werden, das Verfahren umfassend: Bestimmen eines Zielsignaturwerts (SIG_P1) für eine Zielsignatur an einem Programmpunkt (P); Bestimmen einer initialen Instruktionsfolge (404) für einen zu dem Programmpunkt (P) führenden Programmabschnitt, Prüfen, ob das Ausführen der initialen Instruktionsfolge (404) ausgehend von einem Anfangssignaturwert die Berechnung eines initialen Signaturwerts (SIG_P2) für die Zielsignatur zur Folge hätte, der von dem Zielsignaturwert (SIG_P1) verschieden wäre; und falls der initiale Signaturwert (SIG_P2) von dem Zielsignaturwert (SIG_P1) verschieden wäre: Bestimmen einer Modifikation der initialen Instruktionsfolge (404) zur Erlangung einer modifizierten Instruktionsfolge (404'), so dass das Ausführen der modifizierten Instruktionsfolge (404') die Berechnung eines Signaturwerts (SIG'_P2) zur Folge hat, der dem Zielsignaturwert (SIG_P1) entspricht, und ein Ergebnis einer Verarbeitung von Nutzdaten durch die modifizierte Instruktionsfolge (404') einem Ergebnis einer Verarbeitung der Nutzdaten durch die initiale Instruktionsfolge (404) an dem Programmpunkt (P) entspricht, wobei alle Instruktionen der modifizierten Instruktionsfolge nach dem gleichen Verfahren in die Signaturberechnung eingehen.
Verfahren nach Anspruch 1, wobei das Bestimmen der Modifikation eine Änderung der Reihenfolge von zwei oder mehr Instruktionen (I₁, I₂, I_n) umfasst.
Verfahren nach Anspruch 1 oder 2, wobei das Bestimmen der Modifikation eine Einfügung einer Instruktion (I₁', I₂', I_n') umfasst.
Verfahren nach einem der Ansprüche 1 bis 3, wobei das Bestimmen der Modifikation eine Ersetzung einer Instruktion (I₁, I₂, I_n) umfasst.
Verfahren nach einem der Ansprüche 1 bis 4, wobei das Bestimmen der Modifikation eine Aufteilung einer Instruktion (I₁, I₂, I_n) in zwei oder mehr Teilinstruktionen umfasst.
Verfahren nach einem der Ansprüche 1 bis 5, wobei das Bestimmen der Modifikation eine Zuweisung eines konstanten Werts auf ein Register oder ein Speicherelement der Recheneinheit umfasst, ohne dass der konstante Wert nach der Zuweisung für die Verarbeitung der Nutzdaten verwendet wird.
Verfahren nach einem der Ansprüche 1 bis 6, wobei das Bestimmen der Modifikation umfasst: Bestimmen einer Differenz zwischen dem Zielsignaturwert und dem initialen Signaturwert; Vergleichen der Differenz bzw. Restdifferenz mit zumindest einem Signaturmodifizierungswert für zumindest eine Modifizierungsoption; Auswählen einer Modifizierungsoption; Bestimmen einer Restdifferenz; und, falls die Restdifferenz ungleich Null ist: Wiederholen der Schritte des Vergleichens, des Auswählens und des Bestimmens der Restdifferenz.
Verfahren nach einem der Ansprüche 1 bis 7, wobei das Bestimmen der Modifizierung eine Auswahl einer gewählten Modifizierungsoption aus einer Vielzahl von Modifizierungsoptionen umfasst, wobei die gemäß der gewählten Modifizierungsoption modifizierte Instruktionsfolge (404') einen geringeren Verarbeitungsmehraufwand gegenüber der initialen Instruktionsfolge (404) aufweist, als andere Modifizierungsoptionen.
Verfahren nach Anspruch 8, wobei die Auswahl der gewählten Modifizierungsoption eine Abfrage einer Datenbank umfasst, in der Modifizierungsvorschriften für die Vielzahl der Modifizierungsoptionen gespeichert sind, mittels der die Vielzahl der Modifizierungsoptionen für den Programmabschnitt ermittelt werden können.
Verfahren nach einem der Ansprüche 1 bis 9, wobei das Bestimmen des Zielsignaturwerts (SIG_P1) das Ermitteln eines Signaturwerts für einen gegenüber dem Programmabschnitt alternativen Programmpfad (402) zu dem Programmpunkt (P) umfasst.
Verfahren nach einem der Ansprüche 1 bis 10, wobei das Bestimmen der Modifikation umfasst: ein Identifizieren einer aufteilbaren Instruktion in dem Programmabschnitt, ein Zerlegen eines Arguments der aufteilbaren Instruktion in zumindest zwei Teilargumente und ein Ersetzen der aufteilbaren Instruktion durch zumindest zwei Teilinstruktionen mit jeweils einem der zumindest zwei Teilargumente.
Verfahren nach einem der Ansprüche 1 bis 11, wobei beim Schritt des Bestimmens einer Modifikation der initialen Instruktionsfolge (404) versucht wird, eine Modifikation zu bestimmen, die keine Verlängerung der Instruktionsfolge bewirkt, wobei, wenn eine solche Modifikation nicht gefunden wird, das Verfahren zumindest einen der folgenden Schritte aufweist: – Bestimmen einer Modifikation, die eine Verlängerung der Instruktionsfolge (404) bewirkt; – Einfügen einer Anweisung für eine explizite Codeaktualisierung; und – Ändern des Zielsignaturwerts (SIG_P1) und/oder der initialen Signatur.
Verfahren zum Ausführen eines Programms auf einer programmgesteuerten Recheneinheit, wobei das Programm zumindest eine modifizierte Instruktionsfolge (404') umfasst, die von einem Verfahren nach einem der Ansprüche 1 bis 12 erzeugt wurde.
Computerprogramm mit einem Programmcode zur Durchführung des Verfahrens nach einem der Ansprüche 1 bis 12, wenn das Computerprogramm auf einem Computer abläuft.
Kompilierer zum Erstellen eines Computerprogramms, der das Verfahren nach einem der Ansprüche 1 bis 12 anwendet.
Vorrichtung zur Erzeugung einer Instruktionsfolge (404') für eine Recheneinheit, die von einem zumindest die Instruktionsfolge (404') umfassenden Programm gesteuert werden kann, wobei zur Laufzeit des Programms Signaturwerte (SIG'_P2) als Instruktionssignaturen durch Aufsummieren der ausgeführten Instruktionen (I₁', I₂', I_n') in eine Prüfsumme berechnet und mit Referenzwerten verglichen werden, die Vorrichtung umfassend: eine Zielsignaturbestimmung (102) zum Bestimmen eines Zielsignaturwerts (SIG_P1) an einem Programmpunkt (P); eine Instruktionsfolgebestimmung (104) zum Bestimmen einer initialen Instruktionsfolge (404) für einen zu dem Programmpunkt (P) führenden Programmabschnitt; eine Signaturermittlung (106) zum Ermitteln eines initialen Signaturwerts (SIG_P2), der dem Programmpunkt (P) zugeordnet ist, auf der Basis der initialen Instruktionsfolge (404); und eine Modifikationsbestimmung (110) zum Bestimmen einer Modifikation der initialen Instruktionsfolge (404), falls der initiale Signaturwert (SIG_P2) von dem Zielsignaturwert (SIG_P1) verschieden ist, zur Erlangung einer modifizierten Instruktionsfolge (404') auf der Grundlage des Zielsignaturwerts (SIG_P1) und des initialen Signaturwerts (SIG_P2), so dass das Ausführen der modifizierten Instruktionsfolge (404') die Berechnung des Zielsignaturwerts (SIG_P1) zur Folge hat, und ein Ergebnis einer Verarbeitung von Nutzdaten durch die modifizierte Instruktionsfolge (404') einem Ergebnis einer Verarbeitung der Nutzdaten durch die initiale Instruktionsfolge (404) an dem Programmpunkt (P) entspricht, wobei alle Instruktionen (I₁', I₂', I_n') der modifizierten Instruktionsfolge (404') nach dem gleichen Verfahren in die Signaturberechnung eingehen.