Assembler: Schleifen automatisiert erkennen

Hallo,

da das Unterforum auch für andere Sprachen gedacht ist, stell ich sie einfach mal, vlt gibts ja den ein oder anderen Assembler Profi 😉

Ich habe ein Softwarepaket, bestehend aus vielen Modulen. Diese Module werden in einem Disassembler (IDA Pro) disassembliert und für den erzeugten Assemblercode soll ich nun ein kleines Tool schreiben welches die Methoden extrahiert (fertig und funktioniert) und dann in den Methoden Schleifen sucht (egal ob while/foreach/for/etc.) und prüft ob eine bestimmte Methode innerhalb der Schleifen aufgegrufen wird (lasst uns bitte nicht über Sinn und Unsinn streiten...).

Mein großes Problem ist, kann ich im Assemblercode überhaupt Schleifen zu 100% identifizieren ? ifs/switches/schleifen, alles ist ja gleich aufgebaut, meistens durch ein compare und dem entsprechenden jump danach.

Ich dachte zuerst das Schleifen die einzigen Jumps sind die im Code wieder rückwärts springen, hab jetzt aber auch schon ifs gefunden die dies tun...
Gibt es da eine zuverlässige Möglichkeit Schleifen zu erkennen ? Welche Indikatoren wären das ? Mir fehlt derzeit völlig der Ansatz. Mir gefällt es sowieso nicht mittels Stringvergleichen in dem Assemblercode rumzuhüpfen, aber viel andere Möglichkeiten wirds kaum geben...

Hallo,

ich denke mit deinen Gedanken bringst du das Problem ganz gut auf den Punkt.

Ich würd vielleicht so rangehen: Irgend nen Miniprogramm schreiben welches die verschiedenen Schleifenarten demonstriert. Dann mit dem Compiler kompilieren der auch den Zielcode übersetzt hat. Dann sollte man recht gut sehen wie der Compiler die verschiedenen Schleifen umsetzt und dann versuchen diese Muster im Zielcode wiederzufinden. Je nach Compiler, Compileroptionen usw. unterscheidet sich ja der generierte Code erheblich und wenn man ds eingrenzen kann, ist man schon nen Stück weiter.

Oder wurde der Assemblercode von Hand geschrieben?

Wenn man von einem knoten (anweisung) über sprünge wieder zu dieser anweisung gelangen kann, dann ist das eine schleife.

Ich würde vorschlagen, mir alle knoten durchzugehen, mir dabei zu merken wo man schon war und wenn man bei einer Instruktion ankommt, wo man schon war und diese im zurückgelegten weg vorhanden ist, dann ist es eine schleife.

... ist das eine schleife.

Naja, sicherlich ist es eine Schleife, aber es muss kein typisches Schleifenkonstrukt sein. Genauso wäre nen Vergleich mit Goto denkbar. Oder Methoden die sich gegenseitig aufrufen.

Denke da sollte der Threadersteller nochmal präzisieren ob wirklich nur Schleifenkonstrukte oder alles schleifenartige gefunden werden soll.

Genauso wäre nen Vergleich mit Goto denkbar.

Das lässt sich in der tat in keiner weise bestimmen. Es ist aber auch egal in der praxis, da beides richtige übersetzungen sind.

Oder Methoden die sich gegenseitig aufrufen.

das erkennt man dann an der call-instruktion anstatt eines jumps

Hallo talla,

mir kommt das so vor, als ob du da was falsch verstehst. Du hast von einem Compiler gesprochen. Der Assembler-Code ist schon kompiliert. Was getan wird, ist im Grunde nur den Assembler-Code, den Maschienen-Code, auszuführen. Dort wird also nichts kompiliert.

OllyDbg und IDA Pro können den Assembler-Code analysieren. Meist wird an der Seite die Stellen angezeigt, an denen Schleifen oder if-Abfragen sind. Die beiden Tools zeigen die Schleifen/Abfragen an, obwohl der Code noch gar nicht augeführt worden ist. Also muss dahinter sowas wie ein Parser stecken. Und davon gehe ich sehr stark aus.

Hallo scrabbl,

