TestU01

TestU01 on ANSI C :ssä toteutettu tilastollinen empiirinen testipaketti , joka tarjoaa joukon apuohjelmia satunnaislukugeneraattoreiden testaamiseen . Pierre L'Ecuyer ja Richard Simard Montrealin yliopistosta esittelivät kirjaston uusimman version vuonna 2007 [1] .

Paketti sisältää useita PRNG -tyyppejä , mukaan lukien joitain kirjallisuudessa ehdotettuja ja joitain laajasti ohjelmistoissa käytettyjä . Se antaa yleisiä toteutuksia klassisista tilastollisista testeistä satunnaislukugeneraattoreille, samoin kuin kirjallisuudessa ehdotetut ja eräät alkuperäiset testit. Näitä testejä voidaan soveltaa kirjastossa jo oleviin generaattoreihin, mukautettuihin generaattoreihin ja satunnaislukuvirtoihin. Erikoistekeillä testataan kaikki tasaisesti jakautuneiden satunnaislukujen sekvenssit bittisarjoissa. Mukana on myös perustyökaluja generaattoreiden generoimien pistevektoreiden rakentamiseen [1] . $[0,1]$

Historia [1]

TestU01 otettiin käyttöön ensimmäisen kerran vuonna 1985 Pascalissa , ja se sisälsi Donald Knuthin ehdottamia testejä ohjelmoinnin taiteen toisen osan toisessa painoksessa [2] . Neljä vuotta myöhemmin se otettiin uudelleen käyttöön Modula-2- kielellä modulaarisena pakettina . Sitten uusien testien ohella joitain yleisimmin käytetyistä PRNG:istä lisättiin. Vuosina 1990-2001 pakettia päivitettiin säännöllisesti uusilla generaattoreilla ja testeillä, ja käyttöopas päivitettiin oikea-aikaisesti (ranskaksi). generaattoriperheiden testaustyökaluja sisältävät moduulit esiteltiin ensimmäisen kerran vuonna 1997. Vuonna 2002 Pierre L'Ecuyer ja Richard Simard suunnittelivat kirjaston uudelleen, ottivat sen käyttöön C -kielellä ja käänsivät oppaan englanniksi. $f$

PRNG-laatukriteerit

PRNG:t on pääasiassa suunniteltu simuloimaan hyvin riippumattomien satunnaismuuttujien sarjaa , yleensä reaalivälissä tai binäärijoukossa . Ensimmäisessä tapauksessa hypoteesi 0 A sanoo, että luvut 0 , 1 , 2 , 3 ... ovat riippumattomia suureita tasaisesta jakaumasta alueella [3] . Toisessa 0 B sanoo, että on sarja itsenäisiä satunnaisia bittejä, joista jokainen saa arvon tai samalla todennäköisyydellä [3] . $(0,1)$ $[0,1]$ $\mathrm{H}$ $u$ $u$ $u$ $u$ $(0,1)$ $\mathrm{H}$ $0$ $yksi$

$\mathrm{H}$ 0 A vastaa sanomista, että minkä tahansa kokonaisluvunvektori ( 0 , ...,) on jakautunut tasaisesti-ulotteiseen kuutioon. Algoritmisille PRNG:ille lause on väärä, koska niissä olevat vektorit ottavat arvonsa äärellisestä määrästäkaikkiulotteisiavektoreita, jotka generaattori pystyy tuottamaan [3] . $t$ $u$ $u$ $t-1$ $t$ $(0,1)$ $t$ $\psi$ $t$ $t$

Bittisekvenssille hypoteesia 0 B ei voida myöskään muodollisesti kutsua todeksi siinä tapauksessa , että sekvenssin pituus ylittää generaattoritilojen bittien lukumäärän, koska mahdollisten sekvenssien määrä ei voi ylittää [3] . Generaattorin tehtävänä on varmistaa, että kaikki mahdolliset sekvenssit kentässä ovat . $\mathrm{H}$ $t$ $b$ $2$ $b$ $2$ $t$

