Автоматик коде. СанктПетербургский государственный
 Скачать 0.58 Mb.
|
Алгоритм работы инструмента ProphetНа вход инструменту Prophet подается исходный код программы на C и набор положительных и отрицательных тестов, выявляющих ошибку. На основе входных данных происходит локализация дефек- та и в дальнейшем валидация сгенерированных исправлений. Полный процесс исправления ошибки схематически показан на рис. 1. На этапе локализации происходит анализ потоков выполнения про- граммы, запущенной на предоставленных тестах. В результате выдает- ся упорядоченный список локаций с вероятностью содержания ошиб- ки, где наибольший приоритет имеют утверждения, которые 1) часто выполняются на отрицательных тестах, 2) редко выполняются на поло- жительных тестах и 3) выполняются позже на отрицательных тестах. На следующем этапе Prophet генерирует множество всевозможных  Рис. 1: Алгоритм работы Prophet исправлений, каждое из которых изменяет одно утверждение в найден- ной локации. Prophet использует правила трансформации, идентичные SPR[9], а именно: изменение условия (TightenCondition, LoosenCondition), добавление условия (Guard, SpecialGuard), условное добавление управляющего утверждения (IfExit), добавление инициализации переменной (AddInit), изменение утверждения и значения переменной (Replace, ReplaceString), добавление измененного утверждения (AddAndReplaceKind). Данный этап определяет классы ошибок, которые инструмент мо- жет исправить, и, следовательно, задает пространство поиска кандида- тов. В дальнейшем происходит извлечение универсальных признаков у сгенерированных изменений: признаки состояния – свойства, отвечающие за взаимодействие переменных, входящих в область изменения; признаки модификаций – свойства, фиксирующие вид изменений и различия между исходным и сгенерированным утверждением и его окружающими утверждениями. Например, для исходного и измененного утверждения будут вычис- ляться признаки входящих в них переменных, зависимости между эти- ми переменными, вид утверждения, признаки трех предшествующих и трех последующих утверждений, вид исправления. На этапе ранжирования подсчитывается вероятностная оценка кан- дидатов с использованием заранее обученной модели. На финальную оценку кандидата, влияют не только универсальные признаки исправ- ления, но и вероятностная оценка места, полученная на этапе локали- зации. Данный этап определяет порядок обхода кандидатов. В результате упорядоченные кандидаты проходят поочередную ва- лидацию: вначале каждый кандидат пытается пройти негативные тесты и в случае успеха – положительные. Из-за пересборки проекта и запус- ка тестов данный этап является самым долгим и ресурсозатратным, поэтому правильный порядок обхода кандидатов очень важен. На рис. 2 показан пример исправления ошибки неучтенной едини- цы1. Слева разработчик неправильно определил границы цикла: индекс должен был быть строго меньше PATH_SIZE, чтобы массив не вы- шел за свои границы. Справа показано сгенерированное исправление Prophet. Если индекс равен 60, то цикл заканчивает свое выполнение, что соответствует корректному поведению, так как размер массива ра- вен 60 (PATH_SIZE). Для обучения модели корректного кода используется 778 примеров. На этапе обучения Prophet выполняет: для каждого изменения в тренировочном наборе данных Prophet анализирует структурные отличия AST в изменении разработчи- ка и проверяет, что изменение программиста находится в про- странстве поиска Prophet; 1Ошибка неучтенной единицы (ошибка off-by-one) — логическая ошибка в алгоритме, заключающая в неправильном определении границ величины ровно на единицу.  Рис. 2: Исправление ошибки неучтенной единицы инструментом Prophet происходит имитация работы локализатора: в исходном коде с помощью аппроксимации локализатора находятся потенциальные места с дефектом; в найденных местах и в известной локации с ошибкой происходит генерация изменений; из каждого кандидата извлекаются признаки; модель обучается так, чтобы уменьшить среднюю долю канди- датов, которые имеют ранг выше, чем правильное исправление разработчика. |