Пакеты статистических тестов и тестируемые характеристики

Для выявления закономерностей к анализируемым ПСП (а также к их отрезкам различной длины) применяется широкий спектр различных статистических тестов. В последние десятилетия разработано большое количество тестов для анализа ПСП. В табл. 10.1 даны наиболее известные пакеты статистических тестов со ссылками на программные реализации.

Таблица 10.1

Основные пакеты статистических тестов.

Тесты Кнута. Впервые набор статистических тестов ПСП был предложен в [3]. Тесты разработаны для последовательностей целых чисел, применение к бинарным последовательностям требует определенной адаптации. В комплект входит 11 тестов: критерий частот, критерий серий, критерий интервалов, покер-критерий, критерий собирания купонов, критерий перестановок, критерий монотонности, критерий конфликтов, критерий промежутков между днями рождений, критерий «максимум-^», критерий сериальной корреляции. Появившиеся впоследствии пакеты статистических тестов развивают предложенные Д. Кнутом методы тестирования ПСП.

Статистические тесты NIST. Разработаны Лабораторией информационных технологий, главной исследовательской организацией Национального института стандартов и технологий (NIST), и ориентированы на проверку случайности двоичных последовательностей. Пакет NIST STS является наиболее полным из имеющихся пакетов для статистического тестирования двоичных последовательностей. В табл. 10.2 приведены статистические тесты NIST и выявляемые дефекты (отклонения от значений аналогичных характеристик ИСП).

Недостатки пакета: некоторые параметры тестов фиксированы, что при изменении (в частности, при уменьшении) длины последовательности не позволяет применять ряд тестов.

Анализ пакета тестов NIST.

Таблица 10.2

DIEHARD — предложенный Джорджем Марсальей набор тестов, применяется к последовательностям 32-битных чисел, применение их для двоичных последовательностей требует преобразования. В состав входят 12 тестов, в частности:

• 1) проверка промежутков между днями рождения (The Birthday Spacing Test);
• 2) проверка пересекающихся перестановок (The Overlapping k-permutation Test);
• 3) проверка рангов матриц (The Binary Rank Test);
• 4) буквенные тесты (Monkey Tests);
• 5) подсчет единиц в потоке байт (The Count-the-Ts Test On A Stream Of Byte).

Недостатки пакета: многие тесты математически не описаны, параметры всех тестов фиксированы, что препятствует варьированию параметров и добавлению новых тестов.

TestUOl — пакет состоит из двух частей: для последовательностей действительных чисел из интервала (0, 1) и для двоичных последовательностей. Одна из задач пакета — устранить недостатки пакета DIEHARD. Последовательности битов проверяют на случайность тестами:

• 1) тест на линейную сложность (Linear Complexity Test);
• 2) тест сложности на базе алгоритма Лемнеля — Зива (Lempel — Ziv Complexity);
• 3) тест коэффициентов Фурье (Fourier Coefficients);
• 4) тест автокорреляции (Autocorrelations);
• 5) тест серий и разрывов (Run and Gap Test);
• 6) тест на периодичность (Serial Test);
• 7) CAT тест (CAT Test);
• 8) тест рангов бинарных матриц (Rank of a Binary Matrix);
• 9) тест на самую длинную последовательность единиц в блоке (Longest Run of l’s);
• 10) тест веса Хэмминга (Hamming Weight);
• 11) тест случайных проходов (Random Walk Test).

Недостатки пакета: неподробпое и нечеткое описание алгоритмов.

CRYPT-X — коммерческий набор из пяти статистических тестов, разработанный в Технологическом университете Квинсленда, его исходный код недоступен. В него входят:

• 1) тест частот (Frequency Test);
• 2) тест бинарной производной (Binary Derivative Test);
• 3) тест на последовательность одинаковых бит (Runs Test);
• 4) тест на линейную сложность (Linear Complexity Test);
• 5) тест сложности последовательности (Complexity Test).

Недостатки пакета: закрытость кода; отсутствие методической документации.