TestU01

TestU01 je balíček statistických empirických testů implementovaný v ANSI C , který poskytuje sadu nástrojů pro testování generátorů náhodných čísel . Nejnovější verzi knihovny představili v roce 2007 Pierre L'Ecuyer a Richard Simard z University of Montreal [1] .

Balíček obsahuje několik typů PRNG , včetně některých navržených v literatuře a některých široce používaných v softwaru . Uvádí obecné implementace klasických statistických testů pro generátory náhodných čísel, stejně jako ty navržené v literatuře a některé původní. Tyto testy lze aplikovat na generátory již v knihovně, vlastní generátory a proudy náhodných čísel. Speciální testy testují libovolné sekvence rovnoměrně rozložených náhodných čísel v nebo bitových sekvencích. Nechybí ani základní nástroje pro konstrukci bodových vektorů generovaných generátory [1] . $[0,1]$

Historie [1]

TestU01 byl poprvé implementován v roce 1985 v Pascalu a obsahoval testy navržené Donaldem Knuthem ve druhém vydání druhého dílu The Art of Programming [2] . O čtyři roky později byl znovu implementován v jazyce Modula-2 jako balíček s modulárním designem . Poté byly spolu s novými testy přidány některé z nejčastěji používaných PRNG. V letech 1990 až 2001 byl balíček pravidelně aktualizován o nové generátory a testy a uživatelská příručka byla včas aktualizována (ve francouzštině). moduly obsahující nástroje pro testování rodin generátorů byly poprvé představeny v roce 1997. V roce 2002 Pierre L'Ecuyer a Richard Simard přepracovali knihovnu, implementovali ji v C a přeložili příručku do angličtiny. $F$

Kritéria kvality PRNG

PRNG jsou hlavně navrženy tak, aby dobře simulovaly sekvenci nezávislých náhodných proměnných , obvykle v reálném intervalu nebo v binární množině . V prvním případě hypotéza 0 A říká, že čísla 0 , 1 , 2 , 3 ... jsou nezávislé veličiny z rovnoměrného rozdělení v intervalu [3] . Ve druhém 0 B říká, že existuje sekvence nezávislých náhodných bitů, z nichž každý nabývá hodnoty nebo se stejnou pravděpodobností [3] . $(0,1)$ $[0,1]$ $\mathrm{H}$ $u$ $u$ $u$ $u$ $(0,1)$ $\mathrm{H}$ $0$ $jeden$

$\mathrm{H}$ 0 A je ekvivalentní tvrzení, že pro jakékoli celé číslo jevektor ( 0 , ...,) rovnoměrně rozložen v-rozměrné krychli. U algoritmických PRNG je tvrzení nepravdivé, protože vektory v nich přebírají své hodnoty z konečného počtuvšerozměrnýchvektorů, které je generátor schopen vytvořit [3] . $t$ $u$ $u$ $t-1$ $t$ $(0,1)$ $t$ $\psi$ $t$ $t$

Pro posloupnost bitů nelze hypotézu 0 B také formálně označit za pravdivou v případě, kdy délka sekvence překročí počet bitů stavů generátoru, protože počet možných vytvořených sekvencí nemůže překročit [3] . Úkolem generátoru je zajistit, aby sekvence v poli všech možných sekvencí v . $\mathrm{H}$ $t$ $b$ $2$ $b$ $2$ $t$

Dalším kritériem kvality pro PRNG se používá v kryptologii a výherních automatech. Zde je kromě všeho výše uvedeného věnována zvláštní pozornost nepředvídatelnosti následných čísel [3] .

Funkce [1]

TestU01 nabízí čtyři skupiny modulů pro práci s generátory:

implementace předprogramovaného generátoru (modulu ); $u$
implementace speciálních statistických testů (modul ); $s$
implementace statistických testovacích baterií (modul ); $b$
aplikace testů na celé rodiny generátorů (modul ). $F$

Když je na výstupu generátoru velikosti aplikován konkrétní test , zůstává p - hodnota testu obvykle přiměřená, dokud velikost dat nedosáhne určité hodnoty . Poté se hodnota p odchyluje k nebo exponenciální rychlostí. Modul umožňuje výzkumníkovi prozkoumat vztah mezi konkrétním testem a strukturou množiny bodů získaných pomocí specifické rodiny generátorů. Tato technika může být použita k určení velikosti dat, která mají být testována, v závislosti na délce periody generátoru, než generátor začne systematicky selhávat v testech. $n$ $n_{0}$ $0$ $jeden$ $F$

TestU01 nabízí několik testovacích baterií, jako je SmallCrush (skládající se z 10 testů), Crush (96 testů) a BigCrush (106 testů). Na počítači založeném na Pentiu 4 s operačním systémem Linux u jednoduchého generátoru trvá výdrž baterie testů SmallCrush několik minut, Crush - asi hodinu, BigCrush - asi tucet hodin [3] .

Další programy pro testování PRNG

Jedním z široce používaných testovacích balíků PRNG je DIEHARD [4] , který obsahuje velké množství statistických testů, má však řadu nevýhod a omezení. Jednak je pevně stanovena posloupnost testů a také jejich parametry (jako je velikost vzorku apod.), což má špatný vliv na rychlost testování [3] . Za druhé, DIEHARD vyžaduje 32bitová celá čísla zapsaná binárně jako vstup , zatímco mnoho generátorů produkuje čísla menší než 32 bitů [3] . Ve srovnání s TestU01 je balíček DIEHARD v těchto aspektech méně flexibilní [3] .

