Я в 2005-м или 2006-м оттестировал в пух и прах реализацию красно-чёрных деревьев, применив смесь написанных тестов и случайно сгенерённых. Получил полный или почти полный code coverage. Особая приятность была в том, что проверялись инварианты реализации (5 или сколько там свойств деревьев) и теста. Ошибок не нашёл и следующие 4 года там ничего не всплыло. Однако, в отладочной версии я вставил assert в удалении узла из дерева: просто сделал проверку на принадлежность перед удалением. И он один раз выстрелил, когда коллега допустил у себя ошибку. Пришёл потом спасибо говорить. :)
Что касается покрытия, ещё можно использовать текущее покрытие в комбинации с анализом кода для подкручивания входных данных. Подробностей реализации не знаю (наверное, генетический алгоритм плюс какой-то constraint solver), но так ищут дырки в безопасности во всяких там жутко сложных и больших парсерах. Быть может, и у вас что-то подобное завалялось, что можно открутить от fuzzing'а и прикрутить к тестированию алгоритма.
Comments 1
Что касается покрытия, ещё можно использовать текущее покрытие в комбинации с анализом кода для подкручивания входных данных. Подробностей реализации не знаю (наверное, генетический алгоритм плюс какой-то constraint solver), но так ищут дырки в безопасности во всяких там жутко сложных и больших парсерах. Быть может, и у вас что-то подобное завалялось, что можно открутить от fuzzing'а и прикрутить к тестированию алгоритма.
Reply
Leave a comment