ich würde an deiner Stelle versuchen, einen Parser zu programmieren. Anders kann ich mir das auch nicht vorstellen. Du findest im Internet bestimmt schon fertige Implementierungen. Kannst du uns näher beschrieben, was du vor hast?

zero_x

Soweit ich das verstehe möchte er aufbauend auf dem disassembler einen decompiler bauen. Wobei das dann mit kleines tool eher nix wird.

das erkennt man dann an der call-instruktion anstatt eines jumps

Da habe ich in der Tat zu High Level gedacht 😉 Klar unterscheiden sich die Instruktionen.

@zero_x
Lies dir nochmal durch was ich geschrieben habe. Ich habe beschrieben wie man herausbekommen kann wie der Compiler verschiedene Schleifenarten in Assembler umgesetzt hat. Wenn man nämlich für eine gegebene Sprache mal guckt, wie verschiedene Compiler ein gegebenes Konstrukt umsetzen in Assembler, dann sieht man dass es dort riesige Unterschiede gibt. Also wäre es hilfreich zu wissen wie der Compiler bestimmte Konstrukte umsetzt um sie leichter identifizieren zu können.

Wenn man von einem knoten (anweisung) über sprünge wieder zu dieser anweisung gelangen kann, dann ist das eine schleife.

Ich würde vorschlagen, mir alle knoten durchzugehen, mir dabei zu merken wo man schon war und wenn man bei einer Instruktion ankommt, wo man schon war und diese im zurückgelegten weg vorhanden ist, dann ist es eine schleife.

Das dachte ich auch, war auch mein erster Ansatz den ich programmiert habe. Ich laufen den Assemblercode von oben nach unten ab und speichere mir die locations an denen ich so vorbeikomme. Kommt jetzt ein jump zu einer location die ich schon kenne (also ein Sprung rückwärts) ging ich von einer Schleife aus.
Allerdings habe ich mitterweile schon einfach if/else Konstrukte gefunden die auch "rückwärts" springen. Und da fehlte mir dann wieder die Möglichkeit zu erkennen ob Schleife oder doch nicht.

Kannst du uns näher beschrieben, was du vor hast?

Es geht darum das die Ausgangssoftware spezielle Synchronisationspunkte beinhaltet. Diese müssen, laut Spezifikation, am Anfang jeder Methode, am Ende jeder Methode und in jeder Schleife. Gleichzeitig darf die Anzahl der Maschinenbefehle zwischen 2 Punkten einen Wert x nicht übersteigen, sonst ist ein weitere Punkt notwendig.
Da die Anzahl der Maschinenbefehle aber im Quellcode nicht abzuschätzen ist, muss das im disasemblierten Assemblercode gemacht werden und da sitz ich jetzt.

Ich habe also bis jetzt folgendes gemacht:

1. Alle Funktionen extrahiert (da man ja jede Funktion für sich betrachten kann)

2. Prüfung auf SyncPunkt am Anfang und Ende der Funktion

3. einen Algorithmus der jeden möglichen Pfad abläuft (wenn es zBsp viele ifs/else/elseifs gibt) und jeden Pfad auf die richtige Anzahl Befehle prüft.

Solange keine Schleifen vorkommen, klappts auch einwandfrei. Nun kommen aber Schleifen. Da jede Schleife einen solchen Punkt enthalten muss, kann man eine Schleife ja einfach betrachten. Stimmt ein Durchlauf durch die Schleife, ist es egal wie oft sie später durchlaufen wird, dann stimmen auch alle anderen.

Nur hab ich das große Problem die Schleifen zu erkennen. Es scheint einfach keine eindeutigen Indikatoren für eine Schleife zu geben. IDA Pro zeigt Schleifen ja an und ich wälze derzeit die SDK von IDA Pro ob es da eine Möglichkeit gibt dran zu kommen, weil dann würden wir uns sogar eine Lizenz kaufen. Aber es schaut nicht so gut aus...

Ich möchte keinen Decompiler bauen. Die Aufgabe ist so simpel wie sie sich anhört. Ich möchte nur den Assembler-Code auf Funktionsaufrufe mit dem richtigen Abstand prüfen und da sind lediglich alle Arten von Schleifen ein Problem dem man scheinbar nur sehr schwer Herr wird...

