Getafix: Facebook рассказала об инструменте для автоматического исправления багов

5 декабря 2018, 15:20
Getafix: Facebook рассказала об инструменте для автоматического исправления багов

Разработчики Facebook подробно рассказали об интеллектуальном инструменте для автоисправления ошибок Getafix, созданном и развёрнутом внутри компании. Getafix учится фиксить не только те баги, которые вызывают сбои в приложениях, но и любые проблемы с кодом в принципе.

Сегодня кодовые базы достаточно сложны и постоянно обновляются. Facebook занялась созданием системы, которая способна самостоятельно искать способы исправления ошибок. Для этого был построен инструмент, который обучается на примере изменений, ранее внесённых в код самими инженерами. Он находит скрытые паттерны и на их основе подбирает наиболее вероятные способы исправить новые баги.

Инструмент под названием Getafix, развёрнутый на продакшн в Facebook, обеспечивает стабильность приложений, которыми пользуются миллиарды людей. Getafix работает в связке с двумя другими инструментами Facebook, но может использоваться для решения проблем с кодом, обнаруженных любыми средствами. На сегодня он может рекомендовать способы исправить баги, найденные Infer — статическим анализатором, который определяет ошибки вроде NullPointerException в Android— и Java-коде. Через SapFix инструмент предлагает исправления ошибок, обнаруженных Sapienz — ИИ-системой автоматизированного тестирования ПО от Facebook.

Цель Getafix — переложить выполнение рутинной работы на компьютер, но под пристальным контролем человека, который будет принимать решения в случае, если баг требует сложного нетривиального подхода. Инструмент применяет новый метод иерархической кластеризации к тысячам уже готовых изменений, сделанным инженерами, и при этом учитывает как саму правку, так и её контекст. Такой метод позволяет выявить закономерности в багах и подобрать соответствующие патчи, что было недоступно для предыдущих инструментов для автономного исправления ошибок.

Помимо этого, Getafix сужает область поиска нужного исправления среди возможных программных изменений, что позволяет ему подбирать подходящий патч значительно быстрее, чем в случае с методом перебора или логическими методами. Этот подход более эффективен и позволяет развёртывать Getafix в среде эксплуатации. Вместе с тем, так как Getafix обучается на предыдущих правках кода, инженерам-людям легко понимать предлагаемые им исправления.

Getafix автоматически предлагает исправления багов при разыменовании указателя, найденных Infer, а также связанных с разыменованием указателя сбоях, которые получены из Sapienz. Также он используется для разрешения вопросов к качеству кода, которые возникают при проверке существующего кода более новыми версиями Infer.

Отличия Getafix от более примитивных инструментов автоисправления

В нынешней промышленной практике автоисправления в основном применяют в элементарных ситуациях, поскольку решения к ним очевидны. Например, анализатор может предупредить об ошибке «dead exception», когда разработчик забыл добавить throw перед new Exception(...).  Здесь требуется достаточно простое автоисправление, и оно может быть определено автором правила проверки соблюдения стандартов кодирования без учёта непосредственного контекста, в котором оно будет применяться.

Getafix открывает гораздо более широкие возможности: он применим в случаях, когда исправление ошибки зависит от её контекста. В отрывке кода ниже Getafix предлагает следующее изменение бага, найденного Infer, в строке 22:

Стоит отметить, что изменение учитывает не только переменную ctx, но и возвращаемый тип метода. В отличие от простых lint-изменений ошибок, подобные исправления нельзя внедрить в сам Infer.

Ниже представлены другие примеры патчей, которые Getafix рекомендует для багов Infer. Хотя баг один и тот же (вызов метода через нулевой указатель, что грозит выбросом NullPointerException), все исправления — разные. Но при этом неотличимы от тех, которые сделал бы разработчик-человек.

Ключевые технические детали

Как показано на схеме ниже, Getafix представляет собой цепочку инструментов. В данном разделе описан функционал и сложности его трёх основных компонентов.

Дифференциатор на основе деревьев распознаёт изменения на уровне дерева

Для начала применяется дифференциатор на основе абстрактного синтаксического дерева (AST) для выявления конкретных правок, сделанных между парой исходных файлов, например двух последовательных версий одного файла. Так, он найдёт конкретные изменения, вроде добавления оператора if, вставки аннотации @Nullable или оператора import, или же подстановки оператора раннего возврата return с условием в тело существующего метода. В следующем примере предложены такие изменения, как вставка раннего возврата, если значение dog — пустое, переименование public в private, а также перемещение метода. В то время как построчный дифференциатор оба метода отметил бы как полностью удалённые или вставленные, дифференциатор на основе деревьев распознаёт перемещение, и поэтому распознаёт вставку внутри перемещённого метода как конкретное изменение.

