Laufzeitbetrachtung für das Gaußsche Eliminationsverfahren in Wet Paper Codes

Inhaltsverzeichnis

1 EINLEITUNG
1.1 WET PAPER CODES
1.2 ZIEL DER ARBEIT
1.3 DIE ARBEITSWEISE DES ZU UNTERSUCHENDEN ALGORITHMUS

2 VORGEHENSWEISE
2.1 GESAMTBETRACHTUNG
2.2 AUFGLIEDERUNG DES ALGORITHMUS

3 METHODEN
3.1 AUSZÄHLEN DER ADDITIONEN
3.2 MESSTECHNISCHE ANALYSE MIT GPROF
3.3 MESSTECHNISCHE ANALYSE MIT RPROF

4 ANALYSE-ERGEBNISSE
4.1 GESAMTBETRACHTUNG DES ALGORITHMUS
4.2 LADEN DER MATRIX
4.2.1 Mathematische Analyse
4.2.2 Messanalyse
4.3 GAUß-ELIMINATION
4.3.1 Mathematische Analyse
4.3.2 Messtechnische Analyse
4.4 VERTAUSCHEN DER SPALTEN
4.4.1 Mathematische Analyse
4.4.2 Messtechnische Analyse
4.4.3 Optimierungsmöglichkeit

5 DISKUSSION DER ERGEBNISSE UND AUSBLICK
5.1 ZUSAMMENFASSUNG
5.2 BEURTEILUNG DER ERGEBNISSE
5.3 PERSÖNLICHE ERFAHRUNGEN
5.4 AUSBLICK

6 LITERATURVERZEICHNIS

CD-Verzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung

Die Steganographie beschäftigt sich mit dem Verstecken von Nachrichten in Trägerobjekten unter dem Ziel Botschaften geheim an einen Empfänger zu übermitteln. In dieser Arbeit wird ein Algorithmus einer Methode untersucht, die den so genannten Wet Paper Codes^[1] von Jessica Fridrich, Miroslav Goljan, David Soukal und P. Lisoněk zuzuordnen ist.

1.1 Wet Paper Codes

Mithilfe von Wet Paper Codes soll es dem Angreifer wesentlich erschwert werden, zu erken- nen, ob eine Nachricht in einem Trägerobjekt versteckt ist, bzw. welche Stellen im Trägerob- jekt modifiziert wurden. Nur der Empfänger soll die Nachricht extrahieren können. Um aus- zuschließen, dass ein möglicher Angreifer entdeckt, dass eine Nachricht verschickt wurde, wird zuvor ein Schlüssel zwischen Sender und Empfänger ausgetauscht, der dazu dient be- stimmte Stellen in den Trägerobjekten zu bestimmen, die während der Nachrichteneinbettung geändert werden müssen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Funktionsweise von Wet Paper Codes

Anhand der Abbildung 1 soll die Metapher von Wet Paper Codes veranschaulicht werden. Vor dem Nachrichtenaustausch geschieht ein Schlüsselaustausch, wobei Sender und Empfän- ger den gleichen Schlüssel besitzen. Der Sender besitzt nun das wet paper (dt. "nasses Papier"). Da einige Stellen auf dem Dokument nass sind, kann der Sender nur auf von ihm ausgewählte trockene Stellen schreiben. Denn beim Schreiben auf nasse Stellen würde die Tinte verlaufen und ein Angreifer könnte später nachvollziehen welche Stellen verändert wurden. Der Sender benutzt den Schlüssel um diejenigen trockenen Stellen zu bestimmen, welche geändert werden müssen um die Nachricht einzubetten. Während die Nachricht ver- schickt wird, trocknen die nassen Stellen aus. Einem möglichen Angreifer und dem Empfänger sind nicht bekannt, welche Stellen schon zu Anfang an trocken waren und somit möglicherweise verändert wurden. Der Empfänger jedoch kann mit dem Schlüssel die Nach- richt aus dem versendeten Trägerobjekt extrahieren.

