Пакеты статистических тестов и тестируемые характеристики
Статистические тесты NIST. Разработаны Лабораторией информационных технологий, главной исследовательской организацией Национального института стандартов и технологий (NIST), и ориентированы на проверку случайности двоичных последовательностей. Пакет NIST STS является наиболее полным из имеющихся пакетов для статистического тестирования двоичных последовательностей. В табл. 10.2 приведены… Читать ещё >
Пакеты статистических тестов и тестируемые характеристики (реферат, курсовая, диплом, контрольная)
Для выявления закономерностей к анализируемым ПСП (а также к их отрезкам различной длины) применяется широкий спектр различных статистических тестов. В последние десятилетия разработано большое количество тестов для анализа ПСП. В табл. 10.1 даны наиболее известные пакеты статистических тестов со ссылками на программные реализации.
Таблица 10.1
Основные пакеты статистических тестов.
Пакеты статистических тестов. | Число тестов. | Программная реализация. | Создатели. |
The Art Of Computer Programming Vol. 2 Seminumerical Algorithms. | и. | В составе пакета TestUOl. | Donald Knuth / Stanford University. |
NIST Statistical Test Suite. | http://csrc.nist.gov/. groups/ST/toolkit/. rng/documentation_. software.html. | Andrew Rukhin, et. al./NIST ITL. | |
DIEHARD. | http://stat.fsu.edu/. pub/diehard/. | George Marsaglia / Florida State University. | |
TestUOl. | http://www. iro.umontreal. ca/~simardr/ testuOl/tuOl.html. | Pierre L’Ecuyer, Richard Siinard / D’epartement d’Informatique et de Recherche Op’erationnelle University de Montr’eal. | |
Crypt-X. | https:// www.qut. edu.au/institute-for; future-environments. | Helen Gustafson, et. al./ Queensland University of Technology. |
Тесты Кнута. Впервые набор статистических тестов ПСП был предложен в [3]. Тесты разработаны для последовательностей целых чисел, применение к бинарным последовательностям требует определенной адаптации. В комплект входит 11 тестов: критерий частот, критерий серий, критерий интервалов, покер-критерий, критерий собирания купонов, критерий перестановок, критерий монотонности, критерий конфликтов, критерий промежутков между днями рождений, критерий «максимум-^», критерий сериальной корреляции. Появившиеся впоследствии пакеты статистических тестов развивают предложенные Д. Кнутом методы тестирования ПСП.
Статистические тесты NIST. Разработаны Лабораторией информационных технологий, главной исследовательской организацией Национального института стандартов и технологий (NIST), и ориентированы на проверку случайности двоичных последовательностей. Пакет NIST STS является наиболее полным из имеющихся пакетов для статистического тестирования двоичных последовательностей. В табл. 10.2 приведены статистические тесты NIST и выявляемые дефекты (отклонения от значений аналогичных характеристик ИСП).
Недостатки пакета: некоторые параметры тестов фиксированы, что при изменении (в частности, при уменьшении) длины последовательности не позволяет применять ряд тестов.
Анализ пакета тестов NIST.
Таблица 10.2
Статистический тест NIST. | Выявляемый дефект последовательности. |
Частотный побитовый тест, Frequency Test. | Отклонение числа единиц. |
Частотный блочный тест, Frequency Test within a Block. | Локальные отклонения частоты появления единиц в блоке. |
Тест серий, Runs Test. | Отклонение числа серий из единиц (из нулей) различной длины, в частности, частоты чередования 1 и 0. |
Тест на длиннейшую серию единиц в блоке, Test for the Longest Run of Ones in a Block. | Отклонение от теоретического закона распределения максимальных длин серий единиц. |
Тест рангов бинарных матриц, Binary Matrix Rank Test. | Отклонение значений рангов матрицы, анализ линейной зависимости элементов последовательности. |
Спектральный тест на основе дискретного преобразования Фурье, Discrete Fourier Transform (Spectral) Test. | Выявление периодических компонент. |
Тест на совпадение нспсрскрывающихся шаблонов, Non-overlapping Template Matching Test. | Большое количество заданных непериодических шаблонов. |
Тест на совпадение перекрывающихся шаблонов, Overlap-ping Template Matching Test. | Большое количество m-битовых серий единиц. |
Универсальный тест Маурера, Maurer’s «Universal Statistical» Test. | Сжимаемость последовательности без потери информации. |
Тест на линейную сложность, Linear Complexity Test. | Сниженная сложность последовательности. |
Тест на периодичность, Serial Test. | Отклонение числа перекрывающихся т-грамм. |
Тест приблизительной энтропии, Approximate Entropy Test. | Неравномерность распределения m-грамм (регулярность свойств генератора последовательностей). |
Тест кумулятивных сумм, Cumulative Sums (Сиsum) Test. | Отклонение числа единиц в начале или в конце двоичной последовательности. |
Тест произвольных проходов, Random Excursions Test. | Число попаданий в определенное состояние при произвольном обходе кумулятивной суммы. |
Другой тест произвольных проходов, Random Excursions Variant Test. | Число попаданий в различные состояния при произвольном обходе кумулятивной суммы. |
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).
Недостатки пакета: закрытость кода; отсутствие методической документации.