Введение 4
Постановка задачи 6
1. Обзор существующих решений 7
1.1. Инструмент CrossHair 7
1.1.1 Проблема нативных функций 7
1.1.2 Проблема неизвестных типов 8
1.2. Инструмент PyExZ3 10
1.3. Инструмент PySym 10
1.4. Генераторы тестов без символьного исполнения 10
1.4.1 Инструмент Pynguin 10
1.4.2 Инструмент Klara 11
1.4.3 Инструмент Hypothesis 11
2. Описание алгоритма 12
2.1. Выбранный подход 12
2.2. Компоненты универсальной символьной машины 15
2.3. Основной цикл символьного исполнения 15
2.4. Работа с неизвестными типами 16
3. Реализация 19
3.1. Связывание интерпретатора CPython и USVM в одном процессе 19
3.2. Модификация интерпретатора CPython 20
3.3. Реализация символьных операций 21
3.4. Система типов 23
3.5. Реализация отложенных ветвлений 25
3.6. Варианты реализаций PyVirtualPathSelector 28
3.6.1 Внутренние очереди 28
3.6.2 Выбор действия внутри операции peek 29
3.6.3 Выбор рейтинга типов 30
3.6.4 Планы на будущее 31
4. Полученные результаты 32
4.1. Соревнование SBFT 2024 32
4.2. Детали проведения наших экспериментов 32
4.3. Сравнение с CrossHair 33
4.4. Сравнение с фаззингом в UTBot Python 34
4.5. Сравнение с Pynguin 34
Заключение 39
Список литературы 40
Тема данной работы возникла в контексте задачи автоматической генерации юнит-тестов. Подобные инструменты способствуют улучшению качества программного кода и ускорению процесса тестирования. Автоматически создаваемые тесты позволяют выявлять ошибки и дефекты, обеспечивая более полное покрытие функциональности программы. Кроме того, они ускоряют обнаружение проблем при внесении изменений в код, что упрощает процесс рефакторинга. Поэтому разработка подобных инструментов является важной задачей.
Существуют различные подходы к генерации юнит-тестов. Методы «черного ящика» состоят в том, что анализ тестируемой программы не производится. Есть подходы, когда из анализируемой программы извлекается небольшой набор данных, например, используемые константы. Такие подходы называют методами «серого ящика». Существуют методы «белого ящика», которые состоят в том, что собирается полная информация обо всех операциях внутри тестируемой программы. За счет проведения более полного анализа программы возможно достигать большего покрытия.
Один из распространенных методов для генерации тестов — фаззинг. Он заключается в подстановке случайных данных в качестве входа функции, возможно, с использованием эвристик. Это метод «черного» или «серого» ящика. В определенных ситуациях фаззингу сложно пробиться через множество проверок входных данных внутри функции, что приводит к недостаточному покрытию. В таких случаях более эффективным методом является символьное исполнение, который является методом «белого ящика».
Метод символьного исполнения заключается в реализации интерпретатора, оперирующем символьными выражениями, с которыми умеют работать SMT-решатели1. Такой интерпретатор исследует различные пути выполнения программы и формирует ограничения, соответствующие этим путям. Затем SMT-решатель находит конкретные значения, удовлетворяющие собранным ограничениям.
Разработка анализаторов для Python является весьма сложной задачей. Это связано с разными аспектами данного языка программирования. Во-первых, в языке Python очень большое количество разных синтаксических конструкций, которые надо учитывать. Во-вторых, значительная часть стандартной библиотеки Python — это нативные расширения. К тому же есть много внешних библиотек, которые являются нативными расширениями, например, библиотека numpy.
Главная особенность Python заключается в том, что это динамически типизированный язык. Это представляет большие трудности как для фаззин- га, так и для символьного исполнения. Неудачное определение типов входных данных может привести к быстрому завершению программы. При этом вывод типов в Python является очень сложной задачей сам по себе. В части случаев возможно учитывать информацию из аннотаций типов, однако они используются далеко не во всех проектах на Python, и часто являются неполными и неточными. Существующие инструменты справляются с данной проблемой недостаточно хорошо.
В данной работе был предложен подход, как можно моделировать объекты неизвестного типа в символьном виде, а также каким образом приоритизировать конкретные типы. Основная идея состоит в том, что в символьной машине вводится техника отложенных ветвлений.
Предложенный подход был реализован в рамках символьной машины USVM. Эксперименты показали, что данный подход позволяет генерировать тесты с покрытием строк на 24% больше, чем у лучшего из существующих инструментов символьного исполнения для языка Python. Также добавление техники символьного исполнения в инструмент для генерации юнит-тестов UnitTestBot позволило увеличить покрытие сгенерированных тестов на 8%.
...
В результате данной работы были успешно выполнены следующие задачи:
1. Были проанализированы существующие реализации символьного исполнения для языка Python. Их немного, и в лучшей существующей реализации (инструмент CrossHair) имеется ряд проблем. В частности, инструмент CrossHair недостаточно хорошо подбирает типы в тех ситуациях, когда они не указаны в виде аннотаций.
2. Были разработаны подходы для решения проблем символьного исполнения, специфичных для языка Python. Для облегчения проблемы большого количества инструкций было решено комбинировать символьный интерпретатор с конкретным. Для облегчения проблемы нативных функций было решено модифицировать исходный код CPython. Для решения проблемы неизвестных типов был разработан подход с имитирующими объектами и отложенными ветвлениями.
3. Данные подходы были реализованы в рамках машины USVM. Основная часть кода была написана на Kotlin, но также присутствуют модули, написанные на C и на Python.
4. Было проведено сравнение полученного инструмента с существующими аналогами. Во-первых, инструмент UTBot Python с встроенной символьной машиной стал участником международного соревнования SBFT 2024, где занял призовое место. Во-вторых, был проведен эксперимент по генерации тестов с помощью различных инструментов для реализаций алгоритмов. Реализованная в данной работе символьная машина набрала на 24% большее покрытие, чем наиболее полная существующая реализация символьного исполнения для Python — CrossHair.
Реализация доступна в публичном репозитории:
https://github.com/UnitTestBot/usvm/tree/tochilinak/python.