Anhand eines Beispiels soll nun die genaue Funktionsweise von Wet Paper Codes verdeut- licht werden. Das Beispiel ist an die Vorstellung von Wet Paper Codes von Tobias Hommel^[2] angelehnt. Da mit Bits gerechnet wird, erfolgen Additionen als Additionen modulo 2.

Zunächst benötigt der Sender eine Nachricht m, die er übermitteln möchte. Die Nachricht be- sitzt die Länge q.

[Abbildung in dieser Leseprobe nicht enthalten] mit der Nachrichtenlänge q = 3

Sender und Empfänger haben zuvor einen Schlüssel ausgetauscht mit dem der Sender eine pseudozufällige binäre Matrix D generiert, die q Zeilen und n Spalten besitzt.

[Abbildung in dieser Leseprobe nicht enthalten]mit q = 3 Zeilen und n = 5 Spalten

Als nächstes benötigt der Sender das Trägerobjekt (wet paper). JPEG-Dateien werden wegen ihrer verlustbehafteten Kompression für das Einbetten von Nachrichten bevorzugt. Während der Kompression werden Werte gebildet, die später aufgerundet werden. Darunter sind Werte deren Nachkommateil nahe 0,5 liegt. Diese Werte eignen sich besonders für das Einbetten, da je nach einzubettendem Nachrichtenbit entschieden werden kann, ob auf- oder abgerundet wird. Sie dienen somit als trockene Stellen im wet paper. Würde man versuchen die anderen Werte (nasse Stellen) zum Einbetten zu verwenden, dann verändert man damit das Wahr- scheinlichkeitsmuster der Pixelwerte (die Tinte verläuft), womit ein Angreifer erkennt ob etwas eingebettet wurde. Der Sender extrahiert nun den folgenden Vektor b aus dem Träger- objekt. Dieser Vektor der Länge n enthält die Pixel-LSBs^[3] des Trägerobjektes.

[Abbildung in dieser Leseprobe nicht enthalten] mit der der Länge n = 5

Aus b werden nun Pixelwerte ausgewählt, die das oben genannte Kriterium nicht erfüllen. Da die Nachrichtenlänge nur 3 Bit lang ist, können aus den 5 verfügbaren LSBs auch zwei gestrichen werden. In dem Fall sind das b2 und b5. Nun müssen die entsprechenden Spalten der Matrix D gestrichen werden, welche mit den gestrichenen Elementen aus b korrespondieren. Es wird also die 2. und 5. Spalte aus D gestrichen, wodurch eine neue quadratische Matrix H entsteht.

Abbildung in dieser Leseprobe nicht enthalten

Das folgende Gleichungssystem muss nun nach v aufgelöst werden. Alle Einsen in v zeigen die Stellen an, welche in b geändert werden müssen. Es ist zu beachten, dass in v genau diejenigen Elemente nicht vorhanden sind, welche in b ausgewählt und gestrichen wurden.

Abbildung in dieser Leseprobe nicht enthalten

Entsprechend dem Ergebnis für v muss also das 3. Element in b geändert werden. So erhält man den Vektor b' der nun die Pixel-LSBs enthält, welche sich in dem zu versendendem Trä- gerobjekt befinden.

Abbildung in dieser Leseprobe nicht enthalten

Die echte "Magie" von Wet Paper Codes zeigt sich beim Entpacken der Nachricht. Der Empfänger erhält nun das Trägerobjekt und kann die Pixel-LSBs des Trägerobjektes als b' extrahieren. Das sind genau q Elemente. Anschließend kann er mithilfe des zuvor ausge- tauschten Schlüssels dieselbe Matrix D mit n Zeilen und q Spalten erzeugen. Es wird davon ausgegangen, dass der Empfänger die Nachrichtenlänge q kennt. Das Produkt von D und b' liefert die Nachricht m.

Abbildung in dieser Leseprobe nicht enthalten

Der Empfänger besitzt keinerlei Kenntnisse über die Stellen, welche aus dem Trägerobjekt gestrichen wurden (bzw. nass waren). Dennoch konnte die Nachricht an den Empfänger exakt übermittelt werden.

1.2 Ziel der Arbeit

