Die drei Hersteller

Ein aktueller Vorfall hat mich veranlasst, mich ein wenig genauer mit Software-Forensik zu beschäftigen. Genauer gesagt geht es in diesem Fall um die Erkennung eines Plagiats. In diesem Beitrag schildere ich den Fall und zeige einen einfachen Indikator zur Erkennung von Ähnlichkeiten in Programmen.

Gegenstand der Untersuchung ist die Implementierung eines bestimmten Algorithmus. Hersteller "M" erfand den Algorithmus und implementierte ihn in einem größeren Programm. Es gab jedoch keine öffentlich verfügbare Dokumentation zu dem Verfahren.

Hersteller "S" hat dieses Programm untersucht und daraus den Algorithmus abgeleitet. Der resultierende Quellcode ist unter Version3 der GNU Public License öffentlich verfügbar, ebenso eine compilierte Fassung.

Hersteller "X" schließlich hat als letzter der drei eine Implementierung veröffentlicht. Abermals ist nur das ausführbare Programm verfügbar.

Die Frage ist nun, ob Hersteller "X" seine Implementierung auf der Basis einer eigenen Analyse des Original-Codes erstellt hat, oder ob er den Code aus dem Hause "S" übernommen hat.

Als ersten Indikator habe ich die ausführbaren Dateien der drei Hersteller im Disassembler IDA Pro untersucht. IDA übersetzt die (binäre) Maschinensprache in lesbaren Assembler-Code. Das Assembler-Listing kann dabei durchaus die zehnfache Zeilenzahl des originalen C-Quellcodes enthalten. Es ist deshalb schwer, die Übersicht zu behalten. Gerne lasse ich mir deshalb den Code einer Funktion als Graphen anzeigen. Die folgende Abbildung zeigt die Graphen aller drei Implementierungen. In der Reihenfolge ihres Erscheines, von links nach rechts: Hersteller "M", "S" und "X".

Eine Funktion, drei Implementierungen. Von links: Hersteller M, S und X

Die Graphen werden von oben nach unten gelesen. Kästen ("Knoten") markieren zusammenhängende Abschnitte im Code. Grüne und rote Linien ("Kanten") stellen die wahr/falsch-Äste einer Verzweigung dar.

Es scheint keine großen Übereinstimmungen zwischen den Implementierungen von "M" und "S" zu geben. Zwischen dem Code von "S" und "X" gibt es jedoch eine auffällig hohe Übereinstimmung. Man sollte diesen Befund jedoch nicht überbewerten.

Die Methode berücksichtigt nicht den Code innerhalb eines Knotens. Deswegen können, zumindest theoretisch, zwei unterschiedliche Programme zum gleichen Graphen führen.

Andererseits lassen unterschiedliche Compiler oder Compiler-Optionen den selben Quellcode im Graphen unterschiedlich erscheinen. Bitte betrachten Sie diesen kurzen Codeauszug: for (i=0; i<3; i++;) { x[i] = i; } Der Graph würde aus einem kleinen Knoten und einer Verzweigung bestehen.

Die Compiler-Option "unroll loops" wandelt die for-Schleife in eine Serie von Zuweisungen um:

x[0] = 0;
x[1] = 1;
x[2] = 2;

Nun zeigt der Graph einen größeren Knoten, die Verzweigung fehlt. Der Code erfüllt immer noch die selbe Funktion, wenngleich in einer leicht unterschiedlichen Weise.

Archiv

Impressum

Dieses Blog ist ein Projekt von:
Andreas Schuster
Im Äuelchen 45
D-53177 Bonn
impressum@forensikblog.de

Copyright © 2005-2012 by
Andreas Schuster
Alle Rechte vorbehalten.
Powered by Movable Type 5.12