Diehard

Diehard ist der Name einer „Testbatterie“ (auch: „Testsuite“ oder „Testsortiment“) zur Prüfung der Zufälligkeit einer gegebenen Zeichenfolge, beispielsweise aus Ziffern und/oder Buchstaben oder aus Bytes.

Das englische Wort diehard hat mehrere Bedeutungen und kann hier, als Adjektiv aufgefasst, vielleicht am treffendsten mit „unermüdlich“ übersetzt werden. Die erste Silbe die separat betrachtet bedeutet „Würfel“ und kann zusammen mit hard (deutsch „hart“) auch als Wortspiel interpretiert werden.

Erzeugung von Zufallsfolgen

Beispiel eines Zufalls­textes aus Groß­buchstaben (hier gruppiert in Fünfer­gruppen)

Der amerikanische Mathematiker und Informatiker George Marsaglia (1924–2011) interessierte sich ab den 1960er-Jahren mehrere Jahrzehnte lang sehr für das Phänomen „Zufall“, insbesondere für die Erzeugung von möglichst zufälligen Zahlen („Zufallszahlen“) oder zufälligen Buchstabenfolgen („Zufallstexten“), wie sie beispielsweise in der Kryptologie benötigt werden, und stellte sich selbst die Frage, wie sich „Zufälligkeit“ messen lässt.

Man wusste bereits, dass es alles andere als trivial ist, mithilfe von Algorithmen „gute“ Zufallsfolgen zu erzeugen. Mit „gut“ sind hier Zeichenfolgen gemeint, die sich von „echten“ Zufallsfolgen nicht unterscheiden lassen, also, die keinerlei Gesetzmäßigkeiten erkennen lassen und deren statistische Kenngrößen, wie beispielsweise Mittelwert oder Varianz, keine Auffälligkeiten zeigen. Man spricht hier von Pseudozufall.

Zwar gibt es eine Reihe von Zufalls­zahlen­generatoren, die mehr oder weniger „gute“ Zufallsfolgen erzeugen können, beispielsweise Pseudo­zufalls­folgen für Test­signale, die für spezielle Zwecke durchaus „hinreichend“ zufällig sein können. Letztlich handelt es sich dabei in der Regel jedoch um deterministische Zeichenfolgen, da sie mithilfe gewisser mathematischer Vorschriften berechnet werden. Daher werden diese als Pseudo­zufallszahlen­generatoren bezeichnet.

Für kryptographisch sichere Zufalls­zahlen­generatoren, die „möglichst echten“ Zufall erzeugen sollen, also unvorhersehbare nicht­deterministische Zufalls­zahlen­folgen, nutzt man zumeist physikalische Zufalls­zahlen­generatoren, beispielsweise Rauschgeneratoren. Zuweilen nimmt man auch menschliche Aktionen oder Reaktionen her, beispielsweise Bewegungen der Computermaus oder Zeiten in Millisekunden zwischen Tastendrücken, um daraus Zufallswerte abzuleiten. Allerdings zeigt sich, dass auch diese Ereignisse nicht wirklich zufällig sind, sondern ebenfalls nur quasizufällig. Folglich weisen auch die auf diese Weise erzeugten Zufallszahlen eine mehr oder weniger gute Qualität auf, beispielsweise sind sie zumeist noch nicht einmal gleichverteilt. Marsaglia konnte mithilfe seiner Testbatterie zeigen, dass auch die mithilfe von beispielsweise physikalischen Rauschgeneratoren erzeugten Zufallszahlen nicht alle Tests bestehen, im Gegenteil: „They fail many of the tests in DIEHARD“ (deutsch „Sie bestehen viele Tests in DIEHARD nicht“).