Wie im obigen Beispiel für Wet Paper Codes ersichtlich wurde, muss der Sender ein lineares Gleichungssystem A · x = b im Polynomkörper GF(2n) lösen um herauszubekommen, welche Stellen im Trägerobjekt geändert werden müssen. Dabei ist die Matrix A zum einen quadra- tisch und besitzt somit genauso viele Spalten wie Zeilen (sie besitzt den Rang der Nachrich- tenlänge q). Zum anderen muss A invertierbar sein, damit das Gleichungssystem gelöst wer- den kann. Wie im Verlauf der Arbeit ersichtlich wird, hat das Lösen der Gleichung eine kubi- sche Laufzeitkomplexität O(n3) wenn n als Rang der Matrix A definiert ist. Das Lösen des linearen Gleichungssystems ist somit der rechenaufwendigste Prozess im gesamten Aus- tauschvorgang. Für längere Nachrichten z.B. im Kilobyte-Bereich kann das Lösen dieses Gleichungssystems schon sehr lang dauern. Dennoch sollte in der Praxis nicht darauf ver- zichtet werden größere Informationsmengen wie z.B. Dateien einzubetten und zu verschicken. Zum einen versucht man den Rechenprozess zu beschleunigen indem man das Trägerobjekt in viele kleine Teile zerlegt und für jeden Teil die Gleichung einzeln löst. Zum anderen könnte man versuchen den Algorithmus zur Lösung des Gleichungssystems zu verbessern.

Als ich mich über verschiedene Lösungsverfahren von linearen Gleichungssystemen infor- miert habe, bin ich auf die LR-Zerlegung^[4] gestoßen. Für den Fall das die Matrix A konstant bleibt und sich nur der Vektor b verändert, muss die Matrix A nur ein einziges mal invertiert werden, wobei A in das Produkt einer unteren Dreiecksmatrix L und einer oberen Dreiecks- matrix R zerlegt wird. Alle restlichen Berechnungen für verschiedene b erfolgen dann in quadratischer Laufzeit, da L und R lediglich auf den jeweiligen Vektor bezogen rücksubstitu- iert werden müssen. In der Praxis bedeutet das, dass man für das Einbetten immer denselben Schlüssel und dieselbe Trägerdatei verwendet (beides beeinflusst die Matrix A). Lediglich die Nachricht auf der rechten Seite des Gleichungssystems darf verändert werden. Jedoch sollte das in der Praxis vermieden werden, da ein Angreifer anhand von mehreren ursprünglich glei- chen Trägerobjekten und verschieden eingebetteten Nachrichten Rückschlüsse auf die verän- derten (trockenen) Stellen schließen kann.

Während der Arbeit wurde im Sinne der Effizienzverbesserung ebenfalls eine Methode von Volker Strassen in Betracht gezogen, die die Komplexität von Matrizenmultiplikationen und Matrizeninversionen von O(n3) auf O(n2,07) senkt^[5]. Jedoch erwies sich diese bei genaueren Betrachtungen als unvorteilhaft, denn Strassen versucht durch weniger Multiplikationen und viel mehr Additionen dasselbe Ergebnis zu erzielen. Da Multiplikationen im Normalfall viel länger dauern als Additionen bringt das tatsächlich eine Verringerung der Komplexität. Im zu untersuchenden Algorithmus werden jedoch Additionen durch XOR- und Multiplikationen durch AND-Verknüpfungen realisiert. Da man davon ausgehen kann, dass XOR- und AND- Verknüpfungen gleich schnell ausgeführt werden, bringt die Methode von Strassen in diesem Fall keine Vorteile.

