aus JKUWiki, der freien Wissensdatenbank

Organisatorisches (nicht Inhalt des Dokuments)

Arbeitsseite

Der Aufsatz ist in zwei Formen abzugeben: auf Papier und per eMail.

Die ausgedruckte Fassung ist zu Beginn der Präsentation dem Lehrveranstaltungsleiter zu übergeben. Die elektronische Fassung ist einen Tag vor der Präsentation dem betreuenden Assistenten zu schicken.

Die Blätter (A4-Format) sind einseitig zu bedrucken und mit einem Heftstreifen verbunden abzugeben. Das erste Blatt ist die Titelseite laut Vorlage.

Der Aufsatz ist sowohl im MS-Word-Format, als auch im PDF-Format abzugeben. Die Namen der Dateien lauten <themenkürzel>.doc bzw. <themenkürzel>.pdf, also z.B. T3.doc und T3.pdf.

Kurzfassung

Die nachfolgende Arbeit soll einen Überblick über den aktuellen Stand der Technik zum Thema Decompiling geben. Dazu wird zunächst der Begriff Decompiling gegenüber ähnlichen Begriffen abgegrenzt. Nach einem Überblick über die Gründe für Decompiling und rechtlichen Aspekten wird der Decompiling-Prozess näher dargestellt und in einzelne Phasen unterteilt. Es wird erklärt welche Vorteile diese Einteilung in einzelne Phasen mit sich bringt.

Zur praktischen Veranschaulichung werden gängige Decompiler-Tools für aktuell relevante Sprachen wie zB Java oder .NET vorgestellt. Die Ergebnisse dieser Tools werden mit dem originalen Sourcecode verglichen um ein Indiz für die Qualität der Tools zu liefern. Weiters werden vorhandene theoretische Probleme aufgezeigt, die beim Decompiling auftreten können. Ein Überblick über Techniken zum Schutz vor Decompiling runden diese Arbeit ab.

Begriffe

Einleitung

In der folgenden Arbeit wird versucht ein Überblick über den aktuellen Stand der Technik zum Thema Decompiling zu geben.

Der erste Teil beschäftigt sich mit der Begriffsabgrenzung gegenüber Reverse Engineering und Disassembling. Weiters werden die Gründe für Decompiling behandelt und auf rechtlichen Aspekte eingegangen, die beim Decompiling beachtet werden müssen.

im zweiten Teil der Arbeit wird der Decompiling-Prozess in mehrere Phasen eingeteilt. Die Aufgaben dieser Phasen werden näher erläutert. Darüber hinaus wird festgelegt welche Vorraussetzungen diese Phasen haben bzw. welche Ergebnisse diese liefern müssen. Weiters wird begründet, warum es sinnvoll ist den Decompiling-Prozess derart zu gliedern. Zum Abschluss dieses Teils wird auf verschiedene theoretische Probleme hingewiesen, die sich beim Decompiling Prozess ergeben können.

Im dritten Teil wird näher untersucht, wie sehr sich verschiedene Codearten dazu eignen Decompiling zu unterstützen. Darüber hinaus werden verschiedene Möglichkeiten und Tools vorgestellt, mit denen sich diese Codearten dekompilieren lassen. Ein Vergleich des dekompilierten Sourcecodes mit dem originalen Sourcecode gibt Aufschluss über die Qualität dieser Tools.

Zum Abschluss werden die Möglichkeiten zum Schutz vor Decompiling besprochen und eine Zusammenfassung der Arbeit gegeben.

Allgemeines

Definition / Abgrenzungen

Ein Decompiler, auch Reverse Compiler, ist ein Programm, das ein in Maschinensprache geschriebenes Programm liest und es in ein äquivalentes, in einer High-Level-Sprache geschriebenes Programm übersetzt. Es wird also versucht, den Prozess eines Compilers umzudrehen.

[vgl. Cifuentes94]

Abgrenzung zu Reverse Engineering und Disassembling:

Der Begriff Reverse Engineering stammt ursprünglich aus dem Maschinenbau und wurde in die Terminologie des Software Engineerings übernommen. Nach [Elliot et al. 1990] ist Reverse Engineering ein Prozess, der das betrachtete System analysiert, um seine Komponenten und ihre Beziehungen zu identifizieren. Zweck dieses Prozesses ist es, für das analysierte System neue Abbildungen des Systems zu schaffen, meist in anderer Form und auf höherer Abstraktionsebene.