Сложность для такого дифференциатора состоит в том, чтобы эффективно и точно выстроить части деревьев «до» и «после», чтобы найти правильные конкретные исправления и соотнести их в исходном и новом деревьях.

Новый способ поиска паттернов исправления

Getafix выполняет поиск паттернов с помощью нового метода иерархической кластеризации, наряду с антиунификацией — существующей техникой генерализации разных символьных выражений. Далее он создаёт набор возможно связанных различий деревьев и использует паттерны исправления, являющиеся наиболее распространёнными для того набора. Эти паттерны могут быть абстрактными, содержать «дыры», где программные преобразования отличаются.

В следующем примере изображена иерархическая структура, известная как дендрограмма, которая получается в результате ряда изменений. (В данном случае на ней показаны правки из примера выше.) Каждый ряд показывает паттерн исправления («до» — фиолетовым цветом и «после» — синим), а также некоторые метаданные. Каждая вертикальная чёрная полоса соответствует уровню иерархии, где паттерн исправления вверху полосы получен путём антиунификации всех других изменений, принадлежащих этому уровню иерархии. Другие изменения соединены более тонкими чёрными линиями. Антиунификация комбинирует правку «early return if dog == null» из предыдущего примера с другим изменением, в котором единственная разница в том, что собака пьёт. Результат — абстрактный паттерн исправления, который отражает общее. Символ h0, появившийся после антиунификации, указывает на «дыру», которой можно присвоить значение в зависимости от контекста.

Далее этот паттерн исправления можно совместить с другими паттернами, в которых больше варьируются имена переменных, но которые имеют схожую общую структуру. В результате этого процесса генерируются всё более абстрактные паттерны исправления по мере продвижения вверх по дереву. Например, можно было бы соединить это исправление с исправлением, связанным с котом, чтобы получить абстрактное исправление, которое будет показано ближе к верху диаграммы.

Что ещё важнее, этот процесс иерархического сопоставления даёт Getafix мощный фреймворк для подбора паттернов изменений кода многоразового использования. Дендрограмма ниже (повёрнута горизонтально и уменьшена) получена путём комбинации всех 2288 исправлений ошибок нулевого указателя, найденных Infer в кодовой базе Facebook за некоторый период времени. Паттерны правок, которые нужно получить, находятся в этой дендраграмме.

Идея паттерна на основе антиунификации не нова, однако для поиска паттернов, которые могут использоваться для генерации (и ранжирования) относительно небольшого числа вариантов корректировки новых багов, требовались некоторые улучшения.

Одно из таких изменений — включение части окружающего кода, который остаётся неизменным после правки. Это нововведение позволяет не только находить закономерности в исправлениях, сделанных людьми, но и закономерности контекста, в котором применяются эти исправления. Например, на первой дендрограмме выше видно два отдельных исправления, добавляющих if (dog == null) return; перед dog.drink(…);. Хотя фрагмент dog.drink(…); не меняется, он включён в части паттерна «до» и «после» в качестве контекста, указывающего, где применять эту правку. На более высоком уровне иерархии исправлений, контекст dog.drink() соединяется с другим контекстом и становится абстрактным контекстом h0.h1(), который ограничивает места, где может применяться этот паттерн. Более практичный пример приведён в следующем разделе.

Жадный алгоритм кластеризации, как утверждают в литературе по инструментам автоисправления, не будет узнавать этот контекст. Это объясняется тем, что такой алгоритм поддерживает только одно представление каждого кластера, которое не будет содержать дополнительный контекст, если он не присутствует во всех исправлениях в тренировочных данных. К примеру, если изменение вводит  if (list ! = null) return; до слияния do(list.get()); с примерами dog.drink() выше, жадная кластеризация потеряет весь контекст, в котором вставляется ранний возврат. Подход иерархической кластеризации в Getafix позволяет удержать по возможности максимум контекста на каждом уровне, становясь более обобщённым кверху структуры. На определённом уровне даже общий контекст, который нужно было бы знать, потеряется, но всё равно сохранится на более низких уровнях структуры.

Помимо окружающего кода, исправления также сверяются с баг-репортами Infer, которые вызвали необходимость корректировок. Это позволяет установить связь между паттернами исправления и соответствующими отчётами о багах. Переменная, на которую Infer жалуется в отчёте, показана как «errorVar» в первой дендраграмме выше и присутствует в антиунификации, в результате чего преобразуется в h0. Это позволит впоследствии, при получении нового баг-репорта из Infer, заменить виновную переменную на h0, сделав паттерн исправления более точным.

Как Getafix создаёт патчи