In meiner Arbeit möchte ich eine Laufzeitbetrachtung an dem Algorithmus zur Lösung dieses Gleichungssystems vornehmen. Die Lösung des Gleichungssystems wird in dem zu untersu- chenden Algorithmus mit dem Gaußschen Eliminationsverfahren und einer anschließenden Rücksubstitution realisiert. Diese Arbeit beschränkt sich auf die alleinige Betrachtung des Eliminationsverfahrens (ohne Rücksubstitution). Die Elemente der Matrix A werden während des Lösungsverfahrens in Blöcke gepackt und auch Blockweise behandelt. Eine Möglichkeit der Effizienzverbesserung liegt in der Laufzeitbetrachtung für verschiedene Blockgrößen, so- wie für den Sonderfall, dass jedes Bit einzeln behandelt wird. In dieser Arbeit sollen diese Va- rianten miteinander unter dem Ziel verglichen werden, die beste Variante in Abhängigkeit der Blockgröße zu ermitteln und es soll geprüft werden, ob die Laufzeitkomplexität des Algo- rithmus in Abhängigkeit der Blockgröße verringert werden kann.

1.3 Die Arbeitsweise des zu untersuchenden Algorithmus

Die Ausführungen in diesem Abschnitt beziehen sich vollständig auf den Algorithmus in der Methode gf2_solve() im Quelltext von solve.c^[6]. Dabei handelt es sich um eine C- Implementierung für die Skriptsprache R^[7]. Der Algorithmus wurde von den Autoren mit Kommentaren versehen um die anschließenden Schritte besser nachvollziehen zu können. Abbildung 2 stellt die Lösungsschritte für ein Beispiel dar, auf das während der Ausführungen Bezug genommen wird. Das Packen der Bits in Blöcke wird in dem Beispiel jedoch ignoriert.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Eliminationsverfahren nach solve.c für eine 3 ä 3 Matrix

1. Vo r be r eitung

Im ersten Abschnitt werden die als R-Objekte übergebenen Parameter (Koeffizientenmatrix A, Vektor b) überprüft. Die Matrix A muss quadratisch sein und der Vektor b sollte genau so viele Elemente besitzen wie die Matrix Spalten besitzt. Zusätzlich wird ein entsprechendes Speicherfeld für die zu bearbeitende Matrix A reserviert. Dieses Speicherfeld besteht aus N * NB Speicherzellen, wobei N dem Rang der Matrix A entspricht. NB ist gleich dem Rang N dividiert durch die verwendete Blockgröße BITS_PER_BLOCK in Bits (kurz: BPB) plus 1. Die Größe NB gibt also an, wie viele Blöcke für N Spalten pro Zeile benötigt werden, wenn jeder Block mit BITS_PER_BLOCK Bits der Matrix A gefüllt wird. Die Addition mit 1 ge- schieht deshalb, weil zusätzlich ein Element des Vektors b in jede Zeile muss.

Anschließend werden Permutationsvektoren definiert und initialisiert, in denen die später vor- genommenen Spaltenpermutationen festgehalten werden. Die Zuweisung des Permutations- vektors perm_c2o[1] = 2 (c2o - "current to original") bedeutet z.B., dass die 1. Spalte im Speicher nun der 2. Spalte in der Ausgangsmatrix entspricht.

2. L aden de r Matrix

Der Algorithmus bearbeitet alle Teilschritte während der Eliminierung für jede Zeile. So wird bei jedem neuen Zeilendurchlauf eine neue Zeile der Matrix A in den Speicher geladen. Im Algorithmus werden die Elemente dabei in Blöcke gepackt und blockweise gespeichert. Da während des Lösungsverfahrens Spalten vertauscht werden, müssen Spaltenpermutationen beim Übertragen von Elementen berücksichtigt werden. Im Beispiel wurden vor dem zweiten

Schleifendurchlauf die Spalte 1 und 2 im Speicher miteinander vertauscht. Also wird das Element in Zeile 2 und Spalte 1 im Speicher in Spalte 2 geschrieben. Das Element in Zeile 2 und Spalte 2 wird im Speicher in Spalte 1 geschrieben.

3. G auß-Eli m ination