Decompiling stellt also eine von vielen Ausprägungen des Oberbegriffs Reverse Engineering dar. (http://www.projektmagazin.de/glossar/gl-0268.html)

Bei Disassembling handelt sich ebenfalls um eine Anwendung von Reverse Engineering. Auch hier dient ein in Maschinensprache verfasstes Programm als "Ausgangspunkt". Ein Decompiler erzeugt daraus High-Level-Code, beim Disassembling hingegen wird der Code in eine für Menschen lesbarere Assemblersprache umgewandelt.

[Van Emmerik 2003] (http://www.program-transformation.org/Transform/DecompilationAndReverseEngineering)

Wie in der vorangegangenen Abbildung gut ersichtlich ist, endet das Decompiling im Rahmen des Reverse Engineerings dort, wo die Abstraktion der Architektur hoch wird.

Gründe für die Verwendung von Decompiling

Es gibt eine Vielzahl an Problemen im Software-Bereich, wo zu einer Anwendung der zugehörige Source-Code fehlt bzw. abhanden gekommen ist. Beispiele dafür sind:

• Wiederherstellen verlorenen Source Codes
• Bugfixing eines kompilierten Frameworks bzw. einer Applikation
• Migration einer Anwendung auf eine neue Hardware-Plattform
• Verbesserung der Dokumentation einer Anwendung
• Analyse von fremden Code (auch Viren und Schadprogramme)
• Testen von Compilern, besseres Verständnis für die Compiler-Vorgänge
• Cracken proprietärer Anwendungen
• uvm.

[Van Emmerik 2003]

Rechtliches (Legalität)

Die Legalität von Decompiling und von Reverse Engineering im Allgemeinen ist ein in den letzten Jahren rechtlich heftig diskutiertes Thema.

Viele Unternehmen untersagen explizit in den Lizenzbedingungen kommerzielle Software zu decompilieren, sei es auch nur zu Studienzwecken oder um die Software für den Eigengebrauch zu verändern. Solche Lizenzklauseln sind jedoch in vielen Ländern generell ungültig, da den Nutzern einer Sache gesetzlich das Recht zusteht, zur Überprüfung der Anwendungssicherheit oder zur Fehlerbehebung Reverse Engineering an einer erworbenen Software durchzuführen.

So ist es z.B. auch in Deutschland erlaubt, ein Programm zu dekompilieren, soweit dies notwendig ist, um die „Interoperabilität“ mit einem unabhängig vom ursprünglichen Programm geschaffenen Computerprogramm zu erhalten. Lizenzvereinbarungen, die dem widersprechen, sind laut dem "Gesetz über Urheberrecht und verwandte Schutzrechte" nichtig.

Oftmals dienen solche Lizenzklauseln eher dem Zweck der Abschreckung und sind somit als einseitige Willensäußerung bzw. je nach Form als prophylaktische, einseitig vorgetragene Rechtsauffassung zu verstehen, die bei unabhängiger rechtlicher Prüfung möglicherweise keine Bestätigung und somit keinen weiteren Bestand haben wird.

Benutzt man das Ergebnis eines Reverse Engineering-Vorgangs jedoch zum gewerblichen Nachbau, so wird man sich mit der großen Menge der gewerblichen Schutzrechte (z. B. Plagiat) in ähnlicher Weise konfrontiert sehen. Häufig dient das Reverse Engineering der Produktpiraterie, wobei hier natürlich nicht nur die Software-Branche betroffen ist.

Reverse Engineering von freien oder gar selbst verfassten Programmen ist natürlich in jeder Hinsicht gesetzeskonform.

Der Decompiling Prozess

Ein Decompiler charakterisiert sich, ähnlich einem Compiler, durch mehrere Phasen. Diese werden schrittweise durchlaufen und erzeugen, ausgehend von einem Maschinencode, jeweils ein umgewandeltes Äquivalent des ursprünglichen Codes. Das Ziel-Produkt ist letztendlich ist ein Programm in High-Level-Sprache, welches in seiner Art dem Quell-Programm entspricht.

Module: Gruppierung der Phasen

Die einzelnen Phasen eines Decompilers können in drei Module gruppiert werden:

• Front-End

Das Front-End beginnt den Dekompilierungsvorgang, in dem es den Maschinencode einliest. Es beinhaltet die syntaktische und semantische Analyse, die Zwischencode-Erzeugung sowie die Erstellung eines Control Flow Graph. All diese Phasen sind abhängig von jener Maschine, auf der der ursprüngliche Maschinencode ausgeführt wurde. Am Ende dieses Moduls liegt eine Repräsentation des ursprünglichen Programms in einer Low-Level-Zwischensprache sowie ein Control Flow Graph vor.

• Universal Decompiling Machine (UDM)

Dieses Modul ist sowohl von der ursprünglichen Maschine als auch von der zukünftigen High-Level-Sprache vollkommen unabhängig. Die Datenfluss- und Kontrollfluss-Analyse bilden das Herzstück des Dekompilierungsvorganges. Aus den vom Frontend gelieferten Low-Level-Zwischencode sowie dem Control Flow Graph wird ein High-Level-Zwischencode erzeugtt.

• Back-End

Das Back-End beinhaltet schließlich die Code-Erzeugung eines High-Level-Programms in der jeweiligen Ziel-Sprache, ist also sprachenabhängig.

Theoretisch bietet dieser Aufbau eines Decompiler-Prozesses die Möglichkeit, durch neue Front-Ends und Back-Ends Decompiler für viele Maschinen und viele verschiedene High-Level Ziel-Sprachen zu erzeugen. In der Praxis sind diese Möglichkeiten jeodoch je nach Wahl der Zwischensprache verschieden stark limitiert. [vgl. Cifuentes94 S. 7ff]

Phasen

[vgl. Cifuentes94 S. 8ff]

Syntax-Analyse

Ein Parser liest das Quell-Programm und gruppiert die Bytes zu Maschinencode-Phrasen. Solche Phrasen können als Syntaxbaum dargestellt werden.

Beispiel: Der Ausdruck "sub cx , 50" entspricht semantisch dem Satz "cx := cx - 50".

Die größte und gleichzeitig wohl auch schwierigste Aufgabe der Syntaxanalyse ist die Trennung von Instruktionen und Daten im Maschinencode. Um alle Instruktionen korrekt filtern zu können, ist eine vollständige Menge dieser Anweisungen in der vorhandenen Maschinensprache des Quell-Programms in Form einer Symbol-Tabelle notwendig.

Semantik-Analyse

Hier erfolgt die semantische Prüfung der durch den Parser gelieferten Syntaxbäume. Weiters werden Idiome analysiert und gespeichert. Ein Beispiel für die Erkennung eines Idioms: Ein in Binärcode vorliegender Wert wird um ein Bit nach links verschoben. Die Erkennung dieses Vorgangs als Multiplikation des Wertes mit 2 ist Aufgabe der Semantischen Analyse. Es gibt noch viele weitere Beispiele für solche Idiome.

Gesetzt dem Fall, dass der Maschinencode durch einen funktionierenden Compiler erzeugt wurde, ist es sehr selten, dass in dieser Phase semantische Fehler entdeckt werden. Es können jedoch sehr wohl Fehler auftreten, wenn das Programm auf einer anderen Maschine ausgeführt als für welche es konzipiert wurde. Ähnliche Maschinen, die zwar auf der selben Architektur aufsetzen, unterscheiden sich z.B. in der Anzahl der verwendeten Register und Instruktionen.

Zwischencode-Erzeugung

Anschließen an die syntaktische und semantische Analyse verwandelt ein Decompiler den vorhandenen Maschinensprachen-Quellcode in ein weiterverwendbares Äquivalent in einer Zwischensprache, welches in weiterer Folge von der UDM analysiert wird. [Cifuentes94 S.67]

Control Flow Graph Generation

Für die spätere Analyse-Phasen benötigt ein Decompiler auch einen Control Flow Graph jeder Sub-Routine des Quellprogramms.

"A control flow graph is a directed graph that represents the flow of control of a program, thus, it only represents the instructions of such a program. The nodes of this graph represent basic blocks of the program, and the edges represent the flow of control between nodes." [Cifuentes94 S.76]

Optional kann dieser Graph schließlich auch noch optimiert werden, in dem z.B. unnötige Verweise eliminiert und so Programmteile kürzer und schneller ausführbar werden.

Weiters wird für das Quellprogramm ein Call-Graph erstellt, der die Reihenfolge des Aufrufs der einzelnen Sub-Routinen darstellt.

Datenfluss-Analyse

In der Datenfluss-Analyse wird versucht, den bisher erzeugten Zwischencode weiter zu verarbeiten, um Elemente einer High-Level-Sprache identifizieren zu können. So werden z.B. temporäre Register und Condition Flags im Laufe dieser Analyse entfernt, da beides nicht Bestandteile von High-Level-Sprachen sind.

Somit wird in der Datenfluss-Analyse der gelieferte Low-Level-Zwischencode in einen High-Level-Zwischencode umgewandelt:

Kontrollfluss-Analyse

Diese Phase dient dazu, die gelieferten Kontrollfluss-Graphen in Konstrukte von High-Level-Sprachen umzuwandeln. Die Menge an möglichen Konstrukten muss zumindest die üblichen Konstroll-Instruktionen (z.B. Loops, if-then-else) enthalten, sprachenspezifische Konstrukte sind jedoch nicht erlaubt.

Beispiele für ein High-Level-Konstrukt:

Ergebnis dieser Phase ist ein strukturierter Control Flow Graph:

Code-Erzeugung

Schlussendlich wird aus dem strukturierten Kontrollfluss-Graphen sowie dem High-Level-Zwischencode jeder Sub-Routine Code in der gewünschten High-Level-Sprache erzeugt. Variablen- und Prozedur-Namen automatisch erzeugt, Kontroll-Instruktionen werden in Statements der jeweiligen Zielsprache übersetzt.

Probleme beim automatischen Decompiling

Durch das Halteproblem und Idiome sind dem automatischen Decompiling von Software gewisse Grenzen gesetzt. Diese generellen Grenzen sollen in diesem Kapitel aufgezeigt werden.

Halteproblem

Ein grundsätzliches und theoretisches Problem beim Thema Decompiling ist das sogenannte Halteproblem. Da sich eine genauere Darstellung des Halteproblems in zahlreichen Quellen wiederfinden lässt, wird darauf hier verzichtet. Nähere Informationen über das Halteproblem können zum Beispiel unter [1] gefunden werden.

Zusammenfassend kann das Halteproblem folgendermaßen beschrieben werden:

Der Versuch ein Programm zu schreiben, welches überprüft ob ein bestimmtes Programm mit bestimmten Eingabeparamtern terminiert ist nicht immer möglich. Es wird nämlich genau dann ein Wiederspruch erzeugt, wenn diesem Programm als Eingabeprogramm und als Eingabeparamter das Programm selbst übergeben wird.

Die von Neumann Architektur, welche in allen Intel 80x86 und Pentium CPUs zum Einsatz kommt, unterscheidet im Maschinencode nicht zwischen Daten und Code. Die Verwendung der jeweiligen Bits ergibt sich aus dem Kontext des Programmablaufs. Da ein Compiler normalerweise gültigen Code erzeugt schafft dies beim Ablauf des Programms keine Probleme, beim Dekompilieren können automatische Analyseprogramme allerdings Schwierigkeiten bei der Zuordnung haben. In manchen Fällen muss der Benutzer des Decompilers also manuell entscheiden, welche Bytes als Code, und welche bytes als Daten zu verwenden sind. vgl. [Eriksson 2002 S. 11]

"...this problem is equivalent to the halting problem, as it is impossible to separate data from instructions in a von Neumann architecture that computes both data addresses and branch destination addresses at execution time. [...] The algorithm is proved to be NP-Complete" [Cifuentes 1994 S. 47].

[Cifuentes 1994] Entwickelte zwar heuristische Methoden zur Separierung von Code und Daten im Bitcode, da verschiedene Compiler allerdings verschiedene Ausprägungen von Bitcode erzeugen (etwa zum Erzeugen von case-verzweigungen) muss der verwendete Parser zuvor manuell mit den ensprechenden Voreinstellungen versehen werden um auf den Bitcode angewandt werden zu können. vgl. [Cifuentes 1994 S.47-57]

Idiome

Ein weiteres Problem beim Decompiling sind sogenannte Idiome, welche Cifuentes wie folgt definiert:

"An idiom or idiomatic expression is a sequence of instructions which form a logical entity, and which taken together have a meaning that cannot be derived by considering the primary meanings of the instructions." [Cifuentes 1994 S. 3]

Ein Beispiel für ein Idiom ist die Multiplikation mit 2. Dies wird zB im Assemblercode nicht durch eine Multiplikationsanweisung sondern durch Bitverschiebung eines Registers nach links erreicht. Der Decompiler weiß nun nicht, ob mit dieser Bitverschiebung eine Multiplikation gemeint ist, oder nicht. Die meisten dieser Idiome sind bekannt, und es lassen sich aufgrund des Kontexts Rückschlüsse darauf ziehen, welche Anweisung ursprünglich gemeint war. Dennoch verbleiben Restfälle in denen manuelles Eingreifen unabdingbar ist.

Gerade aufgrund dieser 2 Probleme, sind die Ergebnisse von heutigen Decompilern sehr beachtenswert. Diese werden im nächsten Kapitel näher untersucht und beschrieben.

Überblick über ausgewählte Decompiler

Die Auswahl einer bestimmten Programmiersprache für ein Software-Projekt ist stets mit daraus entstehenden Konsequenzen verbunden. Selbstverständlich wirkt sich diese Entscheidung auch auf die Möglichkeit aus, kompilierten Code wieder in den ursprünglichen Quellcode umzuwandeln.

Im Folgenden soll ein Überblick über die Möglichkeiten des Decompilings hinsichtlich verschiedenem ausführbaren Code geboten werden. Aus Gründen der Übersichtlichkeit wurde die Auswahl auf folgende Codearten beschränkt, die nach Meinung der Verfasser zum derzeitigen Zeitpunkt relevant, repräsentativ und verbreitet sind:

• Maschinensprache
• Assembler
• Java Bytecode
• .NET Assembly, CIL
• Die Skriptsprachen Perl und PHP

Für diese Auswahl sollen jeweils Besonderheiten des Decompilings und gängige Tools erörtert werden. Da eine Aufzählung bestimmter Programmiersprachen niemals vollständig sein kann, sind die folgenden Unterpunkte als exemplarische Veranschaulichung zu verstehen.

Am Ende dieses Kapitels werden Parallelen zwischen den Möglichkeiten des Dekompilierens verschiedener Sprachkonstrukte gezogen, sowie eine Synthese aus den angeführten Beispielen schließbarer allgemeiner Aussagen erarbeitet.

Maschinensprache

Das Dekompilieren von Maschinensprache die direkt von einem Prozessor mit von Neumann Architektur abgearbeitet wird, wird in der wissenschaftlichen Literatur wie eine Art Königsdisziplin behandelt. Die Problematik, welche auf das Halteproblem zurückgeführt werden kann, wurde im vorigen Kapitel näher erläutert. Entsprechend schwierig gestaltet sich das Dekompilieren von Maschinensprache. Der Vorgang des Dekompilierens von Maschinencode, wird mit der Erzeugung von fliegenden Schweinen aus Hamburgern [van Emmerik 2003] verglichen. In populären Newsgroups wird sogar behauptet, dass dies gänzlich unmöglich sei. In der Realität ist allerdings ein großer Teil der existierenden Programme mithilfe von Heuristiken und menschlichem Eingreifens decompilierbar.

Cifuentes legte mit ihrer PhD-Thesis einen wichtigen Grundstein für die wissenschaftliche Bearbeitung dieses Themengebietes und erstellte gleichzeitig mit dcc einen der ersten Maschinensprache->C Decompiler auf wissenschaftlicher Basis mit einem zugrundeliegenden mathematischen Modell. Das Hauptproblem liegt im Überführen der Maschinensprache in eine semantisch korrekt analysierte Zwischensprache . Dies wird mittels Heuristiken, ausgeklügelten Algorithmen und menschlicher Kontrolle und Vervollständigung gelöst. Der Zwischensprache-Code kann anschließend (abhängig vom Backend des Decompilers) in eine High-Level Programmiersprache wie C umgewandelt werden. [Cifuentes 1994]

Assembler Code

Assembler Code ist das Äquivalent zum origniären und von der Hardware-Architektur abhängigen Maschinencode. Die im Maschinencode rein durch Bits repräsentierten Anweisungen und Daten sind im Assemblercode allerdings (theoretisch) menschenverständlich und als solche erkennbar. Der Assemblercode verfügt nicht über die einfach verständlichen Konstrukte einer Hochsprache. Dem Assembler fehlen beispielsweise Schleifenkonstrukte oder die Unterscheidung zwischen Pointern und Daten.

Was den Assemblercode gegenüber dem reinen Maschinencode allerdings auszeichnet, ist die bereits vorgenommene Trennung von Daten und Anweisungen sowie die Möglichkeit von Kommentaren im Code.

[Cifuentes 1994] Nutzt den Assemblercode als Zwischensprache und Input der Universal Decompiling Machine. Auch für die Erzeugung von Delphi-Code aus Maschinencode existieren kaum eigene Delphi-Decompiler. Auch hierfür wird zuerst ein Disassembler genutzt, um dann das Disassembly in Delphi zu übersetzen. Assembler kann also als plattformabhängige Zwischensprache zwischen Maschinensprache und Hochsprache verstanden werden. [Van Emmerik 2004]

Das Decompiling von Assemblercode ist daher einfacher als das Decompiling von Maschinencode Programmen. Allerdings ist es schwieriger Assemblercode zu decompilen als Programme, die auf virtuellen Maschinen ausgeführt werden. Der hauptsächliche Unterschied zu Java oder .NET Bytecode ist, dass Assemblercode mit viel einfacheren Operatoren zurechtkommen muss, was dazu führt, dass komplexere Anweisungen erst wieder semantisch als solche erkannt werden müssen um zu einer Entsprechung in Hochsprache übergeführt zu werden. Diese Problematik wurde im vorigen Kapitel unter dem Punkt Idiome näher erläutert. [Van Emmerik 2007]

Beispiel: Gegenüberstellung Assemblercode und C++

Das nachfolgende Beispiel soll die Arbeitsweise eines Disassemblers anhand eines in C++ implementierten Quicksort Algorithmus näher erläutern.

Der folgende C++ Code wurde mit dem Microsoft Visual Studio 2005 cl.exe compiler (Standardeinstellungen) kompiliert:

#include <iostream>

void quickSort(int numbers[], int array_size);
void q_sort(int numbers[], int left, int right);

int numbers[150];

using namespace std;

int main()
{
   int i,n;
   cout<<"How many numbers you want to sort: ";
   cin>>n;
   cout<<"Enter "<<n<<" numbers.\n";
   for (i = 0; i<n; i++)
      cin>>numbers[i];
//perform quick sort on array
   q_sort(numbers,0,n-1);

   cout<<"Numbers are sorted\n";
   for (i = 0; i<n; i++)
      cout<<numbers[i]<<"   ";
   return(0);
}

// Function to sort
void q_sort(int numbers[], int left, int right)
{
   int pivot, l_hold, r_hold;
   l_hold = left;
   r_hold = right;
   pivot = numbers[left];
   while (left < right)
   {
       while ((numbers[right] >= pivot) && (left < right))
       right--;
       if (left != right)
       {  
	  numbers[left] = numbers[right];
	 left++;
      }
      while ((numbers[left] <= pivot) && (left < right))
	 left++;
      if (left != right)
      {
	  numbers[right] = numbers[left];
	  right--;
      }
   }
   numbers[left] = pivot;
   pivot = left;
   left = l_hold;
   right = r_hold;
   if (left < pivot)
      q_sort(numbers, left, pivot-1);
   if (right > pivot)
      q_sort(numbers, pivot+1, right);
}

[Vishnu 2008]

Die daraus entstehende quicksort.exe Datei wurde im Anschluss mit dem Win 32 Program Disassembler von Sang Cho [Cho 2003] diassembliert. Im Folgenden ist ein Ausschnitt des Disassemblies zu sehen.

Die Ausgabe ist dreigeteilt:

• Links ist der Offset an Bytes vom Programmstart eingetragen (der Program Entry Point liegt bei Offset 00001000).
• In der mittleren Spalte befindet sich der Inhalt der Bytes (jeweils zwei Zeichen bilden den HEX-Code für ein Byte).
• Rechts befinden sich die daraus interpretierten Assembler-Triplets.

+++++++++++++++++++ ASSEMBLY CODE LISTING +++++++++++++++++++
//********************** Start of Code in Object CODE **************
Program Entry Point = 0040B4BE (quicksort.exe File Offset:00001000)

=========
:00401000 55                      push ebp
:00401001 8BEC                    mov ebp, esp
:00401003 83EC08                  sub esp, 008
:00401006 68D0E14100              push 0041E1D0
                      (StringData)"How many numbers you want to sort: "
:0040100B 68104D4200              push 00424D10
:00401010 E86B260000              call 00403680
:00401015 83C408                  add esp, 008
:00401018 8D45FC                  lea eax, dword[ebp-04]
:0040101B 50                      push eax
:0040101C B9744C4200              mov ecx, 00424C74
:00401021 E8BA050000              call 004015E0
:00401026 68F4E14100              push 0041E1F4
                      (StringData)" numbers. <lf>"
:0040102B 8B4DFC                  mov ecx, dword[ebp-04]
:0040102E 51                      push ecx
:0040102F 6800E24100              push 0041E200
                      (StringData)"Enter "
:00401034 68104D4200              push 00424D10
:00401039 E842260000              call 00403680
:0040103E 83C408                  add esp, 008
:00401041 8BC8                    mov ecx, eax
:00401043 E8C8010000              call 00401210
:00401048 50                      push eax
:00401049 E832260000              call 00403680
:0040104E 83C408                  add esp, 008
:00401051 C745F800000000          mov dword[ebp-08], 00000000
:00401058 EB09                    jmp 00401063
--------- 
:0040105A 8B55F8                  mov edx, dword[ebp-08]
:0040105D 83C201                  add edx, 001
:00401060 8955F8                  mov dword[ebp-08], edx
---------
:00401063 8B45F8                  mov eax, dword[ebp-08]
:00401066 3B45FC                  cmp eax, dword[ebp-04]
:00401069 7D17                    jge 00401082
:0040106B 8B4DF8                  mov ecx, dword[ebp-08]
:0040106E 8D148DA0494200          lea edx, dword[4*ecx+004249A0]
:00401075 52                      push edx
:00401076 B9744C4200              mov ecx, 00424C74
:0040107B E860050000              call 004015E0
:00401080 EBD8                    jmp 0040105A
---------
:00401082 8B45FC                  mov eax, dword[ebp-04]
:00401085 83E801                  sub eax, 001
:00401088 50                      push eax
:00401089 6A00                    push 000
:0040108B 68A0494200              push 004249A0
:00401090 E85B000000              call 004010F0
:00401095 83C40C                  add esp, 00C
:00401098 6808E24100              push 0041E208
                      (StringData)"Numbers are sorted <lf>"
:0040109D 68104D4200              push 00424D10
:004010A2 E8D9250000              call 00403680
:004010A7 83C408                  add esp, 008
:004010AA C745F800000000          mov dword[ebp-08], 00000000
:004010B1 EB09                    jmp 004010BC
---------
[...]

Der Maschinencode zwischen Offset 0 und Offset 1000 wurde vom Disassembler nicht disassembliert. Hier befinden sich wohl einige Informationen über den Typ dieser .exe Datei, worauf der String "This program cannot be run in DOS mode." (Bytes 0000004e bis 00000074) hinweist. Es zeigt sich unter anderem, dass sehr viele Subroutinen und Zusatzinformationen durch den Compiler in den Maschinencode gepackt werden. Ein Screenshot des mit dem HT Editor [HT 2008] geöffneten Programms quicksort.exe zeigt den Beginn der .exe Datei:

Java Bytecode

Java Bytecode lässt sich generell sehr unkompliziert decompilen:

"As far as languages go, Java code is exceptionally easy to decompile due to the relative simplicity of the Java virtual machine (as compared with a real microprocessor) and the fact that the language's bytecode format is well documented." [Travis 2001]

[Dyer 1997] führt gleich mehrere Punkte an, warum Java als "decompiler-friendly" bezeichnet werden kann:

• Da in einem originalen Java-Quellcode keine goto Befehle von Programmierern eingebaut werden können, müssen alle im Bytecode vorgefundenen goto's in Hochsprachenkonstrukte umwandelbar sein.
• Die Auswahl an Kontrollstrukturen ist überschaubar. Die Art und Weise wie sie kompiliert werden ist relativ einheitlich.
• Die Java Compilertechnologie ist unausgereift. Stark optimierende Compiler die in Zukunft entwickelt werden könnten, würden den Code sehr viel stärker verändern als es herkömmliche Compiler tun.
• Es besteht ein großer semantischer Zusammenhang zwischen dem Java Quellcode und dem Java Bytecode.

Dem Dekompilat kommt zugute, dass in Java Class Files sehr viele Informationen aus dem ursprünglichen Sourcecode gespeichert sind:

• Namen und Typen von Membervariablen einer Klasse
• Methodennamen
• Signaturen
• Zeilennummer des Quellcodes aus dem die bestimmte Sektion einer Methode erzeugt wurde

Es können auch die Namen lokaler Variablen enthalten sein, falls mit der -g option des javac compilers kompiliert wurde. [Travis 2001]

Im JDK wird darüber hinaus ein funktionsfähiger Disassembler für Java Bytecode mitgeliefert: javap.

Die Popularität von Java kombiniert mit vielen, relativ einfach anzuwendenden Decompilertools hat zu einem regelrechten Wettrüsten zwischen Decompiler- und Obfuscatorentwicklern geführt. Manche Obfuscator zielen direkt auf bestimmte Decompiler ab um diese während des Dekompilierens zum Absturz zu bringen. [Travis 2001, Dyer 1997]

Die voranstehenden Aussagen gelten allerdings nur solange der Java Bytecode auch mit dem gängigsten Compiler, dem javac Compiler von sun, erzeugt wurde und sind vielleicht nicht mehr ganz zeitgemäß. Java Bytecode kann beispielsweise auch von Compilern anderer Sprachen erzeugt werden, darunter Ada, ML, Eiffel und Scheme. Der Java Bytecode kann auch das Ergebnis einer Optimierung sein, an dem ein üblicher Java-Decompiler scheitern könnte. [Miecznikowski und Hendren 2002 S.2]

[Miecznikowski und Hendren S.9] führen weiter aus, dass die in Java zur Verfügung stehenden Sprachkonstrukte nicht einmal ausreichen um etwa alle Möglichkeiten der flexibleren exception-handling Mechanismen im Java Bytecode direkt repräsentieren zu können. Auch im Bereich der Synchronisation von multi-Thread Anwendungen bietet der Java Bytecode Möglichkeiten, die in der Sprache Java in dieser Form nicht direkt ausdrückbar sind.

Dava, ein Java Bytecode Decompiler entwickelt von [Miecznikowski und Hendren] beansprucht für sich, Java bytecode dekompilieren zu können, unabhängig davon aus welchem Compiler oder Optimierer dieser stammt.

Beispiel: Java Original Sourcecode vs. Java Decompiler Sourcecode

Als Ausgangsbasis für dieses Beispiel dient die nachfolgende Java Implementierung des Quicksort Algorithmus, welcher auch schon im vorigen Kapitel verwendet wurde.

/**
 * This class tests the Quicksorter class
 */
public class QuicksorterTester {
	
	public static void main(String[] args) {
		// array mit Integer Werten zum Testen des Algorithmus
		int[] testArray = {0,7,2,5,2,6,4,2,3,10,33,53,8,34};
		
		Quicksorter s = new Quicksorter();
		s.sort(testArray);
		
		// Ausgabe des sortierten Arrays
		for(int i=0; i < testArray.length; i++){
			System.out.println(testArray[i]);
		}
	}

}

**
 * a class that implements the quicksort algorithm
 */
public class Quicksorter {

    private int[] a;
    private int n;

    public void sort(int[] a){
        this.a=a;
        n=a.length;
        quicksort(0, n-1);
    }

    private void quicksort (int lo, int hi){
        int i=lo, j=hi;
        int x=a[(lo+hi)/2];

        //  Aufteilung
        while (i<=j){    
            while (a[i]<x) i++; 
            while (a[j]>x) j--;
            if (i<=j){
                exchange(i, j);
                i++; j--;
            }
        }

        // Rekursion
        if (lo<j) quicksort(lo, j);
        if (i<hi) quicksort(i, hi);
    }

    private void exchange(int i, int j){
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}

Dieser Code wird mit dem javac Compiler in Java Class Files umgewandelt. Nun wird der javap Disassembler benutzt um aus dem Java Bytecode ein Dissassembly zu erzeugen:

Compiled from "Quicksorter.java"
public class Quicksorter extends java.lang.Object
  SourceFile: "Quicksorter.java"
  minor version: 0
  major version: 50
  Constant pool:
const #1 = Method	#7.#24;	//  java/lang/Object."<init>":()V
const #2 = Field	#6.#25;	//  Quicksorter.a:[I
const #3 = Field	#6.#26;	//  Quicksorter.n:I
const #4 = Method	#6.#27;	//  Quicksorter.quicksort:(II)V
const #5 = Method	#6.#28;	//  Quicksorter.exchange:(II)V
const #6 = class	#29;	//  Quicksorter
const #7 = class	#30;	//  java/lang/Object
const #8 = Asciz	a;
const #9 = Asciz	[I;
const #10 = Asciz	n;
const #11 = Asciz	I;
const #12 = Asciz	<init>;
const #13 = Asciz	()V;
const #14 = Asciz	Code;
const #15 = Asciz	LineNumberTable;
const #16 = Asciz	sort;
const #17 = Asciz	([I)V;
const #18 = Asciz	quicksort;
const #19 = Asciz	(II)V;
const #20 = Asciz	StackMapTable;
const #21 = Asciz	exchange;
const #22 = Asciz	SourceFile;
const #23 = Asciz	Quicksorter.java;
const #24 = NameAndType	#12:#13;//  "<init>":()V
const #25 = NameAndType	#8:#9;//  a:[I
const #26 = NameAndType	#10:#11;//  n:I
const #27 = NameAndType	#18:#19;//  quicksort:(II)V
const #28 = NameAndType	#21:#19;//  exchange:(II)V
const #29 = Asciz	Quicksorter;
const #30 = Asciz	java/lang/Object;

{
public Quicksorter();
  Code:
   Stack=1, Locals=1, Args_size=1
   0:	aload_0
   1:	invokespecial	#1; //Method java/lang/Object."<init>":()V
   4:	return
  LineNumberTable: 
   line 4: 0


public void sort(int[]);
  Code:
   Stack=4, Locals=2, Args_size=2
   0:	aload_0
   1:	aload_1
   2:	putfield	#2; //Field a:[I
   5:	aload_0
   6:	aload_1
   7:	arraylength
   8:	putfield	#3; //Field n:I
   11:	aload_0
   12:	iconst_0
   13:	aload_0
   14:	getfield	#3; //Field n:I
   17:	iconst_1
   18:	isub
   19:	invokespecial	#4; //Method quicksort:(II)V
   22:	return
  LineNumberTable: 
   line 10: 0
   line 11: 5
   line 12: 11
   line 13: 22


}

Interessant ist, dass der Java Assembler Code signifikant kürzer ist, als der aus einem C++ Executable generierten Assembler Code im vorigen Kapitel. Dies liegt daran, dass Java Assembler Code verschiedene Sprachkonstrukte von traditionellem Assembler Code zusammenfasst.

Um lesbaren Java Sourcecode aus dem Java Class File zu erzeugen wurde der JAD Decompiler benutzt. In der nachfolgenden Grafik ist der original Sourcecode dem decompiltem Sourcecode gegenübergestellt:

Auf den ersten Blick ist die Differenz der Sourcecodes sehr groß. Bei näherer Betrachtung offenbart sich aber, dass der ursprüngliche Sourcecode 100% richtig wiederhergestellt wurde. Darüber hinaus wurde sogar Methodennamen erhalten und die richtige Einrückung gewählt. Lediglich einige einzelne lokale Variablen wurden umbenannt und einige While-Schleifen durch äquivalente Do-While-Schleifen ersetzt.

Für den JAD Decompiler, gibt es auch ein Eclipse Plugin gibt, welches on-the-fly beim Öffnen eines Java Class Files den Source Code decompiled:

Dieses Plugin eignet sich hervorragend um beim Debuggen Klassen schrittweise abzuarbeiten, zu denen der originale Sourcecode nicht vorhanden ist.

.NET assembly, CIL Code

Da auch das .NET assembly wie der Java Bytecode auf einer virtuellen Maschine ausgeführt wird ist er einfach zu dekompilieren: Zuerst muss die CIL (Common Intermediate Language) wieder aus dem Assembly gewonnen werden. Dieser Vorgang ist mittels eines Hilfsprogramms wie ILDASM (Teil des .NET Frameworks) einfach und unkompliziert machbar.

Danach kann die CIL mit diversen, teilweise frei erhältlichen, Tools wie beispielsweise Reflector wieder in eine High-Level Programmiersprache übergeführt werden. Reflector bietet etwa C#, Visual Basic oder Delphi als Zielsprache an. Auch hierbei bleiben Methoden-, Variablen- und Parameternamen erhalten sofern sie mit entsprechenden Kompilieroptionen Einzug in den Bytecode gefunden haben.

[Mitchell 2004]

Beispiel: C# quicksort Algoritmus

// array of integers to hold values
private int[] a = new int[100];

// number of elements in array
private int x;

// Quick Sort Algorithm
public void sortArray()
{
  q_sort( 0, x-1 );
}

public void q_sort( int left, int right )
{
  int pivot, l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = a[left];

  while( left < right )
  {
    while( (a[right] >= pivot) && (left < right) )
    {
      right--;
    }

    if( left != right )
    {
      a[left] = a[right];
      left++;
    }

    while( (a[left] <= pivot) && (left < right) )
    {
      left++;
    }

    if( left != right )
    {
      a[right] = a[left];
      right--;
    }
  }

  a[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;

  if( left < pivot )
  {
    q_sort( left, pivot-1 );
  }

  if( right > pivot )
  {
    q_sort( pivot+1, right );
  }
}

[Quelle: http://www.publicjoe.f9.co.uk/csharp/sort05.html]

Dieser Code wurde mit Visual Studio 2008 kompiliert und mit .Net Reflector dekompiliert. Das Ergebnis war sehr zufriedenstellend. Die nachfolgende Darstellung vergleicht den kompilierten mit dem dekompilierten Sourcecode. Bis auf die lokalen Variablennamen und die Sortierung der Methoden entspricht der dekompilierte Sourcecode dem Original.

Die Skriptsprachen Perl und PHP

Obwohl Skriptsprachen wie Perl oder PHP üblicherweise direkt von einem Interpreter ausgeführt werden, ohne zuvor ein Kompilat zu erzeugen, gibt es auch bei diesen die Möglichkeit, vorgeparste Artefakte zu erzeugen. Über Bestrebungen, diese Kompilate wiederum in entsprechenden Skript-Sourcecode zu überführen konnte keine nennenswerte Literatur gefunden werden.

[Moise und Wong 2006] verfolgen den Ansatz, aus dem auch für geübte Programmierer oft schwer verständlichen Perl-Code Facts zu extrahieren. Hierzu manipulierten sie einen Perl-Interpreter, der anstatt ein Perl-Skript auszuführen, dieses analysiert und einem von ihnen definierten Schema gemäß strukturiert ausgibt.

"Certain scripting languages, such as Perl, are notoriously difficult to understand. Consequently, reverse engineering for Perl code is very much needed." [Moise und Wong 2006]

Für PHP existieren einige Compiler-Projekte, die sich allerdings teilweise noch im experimentellen Stadium befinden. Das Hauptaugenmerk liegt dabei auf Performancesteigerungen, Schutz proprietärer Applikationen/Bibliotheken durch Verschlüsselung und dem Ausführen von PHP Skripts ohne Interpreter [Bcompiler 2005]. Es existieren Bestrebungen, diesen PHP bytecode wieder zu dekompilieren. Die momentan verfügbaren Tools wie Derick's VLD zielen aber nur darauf ab, den Bytecode etwas lesbarer zu machen. [Knowles 2006]

Zussammenfassend lässt sich sagen, dass das Decompiling von Skriptsprachen, so es überhaupt bereits Compiler für sie gibt, noch im Anfangsstadium steckt. Wissenschaftlich ist es noch kaum behandelt. Eventuell steckt in diesem Feld noch viel Potential für Weiterentwicklung und Forschung.

Parallelen und Folgerungen

Das Boomerang Decompiler Project bringt die Fragestellung nach dem Einfluss von Programmiersprachen auf das Dekompilieren auf einer seiner Informationsseiten auf den Punkt:

"Does it matter what language my software is written in? Yes. If you are trying to recover Java or Visual Basic source code you're in luck. There are many Java and Visual Basic decompilers, many of which can give you excellent recovered source code in minutes. Your own developers should be sufficiently qualified to wield these tools and complete source recovery should take less than a month.

On the other hand, if you're trying to recover C/C++/asm or some other compiled language, you will require expert source recovery services. The state of the art is much more advanced in recovering asm and C than C++ or other languages. C++ recovery is possible but takes longer."

[Boomerang 2004]

Zusammenfassend kann daher festgestellt werden, dass die Auswahl der Programmiersprache und die oft damit zusammenhängende Zielsprache, in welche diese compiled wird, sehr starke Auswirkungen darauf hat, wie aufwändig die Wiederherstellung des Quellcodes ist. Interpretierte Sprachen lassen sich generell einfach Decompilen, da sie beim Compilen mehr Informationen aus dem ursprünglichen Quellcode übernommen haben. Abgesehen davon ist ein abstrakteres, semantisch eindeutigeres Kompilat generell einfacher zu decompilen.

Faktoren für erfolgreiches Decompiling

Erfolgreiches Decompiling in dem Sinne, möglichst den ursprünglichen Quellcode wiederherzustellen hängt wesentlich davon ab, welche Informationen noch über den verlorenen Quellcode vorhanden sind. So kann ein C++ Kompilat mit Debug-Einstellungen für ein Code-Recovery Projekt natürlich sehr wertvoll sein. Der Informationsbegriff sollte sich dabei allerdings nicht nur auf die im Kompilat selbst zu findenden Informationen beschränken.

Insbesondere folgende Ressourcen dürfen nicht außer Acht gelassen werden:

• Dokumentation: Sequenzdiagramme, Klassendiagramme, Prosabeschreibungen etc. sofern diese mit der Version des Kompilats übereinstimmen.
• Aus dem ursprünglichen Code erzeugte Dokumentation (wie z.B. javaDoc-Dokumente).
• Wissen über semantische Zusammenhänge im original-Quellcode der ursprünglichen Entwickler.

[Boomerang 2004]

Obfuscation: Schutz vor Decompiling

Da es nicht immer gewollt ist Sourcecode möglichst einfach zu decompilen, existieren sogenannte Obfuscators die den zugrundeliegenden Sourcecode vor einem Decompiler schützen sollen. Sie arbeiten mit unterschiedlichen Techniken wie zB:

• Umbennennung und Verunstaltung von Variablen, Methoden und Klassen.
• Zusätzliche Codeoptimierung welche den Code unlesbar machen soll, oder bestimmte Decompiler beim Parsen abstürzen lässt
• Verschlüsselung des Codes

Grundsätzlich herrscht hier ein Wettlauf zwischen Decompiler-Bauer und Obfuscator-Autoren. Je nach Technologie gewinnt das eine oder das andere Lager.

Problematisch ist bei Code Obfuscation folgendes zu sehen:

• Code kann dadurch unperformanter werden als vorher
• Dynmaischer Einsatz von Reflection im Code ist nur mehr eingeschränkt möglich, wenn Variablen- und Klassennamen umbenannt werden.

Als Obfuscator der jeweils einfach dekompilierbaren Sprachen für virtuelle Maschinen sind folgende Quellen zu nennen:

• Java: [2]
• [.Net: http://www.howtoselectguides.com/dotnet/obfuscators/]

Zusammenfassung

In der vorliegenden Arbeit wurde aufgezeigt, wie der Decompiling-Prozess im Genauen funktioniert und welche theoretischen Probleme sich daraus ergeben. Der praktische Teil der Arbeit hat gezeigt, welche Codearten sich besser für das Dekompilieren eignen und wo die Limitierungen aktueller Techniken sind. Für die Zukunft bleibt abzuwarten wie sich der Wettlauf Decompiler vs. Obfuscator weiterentwickeln wird und welche Fortschritte es beim automatischen Decompiling von Assemblercode gibt.

Literatur

[Bcompiler 2005] php.net: PHP bytecode compiler, http://at2.php.net/bcompiler, 2008

[Boomerang 2004] The Boomerang Decompiler Project: Help! I've lost my source code, http://boomerang.sourceforge.net/lostsource.php, 2004

[Cho 2003] S. Cho: Win32 Program Disassembler, http://www.geocities.com/~sangcho/disasm.html, Computer & Information Engineering Department CheongJu University, South Korea, 2003

[Cifuentes 1994] C. Cifuentes: Reverse Compilation Techniques; PhD Dissertation, School of Computing Science, Queensland University of Technology, 1994

[Dyer 1997] D. Dyer: Java decompilers compared; JavaWorld.com, http://www.javaworld.com/javaworld/jw-07-1997/jw-07-decompilers.html?page=1, 1997

[Elliot et al. 1990] Elliot J. Chikofsky and James H. Cross II: Reverse Engineering and Design Recovery: A Taxonomy, IEEE Software, vol. 7, 1990

[Eriksson 2002] D. Eriksson: Designing an object-oriented decompiler; Master Thesis, Department of Software Engineering and Computer Science, Blekinge Institute of Technology, 2002

[Knowles 2006] A. Knowles: Recovering encoded php files, http://www.akbkhome.com/blog.php/View/117/Recovering_encoded_php_files.html, 2006

[Miecznikowski und Hendren 2002] J. Miecznikowski und L. Hendren: Decompiling Java Bytecode: Problems, Traps and Pitfalls, Sable Research Group, School of Computer Science, McGill University, 2002

[Mitchell 2004] S. Mitchell: Decompiling .NET Assemblies, 4GyusFromRolla.com, http://aspnet.4guysfromrolla.com/articles/080404-1.aspx, 2004

[Moise und Wong 2006] D. L. Moise und K. Wong: Extracting Facts from Perl Code, Department of Computing Science University of Alberta, Canada, 2006

[Travis 2001] G. Travis: How to lock down your Java code (or open someone else's); IBM developerWorks > Java Technology, http://www.ibm.com/developerworks/java/library/j-obfus/?loc=crtheme, 2001

[Van Emmerik 2003] M. van Emmerik: Is Decompilation Possible?; The Program Transformation Wiki, http://www.program-transformation.org/Transform/DecompilationPossible, 2003

[Van Emmerik 2004] M. van Emmerik: Delphi Decompilers; The Program Transformation Wiki, http://www.program-transformation.org/Transform/DelphiDecompilers, 2004

[Van Emmerik 2007] M. van Emmerik: Assembly Decompilers; The Program Transformation Wiki,http://www.program-transformation.org/Transform/AssemblyDecompilers, 2004

[Vishnu 2008] A. Vishnu: program for quicksort, http://arunmvishnu.siteburg.com/codes/QUICK.txt, 2008