TestU01

TestU01 — это библиотека программного обеспечения для статистического тестирования генераторов псевдослучайных чисел (ГПСЧ), разработанная профессором Пьером Л’Экюйе и его коллегами из Университета Монреаля. Библиотека предоставляет набор стандартизированных тестов, позволяющих оценить качество и статистические свойства последовательностей, генерируемых различными алгоритмами. TestU01 считается одним из наиболее авторитетных и всесторонних инструментов для анализа ГПСЧ, наряду с пакетами Diehard, Dieharder и NIST SP 800-22.

История

Разработка TestU01 началась в конце 1990-х годов как продолжение работы Пьера Л’Экюйе над теорией и практикой генерации случайных чисел. Первая версия библиотеки была выпущена в 2002 году. Основной целью создания было преодоление ограничений существовавших на тот момент тестовых пакетов, в частности, пакета Diehard Джорджа Марсальи, который, хотя и был широко распространён, имел ряд недостатков: неполный охват типов статистических тестов, отсутствие единой методологии и проблемы с воспроизводимостью результатов. TestU01 был спроектирован как модульная, расширяемая и хорошо документированная система, позволяющая проводить как отдельные тесты, так и комплексные батареи тестов.

Структура и компоненты

Библиотека TestU01 написана на языке программирования C и включает в себя несколько ключевых компонентов, организованных в виде модулей.

Основные модули

• bbattery — модуль для запуска предопределённых наборов тестов (батарей). Он включает в себя три основные батареи: SmallCrush, Crush и BigCrush, которые различаются по объёму вычислений и строгости.
• swrite — модуль для вывода результатов тестирования в различных форматах.
• unif01 — модуль, предоставляющий интерфейс для подключения различных генераторов. Он включает в себя множество встроенных ГПСЧ, а также позволяет пользователям подключать собственные реализации.
• fdist — модуль, содержащий функции для работы с различными статистическими распределениями.
• gof — модуль для выполнения тестов на согласие (goodness-of-fit).
• scomp — модуль для сравнения нескольких генераторов по заданным критериям.

Батареи тестов

TestU01 предлагает три стандартных набора тестов, которые различаются по строгости и вычислительной сложности:

1. SmallCrush: Быстрая батарея, состоящая из 10 тестов. Она предназначена для быстрой первичной проверки генератора и выявления грубых дефектов. Выполнение занимает несколько секунд.
2. Crush: Более полная батарея, включающая 96 тестов. Она требует больше времени (от нескольких минут до часа) и позволяет выявить многие статистические аномалии.
3. BigCrush: Самая строгая и ресурсоёмкая батарея, состоящая из 106 тестов. Её выполнение может занимать несколько часов. BigCrush считается одним из самых жёстких тестов для ГПСЧ; успешное прохождение BigCrush является сильным свидетельством высокого качества генератора.

Каждый тест в батареях генерирует одно или несколько значений p-value (вероятность получить наблюдаемое или более экстремальное значение статистики при условии, что нулевая гипотеза о случайности верна). Значения p-value, близкие к 0 или 1, указывают на потенциальную проблему с генератором.

Классификация тестов

Тесты в TestU01 можно классифицировать по типу проверяемого статистического свойства.

Тесты на равномерность

Эти тесты проверяют, равномерно ли распределены генерируемые числа в заданном диапазоне. К ним относятся:

• Тест «Колмогорова-Смирнова»: Сравнивает эмпирическую функцию распределения с теоретической.
• Тест «Хи-квадрат»: Проверяет соответствие наблюдаемых частот ожидаемым.

Тесты на независимость

Эти тесты проверяют, отсутствует ли корреляция между последовательными значениями или значениями, разделёнными определённым шагом.

• Тест «Сериальная корреляция»: Измеряет корреляцию между элементами последовательности.
• Тест «Ранги» (Runs test): Проверяет, является ли последовательность знаков (например, «больше/меньше медианы») случайной.
• Тест «Покер» (Poker test): Анализирует частоту появления определённых комбинаций (например, «пять чисел в ряд»).

Тесты на структуру

Эти тесты ищут закономерности в многомерном пространстве.

• Тест «Сжатие» (Compression test): Проверяет, можно ли сжать последовательность, что свидетельствует о наличии закономерностей.
• Тест «Линейная сложность» (Linear complexity test): Оценивает длину кратчайшего регистра сдвига с линейной обратной связью, который может воспроизвести последовательность.
• Тест «Блуждание» (Random walk test): Моделирует случайное блуждание и проверяет, не отклоняется ли его траектория от ожидаемой.

Применение

TestU01 широко используется в следующих областях:

• Криптография: Для проверки криптостойкости генераторов псевдослучайных чисел, используемых в шифровании, протоколах аутентификации и генерации ключей. Генератор, не прошедший BigCrush, считается непригодным для использования в криптографических целях.
• Моделирование и симуляция: В научных и инженерных расчётах, где требуется высококачественная случайность (например, метод Монте-Карло, моделирование физических процессов, финансовое моделирование).
• Разработка и тестирование ГПСЧ: Разработчики новых алгоритмов используют TestU01 для оценки их качества и сравнения с существующими аналогами.
• Анализ существующих генераторов: TestU01 применяется для выявления скрытых дефектов в широко используемых ГПСЧ, таких как генераторы из стандартных библиотек языков программирования (например, rand() в C, java.util.Random).

Примеры результатов

TestU01 позволил выявить статистические недостатки у многих популярных генераторов. Например, генератор rand() из стандартной библиотеки C (часто основанный на линейном конгруэнтном методе) не проходит даже SmallCrush. Генератор Mersenne Twister (MT19937) успешно проходит BigCrush, но имеет другие недостатки, такие как большой размер состояния и медленный запуск. Некоторые современные генераторы, такие как PCG (Permuted Congruential Generator) и ChaCha8, также успешно проходят BigCrush.

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

Несмотря на свою авторитетность, TestU01 не лишён критики. Основные замечания:

• Вычислительная сложность: BigCrush требует значительных вычислительных ресурсов и времени, что может быть проблематично для больших объёмов тестирования.
• Ограниченность набора тестов: Хотя TestU01 включает множество тестов, он не охватывает все возможные типы статистических аномалий. Например, он не тестирует генераторы на устойчивость к атакам по побочным каналам или на предсказуемость при известном внутреннем состоянии.
• Зависимость от реализации: Результаты тестирования могут зависеть от конкретной реализации генератора и платформы.
• Отсутствие тестов на криптостойкость: TestU01 не проверяет генераторы на устойчивость к атакам, направленным на восстановление внутреннего состояния по выходной последовательности. Для этого существуют отдельные тесты (например, из пакета NIST SP 800-22).

См. также

• Генератор псевдослучайных чисел
• Diehard (тест)
• NIST SP 800-22
• Пьер Л’Экюйе

Источники

1. L’Ecuyer, P., & Simard, R. (2007). TestU01: A C library for empirical testing of random number generators. ACM Transactions on Mathematical Software (TOMS), 33(4), 22.
2. L’Ecuyer, P. (2012). Random number generation. In Handbook of Computational Statistics (pp. 35-71). Springer, Berlin, Heidelberg.
3. Официальная документация библиотеки TestU01 (версия 1.2.3).
4. Marsaglia, G. (1995). The Marsaglia random number CDROM including the diehard battery of tests of randomness.