Daher gab Marsaglia die explizite Empfehlung, zur Erzeugung von „guten“ Zufallsfolgen am besten mehrere – möglichst unterschiedliche – Verfahren zu benutzen und deren Ergebnisse anschließend mithilfe eines Mischers miteinander zu kombinieren. Dabei geht er von dem Grundsatz aus, dass das Ergebnis der Kombination von zwei oder mehreren Zufallsfolgen niemals weniger zufällig ist als jede einzelne, was er empirisch belegen konnte. Marsaglia stellt in einer ZIP-Datei (siehe auch: Diehard.zip unter Weblinks) eine Vielzahl von Pseudo­zufalls­zahlen­generatoren in Form einer EXE-Datei namens Makewhat.exe („Mach was“) zur freien Verfügung sowie auch eine Meld.exe („Verschmelze“) zum Mischen zweier Zufallsdateien.

Messung der Zufälligkeit

Interessanterweise zeigt sich, dass ähnlich wie die Erzeugung von Zufall auch ein Test auf Zufälligkeit alles andere als trivial ist. Niemand kennt eine einfache Methode, mit der man zuverlässig feststellen kann, ob eine gegebene Zeichenfolge wirklich zufällig ist oder nicht. Allerdings gibt es diverse statistische Kenngrößen, die man überprüfen kann, und die ein Maß für die „Qualität des Zufalls“ ergeben.

Beispiel Mittelwert

Spielwürfel als physikalischer Zufalls­zahlen­generator

Ein ganz simpler und durchaus nützlicher Test auf Zufälligkeit ist die Berechnung des Mittelwerts. Beispielsweise könnte man damit die Qualität eines Spielwürfels überprüfen. Ein perfekter Würfel sollte jede Zahl zwischen 1 und 6 gleich häufig erzeugen. Wirft man ihn tausend Mal und addiert alle Ergebnisse, dann sollte sich eine Summe von etwa 3500 ergeben, da ja im Mittel bei sechs Würfen 1+2+3+4+5+6 = 21, also pro Wurf im Mittel 21/6 = 3,5 erzeugt wird. Eine große Abweichung im Ergebnis, beispielsweise 4000, würde den Würfel verdächtig erscheinen lassen. Umgekehrt wäre ein perfekter Mittelwert jedoch keinerlei Garantie für einen einwandfreien Würfel. Ein defekter Würfel könnte beispielsweise sehr häufig die Zahlen 1 und 6 ergeben, und diese beiden möglicherweise gleich häufig, hingegen selten oder nie die anderen Zahlen. Auch dann wäre der Mittelwert jedoch 3,5. Das heißt, der Mittelwert-Test würde solch einen defekten Würfel nicht entlarven.

Beispiel Gleichverteilung

Ein alternativer und ebenso simpler Test wäre die Prüfung der Gleichverteilung. Hiermit würde der obige defekte Würfel sofort erkannt. Ein anderer „fiktiver Würfel“, hier durch einen Algorithmus realisiert, der nacheinander stets die Folge 1, 2, 3, 4, 5, 6 erzeugt, würde den Gleichverteilungs-Test glänzend bestehen und auch den Mittelwert-Test. Dennoch wäre natürlich solch eine Folge keineswegs zufällig, sondern in höchstem Maße deterministisch, also völlig unbrauchbar.

Testbatterie

Wie sich zeigt, genügt kein einzelner Test, um die „wirkliche“ Zufälligkeit einer Zeichenfolge zu überprüfen. Ähnlich wie bei einer Batterie beim Militär, bei der mehrere Kanonen eingesetzt werden, um eine möglichst große Wirkung zu entfalten, hatte Marsaglia die Idee, eine Testsuite, also ein Sortiment von Tests zu benutzen, um die Zufälligkeit zu messen oder abzuschätzen. Er nutzte hierfür den Begriff einer „Testbatterie“. Erstmals im Jahr 1995 veröffentlichte er seine Diehard Battery of Tests of Randomness, deutsch sinngemäß „Diehard-Testbatterie auf Zufälligkeit“. Sie erschien auf einer CD-ROM zusammen mit Dateien, die große Mengen (viele Megabyte) an Zufallszahlen bereitstellten. Im Jahr 2006 wurden diese ursprünglichen Diehard-Tests durch Robert G. Brown von der Duke University zu Dieharder-Tests erweitert.

