Разве неразумно проводить фазз-тестирование с помощью криптографически слабого генератора псевдослучайных данных?

Question

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

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

Разве по сути неразумно использовать слабый PRNG для нечеткого тестирования? Если это теоретически необоснованно, то разумно ли это на практике?

Answer 1

Вы путаете две очень разные степени «слабости»:

• статистическая слабость означает, что выходные данные ГСЧ демонстрируют статистические закономерности, такие как наличие определенных последовательностей болеечасто, чем другие.На самом деле это может привести к неэффективному фаззингу в некоторых редких случаях.Статистически сильные PRNGs являются эффективными и широко доступными (хотя наиболее заметно Twister Mersenne).
• криптографическая слабость означает, что выход RNG в некотором роде предсказуем, учитывая знание, отличное от семени (такой как сам вывод).Абсолютно бессмысленно требовать, чтобы PRNG, используемый для нечеткого тестирования, был криптографически сильным, потому что «шаблоны», демонстрируемые статистически сильными, но криптографически слабыми PRNG, в значительной степени являются проблемой только в том случае, если вам нужно предотвратить криптографически ориентированного злоумышленникаот прогнозирования выхода.

Answer 2

Не думаю, что это действительно имеет значение, но я не могу доказать это.

Fuzz-тестирование будет пробовать только некоторые входные данные, в большинстве случаев это незначительная доля возможностей. Независимо от того, насколько хорошо вы используете ГСЧ, он может найти или не найти один из входов, который нарушает ваш код, в зависимости от того, какая доля всех возможных входов нарушает ваш код. Если шаблон в PRNG не очень прост, мне кажется маловероятным, что он каким-либо образом будет соответствовать шаблону в «плохих» входах, которые вы ищете, поэтому он попадет в него ни больше, ни меньше, чем истинно случайный.

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

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

Обычно на данном языке не так сложно найти крипто или, по крайней мере, безопасные хеш-библиотеки. SHA-1 везде и прост в использовании для генерации потока, или неудача в том, что RC4 тривиально реализовать самостоятельно. Оба обеспечивают довольно хороший PRNG, хотя и не такой безопасный, как Blum Blum Shub. Я бы подумал, что главное беспокойство - это скорость - если, например, Mersenne Twister может генерировать нечеткие тестовые примеры в 10 раз быстрее, а тестируемый код достаточно быстрый, тогда у него может быть больше шансов найти неверные входные данные в заданном время независимо от того, что с учетом 624 выходов можно вывести полное состояние ГСЧ ...

Answer 3

Вам не нужен непредсказуемый источник (именно это и есть криптографически безопасный генератор), вам нужен только источник с хорошими статистическими свойствами.

Таким образом, достаточно использовать генератор общего назначения - он быстрый и обычно воспроизводимый (что означает, что проблемы также воспроизводимы).