Um eine erfolgreiche Rücksubstitution zu garantieren, müssen alle Elemente links der Haupt- diagonale eliminiert werden. Für jede Zeile wird also geprüft ob ein Element vor dem diagonalen Element den Wert 1 besitzt. Im Beispiel besitzt im 2. Durchlauf nach dem Laden der Zeile das Element in Zeile 2 und Spalte 0 den Wert 1. Um dieses Element zu "nullen" muss die Zeile 0 von Zeile 1 abgezogen werden. Das entspricht im Polynomkörper GF(2n) einer Addition^[8] modulo 2, bzw. einer XOR-Verknüpfung. Zu beachten ist, dass bei jeder Zeilenaddition jedes Zeilenelement der Zeile 1 mit jedem Zeilenelement der Zeile 0 addiert werden muss.

4. Spalten ve r tau s chen

Da alle Elemente in der Hauptdiagonale vor der Rücksubstitution den Wert 1 besitzen müs- sen, muss etwas unternommen werden, wenn das diagonale Element nach der Elimination un- gleich 1 ist. Im Beispiel ist während des 2. Durchlaufes das diagonale Element gleich 0. Also muss ein Element in der Zeile gefunden werden, dessen Wert gleich 1 ist. Wenn keins gefun- den wird, gibt es zwei Optionen.

A. Ist das Element vom Vektor b in der entsprechenden Zeile 0, dann darf das diagonale Element gleich 1 gesetzt werden

B. Ist das Element vom Vektor b in der entsprechenden Zeile 1, dann ist die Matrix nicht invertierbar, denn [Abbildung in dieser Leseprobe nicht enthalten]ist eine falsche Aussage.

Es wird bei den Betrachtungen in der Arbeit jedoch immer davon ausgegangen, dass ein ent- sprechendes Element gefunden wird. Im Beispiel befindet sich dieses Element beim 2. Durchlauf in Spalte 2. Also werden die 1. und 2. Spalte vertauscht. Die Permutation wird im Permutationsvektor perm_c2o festgehalten.

5. Rück s ub s titution

Nach allen bisherigen Schritten kann nun von der letzten bis zur ersten Zeile rücksubstituiert werden. Da die erhaltenen Lösungselemente jedoch durch die Spaltenpermutation ebenfalls vertauscht sind, müssen diese über den Permutationsvektor wieder zurück vertauscht werden.

2 Vorgehensweise

Da in der Arbeit anfänglich die Betrachtung von Optimierungsmöglichkeiten im Gaußschen Eliminationsverfahren im Vordergrund stand, habe ich mir zunächst unabhängig vom zu un- tersuchenden Algorithmus eine Übersicht über alternative Lösungsverfahren zum Lösen linearer Gleichungen verschafft. Da sich jedoch das Gaußsche Eliminationsverfahren, wie es im Algorithmus umgesetzt wird, als die beste Variante erwies, begann ich den Algorithmus selbst genauer zu untersuchen.

Da der Algorithmus durch die besondere Eigenschaft gekennzeichnet ist, dass er die zu verar- beitenden Elemente blockweise packt und behandelt, erschien mir eine Betrachtung für ver- schiedene Blockgrößen und den Sonderfall, dass die Bits einzeln behandelt werden, günstig für eine Möglichkeit der Laufzeitverbesserung.

Um den Einfluss der Blockgröße auf den Algorithmus zu untersuchen habe ich zunächst den Algorithmus in seiner Gesamtheit für verschiedene Blockvarianten gemessen (Gesamtbe- trachtung) und anschließend in Teile zerlegt, die ich genauer untersucht habe.

2.1 Gesamtbetrachtung

Der originale Algorithmus arbeitet mit einer Blockgröße von 32 Bit. Um den Algorithmus für verschiedene Blockgrößen zu untersuchen, wurden zunächst drei weitere Versionen erstellt, die sich in der Blockgröße unterscheiden. Eine vierte Version wurde ebenfalls programmiert, bei der die Bits nicht in Blöcke gepackt, sondern einzeln gespeichert und behandelt wurden.

Für die Messung des gesamten Algorithmus standen insgesamt die folgenden C- Implementierungen^[9] zur Verfügung.

- Blockgröße von 64 Bit: solveUINT64.c
- Blockgröße von 32 Bit: solve.c (originale Version)
- Blockgröße von 16 Bit: solveUINT16.c
- Blockgröße von 8 Bit: solveUINT8.c
- 1 Bit pro Block: solveBPB.c (bei 32-Bit-Blöcken)