Im Folgenden werden die von George Marsaglia in den 1990er-Jahren vorgeschlagenen Diehard-Tests kurz beschrieben. Details können seiner Textdatei entnommen werden (siehe auch: test.txt in Diehard.zip unter Weblinks). Die meisten Tests ergeben einen p‑Wert, der das Ergebnis der Untersuchung zusammenfasst und zwischen Null und Eins liegt. Falls ein Test nicht bestanden wird, die Zufallsfolge also als „schlecht“ erkannt wird, dann ist der p‑Wert sehr nahe bei 0 oder bei 1. Bei einer als „gut“ bewerteten Folge liegt er dazwischen, jedoch nicht zwingend bei 0,5 in der Mitte. Im Einzelfall können p‑Werte nahe 0 oder 1 „durch Zufall passieren“. Über alle Tests gesehen, sollten sie näherungsweise gleichverteilt zwischen 0 und 1 liegen.

Geburtstagsabstände (Birthday Spacings)

Die Bezeichnung ist angelehnt an das Geburtstagsparadoxon. Der Test wählt abhängig von der zu prüfenden Folge zufällige Punkte in einem großen Intervall, ähnlich wie Geburtstage innerhalb eines Jahres. Dazu werden systematisch unterschiedliche, spezifische Bits aus der Folge ausgewählt und diese als Zeitpunkte interpretiert. Die Abstände zwischen den Zeitpunkten (Geburtstagen) sollten asymptotisch einer Poisson-Verteilung entsprechen.

Überlappende Permutationen (Overlapping Permutations)

Hier werden jeweils fünf aufeinanderfolgende ganze Zahlen (Integers oder Bytes) betrachtet. Logischerweise gibt es für fünf unterschiedliche Elemente 5! (Fakultät), also 120 denkbare Anordnungen (Permutationen). Diese sollten im statistischen Mittel in der Folge mit gleicher Wahrscheinlichkeit auftreten.

Ränge von 31×31-Matrizen (Binary Rank Test)

Hierzu werden der zu prüfenden Folge systematisch einzelne Bits entnommen und damit eine Matrix der Größe 31×31 binär aufgefüllt. Anschließend wird der Rang der Matrix bestimmt, der theoretisch zwischen 0 und 31 liegen kann, wobei jedoch Ränge kleiner als 28 vergleichbar selten auftreten sollten. Die Ergebnisse von 40.000 Versuchen werden mithilfe des Chi-Quadrat-Tests mit dem Erwartungswert verglichen.

Ränge von 32×32-Matrizen

Dieser Test entspricht dem vorherigen, jedoch hier mit Matrizen der Größe 32×32.

Ränge von 6×8-Matrizen

Hier werden jeweils sechs Bytes, also 6×8 Bits, der Folge entnommen und diese in eine Matrix geschrieben. Auch hier werden die Ränge der Matrizen bestimmt, wobei Ränge kleiner als 4 entsprechend selten auftreten sollten.

Bitfolge (Bitstream Test)

Die Zufallsfolge wird überlappend bitmäßig betrachtet und aus jeweils 20 aufeinanderfolgenden Bits wird ein „Wort“ (aus Nullen und Einsen) gebildet. Das Vorkommen aller denkbaren 2²⁰, also 1.048.576 möglichen „Wörter“ wird geprüft und speziell das Nicht-Vorkommen von Wörtern gezählt. Im Idealfall sollten diese normalverteilt sein.

Affentests

Wenn nur ausreichend lange zufällig auf einer Schreibmaschine getippt wird, dann entstehen so auch sinnvolle Texte.

Grundlage ist das Theorem des endlos tippenden Affen, das besagt, dass ein Affe, der unendlich lange zufällig auf einer Schreibmaschine herumtippt, irgendwann auch jedes beliebige Buch schreiben wird.

Überlappende Paare

Hier werden jeweils zehn Bit aus der Folge entnommen und als ein „Buchstabe“ aus einem „Alphabet“ mit 2¹⁰ also 1024 möglichen Buchstaben aufgefasst. Zwei solcher Buchstaben als Paar ergeben ein „Wort“. Auf diese Weise werden systematisch nacheinander insgesamt 2²¹ gleich 2.097.152 Wörter gebildet. Anschließend wird geprüft, wie viele Wörter nicht ein einziges Mal aufgetreten sind.

