Автоматическая генерация тестов: EvoSuite, фаззинг, мутационное тестирование

Генерация тестов — самая успешная область применения SBSE. Не потому, что она самая интересная теоретически, а потому, что здесь совпали три условия, которые редко совпадают вместе: цель измерима автоматически (покрытие считает инструментатор), кандидатное решение проверяется дёшево (запустить тест — миллисекунды), а результат немедленно полезен человеку (тест можно закоммитить). Всё, что мы строили в предыдущих статьях — представление решения и фитнес из https://courses.digitable.life/post/sbse/01-search-space-and-fitness/, локальный поиск из https://courses.digitable.life/post/sbse/02-local-search/, генетические алгоритмы из https://courses.digitable.life/post/sbse/03-genetic-algorithms/, многокритериальность из https://courses.digitable.life/post/sbse/05-multi-objective/ — здесь сходится в работающие инструменты, которые сегодня крутятся в CI у Google, Mozilla и десятков тысяч open-source проектов.

В статье разберём три техники, которые часто путают, хотя они решают разные задачи:

• Генерация модульных тестов (EvoSuite, Randoop, Pynguin) — построить набор тестов, покрывающий код.
• Фаззинг (AFL++, libFuzzer, honggfuzz) — найти вход, на котором программа падает.
• Мутационное тестирование (PIT, mutmut, Stryker) — измерить, действительно ли тесты что-то проверяют.

Первые две — генераторы, третья — измеритель. И, как мы увидим, третья ещё и работает оракулом для первой.

Почему это задача поиска

Возьмём метод и поставим цель: покрыть в нём конкретную строку. Формально нужно найти такие входные данные, при которых выполнение дойдёт до этой строки. Это задача разрешимости пути в программе, и в общем случае она неразрешима — эквивалентна проблеме останова. Символьное выполнение решает её точно, но упирается в нелинейную арифметику, вызовы нативного кода, хеши и криптографию: SMT-солвер не обратит SHA-256.

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

Есть и вторая, более неприятная половина задачи — проблема оракула. Допустим, мы нашли вход. Что считать правильным выходом? Автоматически это неизвестно: спецификации в машиночитаемом виде нет. Обзор Barr et al., «The Oracle Problem in Software Testing: A Survey» (IEEE TSE, 2015), систематизирует обходные пути, и три из них живут в реальных инструментах:

1. Неявный оракул — падение, зависание, срабатывание санитайзера. Ничего знать о семантике не нужно: любой SIGSEGV — это баг. На этом стоит весь фаззинг.
2. Регрессионный оракул — зафиксировать текущее поведение в ассертах. Не проверяет корректность, но ловит будущие изменения. На этом стоит EvoSuite.
3. Метаморфический оракул — свойства, связывающие входы и выходы (sort(sort(x)) == sort(x), decode(encode(x)) == x). На этом стоит property-based тестирование.

Держите это разделение в голове: почти вся критика автогенерации тестов на самом деле критикует не поиск, а слабость оракула.

Что мы ищем: представление тестового случая

Для модульного теста ООП-кода решение — это не вектор чисел, а последовательность операторов: создать объекты, вызвать методы, передать результаты одних вызовов в аргументы других. Это ближе к генетическому программированию из https://courses.digitable.life/post/sbse/04-genetic-programming/, чем к классическому ГА: хромосома имеет переменную длину и внутренние ограничения типов.

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