EDIT:

Wenn man nämlich für eine gegebene Sprache mal guckt, wie verschiedene Compiler ein gegebenes Konstrukt umsetzen in Assembler, dann sieht man dass es dort riesige Unterschiede gibt. Also wäre es hilfreich zu wissen wie der Compiler bestimmte Konstrukte umsetzt um sie leichter identifizieren zu können.

Richtig, aber ist es garantiert das IDA Pro beim disassemblieren das Konstrukt genauso baut wie der Compiler der es einst kompiliert hat ?

Richtig, aber ist es garantiert das IDA Pro beim disassemblieren das Konstrukt genauso baut wie der Compiler der es einst kompiliert hat ?

Ja. Assembler und Maschinencode stehen in einer 1:1 Beziehung (außer bei Makroassembler etc.). Sprich wenn du Maschinencode disassemblierst kannst du sicher sein das der Compiler genau diesen Assembler generiert hat (das genaue vorgehen hängt dabei ja vom Compiler ab - entweder wird erst Assembler generiert und der dann assembliert, oder der Compiler generiert direkt Maschinencode. Bei letzterer Variante hättest du den Assembler der dem generierten Maschinencode vom Compiler entspricht.)

Das ist schonmal eine gute Nachricht, vlt lässt es sich ja auf diesem Wege lösen. Danke für den Tip.

hast du ein Beispiel für ein If, welches rückwärts springt?
Ich kann mir gerade den Ablauf gar nicht vorstellen...

jump zu einer location die ich schon kenne (also ein Sprung rückwärts)

nope, dass der sprung rückwärts ist, heißt nicht, dass du das ziel schon kennst! Das ziel kann auch vor deinem startpunkt liegen oder bisher mit einem anderen jump übersprungen worden sein. du musst schon wirklich ein dictionary führen. dabei gibt es aber auchnoch zu beachten, dass du den gesamten abgegangenen pfad abspeicherst. wenn ein knoten zwar markiert aber nicht im pfad ist, ist es keine schleife.

hast du ein Beispiel für ein If, welches rückwärts springt?
Ich kann mir gerade den Ablauf gar nicht vorstellen...

Naja es gibt compiler (unter anderem der von ms) bei denen der einstiegspunkt in eine methode in der mitte von dieser liegt, um die sprunglänge zu minimieren. dann springt ein if wirklich rückwärts, und auchnoch vor den einstiegspunkt.

hast du ein Beispiel für ein If, welches rückwärts springt?
Ich kann mir gerade den Ablauf gar nicht vorstellen...

Es handelt sich dabei nicht um ein spezielles if, sondern hängt mehr mit dem Aufbaue der Methode zusammen in dem das if steht. Der Assemblercode wird entsprechend raffiniert angeordnet um möglichst wenige locations und jumps erzeugen zu müssen. Da kann es dann schonmal passieren das auch bei einem if rückwärts gesprungen wird, weil der Code der dann kommt einfach aus Optimierungsgründen weiter oben steht.

Aber wie Floste ja richtig schreibt, ist das alleinige Rückspringen ja ohnehin kein Beweis für eine Schleife, sondern nur in Verbindung mit dem Pfad indem der Rücksprung stattfindet. Das wäre also evt auch eine mögliche Lösung.

Wobei ich mir da jetzt erstmal Gedanken machen muss wie ich einen solchen Pfad am effizientesten speichere.

Ich könnte es mir so vorstellen....

Du machst einen Parser, der den code ausführungstechnisch durchgeht. Dabei erzeugst du einen ausführungsbaum.

Wichtig für dich sind eigentlich nur

1. einstiegspunkt (E)
2. sprungpunkt (S)
3. rücksprungpunkt (R)

jeder Dieser Knoten hat eine ID.

Gehst du den Baum durch und triffst zwischen einen (E) und einem (R) auf den gleichen (S) (ID ist die assemblerzeile), dann hast du eine Schleife.

Möglicherweise reicht schon die Schätzung aus diesem Eingangspost aus: http://forums.arm.com/index.php?/topic/14569-loop-detection/