Überlappende Quadrupel

Dasselbe wird statt mit Buchstabenpaaren, also Wörtern der Länge zwei, auch mit Wörtern der Länge vier durchgeführt, also Buchstaben-Quadrupeln.

Überlappende DNAs

Drittens werden jeweils zwei Bit aus der Folge entnommen und als ein DNA-Baustein Adenin (A), Guanin (G), Thymin (T) oder Cytosin (C) interpretiert. Man könnte auch sagen, als ein Buchstabe aus einem Alphabet mit nur vier Buchstaben. Jeweils zwanzig Bits können nun als ein Wort aus zehn dieser Buchstaben aufgefasst werden. Hier sind 4¹⁰ unterschiedliche Wörter möglich, deren statistische Verteilung durch den Test überprüft wird.

Zähl die Einsen für eine Bytefolge (Count-The-1s)

Nacheinander wird jedes einzelne Byte der Folge betrachtet. In jedem Byte können zwischen null und acht binäre Einsen auftreten, wobei diese neun Fälle unterschiedlich häufig sind (1, 8, 28, 56, 70, 56, 28, 8, 1). Für die Extremfälle (null Einsen und acht Einsen) gibt es nur jeweils eine Möglichkeit; jedoch für vier Einsen gibt es 70 Möglichkeiten. Mithilfe des Chi-Quadrat-Tests wird die Erfüllung des Erwartungswerts überprüft.

Zähl die Einsen für spezielle Bytes

Innerhalb eines 32-bit-Datenworts werden acht Bit ausgewählt und die Anzahl der Einsen gezählt. Anschließend werden die einzelnen Zählergebnisse in Buchstaben umgesetzt, wobei null bis zwei Einsen den Buchstaben A ergeben, drei ein B, vier ein C, fünf ein D und sechs bis acht Einsen ein E. Somit ergeben sich Wörter aus fünf Buchstaben mit unterschiedlichen Wahrscheinlichkeiten der Buchstaben von 37, 56, 70, 56 und 37 aus 256 Fällen. Geprüft wird die Auftretenshäufigkeit aller Wörter im Vergleich zu den einzelnen Erwartungswerten.

Parkplatztest (Parking Lot Test)

Auf einem quadratischen Feld („Parkplatz“) der Größe 100×100 wird an einer beliebigen Stelle, dessen Ort (x-y-Koordinate) durch Werte der Folge bestimmt ist, ein kreisförmiges Objekt („Auto“) platziert. Ist der Platz noch frei und gelingt dies ohne Überlappung („Zusammenstoß“) mit bereits platzierten Objekten, dann erhöht sich die Anzahl der bereits erfolgreich geparkten Autos um eins. Geprüft wird hier die Anzahl der Erfolge über der Anzahl der Versuche, die sich für perfekt zufällige Platzierungen exakt vorhersagen lässt. Aus der Abweichung der Anzahl im Versuch lässt sich auf die Qualität der Zufallsfolge schließen.

Mindestabstandstest (Minimum Distance Test)

Innerhalb eines Quadrates der Seitenlänge 10000 werden abhängig von der Folge viele Punkte an zufälliger x-y-Koordinate gewählt, und zwar insgesamt 8000 Punkte. Nun werden die Abstände zwischen sämtlichen Punktepaaren berechnet und der minimale Abstand betrachtet. Dieses Experiment wird hundert Mal wiederholt und die Abweichungen vom Erwartungswert als Kriterium für die Qualität der Zufallsfolge berechnet.

Kugel-Test (3D Spheres Test)

Innerhalb eines Würfels (Kubus) der Kantenlänge 1000 werden anhand der Folge 4000 Orte (x-y-z-Koordinaten) gewählt. Um jeden Ort als Mittelpunkt wird eine Kugel platziert, deren Radius so groß gewählt wird, dass sie gerade den nächsten Punkt berührt. Der Radius der kleinsten aller Kugeln sollte bei perfekt zufälliger Folge 120·$\pi$/3 betragen. Abweichungen deuten auf Unvollkommenheiten der Folge hin.

