Автоматическая система исправления кода демонстрирует вдвое лучшие результаты по сравнению с предшественниками
Всякий, кому доводилось загружать обновления программ для компьютера или приложений для смартфона, знает, что почти всё коммерческое ПО не обходится без ошибок и слабых мест в системе безопасности, которые требуют регулярных патчей.
Подобные ошибки часто появляются просто по недосмотру. Например, когда программа пытается прочитать уже удаленные данные. Патчи зачастую тоже очень просты. Это может быть одна или две строки кода, которые проверяют, что объект данных всё еще существует.
Подобная простота натолкнула специалистов в области компьютерных наук на идею автоматической генерации патчей. Несколько групп исследователей, включая группу Мартина Ринара (Martin Rinard), профессора MIT в сфере электротехники и компьютерных наук, разработали шаблоны для обобщения часто встречающихся форм патчей. Эти шаблоны используются в специальных алгоритмах для генерации и оценки набора вариантов патчей.
Недавно, на симпозиуме Ассоциации вычислительной техники, посвященном основам разработки программного обеспечения, профессор Ринар, его студент Фэн Лун (Fan Long) и Питер Эмайден (Peter Amidon) из Калифорнийского университета в Сан-Диего представили новую систему, которая формирует шаблоны, обучаясь посредством анализа успешно действующих патчей для реального программного обеспечения.
Там, где написанная вручную система генерации патчей могла бы использовать пять или 10 шаблонов, эта новая система создала 85, обеспечив не только большее разнообразие, но и большую точность. Её шаблоны гораздо лучше "подогнаны" под конкретные разновидности встречающихся на практике патчей, так что она генерирует не так уж много непригодных вариантов. При тестировании эта новая система, получившая название Genesis, исправила почти вдвое больше ошибок, чем лучшая из написанных вручную систем генерации заплат.
Прореживание множества вариантов
"Мы лавируем между двумя альтернативами, — говорит Лун, аспирант MIT в сфере электротехники и компьютерных наук и первый из авторов посвященной системе статьи. — С одной стороны, нужно сгенерировать достаточно вариантов, чтобы среди них действительно были подходящие патчи. С другой стороны, не хотелось бы, чтобы чрезмерное количество вариантов делало невозможным их перебор".
Каждый элемент обучающей последовательности для Genesis включает два фрагмента кода: исходный, с ошибкой, и исправляющий ошибку патч. Genesis начинает с формирования пар обучающих примеров, сопоставляющих каждый элемент набора данных с каждым из остальных элементов.
После этого Genesis анализирует каждую пару и создает общее представление — черновик шаблона — чтобы синтезировать оба патча из прототипов. Конечно, он будет генерировать и непригодные варианты тоже. Но если представление будет достаточно общим, среди вариантов найдутся и патчи, которые обеспечивают нужный результат.
Далее, Genesis проверяет каждый из черновиков шаблонов на всех примерах из обучающей последовательности. Каждый из шаблонов основан всего на двух примерах, но он может работать и для нескольких других тоже. Оцениваются шаблоны по двум критериям: количество исправляемых им ошибок и число генерируемых им непригодных вариантов. Например, шаблон, генерирующий 10 вариантов, четыре из которых исправляют ошибки в обучающей последовательности, будет оценен выше, чем генерирующий 1000 вариантов со всего пятью подходящими заплатами.
На основе этих оценок, Genesis выбирает 500 самых многообещающих шаблонов. Для каждого из них, Genesis добавляет, по очереди, к исходной обучающей последовательности из двух примеров каждый из остальных примеров, создавая огромный набор из обучающих последовательностей по три примера. После этого он выполняет ту же самую процедуру оценки, извлекая 500 самых многообещающих шаблонов.
Перестраховка
После четырёх проходов этого процесса, каждый из 500 лучших шаблонов оказывается обучен на пяти примерах. Для итогового отсеивания используется несколько иной критерий оценки, гарантирующий, что все содержащиеся в обучающей последовательности ошибки, которые вообще можно исправить, будут исправлены. То есть, среди итоговых 500 патчей может встретиться шаблон, исправляющий только одну ошибку и получивший за счет этого относительно низкую оценку на предыдущем этапе оценки. Но если этот шаблон — единственный, исправляющий данную ошибку, то на последнем этапе он будет выбран.
В экспериментах исследователей, итоговое отсеивание снизило число шаблонов с 500 до 85. Genesis работает с программами, написанными на языке программирования Java, и исследователи MIT сравнили его производительность с производительностью лучших из написанных вручную систем генерации заплат. Genesis сумел исправить должным образом ошибки в 21 из 49 контрольных примеров, взятых из 41 программного проекта с открытым исходным кодом, в то время как предыдущая система – только в 11.
Не исключается, что при большем объеме обучающей последовательности и больших вычислительных мощностях удастся достичь еще более впечатляющих результатов. Но в любом случае система, экономящая программистам половину времени, затрачиваемого на поиск ошибок в коде, окажется полезной.
Источник: MIT