• Кроссовер тестов — однотонный по позиции с проверкой зависимостей: берём префикс одного теста и достраиваем суффикс другого, копируя вместе с оператором всё дерево его зависимостей.
• Мутация теста — три вида с равной вероятностью: удалить оператор (и всё, что от него зависит), изменить оператор (заменить вызов, подкрутить примитив на дельту), вставить новый оператор в случайную позицию.
• Мутация примитивов — не «случайное новое число», а value += delta, где delta берётся из распределения с тяжёлым хвостом. Это принципиально: локальность представления (см. https://courses.digitable.life/post/sbse/01-search-space-and-fitness/) даёт поиску возможность плавно двигаться к b == 5, а не прыгать наугад по всему int.

Тонкость, которая всплывает у всех, кто пишет свой генератор: длина теста растёт сама собой — это тот же bloat, что и в ГП. Лечится штрафом за длину в фитнесе или ограничением сверху, а в конце — обязательной минимизацией финального набора.

Фитнес: approach level + branch distance

Наивный фитнес «покрыта ли целевая ветка» бесполезен: он равен 0 почти везде и 1 в одной точке. Ландшафт — плоское плато с иглой, поиск на нём вырождается в случайный перебор. Классическое решение придумал Korel в работе «Automated Software Test Data Generation» (IEEE TSE, 1990), а в законченную форму его привели Wegener, Baresel и Sthamer в эволюционном тестировании Daimler (2001). Фитнес складывается из двух слагаемых:

fitness(target, input) = approach_level + norm(branch_distance)

• approach level — сколько узлов ветвления, управляющих целью, ещё не пройдено. Считается по графу зависимостей по управлению: чем раньше выполнение свернуло не туда, тем больше штраф.
• branch distance — насколько «чуть-чуть» не хватило условию в том узле, где выполнение свернуло не туда. Именно оно превращает плато в наклон.

Формулы branch distance для условия, которое должно было стать истинным (K — небольшая положительная константа, обычно 1):

Нормализация обязательна: без неё одно слагаемое с расстоянием 10^9 полностью заглушит approach level. Стандарт — norm(d) = d / (d + 1), отображающий [0, ∞) в [0, 1). Arcuri в «It Does Matter How You Normalise the Branch Distance in Search Based Software Testing» (ICST 2010) показал, что выбор нормализации влияет на результат сильнее, чем кажется, и предложил 1 - 1.001^(-d) как более устойчивую альтернативу при больших расстояниях.

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

Соберём поиск входа для вложенных условий вручную — так становится видно, откуда берётся ускорение.

import random
from dataclasses import dataclass

K = 1.0

def norm(d: float) -> float:
    """Нормализация расстояния в [0, 1) — иначе approach level утонет."""
    return d / (d + K)

@dataclass
class Trace:
    approach_level: int      # сколько узлов ветвления не пройдено
    branch_distance: float   # насколько не хватило в точке промаха

def instrumented(a: int, b: int, c: int) -> Trace:
    """Инструментированная версия целевой функции.
    Реальные инструменты вставляют такие пробы в байт-код автоматически."""
    if not (a > 0):
        return Trace(2, max(0, 1 - a))      # a > 0  ->  d = 0 - a + K
    if not (b == 5):
        return Trace(1, abs(b - 5))         # b == 5 ->  d = |b - 5|
    if not (c < 10):
        return Trace(0, c - 10 + K)         # c < 10 ->  d = c - 10 + K
    return Trace(-1, 0.0)                   # цель достигнута

def fitness(x) -> float:
    t = instrumented(*x)
    if t.approach_level < 0:
        return 0.0                          # минимизируем: 0 == успех
    return t.approach_level + norm(t.branch_distance)

def mutate(x, sigma: int = 8):
    """Локальная мутация: сдвиг одной координаты, а не случайный int."""
    y = list(x)
    i = random.randrange(len(y))
    y[i] += random.choice([-1, 1]) * random.randint(1, sigma)
    return tuple(y)

def search(budget: int = 20_000, restart_after: int = 400):
    """Hill climbing с принятием плато и рестартами (см. статью о локальном поиске)."""
    random.seed(42)
    best, best_f, stall, evals = None, float("inf"), 0, 0
    cur = tuple(random.randint(-1000, 1000) for _ in range(3))
    cur_f = fitness(cur); evals += 1
    while evals < budget:
        cand = mutate(cur)
        f = fitness(cand); evals += 1
        if f <= cur_f:                       # <= : разрешаем движение по плато
            stall = 0 if f < cur_f else stall + 1
            cur, cur_f = cand, f
        else:
            stall += 1
        if cur_f < best_f:
            best, best_f = cur, cur_f
        if best_f == 0.0:
            return best, evals
        if stall > restart_after:            # застряли — рестарт из новой точки
            cur = tuple(random.randint(-1000, 1000) for _ in range(3))
            cur_f = fitness(cur); evals += 1; stall = 0
    return best, evals

print(search())   # ((374, 5, -923), 1076)

Измеримый результат: направленный поиск находит вход за ≈1 100 запусков, случайная генерация тех же трёх чисел из [-1000, 1000] — за ≈8 100 (усреднено по 200 прогонам). Разрыв всего в 7 раз, потому что условие простое. Замените b == 5 на b == 987654321 — случайный поиск не найдёт вход никогда, а направленный дойдёт за то же время: он идёт по градиенту |b - 987654321|, и размер константы почти не влияет.

Сложность. Пусть G — число поколений, N — размер популяции, L — средняя длина теста, C — стоимость одного запуска. Тогда время ≈ O(G · N · L · C), и C доминирует на порядки: сравнение фитнесов стоит наносекунды, запуск теста — от микросекунд до сотен миллисекунд, если внутри есть I/O. Отсюда практическое правило: бюджет поиска меряется в запусках, а не в поколениях, и главная оптимизация всегда — сделать запуск дешевле (мокировать I/O, не поднимать Spring-контекст, кешировать результаты по хешу теста), а не подкрутить p_mutation.

Память — O(N · L) на популяцию плюс архив покрытых целей; это единицы мегабайт и практически никогда не узкое место.

От «одна цель за раз» к whole test suite и MOSA

Исторический подход: перебирать цели (ветки) по одной и запускать отдельный поиск на каждую. У него три беды.

1. Недостижимые цели съедают бюджет. Мёртвый код, невозможные комбинации условий, защитные throw new IllegalStateException() — поиск честно тратит на них полный бюджет и не находит ничего.
2. Порядок целей влияет на результат, а хорошего порядка мы заранее не знаем.
3. Побочные покрытия теряются. Тест, искавший ветку A, мог по дороге накрыть ветки B и C, но их всё равно ищут заново.

Fraser и Arcuri в «Whole Test Suite Generation» (IEEE TSE, 2013) предложили сменить единицу поиска: особь — не тест, а весь набор тестов, фитнес — суммарное непокрытие по всем целям сразу:

fitness(suite) = |M_нет| + Σ_{b ∈ ветки} norm(d_min(b, suite))

где d_min — минимальная по всем тестам набора branch distance до ветки. Недостижимые цели просто дают постоянное слагаемое и перестают искажать поиск; порядок целей исчезает как понятие; побочные покрытия учитываются бесплатно.

Следующий шаг сделали Panichella, Kifetew и Tonella в «Reformulating Branch Coverage as a Many-Objective Optimization Problem» (ICST 2015): каждая ветка — отдельная цель, а набор строится алгоритмом MOSA на базе NSGA-II (мы разбирали его в https://courses.digitable.life/post/sbse/05-multi-objective/) с двумя доработками:

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

DynaMOSA (IEEE TSE, 2018) добавила динамический выбор целей: по графу зависимостей по управлению цель становится активной, только когда покрыт её родитель. Искать глубоко вложенную ветку, пока не покрыт внешний if, бессмысленно — это тратит бюджет на заведомо плоскую часть ландшафта. DynaMOSA — алгоритм по умолчанию в современном EvoSuite.

EvoSuite на практике

EvoSuite генерирует JUnit-тесты для Java-классов. Запуск из командной строки:

java -jar evosuite-1.2.0.jar \
  -class com.example.billing.Money \
  -projectCP target/classes:target/dependency/* \
  -Dsearch_budget=120 \
  -Dassertion_strategy=mutation \
  -Dminimize=true \
  -Dsandbox=true \
  -criterion line:branch:exception:weakmutation:output:method:cbranch

Что здесь важно по каждому флагу:

• search_budget — бюджет в секундах на класс. Ниже 60 с результат обычно бесполезен; типичная рабочая точка — 120–300 с на класс. Это главный рычаг качества.
• criterion — список критериев, объединяемых в один многокритериальный поиск. Одно только branch даёт тесты, которые проходят по коду, но плохо провоцируют исключения; exception и output заметно поднимают их баг-детектирующую способность.
• assertion_strategy=mutation — самое интересное, см. ниже.
• sandbox=true — перехват System.exit, файловой системы, сети, System.currentTimeMillis, Random. Без песочницы сгенерированный тест однажды удалит файл или запишет в /etc.
• minimize=true — после поиска каждый тест ужимается: операторы и ассерты удаляются по одному, пока покрытие не падает. Это классический delta debugging (Zeller & Hildebrandt, «Simplifying and Isolating Failure-Inducing Input», IEEE TSE, 2002).

Как EvoSuite придумывает ассерты

Поиск даёт последовательность вызовов — но не даёт утверждений о правильности. EvoSuite решает проблему оракула регрессионно и при этом умно: он записывает все наблюдаемые значения как кандидатов в ассерты, а затем отбирает минимальное подмножество, которое убивает максимум мутантов класса (Fraser & Zeller, «Mutation-Driven Generation of Unit Tests and Oracles», IEEE TSE, 2012).

Логика такая: ассерт assertEquals(42, m.getCents()) полезен ровно настолько, насколько он различает исходную программу и её изменённые версии. Ассерт, который проходит на всех мутантах, не проверяет ничего — его выбрасывают. Обычно из сотен кандидатов остаётся 1–3 на тест.

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

Чего ждать по цифрам

Крупнейшая эмпирическая оценка — Fraser & Arcuri, «A Large-Scale Evaluation of Automated Unit Test Generation Using EvoSuite» (ACM TOSEM, 2014), корпус SF110 из 110 случайно выбранных проектов SourceForge. Итог честнее, чем маркетинг: средневзвешенное покрытие ветвей — порядка 70 %, но с колоссальным разбросом. Классы с чистой логикой покрываются почти полностью; классы, завязанные на БД, сеть, файлы, GUI и статическое состояние, — почти никак, потому что поиск не может собрать нужное окружение.

Второй отрезвляющий результат — «Does Automated Unit Test Generation Really Help Software Testers?» (ACM TOSEM, 2015): в контролируемом эксперименте разработчики, получившие сгенерированные тесты, достигали существенно большего покрытия, но находили не больше настоящих багов, чем писавшие тесты вручную. Причина ровно та же — слабость регрессионного оракула. Вывод для практики: автогенерация — отличный способ построить регрессионную сетку вокруг легаси перед рефакторингом и плохой способ искать дефекты в новом коде.

Для Python аналог — Pynguin (та же научная группа, алгоритмы DynaMOSA/MOSA); для .NET исторический предок — IntelliTest/Pex на символьном выполнении; для случайного feedback-directed подхода на Java — Randoop (Pacheco & Ernst, ICSE 2007), который строит тесты инкрементально, отбрасывая последовательности, приводящие к исключениям, и переиспользуя удачные.

Интеграция в CI делается не «прогнать EvoSuite на всём репозитории каждый билд» (это часы), а через continuous test generation (Campos, Arcuri, Fraser, Abreu, ASE 2014): бюджет распределяется между классами по изменённости и текущему покрытию, генерация идёт ночью, результат — pull request на ревью.

<plugin>
  <groupId>org.evosuite.plugins</groupId>
  <artifactId>evosuite-maven-plugin</artifactId>
  <version>1.2.0</version>
  <configuration>
    <!-- бюджет на класс в секундах; общий бюджет ограничиваем ночным окном -->
    <memoryInMB>2000</memoryInMB>
    <cores>4</cores>
    <timeInMinutesPerClass>3</timeInMinutesPerClass>
  </configuration>
</plugin>

Фаззинг: поиск с оракулом «упало»

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

Черный ящик (случайные байты) быстро упирается в стену: любой парсер отбрасывает мусорный вход на первых байтах, и 99,99 % бюджета уходит в одну и ту же ветку. Прорыв — coverage-guided greybox fuzzing (AFL, Michał Zalewski, 2013): программа инструментируется, покрытие пишется в разделяемую карту, и вход, открывший новое ребро графа потока управления, добавляется в корпус как база для дальнейших мутаций.

Инструментация AFL умещается в четыре строки, вставляемые в каждый базовый блок:

cur_location = <случайный id блока, зафиксированный при компиляции>;
shared_mem[prev_location ^ cur_location]++;
prev_location = cur_location >> 1;

Три детали, за которыми стоит инженерная мысль:

• XOR двух идентификаторов даёт индекс ребра, а не блока: покрытие по рёбрам гораздо чувствительнее к структуре, чем по строкам.
• Сдвиг >> 1 ломает симметрию XOR, иначе рёбра A→B и B→A неотличимы, а петля A→A всегда давала бы индекс 0.
• Карта фиксированного размера (64 КБ по умолчанию) — коллизии возможны, но обмен точности на скорость окупается: обновление покрытия стоит две инструкции.

Счётчики попаданий огрубляются до 8 логарифмических корзин (1, 2, 3, 4–7, 8–15, …). Это ключевой трюк: без него цикл, прокрутившийся 1000 против 1001 раза, считался бы «новым поведением», и корпус взорвался бы шумом. С корзинами новым считается только качественный скачок — например, цикл, впервые прокрутившийся 8 раз вместо 4.

Мини-фаззер на Python

Тот же принцип на 40 строках, с покрытием через sys.settrace. Это игрушка (трассировка тормозит на порядки), но она показывает механизм честно.

import random, sys

def target(data: bytes) -> None:
    """Цель: 4 вложенные проверки. Классический «магический» вход."""
    if len(data) < 4: return
    if data[0] != ord('F'): return
    if data[1] != ord('U'): return
    if data[2] != ord('Z'): return
    if data[3] != ord('Z'): return
    raise AssertionError("crash: дошли до магической последовательности")

def run_with_coverage(fn, data):
    """Собираем «рёбра» как пары соседних выполненных строк."""
    edges, prev = set(), 0
    def tracer(frame, event, arg):
        nonlocal prev
        if event == "line":
            # разбрасываем номера строк по карте: соседние строки не должны
            # давать соседние индексы, иначе рёбра схлопываются в коллизии
            cur = (frame.f_lineno * 2654435761) & 0xFFFF
            edges.add((prev >> 1) ^ cur)
            prev = cur
        return tracer
    crash = None
    sys.settrace(tracer)
    try:
        fn(data)
    except Exception as e:
        crash = e
    finally:
        sys.settrace(None)
    return edges, crash

MUTATORS = [
    lambda d, r: d[:(i := r.randrange(len(d)))] + bytes([r.randrange(256)]) + d[i+1:],
    lambda d, r: d + bytes([r.randrange(256)]),                       # вставка в конец
    lambda d, r: d[:-1] if len(d) > 1 else d,                         # усечение
    lambda d, r: d[:(i := r.randrange(len(d)))] + bytes([d[i] ^ (1 << r.randrange(8))]) + d[i+1:],
]

def fuzz(seed=b"\x00", iters=200_000):
    r = random.Random(0)
    global_edges, corpus = set(), [seed]
    for it in range(iters):
        data = r.choice(corpus)                       # база из корпуса
        for _ in range(r.randint(1, 4)):              # стек мутаций (havoc)
            data = MUTATORS[r.randrange(len(MUTATORS))](data or b"\x00", r)
        edges, crash = run_with_coverage(target, data)
        if crash:
            return ("CRASH", data, it, len(corpus))
        if edges - global_edges:                      # обратная связь по покрытию
            global_edges |= edges
            corpus.append(data)
    return ("no crash", None, iters, len(corpus))

if __name__ == "__main__":
    print(fuzz())   # ('CRASH', b'FUZZ\x1e', 118580, 6)

Результат стоит того, чтобы его осознать. Фаззер с обратной связью нашёл вход за 118 580 итераций, накопив корпус из 6 «интересных» входов — по одному на каждый пройденный байт магической последовательности. Тот же мутатор без обратной связи (всегда мутируем исходный seed) за 300 000 итераций не находит ничего и не найдёт: вероятность угадать 4 конкретных байта вслепую — 256⁻⁴ ≈ 2·10⁻¹⁰. Обратная связь по покрытию превращает мультипликативную задачу (256⁴) в аддитивную (4 × 256). В этом вся суть greybox-фаззинга.

Что делает промышленный фаззер сверх этого

• Power schedule — сколько энергии (мутаций) выделить каждому входу корпуса. AFLFast (Böhme et al., CCS 2016) моделирует фаззинг как цепь Маркова и льёт бюджет во входы, ведущие в редко посещаемые участки; ускорение на порядки при том же коде.
• Fork server — цель загружается и инициализируется один раз, каждый прогон — это fork() из уже прогретого процесса. Убирает динамическую линковку и инициализацию из горячего цикла, давая тысячи запусков в секунду.
• Санитайзеры как оракул. Без них ловятся только SIGSEGV. С AddressSanitizer видно чтение за границей буфера и use-after-free, с UBSan — переполнение знакового целого и сдвиги, с MSan — чтение неинициализированной памяти, с LeakSanitizer — утечки. Практическое следствие: фаззинг без санитайзеров пропускает большую часть багов, до которых уже дошёл.
• Структурно-осведомлённые мутации. Для форматов с контрольными суммами, длинами и грамматикой байтовые мутации бессильны: 99,9 % входов отбрасывается валидатором. Ответ — мутировать не байты, а разобранное представление: libprotobuf-mutator, грамматические фаззеры, кастомные мутаторы AFL++.
• Словари — список магических констант формата (PNG, <?xml, ключевые слова SQL) подсовывается мутатору. Дешёвая замена структурному фаззингу, часто дающая большую часть выигрыша.

Каноническая обвязка для libFuzzer — одна функция:

#include <cstdint>
#include <cstddef>
#include "parser.h"

// Точка входа: фаззер вызывает её миллионы раз с разными данными.
extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
    if (size < 1 || size > 64 * 1024) return 0;   // отсекаем бессмысленные размеры
    Parser p;
    p.Parse(reinterpret_cast<const char *>(data), size);  // падение = найденный баг
    return 0;                                     // 0 — единственное валидное значение
}

# Сборка с инструментацией покрытия и двумя санитайзерами
clang++ -g -O1 -fsanitize=fuzzer,address,undefined harness.cc parser.cc -o fuzz_parser
# 4 параллельных процесса, корпус в ./corpus, словарь формата
./fuzz_parser ./corpus -dict=png.dict -jobs=4 -max_total_time=3600

Требования к харнессу, которые нарушают чаще всего: он должен быть детерминированным (никакого времени, random без фиксированного seed, сети), без утечек между вызовами (иначе LeakSanitizer утонет в ложных срабатываниях) и быстрым — каждая миллисекунда умножается на миллионы прогонов.

Индустриальный масштаб задаёт OSS-Fuzz — Google непрерывно фаззит более тысячи открытых проектов, автоматически заводя баги и проверяя исправления; по данным репозитория проекта, счёт найденных дефектов идёт на десятки тысяч. Если ваш код парсит недоверенный вход — это лучший ROI из всего, что описано в статье.

Соседняя ветка: property-based тестирование

Property-based тестирование (QuickCheck, Claessen & Hughes, ICFP 2000; в Python — Hypothesis) — это фаззинг с метаморфическим оракулом вместо неявного. Вы не описываете входы, вы описываете свойство, а генератор ищет контрпример и автоматически его ужимает (shrinking — тот же delta debugging).

from hypothesis import given, settings, strategies as st

@given(st.lists(st.integers()))
@settings(max_examples=500)
def test_sort_is_idempotent_and_permutation(xs):
    ys = sorted(xs)
    assert sorted(ys) == ys                 # метаморфическое свойство
    assert sorted(ys) == sorted(xs)
    assert len(ys) == len(xs)
    from collections import Counter
    assert Counter(ys) == Counter(xs)       # это перестановка исходного списка

Сильная сторона — оракул содержательный, а не «не упало», и это ровно то, чего не хватает EvoSuite. Слабая — свойства пишет человек, автоматизации ноль. В https://courses.digitable.life/post/sbse/09-sbse-in-practice/ мы вернёмся к тому, как LLM-подходы пытаются закрыть именно этот разрыв.

Мутационное тестирование: измеритель, а не генератор

Покрытие лжёт. Тест, который вызывает метод и не проверяет ничего, даёт 100 % покрытия строк:

@Test
public void testCalculate() {
    calculator.calculate(1, 2);   // покрытие 100%, проверок ноль
}

Мутационное тестирование задаёт правильный вопрос: если я испорчу код, заметят ли это тесты? Идея старше SBSE — DeMillo, Lipton, Sayward, «Hints on Test Data Selection: Help for the Practicing Programmer» (IEEE Computer, 1978). В код вносятся мелкие синтаксические изменения (мутанты), затем прогоняются тесты. Мутант убит, если хоть один тест упал; выжил, если все прошли. Выживший мутант — прямое доказательство дыры в проверках.

mutation score = убитые мутанты / (всего мутантов − эквивалентные)

Под этим лежат две гипотезы. Competent programmer hypothesis: реальные баги — это малые отклонения от правильной программы, а не случайный текст. Coupling effect: набор тестов, ловящий простые (одиночные) дефекты, с высокой вероятностью ловит и сложные, составленные из них. Обе подтверждались эмпирически десятилетиями; свод — Jia & Harman, «An Analysis and Survey of the Development of Mutation Testing» (IEEE TSE, 2011).

Типичные операторы:

Два больших препятствия

Эквивалентные мутанты. Мутация синтаксически меняет код, но не меняет наблюдаемое поведение — например, i <= n → i < n в цикле, где i никогда не достигает n, или мутация в мёртвом коде. Такой мутант невозможно убить, и он занижает оценку. Определить эквивалентность в общем случае неразрешимо (Budd & Angluin, 1982); ручная разметка исторически съедала до 15 минут на мутанта. Частичные ответы: TCE — trivial compiler equivalence (Papadakis et al., ICSE 2015): если оптимизирующий компилятор порождает идентичный машинный код для оригинала и мутанта, они эквивалентны. Дешёвый статический фильтр, снимающий ощутимую долю случаев бесплатно.

Стоимость. Наивно — |M| × |T| прогонов: для 5 000 мутантов и 2 000 тестов это 10 миллионов запусков. Оптимизации, которые делают технику применимой:

• Матрица покрытия: мутант прогоняется только против тестов, которые вообще доходят до изменённой строки. Обычно режет работу на порядок и больше.
• Ранний выход: как только тест убил мутанта, остальные тесты для него не запускаются. При хороших тестах убийство происходит на первом-втором тесте.
• Мутационные схемы (mutant schemata): все мутанты кодируются в одну инструментированную программу, переключаемую флагом; компиляция одна вместо тысяч. PIT делает это на уровне байт-кода JVM, вообще без перекомпиляции.
• Выборка мутантов: случайные 10 % дают оценку score с приемлемой точностью; операторно-избирательная выборка (несколько самых «продуктивных» операторов) — ещё лучше.
• Инкрементальный режим: мутировать только строки, изменённые в текущем диффе. Это то, что делает технику пригодной для CI.

Как это выглядит в проде

Для Java — PIT (pitest), стандарт де-факто:

mvn org.pitest:pitest-maven:mutationCoverage \
  -DtargetClasses='com.example.billing.*' \
  -DtargetTests='com.example.billing.*Test' \
  -DmutationThreshold=70 \
  -DwithHistory=true          # инкрементальный анализ: только изменившееся

Для Python — mutmut (mutmut run --paths-to-mutate src/), для JS/TS и C# — Stryker.

Наиболее поучителен опыт Google: Petrović & Ivanković, «State of Mutation Testing at Google» (ICSE-SEIP, 2018) и последующая «Practical Mutation Testing at Scale». Прогнать все мутанты на монорепозитории нереально в принципе, поэтому подход перевернули:

1. Мутационный анализ идёт не на всём коде, а на диффе ревью.
2. На одну изменённую строку показывается максимум один мутант — иначе разработчик тонет в шуме и перестаёт читать.
3. Вводится понятие arid nodes — «бесплодных» узлов (логирование, отладочные проверки, тривиальные геттеры), мутанты в которых почти всегда бесполезны. Их подавляют эвристиками и правилами, выученными на реакции разработчиков.
4. Выживший мутант показывается как комментарий в код-ревью: «этот тест не заметит, если здесь заменить >= на >». Разработчик отвечает «полезно» или «не полезно», и обратная связь дообучает фильтры.

Главный урок отсюда общий для всей автоматизации качества: техническая мощь метрики бесполезна без управления шумом. Мутационное тестирование, выданное сырым, отвергается командами за неделю; выданное точечно и в момент ревью — принимается.

Как три техники складываются в одну систему

Работающая связка выглядит так:

• Фаззинг — для всего, что принимает недоверенный вход: парсеры, декодеры, десериализация, сетевые протоколы. Оракул бесплатный, ROI наивысший.
• EvoSuite / Pynguin — для легаси без тестов перед рефакторингом: быстро построить регрессионную сетку, чтобы заметить, что рефакторинг изменил поведение. Не для поиска багов.
• Мутационное тестирование — как приёмка качества тестов, написанных людьми и машинами, на диффе, в момент ревью.
• Property-based — для кода с формулируемыми инвариантами: сериализация, коллекции, конечные автоматы, арифметика денег.

Сложность и trade-offs

Сквозной вывод: все эти методы упираются не в алгоритм поиска, а в стоимость одного запуска и в качество оракула. Улучшение фитнес-функции даёт проценты, ускорение запуска в 10 раз даёт порядок, а замена слабого оракула на сильный меняет саму ценность результата.

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

1. Считать сгенерированные ассерты спецификацией. Они фиксируют «как есть». Если код багованный, тест будет защищать баг. Всегда ревью.
2. Гнаться за покрытием как за целью. 100 % покрытия при нулевой мутационной оценке — обычная ситуация. Покрытие — необходимое условие, не достаточное.
3. Фаззить без санитайзеров. Вы уже дошли до бага в памяти, но без ASan программа его переживёт и вы ничего не узнаете.
4. Фаззить структурированный формат байтовыми мутациями. Если 99,9 % входов гибнет на валидаторе CRC, поиск не начинался. Нужен словарь или структурный мутатор.
5. Давать поиску маленький бюджет и делать выводы. 10 секунд на класс — это шум. Ниже минуты сравнивать инструменты бессмысленно.
6. Сравнивать рандомизированные алгоритмы по одному прогону. Нужны повторы и статистика — Arcuri & Briand, «A Practical Guide for Using Statistical Tests to Assess Randomized Algorithms in Software Engineering» (ICSE 2011): тест Манна–Уитни и размер эффекта Варга–Делани A₁₂ вместо «у нас получилось лучше».
7. Мержить нестабильные тесты. Сгенерированный тест, зависящий от времени, порядка в HashMap или локали, отравит CI. Песочница и детерминизм — обязательны.
8. Включать мутационное тестирование на весь репозиторий в блокирующий CI. Часы прогона и сотни выживших мутантов приведут к тому, что через неделю его отключат. Только на дифф, только один мутант на строку.

Мини-итог

• Генерация тестов — задача поиска, потому что проверка пути в программе неразрешима, а запуск программы дёшев.
• approach level + norm(branch distance) превращает бинарное «покрыто/нет» в непрерывный градиент — без этого поиск вырождается в случайный перебор.
• Whole test suite generation убрало проблему недостижимых целей, MOSA/DynaMOSA переформулировали покрытие как многокритериальную задачу с архивом и динамическим выбором целей.
• Фаззинг с обратной связью по покрытию превращает мультипликативную задачу угадывания входа в аддитивную; санитайзеры — его настоящий оракул.
• Мутационное тестирование — единственная широко доступная честная мера качества тестов, и оно же служит фильтром ассертов в EvoSuite.
• Узкое место везде одно: слабый оракул и стоимость запуска, а не алгоритм поиска.

Источники

• Fraser, Arcuri. «Whole Test Suite Generation», IEEE TSE, 2013.
• Fraser, Arcuri. «A Large-Scale Evaluation of Automated Unit Test Generation Using EvoSuite», ACM TOSEM, 2014.
• Panichella, Kifetew, Tonella. «Reformulating Branch Coverage as a Many-Objective Optimization Problem», ICST 2015; DynaMOSA, IEEE TSE, 2018.
• Korel. «Automated Software Test Data Generation», IEEE TSE, 1990.
• Jia, Harman. «An Analysis and Survey of the Development of Mutation Testing», IEEE TSE, 2011.
• Papadakis et al. «Mutation Testing Advances: An Analysis and Survey», Advances in Computers, 2019.
• Petrović, Ivanković. «Practical Mutation Testing at Scale», 2021.
• Böhme, Pham, Roychoudhury. «Coverage-based Greybox Fuzzing as Markov Chain», CCS 2016.
• Zeller et al. The Fuzzing Book — лучший бесплатный учебник по фаззингу с исполняемым кодом.
• Документация: EvoSuite, libFuzzer, AFL++, PIT, Hypothesis.

Что дальше

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

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