TestU01

TestU01 — это пакет статистических эмпирических тестов, реализованный на языке ANSI C, который предлагает набор утилит для тестирования генераторов случайных чисел. Последняя версия библиотеки была представлена в 2007 году Пьером Л`Экуйе и Ричардом Симардом из Монреальского университета.

Пакет содержит в себе несколько типов ГПСЧ, включая некоторые предложенные в литературе и некоторые широко используемые в программном обеспечении. Он дает общие реализации классических статистических тестов для генераторов случайных чисел, а также для предложенных в литературе и некоторых оригинальных. Эти тесты могут быть применены к генераторам, которые уже имеются в библиотеке, пользовательским генераторам и потокам случайных чисел. Специальные тесты проверяют любые последовательности равномерно распределенных случайных чисел в $[0,1]$ или битовые последовательности. Основные инструменты для построения векторов точек, вырабатываемых генераторами, тоже присутствуют.

История

TestU01 впервые был реализован в 1985 году на языке Pascal и содержал тесты, предложенные Дональдом Кнутом во втором издании второго тома Искусства программирования. Четыре года спустя был повторно реализован на языке Modula-2 в виде пакета с модульным дизайном. Тогда вместе с новыми тестами были добавлены некоторые наиболее часто используемые ГПСЧ. В период с 1990 по 2001 годы пакет периодически пополнялся новыми генераторами и тестами, а руководство пользователя своевременно обновлялось (на французском). $f$ модули, содержащие инструменты для тестирования семейств генераторов, впервые были представлены в 1997 году. В 2002 году Пьер Л`Экуйе и Ричард Симард переработали библиотеку, реализовали её на языке C и перевели руководство на английский язык.

Критерий качества ГПСЧ

ГПСЧ в основном предназначены для хорошей имитации последовательности независимых случайных величин, обычно в действительном интервале $(0,1)$ или в двоичном наборе $[0,1]$. В первом случае гипотеза $\mathrm {H}$₀^A гласит, что числа $u$₀, $u$₁, $u$₂, $u$₃... – независимые величины из равномерного распределения в интервале $(0,1)$. Во втором, $\mathrm {H}$₀^B гласит, что имеется последовательность независимых случайных бит, каждый из которых принимает значение $0$ или $1$ с равной вероятностью.

$\mathrm {H}$₀^A эквивалентно высказыванию, что для любого целого $t$ вектор ($u$₀, ..., $u$_$t-1$) равномерно распределён в $t$-мерном кубе $(0,1)$^$t$. Для алгоритмических ГПСЧ утверждение является неверным, т.к. векторы в них берут свои значения из конечного числа $\Psi$_$t$ всех $t$-мерных векторов, которые способен выдать генератор.

Для последовательности бит гипотеза $\mathrm {H}$₀^B тоже не может формально называться истинной в случае, когда длина $t$ последовательности превышает количество $b$ бит состояний генератора, потому что количество производимых возможных последовательностей не может превышать $2$^$b$. Задача генератора состоит в том, чтобы убедиться в равномерном распределении последовательностей в поле всех возможных последовательностей в $2$^$t$.

Другой критерий качества для ГПСЧ используется в криптологии и в азартных игровых автоматах. Здесь, вдобавок ко всему вышеперечисленному, отдельное внимание уделяется непредсказуемости последующих чисел.

Особенности

TestU01 предлагает четыре группы модулей для работы с генераторами:

1. реализация заранее запрограммированного генератора (модуль $u$);
2. реализация специальных статистических тестов (модуль $s$);
3. реализация батарей статистических тестов (модуль $b$);
4. применение тестов на целых семействах генераторов (модуль $f$).

Когда конкретный тест применяется на выходных данных генератора размера $n$ , p-значение теста обычно остается разумным до тех пор, пока размер данных не достигнет определенного значения $n_{0}$. После этого p-значение расходится к $0$ или $1$ с экспоненциальной скоростью. Модуль $f$ позволяет исследователю изучить связь между специальным тестом и структурой множества точек, полученных с помощью определенного семейства генераторов. Эта техника может быть использована для определения размера проверяемых данных в зависимости от длины периода генератора до того, как генератор не начнет систематически проваливать тесты.

