Автоматическое исправление программ

Представьте ночной прогон CI. Один тест из двенадцати тысяч стал красным. Утром дежурный инженер откроет логи, полчаса будет искать, где именно ломается, ещё двадцать минут — писать однострочную правку, и ещё час она будет ехать через ревью. Правка при этом окажется скучной: забытая проверка на null, < вместо <=, не тот аргумент в вызове.

Automated Program Repair (APR) задаёт наглый вопрос: а зачем здесь человек? Если у нас есть программа, тест, который её ловит на ошибке, и набор тестов, фиксирующих желаемое поведение, — то «починить баг» это ровно задача поиска: найти в пространстве правок исходного кода такую, после которой все тесты зелёные. А поиск мы уже умеем: локальный, популяционный, над деревьями программ, многокритериальный.

APR — самая известная и самая спорная витрина SBSE. Известная, потому что здесь поиск делает то, что раньше считалось исключительно человеческой работой. Спорная, потому что вся конструкция держится на одном шатком допущении: тест-сьют — корректная спецификация программы. Он ей не является. Половина этой статьи — про то, как поиск чинит баги, вторая половина — про то, как он при этом врёт, и что с этим делают.

Постановка задачи

Дано:

• программа $P$, которая не проходит хотя бы один тест;
• набор тестов $T = T_{\text{fail}} \cup T_{\text{pass}}$, где $T_{\text{fail}} \ne \varnothing$ — падающие (они и воспроизводят баг), $T_{\text{pass}}$ — зелёные (они фиксируют то, что ломать нельзя);
• пространство правок $\Delta$ — какие изменения кода мы вообще разрешаем себе делать.

Найти патч $\delta \in \Delta$ такой, что программа $\delta(P)$ проходит весь $T$.

Три термина, которые нужно развести раз и навсегда, иначе весь дальнейший разговор рассыпается:

Поиск оптимизирует правдоподобность, потому что только её он умеет измерять. Нам же нужна корректность. Между этими двумя множествами — пропасть, и вся инженерия APR построена вокруг неё.

Тест-сьют играет здесь роль оракула: он одновременно задаёт цель поиска (падающие тесты — что чинить) и ограничения (зелёные тесты — регрессии запрещены). Это классический паттерн из статьи про фитнес-функции: цель дешёвая, приближённая и систематически смещённая — а мы всё равно ею пользуемся, потому что альтернатива (формальная спецификация) в реальном проекте недоступна.

Канонический пайплайн

Почти все инструменты семейства generate-and-validate устроены одинаково:

Обратите внимание на порядок в блоках E и G: сначала гоняем только падающие тесты (их единицы), и лишь выжившие кандидаты проверяем полным сьютом (их тысячи). Это не деталь реализации, а главная оптимизация всей схемы — к цене мы вернёмся отдельно.

Шаг 1: локализация дефекта

Пространство «любых правок любой строки» огромно. Чтобы поиск был осмысленным, нужно ранжировать места программы по подозрительности. Классический метод — spectrum-based fault localization (SBFL): инструментируем код, для каждого теста записываем множество выполненных строк и сравниваем покрытие падающих и проходящих тестов.

Интуиция в одну фразу: строка подозрительна, если её выполняют падающие тесты и не выполняют зелёные.

Для строки $s$ считаем четыре числа: $e_f$ — сколько падающих тестов её выполнили, $n_f$ — сколько падающих не выполнили, $e_p$ и $n_p$ — то же для зелёных. Формулы:

$$ \text{Tarantula}(s) = \frac{\dfrac{e_f}{e_f + n_f}}{\dfrac{e_f}{e_f + n_f} + \dfrac{e_p}{e_p + n_p}} \qquad \text{Ochiai}(s) = \frac{e_f}{\sqrt{(e_f + n_f),(e_f + e_p)}} \qquad \text{DStar}(s) = \frac{e_f^{,2}}{e_p + n_f} $$

Эмпирически Ochiai (Abreu et al., 2007) стабильно обходит Tarantula, а DStar с показателем 2 — примерно на её уровне. Сложность SBFL: одна инструментированная сборка плюс один прогон сьюта, $O(|T| \cdot \ell)$ по времени и $O(|T| \cdot \ell)$ по памяти для матрицы покрытия, где $\ell$ — число строк; на практике матрицу хранят разреженно или агрегируют на лету.