Финальный шаг — взять бажный исходный код и паттерны исправления из предыдущего шага по их поиску и сгенерировать новую версию кода с учётом правок. Обычно находится много паттернов правок, как это было видно из дендраграммы выше. Трудность на этом этапе заключается в том, чтобы подобрать верный паттерн для исправления определённого бага. Если паттерн применим в нескольких местах, Getafix должен подобрать точное соответствие. Следующие примеры демонстрируют базовый подход Facebook и то, как инструмент решает эту проблему.

Пример 1. Подобранный выше паттерн h0.h1(); → if (h0 == null) return; h0.h1();.

Вот краткое описание шагов Getafix по созданию следующего патча для ранее не известного кода:

  1. найти абстрактное синтаксическое поддерево, соответствующее части «до»: mListView.clearListeners();
  2. инстанциировать h0 и h1
  3. заменить абстрактное синтаксическое поддерево на инстанциированную часть «после»

Добавление h0 в части «после» обязательно из-за включения неизменного контекста h0.h1();, который удобным образом ограничивает количество мест, где можно применить паттерн. Без неизменного контекста паттерн был бы <nothing> → if (h0 == null) return;. Этот паттерн применим в незапланированных местах, например после mListView.clearListeners(); или даже после mListView = null;.

Паттерн на основе только включения также появится выше в дендраграмме, где паттерн с контекстом h0.h1(); антиунифицирован в паттерном, вставляет возврат перед другим оператором. Следующий пример иллюстрирует то, как Getafix работает с паттернами, которые кажутся применимыми в слишком большом количестве мест.

Пример 2. Паттерн h0.h1() → h0! =null && h0.h1().

Обычно такой патч получается из исправлений внутри условий if или выражений return, поэтому будет применим в таких случаях. Но он также подходит для других ситуаций, таких как оператор вызова из примера выше: mListView.clearListeners();. Стратегия ранжирования Getafix состоит в оценке вероятности того, что тот или иной паттерн действительно является исправлением и что это наиболее подходящее исправление в данном контексте. Такая стратегия снижает зависимость системы от будущего шага валидации, позволяя сберечь время.

Паттерн выше будет соревноваться с другими паттернами, например более специфичным if (h0.h1()) { … } → if (h0! =null && h0.h1()) { … } или паттерном из примера 1, который применим только к операторам вызова, а не выражениям. Более специфичные паттерны подходят в меньшем количестве мест, и поэтому считаются больше предназначенными для данной ситуации, поэтому Getafix ставит их выше.

Реализация и результативность

Getafix автоматически предлагает исправления багов при разыменовании указателя, обнаруженных статическим анализатором Infer, а также связанных с разыменованием указателя сбоях, отправленных Sapienz. Также он используется для исправления найденных Infer багов, которые были упущены ранее.

В одном из экспериментов Facebook сравнила исправления, сгенерированные Getafix, с исправлениями разработчиков для одинаковых ошибок вызова метода через нулевой указатель, найденных Infer, на примере датесета из более чем 200 небольших исправлений, в которых изменялось менее 5 строк. В 25 процентах случаев наиболее вероятный, по мнению Getafix, патч был идентичен патчу, написанному человеком.

В ходе другого эксперимента, где рассматривалось подмножество кодовой базы Instagram, стояла задача исправить сразу 2000 таких ошибок. Getafix предложил патчи к 60 процентам багов. Около 90 процентов из них прошли автоматическую валидацию, то есть были компилируемы и Infer больше не выбрасывал оповещение. В целом Getafix смог самостоятельно исправить 1077 (около 53 процентов) багов.

Помимо рекомендаций исправления поступающих от Infer багов, Facebook использует ту же инфраструктуру для подчистки бэклога багов, которые прошли ревью попали в кодовую базу. Getafix устранил сотни ошибок return not nullable и field not nullable, найденных Infer. Автоисправления к этим ошибкам позволили повысить общие показатели их исправления с 56 до 62 процентов и с 51 до 59 процентов соответственно. По словам Facebook, за последние три месяца около двухсот дополнительных багов было исправлено потому, что Getafix сделал соответствующие рекомендации.

Исправления Getafix используются инструментом SapFix для устранения неполадок, найденных Sapienz. За последние месяцы Getafix сделал около половины возможных рекомендаций, которые SapFix применяет и валидность которых подтверждает. Около 80 процентов возможных исправлений Getafix проходят все тесты.

Значение Getafix

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

Интеллектуальные инструменты статического анализа, такие как Getafix, способны вывести на новый уровень все этапы жизненного цикла разработки ПО, в том числе качество кода и эксплуатационную эффективность.

Обсуждение