Разве неразумно проводить фазз-тест с помощью криптографически слабого псевдослучайного генератора?
При работе над большим программным проектом я часто использую фазз-тестирование как часть моих тестовых случаев, чтобы помочь выявить ошибки, которые могут появляться только тогда, когда входной сигнал достигает определенного размера или формы. Я делал это чаще всего, просто используя стандартные средства случайных чисел, которые связаны с языком программирования, который я использую.
Недавно я начал задаваться вопросом, игнорируя преимущества или недостатки нечеткого тестирования в целом, является ли хорошей идеей использование не криптографически безопасных генераторов псевдослучайных чисел при выполнении нечеткого тестирования. Генераторы слабых случайных чисел часто демонстрируют шаблоны, которые отличают их от истинных случайных последовательностей, даже если эти шаблоны не являются очевидными. Кажется, что нечеткий тест с использованием слабого PRNG всегда может не вызвать определенные скрытые ошибки, которые обнаруживаются только при определенных обстоятельствах, потому что псевдослучайные числа могут быть связаны друг с другом таким образом, чтобы никогда не вызывать эти обстоятельства.
По сути, неразумно использовать слабый PRNG для нечеткого тестирования? Если это теоретически необоснованно, то разумно ли это на практике?
3 ответа
Вы путаете две очень разные степени "слабости":
- статистическая слабость означает, что выходные данные ГСЧ демонстрируют статистические закономерности, например, когда определенные последовательности встречаются чаще, чем другие. На самом деле это может привести к неэффективному нечеткому тестированию в некоторых редких случаях. Статистически сильные PRNGs эффективны и широко доступны, хотя (наиболее заметно Twister Mersenne).
- Криптографическая слабость означает, что выходные данные ГСЧ в некотором роде предсказуемы, учитывая знание, отличное от начального числа (например, самого выходного сигнала). Абсолютно бессмысленно требовать, чтобы PRNG, используемый для нечеткого тестирования, был криптографически сильным, потому что "шаблоны", демонстрируемые статистически сильными, но криптографически слабыми PRNG, в значительной степени являются проблемой только в том случае, если вам нужно предотвратить криптографически разбирающегося злоумышленника от прогнозирования выхода.
Я не думаю, что это действительно имеет значение, но я не могу доказать это.
Fuzz-тестирование будет пробовать только некоторые входные данные, в большинстве случаев это незначительная доля возможностей. Независимо от того, насколько хорошо вы используете ГСЧ, он может найти или не найти один из входов, который нарушает ваш код, в зависимости от того, какая доля всех возможных входов нарушает ваш код. Если шаблон в PRNG не очень прост, мне кажется маловероятным, что он каким-либо образом будет соответствовать шаблону в "плохих" входах, которые вы ищете, поэтому он попадет в него ни больше, ни меньше, чем истинно случайный.
На самом деле, если бы вы знали, как выбрать ГСЧ, чтобы максимизировать вероятность того, что он обнаружит неверные данные, вы, вероятно, могли бы использовать эти знания, чтобы помочь найти ошибку более непосредственно...
Я не думаю, что вы должны использовать действительно плохой PRNG. rand например, разрешено выставлять очень простые шаблоны, такие как чередование LSB. И если ваш код использует PRNG для внутреннего использования, вы, вероятно, захотите избегать использования одного и того же PRNG аналогичным образом в тесте, просто чтобы быть уверенным, что вы случайно не тестируете только те случаи, когда входные данные соответствуют внутренне сгенерированному потоку чисел! Небольшой риск, конечно, поскольку вы надеетесь, что они будут использовать разные семена, но все же.
Обычно на данном языке не так сложно найти крипто или, по крайней мере, безопасные хеш-библиотеки. SHA-1 везде и прост в использовании для генерации потока, или неудача в том, что RC4 тривиально реализовать самостоятельно. Оба обеспечивают довольно хороший PRNG, хотя и не такой безопасный, как Blum Blum Shub. Я бы подумал, что основной проблемой является скорость - если, например, Mersenne Twister может генерировать нечеткие тестовые случаи в 10 раз быстрее, а тестируемый код достаточно быстрый, то у него может быть больше шансов найти неверные входные данные в заданном время независимо от того, что с учетом 624 выходов вы можете вывести полное состояние ГСЧ...
Вам не нужен непредсказуемый источник (именно это и есть криптографически безопасный генератор), вам нужен только источник с хорошими статистическими свойствами.
Поэтому достаточно использовать генератор общего назначения - он быстрый и обычно воспроизводимый (что означает, что проблемы также воспроизводимы).