Добро пожаловать в «The Fuzzing Book»!

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

Учебник для бумаги, экрана и клавиатуры

Эту книгу можно использовать четырьмя способами:

• Читать главы в браузере. Можно воспользоваться списком глав в меню или сразу перейти к введению в тестирование либо к введению в фаззинг. Весь код доступен для скачивания.

• Работать с главами как с блокнотами Jupyter (бета-версия). Это позволяет редактировать и расширять код, экспериментируя с ним прямо в браузере. Для этого в верхней части каждой главы выберите «Resources → Edit as Notebook». Можно попробовать поработать с введением в фаззинг.

• Использовать код в собственных проектах. Код можно скачать в виде программ на Python: выберите «Resources → Download Code» для одной главы или «Resources → All Code» для всех глав. Эти файлы можно исполнять, получая (будем надеяться) те же результаты, что и в блокнотах. Есть и более простой вариант: установить пакет Python fuzzingbook.

• Показывать главы как слайды. Так материал можно использовать на лекциях. В верхней части каждой главы выберите «Resources → View slides». Можно посмотреть слайды к введению в фаззинг.

Для кого предназначена эта книга

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

Новости

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

Об авторах

Книгу написали Андреас Целлер, Рахул Гопинат, Марсель Бёме, Гордон Фрейзер и Кристиан Холлер. Все они — опытные специалисты по тестированию программ и генерации тестов, создавшие или существенно улучшившие одни из важнейших в мире генераторов тестов и фаззеров. Например, если вы читаете эту книгу в Firefox, Chrome или Edge, то можете делать это безопасно отчасти благодаря авторам: описанные в книге методы к настоящему времени обнаружили более 2 600 ошибок в интерпретаторах JavaScript этих браузеров. Авторы рады поделиться своим опытом и сделать его общедоступным.

Часто задаваемые вопросы Устранение неполадок Почему интерактивный блокнот запускается так долго?

Интерактивный блокнот использует сервис mybinder.org, который запускает блокноты на собственных серверах. Обычно запуск Jupyter через mybinder.org занимает около 30 секунд — в зависимости от подключения к Интернету. Однако если после обновления книги вы первым запускаете Binder, сервис заново создаёт среду, что занимает несколько минут. Время от времени обновляйте страницу.

Интерактивный блокнот не работает!

mybinder.org устанавливает ограничение в 100 одновременных пользователей для одного репозитория. Кроме того, как указано на странице состояния и надёжности mybinder.org, этот сервис является экспериментальным исследовательским проектом. Его создатели стремятся поддерживать доступность сайта, однако не гарантируют надёжность для критически важных задач.

Существуют и альтернативы mybinder.org; они перечислены ниже.

Есть ли альтернативы интерактивному блокноту?

Если mybinder.org не работает или не отвечает вашим потребностям, есть несколько вариантов:

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

2. Скачайте блокноты Jupyter через то же меню и откройте их в Jupyter. См. руководство по установке Jupyter Notebook.

Подробности приведены в статье об использовании кода The Fuzzing Book в собственных программах.

Можно также использовать образы Docker (экспериментальная возможность). Установите Docker, а затем выполните:

После этого откройте в браузере адрес (http://127.0.0.1/... или http://localhost/...), показанный в консоли. Вы получите ту же среду, что и на mybinder.org.

Если вы хотите создавать собственные образы Docker, возьмите за основу авторский Dockerfile.

Можно ли запускать код на компьютере с Windows?

Авторы стараются делать код как можно более универсальным, но при взаимодействии с операционной системой иногда предполагается Unix-подобная среда — именно такую предоставляет Binder. Чтобы запускать эти примеры на Windows, можно установить подсистему Linux или виртуальную машину с Linux.

Почему бы авторам не запустить собственный облачный сервис?

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

Содержание Можно ли использовать ваш код в собственных программах?

Да. Подробности приведены в инструкции по установке.

Какие материалы уже опубликованы?

Подробности приведены в примечаниях к выпускам.

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

Спасибо, что ссылаетесь на эту работу! После завершения книги её можно будет цитировать традиционным способом. Пока же нажмите кнопку «cite» в нижней части веб-страницы соответствующей главы, чтобы получить библиографическую запись.

Можете ли вы процитировать мою статью? А возможно, и написать о ней главу?

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

Преподавание и учебные курсы Можно ли использовать ваши материалы в учебном курсе?

Конечно. Соблюдайте условия лицензии, включая указание авторства и распространение на тех же условиях. Для коммерческого использования свяжитесь с авторами.

Можно ли расширять или адаптировать ваши материалы?

Да. Подробности также приведены в лицензии.

Как провести курс на основе книги?

Авторы успешно использовали этот материал в нескольких учебных курсах.

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

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

• Студенты выполняют упражнения из книги или более крупные проекты по фаззингу. Некоторые используют книгу как основу для исследований: Python позволяет очень легко создавать прототипы на Python.

При проведении курса не полагайтесь на mybinder.org — у сервиса недостаточно ресурсов для большой группы студентов. Вместо этого установите и запустите собственный хаб.

Можно ли сосредоточиться на отдельных наборах глав?

Для разных аудиторий подготовлено несколько экскурсий по книге. Карта книги показывает зависимости между отдельными главами.

Как расширять или адаптировать слайды?

Скачайте блокноты Jupyter через меню в верхней части страницы и измените их по своему усмотрению, включая параметры «Slide Type». Затем:

1. скачайте слайды из Jupyter Notebook; или

2. используйте расширение RISE (инструкция), чтобы показывать слайды непосредственно из Jupyter Notebook.

Предоставляете ли вы материалы в PDF?

На данный момент PDF-версии не поддерживаются. Авторы планируют подготовить PDF- и печатную версии после завершения книги.

Прочие вопросы У меня есть вопрос, комментарий или предложение. Что делать?

Можно написать @TheFuzzingBook@mastodon.social в Mastodon, чтобы к обсуждению присоединилось сообщество читателей. Об ошибках, которые следует исправить, сообщайте на странице разработки.

Я сообщил об ошибке две недели назад. Когда её исправят?

Вопросы рассматриваются в следующем порядке приоритета:

1. ошибки в коде, опубликованном на fuzzingbook.org;

2. ошибки в тексте, опубликованном на fuzzingbook.org;

3. написание недостающих глав;

4. ошибки в ещё не опубликованном коде или тексте;

5. вопросы, связанные с разработкой или сборкой;

6. всё, что помечено как «beta»;

7. всё остальное.

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

Авторы рады такому вопросу. На странице разработки находятся все исходные тексты и дополнительные материалы. Запросы на включение изменений с исправлениями приветствуются.

Как внести вклад?

Авторы рады принять:

• исправления и улучшения кода — размещайте код под лицензией MIT, чтобы его можно было легко включить в книгу;

• дополнительный текст, главы и блокноты по специализированным темам — для сторонних материалов планируется отдельный каталог.

Инструкции по написанию текста и кода приведены в руководстве для авторов.

В этой части мы знакомим читателя с темами книги.

Эта книга огромна. В ней более 20 000 строк кода и 150 000 слов текста, а печатная версия заняла бы свыше 1 200 страниц. Разумеется, авторы не предполагают, что каждый читатель захочет прочесть её целиком.

Прежде чем перейти к центральным разделам книги, познакомимся с основными понятиями тестирования программ. Зачем вообще тестировать программное обеспечение? Как его тестировать? Как определить, был ли тест успешным? Как понять, что проведено достаточно тестов? В этой главе мы вспомним важнейшие понятия и одновременно познакомимся с Python и интерактивными блокнотами.

Эта глава, как и вся книга, не заменяет учебник по тестированию. Рекомендованная литература приведена в разделе «Дополнительные сведения» в конце главы.

Простое тестирование

Начнём с простого примера. Вашей коллеге поручили реализовать функцию вычисления квадратного корня √(x). На минуту предположим, что в рабочей среде такой функции ещё нет. Изучив метод Ньютона — Рафсона, она написала следующий код на Python и утверждает, что функция my_sqrt() действительно вычисляет квадратный корень.

Теперь ваша задача — выяснить, действительно ли эта функция выполняет обещанное.

Как устроены программы на Python

Если вы ещё не знакомы с Python, сначала потребуется понять приведённый код. Чтобы получить представление о языке, настоятельно рекомендуем официальное руководство по Python. Для понимания примера особенно важны три момента:

1. Структура программ на Python задаётся отступами: тела функции и цикла while определяются уровнем отступа.

2. Python использует динамическую типизацию: тип переменных x, approx и guess определяется во время выполнения.

3. Большинство синтаксических конструкций Python заимствовано из других распространённых языков: это управляющие конструкции (while, if), присваивание (=) и сравнения (==, !=, <).

Этого уже достаточно, чтобы разобраться в коде. Начав с предположения x / 2, записанного в guess, функция вычисляет всё более точные приближения в approx, пока значение approx не перестанет меняться. В конце именно оно возвращается как результат.

Выполнение функции

Чтобы выяснить, правильно ли работает my_sqrt(), можно протестировать её на нескольких значениях. Например, при x = 4 она выдаёт правильный результат:

В интерактивном блокноте верхняя область с my_sqrt(4) — так называемая ячейка — передаётся интерпретатору Python, который по умолчанию вычисляет выражение. Нижняя область (2.0) содержит результат. Мы видим, что my_sqrt(4) возвращает верное значение.

По-видимому, то же верно и для x = 2.0:

Работа с блокнотами

Если вы читаете эту главу в интерактивном блокноте, попробуйте вызвать my_sqrt() с другими значениями. Щёлкните по одной из ячеек с вызовом функции и замените значение, например на my_sqrt(1). Нажмите Shift+Enter или кнопку запуска, чтобы выполнить ячейку и увидеть результат. Если появится сообщение об ошибке, сначала выполните расположенную выше ячейку с определением my_sqrt(). Можно также выполнить сразу все ячейки — подробности находятся в меню блокнота. Более того, щёлкнув по тексту, можно изменять и его.

Попробуйте сами, раскомментировав и выполнив следующую строку:

Выполнение одной ячейки не запускает остальные. Если она использует определение из другой, ещё не выполненной ячейки, возникнет ошибка. Чтобы гарантированно загрузить все определения, выберите в меню команду Run all cells above.

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

Отладка функции

Простой способ проследить за работой my_sqrt() — добавить вызовы print() в важных местах. Например, можно выводить значение approx, чтобы видеть, как на каждой итерации цикла приближение подходит к точному значению:

Интерактивные блокноты позволяют запускать и интерактивный отладчик: добавьте «магическую строку» %%debug в начало ячейки и посмотрите, что произойдёт. К сожалению, интерактивные отладчики мешают методам динамического анализа, используемым в этой книге, поэтому для отладки авторы в основном применяют журналирование и утверждения.

Проверка функции

Вернёмся к тестированию. Мы можем прочитать и выполнить код, но действительно ли полученное выше значение my_sqrt(2) правильно? Это легко проверить, воспользовавшись тем, что квадрат √(x) должен равняться x, иначе говоря, √(x) × √(x) = x:

Имеется небольшая ошибка округления, но в остальном всё выглядит правильно.

Итак, мы протестировали программу: выполнили её на заданных входных данных и проверили, правилен ли результат. Такой тест — необходимый минимум обеспечения качества перед вводом программы в эксплуатацию.

Автоматизация выполнения тестов

До сих пор мы тестировали программу вручную: сами запускали её и проверяли результаты. Такой способ очень гибок, но в долгосрочной перспективе неэффективен:

1. вручную можно проверить лишь очень ограниченное число запусков и результатов;

2. после каждого изменения программы процесс тестирования приходится повторять.

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

Например, следующий код автоматически проверяет равенство √(4) = 2:

Такой тест можно запускать снова и снова, каждый раз убеждаясь хотя бы в том, что квадратный корень из 4 вычисляется правильно. Однако остаётся несколько проблем:

1. для одного теста требуется пять строк кода;

2. ошибки округления не учитываются;

3. проверяется только один вход и один результат.

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

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

В нашем примере assert позволяет легко проверить, что my_sqrt() возвращает ожидаемый результат:

При выполнении этой строки ничего не происходит: мы лишь показали, то есть утвердили, что реализация действительно даёт √(4) = 2.

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

Можно определить для этой цели специальную функцию и проверить несколько конкретных значений:

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

Подсказка: настоящий программист на Python воспользовался бы функцией INLINEPLACEHOLDER0000END.

Генерация тестов

Помните универсальное свойство √(x) × √(x) = x? Его тоже можно явно проверить для нескольких значений:

Пока всё работает. Но главное — равенство √(x) × √(x) = x очень легко проверить для тысяч значений:

Сколько времени занимает проверка my_sqrt() на множестве значений? Измерим его.

Для измерения прошедшего времени используется собственный модуль Timer. Чтобы подключить его, сначала импортируется вспомогательный модуль, позволяющий импортировать другие блокноты:

Проверка 10 000 значений занимает примерно сотую долю секунды. Следовательно, один вызов my_sqrt() длится порядка одной миллионной секунды, то есть около одной микросекунды.

Повторим тест для 10 000 случайно выбранных значений. Функция Python random.random() возвращает случайное число от 0,0 до 1,0:

Меньше чем за секунду мы проверили 10 000 случайных значений, и квадратный корень каждый раз был вычислен правильно. Этот тест можно повторять после каждого изменения my_sqrt(), всё больше укрепляясь в том, что функция работает как положено. Однако хотя случайная функция выбирает значения без смещения, маловероятно, что она породит особые значения, радикально меняющие поведение программы. К этому вопросу мы вернёмся ниже.

Проверка во время выполнения

Вместо написания и запуска отдельных тестов для my_sqrt() проверку можно встроить непосредственно в реализацию. Тогда каждый без исключения вызов my_sqrt() будет проверяться автоматически.

Такую автоматическую проверку во время выполнения реализовать очень просто:

Теперь при каждом вычислении корня с помощью my_sqrt_checked()…

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

Однако автоматические проверки во время выполнения основываются на двух предположениях:

• Такие проверки нужно уметь формулировать. Сравнение с конкретными значениями обычно возможно, но абстрактно выразить желаемые свойства бывает очень сложно. На практике приходится выбирать наиболее важные свойства и проектировать подходящие проверки. Кроме того, проверка может зависеть не только от локальных свойств, но и от нескольких характеристик состояния программы — их тоже необходимо определить.

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

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

Системный ввод и аргументы функций

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

Смоделируем такой системный ввод программой sqrt_program(), принимающей строку под контролем внешней стороны:

Предположим, sqrt_program — программа, получающая системный ввод из командной строки:

Мы легко можем вызвать sqrt_program() с некоторым системным вводом:

В чём проблема? В том, что мы не проверяем допустимость внешних данных. Например, попробуйте вызвать sqrt_program("-1"). Что произойдёт?

При вызове my_sqrt() с отрицательным числом функция входит в бесконечный цикл. По техническим причинам бесконечные циклы в этой главе недопустимы: иначе код выполнялся бы вечно. Поэтому специальная конструкция with ExpectTimeout(1) прерывает выполнение через одну секунду.

В результате выводится сообщение об ошибке с исключением TimeoutError. Оно показывает стек вызовов функций и строк, активных в момент ошибки. В самом низу находится последняя выполненная строка, выше перечислены вызовы функций — в нашем случае вплоть до my_sqrt(x).

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

Теперь можно быть уверенным, что my_sqrt() вызывается только в соответствии со своей спецификацией:

Но что произойдёт, если передать sqrt_program() не число? Попытка преобразовать произвольную строку также приводит к ошибке времени выполнения:

Здесь возбуждается ValueError, поскольку строку xyzzy невозможно преобразовать в целое число. Следующая версия проверяет и такие неправильные данные:

Итак, на системном уровне программа должна корректно обрабатывать любые входные данные, никогда не переходя в неконтролируемое состояние. Для программистов это, конечно, дополнительная нагрузка: им приходится обеспечивать устойчивость программы при любых обстоятельствах. Но при генерации программных тестов эта нагрузка превращается в преимущество: если программа способна обработать любые данные, пусть даже выдавая строго определённые сообщения об ошибках, мы можем передавать ей любые данные. Однако при вызове функции со сгенерированными значениями необходимо точно знать её предусловия.

Ограничения тестирования

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

Например, вычисление √(0) с помощью my_sqrt() приводит к делению на ноль:

В результате возбуждается ZeroDivisionError: float division by zero.

До сих пор тесты не проверяли это условие. Поэтому программа, рассчитывающая на равенство √(0) = 0, неожиданно завершится с ошибкой. Даже если бы генератор создавал числа в диапазоне 0–1 000 000, а не 1–1 000 000, вероятность случайно получить ноль составляла бы всего один шанс из миллиона. Если поведение функции радикально меняется лишь для нескольких отдельных значений, простое случайное тестирование вряд ли их обнаружит.

Конечно, функцию можно исправить: документировать допустимые значения x и отдельно обработать случай x = 0:

Теперь √(0) = 0 вычисляется правильно:

Недопустимые значения приводят к исключению:

Здесь ожидаемо возбуждается AssertionError.

Тем не менее нужно помнить: обширное тестирование способно дать высокую уверенность в правильности программы, но не гарантирует, что все будущие запуски окажутся успешными. Даже проверка во время выполнения, контролирующая каждый результат, гарантирует лишь следующее: если результат получен, он будет правильным. Нет гарантии, что будущий запуск не завершится неудачной проверкой. На момент написания этой главы автор считает, что my_sqrt_fixed(x) правильно вычисляет √(x) для всех конечных чисел x, но не может быть в этом уверен.

Для метода Ньютона — Рафсона всё ещё есть неплохая возможность действительно доказать правильность реализации: она проста, а математическая основа хорошо изучена. Увы, это справедливо лишь для немногих областей. Если мы не собираемся строить полноценные доказательства корректности, лучшее, что может дать тестирование, — это:

1. проверять программу на нескольких хорошо подобранных входных данных;

2. тщательно и автоматически проверять результаты.

Именно этим посвящена оставшаяся часть книги: методам всестороннего тестирования программ и проверки правильности их состояния. Приятного чтения!

Итоги

• Цель тестирования — выполнить программу так, чтобы обнаружить ошибки.

• Выполнение и генерацию тестов, а также проверку результатов можно автоматизировать.

• Тестирование неполно: оно не даёт стопроцентной гарантии отсутствия ошибок в коде.

Следующие шаги

Теперь можно перейти к фаззингу — тестированию программ случайными входными данными.

Приятного чтения!

Дополнительные сведения

Существует множество работ по тестированию и анализу программного обеспечения.

• Современный, полный и доступный в Интернете учебник — *Effective Software Testing: A Developer's Guide* [Aniche2022]. Авторы настоятельно рекомендуют его.

• В качестве введения в предмет авторы также рекомендуют Software Testing and Analysis [Pezze2008]. Его выраженная техническая направленность отлично соответствует методологии этой книги.

• К числу других обязательных работ с комплексным взглядом на тестирование, включая психологию и организацию процесса, относятся The Art of Software Testing [Myers2004] и Software Testing Techniques [Beizer1990].

Упражнения Упражнение 1. Знакомство с блокнотами и Python

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

Начальный уровень: запуск блокнотов в браузере

Самый простой способ получить доступ к коду — запускать его в браузере.

1. На веб-странице откройте верхнее меню и выберите Resources → Edit as Notebook.

2. После короткого ожидания в браузере откроется Jupyter Notebook с текущей главой.

3. Материал можно прокручивать как обычно, а любой пример кода — редактировать и запускать сочетанием Shift + Return.

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

5. Изменения не сохраняются, если только вы не сохраните блокнот на диск.

Справка по Jupyter Notebook доступна в меню Help веб-страницы.

Продвинутый уровень: запуск кода Python на своём компьютере

Этот способ удобен для более серьёзных изменений, если вы не хотите работать с Jupyter.

1. На веб-странице откройте верхнее меню и выберите Resources → Download Code.

2. Код главы загрузится как один файл Python с расширением .py, который можно сохранить на компьютере.

3. Откройте файл, изменяйте его и запускайте примеры в предпочитаемой среде Python.

4. Особенно важно, что файл можно импортировать в собственный код и повторно использовать функции, классы и другие компоненты.

Справка по Python доступна в меню Help веб-страницы.

Профессиональный уровень: локальный запуск блокнотов

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

1. На веб-странице откройте верхнее меню и выберите Resources → All Notebooks.

2. Все блокноты Jupyter загрузятся как набор файлов .ipynb, который можно сохранить на компьютере.

3. Откройте их в Jupyter Notebook или JupyterLab, изменяйте и запускайте. Для навигации по книге используйте блокнот 00_Table_of_Contents.ipynb.

4. Отдельный блокнот можно скачать через Resources → Download Notebook, но для его запуска остальные блокноты уже должны находиться на компьютере.

Справка по Jupyter Notebook доступна в меню Help веб-страницы.

Уровень босса: внесите свой вклад

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

1. На веб-странице откройте верхнее меню и выберите Resources → GitHub Repo.

2. Откроется репозиторий GitHub со всеми исходными материалами книги, включая последние версии блокнотов.

3. Клонируйте репозиторий на диск, чтобы получить самую новую версию.

4. На странице GitHub можно сообщать о проблемах и отправлять запросы на включение изменений.

5. Команда git pull обновит локальную копию репозитория.

Если вы хотите предложить код или текст, ознакомьтесь с руководством для авторов.

Упражнение 2. Тестирование сортировки Шелла

Рассмотрим следующую реализацию сортировки Шелла, которая принимает список элементов и, предположительно, сортирует его:

Первый тест показывает, что shellsort(), возможно, действительно работает:

В качестве аргумента elems, копируемого в sorted_elems, и для фиксированного набора gaps реализация использует списки. В других языках списки подобны массивам:

Функция range() возвращает итерируемую последовательность элементов. Она часто применяется с циклами for, как в приведённой реализации:

Часть 1. Ручные тестовые случаи

Ваша задача — тщательно протестировать shellsort() на разнообразных входных данных.

Сначала напишите инструкции assert с несколькими ручными тестовыми случаями. Подберите их так, чтобы охватить крайние случаи. Для сравнения двух списков используйте ==.

Решение. Вот несколько выбранных тестов:

Часть 2. Случайные входные данные

Теперь создавайте случайные списки и передавайте их в shellsort(). Следующие вспомогательные предикаты проверяют, что результат, во-первых, отсортирован, а во-вторых, является перестановкой исходного списка:

Создайте генератор случайных списков. Пустой список записывается как [], а elems.append(x) добавляет в elems элемент x. Используйте приведённые вспомогательные функции для оценки результата. Сгенерируйте и протестируйте 1 000 списков.

Решение. Простой генератор случайных списков:

Пример его результата:

Проверка одного списка выглядит так:

А так выглядит тест для 1 000 списков:

Упражнение 3. Решение квадратного уравнения

Для уравнения ax^2 + bx + c = 0 требуется найти значения x по заданным a, b и c. Следующий код должен решать эту задачу с помощью формулы

Формула: x = (-b ± √(b^2 - 4ac))/(2a)

Однако эта реализация неполна. Можно:

1. вызвать деление на ноль;

2. нарушить предусловие my_sqrt_fixed().

Как это сделать и как предотвратить обе ошибки?

Часть 1. Поиск входных данных, вызывающих ошибки

Для каждого из двух случаев подберите значения a, b и c, вызывающие ошибку.

Решение. Вот два подходящих набора:

Первый вызывает AssertionError, поскольку дискриминант отрицателен.

Второй вызывает ZeroDivisionError.

Часть 2. Исправление проблемы

Дополните код, чтобы он обрабатывал эти случаи. Для несуществующих значений возвращайте None.

Решение. Следующая версия quadratic_solver() учитывает все крайние случаи:

Для обоих проблемных наборов она возвращает (None, None).

Часть 3. Дополнительный вопрос

Какова вероятность обнаружить эти условия с помощью случайных данных? Если выполнять миллиард тестов в секунду, сколько в среднем придётся ждать срабатывания ошибки?

Решение. Рассмотрим приведённый код. Если выбирать a, b и c из полного диапазона 32-битных целых чисел, вероятность уже первого условия — одновременного равенства a и b нулю — составляет p = 1 / (2^(32) × 2^(32)), то есть один шанс из 18,4 квинтиллиона:

Сколько лет придётся ждать при миллиарде тестов в секунду?

В среднем ждать пришлось бы 584 года. Очевидно, чисто случайного выбора недостаточно в качестве единственной стратегии тестирования.

Упражнение 4. К бесконечности и далее

Мы утверждали, что my_sqrt_fixed(x) работает для всех конечных чисел x. Что произойдёт, если присвоить x значение in fty — бесконечность? Проверьте сами.

Решение. Вызов my_sqrt_fixed( in fty ) завершается по тайм-ауту. Причина в том, что деление in fty на любое конечное число, выполняемое методом Ньютона — Рафсона, снова даёт in fty, и программа застревает в бесконечном цикле:

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

Эта часть знакомит с генерацией тестов на лексическом уровне, то есть с составлением последовательностей символов.

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

Предварительные требования

• Следует знать основы тестирования программного обеспечения, например материал главы «Введение в тестирование программного обеспечения».

• Необходимо достаточно хорошо понимать Python; подойдёт официальное руководство.

Сделаем эти требования явными. Сначала импортируем стандартный пакет для работы с блокнотами и используемые типы:

Затем явно импортируем предыдущую главу и тем самым объявляем зависимость от неё:

Краткое содержание

Чтобы использовать код этой главы, импортируйте нужный идентификатор:

В главе представлены два важных класса, описанных в разделе «Архитектура фаззинга»:

• Fuzzer — базовый класс фаззеров;

• Runner — базовый класс тестируемых программ.

Фаззеры

Fuzzer — базовый класс фаззеров, а RandomFuzzer — его простая реализация. Метод fuzz() объекта Fuzzer возвращает строку со сгенерированными входными данными.

Конструктор RandomFuzzer() принимает несколько именованных аргументов:

Исполнители

Fuzzer можно связать с объектом Runner, который получает сгенерированные строки. Результат состоит из зависящего от класса состояния и исхода (PASS, FAIL или UNRESOLVED). PrintRunner просто печатает полученные данные:

ProgramRunner передаёт сгенерированные данные внешней программе. Результат — пара из состояния программы, представленного экземпляром CompletedProcess, и исхода (PASS, FAIL или UNRESOLVED):

Задание по тестированию

Фаззинг родился «тёмной и бурной осенней ночью 1988 года» [Takanen2008]. Профессор Бартон Миллер сидел в своей квартире в Мадисоне, штат Висконсин, подключившись к университетскому компьютеру по телефонной линии со скоростью 1 200 бод. Гроза создавала помехи, из-за которых команды UNIX на обоих концах соединения получали искажённые данные и аварийно завершались. Частые сбои удивили Миллера: разве программы не должны быть устойчивее? Как учёный, он решил исследовать масштаб и причины проблемы. Для студентов Висконсинского университета в Мадисоне он подготовил задание по программированию, в рамках которого они создали первые фаззеры.

В задании говорилось:

Цель проекта — оценить устойчивость различных утилит UNIX при непредсказуемом потоке входных данных. […] Сначала вы создадите фазз-генератор — программу, выдающую случайный поток символов. Затем с его помощью вы атакуете как можно больше утилит UNIX, пытаясь вывести их из строя.

В этом задании заключена сущность фаззинга: создавайте случайные входные данные и смотрите, не сломают ли они что-нибудь. Просто дайте ему поработать достаточно долго — и увидите.

Простой фаззер

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

В реализации используются следующие возможности и функции Python:

• random.randrange(start, end) возвращает случайное число из диапазона [ start, end );

• range(start, end) создаёт итератор целых чисел из диапазона [ start, end ), который можно использовать подобно списку;

• for elem in list: body выполняет body в цикле, последовательно присваивая elem каждое значение из list;

• for i in range(start, end): body выполняет body в цикле для i от start до end - 1;

• chr(n) возвращает символ с кодом ASCII n.

Чтобы использовать случайные числа, импортируем соответствующий модуль:

Вот сама функция fuzzer():

С аргументами по умолчанию она возвращает строку случайных символов:

Барт Миллер назвал такие случайные неструктурированные данные словом fuzz. Представьте, что эта строка передана программе, ожидающей определённый формат — например, список значений через запятую или адрес электронной почты. Сможет ли программа без проблем обработать такой ввод?

Если этот пример уже кажется интересным, учтите, что фаззер легко настроить на другие типы данных. Например, fuzzer() может создавать последовательности строчных латинских букв. Функция ord(c) возвращает код ASCII символа c:

Результатом будет строка длиной до тысячи символов, состоящая только из букв от a до z. Предположим, программа ожидает на входе идентификатор. Рассчитана ли она на настолько длинные идентификаторы?

А следующий вызов создаёт строки с произвольными длинными десятичными числами:

Фаззинг внешних программ

Посмотрим, что произойдёт, если действительно вызвать внешнюю программу со сгенерированными данными. Сделаем это в два этапа: сначала создадим входной файл со случайными тестовыми данными, а затем передадим его выбранной программе.

Создание входных файлов

Получим имя временного файла, чтобы не засорять файловую систему:

Теперь файл можно открыть для записи. Функция Python open() открывает файл, в который затем записывается произвольное содержимое. Обычно она используется вместе с инструкцией with, гарантирующей закрытие файла сразу после того, как он перестанет быть нужен:

Убедимся, что файл действительно создан, прочитав его содержимое:

Запуск внешних программ

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

Для запуска bc используем модуль Python subprocess:

Объект result позволяет проверить вывод программы. Для bc это результат вычисления арифметического выражения:

Можно проверить и код завершения. Ноль означает, что программа завершилась штатно:

Все сообщения об ошибках находятся в result.stderr:

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

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

Вероятность получить строку длиной ровно один символ равна 1/101. Длина выбирается вызовом random.randrange(0, max_length + 1), а значение max_length по умолчанию равно 100. Таким образом, равновероятно выбирается одно из 101 значений в диапазоне от 0 до 100 включительно.

Чтобы получить / или ., нужна строка длиной один символ с вероятностью 1/101, а затем один из двух подходящих символов с вероятностью 2/32:

При стандартных параметрах символ ~, обозначающий домашний каталог, появиться не может: вероятность равна 0/32. Символы создаются вызовом chr(random.randrange(char_start, char_start + char_range)), где по умолчанию char_start = 32, а char_range = 32. Кодовая точка ~ равна 126 и не входит в диапазон [32, 64).

Если изменить char_range так, чтобы диапазон охватывал ~, появляется дополнительный опасный вариант удаления домашнего каталога.

На практике опасной может оказаться и более длинная строка, если второй символ — пробел. Например, команда rm -fr / WHATEVER сначала обработает /, а уже затем всё последующее. При стандартном диапазоне первый символ может быть / или ., то есть вероятность равна 2/32. Вероятность пробела на второй позиции — 1/32. Вероятность получить хотя бы два символа составляет 99/101, поскольку исключаются только длины 0 и 1. Итого:

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

Длительный фаззинг

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

Теперь по runs можно вычислять статистику. Например, подсчитаем число запусков без сообщений об ошибке. Здесь используется генератор списка: форма выражение for элемент in список if условие возвращает вычисленные выражения для тех элементов списка, где условие истинно. В данном случае выражение равно 1, а sum() складывает все единицы.

Большинство данных оказалось недопустимым, что неудивительно: случайная строка редко является правильным арифметическим выражением.

Рассмотрим первое сообщение об ошибке:

Проверим, встречаются ли сообщения помимо illegal character, parse error и syntax error, например crash или you found a fatal bug:

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

Возможно, сбой проявится как ненулевой код завершения bc. Подсчитаем такие запуски:

Оставим тест bc работать подольше, а пока посмотрим, как обстояли дела в 1989 году.

Ошибки, которые находят фаззеры

Когда Миллер и его студенты запустили первые фаззеры в 1989 году, результат оказался тревожным: проблемы обнаружились примерно у трети протестированных утилит UNIX — при случайном вводе они аварийно завершались, зависали или иным образом давали сбой [Miller1990]. Среди них была и программа bc. Приведённая выше версия bc — современная реализация, автор которой является убеждённым сторонником фаззинга.

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

Какие именно проблемы выявил эксперимент Миллера? Оказалось, что ошибки, совершавшиеся программистами в 1990 году, продолжают совершаться и сегодня.

Переполнения буфера

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

По иронии судьбы код ломается уже на строке "Wednesday" длиной девять символов. Лишние символы — здесь 'y' и завершающий строку '\0' — записываются в память после weekday, вызывая произвольные последствия. Например, там может находиться логическая символьная переменная, которая неожиданно изменится с 'n' на 'y'. Фаззинг легко создаёт сколь угодно длинные входные данные и их элементы.

Смоделируем такое поведение в Python:

Функция быстро завершается ошибкой:

Строка with ExpectError() обеспечивает вывод сообщения, после чего выполнение продолжается. Так ожидаемая ошибка отличается от неожиданных ошибок в других примерах.

Отсутствующие проверки ошибок

Во многих языках нет исключений; вместо них функции при необычных обстоятельствах возвращают специальные коды ошибок. Например, функция C getchar() обычно возвращает символ из стандартного ввода, а когда данные заканчиваются — специальное значение EOF (end of file, конец файла). Предположим, программист ищет следующий пробел, читая символы с помощью getchar():

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

Смоделируем пропущенную проверку. Эта функция фактически зависнет, если во входной строке нет пробела:

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

Конструкция with ExpectTimeout() прерывает заключённый в ней код через две секунды и печатает сообщение об ошибке.

Необычные числа

Фаззинг легко создаёт во входных данных необычные значения, вызывающие самое разное интересное поведение. Рассмотрим код на C, который сначала читает размер буфера, а затем выделяет буфер заданного размера:

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

Это поведение также легко смоделировать в Python. Функция collapse_if_too_large() завершается ошибкой, если переданная строка после преобразования в целое число оказывается слишком большой:

Попросим fuzzer() создать строку цифр:

При передаче такого числа в collapse_if_too_large() функция сразу даст сбой:

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

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

Обнаружение ошибок

Создав первый фаззер, Миллер и его студенты легко замечали ошибки по аварийному завершению или зависанию программы. Если сбой проявляется тоньше, требуются дополнительные проверки.

Универсальные средства проверки

Рассмотренные выше переполнения буфера — частный случай более общей проблемы. В C и C++ программа может обращаться к произвольным областям памяти, в том числе неинициализированным, уже освобождённым или вовсе не относящимся к структуре данных. Такая свобода необходима при разработке операционной системы и полезна для максимальной производительности и контроля, но опасна с точки зрения ошибок. К счастью, существуют средства, обнаруживающие подобные проблемы во время выполнения; особенно хорошо они сочетаются с фаззингом.

Проверка обращений к памяти

Для выявления проблемных обращений программы на C можно запускать в специальных средах проверки памяти. Во время выполнения они контролируют каждую операцию с памятью и определяют, обращается ли она к допустимой и инициализированной области. Популярный пример — LLVM AddressSanitizer, обнаруживающий целый класс потенциально опасных нарушений безопасности памяти. В следующем примере простая программа на C компилируется с этим средством, после чего чтение за пределами выделенной памяти вызывает ошибку.

Скомпилируем программу с включённой проверкой адресов:

При аргументе 99 программа возвращает buf[99], то есть 42:

Обращение к buf[110] приводит к диагностике AddressSanitizer о выходе за границы:

Чтобы находить ошибки в программах на C, такие проверки достаточно просто включить во время фаззинга. В зависимости от инструмента выполнение замедляется — для AddressSanitizer обычно примерно вдвое — и потребляет больше памяти, однако процессорное время чрезвычайно дёшево по сравнению с человеческими усилиями, необходимыми для поиска этих ошибок.

Выход за границы памяти представляет серьёзную угрозу безопасности: он может позволить злоумышленнику прочитать или даже изменить закрытые для него данные. Известный пример — ошибка Heartbleed в библиотеке OpenSSL, реализующей криптографические протоколы защищённой сетевой связи. Если вы читаете этот текст в браузере, соединение, скорее всего, зашифровано с помощью таких протоколов.

Heartbleed эксплуатировалась специально сформированной командой к службе heartbeat SSL. Она проверяет, жив ли сервер на другом конце соединения. Клиент мог отправить строку:

Сервер отвечал BIRD, подтверждая работоспособность.

К сожалению, службу можно было попросить вернуть больше символов, чем было отправлено. Это хорошо объясняет комикс XKCD:

В реализации OpenSSL прочитанная память могла содержать криптографические сертификаты, закрытые ключи и другие секреты; хуже того, никто не замечал факт доступа. К моменту обнаружения Heartbleed ошибка существовала много лет, и невозможно было узнать, какие тайны уже утекли. Срочно созданная информационная страница Heartbleed говорила сама за себя.

Как обнаружили Heartbleed? Очень просто. Исследователи компании Codenomicon и Google скомпилировали OpenSSL со средством проверки памяти, а затем засыпали библиотеку случайно сгенерированными командами. Проверка заметила выход за границы памяти — причём очень быстро.

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

После завершения примера созданные двоичный и исходный файлы удаляются:

Утечки информации

Утечки возникают не только из-за недопустимых обращений к памяти. Они возможны и внутри «допустимой» памяти, если та содержит конфиденциальные данные, которые не должны покидать программу. Покажем это на Python. Сначала создадим модель памяти с настоящими и случайными данными:

Добавим в secrets ещё «памяти», заполнив её маркером неинициализированной области "deadbeef":

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

Для обычных строк всё работает правильно:

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

Результат начинается с hat, а затем содержит остаток прежней памяти, в том числе маркеры <secret-certificate>, <secret-key>, <other-secrets> и повторяющееся deadbeef.

Как обнаружить такую проблему? Нужно распознавать сведения, которые не должны выходить наружу: секреты и неинициализированную память. Простую проверку можно смоделировать так:

Эта проверка показывает, что секреты и/или неинициализированная память действительно утекают. В главе о потоках информации рассматривается автоматический подход: конфиденциальные данные и производные от них значения помечаются как «заражённые», после чего контролируется, чтобы такие значения не покидали систему.

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

Проверки, зависящие от программы

Помимо универсальных проверок для всех программ определённой платформы или языка, можно разработать специализированные проверки для конкретной программы или подсистемы. Во введении в тестирование уже рассматривалась проверка правильности результатов функций во время выполнения.

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

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

Список кодов может быть критически важен: опечатка способна повлиять на всё приложение. Поэтому введём функцию проверки согласованности. Условие согласованности называется инвариантом представления, а проверяющие его функции или методы традиционно называют repOK() — «представление в порядке».

Сначала проверим отдельный код. Функция завершается ошибкой при нарушении правил:

Теперь code_repOK() можно применить ко всем элементам:

Если добавить недопустимый элемент, проверка сработает:

Вместо прямого изменения отображения лучше использовать отдельную функцию, которая сразу проверяет код:

Такая проверка обнаруживает и перепутанные аргументы:

Для максимальной надёжности add_new_airport() должна проверять представление всего списка кодов до и после изменения:

Так обнаруживается внесённая ранее несогласованность YMML.

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

В заключение рассмотрим сложную структуру — красно-чёрное дерево, самобалансирующееся двоичное дерево поиска. Реализовать его не слишком трудно, но даже опытному программисту могут потребоваться часы, чтобы добиться полной правильности. Метод repOK() одновременно документирует и проверяет все предположения:

Здесь repOK() — метод объекта RedBlackTree, выполняющий пять отдельных проверок с собственными утверждениями. При каждом добавлении или удалении элемента все условия согласованности проверяются автоматически. Ошибка в любом из них будет обнаружена — разумеется, если пропустить через дерево достаточно много случайных данных.

Статические средства проверки кода

Многие преимущества repOK() можно получить с помощью статической проверки типов. Например, MyPy находит ошибки типов в Python, если типы аргументов объявлены явно:

Если добавить ключ нестрокового типа:

MyPy немедленно сообщит об ошибке:

Однако более сложные свойства — например, ровно три заглавные буквы в коде аэропорта или отсутствие циклов в дереве — быстро достигают пределов статического анализа. Утверждения repOK() всё равно необходимы, лучше всего вместе с хорошим генератором тестов.

Архитектура фаззинга

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

Классы исполнителей

Сначала введём понятие Runner — объекта, выполняющего некоторую сущность с заданными входными данными. Обычно это тестируемая программа или функция, хотя возможны и более простые исполнители.

Базовый класс предоставляет метод run(input), передающий строку input исполнителю. run() возвращает пару (result, outcome). Значение result зависит от конкретного исполнителя и содержит подробности запуска; outcome относит результат к одной из трёх категорий:

• Runner.PASS — тест пройден, получены правильные результаты;

• Runner.FAIL — тест не пройден, получены неправильные результаты;

• Runner.UNRESOLVED — тест нельзя считать ни успешным, ни неуспешным, например потому, что запуск не состоялся из-за недопустимого ввода.

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

Например, PrintRunner переопределяет run() и просто печатает всё, что ему передано. Во многих случаях это исполнитель по умолчанию:

Результат — переданная строка "Some input", а исход пока равен UNRESOLVED, поскольку классифицировать поведение нечем.

ProgramRunner вместо этого передаёт данные на стандартный ввод программы, указанной при создании объекта:

Для двоичного, то есть нетекстового, ввода и вывода есть отдельный вариант:

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

Классы фаззеров

Определим фаззер, который передаёт данные потребителю. Базовый класс предоставляет основной метод fuzz(), создающий входные данные. Метод run() отправляет результат fuzz() исполнителю и возвращает исход, а runs() повторяет это заданное число раз (trials).

Сам по себе Fuzzer почти ничего не делает: fuzz() служит абстрактной заглушкой. Подкласс RandomFuzzer реализует описанную ранее функцию fuzzer() и добавляет параметр min_length, задающий минимальную длину:

Теперь конфигурацию фаззера достаточно указать один раз при создании:

Будут напечатаны десять случайных строк длиной ровно 20 символов.

Передадим такие строки созданному ранее исполнителю cat и проверим, что программа действительно копирует вход в выход:

Связывать Fuzzer с Runner приходится настолько часто, что для этого уже предусмотрен метод run():

Метод runs() повторяет фаззинг заданное число раз и возвращает список результатов:

В данном случае список содержит десять экземпляров CompletedProcess с исходом PASS.

Теперь всё готово для создания фаззеров: от простых случайных генераторов этой главы до гораздо более совершенных вариантов. Продолжение следует!

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

Итоги

• Случайная генерация входных данных — фаззинг — это простой и экономичный способ быстро проверить устойчивость произвольных программ.

• Ошибки, обнаруживаемые фаззерами, в основном связаны с дефектами и недостатками обработки входных данных.

• Для обнаружения ошибок следует использовать как можно больше проверок согласованности.

После завершения примеров временные файлы удаляются:

Следующие шаги

Далее можно изучить:

• применение мутаций к существующим входным данным для получения большего числа допустимых вариантов;

• использование грамматик для описания формата и генерации существенно большего числа допустимых данных;

• сокращение входных данных, вызывающих сбой, для эффективной отладки.

Приятного чтения!

Дополнительные сведения

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

• Fuzzing — Brute Force Vulnerability Discovery охватывает множество областей: файлы, веб-страницы, переменные среды и сетевые протоколы. Авторы опираются на большой опыт фаззинга в Microsoft и предлагают готовые инструменты для Windows и UNIX. Инструменты несколько устарели, но принципы остаются актуальными.

• Fuzzing for Software Security Testing and Quality Assurance [Takanen2008], второе издание которой вышло в 2018 году, рассматривает широкий набор фаззеров и методов обнаружения. Авторы обладают значительным опытом тестирования безопасности и поиска уязвимостей. Вероятно, это одна из наиболее полных и современных книг по теме.

Основополагающая работа для этой главы — An Empirical Study of the Reliability of UNIX Utilities [Miller1990], представившая и термин, и сам подход. Это обязательное чтение для всех, кого интересуют фаззинг и тестирование устойчивости: сделанные там наблюдения так же справедливы сегодня, как и тридцать лет назад.

Упражнения

Одна из ошибок, найденных Миллером и его коллегами [Miller1990], относилась к системе вёрстки troff. Она принимает текст по строкам; строка, начинающаяся с точки (.), содержит команду форматирования:

Команда nroff -ms сформировала бы следующий текст:

Во времена исследования Миллера troff давала сбой, если вход содержал:

1. последовательность \D — обратную косую черту и D — с последующим непечатаемым символом;

2. символ ASCII из диапазона 128–255, то есть с установленным восьмым битом, за которым шёл перевод строки;

3. единственную точку (.) с последующим переводом строки.

Упражнение 1. Модель troff

Для каждого случая напишите функцию Python f(s), завершающуюся ошибкой, если s удовлетворяет критерию сбоя.

Решение. Три функции, проверяющие вход на ошибки troff:

Примеры ожидаемых сбоев:

Упражнение 2. Запуск модели troff

Создайте подкласс Runner с именем TroffRunner, который проверяет перечисленные предикаты. Запустите его с Fuzzer. Фаззер должен порождать весь диапазон символов. Подсчитайте частоту нарушения каждого предиката.

Решение. Простой вариант:

Полученные частоты:

Некоторые входы, например единственная точка, действительно крайне маловероятны.

Упражнение 3. Запуск настоящей troff

С помощью BinaryProgramRunner примените настроенный фаззер к настоящей программе troff. Попробуйте получить запуск с ненулевым кодом возврата, указывающим на ошибку или аварийное завершение.

Решение. Достаточно соединить готовые компоненты:

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

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

Предварительные требования

• Необходимо представлять, как выполняется программа.

• Следует знать основы фаззинга из предыдущей главы.

Краткое содержание

Чтобы использовать код этой главы, импортируйте нужный идентификатор:

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

Обычно Coverage применяется с конструкцией with:

Печать объекта покрытия показывает функции и строки; перед невыполненными строками ставится #:

Метод trace() возвращает трассу — упорядоченный список выполненных мест программы. Каждое место представлено парой (имя функции, номер строки).

Метод coverage() возвращает покрытие — множество мест трассы, выполненных хотя бы один раз:

К множествам покрытия применимы обычные операции: пересечение показывает места, выполненные в нескольких запусках, а разность — места, выполненные в запуске a, но не в b. В главе также объясняется получение покрытия программ на C.

Для работы примеров импортируются вспомогательный пакет и используемые типы:

Декодер CGI

Начнём с простой функции Python, декодирующей строку в формате CGI. Кодирование CGI применяется в URL, то есть веб-адресах, чтобы представить недопустимые в них символы — пробелы и некоторые знаки пунктуации:

• пробел заменяется на '+';

• другие недопустимые символы заменяются на %xx, где xx — двухзначный шестнадцатеричный код.

Таким образом, строка "Hello, world!" превращается в "Hello%2c+world%21", где 2c и 21 — шестнадцатеричные коды ',' и '!'.

Функция cgi_decode() принимает такую строку и восстанавливает исходную форму. Реализация воспроизводит код из [Pezze2008], включая его ошибки, которые пока не раскрываются.

Пример работы:

Как систематически протестировать cgi_decode()? В литературе различают два способа получения тестов: тестирование чёрного ящика и белого ящика.

Тестирование чёрного ящика

Идея тестирования чёрного ящика состоит в получении тестов из спецификации. Для cgi_decode() нужно проверить документированные свойства:

• правильную замену '+';

• правильную замену %xx;

• отсутствие замены прочих символов;

• распознавание недопустимых входных данных.

Следующие четыре утверждения охватывают все свойства и успешно выполняются:

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

Тестирование белого ящика

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

• покрытие инструкций — каждая инструкция должна быть выполнена хотя бы одним тестом;

• покрытие ветвей — каждая ветвь должна быть выбрана хотя бы одним тестом; каждое условие if и while должно хотя бы раз стать истинным и хотя бы раз ложным.

Существуют и более сложные критерии: последовательности выбранных ветвей, ноль, одна или много итераций цикла, потоки данных между определениями и использованием переменных и другие. Хороший обзор приведён в [Pezze2008].

Для полного покрытия инструкций cgi_decode() нужно выполнить:

• блок после if c == '+';

• оба блока после if c == '%' — для допустимого и недопустимого кода;

• заключительный else для всех прочих символов.

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

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

Трассировка выполнения

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

В большинстве языков трассировку настроить непросто, но не в Python. Функция sys.settrace(f) задаёт трассировочную функцию f(), вызываемую для каждой выполняемой строки. Она получает доступ к текущей функции и её имени, значениям переменных и другим данным. Это идеальный инструмент динамического анализа — исследования того, что действительно происходит во время выполнения.

Рассмотрим конкретный запуск cgi_decode():

Чтобы проследить путь выполнения через cgi_decode(), воспользуемся sys.settrace(). Сначала определим трассировочную функцию, вызываемую для каждой строки. Она принимает три параметра:

• frame — текущий кадр, предоставляющий доступ к местоположению и переменным:

• frame.f_code содержит выполняемый код, а frame.f_code.co_name — имя функции;

• frame.f_lineno содержит текущий номер строки;

• frame.f_locals содержит локальные переменные и аргументы;

• event — строка, принимающая, среди прочего, значения "line" при достижении новой строки и "call" при вызове функции;

• arg — дополнительный аргумент некоторых событий; например, для "return" он содержит возвращаемое значение.

Наша функция будет регистрировать номер текущей строки через frame:

Трассировка включается и отключается с помощью sys.settrace():

При вычислении cgi_decode("a+b") видно прохождение по функции. После инициализации hex_values, t и i цикл while выполняется трижды — по одному разу для каждого входного символа:

Чтобы сопоставить номера с исходным кодом, получим текст функции через inspect:

cgi_decode_code — строка с исходным текстом. Разобьём её на массив строк, индексируемый номером; пустой первый элемент обеспечивает нумерацию с единицы:

Теперь cgi_decode_lines[L] — строка L исходного кода. Например:

Первые зарегистрированные строки 8–12 инициализируют hex_values, затем строка 15 инициализирует t.

Чтобы увидеть строки, выполненные хотя бы раз, преобразуем трассу в множество:

Полный код можно напечатать, пометив невыполненные строки символом #; такая разметка направляет внимание разработчика на непокрытые участки:

Часть строк — прежде всего комментарии — закономерно остаётся непокрытой, поскольку не исполняется. Но не выполнялись и строки внутри elif c == '%'. Если "a+b" пока единственный тест, отсутствие покрытия побуждает добавить случай, проходящий через строки с #.

Класс Coverage

В книге покрытие используется постоянно: для измерения эффективности разных методов генерации и для направления генерации к непокрытому коду. Глобальная переменная coverage неудобна, поэтому реализуем класс, упрощающий измерение.

Основная идея — воспользоваться инструкцией Python with. Общая форма:

выполняет BODY, определив OBJECT и при необходимости сохранив его в VARIABLE. В начале и конце тела автоматически вызываются OBJECT.__enter__() и OBJECT.__exit__(), даже если возникло исключение. Поэтому Coverage.__enter__() может включать трассировку, а Coverage.__exit__() — отключать. После блока специальные методы предоставят сведения о покрытии:

Во время function_to_be_traced() трассировка включена, после блока — отключена, а множество выполненных строк доступно через cov.

Ниже приведена полная реализация. Для использования необязательно понимать каждую деталь:

Используем класс:

Coverage отслеживает не только строки, но и имена функций, что полезно для программ из нескольких файлов.

В интерактивном режиме объект можно просто напечатать. Получится листинг с # перед невыполненными строками:

Как и ранее, результат показывает, что ветвь обработки % не покрыта.

Сравнение покрытия

Поскольку покрытие представлено множеством выполненных строк, к нему применимы операции над множествами. Например, можно найти строки, покрытые одним тестом, но не другим:

Это единственная строка, которая выполняется только для входа 'a+b'.

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

Теперь легко увидеть строки, пока не покрытые тестом "a+b":

Это строки обработки %xx, которого ещё не было во входных данных данного теста.

Покрытие при базовом фаззинге

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

Один из полученных примеров:

Выполним декодирование и посмотрим на достигнутое покрытие. Вызов cgi_decode() заключён в блок try...except, чтобы игнорировать исключения ValueError, возникающие при недопустимых форматах %xx.

Достигли ли мы максимального покрытия? Очевидно, некоторых строк всё ещё не хватает:

Попробуем ещё раз и будем увеличивать покрытие на протяжении 100 случайных входов. В массиве cumulative_coverage хранится покрытие, накопленное с течением времени: cumulative_coverage[0] — общее число строк, покрытых после первого входа, cumulative_coverage[1] — число строк, покрытых после первого и второго входов, и так далее.

Создадим сто входов, чтобы определить, как растёт покрытие:

Вот как покрытие увеличивается с каждым новым входом:

Это, конечно, только один прогон. Повторим эксперимент несколько раз и построим график средних значений.

Мы видим, что в среднем полное покрытие достигается после 40–60 фаззинговых входов.

Получение покрытия внешних программ

Разумеется, не весь мир программирует на Python. Хорошая новость заключается в том, что задача получения покрытия встречается повсеместно и почти для каждого языка программирования существуют средства его измерения. В качестве примера покажем, как получить покрытие программы на C.

Наша программа на C снова реализует cgi_decode, но на этот раз это самостоятельная программа, запускаемая из командной строки:

Ниже приведён код на C, сначала в виде строки Python. Начнём с обычных включаемых заголовков:

Далее следует инициализация hex_values:

Вот собственно реализация cgi_decode(), использующая указатели на исходные данные (s) и результат (t):

Наконец, драйвер принимает первый аргумент и вызывает для него cgi_decode:

Создадим исходный файл C. Обратите внимание: следующая команда перезапишет cgi_decode.c, если такой файл уже существует в текущем рабочем каталоге. Помните об этом, если вы скачали ноутбуки и работаете локально.

Полный исходный файл доступен отдельно: INLINEPLACEHOLDER0000END.

В ноутбуке он выводится с подсветкой синтаксиса так:

Теперь код C можно скомпилировать в исполняемый файл. Параметр --coverage предписывает компилятору инструментировать код так, чтобы во время выполнения собиралась информация о покрытии. Точный набор параметров зависит от компилятора.

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

Информацию о покрытии обрабатывает программа gcov. Для каждого переданного ей исходного файла она создаёт новый файл .gcov с данными о покрытии. Вспомогательные данные могут храниться в файлах с именами вида cgi_decode... или cgi_decode-cgi_decode....

В файле .gcov перед каждой строкой стоят число её выполнений (- обозначает неисполняемую строку, а ##### — ни одного выполнения) и номер строки. Рассмотрим, например, cgi_decode(). Видно, что единственный ещё не исполненный фрагмент — return -1 для недопустимого входа.

Прочитаем этот файл и получим множество покрытия:

Один из результатов:

С этим множеством можно выполнять те же вычисления покрытия, что и для программ на Python.

Поиск ошибок с помощью базового фаззинга

Если дать фаззеру достаточно времени, он действительно сможет покрыть каждую строку cgi_decode() независимо от языка программирования. Однако это ещё не означает, что в коде нет ошибок. Мы не проверяем результат cgi_decode(), поэтому функция может вернуть что угодно, а мы этого не проверим и даже не заметим. Для обнаружения таких ошибок нужен проверяющий результаты компонент, обычно называемый оракулом, который подтверждал бы правильность результатов теста. В нашем случае можно было бы сравнивать реализации cgi_decode() на C и Python и проверять, дают ли они одинаковые результаты.

Зато фаззинг превосходно находит внутренние ошибки, которые можно обнаружить даже без проверки результата. Если запустить наш fuzzer() для cgi_decode(), такая ошибка обнаружится очень быстро:

Итак, cgi_decode() можно аварийно завершить. Почему? Посмотрим на входные данные:

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

Эта проблема присутствует и в варианте на C, который унаследовал её от исходной реализации [Pezze et al., 2008]:

Здесь s — указатель на считываемый символ, а ++ сдвигает его на один символ.

В реализации на C проблема на самом деле гораздо серьёзнее. Если '%' находится в конце строки, приведённый код сначала прочитает завершающий символ ('\0' в строках C), а затем следующий символ. Последний может содержать любые данные из памяти за пределами строки, из-за чего программа способна выйти из строя непредсказуемым образом. Некоторое утешение состоит в том, что '\0' не является допустимым шестнадцатеричным символом, поэтому версия на C прочитает «всего лишь» один символ за концом строки.

Любопытно, что ни один из составленных ранее ручных тестов эту ошибку не вызывает. Более того, её не обнаружат ни покрытие операторов, ни покрытие ветвей, ни какой-либо из критериев покрытия, обычно обсуждаемых в литературе. Простой фаззинговый прогон, напротив, выявляет ошибку за несколько попыток — если во время выполнения действуют подходящие проверки, способные обнаруживать такие выходы за границы. Это определённо повод фаззить больше!

Итоги

В этой главе представлен класс Coverage, позволяющий измерять покрытие программ на Python. В контексте этой книги мы используем сведения о покрытии, чтобы направлять фаззинг к ещё не исполненным участкам кода.

Типичный способ применения класса Coverage — в конструкции with:

После выхода из блока with метод coverage() возвращает множество пар (имя функции, номер строки), а метод trace() — последовательность выполненных строк. Полное определение класса и примеры его использования приведены выше в этой главе.

Полученные знания

• Метрики покрытия — простой и полностью автоматизированный способ приблизительно оценить, какая доля функциональности программы действительно выполняется во время тестового прогона.

• Существует несколько метрик покрытия; важнейшие среди них — покрытие операторов и покрытие ветвей.

• В Python очень легко получить доступ к состоянию программы во время выполнения, включая исполняемый в данный момент код.

Дальнейшие шаги

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

• направлять *мутации* существующих входных данных к лучшему покрытию в главе о мутационном фаззинге.

Дополнительные сведения

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

Упражнения Упражнение 1. Исправление cgi_decode()

Создайте подходящий тест, воспроизводящий рассмотренный выше IndexError. Исправьте cgi_decode(), чтобы предотвратить ошибку. Покажите, что ваш тест и дополнительные запуски fuzzer() больше её не выявляют. Сделайте то же самое для варианта на C.

Решение

Вот тестовые случаи:

Корректная последовательность из двух шестнадцатеричных цифр по-прежнему должна декодироваться:

Вот исправление:

Проверим исправление на трёх случаях:

А теперь снова запустим фаззер:

Для варианта на C подойдёт следующее исправление:

После этого вернитесь к приведённым выше командам компиляции и заново соберите cgi_decode.

Упражнение 2. Покрытие ветвей

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

нужно покрыть как случай, когда CONDITION истинно и управление переходит к do_a(), так и случай, когда CONDITION ложно и управление переходит к do_b(). Это относится ко всем управляющим конструкциям с условием: if, while и другим.

Чем покрытие ветвей отличается от покрытия операторов? В предыдущем примере различий фактически нет. Но они есть здесь:

Для покрытия операторов достаточно одного теста, в котором CONDITION истинно и вызывается do_a(). Для покрытия ветвей нужен также тест, в котором do_a() не вызывается.

Используя нашу инфраструктуру Coverage, покрытие ветвей можно имитировать с помощью пар последовательно исполненных строк. Метод trace() выдаёт список строк в порядке выполнения:

Часть 1. Вычисление покрытия ветвей

Определите функцию branch_coverage(), которая принимает трассу и возвращает множество пар последовательных строк. Например:

Дополнительное задание для опытных программистов на Python: определите BranchCoverage как подкласс Coverage и реализуйте описанную branch_coverage() в виде метода coverage() класса BranchCoverage.

Решение

Простое определение branch_coverage():

Результат содержит пары переходов, в том числе:

А вот определение в виде класса:

Часть 2. Сравнение покрытия операторов и ветвей

Используйте branch_coverage(), чтобы повторить эксперименты из этой главы с покрытием ветвей вместо покрытия операторов. Покрывают ли написанные вручную тесты все ветви?

Решение

Повторим предыдущие эксперименты с BranchCoverage:

Результат — множество из 20 переходов, совпадающее с приведённым в решении первой части.

Сравним вход с плюсом и обычный вход:

Зададим максимальное покрытие с помощью ручных тестов:

Снова используем ранее созданный случайный пример:

Этот прогон покрывает 23 пары строк. До заданного вручную максимума не хватает следующих переходов:

Определим накопительное покрытие ветвей для набора входов:

Ручные тесты дали 28 переходов:

Дополнительное покрытие в ручном максимуме возникает из-за исключения, вызванного недопустимым входом, например %g:

Это артефакт последовательных вызовов cgi_decode() при вычислении cov_max.

Часть 3. Среднее покрытие

Ещё раз повторите предыдущие эксперименты с покрытием ветвей. Покрывает ли fuzzer() все ветви и, если да, сколько тестов для этого требуется в среднем?

Решение

Повторим для покрытия ветвей эксперименты, ранее проведённые для покрытия строк:

Мы видим, что покрытия ветвей удаётся достичь позднее, чем покрытия операторов: для случайных входов это просто более трудный критерий.

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

Предварительные требования

• Следует знать, как работает базовый фаззинг, например из главы «Фаззинг: случайные входные данные».

• Следует понимать основы получения покрытия.

Краткое содержание

Чтобы использовать код этой главы, импортируйте нужный идентификатор:

В главе представлен класс MutationFuzzer, принимающий список начальных входов, или семян, которые затем подвергаются мутациям:

Один из результатов:

Класс MutationCoverageFuzzer поддерживает популяцию входов, которые эволюционируют так, чтобы максимизировать покрытие:

Фаззинг с мутациями

В ноябре 2013 года вышла первая версия American Fuzzy Lop (AFL). С тех пор AFL стал одним из самых успешных инструментов фаззинга и обзавёлся множеством вариантов, например AFLFast, AFLGo и AFLSmart, которые также обсуждаются в этой книге. AFL сделал фаззинг популярным средством автоматического поиска уязвимостей. Он первым продемонстрировал, что уязвимости можно автоматически и в большом масштабе обнаруживать во множестве реальных приложений, критичных с точки зрения безопасности.

Рисунок 1. Пользовательский интерфейс командной строки American Fuzzy Lop.

В этой главе мы познакомимся с основами мутационного фаззинга. В следующей главе будет показано, как направлять фаззинг к определённым целям в коде.

Фаззинг анализатора URL

Многие программы ожидают, что входные данные будут иметь строго определённый формат, и только после этого приступают к их обработке. В качестве примера рассмотрим программу, принимающую URL — веб-адрес. Чтобы программа могла работать с адресом, он должен иметь корректный формат URL. Какова вероятность случайно сгенерировать корректный URL при фаззинге случайными входами?

Чтобы лучше понять задачу, разберём состав URL. URL состоит из нескольких элементов:

где:

• scheme — используемый протокол, например http, https, ftp, file и другие;

• netloc — имя узла, с которым устанавливается соединение, например www.google.com;

• path — путь на этом узле, например search;

• query — список пар «ключ — значение», например q=fuzzing;

• fragment — метка позиции в полученном документе, например #result.

В Python для разбора URL на составные части можно использовать функцию urlparse().

Результат кодирует отдельные части URL в разных атрибутах.

Предположим, что у нас есть программа, принимающая URL. Для простоты она почти ничего не делает: только проверяет корректность переданного адреса. Если URL корректен, программа возвращает True, иначе возбуждает исключение.

Попробуем фаззить http_program(). Будем использовать весь диапазон печатаемых символов ASCII, чтобы в него входили :, / и строчные буквы.

Один из результатов:

Попробуем 1000 случайных входов и посмотрим, добьёмся ли хоть какого-нибудь успеха:

Какова вероятность получить корректный URL? Наша строка должна начинаться с "http://" или "https://". Сначала рассмотрим "http://". В начале должны оказаться семь строго определённых символов. Вероятность случайно породить их при диапазоне из 96 символов равна 1 : 96^7, то есть:

Шанс получить префикс "https://" ещё ниже — 1 : 96^8:

Общая вероятность составляет:

А вот сколько прогонов в среднем понадобится, чтобы получить корректную схему URL:

Измерим длительность одного прогона http_program():

Довольно быстро, не правда ли? К сожалению, выполнить нужно очень много прогонов.

В годах это составляет:

Даже при широкой распараллеленности ждать всё равно придётся от нескольких месяцев до нескольких лет. И всё это ради одного успешного прогона, который проникнет глубже в http_program().

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

Мутация входных данных

Вместо генерации случайных строк с нуля можно начать с заданного корректного входа и затем последовательно его мутировать. В данном контексте мутация — простое преобразование строки: например, вставка случайного символа, удаление символа или инвертирование бита в представлении символа. Такой подход называется мутационным фаззингом, в отличие от рассмотренных ранее методов генерационного фаззинга.

Начнём с нескольких видов мутаций.

Удаление случайного символа:

Вставка случайного печатаемого символа:

Инвертирование случайного бита в случайной позиции:

Теперь создадим общий мутатор, случайно выбирающий применяемую мутацию:

Идея состоит в следующем: если вначале у нас есть один или несколько корректных входов, можно получать новые кандидаты, применяя одну из этих мутаций. Чтобы увидеть подход в действии, вернёмся к URL.

Мутация URL

Вернёмся к задаче разбора URL. Создадим функцию is_valid_url(), проверяющую, принимает ли http_program() данный вход.

Применим функцию mutate() к заданному URL и посмотрим, сколько корректных входов удастся получить.

Видно, что благодаря мутациям исходного входа значительная доля результатов остаётся корректной:

Какова вероятность получить префикс https:, мутируя начальный образец с http:? Нужно выбрать вставку (1 : 3), вставить правильный символ 's' (1 : 96) и поместить его в нужную позицию (1 : l), где l — длина начального входа. Значит, в среднем понадобится столько прогонов:

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

Один из результатов:

Разумеется, для получения, например, префикса "ftp://" потребовались бы дополнительные мутации и прогоны. Самое важное — пришлось бы применить несколько мутаций.

Несколько мутаций

До сих пор мы применяли к строке-образцу только одну мутацию. Но можно выполнить и несколько мутаций, изменяя строку всё сильнее. Что, например, произойдёт, если применить к образцу 20 мутаций?

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

Чтобы объединить несколько мутаций в одном компоненте, введём класс MutationFuzzer. Он принимает семя — список строк, — а также минимальное и максимальное число мутаций.

Далее мы будем постепенно расширять MutationFuzzer, добавляя к нему методы. Язык Python требует определять весь класс со всеми методами как единый непрерывный блок, но нам хочется вводить методы по одному. Для этого воспользуемся специальным приёмом. Когда нужно добавить новый метод к классу C, применяется конструкция:

На первый взгляд C объявляется подклассом самого себя, что не имеет смысла. В действительности создаётся новый класс C как подкласс старого класса C, после чего старое определение скрывается. В итоге получается класс C с методом new_method(), что нам и требуется. Объекты C, созданные ранее, сохранят прежнее определение класса, поэтому их придётся создать заново.

С помощью этого приёма добавим метод mutate(), вызывающий определённую выше одноимённую функцию. Метод удобен тем, что позднее позволит расширять MutationFuzzer.

Вернёмся к нашей стратегии максимизации разнообразия покрытия популяции. Сначала создадим метод create_candidate(): он случайно выбирает вход из текущей популяции (self.population), применяет от min_mutations до max_mutations мутаций и возвращает итоговый результат.

Метод fuzz() сначала выдаёт семена, а когда они заканчиваются, переходит к мутациям:

Посмотрим на fuzz() в действии. Каждый новый вызов даёт очередной вариант с несколькими мутациями.

Однако рост разнообразия входов повышает риск получить некорректные данные. Ключ к успеху — направлять мутации, то есть сохранять особенно ценные варианты.

Управление с помощью покрытия

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

Поскольку тестирование всегда исполняет рассматриваемую программу, сведения о выполнении можно собирать в любом случае — как минимум информацию, необходимую для решения, прошёл тест или нет. Покрытие также часто измеряют для оценки качества теста, поэтому предположим, что покрытие тестового прогона нам доступно. Тогда возникает вопрос: как использовать покрытие для управления генерацией тестов?

Особенно успешная идея реализована в популярном фаззере American Fuzzy Lop, или сокращённо AFL. Подобно нашим предыдущим примерам, AFL развивает успешные тестовые случаи, но для него «успех» означает обнаружение нового пути выполнения программы. Поэтому AFL продолжает мутировать входы, которые уже нашли новые пути; если очередной вход обнаруживает ещё один путь, он также сохраняется.

Построим такую стратегию. Начнём с класса Runner, сохраняющего покрытие заданной функции. Сначала определим FunctionRunner:

Расширим FunctionRunner, чтобы он также измерял покрытие. После вызова run() метод coverage() будет возвращать покрытие последнего прогона.

Первые пять покрытых позиций:

Теперь определим основной класс. В нём хранятся популяция и множество уже достигнутых покрытий (coverages_seen). Метод run() исполняет вход с помощью переданного исполнителя. Если покрытие оказалось новым, то есть отсутствует в coverages_seen, вход добавляется в population, а покрытие — в coverages_seen.

Используем этот класс:

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

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

Итоги

В этой главе представлен класс MutationFuzzer, который принимает список начальных входов и подвергает их мутациям. Класс MutationCoverageFuzzer поддерживает популяцию входов и развивает её с целью максимизации покрытия. Полные определения обоих классов и примеры их использования приведены выше.

Полученные знания

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

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

Дальнейшие шаги

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

Упражнения Упражнение 1. Фаззинг декодирования CGI с помощью мутаций

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

Один из результатов:

После 10 000 прогонов удалось синтезировать символ + и корректную форму %xx. Результат всё ещё можно улучшить.

Упражнение 2. Фаззинг bc с помощью мутаций

Примените описанный выше мутационный фаззинг к bc, как в главе «Фаззинг: случайные входные данные».

Часть 1. Неуправляемые мутации

Начните с неуправляемых мутаций. Сколько входов окажутся корректными?

Решение

Достаточно связать ProgramRunner с MutationFuzzer:

Часть 2. Управляемые мутации

Продолжите с управляемыми мутациями. Для этого потребуется извлекать покрытие из программы на C, такой как bc. Выполните следующие шаги.

Сначала получите GNU bc; например, скачайте bc-1.07.1.tar.gz и распакуйте его:

Затем настройте пакет:

Скомпилируйте пакет со специальными флагами покрытия:

Теперь файл bc/bc должен быть исполняемым:

После этого можно запустить gcov для получения сведений о покрытии:

Как показано в главе «Покрытие кода», файл bc-1.07.1/bc/main.c.gcov теперь содержит сведения о покрытии bc.c. Перед каждой строкой указано число её выполнений. ##### означает отсутствие выполнений, а - — неисполняемую строку.

Разберите файл GCOV для bc и создайте множество coverage, как в FunctionCoverageRunner. Оформите решение в виде класса ProgramCoverageRunner, который принимает список исходных файлов (bc.c, main.c, load.c), для которых следует запускать gcov.

После завершения работы не забудьте удалить временные файлы:

Упражнение 3

В этой записи блога автор American Fuzzy Lop (AFL), очень популярного мутационного фаззера, обсуждает эффективность различных операторов мутации. Реализуйте четыре из них и оцените их эффективность по аналогии с приведёнными выше примерами.

Упражнение 4

При добавлении нового элемента в список кандидатов AFL на самом деле сравнивает не покрытие, а добавляет элемент, если тот проходит по новой ветви. Используя покрытие ветвей из упражнений главы «Покрытие кода», реализуйте эту стратегию и сравните её с приведённой выше стратегией покрытия.

Упражнение 5

Спроектируйте и реализуйте систему, которая собирает популяцию URL из Всемирной паутины. Удаётся ли добиться с этими образцами более высокого покрытия? Что произойдёт, если использовать их как начальную популяцию для дальнейших мутаций?

В предыдущей главе мы познакомились с мутационным фаззингом — методом, который создаёт фаззинговые входы, внося небольшие изменения в заданные данные. Теперь покажем, как направлять эти мутации к определённым целям, например к увеличению покрытия. Алгоритмы этой главы происходят от популярного фаззера American Fuzzy Lop (AFL), в особенности от его вариантов AFLFast и AFLGo. Мы исследуем лежащий в основе AFL алгоритм фаззинга серого ящика и способы применять его для решения различных задач автоматического обнаружения уязвимостей.

Предварительные требования

• Рекомендуется прочитать введение в мутационный фаззинг.

Краткое содержание

Чтобы использовать код этой главы, импортируйте нужный идентификатор:

В главе представлены усовершенствованные методы фаззинга серого ящика, вдохновлённые AFL. Конструктор класса GreyboxFuzzer принимает три аргумента. Первый — список начальных входов:

Второй — мутатор, изменяющий отдельные части входа:

Третий — расписание энергии, распределяющее усилия фаззинга между элементами популяции:

Все три аргумента передаются конструктору GreyboxFuzzer:

Класс GreyboxFuzzer используется совместно с FunctionCoverageRunner:

После фаззинга можно изучить популяцию:

Она содержит исходный URL и множество всё сильнее мутировавших вариантов, которые привели к новому покрытию.

Помимо простого PowerSchedule, доступны усовершенствованные расписания:

• AFLFastSchedule назначает высокую энергию «необычным» путям, по которым проходят редко.

• AFLGoSchedule назначает высокую энергию путям, близким к ещё не покрытым позициям программы.

Конструктору AFLGoSchedule требуется метрика distance от каждого узла к целевым позициям, вычисленная анализом кода программы. Подробности приведены далее в этой главе.

AFL — эффективный фаззер серого ящика

Алгоритмы этой главы происходят от популярного фаззера American Fuzzy Lop (AFL).

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

AFL также является фаззером серого ящика: не чёрного и не белого. Он использует обратную связь по покрытию, чтобы учиться проникать глубже в программу. Это не полностью чёрный ящик, поскольку AFL применяет по меньшей мере некоторый анализ программы. Но это и не полностью белый ящик: AFL не опирается на тяжеловесный анализ кода или решение ограничений. Вместо этого он использует лёгкую инструментацию программы, чтобы получать сведения о покрытии ветвей сгенерированным входом. Если вход увеличивает покрытие, он добавляется в корпус семян для дальнейшего фаззинга.

Для инструментации AFL вставляет небольшой фрагмент кода сразу после каждой инструкции условного перехода. При выполнении этот так называемый трамплин присваивает пройденной ветви уникальный идентификатор и увеличивает связанный с ней счётчик. Ради эффективности число попаданий учитывается лишь приблизительно. Иными словами, для каждого входа фаззер знает, какие ветви выполнялись и примерно сколько раз.

Обычно инструментация выполняется во время компиляции исходного кода в исполняемый файл. Однако AFL можно запускать и для неинструментированных двоичных файлов с помощью виртуальной машины, например QEMU, либо средства динамической инструментации, например Intel PinTool. Для программ на Python сведения о покрытии можно собирать без инструментации, как показано в главе «Покрытие кода».

Составляющие фаззинга серого ящика

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

Мутаторы

Введём специальные классы для мутации семени.

Сначала определим класс Mutator. Получив начальный вход inp, он возвращает слегка изменённую версию inp. В главе о грамматическом фаззинге серого ящика этот класс будет расширен с учётом грамматики входа, что позволит реализовать интеллектуальный фаззинг серого ящика.

Операция вставки добавляет случайный символ в случайную позицию:

При удалении выбирается случайная позиция в непустой строке и удаляется соответствующий символ. Для пустой строки вместо этого выполняется вставка:

При замене в символе на случайной позиции непустой строки инвертируется случайный бит. Для пустой строки снова используется вставка:

Главный метод mutate() случайно выбирает оператор из списка:

Попробуем мутатор:

Семена и расписания энергии

Теперь введём новое понятие — расписание энергии. Оно распределяет драгоценное время фаззинга между семенами популяции. Наша цель — как можно больше времени тратить на наиболее прогрессивные семена, которые быстрее приводят к росту покрытия.

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

Помимо самих данных к каждому семени нужно прикрепить дополнительную информацию. Для этого определим класс Seed.

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

В Python длинные циклы for можно выразить компактнее:

• lambda x: ... возвращает функцию, принимающую x; лямбда-выражения позволяют быстро определять безымянные функции;

• map(f, l) возвращает последовательность результатов применения f к каждому элементу l;

• random.choices(l, weights)[0] возвращает элемент l[i] с вероятностью weights[i].

Проверим, действительно ли расписание выбирает семена равномерно и случайно. Попросим его 10 000 раз выбрать семя из популяции A, B, C и подсчитаем попадания. Каждое семя должно встретиться примерно 3300 раз.

Результат выглядит правильно: каждое семя выбиралось примерно в трети случаев.

Исполнители и программа-пример

Начнём с небольшой программы из шести строк. Для сбора покрытия во время выполнения импортируем класс FunctionCoverageRunner из главы о мутационном фаззинге.

Конструктор FunctionCoverageRunner принимает исполняемую функцию Python. Метод run() принимает вход, передаёт его функции и собирает сведения о покрытии этого выполнения. Метод coverage() возвращает список пар (имя функции, номер строки) для каждого покрытого оператора.

Функция crashme() возбуждает исключение для входа "bad!". Посмотрим, какие операторы покрывает вход "good".

В crashme вход "good" покрывает только условный оператор в строке 2. Условие ветви len(s) > 0 and s[0] == 'b' ложно.

Усовершенствованный мутационный фаззинг чёрного ящика

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

Класс AdvancedMutationFuzzer — усовершенствованная и параметризуемая версия MutationFuzzer из предыдущей главы. Он также наследует класс Fuzzer. Пока достаточно знать методы fuzz(), возвращающий сгенерированный вход, и runs(), выполняющий fuzz() заданное число раз. В AdvancedMutationFuzzer мы переопределим fuzz().

AdvancedMutationFuzzer создаётся с набором начальных семян, мутатором и расписанием энергии. Во время кампании он поддерживает корпус семян population. Метод fuzz() возвращает либо ещё не фаззившееся начальное семя, либо результат фаззинга семени из популяции. Последним занимается create_candidate(): метод выбирает вход из популяции и применяет несколько мутаций.

Испытаем мутационный фаззер. Передадим одно семя и попросим создать три входа.

Посмотрим, сколько операторов покроет мутационный фаззер чёрного ящика за кампанию из n = 30 000 входов.

Вызов runs(crashme_runner, trials=n) создаёт n входов и исполняет их функцией crashme через crashme_runner. Как уже отмечалось, исполнитель также собирает сведения о покрытии.

Для измерения покрытия используется функция population_coverage(). Она принимает набор входов и функцию Python, исполняет входы и собирает сведения о покрытии. Результат — пара (all_coverage, cumulative_coverage), где all_coverage содержит все покрытые операторы, а cumulative_coverage — число покрытых операторов по мере роста числа выполненных входов. Для графика покрытия во времени нас интересует второе значение.

Извлечём созданные фаззером входы и измерим рост покрытия:

Следующие входы увеличили покрытие нашего примера crashme:

Итог. Так работает мутационный фаззер чёрного ящика. Мы встроили мутатор, создающий входы из заданного набора семян, и расписание энергии, решающее, какое семя выбрать следующим.

Мутационный фаззинг серого ящика

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

Метод run() унаследован от класса Fuzzer; он создаёт и исполняет ровно один вход. Мы переопределим его так, чтобы вход, увеличивающий покрытие, добавлялся в population. Атрибут coverages_seen хранит множество ранее покрытых операторов.

Испытаем фаззер серого ящика:

Покрывает ли он больше операторов после генерации того же числа тестовых входов?

Популяция нашего примера теперь содержит следующие семена:

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

Итог. Мы увидели, как фаззер серого ящика «обнаруживает» интересные семена, способные обеспечить дальнейший прогресс. Начав с good, он постепенно научился генерировать bad!, возбуждающий исключение. Как сделать это ещё быстрее?

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

Дополнительное чтение. Мы рассмотрели AFL на высоком уровне. Технические подробности одного из наиболее успешных инструментов обнаружения уязвимостей описаны в документации AFL.

Усиленный фаззинг серого ящика

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

Чтобы определить путь конкретного входа, воспользуемся функцией getPathID из раздела о покрытии трасс.

Функция getPathID() возвращает уникальный хеш множества покрытия:

Энергию можно назначать по необычности пройденного пути несколькими способами. Здесь реализуем экспоненциальное расписание, вычисляющее энергию e(s) семени s так:

Формула: e(s) = (1)/(f(p(s))^a)

где:

• p(s) возвращает идентификатор пути, пройденного семенем s;

• f(p) возвращает число прохождений пути p сгенерированными входами;

• a — заданный показатель степени.

Пусть фаззер серого ящика считает число f(p) прохождений каждого пути p и обновляет расписание:

Запустим усиленный фаззер n=10 000 раз на простом примере, установив показатель экспоненциального расписания a=5:

Построим распределение частот путей:

Сравним результат с фаззером серого ящика, использующим классическое расписание:

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

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

При быстром расписании почти вся энергия достаётся самому редкому пути:

Именно так: новое экспоненциальное расписание назначает основную энергию семени, проходящему по самому редкому пути.

Сравним достигаемое покрытие во времени:

Как и ожидалось, усиленный фаззер с экспоненциальным расписанием достигает покрытия гораздо быстрее.

Итог. Чаще фаззя семена, проходящие по низкочастотным путям, можно значительно эффективнее исследовать пути программы.

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

Дополнительное чтение. Подробнее об усилении фаззеров рассказано в статье «Coverage-based Greybox Fuzzing as Markov Chain» [Böhme et al., 2016]; реализация для AFL доступна в репозитории AFLFast.

Сложный пример: HTMLParser

Сравним три фаззера на более реалистичном примере — анализаторе HTML из Python. Запустим каждый фаззер n=5000 раз для HTMLParser, начав с «пустого» семени.

Сравним рост покрытия:

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

Фаззер серого ящика исполняет гораздо более сложные входы, многие из которых содержат специальные символы — круглые и квадратные скобки, а также угловые скобки <, >, [, ]. Однако важные ключевые слова, например <html>, всё ещё отсутствуют.

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

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

Направленный фаззинг серого ящика

Иногда требуется, чтобы фаззер достиг определённой опасной позиции в исходном коде — например, места предполагаемого переполнения буфера — или проверил недавнее изменение в кодовой базе. Как направить фаззер к таким позициям?

Здесь мы представим направленный фаззинг серого ящика как задачу оптимизации.

Решение лабиринта

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

Лабиринт задаётся простой строкой:

Код генерируется функцией generate_maze_code(). Здесь мы не раскрываем её реализацию, а объясняем результат; подробности реализации будут приведены в приложении о потоке управления.

Следующие заглушки будут заменены с помощью exec():

Цель — переместить X к #, передавая символы D для движения вниз, U — вверх, L — влево и R — вправо.

Каждый символ maze_string обозначает клетку. Для каждой клетки генерируется отдельная функция:

• если текущая клетка безопасна ( ), вызывается функция клетки, соответствующая следующему входному символу D, U, L или R; неожиданные символы игнорируются; когда вход заканчивается, возвращаются "VALID" и текущее состояние лабиринта;

• если текущая клетка является ловушкой (+, |, -), возвращаются "INVALID" и текущее состояние;

• если текущая клетка — цель (#), возвращаются "SOLVED" и текущее состояние.

Попробуйте сами. Проверьте другие последовательности ходов или измените сам лабиринт.

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

Граф содержит функцию maze, функции всех клеток tile_<строка>_<столбец> и рёбра допустимых переходов между ними. Он автоматически строится Graphviz из сгенерированного исходного кода.

Первая попытка

Введём класс DictMutator, который изменяет строки, вставляя ключевое слово из заданного словаря:

Для фаззинга лабиринта расширим DictMutator: добавим операции дописывания словарного ключа и удаления символа в конце начального значения.

Испытаем обычный фаззер серого ящика с классическим энергетическим расписанием и расширенным мутатором лабиринта на 20 000 входах.

Нам ещё не раз понадобятся статистические данные разных фаззеров, поэтому вынесем их печать в функцию:

Насколько хорошо справится старый добрый фаззер серого ящика?

Вероятно, лабиринт не был решён ни разу. Как сообщить фаззеру, насколько начальное значение «далеко» от цели? Зная это, мы могли бы просто выделить такому значению больше энергии.

Попробуйте сами. Напечатайте статистику усиленного фаззера с AFLFastSchedule и CountingGreyboxFuzzer. Скорее всего, он значительно превзойдёт неусиленный вариант: путь с наименьшей вероятностью случайно оказывается путём к цели.

Вычисление расстояния на уровне функций

По статическому графу вызовов кода лабиринта и целевой функции можно вычислить расстояние от каждой функции f до цели t как длину кратчайшего пути между f и t.

Сгенерированный код лабиринта содержит функцию target_tile, которая возвращает имя целевой функции:

Теперь найдём соответствующую функцию в графе вызовов. get_callgraph() возвращает граф вызовов кода лабиринта в виде графа NetworkX, а NetworkX предоставляет полезные операции анализа графов.

Теперь можно получить расстояния на уровне функций. Словарь distance сопоставляет каждой функции расстояние до цели. Если пути к цели нет, назначается максимальное расстояние 0xFFFF.

Функция nx.shortest_path_length(cg, node, target_node) возвращает длину кратчайшего пути от node к target_node в графе cg.

Ниже приведены расстояния для всех функций клеток на пути к целевой функции:

Итог. Используя статический граф вызовов и целевую функцию t, мы показали, как вычислить расстояние от каждой функции f до t на уровне функций.

Попробуйте сами. Подумайте над следующими вопросами:

• Как вычислять расстояние, если целей несколько? Подсказка: среднее геометрическое.

• Если известны граф вызовов CG и граф потока управления CFG_f каждой функции f, как вычислить расстояние на уровне базовых блоков? Подсказка: в CFG_f измеряйте расстояние до вызовов функций, находящихся на пути к цели. Помните, что расстояние между базовыми блоками в функциях с большим расстоянием на уровне функций тоже должно быть больше.

Дополнительное чтение. Другие аспекты поиска рассмотрены в главе о поисковом фаззинге. Решение поставленных выше задач описано в статье «Directed Greybox Fuzzing».

Направленное энергетическое расписание

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

Точнее, пусть d_f(s,t) — расстояние на уровне функций от функции s до функции t в графе вызовов CG. Тогда расстояние начального значения i до функции t равно

Формула: d(i,t)=(Σ_(s in CG) d_f(s,t))/(|CG|),

где |CG| — число узлов графа вызовов, посещённых этим входом.

Сравним направленное расписание со старым добрым фаззером серого ящика:

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

Нормализуем ось y, чтобы повысить важность начальных значений с малым расстоянием.

Улучшенное направленное энергетическое расписание

Улучшенное расписание нормализует расстояние начального значения между минимальным и максимальным значениями. Для расстояния d(i,t) от начального значения i до функции t новое расстояние d'(i,t) вычисляется так:

Формула: d'(i,t)= 1 если d(i,t) = minD = maxD; maxD - minD если d(i,t) = minD ≠ maxD; (maxD - minD)/(d(i,t)-minD) в остальных случаях,

где

Формула: minD=min_(i in T)[d(i,t)] и maxD=max_(i in T)[d(i,t)],

а T — множество начальных значений, то есть популяция.

Посмотрим, как работает улучшенное расписание:

В отличие от всех предыдущих расписаний, это породило сотни решений. Отфильтруем из первого решения все игнорируемые входные символы. filter(f, seed.data) возвращает элементы e из seed.data, для которых f(e) истинно.

Это действительно решение лабиринта, заданного в начале раздела.

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

Попробуйте сами. Реализуйте и оцените более простое направленное расписание, использующее минимальное, а не среднее расстояние на уровне функций. В чём недостаток минимального расстояния?

Дополнительное чтение. Подробнее о направленном фаззинге серого ящика можно узнать из одноимённой статьи «Directed Greybox Fuzzing»; реализация для AFL доступна в репозитории AFLGo.

Краткое содержание

В этой главе представлены продвинутые методы фаззинга серого ящика, вдохновлённые популярным фаззером AFL. Конструктор GreyboxFuzzer принимает три аргумента. Во-первых, список начальных входов:

Во-вторых, мутатор, изменяющий отдельные части входа:

В-третьих, энергетическое расписание, распределяющее усилия фаззинга по популяции:

Все три передаются конструктору:

GreyboxFuzzer используется вместе с FunctionCoverageRunner:

После фаззинга можно изучить популяцию:

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

Кроме простого PowerSchedule, доступны продвинутые расписания:

• AFLFastSchedule выделяет много энергии «необычным» путям, которые выполнялись редко;

• AFLGoSchedule выделяет много энергии путям, близким к ещё не покрытым позициям программы.

Конструктору AFLGoSchedule требуется метрика distance от каждого узла к целевым позициям, полученная анализом кода программы.

Иерархию основных классов можно воспроизвести так:

Усвоенные уроки

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

• Энергетическое расписание позволяет направлять и контролировать фаззер:

• усиленный фаззер серого ящика тратит больше энергии на начальные значения, выполняющие «маловероятные» пути, в надежде открыть ещё более редкие пути и увеличить число исследованных путей за единицу времени;

• направленный фаззер тратит больше энергии на значения, которые «ближе» к целевой позиции, чтобы следующие входы приблизились к ней ещё сильнее.

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

Дополнительные материалы

• Домашняя страница AFL.

• Документация LibFuzzer — другого известного фаззера серого ящика.

• Marcel Böhme, Soumya Paul. «A Probabilistic Analysis of the Efficiency of Automated Software Testing», IEEE TSE, 42:345–360, 2016. В работе исследуется, насколько быстро фаззер белого ящика должен проходить каждый путь, чтобы оставаться эффективнее фаззера серого ящика.

Что дальше

Наша цель всё та же: достаточно полно покрывать функциональность, чтобы обнаруживать как можно больше ошибок. Для этого книга рассматривает два класса методов:

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

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

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

Совместимость

В предыдущей версии главы класс AdvancedMutationFuzzer назывался просто MutationFuzzer, что создавало путаницу с одноимённым классом из введения в мутационный фаззинг. Следующее объявление вводит обратно совместимый псевдоним:

Упражнения

Будут добавлены.

Иногда нас интересует не просто как можно больше разнообразных входов, а конкретные тестовые данные, достигающие заданной цели — например, определённой строки программы. Если мы понимаем, что ищем, это можно найти поиском.

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

Систематическое применение эвристик воплощено в метаэвристических алгоритмах. Приставка «мета» означает, что алгоритмы универсальны и настраиваются под конкретную задачу. Они часто вдохновлены природой: эволюцией, роевым интеллектом или химическими реакциями. Такие методы намного эффективнее полного перебора и подходят даже для огромного пространства входов программ.

Предварительные знания

• Следует понимать, как работает покрытие кода; см. главу о покрытии.

Краткое содержание

Эта глава показывает, как с помощью метаэвристического поиска находить входы, достигающие заданных мест исходного кода. Простейший алгоритм — подъём на холм:

Он начинает со случайной точки, многократно переходит к лучшему соседу и в одном из прогонов получает:

Разные задачи требуют вариантов вроде steepest_ascent_hillclimber и restarting_hillclimber. Поиск направляют функции приспособленности; чтобы оценивать близость к строкам программы, код инструментируется. Для более сложных пространств применяются эволюционные методы, в том числе генетические алгоритмы.

Генерация тестов как задача поиска

Чтобы применить метаэвристический алгоритм к генерации тестов, прежде всего нужно определить пространство поиска. Оно зависит от представления искомого результата: одно целое число, кортеж, объект, XML-документ или иной тип данных.

Представление входов программы как задачи поиска

Представление сильно зависит от тестируемой программы. Рассмотрим функцию test_me():

У неё два параметра, а результат определяется их соотношением. Тестовый вход — пара значений x и y:

Поэтому естественное представление пространства входов — кортежи (x, y). У каждой его точки восемь соседей:

• (x - 1, y - 1);

• (x - 1, y);

• (x - 1, y + 1);

• (x, y + 1);

• (x + 1, y + 1);

• (x + 1, y);

• (x + 1, y - 1);

• (x, y - 1).

Для начала ограничим обе координаты диапазоном от −1000 до 1000:

Функция neighbors() реализует окрестность Мура: возвращает восемь непосредственных соседей, не выходящих за границы MIN и MAX.

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

Ландшафт поиска: функции приспособленности

Все метаэвристики используют функцию, оценивающую качество кандидата. Это качество называется приспособленностью (fitness), а эвристика — функцией приспособленности. Она отображает любую точку пространства поиска в число. Чем кандидат ближе к оптимуму, тем лучше это значение.

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

Предположим, требуется покрыть истинную ветвь условия x == 2 * (y + 1). Насколько произвольная точка (274, 153) далека от этой цели?

Чтобы условие стало истинным, оба числа должны совпасть. Чем больше разность, тем дальше вход от нужной ветви. Поэтому расстояние можно вычислить как abs(x - 2 * (y + 1)):

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

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

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

Инструментация

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

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

Функции приспособленности нужен программный доступ к расстоянию. В простейшем варианте сохраним его в глобальной переменной:

Теперь функция приспособленности запускает инструментированную программу и читает distance:

Подъём на холм для нашего примера

Определив представление — пары целых чисел — и функцию приспособленности — расстояние до целевой ветви, можно реализовать поиск. Возьмём простейшую метаэвристику: подъём на холм. Название хорошо передаёт идею, хотя в нашем ландшафте лучшие точки находятся внизу, так что технически алгоритм спускается в долину.

Алгоритм очень прост:

1. Выбрать случайную начальную точку.

2. Определить приспособленность всех соседей.

3. Перейти к соседу с лучшей приспособленностью.

4. Если решение ещё не найдено, вернуться к шагу 2.

Вероятность того, что случайные x и y сразу удовлетворят x == 2 * (y + 1), мала. Пусть начальная точка равна (274, 153). Правая часть равна 308, поэтому условие ложно. Посмотрим на приспособленность точки и соседей:

Увеличение y на единицу повышает правую часть до 310, то есть делает значения ещё менее равными. Увеличение x, напротив, сближает их. Интуитивно лучший из восьми соседей — (275, 152): условие всё ещё ложно, но «менее ложно», чем прежде.

Реализуем алгоритм:

Один из прогонов даёт:

Алгоритм случайно выбирает x и y в небольшом диапазоне [MIN, MAX], чтобы пример выполнялся быстро, затем вычисляет приспособленность. Поскольку ищется минимум, цикл продолжается, пока значение не станет равным 0.

В каждой итерации проверяются соседи. Как только находится лучший, он становится новой текущей точкой. Если убрать break, будут оценены все соседи и выбран лучший из них. Такой вариант называется подъёмом на холм с наискорейшим восхождением. Число итераций обычно уменьшается, хотя в каждой выполняется больше тестов.

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

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

Для покрытия истинной ветви снова возьмём разность сторон сравнения и инструментируем функцию:

Построим новый ландшафт:

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

Изменение невелико: логический флаг отмечает, произошло ли перемещение. Если нет, выбирается новая случайная позиция. Заодно функция приспособленности стала параметром алгоритма.

Запустите пример несколько раз. Иногда градиент сразу ведёт к оптимуму, а иногда до решения происходит несколько перезапусков.

Мы ограничивали начальные x и y сравнительно малым диапазоном [MIN, MAX]. Это распространённый приём: в большинстве случаев решения состоят из небольших значений, и такое смещение ускоряет поиск. Но если нужное решение находится далеко, алгоритм будет идти к нему очень долго и при фиксированном бюджете с меньшей вероятностью успеет его найти.

Расширим диапазон:

Теперь поиск обычно занимает намного больше времени — возможно, больше, чем хотелось бы ждать для столь простой функции. Как же такой подход справится с реальными программами, где параметров и соседей ещё больше?

Тестирование более сложной программы

Перейдём к чуть более сложной программе — знакомому по главе о покрытии декодеру CGI:

Декодер CGI как задача поиска

cgi_decode() принимает одну строку. Окрестность строки можно определить как все строки с редакционным расстоянием 1. Например, при замене каждого символа test на предыдущий или следующий символ получаются:

• uest, sest;

• tfst, tdst;

• tett, tert;

• tesu, tess.

Добавление любого символа в начало или конец тоже даёт расстояние 1. Ради простоты зафиксируем разумную длину входов, например 10 символов. Тогда у каждого входа будет 20 соседей — по два на символ.

Функция берёт числовое значение каждого символа и создаёт строки с предыдущим и следующим печатным символом ASCII из диапазона 32–126.

Пространство поиска для cgi_decode() определено. Теперь нужна функция приспособленности.

Расстояния до ветвей

В test_me() было одно условие, сравнивавшее целые числа. В cgi_decode() есть три условных конструкции и цикл, сравнивающие символы. Символы можно рассматривать как числа и применять прежнюю оценку расстояния.

Но два условия проверяют принадлежность множеству: например, digit_high in hex_values. Естественная оценка близости к множеству — расстояние до ближайшего его элемента:

До сих пор предполагалось, что условие должно стать истинным. Но часто требуется и ложный исход. Поэтому у каждого условия две оценки: расстояние до истины и расстояние до лжи. Если условие истинно, первое равно 0; если ложно, второе равно 0.

Например, для a == b при разных значениях расстояние до лжи по определению равно 0. Если же a равно b, любое изменение одного операнда сделает условие ложным, поэтому расстояние можно положить равным 1.

Правила для распространённых сравнений:

В таблице выражения применяются тогда, когда соответствующий исход ещё не достигнут; расстояние достигнутого исхода равно 0. Положительная константа нужна для строгих границ. Например, при a = b = 27 условие a < b ложно, а простая разность дала бы 0. Подойдёт любая положительная константа, не обязательно 1.

Сложные условия

В cgi_decode() есть составной предикат:

В принципе, расстояние до истинности конъюнкции A and B равно сумме расстояний для A и B, поскольку истинными должны стать оба условия. Для A or B достаточно минимума двух расстояний: истинным должен стать хотя бы один операнд.

На практике всё сложнее. Предикаты могут содержать вложенные условия и отрицания, так что выражение пришлось бы приводить к канонической форме. Кроме того, современные языки используют сокращённое вычисление: если в A or B выражение A истинно, B не вычисляется. Принудительное вычисление B ради расстояния способно вызвать побочный эффект и изменить поведение программы, что недопустимо.

Побочные эффекты возможны и в самом условии. Пусть оно выглядит как x == 2 * foo(y). Наивная инструментация дала бы:

foo() выполнится дважды. Если она печатает данные, работает с файловой системой или меняет состояние, это нарушит семантику. Один из вариантов — преобразовать условие и сохранить операнды во временных переменных:

Ручная глобальная переменная и отдельная обработка каждой ветви всё равно неудобны, особенно в функции с несколькими условиями. Нужна автоматическая инструментация.

Инструментация атомарных условий

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

• num — уникальный идентификатор условия;

• op — оператор сравнения;

• lhs и rhs — операнды.

Она вычисляет расстояния до истины и лжи. Один из исходов всегда достигнут и имеет расстояние 0. Поскольку функция заменяет исходное сравнение, она возвращает соответствующее логическое значение.

Исходное условие

превратится в

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

Оба расстояния инициализируются нулём. Поэтому при равных операндах distance_true остаётся равным 0, а при разных — нулевым остаётся distance_false.

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

condition_num однозначно определяет условие. При первом выполнении оба расстояния просто сохраняются. Однако одно условие может выполняться много раз: например, i < len(s) проверяется перед каждой итерацией цикла. Для теста нужна одна итоговая оценка. Чтобы покрыть ветвь, достаточно приблизиться к ней хотя бы в одном выполнении, поэтому сохраняется минимальное наблюдавшееся расстояние.

Добавим вычисления для in и <, нужных декодеру CGI, и преобразование символов в числа с помощью ord():

Составное условие декодера после инструментации выглядит так:

Два вызова соответствуют двум атомарным условиям, а исходный and сохраняет сокращённое вычисление. Осталось научиться получать такую версию автоматически.

Автоматическая инструментация исходного кода

В Python сравнения нетрудно заменять автоматически с помощью абстрактного синтаксического дерева (AST). Сравнение обычно представлено узлом с оператором и дочерними узлами левого и правого операндов. Чтобы заменить его вызовом evaluate_condition(), достаточно подставить вместо узла сравнения узел вызова функции. Именно это делает BranchTransformer на основе ast.NodeTransformer:

Встроенный ast.parse() строит AST, а API Python позволяет обходить и менять его. NodeTransformer реализует шаблон «Посетитель»: для каждого типа узла существует метод visit_*. Мы переопределяем visit_Compare и возвращаем вместо сравнения новый ast.Call с четырьмя ожидаемыми аргументами:

• номер ветви, счётчик которого хранится в branch_num;

• оператор — имя его класса;

• левый операнд;

• правый операнд.

Python разрешает цепочки сравнений вроде 1 < x < 10. Ради простоты здесь обрабатывается лишь одиночное сравнение, но код можно расширить, создав отдельный вызов для каждой пары. visit_FunctionDef добавляет к имени _instrumented, чтобы исходная и инструментированная функции могли существовать одновременно.

Разберём исходник cgi_decode() в AST, преобразуем и снова напечатаем:

Существенная часть результата выглядит так:

Для вычисления приспособленности преобразованное AST нужно снова скомпилировать функцией compile(). Затем полученный код добавляется в пространство имён текущего модуля через exec(), после чего становится доступна cgi_decode_instrumented().

Проверим эквивалентность исходной и преобразованной функций:

Условия 1 и 2 принимали оба логических значения, а условие 3 — только ложное. Это ожидаемо: цикл был открыт и завершён, во входе встретился пробел +, но не было символа %.

Функция приспособленности для допустимых шестнадцатеричных входов

Поставим цель проверить часть cgi_decode(), которая декодирует допустимые шестнадцатеричные коды. Для этого условия 1, 3, 4 и 5 должны стать истинными, а условие 2 — ложным. Приспособленность можно получить суммой расстояний до этих ветвей.

Однако простая сумма создаёт перекос: если одно условие сравнивает огромные числа, а другое — маленькие, улучшение первого почти всегда сильнее влияет на итог. Поэтому перед сложением расстояния следует нормализовать.

Нормализация в диапазон [a, b] должна сохранять порядок: если x < y, то и normalize(x) < normalize(y). Простая функция

Формула: normalize(x)=(x)/(x+k)

дешёва и отображает положительные числа в [0, 1]. Множитель позволил бы получить [0, b]. Параметр k задаёт крутизну; значение 1 — разумное по умолчанию, при котором кривая быстро приближается к 1, но никогда его не достигает.

Построим график исходных и нормализованных значений:

Не каждое условие выполняется каждым тестом. Расстояние для невыполненной ветви должно быть больше любого наблюдавшегося. После нормализации верхняя граница известна — это 1. Поэтому функция приспособленности выглядит так:

Посмотрим, как оценка уменьшается по мере приближения к цели:

Поиск допустимого шестнадцатеричного входа подъёмом на холм

Пространство поиска определено neighbor_strings(), а оценка — get_fitness_cgi(). Осталось получить случайную начальную точку, как в главе о мутационном фаззинге:

Объединим компоненты. Алгоритм почти не меняется: он создаёт строки вместо чисел и использует новую оценку.

Запустите алгоритм несколько раз. Иногда ему требуется лишь несколько шагов, иногда больше, но в конце он всегда создаёт строку с допустимой парой шестнадцатеричных символов.

Эволюционный поиск

Подъём на холм хорошо работает при сравнительно небольшой окрестности. В примере cgi_decode() этому помогли фиксированная длина 10 и печатный ASCII. Но что будет с 16-битными символами Unicode? Для URL они не подходят, однако такое расширение наглядно показывает проблему:

UTF-16 даёт 65 536 возможных значений. Добавим предел итераций, чтобы поиск мог отказаться от задачи, а не работать вечно:

Типичный запуск остаётся около приспособленности 3 даже после ста шагов. Можно менять предел и наблюдать время поиска; без очень удачной начальной точки решение обычно требует неприемлемо долгого ожидания.

Глобальный поиск

Подъём на холм исследует локальную окрестность. Когда она огромна, это слишком дорого. Альтернатива — глобальный поиск с более крупными шагами. Простое изменение превращает подъём на холм в глобальный алгоритм: вместо перебора непосредственных соседей особь подвергается мутации.

Мутация должна теоретически позволять последовательными применениями достичь любой точки пространства, но не должна каждый раз полностью заменять особь случайной. Для эффективности большая часть признаков сохраняется. В строке из десяти символов можно заменить один символ:

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

Обычно он находит решение быстрее обычного подъёма, хотя всё ещё довольно медленно.

Есть тонкое, но важное отличие: используется new_fitness <= fitness, а не строгое <. В ландшафте могут быть плато одинаковой приспособленности. Обычный алгоритм преодолевал их перезапусками. Если рандомизированный вариант отвергал бы равных потомков, он снова и снова мутировал бы одну особь. Принимая равных, поиск перемещается по плато и повышает шанс выбраться.

Рандомизированный подъём известен также как эволюционный алгоритм 1+1, или (1+1)EA. Эволюционные алгоритмы имитируют естественную эволюцию: давление среды создаёт отбор, выживают наиболее приспособленные, и качество популяции постепенно растёт. В (1+1)EA популяция состоит из одной особи, порождающей одного потомка. На практике гораздо распространённее генетический алгоритм.

Генетические алгоритмы

Генетический алгоритм (ГА) исходит из того, что решение можно закодировать генетически. Хромосома — последовательность генов, каждый из которых задаёт один признак. Описание представляет генотип, а полученное решение — фенотип. Функция приспособленности оценивает фенотип.

Для cgi_decode() генами могут быть отдельные символы, а хромосомой — их последовательность. Это уже знакомое представление, но ГА требует других операций, чем перечисление соседей.

Алгоритм имитирует эволюцию:

1. Создать начальную популяцию случайных хромосом.

2. Отобрать приспособленные особи для размножения.

3. Получить новую популяцию размножением выбранных особей.

4. Повторять до оптимального решения или исчерпания бюджета.

Начальную популяцию создать просто:

Отбор предпочитает более приспособленных, поэтому оценим всю популяцию и сохраним пары «особь, приспособленность»:

Отбор часто объясняют «выживанием наиболее приспособленных», но Дарвин подчёркивал и половой отбор. На выбор партнёра влияет конкуренция и демонстрация качеств — например, хвост павлина сигнализирует о здоровье. В ГА лучшая приспособленность повышает вероятность размножения.

Простой способ — турнирный отбор: несколько случайных особей соревнуются, и выбирается лучшая.

tournament_size определяет давление отбора. В большом турнире чаще присутствует очень хорошая особь; она может быстро захватить следующее поколение, уменьшить разнообразие и вызвать преждевременную сходимость. Слишком маленький турнир, напротив, тормозит эволюцию. Значение зависит от размера популяции, но обычно невелико, например 5.

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

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

Скрещивание и мутация вероятностны. Для последовательности можно мутировать каждый ген с вероятностью 1/n, чтобы в среднем менялся один. Новый символ берётся не равновероятно из всего диапазона, а из нормального распределения со средним в текущем значении. Произвольно выбранное стандартное отклонение 100 делает малые изменения вероятнее больших.

Теперь соберём полный алгоритм:

Один из прогонов начинает с оценки около 2,99, на третьем поколении находит %, затем приближается к допустимым цифрам и завершает строкой вроде '予ß쥇᳗轐咆隭%2A' с приспособленностью 0.

Итоговое краткое содержание

Глава показала, как метаэвристические алгоритмы находят входы, достигающие заданных позиций исходного кода. Простейший метод — hillclimber(). В зависимости от ландшафта применяются варианты steepest_ascent_hillclimber() и restarting_hillclimber().

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

Оценка получается запуском инструментированной версии:

Для сложных функций пространство поиска становится намного больше, и его исследуют эволюционными методами, например genetic_algorithm().

Усвоенные уроки

• Задача метаэвристического поиска состоит из алгоритма, представления и функции приспособленности.

• В генерации тестов функция приспособленности обычно оценивает, насколько близко выполнение подошло к целевой позиции. Расстояние вычисляется во время запуска посредством инструментации.

• Локальные методы вроде подъёма на холм хорошо работают, если окрестность определена и не слишком велика.

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

Что дальше

Здесь рассматривались сравнительно простые входы. Те же алгоритмы можно применять для эволюции сложных тестовых данных, в частности входов, описанных грамматикой.

Дополнительные материалы

Цели поиска обычно связаны с покрытием. Дополнительные источники перечислены во введении в тестирование.

Упражнения

Будут добавлены позднее.

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

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

Предварительные знания

• Нужно понимать основы выполнения программ.

• Следует прочитать главу о покрытии.

Краткое содержание

Глава вводит два способа мутационного анализа. MuFunctionAnalyzer работает с отдельными функциями. Для функции gcd и двух тестов анализ запускается так:

Из семи мутантов тесты обнаруживают три, поэтому оценка равна:

MuProgramAnalyzer предназначен для самостоятельных программ с наборами тестов. Пусть исходный код gcd хранится в gcd_src, а тесты — в TestGCD:

В показанном прогоне тесты уничтожают всех мутантов, и оценка равна 1. Мутационная оценка лучше чистого покрытия отражает качество тестового набора.

Почему структурного покрытия недостаточно

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

Рассмотрим такой «тест»:

Последнее утверждение проходит независимо от поведения execute_the_program_as_a_whole(). Исключение всё же уронит тест, но можно обойти и это:

Такие «тесты» способны достичь 100%-го покрытия кода или любой другой структурной метрики, но их способность обнаруживать ошибки равна нулю.

Как убедиться, что тесты действительно полезны? Можно внедрять ошибки и оценивать, поймает ли их набор. Но возникает вопрос: откуда брать ошибки? Ручной выбор будет смещён представлениями разработчика о вероятных местах и эффектах дефектов, а создание качественных дефектов требует много времени ради косвенной выгоды.

Внедрение искусственных дефектов с помощью мутационного анализа

Мутационный анализ предлагает систематическую альтернативу: в программу внедряются искусственные дефекты, или мутации, и проверяется, обнаружит ли их набор тестов. Например, где-нибудь в execute_the_program_as_a_whole() оператор + можно заменить на -. Приведённые выше неэффективные тесты этого не заметят, поскольку не проверяют результаты. Эффективный тест заметит; считается, что чем лучше тест обнаруживает искусственные дефекты, тем лучше он обнаруживает реальные.

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

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

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

Достаточность структурного покрытия на примере

Рассмотрим более подробный пример. Функция triangle() классифицирует треугольник со сторонами a, b и c; требуется проверить её правильность.

Вот несколько тестов:

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

Добавим визуализацию выполненных строк:

strong_oracle() охватывает все возможные условия и выглядит достаточно хорошим по структурному покрытию. Но рассказывает ли покрытие всю историю? Рассмотрим другой набор:

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

Результат строка в строку совпадает с покрытием strong_oracle(). Однако очевидно, что слабый оракул менее эффективен. Покрытие не различает эти наборы, потому что не оценивает качество утверждений — более того, утверждения вообще его не интересуют. А именно они являются важнейшей частью эффективности тестов. Значит, нужен способ оценивать их качество.

Внедрение искусственных дефектов

Покрытие выступает лишь косвенным показателем вероятности обнаружения ошибок. Можно попробовать измерить эту вероятность непосредственно: внедрять ошибки по одной и считать, сколько из них обнаруживает тестовый набор. Частота обнаружения и будет оценкой. Такая техника называется внедрением дефектов.

Создадим вариант triangle() с искусственной ошибкой:

Проверим слабый оракул:

Он не замечает изменения. Сильный оракул обнаруживает его:

Это свидетельство того, что strong_oracle() — лучший набор тестов.

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

Мутационный анализ предлагает альтернативу curated-набору. Если программист понимает программу, большинство его ошибок, вероятно, является небольшими ошибками переписывания — изменением нескольких токенов. Компилятор обнаружит многие из них, а большинство оставшихся дефектов будет представлять небольшое, часто однотокенное, отклонение от правильной программы. Это называется гипотезой компетентного программиста, или гипотезой конечной окрестности.

А как быть с крупными дефектами, состоящими из нескольких малых? Для большинства из них тест, обнаруживающий отдельный малый дефект, скорее всего обнаружит и содержащий его сложный дефект. Это предположение называется эффектом сцепления.

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

Далее реализуем простой каркас мутационного анализа и применим его к нашим наборам тестов.

Мутация кода Python

Для преобразования программы Python будем работать с её абстрактным синтаксическим деревом (AST) — внутренним представлением, которое компилятор и интерпретатор используют после чтения текста.

Программа превращается в дерево, затем части дерева изменяются: например, + заменяется на - и наоборот, а настоящий оператор — на ничего не делающий pass. Полученное дерево можно передать интерпретатору либо преобразовать обратно в текст.

Сначала импортируем средства работы с AST:

Исходный текст функции можно получить через inspect.getsource(); для функций из других ноутбуков это не работает.

Для удобного форматирования print_content(s, suffix) подсвечивает строку s, как содержимое файла с расширением suffix:

Разбор текста создаёт абстрактное синтаксическое дерево:

Структуру можно исследовать текстовой функцией ast.dump() или графически с помощью showast. Корень — Module, содержащий FunctionDef с именем и аргументами. Тело функции — список операторов; здесь оно начинается с If, внутри которого находятся другие узлы If, Compare, Name, Constant и Return.

Начало дампа:

Графическое представление воспроизводится так:

Функция ast.unparse() превращает дерево обратно в привычный исходный код Python:

Результат семантически совпадает с triangle(), хотя unparse() может упростить вложенные конструкции else: if до elif и нормализовать кавычки и пробелы.

Простой мутатор функций

Теперь изменим программу triangle(). Простой способ получить допустимый вариант — заменить один из её операторов на pass.

MuFunctionAnalyzer — основной класс мутационного анализа тестового набора для отдельной функции. Он принимает тестируемую функцию и нормализует её код, один раз разбирая и снова выводя AST. Это нужно, чтобы будущие различия между оригиналом и мутантом не искажались пробелами, комментариями и форматированием.

get_mutation_count() получает число возможных мутаций:

Mutator — базовый класс отдельных преобразований. Он принимает номер изменяемой позиции. Подкласс вызывает mutable_visit() для интересующих узлов. Без конкретной позиции метод лишь обходит все точки мутации и считает их в self.count; с указанной позицией вызывает mutation_visit(), который меняет узел. Одна позиция в более сложных мутационных операторах может порождать несколько вариантов.

StmtDeletionMutator подключается ко всем посетителям операторов:

Сама мутация заменяет оператор на pass:

Для triangle() получаются пять мутаций — по одной для каждого return:

Чтобы получать мутантов по одному, сделаем анализатор итерируемым:

Итератор хранит анализатор и текущий индекс:

__next__() возвращает соответствующий Mutant, регистрирует его и завершает обход после всех позиций:

Класс Mutant хранит сведения, необходимые для генерации и оценки одного варианта:

generate_mutant() создаёт новый мутатор для нужной позиции и передаёт ему копию AST, полученную повторным разбором нормализованного исходника:

src() лениво вычисляет и кэширует мутированный текст:

Различия с оригиналом можно показать через difflib:

Каждый из пяти вариантов заменяет очередной return на pass. Например:

Добавим вывод различий непосредственно в Mutant:

Оценка мутаций

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

Пока mutant активен — внутри блока with — исходная функция заменяется мутированной.

__enter__() вызывается при входе в блок. Он компилирует мутанта как функцию Python и помещает её в глобальное пространство имён, поэтому утверждения вызывают изменённую версию:

__exit__() проверяет, возникло ли исключение — упало утверждение или произошла другая ошибка. В таком случае мутация помечается обнаруженной. Затем исходная функция восстанавливается:

После обхода finish() собирает необнаруженных мутантов:

Мутационная оценка — доля обнаруженных мутантов. Значение 1 означает, что уничтожены все; 0,1 — только 10%.

Испытаем слабый набор напрямую:

Только одна из пяти мутаций вызывает падение утверждения:

Тот же результат получается через ранее определённый оракул:

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

Сильный оракул обнаруживает все пять вариантов:

Рассмотрим ещё один пример. gcd() вычисляет наибольший общий делитель двух чисел:

Насколько эффективны два простых теста?

Из семи мутантов обнаруживаются три: один по UnboundLocalError, два по утверждениям.

Таким образом, этот набор для gcd() получает около 42%.

Мутатор модулей и наборов тестов

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

Для демонстрации создадим настоящий объект модуля из строки с исходным кодом:

Сильный набор тестов проверяет точное значение каждого результата:

Вспомогательная функция собирает все методы, имена которых начинаются с test_:

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

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

Анализатор программы

MuProgramAnalyzer разбирает исходный текст модуля, нормализует его через AST, находит все точки изменения и запоминает нераспознанные мутанты:

Расширенный посетитель либо регистрирует изменяемые позиции, либо применяет изменения в переданных позициях:

Для triangle() анализатор находит пять мутаций:

Перебор мутантов программы

Сделаем анализатор итерируемым:

AdvMutant хранит набор позиций, по которому строится конкретный вариант программы:

Имена пяти мутантов имеют вид shape_(1, 0), …, shape_(5, 0).

Генератор передаёт копию AST мутатору с выбранными позициями, а src() кэширует полученный текст:

Как и раньше, разницу с исходной программой удобно показывать в едином формате diff:

Например, первый мутант заменяет return 'Equilateral' на pass.

Запуск тестов на мутантах

Оператор индексирования принимает модуль тестов, заменяет в его пространстве имён исходный модуль мутантным и возвращает исполнитель тестов:

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

Оценка программы определяется той же долей убитых мутантов:

Применим фреймворк к слабому набору:

Слабый набор получает лишь 20%: из пяти мутантов он убивает один.

Сильный набор убивает все варианты:

Таким образом, StrongShapeTest получает 100%. Аналогично можно оформить тесты gcd() как класс:

Результат совпадает с анализом отдельной функции: набор TestGCD получает около 42%.

Проблема эквивалентных мутантов

Не всякий автоматически созданный мутант обязательно ошибочен. Рассмотрим другую запись алгоритма Евклида:

Один из мутантов удаляет присваивание в ветви else:

Мутатор удаления операторов порождает четыре варианта: удаление присваивания в ветви if, присваивания в else, тела цикла или итогового return. Второй вариант семантически неотличим от оригинала, потому что удалённое присваивание a, b = a, b ничего не меняет. Такие варианты называются эквивалентными мутантами.

Эквивалентные мутанты затрудняют интерпретацию оценки. Если она равна 70%, то эквивалентными могут быть от 0 до 30% всех мутантов. Не зная их настоящего числа, невозможно понять, насколько ещё можно улучшить тесты. Рассмотрим два способа работы с этой проблемой.

Статистическая оценка числа эквивалентных мутантов

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

Формула: n ≥ p_hat(1-p_hat) ((Z_((α)/(2)))/(Δ))^2,

где n — число образцов, p — параметр вероятностного распределения, α — желаемая достоверность, а Δ — точность. Для доверительного уровня 95% критическое значение равно 1,96. Поскольку максимум p_hat(1-p_hat) равен 0,25, получаем

Формула: n ≥ 0.25((1.96)/(Δ))^2.

При Δ=0.01, то есть максимальной ошибке 1%, на эквивалентность потребуется проверить 9604 мутанта. Если допустить ошибку 10% (Δ=0.1), достаточно 96 мутантов.

Оценка числа бессмертных мутантов методом Чао

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

Формула: S_hat_Chao1 = S(n) + (f_1^2)/(2f_2), если f_2>0; S(n) + (f_1(f_1-1))/(2), иначе.

Основная идея — вычислить полную матрицу T × M: запустить каждый тест на каждом мутанте. Здесь f_1 — число мутантов, убитых ровно один раз, f_2 — число мутантов, убитых ровно дважды, а S(n) — общее число убитых мутантов. Значение S_hat_Chao1 оценивает истинное число обнаружимых мутантов. Если всего создано M вариантов, то M-S_hat_Chao1 оценивает число бессмертных мутантов.

Бессмертный мутант не вполне то же самое, что традиционный эквивалентный мутант: его «смертность» зависит от оракула, различающего поведение вариантов. Например, фаззер, считающий мутанта убитым лишь при исключении, не заметит иной результат без исключения. Поэтому оценка Chao1 — это асимптотическое число мутантов, которое данный фаззер мог бы обнаружить за бесконечное время. При достаточно сильном оракуле оценка бессмертных мутантов приближается к числу истинно эквивалентных. Подробнее это обсуждается в главе о завершении фаззинга; полный разбор обнаружения «видов» в тестировании дан в работе Бёме [Boehme et al., 2018].

Итоги

В этой главе представлены два способа анализа мутаций.

MuFunctionAnalyzer предназначен для отдельных функций. Например, качество двух тестов gcd() вычисляется так:

MuProgramAnalyzer предназначен для самостоятельных программ с тестовыми наборами:

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

Усвоенные уроки

• Структурного покрытия недостаточно для оценки качества тестовых наборов.

• Анализ мутаций позволяет оценивать силу тестов и их оракулов.

• Метод ограничивают эквивалентные и избыточные мутанты; их число можно оценивать статистически.

Дальнейшие шаги

• Наивный фаззинг создаёт слабые оракулы; символическое и конколическое выполнение способны их усилить.

• Динамические инварианты также помогают улучшать оракулы.

• В главе о том, когда прекращать фаззинг, оценка Чао рассматривается подробнее.

История вопроса

Идею анализа мутаций впервые предложили Липтон и соавторы [Lipton et al., 1971]. Прекрасный обзор исследований опубликовали Цзя и Харман [Jia and Harman, 2011]. Ещё один обстоятельный обзор современных направлений дан в главе Пападакиса и соавторов [Papadakis et al., 2019].

Упражнения Упражнение 1. Мутаторы арифметических выражений

Удаление операторов — лишь один способ изменять программу. Другая категория — мутации выражений, при которых арифметические операторы {+, -, *, /} заменяются друг другом. Например,

можно превратить в x = x - 1, x = x * 1 или x = x / 1.

Сначала выясним тип нужных узлов AST:

Двоичные операции представлены узлами BinOp; для мутации нужно менять их атрибут op, имеющий, в частности, значения Add, Sub, Mult и Div. Напишите BinOpMutator, а затем производный от MuFunctionAnalyzer класс MuBinOpAnalyzer, который его использует.

Решение. Как и в StmtDeletionMutator, посетим все подходящие узлы AST:

Проверим мутатор на функции:

Он по очереди заменяет внешнее вычитание на сложение, сложение на вычитание, деление на умножение и умножение на деление.

Упражнение 2. Оптимизация анализа мутаций

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

Решение. Оставлено внимательному читателю.

Упражнение 3. Мутатор байт-кода

Мы изменяли AST, полученное из исходного текста. Однако байт-код Python может быть целевым форматом и для других языков, исходный текст которых нельзя непосредственно преобразовать в Python AST. Реализуйте мутатор функции Python, который изменяет байт-код вместо получения и изменения исходного текста.

Решение. Оставлено внимательному читателю.

Упражнение 4. Оценка остаточной плотности дефектов

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

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

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

Решение. Оставлено внимательному читателю.

В этой части рассматривается генерация тестов на синтаксическом уровне — составление входных данных из конструкций языка.

В главе о фаззинге на основе мутаций мы увидели, как дополнительные подсказки — например, образцы входных файлов — ускоряют генерацию тестов. Теперь сделаем следующий шаг и зададим спецификацию допустимых входов программы. Грамматика позволяет систематически и эффективно создавать тесты для сложных форматов. Кроме того, грамматики служат основой фаззинга конфигураций, API, графических интерфейсов и многих других областей.

Предварительные знания

• Нужно понимать основы фаззинга, изложенные во вводной главе.

Краткое содержание

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

Нетерминалы заключаются в угловые скобки, например <digit>. Генератор начинает со стартового символа <start>, случайно выбирает одно из его раскрытий и продолжает, пока не раскроет все нетерминалы. Именно так работает simple_grammar_fuzzer():

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

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

Языки входных данных

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

Для простоты пока предположим, что у программы есть только один источник входа, как и в предыдущих главах. Множество допустимых входов называется языком. Языки бывают простыми и сложными: язык CSV задаёт корректные записи с разделителями-запятыми, а язык Python — корректные программы на Python. Обычно различают языки данных и языки программирования, хотя программу тоже можно рассматривать как входные данные, например для компилятора. Существуют тысячи форматов файлов, каждый со своим языком.

Теория формальных языков предлагает спецификации для строгого описания языков. Простейший класс строковых языков задают регулярные выражения: например, [a-z]* обозначает, возможно пустую, последовательность строчных букв. Теория автоматов связывает такие языки с распознающими их автоматами; язык регулярного выражения можно задать конечным автоматом.

Регулярные выражения удобны для не слишком сложных форматов, а конечные автоматы обладают полезными для рассуждений свойствами. Однако при описании сложных входов быстро проявляются ограничения. На противоположном конце спектра находятся универсальные грамматики, задающие языки машин Тьюринга. Машина Тьюринга может вычислить всё вычислимое; поскольку Python полон по Тьюрингу, программу на Python также можно использовать для задания или даже перечисления допустимых входов. Но такую тестирующую программу пришлось бы писать специально для каждой проверяемой системы, а это не тот уровень автоматизации, к которому мы стремимся.

Грамматики

Промежуточное положение между регулярными выражениями и машинами Тьюринга занимают грамматики — один из самых популярных и хорошо изученных формализмов спецификации языков входных данных. Грамматика выражает широкий круг свойств языка и особенно хорошо описывает синтаксическую структуру, вложенные и рекурсивные входы. Здесь используются контекстно-свободные грамматики, один из самых простых и распространённых видов грамматик.

Правила и раскрытия

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

Чтение начинается со стартового символа <start>. Правило <A> ::= <B> означает, что символ слева можно заменить строкой справа. Поэтому <start> заменяется на <digit><digit>. Затем каждый <digit> заменяется правой частью соответствующего правила. Знак | разделяет альтернативы раскрытия: можно выбрать любую цифру. В итоге получаем строку от 00 до 99; терминалы 0–9 дальнейшего раскрытия не требуют.

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

Здесь <integer> — либо одна цифра, либо цифра, за которой следует ещё одно целое число. Число 1234 представляется цифрой 1 и целым 234, которое, в свою очередь, состоит из цифры 2 и целого 34.

Чтобы разрешить знак + или -, добавим правило:

Эти правила формально определяют язык: всё, что выводится из стартового символа, принадлежит языку; всё остальное — нет. Интерактивные опросы из оригинала здесь и далее опущены.

Арифметические выражения

Расширим грамматику до полных арифметических выражений — классического примера применения грамматик. Выражение <expr> является суммой, разностью или термом; терм — произведением, частным или множителем; множитель — числом либо выражением в скобках. Почти все правила рекурсивны и потому допускают выражения произвольной сложности, например (1 + 2) * (3.4 / 5.6 - 789).

Обратите внимание: пробелы вокруг операторов входят в язык буквально. Поэтому 1 + 1 выводится из этой грамматики, а 1+1 — нет.

Представление грамматик в Python

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

Экскурс: тип Grammar

Определим тип грамматик, чтобы их можно было статически проверять. В первом приближении каждый символ-строка отображается в список строк-раскрытий:

Однако функция opts(), представленная далее в главе, позволяет снабжать раскрытия необязательными атрибутами. В таком случае раскрытие может быть парой из строки и словаря параметров:

Итоговый тип Grammar отображает строки в списки Expansion:

Конец экскурса

Полная грамматика арифметических выражений в этом представлении имеет вид:

Каждый символ определяется в грамматике ровно один раз. Правило доступно по имени символа:

Можно также проверить наличие символа:

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

Некоторые определения

Каноническим стартовым символом считаем <start>:

Функция nonterminals() извлекает из раскрытия список нетерминалов — всё, что заключено между < и >, кроме пробелов:

Проверим разные случаи:

А is_nonterminal() проверяет, является ли строка нетерминалом:

Простой грамматический фаззер

Применим созданные грамматики. Построим простой фаззер, который начинает со <start> и последовательно раскрывает символы. Чтобы результат не рос бесконечно, ограничим число остающихся нетерминалов параметром max_nonterminals. Чтобы алгоритм не застрял, когда это число невозможно уменьшить, ограничим также общее число неудачных попыток раскрытия.

Посмотрим, как фаззер получает арифметическое выражение из стартового символа:

Один из запусков последовательно превращает <start> в <expr>, раскрывает термы, множители и цифры и завершается строкой:

Увеличение предела нетерминалов быстро приводит к гораздо более длинным результатам:

Примеры созданных выражений:

Функция simple_grammar_fuzzer() выполняет задачу в большинстве случаев, но имеет недостатки. Многочисленные операции поиска и замены строк делают её неэффективной; кроме того, она может так и не получить строку и завершиться ExpansionError. Зато реализация проста и подходит для этой главы. В следующей главе будет построен более эффективный фаззер.

Визуализация грамматик в виде синтаксических диаграмм

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

Синтаксические диаграммы, также называемые железнодорожными, — графическое представление контекстно-свободных грамматик. Их читают слева направо вдоль возможных «путей»; последовательность встреченных на пути символов задаёт язык. Для создания таких диаграмм реализуем syntax_diagram().

Экскурс: реализация syntax_diagram()

Для визуализации используем внешнюю библиотеку RailroadDiagrams:

Сначала определим syntax_diagram_symbol(), визуализирующую один символ. Терминалы обозначаются овалами, а нетерминалы наподобие <term> — прямоугольниками:

Например, следующий вызов отображает прямоугольный узел term:

Функция syntax_diagram_expr() визуализирует одну альтернативу раскрытия. Она разделяет строку на терминальные и нетерминальные фрагменты и соединяет их последовательностью. Пустое раскрытие обрабатывается отдельно.

Так визуализируется первая альтернатива <term> — множитель <factor>, за которым следуют * и ещё один <term>:

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

Вызов для правила <digit> показывает, что цифрой может быть любой единственный символ от 0 до 9:

Наконец, syntax_diagram() проходит по всем правилам грамматики и выводит их диаграммы:

Конец экскурса

Построим диаграммы грамматики выражений:

Будут показаны отдельные схемы правил start, expr, term, factor, integer и digit. Такое представление удобно для понимания структуры, особенно у более сложных грамматик. Машинно созданный SVG из вывода блокнота не включён: он полностью воспроизводится приведённым кодом.

Примеры грамматик

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

Грамматика CGI

Ниже приведена грамматика входов для cgi_decode() из главы о покрытии:

Её структуру можно вывести уже знакомой функцией:

В отличие от базового фаззинга и фаззинга на основе мутаций, грамматика быстро создаёт всевозможные допустимые сочетания:

Грамматика URL

Свойства, показанные на CGI-входах, сохраняются и для более сложных данных. Используем грамматику для создания множества корректных URL.

Диаграмма показывает правила для схемы, полномочий, узла, порта, данных пользователя, пути и параметров запроса:

И снова за миллисекунды можно получить множество корректных входов:

Грамматика естественного языка

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

Сгенерируем множество из десяти разных названий:

Здесь встречаются повторы вроде «Robustness and Robustness». В главе о фаззинге на основе покрытия грамматики будет показано, как раскрывать каждую альтернативу лишь однажды. Если же одни альтернативы предпочтительнее других, их выбором можно управлять с помощью вероятностного грамматического фаззинга.

Грамматики как источники мутаций

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

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

Один выход — прикреплять к грамматикам ограничения, что будет рассмотрено далее в книге. Другой — объединить сильные стороны грамматического фаззинга и фаззинга на основе мутаций: использовать сгенерированные грамматикой входы как начальные образцы для последующих мутаций. Тогда исследуются не только допустимые входы, но и границы между допустимым и недопустимым. Слегка повреждённые входы особенно полезны для поиска многочисленных ошибок синтаксических анализаторов. Как и в фаззинге вообще, ошибки выявляет неожиданное.

Передадим сгенерированные входы ранее созданному мутационному фаззеру:

Пример набора начальных URL:

Первые десять вызовов fuzz() возвращают начальные входы, как и предусмотрено, а следующие создают произвольные мутации, например:

Если вместо MutationFuzzer использовать MutationCoverageFuzzer, поиск снова будет направляться покрытием. Так можно совместить преимущества нескольких подходов.

Набор инструментов для грамматик

Рассмотрим несколько приёмов, упрощающих написание грамматик.

Экранирование

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

В simple_nonterminal_grammar ни раскрытие <left-angle>, ни раскрытие <right-angle> нельзя принять за нетерминал, поэтому эти знаки можно создавать в любом количестве. Этот приём не работает с simple_grammar_fuzzer(), но работает с классом GrammarFuzzer из следующей главы.

Расширение грамматик

На протяжении книги часто понадобится создавать грамматику путём расширения уже существующей новыми возможностями. Эта операция напоминает наследование в объектно-ориентированном программировании.

Чтобы получить g' из g, сначала скопируем g, а затем добавим альтернативы к существующим правилам или введём новые символы. Например, улучшим правило идентификатора в предыдущей грамматике:

Получается такая структура:

Поскольку расширение используется часто, введём функцию extend_grammar(): она копирует грамматику и обновляет её методом словаря update().

Тот же результат теперь записывается компактнее:

Классы символов

В nonterminal_grammar перечислены лишь первые несколько букв. Записывать вручную все буквы или цифры в форме <idchar> ::= 'a' | 'b' | 'c' ... утомительно. Но грамматика является частью программы, поэтому её можно строить программно. Функция srange() превращает строку в список составляющих её символов:

Константа string.ascii_letters содержит все латинские буквы ASCII:

С помощью таких констант быстро задаются идентификаторы:

Сокращение crange(start, end) возвращает все символы диапазона ASCII от start до end включительно:

Сокращения грамматик

В nonterminal_grammar, как и в других грамматиках, повторение символов выражалось рекурсией:

Было бы проще прямо указать, что нетерминал является непустой последовательностью символов:

Здесь + обозначает одно или несколько повторений предшествующего символа. Такие операторы часто вводят как удобные сокращения. Формально наши грамматики записаны в форме Бэкуса — Наура (BNF). Дополнительные операторы образуют расширенную форму Бэкуса — Наура (EBNF):

• <symbol>? означает, что <symbol> необязателен и встречается ноль или один раз;

• <symbol>+ означает одно или несколько повторений;

• <symbol>* означает ноль или несколько повторений, то есть необязательное повторение.

Сокращения можно применять и к группам в скобках. Например, (<foo><bar>)? означает необязательную последовательность <foo> и <bar>.

Упростим правило идентификатора в копии исходной грамматики:

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

Реализуем convert_ebnf_grammar(), автоматически переводящую такую EBNF-грамматику в BNF.

Экскурс: реализация convert_ebnf_grammar()

Наша цель — преобразовать EBNF-грамматику в обычную BNF. Для этого применяются четыре правила:

1. Выражение (content)op, где op — один из операторов ?, + или *, заменяется на <new-symbol>op, а также добавляется правило <new-symbol> ::= content.

2. <symbol>? заменяется на <new-symbol> с правилом <new-symbol> ::= <empty> | <symbol>.

3. <symbol>+ заменяется на <new-symbol> с правилом <new-symbol> ::= <symbol> | <symbol><new-symbol>.

4. <symbol>* заменяется на <new-symbol> с правилом <new-symbol> ::= <empty> | <symbol><new-symbol>.

Здесь <empty> раскрывается в пустую строку: <empty> ::= . Такое раскрытие также называется эпсилон-раскрытием.

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

Для предыдущих примеров преобразование выглядит так:

• <idchar>+ превращается в <idchar><new-symbol>, где <new-symbol> ::= <idchar> | <idchar><new-symbol>;

• <integer>(.<integer>)? превращается в <integer><new-symbol>, где <new-symbol> ::= <empty> | .<integer>.

Реализуем это в три этапа.

Создание новых символов

Сначала нужен механизм создания отсутствующего в грамматике имени:

Раскрытие выражений в скобках

Теперь извлечём выражения в скобках, за которыми следует один из операторов:

Применим первое правило, вводя новые символы для выражений в скобках:

Простой пример даёт ожидаемое промежуточное правило:

Функция справляется и со вложенными скобками:

Раскрытие операторов

После скобок обработаем символы с ?, * и +. Сначала найдём все такие конструкции:

Преобразователь отделяет символ от оператора и добавляет правила согласно описанной схеме:

Объединение этапов

Сначала преобразуем скобки, затем операторы:

Конец экскурса

Пример использования convert_ebnf_grammar():

Преобразуем полную грамматику выражений:

Преобразование успешно. Классы символов и перевод EBNF в BNF — два мощных инструмента, которые многократно упростят запись грамматик.

Расширения грамматик

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

Аннотации прикрепляются к отдельным раскрытиям. Раскрытие теперь может быть не только строкой, но и парой из строки и набора атрибутов:

opts() задаёт аннотации конкретной альтернативы. Здесь сложение получает min_depth=10, а вычитание — max_depth=2. Значение атрибутов определяется алгоритмом, работающим с грамматикой; алгоритмы, которым они не нужны, могут их игнорировать.

Экскурс: реализация opts()

Вспомогательная функция opts() возвращает отображение именованных аргументов в их значения:

Чтобы одинаково обрабатывать обычные строки и пары с аннотациями, строка раскрытия и параметры читаются отдельными функциями exp_string() и exp_opts():

Наконец, вспомогательная функция устанавливает параметры выбранного раскрытия. Новые атрибуты объединяются с существующими; пустой словарь удаляет аннотацию.

Конец экскурса Проверка грамматик

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

is_valid_grammar() проходит по грамматике и проверяет, что все используемые символы определены и наоборот, а также что они достижимы из стартового символа. Это особенно полезно при отладке. Детали реализации можно пропустить, но перед применением грамматики важно удостовериться в корректности исходных данных.

Экскурс: реализация is_valid_grammar()

Сначала соберём множества определённых и использованных нетерминалов, одновременно проверяя базовую структуру:

Достижимые символы находятся рекурсивным обходом:

Также соберём имена применённых параметров:

Основная функция объединяет проверки. Она сообщает о неиспользуемых, неопределённых и недостижимых символах, а также о неподдерживаемых аннотациях:

Если добавленные правила сделали некоторые нетерминалы ненужными, trim_grammar() удаляет неиспользуемые и недостижимые определения:

Конец экскурса

Созданные выше грамматики проходят проверку:

А ошибочные примеры не проходят:

Эти случаи соответственно сообщают, что раскрытия не являются списком, список пуст или его элементы не являются строками. Комментарии # type: ignore не позволяют статическому анализатору заранее отклонить намеренно ошибочные примеры. Далее при определении грамматик всегда будет применяться is_valid_grammar().

Итоги

Эта глава представила грамматики как простой способ задавать языки входных данных и тестировать программы синтаксически корректными входами. Грамматика — отображение нетерминальных символов в списки альтернативных раскрытий. Например, грамматика телефонного номера США была приведена в начале главы.

Генератор начинает со <start>, случайно выбирает раскрытие и продолжает, пока не останется нетерминалов. Это делает simple_grammar_fuzzer(). На практике лучше применять GrammarFuzzer или его производные на основе покрытия, вероятностей и генераторов: они эффективнее, защищены от бесконечного роста и обладают дополнительными возможностями.

Также был введён набор вспомогательных инструментов: классы символов, сокращения повторений, расширение и проверка грамматик.

Усвоенные уроки

• Грамматики — мощный инструмент описания и создания синтаксически корректных входов.

• Созданные грамматикой входы можно использовать непосредственно или как начальные образцы мутационного фаззинга.

• Классы символов и операторы расширяют грамматики и упрощают их запись.

Дальнейшие шаги

Грамматики являются прекрасной основой для генерации тестов и будут неоднократно использоваться в книге. Например, они позволяют фаззить конфигурации:

Грамматики подходят для фаззинга функций, API и графических интерфейсов:

Отдельным раскрытиям можно назначать вероятности и ограничения:

Эти дополнения особенно ценны, поскольку позволяют:

1. автоматически выводить грамматики, не задавая их вручную;

2. направлять генерацию к конкретным целям — например, покрытию или критическим функциям.

Все эти техники будут рассмотрены далее. Следующий необходимый шаг — создание эффективного грамматического фаззера.

История вопроса

Грамматики как основа человеческого языка существуют столько же, сколько и сам язык. Первую формализацию порождающей грамматики создал Дакшипутра Панини около 350 года до н. э. [Panini, 350 BCE]. Роль грамматик как общего средства описания формальных языков данных и программ в информатике трудно переоценить. Основополагающая работа Хомского [Chomsky, 1956] ввела центральные модели регулярных языков, контекстно-свободных, контекстно-зависимых и универсальных грамматик, которые с тех пор используются для спецификации языков входов и программирования.

Применение грамматик для создания тестовых входов восходит к Буркхардту [Burkhardt, 1967], а позднее было заново открыто и применено Хэнфордом [Hanford, 1970] и Пёрдомом [Purdom, 1972]. Важнейшей областью грамматического тестирования стало тестирование компиляторов. Именно оно во многом способствует надёжности современных компиляторов и браузеров:

• CSmith [Yang et al., 2011] специально создаёт программы на C. Он начинает с грамматики C, а затем учитывает ранее определённые переменные и функции, безопасность целых чисел и типов. Авторы сообщили более чем о 400 ранее неизвестных ошибках компиляторов.

• LangFuzz [Holler et al., 2012], созданный при участии двух авторов этой книги, использует общую грамматику для круглосуточной генерации JavaScript и тестирования интерпретаторов. Он обнаружил более 2600 ошибок в Mozilla Firefox, Google Chrome и Microsoft Edge.

• EMI Project [Le et al., 2014] испытывает компиляторы C, превращая известные тесты в альтернативные программы, которые должны быть семантически эквивалентны для всех входов. Благодаря этому исправлено более ста ошибок компиляторов C.

• Grammarinator [Hodovan et al., 2018] — открытый грамматический фаззер на Python, использующий популярный формат ANTLR. Подобно LangFuzz, он применяет грамматику и для разбора, и для генерации; с его помощью найдено более ста проблем в лёгком движке JavaScript JerryScript и связанной платформе.

• Domato — универсальный движок грамматической генерации, специально применяемый для фаззинга DOM. Он выявил ряд уязвимостей в популярных браузерах.

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

Упражнения Упражнение 1. Грамматика JSON

Изучите спецификацию JSON и выведите из неё грамматику:

• применяйте классы символов для допустимых знаков;

• используйте EBNF для повторений и необязательных частей;

• считайте, что строка является последовательностью цифр, букв ASCII, знаков пунктуации и пробелов без кавычек и экранирования;

• считайте пробельным символом один обычный пробел;

• проверьте грамматику с помощью is_valid_grammar().

Передайте результат simple_grammar_fuzzer(). Возникают ли ошибки и почему?

Решение. Спецификация переводится достаточно непосредственно:

Попробуем создать 50 объектов, ожидая возможные ошибки раскрытия:

Фаззер создаёт разнообразные объекты, но иногда заканчивает ExpansionError. Причина в том, что он сначала достигает максимального числа элементов, после чего отвергает любое раскрытие, временно увеличивающее число нетерминалов, даже если в дальнейшем оно сократило бы строку. В следующей главе этот недостаток устраняется более надёжным алгоритмом.

Упражнение 2. Поиск ошибок

Название simple_grammar_fuzzer() выбрано неслучайно: способ раскрытия грамматик имеет несколько ограничений. Что произойдёт при применении функции к определённым выше nonterminal_grammar и expr_grammar и почему?

Решение. nonterminal_grammar не работает, потому что фаззер в конце концов пытается раскрыть только что созданный текст, похожий на нетерминал:

После генерации <j> функция распознаёт его как нетерминал, но такого ключа в грамматике нет, поэтому возникает KeyError: '<j>'.

С expr_grammar ситуация ещё хуже: фаззер может начать бесконечную последовательность раскрытий.

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

Упражнение 3. Грамматики с регулярными выражениями

В грамматике, расширенной регулярными выражениями, специальная форма

включает регулярное выражение в раскрытие. Например,

кратко задаёт целое число как необязательный знак и последовательность цифр.

Часть 1. Преобразование регулярных выражений

Напишите convert_regex(r), которая принимает регулярное выражение r и создаёт эквивалентную грамматику. Поддержите следующие конструкции:

• *, +, ? и () работают так же, как в EBNF;

• a|b преобразуется в список альтернатив [a, b];

• . соответствует любому символу, кроме перевода строки;

• [abc] преобразуется в srange("abc");

• [^abc] — во множество символов ASCII за исключением srange("abc");

• [a-b] преобразуется в crange(a, b);

• [^a-b] — во множество символов ASCII за исключением crange(a, b).

Например, convert_regex(r"[0-9]+") должна вернуть грамматику наподобие:

Решение. Оставлено читателю.

Часть 2. Поиск и раскрытие регулярных выражений

Напишите convert_regex_grammar(g), принимающую EBNF-грамматику g с регулярными выражениями /.../ и создающую эквивалентную BNF-грамматику. Поддержите перечисленные выше конструкции.

Например, convert_regex_grammar({"<integer>": "/[+-]?[0-9]+/"}) должна дать результат наподобие:

Дополнительно можно поддержать экранирование: \c означает буквальный c, \/ — символ /, не завершающий регулярное выражение, а \\ — обратную косую черту.

Решение. Оставлено читателю.

Упражнение 4. Определение грамматик функциями (повышенная сложность)

Для более приятного синтаксиса спецификации можно использовать конструкции Python, которые затем разбирает отдельная функция. Например, альтернативы можно разделять оператором |:

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

Воспользуемся модулями ast для абстрактных синтаксических деревьев и inspect для анализа кода:

Теперь дерево можно обойти и найти операторы с альтернативами. get_alternatives() рекурсивно спускается по узлам бинарного |. Когда достигнуто отдельное раскрытие, параметр to_expr преобразует его в нужное представление; здесь это строка.

funct_parser() принимает AST функции и проходит по всем присваиваниям:

Результат имеет обычный формат грамматики:

Часть 1(a). Одна функция

Напишите define_grammar(fn), которая принимает грамматику, записанную как функция, и возвращает обычную грамматику.

Решение. Достаточно объединить получение исходного текста, разбор AST и созданный анализатор:

Python позволяет сразу связать сгенерированную грамматику с именем функции с помощью декоратора. Тогда ошибочная функция не остаётся доступной:

Часть 1(b). Альтернативные представления

Предыдущее представление не позволяет просто включать результаты srange() и crange(), а строковая запись выражений может показаться ограниченной. Её легко расширить:

Теперь грамматику можно записать с помощью имён Python и оператора сложения для последовательности:

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

В этом варианте ещё не поддерживаются srange() и crange(). Как добавить их? Подсказка: оберните define_expr() и ищите узлы ast.Call.

Часть 2. Расширенные грамматики

Введите оператор *, принимающий пару (min, max), где min и max — минимальное и максимальное число повторений. Отсутствующий min означает ноль, отсутствующий max — бесконечность.

Через * можно обобщить операторы EBNF: ? соответствует (0, 1), * — (0,), а + — (1,). Напишите преобразователь, который разбирает записанную таким образом расширенную грамматику и переводит её в BNF.

Решение. Решения пока нет :-)

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

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

Предварительные знания

• Нужно понимать основы грамматического фаззинга из предыдущей главы.

Краткое содержание Эффективный грамматический фаззинг

В главе вводится GrammarFuzzer — эффективный фаззер, создающий по грамматике синтаксически корректные строки. Типичное применение:

Конструктор GrammarFuzzer принимает именованные параметры, управляющие поведением. Например, start_symbol задаёт начальный символ вместо <start>:

Параметры конструктора имеют следующий смысл:

• grammar — грамматика генерируемых строк;

• start_symbol — стартовый символ;

• min_nonterminals и max_nonterminals — границы числа создаваемых нетерминалов;

• disp включает отображение промежуточных деревьев вывода;

• log печатает промежуточные шаги в стандартный поток вывода.

Деревья вывода

Внутри GrammarFuzzer использует деревья вывода, раскрываемые шаг за шагом. После генерации строки полученное дерево доступно в атрибуте derivation_tree:

Во внутреннем представлении узел — пара (symbol, children). У нетерминала symbol содержит раскрываемый символ, а children — список дочерних узлов. У терминала symbol содержит терминальную строку, а список потомков пуст.

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

Недостаточный алгоритм

В предыдущей главе функция simple_grammar_fuzzer() принимала грамматику и автоматически создавала синтаксически корректную строку. Однако она действительно проста и обладает существенными ограничениями. Вернёмся к грамматике выражений, полученной из EXPR_EBNF_GRAMMAR.

У expr_grammar есть любопытное свойство: simple_grammar_fuzzer() на ней застревает.

В течение секунды функция не завершается. Причина заключена в правиле:

Любая альтернатива, кроме (<expr>), хотя бы временно увеличивает число символов. Поскольку установлен жёсткий предел на число раскрываемых символов, единственным доступным выбором для <factor> остаётся (<expr>). Это ведёт к бесконечному добавлению скобок.

Потенциально бесконечное раскрытие — лишь один недостаток simple_grammar_fuzzer():

1. Низкая эффективность. На каждой итерации фаззер ищет в уже созданной строке символы для раскрытия. По мере роста строки поиск дорожает.

2. Слабая управляемость. Даже при ограничении числа символов результат может оказаться очень длинным или бесконечным.

Измерим время создания строк различной длины:

Построим диаграмму зависимости времени от длины:

Эксперимент показывает две вещи: время создания растёт квадратично с длиной результата, а значительная часть результатов имеет десятки тысяч символов. График генерируется приведённым кодом, поэтому растровый вывод блокнота не дублируется.

Нужен более разумный алгоритм: эффективный, хорошо управляемый и способный заранее понять, что альтернатива (<expr>) в expr_grammar может раскрыться бесконечно, в отличие от двух других.

Деревья вывода

Чтобы повысить эффективность и контролировать раскрытие, будем представлять создаваемые строки специальной структурой — постепенно раскрываемым деревом вывода. Оно сохраняет текущее состояние: какие элементы во что раскрылись и какие символы ещё предстоит обработать. Кроме того, добавлять узлы дерева значительно дешевле, чем многократно заменять фрагменты строки.

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

Рассмотрим процесс раскрытия на арифметической грамматике. Начинаем с единственного корневого узла, представляющего стартовый символ <start>:

Для раскрытия дерева ищется нетерминал S без потомков — ещё не раскрытый символ. Из грамматики выбирается его раскрытие и добавляется как потомок S. Единственная альтернатива <start> — <expr>:

Чтобы получить строку из дерева, обходим его по порядку и собираем символы листьев. На этом этапе результат равен "<expr>".

Далее раскрывается <expr>. Если выбрать <expr> + <term>, у узла появятся три потомка:

Раскрытие повторяется, пока не останется необработанных нетерминалов. Например, обе ветви в итоге проходят через <term>, <factor>, <integer> и <digit> к терминалу 2:

Так получено представление строки 2 + 2. В отличие от самой строки, дерево сохраняет всю структуру и историю порождения. Его легко сравнивать и изменять — например, заменять одно поддерево другим. Диаграммы оригинального блокнота генерируются через Graphviz; выше они представлены эквивалентными текстовыми деревьями без машинного SVG.

Представление деревьев вывода

В Python узел представляется парой

где SYMBOL_NAME — строка узла, например "<start>" или "+", а CHILDREN — список дочерних узлов.

CHILDREN имеет два особых значения:

1. None — место для будущего раскрытия. Узел является нетерминалом и должен быть обработан дальше.

2. [] — пустой список, то есть потомков нет. Узел является терминалом и больше не раскрывается.

Тип DerivationTree описывает эту структуру. Строго говоря, вместо Any должен стоять DerivationTree, но статическая типизация Python не всегда хорошо обрабатывает рекурсивные типы.

Представим промежуточное дерево <expr> + <term>:

Для наглядности введём display_tree().

Экскурс: реализация display_tree()

Функция программно обходит структуру и строит изображение утилитой dot из Graphviz. Если реализация визуализации неинтересна, можно перейти сразу к следующему примеру.

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

Хотя сейчас визуализируется именно derivation_tree, полезно обобщить функцию на любую древовидную структуру. extract_node() извлекает символ, потомков и необязательную аннотацию:

Иногда обработанные и необработанные узлы нужно рисовать по-разному. Стандартные функции атрибутов узла, ребра и графа можно заменить пользовательскими:

display_tree() принимает эти четыре функции и использует их при рекурсивном обходе:

Конец экскурса

Вызов отображает уже определённую структуру:

Её внутреннее представление можно проверить непосредственно:

В книге иногда используется display_annotated_tree(), добавляющая аннотации к отдельным узлам.

Экскурс: исходный код и пример display_annotated_tree()

Функция отображает аннотированное дерево слева направо:

Например, узел с номером 3 помечается словом plus, а ребро от узла 1 к 3 — op:

Конец экскурса

Чтобы собрать все листья дерева в строку, пригодится all_terminals():

Альтернативная tree_to_string() тоже преобразует дерево в строку, но заменяет нераскрытые нетерминалы пустыми строками:

Раскрытие узла

Разработаем алгоритм, который принимает дерево с нераскрытыми символами и последовательно обрабатывает их. Как и прежде, создадим производный от Fuzzer класс GrammarFuzzer. Он получает грамматику и стартовый символ; остальные параметры позднее будут управлять генерацией и отладкой.

Для последовательного добавления методов используется уже знакомый приём:

Фактически создаётся новый класс, наследующий предыдущий, но для дальнейшего изложения разница несущественна.

Экскурс: реализация check_grammar()

Метод проверяет наличие стартового символа и согласованность грамматики. Подклассы смогут объявлять поддерживаемые аннотации:

Конец экскурса

init_tree() создаёт дерево только со стартовым символом:

Именно это одноузловое дерево предстоит раскрыть.

Выбор альтернативы потомков

Один из центральных методов — choose_node_expansion(). Он получает узел и список возможных списков потомков — по одному для каждой альтернативы правила — и возвращает индекс выбранного варианта.

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

Получение возможных раскрытий

Для построения возможных потомков нужна expansion_to_children(). Она принимает строку раскрытия и разбивает её на список деревьев — по одному для каждого терминального или нетерминального фрагмента.

Экскурс: реализация expansion_to_children()

Функция использует re.split():

Конец экскурса

Обычное раскрытие делится на три узла:

Эпсилон-раскрытие требует отдельной обработки:

Как и nonterminals(), функция принимает кортеж с дополнительными данными, игнорируя их:

Сделаем утилиту методом, чтобы подклассы могли её переопределять:

Объединение компонентов

Теперь можно:

1. взять нераскрытый узел дерева;

2. случайно выбрать раскрытие;

3. вернуть новое дерево.

Именно это делает expand_node_randomly().

Экскурс: реализация expand_node_randomly()

Функция строит массив возможных потомков и передаёт его choose_node_expansion(), которую подклассы могут переопределять.

Общий expand_node() в будущем позволит выбирать стратегию, а пока просто вызывает случайное раскрытие:

Хук process_chosen_children() по умолчанию ничего не меняет, но подклассы смогут обрабатывать уже выбранных потомков:

Конец экскурса

Проверим работу на узле <integer>:

В данном запуске <integer> раскрывается в <digit>:

Можно отдельно взять поддерево цифры и раскрыть его:

<digit> превращается в одну из цифр согласно правилу грамматики. При этом исходное expr_tree не меняется: expand_node_randomly() возвращает новое дерево, не модифицируя аргумент.

Раскрытие дерева

Применим раскрытие отдельного узла к узлам всего дерева. Для этого сначала нужно найти нераскрытые узлы. possible_expansions() подсчитывает их число.

В нашем демонстрационном дереве таких узлов два:

Метод any_possible_expansions() сообщает, остался ли в дереве хотя бы один нераскрытый узел:

Главный метод алгоритма, expand_tree_once(), раскрывает ровно один узел. Если ему передан ещё не раскрытый нетерминал, он вызывает рассмотренный выше expand_node(). Если у узла уже есть потомки, метод находит среди них поддеревья с нераскрытыми символами, случайно выбирает одно и рекурсивно продолжает обход в нём.

Экскурс: реализация expand_tree_once()

Метод заменяет выбранного потомка на месте: переданное дерево действительно изменяется, а не только возвращается новая версия. Благодаря этому операция особенно эффективна. Вспомогательный choose_tree_expansion() возвращает индекс выбранного раскрываемого поддерева:

Конец экскурса

Покажем работу метода на уже знакомом дереве:

Теперь дважды раскроем по одному узлу:

На каждом шаге раскрывается ещё один символ. Остаётся повторять операцию, постепенно наращивая дерево.

Завершение раскрытия

С помощью expand_tree_once() дерево можно увеличивать и дальше — но когда и как остановиться? Ключевая идея, предложенная Люком (Luke, 2000), состоит в следующем: после раздувания дерева вывода до некоторого максимального размера следует применять только те раскрытия, которые увеличивают дерево минимально.

Например, для <factor> предпочтительно раскрытие в <integer>, поскольку оно не добавляет рекурсии и связанного с ней роста. Для <integer> по той же причине лучше <digit>, а не <digit><integer>.

Чтобы определить стоимость раскрытия символа, введём две взаимно зависимые функции:

• symbol_cost() возвращает минимальную стоимость среди всех вариантов раскрытия символа, вычисляя каждый вариант через expansion_cost();

• expansion_cost() возвращает сумму стоимостей всех символов в варианте. Если при обходе нетерминал встречается повторно, стоимость считается бесконечной: это признак потенциально бесконечной рекурсии.

Экскурс: реализация стоимостных функций Конец экскурса

Минимальная стоимость раскрытия цифры равна единице: нужно выбрать один из её терминальных вариантов.

Для <expr> минимальная стоимость равна пяти — именно столько раскрытий требуется в кратчайшей цепочке:

<expr> → <term> → <factor> → <integer> → <digit> → 1.

Вариант expand_node_by_cost(self, node, choose) учитывает эту стоимость. Он вычисляет стоимости всех альтернатив, функцией choose выбирает нужное значение — по умолчанию минимальное — и случайно выбирает одну из альтернатив с такой стоимостью, если их несколько.

Экскурс: реализация expand_node_by_cost() Конец экскурса

Сокращённый метод expand_node_min_cost() передаёт в качестве choose функцию min() и тем самым раскрывает узел с минимальной стоимостью:

Теперь им можно завершить раскрытие нашего дерева. Переопределим expand_node(), чтобы expand_tree_once() использовал минимальную стоимость:

Сначала дерево ещё содержит нераскрытые узлы:

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

Продолжим до тех пор, пока не будут раскрыты все нетерминалы:

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

Раздувание узлов

Особенно в начале генерации нам может понадобиться как можно больше узлов, то есть следует предпочитать варианты с большим числом нетерминалов для последующего раскрытия. Это прямая противоположность expand_node_min_cost(). Метод expand_node_max_cost() всегда выбирает среди вариантов с наибольшей стоимостью:

Для демонстрации снова переопределим expand_node() и выполним несколько шагов:

Повторные вызовы дают, например:

На каждом шаге число нетерминалов растёт. Очевидно, на этот рост нужно наложить ограничение.

Три фазы раскрытия

Объединим три фазы в одной функции expand_tree():

1. Раскрытие с максимальной стоимостью. Дерево раскрывается наиболее дорогими вариантами, пока в нём не появится хотя бы min_nonterminals нетерминалов. Значение 0 полностью отключает эту фазу.

2. Случайное раскрытие. Дерево раскрывается случайно, пока число нетерминалов не достигнет max_nonterminals.

3. Раскрытие с минимальной стоимостью. Оставшиеся ветви закрываются наиболее дешёвыми вариантами.

Для этого ссылка на метод expand_node последовательно получает значения expand_node_max_cost, expand_node_randomly и expand_node_min_cost. В первых двух фазах задаются пределы min_nonterminals и max_nonterminals соответственно.

Экскурс: реализация трёхфазного expand_tree() Конец экскурса

Опробуем стратегию на частично раскрытом дереве:

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

Итоговое дерево можно визуализировать, а его терминальную строку получить так:

Собираем всё вместе

Теперь можно определить fuzz(), который, как и simple_grammar_fuzzer(), принимает грамматику и производит строку, скрывая от вызывающего кода всю сложность деревьев вывода:

Теперь фаззер можно применять ко всем определённым грамматикам и при желании визуализировать полученное дерево:

После вызова fuzz() дерево вывода доступно через атрибут derivation_tree:

Проверим фаззер и его деревья на других форматах:

Сравним производительность с simple_grammar_fuzzer():

Связь времени со размером результата строится следующим кодом:

Генерация стала намного быстрее, хотя и строки теперь меньше. Деревья вывода дают существенно больше контроля над производством строк по грамматике.

Наконец, проверим GrammarFuzzer на рекурсивной expr_grammar, с которой не справился simple_grammar_fuzzer(). Новый фаззер работает без проблем:

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

Итоги главы

• Деревья вывода важны для выражения структуры входных данных.

• Грамматический фаззинг на основе деревьев вывода:

1. значительно эффективнее строкового грамматического фаззинга;

2. даёт намного больше контроля над генерацией входных данных;

3. эффективно предотвращает бесконечные раскрытия.

Что дальше

Поздравляем! Вы достигли одного из центральных узлов книги. Отсюда расходится множество методов, основанных на грамматическом фаззинге.

Расширение грамматик

Сначала рассмотрим методы, каждый из которых тем или иным образом расширяет грамматику:

• разбор и рекомбинация входных данных позволяют использовать существующие входы, снова опираясь на деревья вывода;

• покрытие вариантов грамматики обеспечивает комбинаторное покрытие;

• назначение отдельным вариантам вероятностей даёт дополнительный контроль над раскрытиями;

• назначение отдельным вариантам ограничений позволяет выражать семантические условия для правил.

Применение грамматик

Кроме того, грамматики можно применять в нескольких контекстах, где они в той или иной форме изучаются автоматически:

• фаззинг API — грамматика извлекается из API;

• фаззинг графических пользовательских интерфейсов — грамматика изучается по интерфейсу для последующей генерации;

• добыча грамматик — грамматика изучается для произвольного формата входных данных.

Продолжайте раскрывать правила!

История и дополнительная литература

Деревья вывода, которые часто называют также деревьями разбора, — стандартная структура данных, в которую синтаксические анализаторы раскладывают вход. «Книга дракона» (Compilers: Principles, Techniques, and Tools, Aho et al., 2006) рассматривает разбор в деревья вывода в контексте компиляции программ. Мы также используем их при разборе и рекомбинации входных данных.

Главная идея этой главы — раскрывать дерево до достижения предела числа символов, а затем всегда выбирать кратчайший путь — восходит к работе Люка (Luke, 2000).

Упражнения Упражнение 1. Кеширование результатов методов

Трассировка GrammarFuzzer показывает, что некоторые методы многократно вызываются с одними и теми же значениями.

Создайте класс FasterGrammarFuzzer с кешем: если метод уже вызывался, он должен вернуть ранее вычисленное, «мемоизированное» значение. Реализуйте это для expansion_to_children() и сравните число вызовов до и после оптимизации.

Важно: каждый список, возвращаемый expansion_to_children(), должен быть отдельной копией. Возврат одного и того же кешированного списка помешает модификации дерева на месте, которую выполняет GrammarFuzzer. Используйте copy.deepcopy().

Решение. Покажем кеширование на expansion_to_children():

Упражнение 2. Предварительная компиляция грамматики

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

Решение. Один из вариантов использует небольшой трюк: после заполнения таблиц исходные функции symbol_cost() и expansion_cost() заменяются функциями чтения из кеша.

Стоимости отдельных вариантов:

Упражнение 3. Хранение раскрываемых деревьев

В expand_tree_once() алгоритм снова и снова обходит дерево в поисках нетерминалов, которые ещё можно раскрыть. Ускорьте процесс, поддерживая список таких нетерминалов.

Решение: оставлено читателю в качестве упражнения.

Упражнение 4. Альтернативное случайное раскрытие

Можно определить expand_node_randomly() так, чтобы он просто вызывал expand_node_by_cost(node, random.choice):

Чем эта версия отличается от исходной реализации?

Решение. В ExerciseGrammarFuzzer распределение вероятностей иное. Исходный GrammarFuzzer выбирает все варианты раскрытия с одинаковой вероятностью. В альтернативной версии сначала случайно выбирается стоимость, а затем — снова случайно — один из вариантов с этой стоимостью. Поэтому варианты с уникальной стоимостью получают более высокую вероятность выбора.

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

Предварительные требования

• Следует прочитать главу о грамматиках.

• Следует прочитать главу об эффективном грамматическом фаззинге.

Краткое содержание

Чтобы использовать код этой главы, импортируйте нужный идентификатор:

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

В следующем примере GrammarCoverageFuzzer создаёт выражение. Полученная строка за один запуск содержит все цифры и все операторы:

После генерации метод expansion_coverage() возвращает множество покрытых вариантов грамматики:

Последующие вызовы fuzz() продолжают наращивать покрытие, а reset() очищает накопленные сведения и начинает работу заново.

Поскольку разнообразие входных данных обычно повышает и покрытие кода, GrammarCoverageFuzzer — рекомендуемое расширение GrammarFuzzer.

Иллюстрация к краткому содержанию, указанная в исходной тетради как PICS/GrammarCoverageFuzzer-synopsis-1.svg, в локальном зеркале отсутствует; результат полностью воспроизводится приведённым кодом.

Покрытие элементов грамматики

Цель генерации тестов — охватить всю функциональность программы, включая, если повезёт, ошибочную. Однако функциональность связана со структурой входных данных: если генератор не создаёт определённые элементы, соответствующий код не выполняется и шанс найти в нём ошибку исчезает.

Рассмотрим грамматику выражений EXPR_GRAMMAR из предыдущей главы:

• если не создавать отрицательные числа, они не будут протестированы;

• если не создавать числа с плавающей точкой, они тоже не будут протестированы.

Следовательно, нужно покрыть все возможные варианты раскрытия — не случайно, а целенаправленно.

Один из способов повысить разнообразие — отслеживать раскрытия во время генерации. Если некоторый вариант уже встречался, можно предпочесть ещё не покрытые альтернативы. Рассмотрим правило для множителя:

Предположим, что при первом раскрытии <factor> уже был получен <integer>. При следующем раскрытии этот вариант отмечается как покрытый, и генератор выбирает одну из ещё не использованных альтернатив: например, -<factor> для отрицательного числа или <integer>.<integer> для числа с плавающей точкой. Только покрыв все альтернативы, он снова начнёт рассматривать уже встречавшиеся варианты.

Отслеживание покрытия грамматики

Эту концепцию реализовать несложно. Введём класс TrackingGrammarCoverageFuzzer, который хранит достигнутое покрытие:

Хранение покрытых раскрытий

В множестве covered_expansions сохраняются все встреченные варианты:

Варианты сохраняются в виде строк «символ -> раскрытие». Следующий метод expansion_key() создаёт строковое представление пары (символ, раскрытие).

Пример:

Вместо строки раскрытия можно передать список потомков; он будет автоматически преобразован в строку:

Вычисление возможных раскрытий

Множество всех возможных раскрытий грамматики можно получить простым перечислением. Метод max_expansion_coverage() рекурсивно обходит грамматику от заданного символа — по умолчанию от начального — и накапливает варианты в множестве expansions. Параметр max_depth, по умолчанию равный бесконечности, ограничивает глубину обхода; он понадобится далее в этой главе.

Так можно вычислить все варианты грамматики выражений:

Результат совпадает с полным множеством из краткого содержания: 24 варианта для начального символа, выражения, терма, множителя, целого числа и цифры.

Отслеживание раскрытий во время фаззинга

Во время генерации можно отмечать каждое встреченное раскрытие. Для этого подключимся к методу choose_node_expansion(), который выбирает вариант при раскрытии одного узла:

Вспомогательный метод missing_expansion_coverage() возвращает ещё не покрытые варианты:

Собираем компоненты

Покажем отслеживание на простом примере, ограничившись раскрытиями <digit>:

Следующий запуск сохраняет прежнее покрытие и добавляет новый вариант:

Третий вызов может добавить цифру 5:

Полученное к этому моменту покрытие:

Полное множество доступных вариантов:

Следовательно, пока отсутствует такое покрытие:

Сколько символов в среднем приходится сгенерировать, прежде чем будут покрыты все варианты? Это измеряет следующая функция:

Для полных выражений требуется больше данных:

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

Теперь будем не только измерять покрытие, но и целенаправленно создавать его. Стратегия такова:

1. определить ещё не покрытых потомков в uncovered_children;

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

3. иначе выбрать одного из непокрытых потомков и отметить его как покрытого.

Новый SimpleGrammarCoverageFuzzer реализует эту стратегию в choose_node_expansion() — методе, через который суперкласс GrammarFuzzer выбирает раскрытие:

Два метода выбора предусмотрены как точки расширения для подклассов:

Поскольку фаззер сохраняет множество уже покрытых вариантов, повторные вызовы постепенно увеличивают покрытие. Для <digit> каждый вызов выдаёт новую цифру:

Текущее покрытие:

Ещё семь запусков каждый раз покрывают новое раскрытие:

После этого покрыты все цифры:

Применим тот же подход к полной грамматике выражений. Уже после нескольких итераций он покрывает все цифры, операторы и варианты раскрытия:

Целенаправленная стратегия заметно эффективнее случайной:

Глубокое предвидение

Выбирать варианты отдельного правила — хорошее начало, но этого недостаточно. Рассмотрим пример с CGI-грамматикой:

После десяти итераций остаётся немало непокрытых вариантов:

Почему? Больше всего вариантов CGI-грамматики сосредоточено в правиле <hexdigit>, но сначала генератор должен дойти до него. При раскрытии <letter> есть три альтернативы:

Когда все три уже покрыты, прежний choose_node_expansion() выбирает между ними случайно, хотя за <percent> могут оставаться непокрытые шестнадцатеричные цифры.

Нужна стратегия, которая предпочитает <percent>, если ниже него ещё есть непокрытые раскрытия, даже когда сам вариант <percent> уже покрыт. У. Буркхардт (W. Burkhardt, 1967) впервые описал её как «выбор кратчайшего пути»: среди альтернатив выбирается та синтаксическая единица, под которой ещё доступен неиспользованный элемент, начиная с кратчайшего пути.

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

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

Параметр symbol позволяет вычислять возможное покрытие для любого символа:

Таким образом, раскрывая <integer>, можно покрыть двенадцать вариантов. Для <digit> доступны десять терминальных вариантов.

Определение ещё не покрытых потомков

Начнём реализацию GrammarCoverageFuzzer, вычисляя недостающее покрытие для каждого потомка. Для списка потомков max_expansion_coverage() даёт максимально достижимое покрытие; вычтем из него уже встреченное expansion_coverage():

Покажем работу new_child_coverage(). Сначала случайное раскрытие цифры даёт 2:

Раскрытие в 0 принесло бы новое покрытие, а повторное раскрытие в 2 — нет:

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

Следовательно, при выборе раскрытия можно предпочитать альтернативы, обещающие наибольшее новое покрытие.

Адаптивный просмотр вперёд

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

Центральный метод new_coverages() начинает с нулевой максимальной глубины и увеличивает её, пока не обнаружит хотя бы одно непокрытое раскрытие.

Экскурс: реализация new_coverages() Конец экскурса Собираем всё вместе

Теперь choose_node_expansion() реализует стратегию в два шага:

1. определяет возможное новое покрытие через new_coverages();

2. случайно выбирает среди потомков с максимальным новым покрытием через choose_uncovered_node_expansion().

Экскурс: реализация choose_node_expansion() Конец экскурса

GrammarCoverageFuzzer готов. На грамматике выражений он быстро покрывает все цифры и операторы:

Средний объём до полного покрытия снова меньше, чем у простой стратегии:

Для CGI-грамматики достаточно нескольких итераций, чтобы покрыть все буквы и цифры:

Сравнение случайной стратегии, покрытия только непосредственных вариантов и глубокого предвидения на CGI-грамматике:

Покрытие в контексте

Иногда один элемент грамматики используется в нескольких местах. Например, <integer> в грамматике выражений обозначает как целые числа, так и обе части чисел с плавающей точкой:

Описанная стратегия гарантирует покрытие всех раскрытий <integer> и <digit>, но отдельные цифры распределяются между всеми появлениями <integer>. Например, строки 1234.56 и 7890 вместе дают полное покрытие цифр, однако варианты <integer>.<integer> и <integer> по отдельности охватывают лишь часть цифр.

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

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

Ручное расширение грамматики для контекстного покрытия

Простой способ — дублировать символы вместе с правилами, на которые они ссылаются. Например, <integer>.<integer> можно заменить на <integer-1>.<integer-2> и дать обоим новым символам определение исходного <integer>. Тогда фаззер покроет все варианты не только <integer>, но также <integer-1> и <integer-2>.

На расширенной грамматике покрываются цифры обычных целых чисел, а также целой и дробной частей вещественных чисел:

Фаззер с предвидением специально создаёт вещественные числа, покрывающие все цифры и в целой, и в дробной части.

Программное расширение грамматики для контекстного покрытия

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

duplicate_context() принимает грамматику, символ и один из его вариантов (если вариант не указан — все варианты). Она заменяет ссылки внутри выбранного раскрытия ссылками на копии исходных правил. Предполагаемое использование:

Основная функция выглядит так:

Экскурс: реализация _duplicate_context()

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

Конец экскурса

Продублируем <integer>.<integer>. Получится новое правило <integer-1>.<integer-2>, обе части которого ссылаются на копии исходных правил:

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

Параметр depth управляет глубиной дублирования. Значение 1 копирует только следующее правило:

По умолчанию depth бесконечен. Истинно неограниченное копирование рекурсивной грамматики привело бы к проблемам, поэтому уже продублированные символы повторно не копируются. Тем не менее дублирование всех вариантов <expr> создаёт 292 правила и почти две тысячи раскрытий:

Ещё один уровень дублирования увеличивает грамматику до 594 правил и 3994 вариантов:

Теперь множество контекстов можно покрывать независимо — например, умножение элементов внутри сложения:

Такие грамматики становятся неудобны для ручного сопровождения, зато GrammarCoverageFuzzer систематически покрывает их варианты во всех контекстах. Для большого числа контекстов сочетание duplicate_context() и фаззера, управляемого покрытием, особенно полезно.

Покрытие кода через покрытие грамматики

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

Многие элементы грамматики прямо соответствуют функциям программы. В обработчике арифметических выражений знак + запускает сложение, - — вычитание, а вещественное число — арифметику с плавающей точкой.

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

CGI-грамматики

Исследуем эту связь на CGI-декодере из главы о покрытии кода.

Экскурс: построение графика

В словаре coverages значение coverages[x] = {y_1, y_2, ...} означает: x — достигнутое покрытие грамматики, а y_n — покрытие кода в запуске номер n.

Сначала приближённо получим максимальное покрытие декодера:

Теперь проведём сто испытаний:

Усредним значения y и построим диаграмму рассеяния:

Конец экскурса

По горизонтальной оси диаграммы отложено покрытие грамматики, по вертикальной — покрытие кода. Чем выше первое, тем выше и второе.

Коэффициент линейной корреляции превышает 0.8, что указывает на сильную связь:

Ранговая корреляция Спирмена подтверждает результат:

URL-грамматики

Повторим эксперимент для URL, заменив грамматику и исследуемую функцию:

Экскурс: построение графика

Сначала оценим максимальное покрытие:

Сам эксперимент:

Конец экскурса

Диаграмма снова сопоставляет покрытие грамматики по оси X и покрытие кода по оси Y. Линейная корреляция составляет около 0.88:

Корреляция Спирмена также близка к 0.95:

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

Всегда ли это работает?

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

Эквивалентные элементы

Некоторые элементы грамматики программа обрабатывает одинаково, хотя грамматика различает их. Имя хоста URL может содержать много символов, но обработчик обычно относится к ним единообразно. Отдельные цифры после объединения в число тоже менее важны, чем значение числа. Поэтому разнообразие символов и цифр не обязательно ведёт к разнообразию функциональности.

Частично проблему решает различение элементов по контексту и покрытие альтернатив в каждом контексте. Главное — определить, где разнообразие существенно, а где нет.

Глубокая обработка данных

Большую роль играет способ обработки данных. Вход медиапроигрывателя состоит из сжатых медиаданных. Разные данные меняют поведение и вывод проигрывателя, но эти различия нельзя напрямую вызвать отдельными синтаксическими элементами. Аналогично поведение модели машинного обучения, обученной на большом наборе входов, обычно не определяется одним элементом синтаксиса. При такой «глубокой» обработке структурное покрытие грамматики не обязательно создаёт покрытие кода.

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

При этом некоторые компоненты всё равно поддаются структурному покрытию: метаданные вроде имени автора или композитора и конфигурационные данные вроде настроек модели следует систематически перебирать. Этому посвящена глава о фаззинге конфигураций.

Иерархия реализованных классов такова: GrammarCoverageFuzzer наследует SimpleGrammarCoverageFuzzer, тот — TrackingGrammarCoverageFuzzer, далее следуют GrammarFuzzer и базовый Fuzzer. Диаграмма в исходной тетради строится программно из этих классов.

Итоги главы

• Быстрое достижение покрытия грамматики создаёт большое разнообразие входов.

• Дублирование правил позволяет покрывать элементы в определённых контекстах.

• Покрытие грамматики помогает повышать покрытие кода.

Что дальше

Далее покрытие грамматики применяется для систематического тестирования конфигураций.

История и дополнительная литература

Идея хотя бы однократного использования каждого варианта грамматики восходит к Буркхардту (Burkhardt, 1967), а позднее была независимо переоткрыта Полом Пёрдомом (Paul Purdom, 1972). Связь между покрытием грамматики и покрытием кода обнаружил Николас Хавриков (Nikolas Havrikov), исследовавший её в своей диссертации.

Упражнения Упражнение 1. Тестирование ls

Рассмотрим программу Unix ls, выводящую содержимое каталога. Создайте грамматику её вызова:

Используйте GrammarCoverageFuzzer, чтобы проверить все параметры. Убедитесь, что ls вызывается с каждым из них.

Решение. Символы параметров можно взять непосредственно со страницы руководства:

Значением max_nonterminals можно управлять числом параметров в каждом вызове ls. Другие примеры рассматриваются в главе о тестировании конфигураций.

Упражнение 2. Кеширование

Значение max_expansion_coverage() зависит только от грамматики. Измените реализацию так, чтобы значения для каждого символа и глубины предварительно вычислялись в __init__(), а max_expansion_coverage() лишь находил результат в таблице.

Решение. Задача аналогична первым двум упражнениям главы об эффективном грамматическом фаззинге; здесь применима такая же схема кеширования.