Für jede dieser C-Implementierungen wurde mithilfe von R eine dll-Datei^[10] erzeugt, welche anschließend in die R-Umgebung eingebunden wurde. Mittels eines erstellten Testskripts wurde für alle Implementierungen bei der gleichen Matrix A die Laufzeit gemessen und in eine Ausgabedatei "Rprof.out" geschrieben. Mit Rprof (Profiler von R) konnte die Ausgabe- datei geöffnet und die Laufzeiten eingesehen werden.

2.2 Aufgliederung des Algorithmus

Nach der Gesamtbetrachtung wurde der Algorithmus in drei Teile aufgegliedert. Die folgen- den Abschnitte im Algorithmus wurden in C als Methoden programmiert^[11] und einzeln unter- sucht.

1) Laden der Matrix
2) Gauß-Elimination
3) Vertauschen der Spalten

Die Betrachtungen in dieser Arbeit erfolgten für alle drei Teilbereiche des Algorithmus. Der Schwerpunkt jedoch lag auf der Gauß-Elimination. Die anderen beiden Teile sind trotzdem ein wesentlicher Bestandteil während des Eliminationsverfahrens und wurden deshalb ebenso analysiert.

In allen drei Teilbereichen wurden zwei grundlegende Versionen gegenübergestellt: zum ei- nen die Bit-pro-Block-Variante (BPB-Variante) in welcher die Bits einzeln behandelt werden und zum anderen die Block-Variante für verschiedene Blockgrößen, bei der die Bits in Blö- cken behandelt werden.

Für jeden Teilbereich erfolgte die Analyse auf zwei verschiedene Weisen. Bei der mathemati- schen Analyse wurde die Zahl an Operationen in Abhängigkeit von N und der Blockgröße ermittelt. Die gewonnenen Formeln wurden mit einzelnen Messungen (Mitzählen der Schlei- fendurchläufe) auf ihre Richtigkeit überprüft. In der messtechnischen Analyse wurde (nach der Kompilierung der einzelnen Quelltexte) die Laufzeit für die Bit-pro-Block-Variante und die Block-Variante mit GProf gemessen. Für das Laden der Matrix und das Vertauschen der Spalten wurden auch für die Bit-pro-Block-Variante verschiedene Blockgrößen getestet. Da ich mich bei der Eliminierung auf den Einfluss der Blockgröße in der Block-Variante kon- zentrieren wollte, habe ich die Bit-pro-Block-Variante nur für die Standard-Blockgröße von 32 Bit getestet.

3 Methoden

3.1 Auszählen der Additionen

Für die Block- und die Bit-pro-Block-Variante wurden jeweils die Zahl an Operationen in dem jeweiligen Teilbereich bestimmt. Für die Block-Variante ergab sich ebenso eine Abhängigkeit von der Blockgröße, die mit BPB ("Bits per Block") bezeichnet wurde. Um die genaue Zahl an Operationen in Abhängigkeit von der Eingabegröße N (Rang der Matrix A) zu bestimmen, wurde dafür zunächst eine mathematische Formel durch allgemeine Überlegungen oder Betrachtungen anhand von Beispielmatrizen bzw. Beispieleingaben für N aufgestellt. Mit der programmierten Methode des jeweiligen Teilbereichs wurde anhand die- ser Beispielmatrizen gedanklich nachvollzogen wie oft alle Schleifen in der Methode durch- geführt werden um dann aus verschiedenen Beispielen eine allgemeine Formel zu entwickeln. Um die Formeln zu überprüfen wurden einzelne Versionen der Methoden erzeugt, in denen die Operationenzahl durch Zählvariablen gemessen und ausgegeben wurde (s. Beispiel in Abbildung 3). Dabei wurden zunächst für verschiedene N die Schleifendurchläufe mithilfe der Formel berechnet und anschließend geprüft ob das Ergebnis mit den Ausgabedaten über- einstimmt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Beispiel für das Zählen von Schleifendurchläufen mithilfe von Zählvariablen