Toista PRNG:n laatukriteeriä käytetään kryptologiassa ja peliautomaateissa. Kaiken edellä mainitun lisäksi tässä kiinnitetään erityistä huomiota myöhempien lukujen arvaamattomuuteen [3] .

Ominaisuudet [1]

TestU01 tarjoaa neljä moduuliryhmää generaattoreiden kanssa työskentelemiseen:

esiohjelmoidun generaattorin (moduulin ) käyttöönotto; $u$
erityisten tilastollisten testien toteuttaminen (moduuli ); $s$
tilastollisten testiakkujen käyttöönotto (moduuli ); $b$
testien soveltaminen kokonaisille generaattoriperheille (moduuli ). $f$

Kun tiettyä testiä sovelletaan kokogeneraattorin ulostuloon, testin p - arvo pysyy yleensä kohtuullisena, kunnes datan koko saavuttaa tietyn arvon . Sen jälkeen p - arvo poikkeaa eksponentiaalisella nopeudella. Moduulin avulla tutkija voi tutkia tietyn testin ja tietyllä generaattoriperheellä saadun pistejoukon rakenteen välistä suhdetta. Tällä tekniikalla voidaan määrittää testattavan datan koko riippuen generaattorin ajanjakson pituudesta, ennen kuin generaattori alkaa systemaattisesti epäonnistua testeissä. $n$ $n_{0}$ $0$ $yksi$ $f$

TestU01 tarjoaa useita testiakkuja, kuten SmallCrush (koostuu 10 testistä), Crush (96 testiä) ja BigCrush (106 testiä). Pentium 4 -pohjaisessa tietokoneessa, jossa on Linux - käyttöjärjestelmä , yksinkertaisella generaattorilla SmallCrush-testien akunkesto kestää useita minuutteja, Crush - noin tunnin, BigCrush - noin tusina tuntia [3] .

Muita ohjelmia PRNG:n testaamiseen

Yksi laajalti käytetyistä PRNG-testipaketeista on DIEHARD [4] , joka sisältää suuren määrän tilastollisia testejä, mutta jolla on useita haittoja ja rajoituksia. Ensinnäkin testien järjestys ja niiden parametrit (kuten näytteen koko jne.) ovat kiinteät, mikä vaikuttaa huonosti testausnopeuteen [3] . Toiseksi DIEHARD vaatii syötteenä 32-bittisiä kokonaislukuja, jotka on kirjoitettu binäärimuodossa , kun taas monet generaattorit tuottavat alle 32 bitin lukuja [3] . TestU01:een verrattuna DIEHARD-paketti on näiltä osin vähemmän joustava [3] .

Toinen julkinen testipaketti on SPRNG [5] -kirjasto , joka sisältää ohjelmoinnin taiteessa [2 ] kuvatut klassiset testit . Myös National Institute of Standards and Technology on kehittänyt oman 15 testin sarjan kryptografiassa käytettävien generaattoreiden testaamiseen [6] .

Paristot

Alphabit - akku luotiin testaamaan laitteiston satunnaislukugeneraattoreita . Suorittaa yhdeksän peräkkäistä testiä, ennen kuin jokainen kirjoittaa syöttötiedot uudelleen.

Rabbit on akku, joka keskittyy enemmän binääritietojen testaamiseen , mutta jotkut testit läpäisevät kiinteitä parametreja riippumatta siitä, kuinka suuri tulo on. Siksi yli 64 megatavua suurempi data johtaa virheeseen yhdessä testissä ja johtaa RAM-muistin ylivuotoon . [7]

SmallCrush , pieni ja nopea testisarja, lukee generaattorin tiedostona, joka sisältää kelluvan . Tiedostojen raja on hieman alle 51320000 satunnaislukua. Tiedosto korvataan jokaisen testin alussa. Jotkut testit edellyttävät, että generaattori palauttaa vähintään 30 bittiä ratkaisua, muuten generaattori todennäköisesti epäonnistuu ne. Käytetään yleensä testaamaan tiukempien akkujen testauksen toteutettavuutta [7] . $[0,1)$