Честное предупреждение: SBFL работает хуже, чем принято думать. В работе Pearson et al. (ICSE 2017) показано, что результаты, полученные на искусственно засеянных дефектах, не переносятся на реальные: на настоящих багах из Defects4J дефектная строка попадает в top-1 в единицах процентов случаев. Поэтому современные инструменты либо смотрят top-100 и глубже, либо усиливают SBFL:

• мутационная локализация (Metallaxis, MUSE) — вносим мутацию в строку и смотрим, меняется ли результат тестов; сигнал сильнее, цена — на порядок выше;
• срезы программ (dynamic slicing) — оставляем только то, что реально влияет на упавшее утверждение;
• история изменений — недавно изменённые строки подозрительнее (в проде это самый сильный признак);
• learning-to-rank поверх десятков признаков (DeepFL, GRACE).

Шаг 2: пространство патчей и операторы правки

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

Гипотеза избыточности

GenProg — исторически первый успешный APR-инструмент (Weimer et al., ICSE 2009) — сделал ставку на смелую идею: исправление уже есть где-то в этом же проекте. Не нужно синтезировать новый код, достаточно скопировать существующую инструкцию из другого места файла. Отсюда три оператора правки: delete (удалить инструкцию), insert (вставить копию донорской инструкции) и replace (заменить одну на другую).

Гипотеза не взята с потолка. Barr et al. в работе «The Plastic Surgery Hypothesis» (FSE 2014) измерили её на истории 12 Java-проектов: около 30 % изменений полностью собираются из фрагментов, уже присутствующих в кодовой базе на момент коммита, а при разбиении на более мелкие куски доля растёт до 43 %. Программисты действительно копипастят, и APR это эксплуатирует.

Шаблоны исправлений

Второй подход — не искать донора, а применять шаблоны, извлечённые из истории человеческих правок. PAR (Kim et al., ICSE 2013) вручную выделил десяток паттернов: добавить проверку на null, поменять границу цикла, добавить try/catch, заменить вызванный метод на однотипный, изменить параметр. TBar (Liu et al., ISSTA 2019) довёл идею до 35 шаблонов и показал, что грамотный шаблонный инструмент бьёт большинство «умных» эволюционных.

Практический вывод, который стоит запомнить: сужение пространства поиска правильными априорными знаниями почти всегда сильнее, чем улучшение самого алгоритма поиска. Это универсальный урок SBSE, но в APR он виден особенно ярко.

Гранулярность

Шаг 3: фитнес-функция и её плоскость

Классический фитнес GenProg — взвешенное число пройденных тестов:

$$ f(\delta) = w_{\text{fail}} \cdot |{t \in T_{\text{fail}} : \delta(P) \text{ проходит } t}| + w_{\text{pass}} \cdot |{t \in T_{\text{pass}} : \delta(P) \text{ проходит } t}| $$

с $w_{\text{fail}} > w_{\text{pass}}$ (обычно 10 против 1) — иначе поиск предпочтёт «ничего не сломать» вместо «что-нибудь починить».

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

Как с этим борются:

• более мелкозернистый сигнал вместо булева «прошёл/не прошёл»: branch distance до нужной ветки, расстояние между ожидаемым и фактическим значением в ассерте, число совпавших байт вывода (тот же приём, что в генерации тестов);
• вторая цель — размер патча, что превращает задачу в многокритериальную; маленький патч почти всегда предпочтительнее большого при равной правдоподобности;
• признание, что градиента нет, и переход к систематическому перебору пространства правок вместо эволюции (так устроены AE, RSRepair, PraPR, TBar — и они не хуже).

Последний пункт заслуживает отдельного упоминания. RSRepair (Qi et al., ICSE 2014) заменил генетический поиск GenProg на случайный — и починил столько же багов быстрее. Это не аргумент против SBSE, а аргумент за честный baseline: если у фитнеса нет градиента, кроссовер и селекция работают вхолостую, а вся полезная работа делается операторами мутации и локализацией.

Рабочий пример: мини-APR на Python

