Как выполнить модульное тестирование генератора псевдослучайных чисел?

Question

У меня есть класс генератора псевдослучайных чисел (PRNG), который я хочу протестировать. Есть два подхода:

1. напишите тестовый набор, который будет отбирать большое количество выборок и проверить, правильно ли они распределены. Такой подход может привести к довольно длительному времени выполнения тестового примера;
2. вычислить небольшую серию выборок «вручную» и проверить, воспроизводит ли ее алгоритм PRNG. Этот подход может привести к тому, что неслучайная последовательность будет сгенерирована без замечаний;

Я бы сказал, что первый подход на самом деле не является модульным тестированием, потому что он не выполняет тест белого ящика генератора, но, с другой стороны, он правильно проверяет ответственность класса. Второй подход больше похож на реальный модульный тест, ориентированный на алгоритм, но он не дает столько доказательств того, выполняет ли класс свою ответственность.

Какой подход вы предпочитаете и почему?

---

Answer 1

Получите еще одну реализацию того же алгоритма PRNG, сгенерируйте небольшое количество длинных тестовых случаев на основе известных начальных значений и убедитесь, что ваша реализация алгоритма соответствует всем остальным реализациям. Чем больше данных вы тестируете, тем больше у вас шансов. Если вы хотите быть серьезным, посмотрите, как выполняется проверка FIPS для алгоритма.

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

Если вы изобрели свой собственный алгоритм PRNG, тогда у вас будет совсем другая проблема, потому что помимо тестирования вашего кода вам также необходимо протестировать ваш новый алгоритм. Есть разные вещи - я думаю, что наиболее важными являются статистическое тестирование выходных данных и рецензирование другими криптографами. Однако, в принципе, если бы вы разрабатывали алгоритм PRNG, не обладая достаточными знаниями в этой области, чтобы знать, как его протестировать, то это будет мусор.

Answer 2

Для тестирования PRNG я бы использовал ENT , который представляет собой набор статистических тестов, которые скажут вам, насколько хорошо работает ваш PRNG. Я полагаю, это подход 1.

Answer 3

Я бы предположил, что в конечном итоге вам понадобятся оба теста - потому что вы хотите быть уверены, что оба следующих условия верны:

(1) номера правильно распределены и (2) конкретный алгоритм работает, как и ожидалось.

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

Answer 4

Вот статья CodeProject , которая включает в себя реализацию теста Колмогорова-Смирнова, упомянутого в томе Дональда Кнута 2, Получисленные алгоритмы. Как упомянул InSciTek Jeff выше, есть две проблемы: тестирование алгоритма и тестирование вашей реализации алгоритма. K-S тест, скорее всего, найдет ошибки в реализации, и это хорошее начало для тестирования качества самого алгоритма.

Answer 5

«Случайность» в генераторе псевдослучайных чисел обычно выражается как среднее число итераций, прежде чем число повторяется. Существует множество алгоритмов, которые имеют различную «случайность» и производительность. Random.org имеет хорошее объяснение некоторого анализа, выполненного на их алгоритмах. Посмотрите фотографии примерно на полпути вниз по странице. На статических изображениях легко увидеть, насколько случайны два алгоритма.

Одна особенность PRNG (истинная особенность, а не ошибка, замаскированная под особенность) - это то, что она предсказуема. Для данного семени должна быть произведена та же последовательность чисел. Это чрезвычайно важно и необходимо для тестирования и отладки программ, использующих стохастические (или случайные) методы.

Числовая последовательность должна приближаться к определенному статистическому распределению. Проверьте свой PRNG, сгенерировав большую последовательность (скажем, 10 ^ 6 чисел), и выполните несколько статистических тестов на последовательность, особенно критерий хи-квадрат (если распределение нормальное). Сделайте гистограмму вашего образца и посмотрите, выглядит ли она так, как вы ожидаете.

Если вы контролируете, как задано начальное число, сгенерированная последовательность должна быть одинаковой каждый раз, что подходит для тестирования белого ящика. При выполнении тестов также полезно «прогреть» генератор, запустив его примерно на 100 итераций, прежде чем собирать образец.

Answer 6

Я считаю, что ваша первая точка (# 1) получает больше при тестировании качества генерируемых случайных чисел, что определяется используемым алгоритмом. Второй пункт (# 2) получает больше при тестировании реализации алгоритма. Если вы разработали алгоритм, оба теста важны. Если вы реализовали алгоритм продемонстрированной производительности, # 2 должно быть достаточно. Хотя я, вероятно, протестировал бы больше, чем несколько начальных чисел и последовательности, которые были получены, используя некоторые знания о структуре вашего конкретного генератора.

Answer 7

Вы можете найти некоторые ответы на этот вопрос полезными.

По сути, вы не можете "доказать", что ГСЧ является случайным, но вы можете выполнить различные тесты, чтобы повысить уверенность в том, что это так. Эти тесты различаются по сложности. Diehard является исчерпывающим, но на самом деле он не предлагает ответа «да / нет», больше как пара сотен «майбов». На другом конце спектра довольно просто сгенерировать последовательность значений (не менее 10000), а затем проверить, равны ли среднее значение и стандартное отклонение / дисперсия , как ожидалось .

Answer 8

Plesae, имейте в виду: если вы «изобрели» свой PRNG, вы, вероятно, ошиблись и произвели что-то, что имеет неоптимальное распределение. Основным тестом на случайность вашего генератора является критерий хи-квадрат

Answer 9

Один из методов заключается в том, чтобы направить вывод в PractRand .

Если PractRand говорит, что выход PRNG в порядке, действительно ли PRNG в порядке? Я не квалифицирован, чтобы судить, но я могу сказать, что PRNG достаточно требователен, чтобы он считал неудовлетворительным вывод различных LFSR и алгоритмов xor-and-shift, которые я нашел в литературе или в Интернете, и считал, что вывод OK Ксоргенов Р.П. Брента.

Answer 10

Random.org использует этот тестовый костюм: http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html

Вы можете загрузить программное обеспечение (Unix и Mac OS X) в: http://csrc.nist.gov/groups/ST/toolkit/rng/documents/sts-2.1.1.zip

Документация здесь: http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22rev1a.pdf