Статистически тестове на случайни генератори

Diehard

Тестовете са разработени от George Marsaglia през 80-те години на миналия век. През 1995 г. той публикува CD-ROM, съдържащ файлове със случайни числа, компилирани изпълними файлове съставляващи самите Diehard тестове, както и файлове с документация и указания за използване [3]. Общо батерията се състои от 18 статистически теста. Макар и леко поостарели, тези алгоритми са се превърнали в класика и са вдъхновили множество усъвършенствания.

Поради липсата на изходен сорс код, сме използвали C# обвивка на оригиналните изпълними файлове (компилирани на FORTRAN за MS-DOS), които се извикват от .NET конзолно приложение. За всяко стартиране на батерията, първоначално се генерират 80,000,000 случайни бита (10,000,000 байта) под формата на бинарен файл, който се подава като аргумент към оригиналните .exe файлове. Върху получените 234 p-стойности се прилагат Chi-Square и Kolmogorov-Smirnov тестове за равномерност и на базата на тяхната оценка се прави окончателен извод за изхода от теста. Във всички свои тестове Diehard използва ниво на съгласие α = 0.01. GTR-01 минава успешно всички тестове! Времето за изпълнение на цялата батерия е около 15 s на персонален компютър с Windows 10, Intel Pentium CPU G4600@3.60GHz, 8GB RAM (DDR4 2400MHz).

Важно е да отбележим, че Diehard използва приближени апроксимации на статистическите разпределения в алгоритмите си. При последователното прилагане на батерията към множество отделни бинарни файлове (примерно 50, 100 или повече) и оценка на получените p-стойности в съвкупност, се наблюдава силно отклонение от равномерното разпределение. Ето защо, тестовете са подходящи само за единична оценка така, както са били предложени оригинално от самия автор.

TestU01

Тестовете са разработени от Pierre L’Ecuyer и са представени през 2007 г. [1][2]. Разпределени са в няколко статистически батерии: SmallCrush (10 теста), Crush (96 теста) и BigCrush (106 теста). В добавка, тестовете включват и PseudoDIEHARD (съдържаща повечето от оригиналните тестове на Diehard), Alphabit (специално разработена за проверка на хардуерни случайни генератори), Rabbit, както и FIPS-140-2 (разработена по стандарт на NIST). Важен факт е, че тестовете използват ниво на съгласие α = 0.001. TestU01 е написана на ANSI C за UNIX операцианни системи и затова сорс кода беше преработен за MS Windows и компилиран с Visual C++ Express Edition 2008. Първоначално е генериран бинарен файл с 8,000,000,000 случайни бита (1,000,000,000 байта) и последователно са стартирани SmallCrush, PseudoDIEHARD, FIPS-140-2, Rabbit и Alphabit. Общото време за изпълнение е около 40 мин. Описаната процедура се повтаря многократно, като GTR-01 преминава успешно всички тестове! Фигурата по-долу показва резултат от PseudoDIEHARD.

Отделно от горните батерии, Crush е запусната самостоятелно, като отново се засича общото време за изпълнение на всичките 96 теста. За разлика от предишния случай, където се генерира един и същи бинарен файл, който се използва последователно при отделните батерии, то тук, за всеки тест от Crush, програмата автоматично генерира нова последователност от случайни битове. В резултат, времето за изпълнение нараства многократно. Едно запускане на батерията отнема приблизително 8 денонощия! Като краен резултат, можем да направим следното заключение:

GTR-01 преминава успешно всички тестове на TestU01 Crush battery!

Следващите фигури показват резултатите за някои от тестовете в Crush.

NIST статистически тестове

Тестовете са публикувани от National Institute of Standards and Technology [6]. Към момента, батерията включва 15 статистически теста. Кодът е свободен, което позволява някои малки модификации и експериментиране с тестовете. Алгоритмите се използват практически като стандарт за проверка надеждността на всички съвременни генератори на случайни числа, било то псевдослучайни генератори или хардуерни такива. Оригиналният сорс код (написан на C) за цялата статистическа батерия беше пренаписан на C# за .NET и тестван, за да се осигури пълно съответствие между двата варианта. Въз основа на този код, сме конструирали обща процедура, включваща всички тестове, като някои са в различни разновидности, в зависимост от входните им аргументи. Процедурата приема 1, 10, 100 или 1000 броя двоични последователности от случайни битове, като дължината им може да варира от 1,000,000 до 10,000,000 бита. Включени са следните тестове:

1. Frequency Monobit.
2. Frequency Block (n/80).
3. Runs.
4. Longest Run of Ones.
5. Binary Matrix Rank (7x7).
6. Binary Matrix Rank (8x8).
7. Binary Matrix Rank (15x15).
8. Binary Matrix Rank (16x16).
9. Binary Matrix Rank (31x31).
10. Binary Matrix Rank (32x32).
11. Binary Matrix Rank (63x63).
12. Binary Matrix Rank (64x64).
13. Discrete Fourier Transform (Spectral).
14. Non-overlapping Template Matching (9).
15. Overlapping Template Matching (9)
16. Universal
17. Linear Complexity (1000).
18. Serial (2).
19. Serial (8).
20. Serial (14).
21. Approximate Entropy (2).
22. Approximate Entropy (8).
23. Approximate Entropy (14).
24. Cumulative Sums (forward).
25. Cumulative Sums (backward).
26. Random Excursions.
27. Random Excursions Variant.

Non-overlapping Template Matching съдържа 148 независими теста, Serial – 2, Random Excursions – 8 и Random Excursions Variant – 18. Общо тестовете са 201. Random Excursions и Random Excursions Variant правят вътрешна проверка за приложимост, която ако не е изпълнена, алгоритъмът връща нулеви стойности и резултатите от тези тестове се игнорират. Ако това се случи, общия брой тестове става 175. Оценката за успешност на даден тест се получава след проверка на p-стойността спрямо приетото ниво на съгласие α. Ако p-стойноста ≥ α теста се смята за сполучлив. Тестовете се провеждат за α = 0.001, 0.005, 0.01, 0.05, 0.1. Всички 201 теста се разглеждат като статистически независими [6].