Соберём игрушечный, но полностью рабочий инструмент: локализация Ochiai по трассам исполнения, поиск патча случайной мутацией AST с весами по подозрительности, минимизация патча в конце. Всё на стандартной библиотеке.

"""Мини-APR: локализация -> поиск патча -> минимизация."""
import ast, copy, random, sys, textwrap

BUGGY = textwrap.dedent("""
    def classify(n):
        if n < 0:
            return "negative"
        if n == 0:
            return "negative"       # БАГ: должно быть "zero"
        if n % 2 == 0:
            return "even"
        return "odd"

    def _donor_pool_unused(n):
        return "zero"               # донор: нужная строка есть в проекте
""")

TESTS = [(-3, "negative"), (0, "zero"), (4, "even"),
         (7, "odd"), (-1, "negative"), (2, "even")]


def label_statements(tree):
    """Присваиваем каждой инструкции стабильный id: deepcopy его сохраняет."""
    sid = 0
    for node in ast.walk(tree):
        for _, value in ast.iter_fields(node):
            if isinstance(value, list):
                for item in value:
                    if isinstance(item, ast.stmt):
                        item.sid = sid
                        sid += 1
    return sid


def find_slot(tree, sid):
    """Ищем инструкцию по id и возвращаем (список-владелец, индекс) — точку правки."""
    for node in ast.walk(tree):
        for _, value in ast.iter_fields(node):
            if isinstance(value, list):
                for i, item in enumerate(value):
                    if isinstance(item, ast.stmt) and getattr(item, "sid", None) == sid:
                        return value, i
    return None, None


def run_tests(tree, filename="<patch>"):
    """Компилируем дерево, гоняем тесты, попутно снимая трассу выполненных строк."""
    try:
        code = compile(ast.fix_missing_locations(copy.deepcopy(tree)), filename, "exec")
    except (SyntaxError, ValueError):
        return [False] * len(TESTS), {}       # не собралось — фитнес нулевой
    ns = {}
    try:
        exec(code, ns)
    except Exception:
        return [False] * len(TESTS), {}
    fn, results, traces = ns.get("classify"), [], {}
    for i, (arg, expected) in enumerate(TESTS):
        hit = set()

        def tracer(frame, event, _arg, hit=hit):
            if event == "line" and frame.f_code.co_filename == filename:
                hit.add(frame.f_lineno)
            return tracer

        sys.settrace(tracer)                  # в проде тут coverage.py или JaCoCo
        try:
            ok = fn(arg) == expected
        except Exception:
            ok = False
        finally:
            sys.settrace(None)
        results.append(ok)
        traces[i] = hit
    return results, traces


def ochiai(results, traces, line_of):
    """Подозрительность строки: часто в падающих тестах и редко в зелёных."""
    total_fail = sum(1 for r in results if not r)
    susp = {}
    for sid, line in line_of.items():
        ef = sum(1 for i, r in enumerate(results) if not r and line in traces.get(i, ()))
        ep = sum(1 for i, r in enumerate(results) if r and line in traces.get(i, ()))
        denom = (total_fail * (ef + ep)) ** 0.5
        susp[sid] = ef / denom if denom else 0.0
    return susp


def apply_edits(base, edits):
    """Патч — это СПИСОК правок, а не изменённый файл. Так его легко минимизировать."""
    tree = copy.deepcopy(base)
    for op, target, donor in edits:
        body, idx = find_slot(tree, target)
        if body is None:
            continue                          # правка «повисла» после предыдущей — пропускаем
        if op == "delete":
            body[idx] = ast.Pass()
        elif op == "insert":
            body.insert(idx, copy.deepcopy(donor))
        elif op == "replace":
            body[idx] = copy.deepcopy(donor)
    return tree

Сам поиск — намеренно примитивный: случайная мутация с вероятностным выбором места по Ochiai. Это и есть baseline, который стоит побить, прежде чем строить полноценный ГА.

def mutate(edits, susp, donors, sids, rng):
    """Место правки выбираем со смещением к подозрительным инструкциям."""
    weighted = [s for s in sids for _ in range(int(susp.get(s, 0) * 10) + 1)]
    op = rng.choice(["delete", "insert", "replace"])
    return edits + [(op, rng.choice(weighted), rng.choice(donors))]


