Автоматическое исправление ошибок
Автоматическое исправление ошибок (англ. Automatic bug-fixing) — это автоматическое устранение ошибок в программном обеспечении, осуществляемое без участия программмиста-человека.[1][2][3] Это направление также известно как автоматическая генерация патчей, автоматическое исправление ошибок или автоматическое восстановление программ[3]. Обычной целью таких подходов является автоматическая генерация корректных патчей для устранения ошибок в программах, при этом не должно допускаться регрессий, то есть усугубления состояния ПО[4].
Спецификация
Автоматическое исправление ошибок производится на основе спецификации ожидаемого поведения, которой может быть, например, формальная спецификация или набор тестов[5].
Набор тестов — пары входных и выходных данных, специфицирующие функциональность программы, часто фиксируемые в утверждениях, — может быть использован в качестве тестового оракула для управления поиском. Такой оракул условно делят на оракул ошибки (фиксирующий дефектное поведение) и оракул регрессии (гарантирующий сохранение функций, которые должен сохранять исправленный код). Однако тест-набор обычно неполон и не покрывает все случаи, вследствие чего может быть создан патч, успешно проходящий тесты, но неверно работающий на других входах[6]. Существование таких патчей — одна из главных проблем generate-and-validate-методов[6]. Современные успешные технологии автоматического исправления ошибок часто используют дополнительную информацию, например, модели, обученные на предыдущих человеческих исправлениях, чтобы выбирать более корректные патчи среди прошедших тесты[7].
Другой способ специфицировать ожидаемое поведение — применять формальные спецификации[8]. Проверка на полноту спецификации (то есть, покрывающей все функции) встречается реже из-за недоступности таковых в индустрии и высокой вычислительной стоимости формальной верификации. Однако для отдельных классов ошибок возможны неявные частичные спецификации — например, целевые методы для предотвращения выхода за границы переполнения в выбранных местах программы.
Технологии
Генерация и валидация (generate-and-validate)
Методы generate-and-validate компилируют и тестируют каждый кандидат-патч, собирая патчи, проходящие набор тестов[5]. Обычно это начинается с набора тестов, среди которых есть кейс, воспроизводящий ошибку[5][7][9][10]. Одной из ранних систем данного класса является GenProg[5]. Эффективность generate-and-validate методов часто дискутируется из-за отсутствия гарантии корректности патча.[6] Тем не менее, результаты современных подходов показывают многообещающие успехи. Например, система Prophet на стандартной коллекции из 69 ошибок в восьми крупных C-программах сгенерировала корректные патчи для 18 ошибок[7].
Одним из способов генерации кандидатных патчей является применение мутационных операторов: они модифицируют исходную программу, например через её абстрактное синтаксическое дерево, либо на уровне операторов/блоков. Ранние подходы генетического улучшения работали на уровне операторов, реализуя простые удаления/замены инструкций[5][11]. Новейшие методы работают на более детальных представлениях AST для создания большего разнообразия патчей[10]. Особенно удаление инструкций (statement deletion), а также более общие удаления кода, оказываются эффективны по локализации ошибок[12].
Другой подход к генерации патчей — использование шаблонов исправлений. Шаблоны — это заранее заданные модификации для определённых классов багов (например, вставка условного оператора для проверки значения на null, с целью устранения NullPointerException, либо изменение целочисленной константы на 1 для исправления ошибок типа off-by-one)[13].
Основанные на синтезе
Некоторые техники используют символическое исполнение. Например, Semfix[14] применяет символическое выполнение для извлечения ограничений на исправление. Angelix[15] ввёл концепцию «ангельского леса» для поддержки многострочных патчей.
В некоторых случаях задача исправления формулируется как задача синтеза кода. SemFix[14] использует компонентный синтез[16]. Dynamoth использует динамический синтез[17]. S3[18] опирается на синтаксически управляемый синтез кода[19]. SearchRepair[20] конвертирует потенциальные патчи в SMT-формулы и ищет такие варианты, для которых исправленная программа проходит все тесты.
На основе данных (data-driven)
Методы машинного обучения могут повышать эффективность автоматического исправления ошибок[7] Примером является подход, обучающийся на исправлениях, сделанных разработчиками (несколько сотен тысяч патчей из GitHub и SourceForge), и использующий полученные знания для распознавания и ранжирования потенциально верных патчей среди всех сгенерированных.[7] Альтернативой является майнинг патчей из других проектов (доноров) или Q&A-сайтов.[21].
Getafix[22] — язык-независимая система, применяемая в Facebook: она извлекает характерные паттерны исправлений по примерам коммитов и затем использует их для аналогичных багов в будущем, предлагая наиболее релевантное решение для последующей проверки.
Исправление по шаблонам
Для отдельных классов ошибок (например, утечек памяти, null pointer exception и др.) применяются специализированные шаблоны исправления:
- устранение null pointer exception путём проверки переменной на null[23];[13][24]
- устранение целочисленного переполнения
- устранение переполнения буфера
- устранение утечек памяти с автоматической вставкой освобождения памяти[25];
По сравнению с generate-and-validate, шаблонные методы обеспечивают более высокую точность для своей области, но сильно ограничены по классу ошибок[6][25].
Применение
Схемы использования автоматического исправления ошибок:
- В процессе разработки: разработчик по мере обнаружения ошибки инициирует автоматический поиск патча (например, нажатием кнопки в среде разработки). Поиск может проходить на фоне, если IDE сама анализирует проект на потенциальные проблемы[26].
- В режиме исполнения: при отказе во время работы возможно динамическое создание и подмена бинарного патча (on-line). Пример: система ClearView[27] для on-the-fly исправления x86-кода.
Пространство поиска
Фактически автоматическое исправление ошибок — это задача поиска, основанная на дедукции либо эвристиках. Пространство поиска состоит из всех допустимых изменений исходной программы. Исследования показывают, что исходная функция пригодности системы GenProg не лучше случайного поиска, а корректные патчи встречаются очень редко относительно некорректных (см. также раздел о переобучении ниже)[28].
Переобучение (overfitting)
В тест-ориентированном исправлении часто возникают патчи, проходящие тесты, но некорректные на недостающем покрытии; это называют переобучением (overfitting)[29]. Под этим понимается слишком точная подгонка патча под тестовые входы. Возможные проявления переобучения — частичное исправление (fixed только часть дефектных входов), либо внесение новых регрессий. В ранних прототипах переобучение было широко распространено: например, на ManyBugs у GenProg 104 из 110 сгенерированных патчей оказались переобученными[6] Для методов синтеза кода этот процент может превышать 80 %.[30].
Одним из путей борьбы с переобучением служит дополнительная фильтрация патчей — например, с помощью динамического анализа[31]. Альтернативные методы основываются на эвристиках или представлениях изменений кода[32].[33]
Ограничения автоматического исправления ошибок
Методы, опирающиеся только на тест-наборы, не обеспечивают гарантии корректности патчей, так как тесты зачастую неполны[6] Слабые тест-наборы могут приводить к появлению «валидных» (тест-проходящих), но некорректных патчей с удалением важных функций, утечками памяти, появлением новых уязвимостей.[6] Для уменьшения трудоёмкости квалификации тестов может применяться автоматическое построение тестовых оракулов, постепенно обучаемых на новых кейсах.[34].
Другим важным ограничением generate-and-validate является «взрыв» пространства поиска: количество инструкций и вариантов изменений настолько велико, что только гипотеза о малых изменениях позволяет значительно сокращать пространство перебора[35].
Недостатком символических методов[14][15] является резкое увеличение размера формул для реальных программ, особенно при необходимости изменения операторов с побочными эффектами.
Бенчмарки
Бенчмарки для автоматического исправления обычно ориентированы на конкретный язык программирования. В C основной набор — ManyBugs (69 реальных ошибок, собрано командой GenProg), который широко используется для сравнения средств для C[11].[7][10][15]
В Java стандартным эталоном является Defects4J, на котором строится большинство современых исследований исправления ошибок для Java[36].[37] Среди других бенчмарков — QuixBugs[38] (содержит «оригинальные» ошибки для задач восстановления), а также Bugs.jar[39], на основе коммитов.
Примеры инструментов
Автоматическое исправление ошибок активно исследуется в программной инженерии, разработано множество инструментов для C и Java (большинство носит исследовательский или экспериментальный характер).
C
- ClearView:[27] Инструмент для генерации бинарных патчей для развёрнутых приложений, проходят оценку на 10 случаях уязвимостей. В последующем исследовании по крайней мере для 4 из них были получены корректные патчи[6]
- GenProg:[5][11]. Базовый инструмент класса generate-and-validate, широко используется на ManyBugs.
- SemFix:[14] Первый программный инструмент для исправления багов в C на основе решателей.
- CodePhage: Первый инструмент, самостоятельно переносящий фрагменты кода между программами (может извлекать фрагменты даже из бинарных исполняемых файлов).
- LeakFix:[25] Средство для автоматического исправления утечек памяти в C-программах.
- Prophet:[7] Первая система этого класса, использующая обучение на человеческих патчах. Для 18 из 69 случаев производит патч, эквивалентный ручному исправлению[7]
- SearchRepair:[20]. Заменяет ошибочный код с помощью корректных примеров из других частей ПО. На наборе IntroClass качество патчей превышает решения GenProg, RSRepair и др[40].
- Angelix:[15] Улучшенный инструмент класса решателей; на GenProg-наборе для 10 случаев патчи эквивалентны человеческим.
- Learn2Fix:[34] Первый человек-в-петле (human-in-the-loop) полуавтоматический инструмент: систематически опрашивает пользователя для уточнения ошибок; работает с программами на целых числах.
Java
- PAR:[13] Инструмент generate-and-validate с использованием набора ручных шаблонов исправлений.
- QACrashFix:[21] — фиксирует Java-ошибки аварийных завершений через майнинг исправлений на Q&A сайтах.
- ARJA:[41] — многоцелевая система исправления Java на основе генетического программирования.
- NpeFix:[42] — автогенерация патчей для NullPointerException в Java (GitHub).