Тест Diehard

Тест Diehard — это набор статистических тестов для оценки качества генераторов псевдослучайных чисел (ГПСЧ), разработанный американским математиком и статистиком Джорджем Марсальей (George Marsaglia) в 1995 году. Набор включает 18 тестов, предназначенных для выявления статистических аномалий в последовательностях чисел, которые могут указывать на недостаточную случайность генератора. Тест Diehard считается одним из наиболее известных и широко используемых пакетов для проверки ГПСЧ, хотя в настоящее время существуют более современные и всеобъемлющие наборы, такие как TestU01 и NIST SP 800-22.

История

Джордж Марсалья, профессор статистики Университета штата Флорида, был одним из ведущих специалистов в области генерации случайных чисел и статистического тестирования. В 1995 году он опубликовал набор тестов Diehard, который быстро стал стандартом де-факто для проверки ГПСЧ. Название «Diehard» (с англ. — «упрямый», «неумирающий») отражает настойчивость, с которой тесты выявляют даже слабые статистические дефекты, а также отсылает к знаменитому генератору случайных чисел RANDU, который был признан неудовлетворительным после прохождения тестов Diehard.

Марсалья разработал тесты в ответ на растущую потребность в надежных методах оценки случайности, особенно в криптографии, научных симуляциях и статистическом моделировании. Набор был впервые распространен в виде исходного кода на языке C и сопровождался документацией, описывающей каждый тест и интерпретацию результатов.

Состав и принципы работы

Набор Diehard состоит из 18 отдельных тестов, каждый из которых проверяет определенное свойство случайности. Тесты основаны на различных статистических критериях, таких как критерий согласия Пирсона (хи-квадрат), критерий Колмогорова-Смирнова, критерий серий и другие. Каждый тест вычисляет P-значение (probability value) — вероятность того, что наблюдаемое отклонение от ожидаемого случайного поведения может быть получено случайно, если генератор действительно является случайным.

Ключевые тесты

1. Birthday Spacings (Дни рождения) — проверяет распределение интервалов между повторяющимися значениями в последовательности, имитируя «парадокс дней рождения».
2. Overlapping Permutations (Перекрывающиеся перестановки) — анализирует частоту появления различных перестановок в последовательности.
3. Ranks of Matrices (Ранги матриц) — проверяет распределение рангов бинарных матриц, сформированных из последовательности.
4. Monkey Tests (Обезьяньи тесты) — серия тестов, моделирующих печатание случайных символов на клавиатуре и проверяющих, насколько часто встречаются определенные слова или последовательности.
5. Count the 1s (Подсчет единиц) — проверяет распределение количества единиц в битовых строках.
6. Parking Lot Test (Тест парковки) — моделирует случайное размещение точек в квадрате и проверяет, насколько хорошо они заполняют пространство.
7. Minimum Distance (Минимальное расстояние) — проверяет распределение минимальных расстояний между случайными точками в кубе.
8. Random Spheres Test (Тест случайных сфер) — проверяет распределение радиусов сфер, центры которых расположены случайным образом.
9. Squeeze Test (Тест сжатия) — проверяет, как быстро генератор может произвести последовательность, удовлетворяющую определенному условию.
10. Overlapping Sums (Перекрывающиеся суммы) — проверяет распределение сумм последовательных чисел.
11. Runs Test (Тест серий) — проверяет длину и количество серий (последовательностей возрастающих или убывающих значений).
12. Craps Test (Тест игры в кости) — моделирует игру в кости и проверяет, насколько часто выпадают определенные комбинации.

Интерпретация результатов

Результаты каждого теста представляются в виде P-значения. Если P-значение находится в диапазоне от 0.01 до 0.99, тест считается пройденным. Значения, выходящие за эти пределы, указывают на потенциальные проблемы с генератором. Однако Марсалья предупреждал, что единичное отклонение может быть случайным, и для надежности следует проводить несколько прогонов тестов.

Применение

Тест Diehard используется в следующих областях:

• Криптография — для проверки генераторов случайных чисел, используемых в шифровании, цифровых подписях и генерации ключей.
• Научные симуляции — в физике, биологии, экономике и других науках, где требуется моделирование случайных процессов.
• Статистическое моделирование — для проверки качества ГПСЧ, используемых в методах Монте-Карло.
• Разработка программного обеспечения — для тестирования встроенных ГПСЧ в языках программирования (например, rand() в C, Random в Java, numpy.random в Python).
• Анализ случайности — для оценки качества аппаратных генераторов случайных чисел (ГСЧ) и энтропийных источников.

Критика и ограничения

Несмотря на широкую популярность, тест Diehard имеет ряд недостатков:

• Устаревшая архитектура — набор был разработан в 1995 году и не учитывает современные требования к криптографической стойкости. Он не включает тесты на корреляцию, линейную сложность и другие атаки, актуальные для криптографии.
• Ограниченный набор тестов — Diehard проверяет только статистические свойства, но не гарантирует криптографическую стойкость. Генератор может пройти все тесты, но быть уязвимым для атак, основанных на знании внутреннего состояния.
• Зависимость от реализации — результаты тестов могут зависеть от размера входной последовательности и способа ее представления.
• Отсутствие автоматизации — оригинальная версия требует ручной настройки и интерпретации результатов.

Современные альтернативы

В настоящее время существуют более совершенные наборы тестов, которые заменили Diehard в профессиональной среде:

• TestU01 (2007) — разработан Пьером Лекуйе (Pierre L’Ecuyer) и Ричардом Симаром (Richard Simard). Включает более 100 тестов, в том числе криптографические, и поддерживает автоматическое тестирование.
• NIST SP 800-22 (2010) — набор из 15 тестов, разработанный Национальным институтом стандартов и технологий США (NIST) для проверки криптографических ГПСЧ. Является стандартом для федеральных агентств США.
• Dieharder (2008) — расширенная версия Diehard, разработанная Робертом Брауном (Robert Brown) и Дэвидом Бауэром (David Bauer). Включает все тесты Diehard, а также дополнительные тесты из NIST и других источников.

Интересные факты

• Тест Diehard был назван в честь фразы «die hard» (упрямый), а не в честь одноименного фильма, хотя Марсалья признавал, что это совпадение.
• Один из тестов, «Craps Test», моделирует игру в кости и проверяет, насколько часто выпадают определенные комбинации, что делает его наглядным примером применения статистики к реальным задачам.
• Тест Diehard был использован для выявления дефектов в генераторе RANDU, который ранее считался приемлемым, но оказался статистически неудовлетворительным.

Источники

• Marsaglia, G. (1995). The Diehard Battery of Tests of Randomness. Florida State University.
• L’Ecuyer, P., & Simard, R. (2007). TestU01: A C Library for Empirical Testing of Random Number Generators. ACM Transactions on Mathematical Software.
• NIST Special Publication 800-22 (2010). A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications.
• Brown, R., & Bauer, D. (2008). Dieharder: A Random Number Test Suite.