Die Sprungmarke hat einen geringeren Wert, als die aktuelle Position. Ob das nur bei Schleifen so ist, wage ich zu bezweifeln (-> Funktionsaufrufe).

@JunkyXL:
Funktionsaufrufe sind keine Jumps sondern es sind Calls. Das kann man gut unterscheiden.

Die Sprungmarke hat einen geringeren Wert, als die aktuelle Position.

Lese dir die vorigen Posts durch. Denn das gilt eben nicht immer.

Ich hab was neues gefunden, was unter Umständen auch möglich wäre.

In IDA Pro ist es möglich sich von Funktionen einen FlowChart generieren zu lassen. Diese sehen dann ungefähr so aus: siehe Anhang.

Darauf sind Schleifen ja leicht zu identifizieren. Diese Charts lassen sich auch auf der Festplatte ablegen, allerdings nur als "Graph Definition File" mit der keiner was anfangen kann.

Also bin ich hingegangen, hab es gespeichert und einfach mal aus *.gdl -> *.xml gemacht. Steck ich das jetzt in den Texteditor, kommt folgens bei raus:

node: { title: "0" label: "58sub_4113D031:
push ebp
mov ebp, esp
sub esp, 0CCh
push ebx
push esi
push edi
lea edi, [ebp+var_CC]
mov ecx, 33h
mov eax, 0CCCCCCCCh
rep stosd
mov [ebp+var_8], 0" vertical_order: 0 }

node: { title: "1" label: "58loc_4113F531:
mov eax, 1
test eax, eax
jz short loc_41142F" }

node: { title: "2" label: "76004113FE31:
mov eax, [ebp+var_8]
add eax, 1
mov [ebp+var_8], eax
cmp [ebp+var_8], 0Ah
jnz short loc_411425" }

node: { title: "3" label: "58loc_41140D31:
mov eax, 1
test eax, eax
usw.

Und noch interessanter wirds etwas weiter unten:

// node 0
edge: { sourcename: "0" targetname: "1" }
// node 1
edge: { sourcename: "1" targetname: "2" label: "false" color: red }
edge: { sourcename: "1" targetname: "10" label: "true" color: darkgreen }
// node 2
edge: { sourcename: "2" targetname: "3" label: "false" color: red }
edge: { sourcename: "2" targetname: "7" label: "true" color: darkgreen }
// node 3
edge: { sourcename: "3" targetname: "4" label: "false" color: red }
edge: { sourcename: "3" targetname: "7" label: "true" color: darkgreen }

Damit kann ich jetzt doch quasi unabhängig vom Assemblercode auf Schleifen prüfen, oder ? Da der Graph den Ablauf darstellt, sind Wege rückwärts eigtl ziemlich sicher Schleifen, im Prinzip könnt ich das doch nun auch verwenden, oder ?
Dann brauch ich mich nicht durch den Assemblercode wühlen um einen Baum zu erstellen sondern kann den nehmen den ich schon geliefert bekomme.

Nun weist du aber immer noch nicht ob es eventuell doch ein Methodenaufruf war, der dann wieder nach Oben springt.

Ich weis jetzt nicht auf was für eine Basis du die Grafik erstellen lassen hast, aber dort gehen doch bis auf einen Pfeil immer wieder welche zurück nach oben.

// Edit mein Fehler, wurde ja schon besprochen dass Funktions-/Methodenaufrufe kein Jump sondern ein Call sind.

Der Graph lässt sich im übrigen auch immer nur für eine einzelne Methode erstellen. D.h. wenns rückwärts geht in dem Graph, geht es innerhalb einer einzelnen Methode rückwärts und das kann ja nur eine Schleife sein.

huhu,

wollte noch in den Raum werfen, dass sich "alle Schleifen" immer als for () darstellen lassen. Auch ein "goto" ist nur eine verkappte Schleife.

naja, aber eine Schleife definiert sich doch eh nur durch die Tatsache, dass Code mindestens 2x durchlaufen werden kann, oder?

Auch ein if-goto ist dann eine Schleife und kann durch ein for() ersetzt werden. Damit sollten sich doch die Möglichkeiten deutlich reduzieren.

😃

Xynratron