TestU01

TestU01 är ett statistiskt empiriskt testpaket implementerat i ANSI C som tillhandahåller en uppsättning verktyg för att testa slumptalsgeneratorer . Den senaste versionen av biblioteket introducerades 2007 av Pierre L'Ecuyer och Richard Simard från University of Montreal [1] .

Paketet innehåller flera typer av PRNG:er , inklusive några föreslagna i litteraturen och några som används ofta i programvara . Den ger allmänna implementeringar av klassiska statistiska tester för slumptalsgeneratorer, såväl som de som föreslagits i litteraturen och några original. Dessa tester kan tillämpas på generatorer som redan finns i biblioteket, anpassade generatorer och slumptalsströmmar. Specialtester testar alla sekvenser av enhetligt fördelade slumptal i eller bitsekvenser. Grundläggande verktyg för att konstruera punktvektorer som genereras av generatorer finns också [1] . $[0,1]$

Historik [1]

TestU01 implementerades först 1985 i Pascal och innehöll tester föreslagna av Donald Knuth i den andra upplagan av andra volymen av The Art of Programming [2] . Fyra år senare implementerades det på nytt i Modula-2- språket som ett paket med en modulär design . Sedan, tillsammans med nya tester, lades några av de vanligaste PRNG:erna till. Mellan 1990 och 2001 uppdaterades paketet regelbundet med nya generatorer och tester, och användarmanualen uppdaterades i tid (på franska). moduler som innehåller verktyg för att testa familjer av generatorer introducerades först 1997. 2002 gjorde Pierre L'Ecuyer och Richard Simard om biblioteket, implementerade det i C och översatte manualen till engelska. $f$

PRNG-kvalitetskriterier

PRNG:er är huvudsakligen utformade för att väl simulera en sekvens av oberoende slumpvariabler , vanligtvis i ett reellt intervall eller i en binär uppsättning . I det första fallet säger hypotesen 0 A att talen 0 , 1 , 2 , 3 ... är oberoende storheter från en enhetlig fördelning i intervallet [3] . I den andra säger 0 B att det finns en sekvens av oberoende slumpmässiga bitar, som var och en tar på sig värdet eller med lika stor sannolikhet [3] . $(0,1)$ $[0,1]$ $\mathrm{H}$ $u$ $u$ $u$ $u$ $(0,1)$ $\mathrm{H}$ $0$ $ett$

$\mathrm{H}$ 0 A motsvarar att säga att för vilken heltalsvektor som helst( 0 , ...,) är likformigt fördelad ien dimensionell kub. För algoritmiska PRNG:er är påståendet falskt, eftersom vektorerna i dem tar sina värden från ett ändligt antalalldimensionellavektorer som generatorn kan producera [3] . $t$ $u$ $u$ $t-1$ $t$ $(0,1)$ $t$ $\psi$ $t$ $t$

För en sekvens av bitar kan hypotesen 0 B inte heller formellt kallas sann i fallet när längden på sekvensen överstiger antalet bitar av generatortillstånd, eftersom antalet möjliga sekvenser som produceras inte kan överstiga [3] . Generatorns uppgift är att se till att sekvenserna i fältet av alla möjliga sekvenser i . $\mathrm{H}$ $t$ $b$ $2$ $b$ $2$ $t$

Ett annat kvalitetskriterium för PRNG används i kryptologi och spelautomater. Här, utöver allt ovanstående, ägnas särskild uppmärksamhet åt oförutsägbarheten av efterföljande nummer [3] .

Funktioner [1]

TestU01 erbjuder fyra grupper av moduler för att arbeta med generatorer:

implementering av en förprogrammerad generator (modul ); $u$
genomförande av särskilda statistiska tester (modul ); $s$
implementering av statistiska testbatterier (modul ); $b$
tillämpning av tester på hela familjer av generatorer (modul ). $f$

När ett visst test appliceras på utmatningen av en storleksgenerator , förblir p - värdet för testet vanligtvis rimligt tills storleken på data når ett visst värde . Därefter divergerar p - värdet till eller med en exponentiell hastighet. Modulen låter forskaren utforska sambandet mellan ett specifikt test och strukturen av en uppsättning poäng som erhålls med hjälp av en specifik familj av generatorer. Denna teknik kan användas för att bestämma storleken på data som ska testas, beroende på generatorns längd, innan generatorn systematiskt börjar misslyckas i testerna. $n$ $n_{0}$ $0$ $ett$ $f$

TestU01 erbjuder flera testbatterier som SmallCrush (bestående av 10 tester), Crush (96 tester) och BigCrush (106 tester). På en Pentium 4 -baserad dator med ett Linux- operativsystem , för en enkel generator, tar batteritiden för SmallCrush-tester flera minuter, Crush - ungefär en timme, BigCrush - ungefär ett dussin timmar [3] .

Andra program för att testa PRNG

Ett av de mycket använda PRNG-testpaketen är DIEHARD [4] , som innehåller ett stort antal statistiska tester, men har ett antal nackdelar och begränsningar. För det första är testsekvensen, såväl som deras parametrar (såsom provstorlek, etc.) fixerade, vilket har en dålig effekt på testhastigheten [3] . För det andra kräver DIEHARD 32-bitars heltal skrivna i binärt som input , medan många generatorer producerar tal mindre än 32 bitar [3] . Jämfört med TestU01 är DIEHARD-paketet mindre flexibelt i dessa aspekter [3] .

