Взять изначальное множество из интернета(либо из исходников, либо с гитхаба)
Сгенерировать самим
Как генерировать?
Равновероятно по грамматике
По грамматике с вероятностями
Откуда брать вероятности?
Если есть какое-то множество примеров, можно по частоте встречаемости нетерминалов в них.
По количеству поддеревьев в нетерминале.
Можно брать обратные вероятности Это позволит "мыслить" фаззеру в противоположном направлении. Плюсы: чаще будем покрывать неожиданные пути в грамматике. Минусы: чаще будем попадать в неинтересные символы(например в js часто будет вызываться return)
Как прогонять множество во время фаззинга?
Менять СРАЗУ всё поколение: Запускать все тесты и считать для каждого функцию качества
Минимизация размера
подтема
Запускать только один пример из очереди
Уменьшение поддерева
Рекурсивное замещение поддерева
Можно просто выкидывать поддеревья
Контролировать размер во время построение теста, если такое используется
Мутации
Скрещивание с другими тестами, путём замены поддеревьев
Замена поддерева на случайно сгенерированное
Для каждой вершинки в дереве считаем какую-то дополнительную информация и меняем, только на дерево с такой же инфомарцией. Например, тип нетерминала, количество переменных.
Если используется вероятностная грамматика, то в ней можно изменять случайно вероятности
Убрать из тестов семантические ошибки. Например, использование необъявленных переменных
Как понять, что тест успешный?
Функция(какая-то) от метрик, полученных при запуске, построении(сложность теста, покрытие, наличие эксепшона, длина)
Сложные рекурсивные тесты
Короткие
Покрытие веток(путей)
Подсчёт количества строк/функций, которые покрыл тест. Плюсы: просто (относительно) Минусы: метрика сама по себе не очень информативна. В контесте множества тестов можно выялять те, которые попадают в новые строки/функции.
Более детальный способ описывать покрытие. Метрика интересена только в контексте наличия других тестов. Плюсы: получаем более информативную оценку. Минусы: сложно реализовывать.
Информацию о покрытии
Какие свойства хотим получить у сгенерированных?
Из истории - чем код сложнее и рекурсивнее, тем вероятнее в нём есть баг.
Чем длиннее тест - тем он дольше будет выполняться, и тем сложнее будет разбираться в случае обнаружении бага
При генерации с равной вероятностью выбираем символ грамматики из текущей вершинки Плюсы: просто Минусы: работает хуже остальных. Например: будет часто вставлять терминальный символ вместо расширения дерева.
Чем чаще встречается переход в тестах, тем чаще мы его будем использовать. Плюсы: просто пишется. Позволяет направлять фаззер, путём изменения множества. Выбор символа становится более осмысленным с точки зрения программирования. Минусы: нужно начальное множество
Если в вершине потенциально много поддеревьев, будем ходить туда чаще. Плюсы: позволит наиболее полно покрыть грамматику. Минусы: требуется предпосчёт количества деревьев для каждого нетерминала.
Как выбрать наиболее успешные?
Оставить какой-то процент тех, у кого максимальна функция качества
Выбрать несколько случайным образом
Провести "турнир" в случайном подмножестве и взять нескольких победителей.
Как понять нужен ли этот тест?
Исходя из контекста выбранной метрики. Например, если метрика - покрытие функций - и тест запустил новую функцию - то его оставляем.
Обработка успешных
Если в дереве грамматики есть вершина S с подвершиной S, то заменяем S на дочернюю вершину S
Перебираем все короткие поддеревья нетерминала и пытаемся заменить текущее
Генерация тестов/деревьев
При генерации по правилам грамматики используется рандомизированный выбор. После выбора какого-то правила вероятность его повторного выбора уменьшается.
Производится предподсчёт размера поддеревьев для каждого символа и при генерации выбираются только те символы, которые не превысят заданную длину тестов.