def fitness(tree):
    return sum(run_tests(tree)[0])


def repair(rng=random.Random(7), budget=400):
    base = ast.parse(BUGGY)
    label_statements(base)
    line_of = {s.sid: s.lineno for n in ast.walk(base)
               for _, v in ast.iter_fields(n) if isinstance(v, list)
               for s in v if isinstance(s, ast.stmt)}

    results, traces = run_tests(base)
    susp = ochiai(results, traces, line_of)          # шаг 1: локализация
    donors = [s for n in ast.walk(base) for _, v in ast.iter_fields(n)
              if isinstance(v, list) for s in v if isinstance(s, ast.stmt)]

    best, best_fit = [], sum(results)
    for gen in range(budget):                        # шаг 2: поиск
        cand = mutate(best if rng.random() < 0.3 else [], susp, donors, list(line_of), rng)
        f = fitness(apply_edits(base, cand))
        if f > best_fit:
            best, best_fit = cand, f
            print(f"поколение {gen}: фитнес {f}/{len(TESTS)}")
        if best_fit == len(TESTS):
            break

    if best_fit < len(TESTS):
        return None
    for e in list(best):                             # шаг 3: минимизация
        trial = [x for x in best if x is not e]
        if fitness(apply_edits(base, trial)) == len(TESTS):
            best = trial
    return ast.unparse(apply_edits(base, best))


print(repair())

Вывод:

поколение 6: фитнес 6/6
def classify(n):
    if n < 0:
        return 'negative'
    if n == 0:
        return 'zero'
    ...

Шесть случайных мутаций — и патч найден, причём семантически корректный, а не просто зелёный. Три вещи в этом коде — не упрощения, а настоящие проектные решения промышленных APR:

1. Патч представлен списком правок, а не текстом. Это даёт бесплатную минимизацию (выкидываем правку — тесты всё ещё зелёные? значит, она была лишней) и осмысленный кроссовер: потомок = конкатенация или подмножество списков родителей.
2. Донорский пул — код того же проекта. Уберите _donor_pool_unused — и поиск не сойдётся никогда, потому что строки return "zero" неоткуда взять. Гипотеза избыточности здесь не украшение, а условие существования решения.
3. Минимизация обязательна. Без неё поиск с удовольствием отдаст патч из семи правок, шесть из которых — шум, случайно не сломавший тесты.

Стоит убрать один тест — например, (2, "even") — и вы своими глазами увидите переобучение: поиск начнёт находить патчи вроде «удалить проверку чётности», которые тоже зелёные, но неверные.

Цена поиска: где на самом деле уходит время

Асимптотика APR обманчиво проста. Пусть $G$ — число поколений, $\Pi$ — размер популяции, $|T|$ — число тестов, $t_{\text{test}}$ — время одного теста, $t_{\text{build}}$ — время сборки.

$$ \text{Cost} \approx G \cdot \Pi \cdot \big(t_{\text{build}} + |T| \cdot t_{\text{test}}\big) $$

Всё остальное — мутации, обход AST, вычисление подозрительности — исчезающе мало на этом фоне. Поэтому вся инженерия APR это инженерия валидации патчей:

Историческая калибровка масштаба: работа Le Goues et al. «A systematic study of automated program repair: fixing 55 out of 105 bugs for \8 $ each» (ICSE 2012) чинила дефекты примерно за 8 долларов облачного времени каждый. Дёшево по сравнению с инженером — если патч корректен. Именно это «если» и оказалось проблемой.

Переобучение под тесты: центральная проблема APR

В 2015 году Qi, Long, Achour и Rinard (ISSTA 2015) вручную проверили патчи, которые GenProg, RSRepair и AE сгенерировали для 105 дефектов бенчмарка ManyBugs. Результат оказался разрушительным: корректными были 2, 2 и 3 патча соответственно. Остальные проходили тесты, не решая задачу: удаляли функциональность, роняли ветку кода целиком, обрезали цикл.

Контрольный выстрел там же — инструмент Kali, который умеет только удалять код и ничего больше. Kali «починил» сопоставимое число дефектов. Вывод: заявленные успехи объяснялись не мощью эволюционного поиска, а слабостью тестовых наборов.