Последния факт ни дава право да конструираме обща оценка за успешността на цялата тестова процедура в съвкупност. Разглеждаме всеки тест от батерията като независим случаен опит на Бернули (Bernoulli trial) с два възможни изхода: успех с вероятност p = 1 – α и неуспех с вероятност α [9]. При провеждане на n на брой независими опита (теста), броят успешни изхода е случайна величина с биномно разпределение (Binomial distribution), От функцията на разпределение (Cumulative distribution function, CDF) пресмятаме кумулативната вероятност за даден интервал от брой успешни опита, всеки с вероятност за успех p от общо n направени опита [9]. Така определяме минималния брой C сполучливи опита, необходим, за да считаме тестовата процедура за успешна. Използваме следното уравнение:

P{X ≤ C | n, p} = ∑_{k = 0}^⌊C⌋(_kⁿ)p^k(1 - p)^{n - k} = α

Примерно, нека n = 201, α = 0.01, p = 0.99, откъдето получаваме C = 194 т.е. ако броя сполучливи теста е равен или по-голям от 195, приемаме цялата процедура за успешна, при даденото ниво на съгласие α. Ако изключим резултатите от Random Excursions и Random Excursions Variant, тогава n = 175 и C = 169. Подобен подход е описан в [8].

Когато тестваните случайни последователности са повече от една, т.е. 10, 100 или 1000, се прави и допълнителна оценка за равномерността в разпределението на p-стойностите. Използвани са три независими теста.

• Proportion. Пресмятане по горната формула на обща оценка за цялата съвкупност от тествани битови последователности при n = 10, 100 или 1000 и ниво на съгласие α. Общата оценка от направените 201 теста се разглежда отново като независим опит на Бернули с p и α и по същия начин се определя числото C за различните стйности на n.
• Chi-Squire. При тази оценка използваме горните стойности за α, за разлика от предложеното в [6] ниво на съгласие 0.0001.
• Kolmogorov-Smirnov. При пресмятането на статистиката е използвана процедурата описана в [7], която е подобрен вариант на алгоритъма показан в [4].

Проведени са множество повторения на тестовете за бинарни последователности с различни дължини и за серии от по 10, 100 и 1000 броя последователности. Можем да направим следното заключение:

GTR-01 преминава успешно всички тестови процедури в NIST STS!

Следващата фигура показва типичен резултат от проведен тест на генератора.

NIST STS е вградена в StudioGTR – специално разработен .NET софтуер с графичен интерфейс за работа с GTR-01. Програмата позволява използването на тестовете с различни стойности за нивото на съгласие α. Повече информация можете да намерите на страницата с описание на StudioGTR.

Важно е да отбележим следното. Разглеждайки работата на генераторите за случайни числа, не трябва да забравяме, че работим със случайни събития, които се описват в термините на вероятностни разпределения и нищо не е абсолютно точно. Така например, понякога, може да се случва резултатът от изпитването, за всички тестове в дадена батерия, да е сполучлив на сто процента. Чудесно! Понякога може някоя от p-стойностите да е по-малка от зададеното ниво на съгласие и теста формално да е неуспешен. В света на вероятностните събития това е съвсем нормално. Но трябва да внимаваме. Ако стопроцентовият успешен резултат се повтаря постоянно, а вероятността за това при наистина добър случаен генератор е нищожна, би било ясна индикация за проблем в методологията или в самите тестове. Важно е да помним, че работим със случайни величини. При всички случаи, достоверна оценка за качеството на даден генератор може да бъде получена само след провеждането на множество тествания и внимателно анализиране на резултатите.

Заключение

Описаните процедури и статистически тестове ясно демонстрират превъзходното качество на генерираните бинарни данни от GTR-01. Нещо повече, разработената от нас методология с вградена софтуерна поддръжка, позволява бързото и лесно калибриране и тестване на всяка една бройка от устройството. Това може да се прави не само в етапа на производство, а и периодически, в процеса на реалната работа на генератора, с цел гарантиране качеството на получаваните данни.

Литература

1. L’Ecuyer P., Simard R. TestU01: A C library for empirical testing of RNGs, ACM Transactions on Mathematical Software, Vol. 33, No. 4, Article 22, 2007.
2. L’Ecuyer P., Simard R. TestU01: A software library in ANSI C for empirical testing of random number generators, User’s guide, 2013.
3. Marsaglia G. The Marsaglia random number CDROM, with the Diehard battery of tests of randomness, 1995.
4. Marsaglia G., Tsang W., Wang J. Evaluating Kolmogorov's distribution, Journal of Statistical Software, 8(18), pp. 1-4, 2003.
5. Marton K., Sucio A. Towards a methodology for randomness assessment: challenges and pitfalls, Proceedings of the Romanian Academy, Series A, Vol. 16, pp. 385-394, 2015.
6. Rukhin et al. A statistical test suite for random and pseudorandom number generators for cryptographic applications, National Institute of Standards and Technology, SP 800-22 Rev. 1a, 2010.
7. Simard R., L’Ecuyer P. Computing the two-sided Kolmogorov-Smirnov distribution, Journal of Statistical Software, Vol. 39, Issue 11, 2011.
8. Sys et al. On the interpretation of results from the NIST statistical test suite, Romanian Jurnal of Information, Science and Technology, Vol. 18, pp. 18-32, 2015.
9. Димитров Б., Янев Н. Вероятности и статистика, Софтех, II изд., 2007.