TestU01 предлагает несколько батарей тестов, таких как SmallCrush (состоит из 10 тестов), Crush (96 тестов) и BigCrush (106 тестов). На компьютере на базе процессора Pentium 4 и с операционной системой Linux для простого генератора время работы батареи тестов SmallCrush занимает несколько минут, Crush — порядка часа, BigCrush — порядка десятка часов.

Другие программы для тестирования ГПСЧ

Одним из широко распространённых пакетов тестов ГПСЧ является DIEHARD, содержащий большое число статистических тестов, но имеющий ряд недостатков и ограничений. Во-первых, последовательность тестов, а также их параметры (такие как размер образца и др.) фиксированы, что плохо сказывается на скорости тестирования. Во-вторых, DIEHARD требует на вход данные в виде целых чисел размером 32 бита, записанных в двоичном файле, когда как многие генераторы выдают числа размером меньше, чем 32 бита. По сравнению с TestU01, пакет DIEHARD менее гибок в этих аспектах.

Ещё один общедоступный пакет тестов – это библиотека SPRNG, включающая в себя классические тесты, описанные в "Искусстве Программирования". Также, Национальный институт стандартов и технологий разработал свой пакет из 15 тестов для тестирования генераторов, используемых в криптографии.

Батареи

Батарея Alphabit создавалась для тестирования аппаратных генераторов случайных чисел. Проводит девять последовательных тестов, перед каждым переписывая входные данные.

Rabbit – батарея, больше сфокусированная на тестировании двоичных данных, но некоторые тесты проходят с фиксированными параметрами, какого бы размера ни были входные данные. Поэтому данные, размер которых превышает 64 мегабайта, приводит к ошибке в одном из тестов и приводит к переполнению оперативной памяти.

SmallCrush, маленькая и быстрая батарея тестов, считывает генератор как файл, содержащий числа с плавающей точкой в пределах $[0,1)$. Ограничение на файл чуть менее 51320000 случайных чисел. Файл будет переписан в начале каждого теста. Некоторые тесты требуют чтобы генератор возвращал как минимум 30 бит решения, в противном случае генератор с большой вероятностью провалит их. Обычно используется для проверки целесообразности проведения тестов на более строгих батареях.

Crush – Батарея из строгих статистических тестов. Включает в себя как классические тесты Кнута, так и множество других. Некоторые из этих тестов предполагают, что генератор возвращает как минимум 30 бит решения, в противном случае тесты будут считаться проваленными. Один из тестов требует 31 бит данных. Батарея использует примерно 2³⁵ случайных чисел.

BigCrush – батарея самых строгих статистических тестов. Так же как и в остальных батареях, некоторые тесты требуют как минимум 30 бит входных данных, иначе тесты будут провалены. Так же один из тестов требует 31 бит данных. Батарея использует почти 2³⁸ случайных чисел. Когда BigCrush впервые появился, даже считавшиеся хорошими ГПСЧ с трудом его проходили.

Тесты батареи SmallCrush

Вот некоторые примеры тестов батареи SmallCrush.

BirthdaySpasings	Тест, основанный на парадоксе дней рождения. Выбираются случайные точки на большом интервале, расстояния между которыми должны быть асимптотически распределены по Пуассону.
Gap	Тест, использующийся для определения интервала между повторениями одной и той же цифры.
CouponCollector	Пусть $\xi _{1},\xi _{2},\dots ,\xi _{n}$ последовательность длины n и размерности m. Исследуются последовательности определенной длины, которые содержат m-разрядное число.
MatrixRank	Тест выбирает определённое количество бит из некоторого количества случайных чисел чтобы сформировать матрицу над {0,1}. Затем определяется ранг матрицы.

Литература

• Pierre L’Ecuyer, Richard Simard. TestU01: A C Library for Empirical Testing of Random Number Generators. — D´epartement d’Informatique et de Recherche Op´erationnelleUniversit´e de Montr´eal: ACM Transactions on Mathematical Software, 2007. — 40 с.
• Knuth D.E. The Art of Computer Programming volume 2, — ISBN 0-201-89684-2.

Ссылки

• The TestU01 Site.  (неопр.)
• TestU01. A Software Library in ANSI C for Empirical Testing of Random Number Generators.  (неопр.)