Ett annat offentligt testpaket är SPRNG [5] -biblioteket , som inkluderar de klassiska testerna som beskrivs i Konsten att programmera [2] . National Institute of Standards and Technology har också utvecklat sin egen uppsättning av 15 tester för att testa generatorer som används i kryptografi [6] .

Batterier

Alphabit- batteriet skapades för att testa hårdvarugeneratorer för slumptal . Genomför nio på varandra följande tester innan varje omskrivning av indata.

Kanin är ett batteri fokuserat mer på att testa binära data , men vissa tester klarar med fasta parametrar, oavsett hur stor ingången är. Därför leder data större än 64 megabyte till ett fel i ett av testerna och leder till ett överflöd av RAM . [7]

SmallCrush , ett litet och snabbt batteri av tester, läser generatorn som en fil som innehåller flöten inom . Filgränsen är strax under 51320000 slumptal. Filen kommer att skrivas över i början av varje test. Vissa tester kräver att generatorn returnerar minst 30 bitar av lösningen, annars är det mycket troligt att generatorn misslyckas med dem. Används vanligtvis för att kontrollera genomförbarheten av testning på strängare batterier [7] . $[0,1)$

Crush - Ett batteri av rigorösa statistiska tester. Innehåller både de klassiska Knuth-testerna och många andra. Vissa av dessa tester förutsätter att generatorn returnerar minst 30 bitar av lösningen, annars misslyckas testerna. Ett av testerna kräver 31 bitar data. Batteriet använder ungefär 2 35 slumptal [7] .

BigCrush är ett batteri av de mest stränga statistiska testerna. Som med andra batterier kräver vissa tester minst 30 bitars inmatning, annars misslyckas testerna. Ett av testerna kräver också 31 bitar data. Batteriet använder nästan 238 slumptal. När BigCrush först dök upp hade till och med PRNGs som ansågs bra svårt att ta sig förbi det [7] .

SmallCrush Battery Tests

Här är några exempel på SmallCrush-batteritester [1] .

Födelsedag Spasings	Ett test baserat på födelsedagsparadoxen . Slumpmässiga punkter på ett stort intervall väljs, avstånden mellan vilka måste vara asymptotiskt Poisson-fördelade .
glipa	Ett test som används för att bestämma intervallet mellan repetitioner av samma siffra.
CouponCollector	Låt en följd av längden n och dimensionen m. Vi studerar sekvenser av en viss längd som innehåller ett m-bitars tal. $\xi _{1},\xi _{2},\dots ,\xi _{n}$
MatrixRank	Testet väljer ett visst antal bitar från ett visst antal slumpmässiga tal för att bilda en matris över {0,1}. Därefter bestäms matrisens rangordning.

Litteratur

Pierre L'Ecuyer, Richard Simard. TestU01: AC-bibliotek för empirisk testning av slumptalsgeneratorer. — D'epartement d'Informatique et de Recherche Op'erationnelleUniversit'e de Montr'eal: ACM Transactions on Mathematical Software, 2007. — 40 sid.
Knuth D.E. The Art of Computer Programming volym 2, - ISBN 0-201-89684-2 .

Länkar

TestU01-webbplatsen. . (obestämd)
TestU01. Ett mjukvarubibliotek i ANSI C för empirisk testning av slumptalsgeneratorer. . (obestämd)

Anteckningar

↑ 1 2 3 4 5 Pierre L'Ecuyer, Richard Simard. TestU01: AC-bibliotek för empirisk testning av slumptalsgeneratorer // ACM Trans. Matematik. Softw .. - Augusti 2007. - T. 33 , nr. 4 . — S. 22:1–22:40 . — ISSN 0098-3500 . doi : 10.1145 / 1268776.1268777 .
↑ 12 D.E. Knuth. Konsten att programmera, volym 2: Seminumeriska algoritmer . - Addison-Wesley, 1981. - 142 sid. Arkiverad 4 september 2008 på Wayback Machine
↑ 1 2 3 4 5 6 7 8 9 Pierre L'Ecuyer och Richard Simard. Ett programbibliotek i ANSI C för empirisk testning av slumptalsgeneratorer . - 2013. - S. 219. Arkivexemplar daterad 9 december 2014 på Wayback Machine
↑ Marsaglia . ] DIEHARD: ett batteri av slumpmässighetstester (nedlänk) . Institutionen för statistik (1996). Arkiverad från originalet den 20 januari 2016. (obestämd)
↑ M. Mascagni och A. Srinivasan. Algoritm 806: SPRNG: Ett skalbart bibliotek för generering av pseudoslumptal // ACM-transaktioner på matematisk programvara. - 2000. - 1 december ( vol. 26 , nr 4 ). — S. 436–461 .
↑ CSRC - NIST SP 800-22: Dokumentation och programvara . csrc.nist.gov. Hämtad 24 september 2017. Arkiverad från originalet 25 september 2017. (obestämd)
↑ 1 2 3 4 TestU01-resultat - BitBabbler . www.bitbubbler.org Hämtad 26 september 2017. Arkiverad från originalet 6 oktober 2017.