Crush - Sarja tiukkoja tilastollisia testejä. Sisältää sekä klassiset Knuthin testit että monet muut. Jotkut näistä testeistä olettavat, että generaattori palauttaa vähintään 30 bittiä ratkaisua, muuten testit epäonnistuvat. Yksi testeistä vaatii 31 bittiä dataa. Akku käyttää noin 2 35 satunnaislukua [7] .

BigCrush on akku tiukimmista tilastollisista testeistä. Kuten muidenkin akkujen kohdalla, jotkin testit vaativat vähintään 30 bitin syöttöä tai testit epäonnistuvat. Myös yksi testeistä vaatii 31 bittiä dataa. Akku käyttää lähes 238 satunnaislukua. Kun BigCrush ilmestyi ensimmäisen kerran, jopa hyviksi pidetyillä PRNG:illä oli vaikeuksia päästä sen ohi [7] .

SmallCrush Battery Tests

Tässä on esimerkkejä SmallCrush-akkutesteistä [1] .

Syntymäpäivät	Syntymäpäiväparadoksiin perustuva testi . Valitaan satunnaisia pisteitä suurelta väliltä, joiden välisten etäisyyksien tulee olla asymptoottisesti Poisson-jakaumia .
aukko	Testi, jolla määritetään saman numeron toistojen välinen aika.
CouponCollector	Olkoon sekvenssi, jonka pituus on n ja mitta m. Tutkimme tietynpituisia sekvenssejä, jotka sisältävät m-bittisen luvun. $\xi _{1},\xi _{2},\pisteet ,\xi _{n}$
MatrixRank	Testi valitsee tietyn määrän bittejä tietystä määrästä satunnaislukuja muodostaakseen matriisin yli 0,1}. Sitten matriisin sijoitus määritetään.

Kirjallisuus

Pierre L'Ecuyer, Richard Simard. TestU01: AC-kirjasto satunnaislukugeneraattoreiden empiiriseen testaukseen. — 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 osa 2, - ISBN 0-201-89684-2 .

Linkit

TestU01-sivusto. . (määrätön)
TestU01. Ohjelmistokirjasto ANSI C:ssä satunnaislukugeneraattoreiden empiiriseen testaukseen. . (määrätön)

Muistiinpanot

↑ 1 2 3 4 5 Pierre L'Ecuyer, Richard Simard. TestU01: AC-kirjasto satunnaislukugeneraattoreiden empiiriseen testaukseen // ACM Trans. Matematiikka. Softw .. - elokuu 2007. - T. 33 , no. 4 . – S. 22:1–22:40 . — ISSN 0098-3500 . doi : 10.1145 / 1268776.1268777 .
↑ 12 D.E. Knuth. Tietokoneohjelmoinnin taito, osa 2: Puolinumeeriset algoritmit . - Addison-Wesley, 1981. - 142 s. Arkistoitu 4. syyskuuta 2008 Wayback Machinessa
↑ 1 2 3 4 5 6 7 8 9 Pierre L'Ecuyer ja Richard Simard. Ohjelmistokirjasto ANSI C:ssä satunnaislukugeneraattoreiden empiiriseen testaukseen . - 2013. - S. 219. Arkistokopio päivätty 9. joulukuuta 2014 Wayback Machinessa
↑ Marsaglia . ] DIEHARD: joukko satunnaisuustestejä (downlink) . Tilastolaitos (1996). Arkistoitu alkuperäisestä 20. tammikuuta 2016. (määrätön)
↑ M. Mascagni ja A. Srinivasan. Algoritmi 806: SPRNG: Skaalautuva kirjasto näennäissatunnaisten lukujen luomiseen // ACM Transactions on Mathematical Software. - 2000. - 1. joulukuuta ( nide 26 , nro 4 ). — S. 436–461 .
↑ CSRC - NIST SP 800-22: Dokumentaatio ja ohjelmistot . csrc.nist.gov. Haettu 24. syyskuuta 2017. Arkistoitu alkuperäisestä 25. syyskuuta 2017. (määrätön)
↑ 1 2 3 4 TestU01 tulokset - BitBabbler . www.bitbubbler.org Haettu 26. syyskuuta 2017. Arkistoitu alkuperäisestä 6. lokakuuta 2017.