Логика провала прозрачна. Тест-сьют задаёт конечное число точек поведения. Патч, зафиксировавший поведение ровно в этих точках и сломавший его во всех остальных, для фитнес-функции неотличим от настоящего исправления. Это буквально переобучение из машинного обучения: тест-сьют — обучающая выборка, реальные входы — тестовая, а APR-инструмент оптимизирует train-loss.

Жизненный цикл кандидата удобно смотреть как автомат — он же показывает, где именно теряется корректность:

Как реально борются с переобучением

• Догенерировать тесты. Прогнать EvoSuite или фаззер на исходной программе, зафиксировать её поведение как регрессионный оракул, и требовать, чтобы патч его не ломал вне области бага. Подход UnsatGuided (Yu et al., EMSE 2019) отсеивает заметную долю переобученных патчей, но не все — сгенерированные тесты сами наследуют баг.
• Дифференциальное тестирование патчей. Если два правдоподобных патча расходятся в поведении на каком-то входе — этот вход отличный кандидат в новый тест. Ровно то же, что мутационное тестирование делает с мутантами.
• Минимальность как второй критерий. Оптимизируем по Парето: «число зелёных тестов» против «размер diff». Патчи-удаления по-прежнему проходят, но конкурируют с точечными правками.
• Априорная правдоподобность кода. Оценить патч языковой моделью кода: настоящие исправления выглядят как человеческий код, а if (false) в середине функции — нет. Эта идея и привела APR к нейросетевым подходам.
• Не автоматизировать merge. Самое действенное. В проде патч почти всегда идёт человеку как предложение, а не в мастер напрямую.

Семейства подходов

Семантический ремонт

Generate-and-validate угадывает патч и проверяет тестами. Семантический подход идёт с другой стороны: выводит ограничения, которым патч обязан удовлетворять, и синтезирует выражение, им отвечающее.

Схема SemFix (Nguyen et al., ICSE 2013) и Angelix (Mechtaev et al., ICSE 2016):

1. локализуем подозрительное выражение (условие if, правую часть присваивания);
2. заменяем его символьной переменной $\alpha$;
3. символьным исполнением находим ангельские значения — какие значения $\alpha$ на каждом тесте заставляют программу вести себя правильно;
4. решаем задачу синтеза: найти минимальное выражение над доступными переменными и константами, которое на всех тестах даёт эти значения (component-based synthesis через SMT-решатель);
5. подставляем найденное выражение обратно.

Сильные стороны: патч по построению удовлетворяет всем тестам, ищется минимальное выражение (DirectFix прямо формулирует это как MaxSMT), правки точечные и читаемые. Слабые: нужно символьное исполнение всей программы — а это взрыв путей, проблемы с указателями, внешними вызовами, многопоточностью. На больших C/Java-проектах масштабируется тяжело. Nopol сузил задачу до починки только условных выражений и за счёт этого стал практичным.

Переобучение здесь тоже есть — просто перенесено внутрь синтезатора: он подгоняет выражение под конечное число ангельских значений. Но пространство ограничено «маленькими выражениями над реальными переменными», и это само по себе сильный регуляризатор.

Обучаемый ремонт и LLM

Если у нас есть миллионы пар «код до коммита — код после», можно просто выучить отображение. SequenceR (Chen et al., TSE 2019) поставил задачу как машинный перевод: вход — падающая строка плюс контекст, выход — исправленная строка, с copy-механизмом для копирования идентификаторов. CoCoNuT и CURE (2020–2021) добавили ансамбли, предобучение на коде и учёт контекста.

Перелом дала AlphaRepair (Xia, Zhang, FSE 2022): вместо обучения «переводу» они заменили подозрительную строку на маску и попросили предобученную модель кода (CodeBERT) её заполнить — zero-shot, без обучения на парах патчей. Результат превзошёл все тренированные системы. Дальше ChatRepair и агентные подходы к SWE-bench (Jimenez et al., ICLR 2024) встроили в цикл обратную связь: показать модели сообщение об ошибке от упавшего теста и попросить попробовать снова.

