Тест на случайность
Тест на случайность (или тест на случайность ) при оценке данных — это тест, используемый для анализа распределения набора данных, чтобы увидеть, можно ли его описать как случайный (без шаблона). В стохастическом моделировании , как и в некоторых компьютерных симуляциях , ожидаемая случайность потенциальных входных данных может быть проверена с помощью формального теста на случайность, чтобы показать, что данные действительны для использования в запусках моделирования. В некоторых случаях данные обнаруживают очевидную неслучайную закономерность, как в случае с так называемыми «прогонами данных» (например, ожидание случайных чисел 0–9, но обнаружение «4 3 2 1 0 4 3 2 1...» и редко выше 4). Если выбранный набор данных не проходит тесты, параметры можно изменить или использовать другие рандомизированные данные, которые не проходят тесты на случайность.
Фон
[ редактировать ]Проблема случайности является важным философским и теоретическим вопросом. Тесты на случайность можно использовать, чтобы определить, имеет ли набор данных узнаваемый шаблон, который будет указывать на то, что процесс, который его сгенерировал, в значительной степени неслучайен. По большей части статистический анализ на практике гораздо больше занимается поиском закономерностей в данных, а не проверкой случайности. Многие используемые сегодня «генераторы случайных чисел» определяются алгоритмами и на самом деле являются псевдослучайных генераторами чисел. Последовательности, которые они создают, называются псевдослучайными последовательностями. Эти генераторы не всегда генерируют достаточно случайные последовательности, а вместо этого могут создавать последовательности, содержащие шаблоны. Например, печально известная процедура RANDU резко проваливает многие тесты на случайность, включая спектральный тест .
Стивен Вольфрам использовал тесты на случайность результатов Правила 30, чтобы изучить его потенциал для генерации случайных чисел. [1] хотя было показано, что эффективный размер ключа намного меньше его фактического размера. [2] и плохо выполнить тест хи-квадрат . [3] Использование непродуманного генератора случайных чисел может поставить под сомнение достоверность эксперимента, нарушив статистические предположения. Хотя существуют широко используемые методы статистического тестирования, такие как стандарты NIST, Юнге Ван показал, что стандартов NIST недостаточно. Кроме того, Юнге Ван [4] разработал методы тестирования, основанные на статистическом расстоянии и законе повторного логарифма. Используя эту технику, Юнге Ван и Тони Никол [5] обнаружил слабость в широко используемых генераторах псевдослучайных чисел, таких как хорошо известная версия генератора псевдослучайных чисел OpenSSL для Debian, которая была исправлена в 2008 году.
Специальные тесты на случайность
[ редактировать ]На практике использовалось довольно небольшое количество различных типов генераторов (псевдо)случайных чисел. Их можно найти в списке генераторов случайных чисел , и они включают в себя:
- Линейный конгруэнтный генератор и сдвиговый регистр с линейной обратной связью
- Обобщенный генератор Фибоначчи
- Криптографические генераторы
- Квадратичный конгруэнтный генератор
- Клеточные автоматы-генераторы
- Псевдослучайная двоичная последовательность
Эти разные генераторы имеют разную степень успеха при прохождении принятых наборов тестов. Некоторые широко используемые генераторы более или менее плохо выдерживают испытания, в то время как другие «лучшие» и предшествующие генераторы (в том смысле, что они прошли все существующие батареи тестов и они уже существовали) в значительной степени игнорировались.
Существует множество практических мер случайности двоичной последовательности . К ним относятся меры, основанные на статистических тестах , преобразованиях и сложности или их сочетании. Хорошо известным и широко используемым набором тестов была «Батарея тестов Дихарда» , представленная Марсальей; расширили его до пакета TestU01 L'Ecuyer и Simard . Использование преобразования Адамара для измерения случайности было предложено С. Как и развито далее Филлипсом, Юэнем, Хопкинсом, Бет и Даем, Мундом, Марсальей и Заманом. [6]
Некоторые из этих тестов, имеющих линейную сложность, обеспечивают спектральные меры случайности. Т. Бет и ЗД. Дай намеревался показать, что колмогоровская сложность и линейная сложность практически одинаковы. [7] хотя Ю. Ван позже показал, что их утверждения неверны. [8] Тем не менее, Ван также продемонстрировал, что для случайных последовательностей Мартина-Лёфа колмогоровская сложность по существу такая же, как и линейная сложность.
Эти практические тесты позволяют сравнить случайность строк . По вероятностным соображениям все строки заданной длины имеют одинаковую случайность. Однако разные струны имеют разную колмогоровскую сложность. Например, рассмотрим следующие две строки.
- Строка 1:
0101010101010101010101010101010101010101010101010101010101010101 - Строка 2:
1100100001100001110111101110110011111010010000100101011110010110
Строка 1 допускает краткое лингвистическое описание: «32 повторения «01»». Это описание состоит из 22 символов и может быть эффективно составлено из некоторых базовых последовательностей. [ нужны разъяснения ] Строка 2 не имеет очевидного простого описания, кроме записи самой строки, состоящей из 64 символов. [ нужны разъяснения ] и у него нет сравнительно эффективного представления базисной функции . Используя линейные спектральные тесты Адамара (см. Преобразование Адамара ), первая из этих последовательностей окажется гораздо менее случайной, чем вторая, что согласуется с интуицией.
Известные реализации программного обеспечения
[ редактировать ]См. также
[ редактировать ]Примечания
[ редактировать ]- ^ Вольфрам, Стивен (2002). Новый вид науки . Wolfram Media, Inc., стр. 975–976 . ISBN 978-1-57955-008-0 .
- ^ Вилли Мейер; Отмар Стаффельбах (1991). «Анализ псевдослучайных последовательностей, генерируемых клеточными автоматами». Достижения в криптологии — EUROCRYPT '91 . Конспекты лекций по информатике. Том. 547. стр. 186–199. дои : 10.1007/3-540-46416-6_17 . ISBN 978-3-540-54620-7 .
- ^ Моше Сиппер; Марко Томассини (1996), «Генерация параллельных генераторов случайных чисел с помощью клеточного программирования», Международный журнал современной физики C , 7 (2): 181–190, Бибкод : 1996IJMPC...7..181S , CiteSeerX 10.1.1.21.870 , дои : 10.1142/S012918319600017X .
- ^ Юнге Ван. О разработке тестов LIL для (псевдо)случайных генераторов и некоторых экспериментальных результатах, http://webpages.uncc.edu/yonwang/ , 2014 г.
- ^ Юнге Ван; Тони Никол (2014), «Статистические свойства псевдослучайных последовательностей и эксперименты с PHP и Debian OpenSSL», Esorics 2014, LNCS 8712 : 454–471
- ^ Терри Риттер, «Тесты случайности: обзор литературы», веб-страница: Рэнд ЦБ РФ .
- ^ Бет, Т. и ЗД. Дай. 1989. О сложности псевдослучайных последовательностей, или: если вы можете описать последовательность, она не может быть случайной. Достижения в криптологии – EUROCRYPT '89. 533-543. Шпрингер-Верлаг
- ^ Юнге Ван 1999. Линейная сложность против псевдослучайности: о результате Бет и Дая. В: Учеб. Asiacrypt 99, страницы 288–298. LNCS 1716, Шпрингер Верлаг
- ^ ЛОР: Программа тестирования псевдослучайной числовой последовательности , Fourmilab, 2008.
- ^ Набор статистических тестов для генераторов случайных и псевдослучайных чисел для криптографических приложений , специальная публикация 800-22, редакция 1a, Национальный институт стандартов и технологий , 2010.
- ^ Внедрение набора статистических тестов NIST.
Внешние ссылки
[ редактировать ]- Тесты на случайность, включенные в набор криптографических инструментов NIST.
- Джордж Марсалья , Вай Ван Цанг (2002), « Некоторые труднопроходимые тесты случайности », Журнал статистического программного обеспечения , том 7, выпуск 3
- DieHarder: набор тестов для случайных чисел , Роберт Г. Браун, Университет Дьюка
- Онлайн-анализ генератора случайных чисел от CAcert.org