Dalším veřejným testovacím balíčkem je knihovna SPRNG [5] , která zahrnuje klasické testy popsané v The Art of Programming [2] . Také National Institute of Standards and Technology vyvinul vlastní sadu 15 testů pro testování generátorů používaných v kryptografii [6] .

Baterie

Baterie Alphabit byla vytvořena pro testování hardwarových generátorů náhodných čísel . Před každým přepsáním vstupních dat provede devět po sobě jdoucích testů.

Rabbit je baterie zaměřená spíše na testování binárních dat , ale některé testy projdou s pevnými parametry, bez ohledu na to, jak velký je vstup. Data větší než 64 MB proto vedou k chybě v jednom z testů a vedou k přetečení paměti RAM . [7]

SmallCrush , malá a rychlá baterie testů, čte generátor jako soubor obsahující floats v . Limit souboru je těsně pod 51320000 náhodných čísel. Soubor bude přepsán na začátku každého testu. Některé testy vyžadují, aby generátor vrátil alespoň 30 bitů řešení, jinak je generátor velmi pravděpodobně selže. Obvykle se používá ke kontrole proveditelnosti testování na přísnějších bateriích [7] . $[0,1)$

Crush – Baterie přísných statistických testů. Zahrnuje jak klasické Knuthovy testy, tak mnoho dalších. Některé z těchto testů předpokládají, že generátor vrátí alespoň 30 bitů řešení, jinak testy selžou. Jeden z testů vyžaduje 31 bitů dat. Baterie používá přibližně 2 35 náhodných čísel [7] .

BigCrush je baterie nejpřísnějších statistických testů. Stejně jako u jiných baterií vyžadují některé testy alespoň 30 bitů vstupu, jinak testy selžou. Jeden z testů také vyžaduje 31 bitů dat. Baterie používá téměř 238 náhodných čísel. Když se BigCrush poprvé objevil, dokonce i PRNG, které byly považovány za dobré, měly problém se přes to dostat [7] .

Testy baterií SmallCrush

Zde je několik příkladů testů baterií SmallCrush [1] .

Narozeninové spasingy	Test založený na narozeninovém paradoxu . Jsou vybrány náhodné body na velkém intervalu, vzdálenosti mezi nimiž musí být asymptoticky Poissonově rozděleny .
mezera	Test používaný k určení intervalu mezi opakováními stejné číslice.
CouponCollector	Nechť posloupnost délky n a dimenze m. Studujeme posloupnosti určité délky, které obsahují m-bitové číslo. $\xi _{1},\xi _{2},\tečky ,\xi _{n}$
MatrixRank	Test vybere určitý počet bitů z určitého počtu náhodných čísel k vytvoření matice nad {0,1}. Poté se určí hodnost matice.

Literatura

Pierre L'Ecuyer, Richard Simard. TestU01: AC knihovna pro empirické testování generátorů náhodných čísel. — D'epartement d'Informatique et de Recherche Op'erationnelleUniversit'e de Montr'eal: ACM Transactions on Mathematical Software, 2007. — 40 s.
Knuth D.E. The Art of Computer Programming, svazek 2, - ISBN 0-201-89684-2 .

Odkazy

Web TestU01. . (neurčitý)
TestU01. Softwarová knihovna v ANSI C pro empirické testování generátorů náhodných čísel. . (neurčitý)

Poznámky

↑ 1 2 3 4 5 Pierre L'Ecuyer, Richard Simard. TestU01: AC knihovna pro empirické testování generátorů náhodných čísel // ACM Trans. Matematika. Softw .. - srpen 2007. - T. 33 , no. 4 . — S. 22:1–22:40 . — ISSN 0098-3500 . doi : 10.1145 / 1268776.1268777 .
↑ 12 D. E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms . - Addison-Wesley, 1981. - 142 s. Archivováno 4. září 2008 na Wayback Machine
↑ 1 2 3 4 5 6 7 8 9 Pierre L'Ecuyer a Richard Simard. Softwarová knihovna v ANSI C pro empirické testování generátorů náhodných čísel . - 2013. - S. 219. Archivní kopie ze dne 9. prosince 2014 na Wayback Machine
↑ Marsaglia . ] DIEHARD: baterie testů náhodnosti (downlink) . Katedra statistiky (1996). Archivováno z originálu 20. ledna 2016. (neurčitý)
↑ M. Mascagni a A. Srinivasan. Algoritmus 806: SPRNG: Škálovatelná knihovna pro generování pseudonáhodných čísel // ACM Transactions on Mathematical Software. - 2000. - 1. prosince ( roč. 26 , č. 4 ). — S. 436–461 .
↑ CSRC - NIST SP 800-22: Dokumentace a software . csrc.nist.gov. Získáno 24. září 2017. Archivováno z originálu 25. září 2017. (neurčitý)
↑ 1 2 3 4 Výsledky TestU01 - BitBabbler . www.bitbubbler.org Získáno 26. září 2017. Archivováno z originálu 6. října 2017.