3.2 Messtechnische Analyse mit Gprof

Der theoretisch-mathematischen Betrachtung folgte eine Messanalyse bei der die Laufzeit für alle Varianten bestimmt wurde. Alle Programme wurden mit der 32 Bit C/C++ Entwicklungsumgebung DJGPP^[12] kompiliert und gemessen. Das Übersetzen geschah in der DOS-Konsole über

C:\gcc\mystuff> gcc solve_P1.c -o solve_P1.exe -pg

Dabei wurde lediglich die Profilingfunktion (-pg) genutzt. Es wurden keine Optimierungs- funktionen des Compilers verwendet, sodass die am Quelltext vorgenommenen theoretischen Überlegungen möglichst unverfälscht durch die Messungen repräsentiert werden konnten.

Nach dem Ausführen des Programms konnte die erzeugte Ausgabedatei des Profilers mit Gprof analysiert werden:

C:\gcc\mystuff> solve_P1.exe C:\gcc\mystuff> Gprof solve_P1.exe

Abbildung 4 zeigt wie eine Analyse mit Gprof aussehen könnte. In der Spalte "self s/call" befindet sich die Laufzeit der aufgerufenen Methode in Sekunden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: Beispiel für Laufzeituntersuchung mit Gprof

In den meisten Fällen wurde die Laufzeitanalyse für verschiedene Eingabegrößen vorgenom- men. Die Eingabegröße wurde jeweils im Quelltext bestimmt (int N = 100;). Wenn nicht an- ders angegeben, setzen sich alle dargestellten Messwerte aus 5 Messproben zusammen, von denen jeweils der kleinste Messwert für die Analyse verwendet wurde um so den Störeinfluss gering zu halten.

Alle Messungen wurden unter folgenden Systemvoraussetzungen durchgeführt:

- Betriebssystem: Microsoft Windows XP Professional, Version 2002, Servicepack 2
- Prozessor: AMD AthlonXP 3000+ (2,17 GHz)
- RAM: 1 GB

3.3 Messtechnische Analyse mit Rprof

Die Gesamtbetrachtung des Algorithmus wurde innerhalb der Statistik-Umgebung R (Ver. 2.4.1) durchgeführt. Dazu wurde zunächst für alle Programme mithilfe von R in eine dll-Datei erzeugt:

C:\Program Files\R2\R-2.4.1\bin> R CMD SHLIB solve.c

Nach dem Einfügen der dll-Dateien in das Hauptverzeichnis (C:\Program Files\R2\R- 2.4.1) wurde die Statistik-Umgebung gestartet.

[...]

---

^[1] J. Fridrich, M. Goljan, D. Soukal, P. Lisoněk: Perturbed Quantization Steganography with Wet Paper Codes

^[2] Hommel, Tobias: Wet Paper Codes

^[3] LSB: least significant bit (dt. "niedrigstwertige Bit")

^[4] Siehe: www.numerik.mathematik.uni-mainz.de: LR-Zerlegung

^[5] Vgl. Volker Strassen: Gaussian Elimination is not optimal

^[6] solve.c: Entwickelt von David Soukal und später ergänzt von Rainer Böhme, Begleit-CD:\Programmdateien\R- implementierungen\src\solve.c

^[7] R: frei verfügbare Statistik-Umgebung, Entwickler: The R Foundation for Statistical Computing

^[8] Siehe: Elmar Böhler: Der Polynomkörper GF(2n)

^[9] Alle Quelltexte der C-Implementierungen für R befinden sich auf der Begleit-CD: \Programmdateien\C-Implementierungen für R\src

^[10] Alle erzeugten dll-Dateien befinden sich auf der Begleit-CD:\Programmdateien\C-Implementierungen für R\dll

^[11] Alle für die Messungen der Teilbereiche verwendeten C-Quelltexte befinden sich für jeden Teilbereich geordnet auf der Begleit-CD:\Programmdateien\Teiluntersuchungen

^[12] DJGPP (Ver. 2.03): http://www.delorie.com/djgpp/