Внимательный читатель заметит: это тот же цикл generate-and-validate, только генератором кандидатов вместо мутаций AST служит языковая модель. Всё, что мы обсуждали, остаётся в силе — локализация нужна, валидация тестами нужна, переобучение никуда не делось. Изменилось качество распределения кандидатов: LLM генерирует правдоподобный человеческий код, а не случайные перестановки инструкций. Об этой преемственности — подробно в заключительной статье трека.

Две ловушки оценки, о которых нужно знать:

• Утечка данных. Defects4J и QuixBugs опубликованы задолго до обучения современных моделей. Часть «починенных» багов модель просто помнит. Корректная оценка требует бенчмарков с датой отсечки после обучения.
• Метрика «resolved» на SWE-bench — это прохождение скрытых тестов, то есть та же правдоподобность. Она не равна корректности, и ручные аудиты это регулярно подтверждают.

APR в продакшене

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

SapFix в Meta (Marginean et al., ICSE-SEIP 2019) чинит краши, найденные фаззером Sapienz, на кодовой базе Facebook для Android. Ключевые решения — не алгоритмические, а процессные: работать по diff-у конкретного коммита (пространство поиска резко сужается), сначала пробовать шаблонные фиксы и откат изменения, генерировать патч за минуты, а не часы, и обязательно отдавать его автору коммита в ревью.

Getafix в Meta (Bader et al., OOPSLA 2019) — другой угол: он учится на истории того, как инженеры сами чинили срабатывания статического анализатора, кластеризует правки в иерархию шаблонов и предлагает фикс прямо в отчёте линтера. Никакого поиска в рантайме — только выученные шаблоны и ранжирование. По принятым патчам это одна из самых успешных систем в индустрии.

Что общего у всех прижившихся внедрений:

1. Узкий класс дефектов (NPE, краш, срабатывание линтера), а не «любой баг».
2. Сильный сигнал о падении — стек-трейс или воспроизводимый краш, а не «где-то что-то не так».
3. Жёсткий бюджет времени — минуты, потому что патч должен успеть к ревью коммита.
4. Человек в цикле на merge. Ни одна известная промышленная система не льёт патчи в мастер сама.

Бенчмарки, на которых имеет смысл мерить свои эксперименты: Defects4J (835 реальных Java-багов с падающими тестами), ManyBugs и IntroClass для C, QuixBugs (40 однострочных багов на Java и Python), BugsInPy для Python и SWE-bench для задач уровня «issue из GitHub».

Типичные ошибки

• Считать зелёный сьют доказательством корректности. Это главная ошибка, и она не техническая, а мировоззренческая. Всегда держите held-out тесты, о которых поиск не знает.
• Не минимизировать патч. Патч из пяти правок, из которых работает одна, невозможно ревьюить — и его отклонят, даже если он корректен.
• Гонять полный сьют на каждом кандидате. Прямой путь к бюджету в сутки на один баг. Сначала падающие тесты, потом остальное.
• Игнорировать флейки. Нестабильный тест превращает фитнес-функцию в шум: один и тот же патч получает разные оценки. Прогоняйте подозрительные тесты трижды перед началом или исключайте их.
• Оценивать инструмент по числу правдоподобных патчей. Публикуйте долю корректных и описывайте процедуру ручной проверки — иначе цифра ничего не значит.
• Не сравниваться со случайным поиском и с «просто удалить строку». Оба baseline унизительно сильны; если ваш алгоритм их не бьёт, сложность не оправдана.
• Отсутствие таймаутов и песочницы. Мутация легко порождает бесконечный цикл, rm -rf или бомбу из памяти. Гоняйте кандидатов в контейнере с лимитами CPU, памяти и без сети.
• Локализация только по SBFL. На реальных багах она слаба; добавляйте историю изменений и ограничивайте область поиска свежим диффом — это самый дешёвый и самый эффективный приём.

Мини-итог

