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

14

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

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

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

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

Существуют ли лучшие практики для тестирования систем такого рода? Если это так, некоторые ссылки будут очень полезны. Если нет, любые другие предложения приветствуются!

Джон Дусетт
источник
5
Вы не можете посмеяться над кольцевым буфером ядра тоже? И другие случайные аспекты вашего кода?
Джонатан Мерлет
1
@JonathanMerlet Потенциально, но проблема в том, что при развертывании код будет иметь доступ к реальному кольцевому буферу (на самом деле, к реальной ОС). Так что, если я тестирую только макетированную версию, я просто откладываю обнаружение этих ошибок на потом.
Джон Дусетт
Мне кажется , что проблема не связана с программой случайного поведения (так как это может управляться с помощью случайного семени) , но в конкретные состояния этого «ядро кольцевого буфера». Таким образом, ваш вопрос на самом деле «как проверить программу, которая зависит от внешнего состояния», верно?
AakashM
@AakashM, да, это лучший способ выразить это. Точнее говоря, программа с внешним состоянием, которое стохастически обращается или изменяет внешнее состояние.
Джон Дусетт

Ответы:

7

Полезно добавить хуки, как предлагается, для воссоздания точных состояний. Также настройте систему так, чтобы она могла выводить свои «семена» (в вашем случае, включая начальное число PRNG, а также кольцевой буфер ядра и любые другие источники недетерминированного ввода).

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

В конкретном случае вашего доступа к ядру, я бы порекомендовал сделать макет в любом случае. Используйте макет, чтобы вызвать классы эквивалентности, которые с меньшей вероятностью будут отображаться на практике, в духе «пусто» и «полностью» для контейнеров, или «0, 1, 2 ^ n, 2 ^ n + 1, много» для исчисляемые вещи. Затем вы можете протестировать с имитацией и с реальной вещью, зная, что вы обработали и протестировали случаи, о которых вы до сих пор думали.

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

Стефан А. Терре
источник
6

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

Дима
источник
1
это; или полностью прогонять prng
.
1
Спасибо за предложение! Я делаю это уже для модульного тестирования, но я не могу протестировать все возможные программы вручную.
Джон Дусетт
2
но это означает, что вы не можете проверить, правильно ли работает случайность ..
Луис Рис,
2

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

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

Euphoric
источник
Не обязательно, потому что вы можете выбрать небольшой «охватывающий» набор входов и запустить их несколько раз - количество входов, необходимых для определения надежности, может быть меньше. Этот «охватывающий» набор должен входить в каждую ветвь кода, инициализировать все объекты и т. Д.
Даниил Москович
2

Я не специалист в этой области, но есть научная литература относительно стохастического тестирования программ.

Если вы не можете легко создать тестовые классы, можно использовать статистический тест, как сказал #Euphoric. Borning et al. сравнить традиционный подход и статистический. Обобщение статистических тестов, предложенных @Euphoric, может быть обсуждением Уиттакера. Он предложил создать стохастическую модель желаемого (в вашем случае стохастического) поведения, а затем сгенерировать конкретные тестовые примеры из этой модели (см. Его специальную статью ).

mgoeminne
источник
Благодарность! Выглядит очень полезно. Для тех, кто находится за пределами академических учреждений, препринтную версию статьи можно взять из репозитория кода Google автора здесь: team4model.googlecode.com/svn/trunk/resources/paper/…
Джон