Superion

Plus de détails

%D0%A0%D0%B0%D0%B7%D0%B4%D0%B5%D0%BB%D1%8B%20%D1%80%D1%83%D1%81%D1%81%D0%BA%D0%BE%D0%B3%D0%BE%20%D1%8F%D0%B7%D1%8B%D0%BA%D0%B0

par Юлия Никитина

Часціны мовы

par Ya Vika

Grammarinator

par Николайчук Артём Константинович

Грамматика

par Vlada Zhzhenykh

В статье сравнивали различные мутации. Самыми удачными оказались мутация замены поддеревьев и перезапись токенов при помощи словаря, определённого человеком.

Берётся текущий тест и случайный из очереди длины <=10000 байт. Они парсятся и из их поддеревеьев формируется множество для мутаций. Берётся не больше 10000 поддеревеьев и длина каждого поддерева ограничена 200 байтами. Затем каждое поддерево текущего теста заменяется на каждое поддерево из множества, формируя новый тест. Плюсы: очень подробный перебор возможных тестов. Минусы: несмотря на ограничения тестов получается очень много.

Не совсем стандартные мутации АФЛ, а с улучшением под грамматику. Сначала создаётся словарь токенов(интересных слов). Его можно либо забить вручную, либо при помощи АФЛ. Далее делается предположение, что все токены должны состоять из цифр и букв. При мутации новый токен(из словаря) либо вставляется между двумя старыми, либо заменяет один из них.

Сначала парсим тест в AST(abstract syntax tree). Если происходит ошибка при парсинге, то делаем уменьшение по стратегии АФЛ: режем тест на чанки и последовательно пытаемся запустить без них, если покрытие не уменьшилось сохраняем изменения. Если ошибок не было, то поочерёдно выкидываем поддеревья и смотрим на покрытие, если не уменьшилось, выкидываем поддерево, заново парсим и начинаем алгоритм уменьшения с начала. Плюс: после такого уменьшение все тесты всегда будут валидными с точки зрения грамматики. Минусы: тесты "меньше" уменьшаются по сравнению с АФЛ. Вывод из статьи: таким образом, несмотря на относительно низкий коэффициент обрезки, эта стратегия обрезки с учетом грамматики может значительно улучшить коэффициент валидности для тестовых входных данных после обрезки, что облегчает и ускоряет дальнейшую работу с ними.

Берём все успешные тесты

Функция самая простая: если покрытие увеличилось, считаем тест успешным

В superion используется стандартное покрытие AFL, а именно: считаются все ветки, которые покрыл тест, и количество проходов по ним

Перебираем все короткие поддеревья нетерминала и пытаемся заменить текущее

Если в дереве грамматики есть вершина S с подвершиной S, то заменяем S на дочернюю вершину S

Обработка успешных

Исходя из контекста выбранной метрики. Например, если метрика - покрытие функций - и тест запустил новую функцию - то его оставляем.

Как понять нужен ли этот тест?

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

Выбрать несколько случайным образом

Оставить какой-то процент тех, у кого максимальна функция качества

Как выбрать наиболее успешные?

Если в вершине потенциально много поддеревьев, будем ходить туда чаще. Плюсы: позволит наиболее полно покрыть грамматику. Минусы: требуется предпосчёт количества деревьев для каждого нетерминала.

Чем чаще встречается переход в тестах, тем чаще мы его будем использовать. Плюсы: просто пишется. Позволяет направлять фаззер, путём изменения множества. Выбор символа становится более осмысленным с точки зрения программирования. Минусы: нужно начальное множество

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

Чем длиннее тест - тем он дольше будет выполняться, и тем сложнее будет разбираться в случае обнаружении бага

Из истории - чем код сложнее и рекурсивнее, тем вероятнее в нём есть баг.

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

Информацию о покрытии

Более детальный способ описывать покрытие. Метрика интересена только в контексте наличия других тестов. Плюсы: получаем более информативную оценку. Минусы: сложно реализовывать.

Подсчёт количества строк/функций, которые покрыл тест. Плюсы: просто (относительно) Минусы: метрика сама по себе не очень информативна. В контесте множества тестов можно выялять те, которые попадают в новые строки/функции.

Покрытие веток(путей)

Короткие

Сложные рекурсивные тесты

Функция(какая-то) от метрик, полученных при запуске, построении(сложность теста, покрытие, наличие эксепшона, длина)

Как понять, что тест успешный?

Убрать из тестов семантические ошибки. Например, использование необъявленных переменных

Если используется вероятностная грамматика, то в ней можно изменять случайно вероятности

Рекурсивное дублирование поддерева

AFL мутации - бит флип, замена "интересных значений"

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

Замена поддерева на случайно сгенерированное

Скрещивание с другими тестами, путём замены поддеревьев

Мутации

Контролировать размер во время построение теста, если такое используется

Можно просто выкидывать поддеревья

Рекурсивное замещение поддерева

Уменьшение поддерева

Запускать только один пример из очереди

Минимизация размера

Менять СРАЗУ всё поколение: Запускать все тесты и считать для каждого функцию качества

Как прогонять множество во время фаззинга?

Можно брать обратные вероятности Это позволит "мыслить" фаззеру в противоположном направлении. Плюсы: чаще будем покрывать неожиданные пути в грамматике. Минусы: чаще будем попадать в неинтересные символы(например в js часто будет вызываться return)

По количеству поддеревьев в нетерминале.

Если есть какое-то множество примеров, можно по частоте встречаемости нетерминалов в них.

Откуда брать вероятности?

По грамматике с вероятностями

Равновероятно по грамматике

Как генерировать?

Сгенерировать самим

Взять изначальное множество из интернета(либо из исходников, либо с гитхаба)

Откуда брать начальное множество?

Множество тестов

Покрытие функций(function coverage)

Покрытие кода(line coverage)

Патчим бинарь, чтобы получать метрики от тестов

Какие метрики хотим получать от бинаря?

Как патчить?

Можно как в АФЛ

Fuzzer

whitebox Предпочтительнее

greybox