Quetsch-Test (Squeeze Test)

Hierbei nutzt man eine bestimmte Programmierfunktion, die eine beliebige reelle Zahl auf die nächstgrößere ganze Zahl rundet. Eine 32-Bitfolge wird als reelle Zahl von mindestens Null und kleiner als Eins aufgefasst, also zwischen 0 und 0,999… liegend („gefloatet“). Diese Zahl wird mit 2³¹ gleich 2.147.483.648 multipliziert. Das Produkt wird, falls es keine ganze Zahl ist, auf die nächstgrößere ganze Zahl aufgerundet („ceiling“). Falls diese nicht Eins ist, dann wird das Ergebnis erneut mit der ursprünglichen reellen Zahl multipliziert. Dieser Vorgang wird so lange wiederholt, bis sich Eins ergibt. Die Zahl der nötigen Wiederholungen ist hier das Kriterium dieses Quetsch-Testes.

Der Quetsch-Test wird 100.000 Mal durchgeführt. Dabei muss sich eine bestimmte Verteilung der Kriteriums-Zahlen ergeben.

Überlappende Summen (Overlapping Sums Test)

Auch hierbei werden Bitfolgen als reelle Zahlen interpretiert, die im Intervall zwischen Null und kleiner als Eins liegen, also [0,1). Jeweils hundert nacheinander so erzeugte reelle Zahlen werden summiert. Anschließend wird der erste Summand entfernt und dafür ein hunderterster neu aufgenommen. Und so weiter. Für die Summenfolgen sollten sich charakteristische Mittelwerte und Varianzen ergeben.

Runs-Test

→ Hauptartikel: Run-Test

Wieder werden Bitfolgen als reelle Zahlen zwischen Null und Eins aufgefasst. Geprüft werden die jeweils auftretenden Längen von aufsteigenden beziehungsweise absteigenden Zahlenwerten, die bei idealen Zufallszahlen einer bestimmten statistischen Verteilung entsprechen.

Craps-Test

→ Hauptartikel: Craps

Anhand der zu prüfenden Zahlenfolge werden 200.000 Craps-Spiele durchgeführt. Gezählt werden die Anzahl der Würfe pro Spiel und die Anzahl der Siege. Bei idealen Zufallszahlen sollten beide einer bestimmten Verteilung folgen.

Hinweis

Ein wichtiger Hinweis, den Marsaglia gab, war: „So keep in mind that ‘p happens’.“ Hier vielleicht schlicht zu übersetzen mit: „Bedenke, dass ‘Zufall passiert’.“ Er weist darauf hin, dass der Test einer einzelnen Ausgangsfolge auch eines wirklich exzellenten Zufallsgenerators gelegentlich durchaus einmal ein weit vom Erwartungswert abweichendes Ergebnis produzieren kann. Das ist jedoch kein Beweis für dessen vermeintlich schlechte Qualität, sondern einfach Zufall. Auch beim Roulette kann mehrfach hintereinander dieselbe Farbe fallen (siehe auch: Umgekehrter Spielerfehlschluss). Das ist nicht unmöglich, sondern hat seinen Grund in der Tatsache, die der französische Mathematiker Joseph Bertrand (1822–1900) einst prägnant formulierte: „Der Zufall hat kein Gedächtnis.“

Literatur

• A. Kälin: Statistische Tests für die Zufälligkeit von Zeichen- und Zahlenfolgen. ETH Zürich, 1976, PDF; 7 MB.

Weblinks

Wiktionary: diehard – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen (englisch)

• Diehard.zip. Die originale Diehard Battery von 1995 als ZIP-Datei (600 kB, englisch).
• The Marsaglia Random Number CDROM including the Diehard Battery of Tests of Randomness. Abbild der kompletten CD‑ROM von 1995 (englisch).
• Robert G. Brown’s General Tools Page, enthält das Dieharder-Programm (englisch).
• Random Bit Generation. Richtlinien und Empfehlungen zur Generierung von Zufallszahlen vom NIST (englisch).