Автоматическое преобразование кода логического вывода для создания исправлений

Это статья, предоставленная инструктором. Из-за привычки удалять файлы я разместил эту статью в сообществе Nuggets в качестве резервной копии. Исходный адрес:Automatic Inference of Code Transforms for Patch Generation., В настоящее время у меня плохие навыки перевода. Если некоторые друзья считают, что есть проблема с переводом, я надеюсь указать на это в области комментариев, и все вместе смогут добиться прогресса ?

бумага: Фан Лонг, Питер Амидон и Мартин Ринар, 2017 г. Автоматический вывод преобразований кода для создания исправлений, Материалы 11-го совместного совещания Европейской конференции по программной инженерии и симпозиума ACM SIGSOFT по основам программной инженерии, Падерборн, Германия, 2017 г. , 4-8 сентября 2017 г. (ESEC/FSE'17), 13 стр.сделать i.org/10.1145/310…

Резюме

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

Ключевые слова

Генерация исправлений, преобразование кода, вывод пространства поиска

1. Введение

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

Genesis

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

конвертировать: Каждое преобразование Genesis имеет два шаблона абстрактных синтаксических деревьев (AST). Шаблон AST соответствует коду исходной программы. Другой шаблон AST указывает код замены для создания исправления. Шаблоны AST содержат переменные шаблона, соответствующие поддеревьям или подлесам в исходном или исправленном коде. Переменные шаблона позволяют преобразованиям абстрагироваться от конкретных деталей приложения, чтобы зафиксировать общие шаблоны, реализованные несколькими исправлениями, взятыми из разных приложений.

Строитель: Многие полезные патчи не просто перестраивают существующий код и логику, они также вводят новый код и логику. Таким образом, преобразование Genesis реализует частичное сопоставление с образцом, где замененный шаблон AST содержит свободные переменные шаблона, которые не совпали в исходном коде. Каждая свободная переменная шаблона связана с генератором, который может систематически генерировать новые компоненты кода-кандидата для свободной переменной. Эта технология позволяет Genesis синтезировать новый код и логику в патчах-кандидатах, что позволяет создавать корректные патчи для ранее невидимых приложений, что очень важно для Genesis.

Вывод пространства поиска с использованием ILP: При проектировании пространства поиска исправлений очень важно найти неотъемлемый компромисс между охватом и отслеживаемостью. С одной стороны, пространство поиска должно быть достаточно большим, чтобы содержать правильное исправление (покрытие) для целевого класса дефектов; с другой стороны, пространство поиска должно быть достаточно маленьким, чтобы система генерации исправлений могла эффективно исследовать дефекты. пространство и найти правильный патч (отслеживаемый пол).

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

2. Обоснование конверсии

Далее мы рассмотрим алгоритм вывода преобразования Genesis на примере. Genesis использует набор успешно обученных искусственных патчей, чтобы вывести набор патчей для создания преобразований. В нашем примере обучающий набор состоит из 963 человеческих патчей, индивидуально отфильтрованных из 356 репозиториев GitHub.

Патч-сэмплирование и обобщение: Алгоритм вывода Genesis обучается с использованием подмножества образцов обучающего набора. Для каждого подмножества он применяет алгоритм обобщения для вывода преобразований, которые можно использовать для создания исправлений-кандидатов. На рис. 1 показано подмножество исправлений в этом примере: первое исправление разлагает оператор mapperTypeElement==null на условный оператор if. Второй патч объединяет предложение subject!=null в оператор, который возвращает значение, а третий патч объединяет предложения Material.getMaterials(getTypeId())!=null в условный оператор if из трех разных приложений, а именно: mapstruct, modelmappe и Букки. На рис. 1 Genesis обобщает эти исправления, чтобы вывести преобразование P1, которое при применении может генерировать все три выбранных исправления, а также другие исправления для других приложений.

Структура шаблона: Для каждого преобразования есть шаблон. В нашем случае шаблон V0 ==> ((V3)op2(null))op1(V0) (графически этот шаблон показан на рис. 1). Преобразование имеет начальный шаблон AST T0, который соответствует логическому выражению V0 в неисправленном. V0 должен появиться в теле функции (если все обучающие патчи изменили условия if, то T0 будет отражать более конкретный контекст). Преобразование также имеет замещающий шаблон AST T1, который заменяет соответствующее логическое выражение V0 исправлением формы ((V3)op2(null))op1(V0). Здесь V3, op2 и op1 — несовпадающие переменные шаблона. Каждая такая переменная связана с генератором, который перечисляет компоненты кода-кандидата переменной.

Ограничения генератора: ограничения генератора управляют компонентами, которые генератор будет перечислять. Ограничения генератора для op2 и op1 (op2 ∈ {==,! =} и op1 ∈ {&&,||}) определяют только набор операторов для перечисления. Ограничения генератора V3 управляют поддеревьями AST, перечисляемыми V3. V3 ∈ Expr указывает, что V3 является выражением, а nodes(V3) ⊆ Call∪Var указывает, что V3 может содержать только вызовы методов или ссылки на переменные. |V3|≤ 2 означает, что V3 может содержать не более 2 узлов AST.

vars(V3) ⊆ M указывает, что любые переменные, которые появляются в V3, должны также появляться в соответствующем шаблоне AST V0 (здесь M представляет набор узлов в исходном коде сопоставления). |vars(V3)| ≤ 1 означает, что в V3 может появиться не более одной переменной. вызовы(V3) ⊆ M аналогичны |вызовам(V3)| ≤ 2, что указывает на ограничения на возможные вызовы методов в V3.

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

конверсия кандидата: Genesis многократно сэмплирует обучающий патч для получения преобразований-кандидатов (из которых Genesis выберет выбранные преобразования, которые он использует для создания патчей). В нашем случае переходы-кандидаты включают предыдущие переходыP1и конвертация(P2), который добавляет условный (тернарный) оператор для защиты вычисления выражения от недостатков NP; преобразование (P3) добавить оператор if-return или if-continue, чтобы пропустить вычисление, вызывающее дефект NP; переходP4Произвольно заменить выражение новым выражением. Новое выражение может содержать бинарные операторы, условные операторы и до шести переменных и шести вызовов методов из объемлющей функции.

Но не все эти преобразования одинаково полезны. Например,P4— это слишком общее преобразование, которое может создать огромное пространство для поиска исправлений, в котором Genesis не может эффективно искать. с другой стороны,P1,P2иP3Более целенаправленные — поскольку они выводятся из концептуально схожих обучающих патчей, каждый из них генерирует гораздо меньшее пространство поиска, но содержит правильные патчи.P1,P2иP3Эффективно дополняют друг друга - они генерируют области поиска с относительно небольшим количеством общих исправлений.

рассуждение о пространстве поиска: Чтобы получить действительный набор преобразований, Genesis должен отбросить, например.P4сверхобщие преобразования и выбирать дополнительные, эффективные целевые преобразования, такие какP1,P2иP3. Genesis использует набор проверочных исправлений, выбранных из обучающих исправлений, для управления выбором преобразования. Сначала Genesis вычисляет количество проверочных исправлений, сгенерированных каждым преобразованием-кандидатом, и размер пространства поиска, сгенерированного каждым преобразованием-кандидатом при применении к коду до исправления каждого проверочного исправления.

Матрица на рисунке 2 дает четыре варианта переходаP1,P2,P3иP4и три проверочных патчаVP1,VP2иVP3. Каждое число в матрице — это количество патчей-кандидатов, сгенерированных при преобразовании кода предварительного патча, примененного к патчу проверки. Цифры, выделенные жирным зеленым цветом, указывают на то, что исправление проверки может быть сгенерировано, когда преобразование применяется к предварительно исправленному коду исправления. Эти цифры подчеркивают компромисс между охватом и отслеживаемостью, обеспечиваемой патчами-кандидатами. Для управляемого пространства поиска,P1,P2иP3Оба генерируют патч проверки. Напротив,P4Можно сгенерировать два патча проверки, но за счет неуправляемо большого пространства поиска.

Используя информацию в матрице, Genesis формулирует целочисленную линейную программу (ILP), которая максимизирует количество проверочных исправлений, которые могут быть сгенерированы выбранными преобразованиями, с учетом ограничений общего количества сгенерированных исправлений-кандидатов для всех выбранных преобразований. Случаи проверки покрытия составляют менее 5×10^4. В нашем примере ILP выбираетP1,P2иP3как выбранное преобразование и исключениеP4.

Генерация патчей: Для дефекта NP в версии DataflowJavaSDK c06125 (показанной в нижней части рисунка 1) Genesis сначала использовал метод обнаружения дефекта для создания потенциально отсортированного списка операторов для изменения. Результирующий отсортированный список включает условие if, показанное в левом нижнем углу рисунка 1. Затем Genesis применяет все выбранные преобразования (включая P1) к условию if для создания патчей-кандидатов.

На рис. 1 показано, как Genesis применяет P1 к условию if. Здесь патч создает V3 как объединение переменных, op2 как == и op3 как ||, разбивая оператор unions == null на примитивный оператор if. Патч заставляет включающую функцию innerGetOnly() возвращать предопределенное значение по умолчанию, когда union имеет значение null (вместо того, чтобы неправильно генерировать исключение нулевого указателя). Это исправление подтверждает его правильность (генерирует правильные выходные данные для всех входных данных в наборе тестов JUnit DataflowJavaSDK) и согласуется с исправлением, разработанным человеком для устранения этой уязвимости.

3. Реализация

Мы используем Genesis в наших программах Java, в этом эксперименте мы используем библиотеку ложек для анализа программ Java, в настоящее время мы поддерживаем любое приложение Java, используя систему управления проектами maven и среду тестирования JUnit.

Имея программу p, тестовый набор, по крайней мере один дефект, обнаруженный в p, и предполагаемое пространство поиска P, Genesis сначала использует алгоритм локализации дефекта для определения отсортированного списка подозрительных местоположений, связанных с дефектами в p (например, фрагмент AST). Для каждого подозрительного фрагмента AST S Genesis применяет каждое преобразование в P для создания исправлений-кандидатов. Он проверяет каждое исправление-кандидат на соответствие тестовым примерам и, если все тестовые случаи пройдены, добавляет его в сгенерированный список исправлений. Genesis разработан для использования произвольных алгоритмов локализации дефектов. Наша текущая реализация основана на подозрительных местах, известных из трассировки стека тестового набора, которые вызывают исключения Java. Genesis применяет свое предполагаемое преобразование к каждому подозрительному утверждению в ранжированном списке местоположений дефектов. Для каждого преобразования Genesis вычисляет оценку затрат, которая представляет собой среднее количество патчей-кандидатов, которые преобразование должно сгенерировать для покрытия случая проверки. Для каждого подозрительного утверждения Genesis отдает приоритет исправлениям-кандидатам, созданным в результате преобразований с более низкими показателями стоимости.

4. Экспериментальные результаты

Мы используем Genesis, чтобы рассуждать о пространстве поиска исправлений и генерировать исправления для трех классов дефектов в программах на Java: нулевой указатель (NP), выход за пределы (OOB) и приведение классов (CC). Genesis использует обучающий набор, состоящий из 483 исправлений NP, 199 исправлений OOB и 287 исправлений CC из 356 приложений с открытым исходным кодом, и выводит пространство поиска, сгенерированное 108 преобразованиями.

Наши базовые дефекты включают 20 дефектов NP, 13 дефектов OOB и 16 дефектов CC из 41 приложения с открытым исходным кодом. Все тестовые приложения собираются с GitHub и содержат до 235 тысяч строк кода. С помощью 108 предполагаемых трансформаций Genesis сгенерировал правильные заплаты для 21 из 49 дефектов (11 NP, 6 OOB и 4 CC дефекта).

PAR — это система генерации исправлений Java в прошлом, которая использовала определенные вручную шаблоны исправлений. Мы сравниваем с ним Бытие. Для того же набора тестов шаблон PAR создает правильные исправления для 10 дефектов (в частности, 7 дефектов NP и 4 дефектов OOB).

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

5. Резюме

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

6. Основной вклад этой статьи

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

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

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

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

Насколько нам известно, Genesis — это первая система, которая автоматически анализирует преобразование поколения патчей или ищет пространство патчей-кандидатов на основе ранее успешных патчей. Все экспериментальные данные (включая исходный код Genesis, шаблоны выводов и сгенерированные исправления) доступны по адресу http://groups.csail.mit.edu/pac/patchgen/.

7. Ссылки

[1] Фан Лонг и Мартин С. Ринар, 2016 г. Анализ пространств поиска для создания и проверки систем генерации исправлений, Материалы 38-й Международной конференции по программной инженерии, ICSE 2016, Остин, Техас, США, 14 мая. 22, 2016. 702–713.

[2] Dataflow Java SDK. GitHub.com/Googlecloud….

(2017).

[3] JUnit. junit.org/. (2017).