• APR — это поиск в пространстве правок кода, где фитнес-функцией служит тест-сьют. Пайплайн: локализация → генерация кандидата → валидация → минимизация → проверка человеком.
• Локализация (SBFL: Ochiai, DStar) сужает пространство, но на реальных дефектах слаба; усиливайте её историей изменений и ограничением области поиска.
• Три семейства: generate-and-validate (поиск по операторам/шаблонам), semantics-driven (символьное исполнение + синтез через SMT), learning-based (seq2seq, предобученные модели кода, LLM-агенты). Последнее — тот же цикл G&V с более качественным генератором кандидатов.
• Правдоподобный ≠ корректный. Это центральный факт области, доказанный Qi et al. и экспериментом Kali. Тест-сьют — приближённая спецификация, и поиск неизбежно переобучается под неё.
• Стоимость поиска почти целиком — стоимость прогона тестов. Оптимизируйте валидацию, а не алгоритм поиска.
• В проде APR живёт как «умное предложение в ревью» для узкого класса дефектов с сильным сигналом о падении, и merge всегда делает человек.

Источники

• C. Le Goues, T. Nguyen, S. Forrest, W. Weimer. «GenProg: A Generic Method for Automatic Software Repair», IEEE TSE, 2012.
• C. Le Goues, M. Dewey-Vogt, S. Forrest, W. Weimer. «A systematic study of automated program repair: Fixing 55 out of 105 bugs for \8 $ each», ICSE 2012.
• Z. Qi, F. Long, S. Achour, M. Rinard. «An Analysis of Patch Plausibility and Correctness for Generate-and-Validate Patch Generation Systems», ISSTA 2015 — работа про Kali, обязательна к прочтению.
• E. Barr, Y. Brun, P. Devanbu, M. Harman, F. Sarro. «The Plastic Surgery Hypothesis», FSE 2014.
• D. Kim, J. Nam, J. Song, S. Kim. «Automatic patch generation learned from human-written patches» (PAR), ICSE 2013.
• K. Liu, A. Koyuncu, D. Kim, T. Bissyandé. «TBar: Revisiting Template-based Automated Program Repair», ISSTA 2019.
• H. D. T. Nguyen, D. Qi, A. Roychoudhury, S. Chandra. «SemFix: Program Repair via Semantic Analysis», ICSE 2013.
• S. Mechtaev, J. Yi, A. Roychoudhury. «Angelix: Scalable Multiline Program Patch Synthesis via Symbolic Analysis», ICSE 2016.
• J. Xuan et al. «Nopol: Automatic Repair of Conditional Statement Bugs in Java Programs», IEEE TSE, 2017.
• R. Abreu, P. Zoeteweij, A. van Gemund. «On the Accuracy of Spectrum-based Fault Localization», TAICPART-MUTATION 2007 — метрика Ochiai.
• S. Pearson et al. «Evaluating and Improving Fault Localization», ICSE 2017.
• E. K. Smith, E. Barr, C. Le Goues, Y. Brun. «Is the Cure Worse Than the Disease? Overfitting in Automated Program Repair», FSE 2015.
• M. Monperrus. «Automatic Software Repair: A Bibliography», ACM Computing Surveys, 2018 — лучшая обзорная точка входа.
• C. Le Goues, M. Pradel, A. Roychoudhury. «Automated Program Repair», Communications of the ACM, 2019.
• A. Marginean et al. «SapFix: Automated End-to-End Repair at Scale», ICSE-SEIP 2019.
• J. Bader, A. Scott, M. Pradel, S. Chandra. «Getafix: Learning to Fix Bugs Automatically», OOPSLA 2019.
• Z. Chen et al. «SequenceR: Sequence-to-Sequence Learning for End-to-End Program Repair», IEEE TSE, 2019.
• C. S. Xia, L. Zhang. «Less Training, More Repairing Please: Revisiting Automated Program Repair via Zero-shot Learning» (AlphaRepair), FSE 2022.
• C. S. Xia, L. Zhang. «Keep the Conversation Going: Fixing 162 out of 337 bugs for \0.42 $ each using ChatGPT», 2023.
• C. Jimenez et al. «SWE-bench: Can Language Models Resolve Real-World GitHub Issues?», ICLR 2024.
• R. Just, D. Jalali, M. Ernst. «Defects4J: A Database of Existing Faults to Enable Controlled Testing Studies for Java Programs», ISSTA 2014.

Что дальше

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

Дальше — SBSE на практике и связь с современными ИИ-подходами.