Metamorphic testing обнаружил 147 подтверждённых багов в GCC и LLVM, дефекты в коммерческих симуляторах ADAS, используемых автомобильными OEM, и критический изъян в системе восприятия самоуправляемого автомобиля за восемь дней до того, как она стала причиной гибели пешехода. Техника звучит академично, но баги реальны.

Проблема в том, что это проблема oracle. Для многих программ вы можете запускать входные данные, но не можете независимо проверить, что выходные данные верны. Каков точно кратчайший путь через дорожную сеть с 10 000 узлов? Сохраняет ли эта оптимизация компилятора семантику? Верна ли на самом деле классификация этой ML-модели? Вы не знаете. Традиционное юнит-тестирование здесь не работает, потому что вы не можете написать assertEquals(expected, actual), когда понятия не имеете, чем должно быть expected.

Metamorphic testing обходит это, вообще не проверяя выходные данные. Он проверяет отношения между выходными данными.

Что такое metamorphic testing?

Metamorphic testing — это техника, при которой вы преобразуете входные данные в связанные входные данные, прогоняете оба варианта через вашу программу и утверждаете, что два выхода подчиняются известному математическому или логическому отношению. Это отношение называется metamorphic relation.

Если ваша программа вычисляет среднее значение списка чисел, вам не нужно знать точное среднее [4.2, 1.7, 9.3, 2.1], чтобы протестировать это. Вам нужно только знать, что перемешивание списка должно дать тот же результат, или что удвоение каждого элемента должно удвоить среднее. Это и есть metamorphic relations.

Первый вход — это source test case. Преобразованный вход — это follow-up test case. Oracle — это само отношение.

Вот конкретный пример на Python:

import random

def compute_average(numbers):
    """Returns the arithmetic mean of a list of numbers."""
    if not numbers:
        raise ValueError("empty list")
    return sum(numbers) / len(numbers)

def test_average_permutation_invariant():
    """MR-1: Shuffling the input should not change the average."""
    source = [4.2, 1.7, 9.3, 2.1, 5.6]
    follow_up = source.copy()
    random.shuffle(follow_up)

    source_out = compute_average(source)
    follow_up_out = compute_average(follow_up)

    assert source_out == follow_up_out, (
        f"Permutation MR failed: {source_out} != {follow_up_out}"
    )

def test_average_scaling():
    """MR-2: Doubling every element should double the average."""
    source = [3.0, 6.0, 9.0]
    follow_up = [x * 2 for x in source]

    source_out = compute_average(source)
    follow_up_out = compute_average(follow_up)

    assert follow_up_out == source_out * 2, (
        f"Scaling MR failed: {follow_up_out} != {source_out * 2}"
    )

def test_average_inclusion():
    """MR-3: Appending the average itself should not decrease the average."""
    source = [10.0, 20.0, 30.0]
    source_out = compute_average(source)
    follow_up = source + [source_out]
    follow_up_out = compute_average(follow_up)

    assert follow_up_out == source_out, (
        f"Inclusion MR failed: {follow_up_out} != {source_out}"
    )

if __name__ == "__main__":
    test_average_permutation_invariant()
    test_average_scaling()
    test_average_inclusion()
    print("All metamorphic relations passed.")

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

Реальные баги, найденные в продакшен-системах

Эта техника не теоретическая. Вот задокументированные случаи, когда metamorphic testing нашёл реальные баги в продакшен-ПО.

147 багов в GCC и LLVM

Исследователи применили metamorphic testing к конвейерам оптимизации C-компиляторов и нашли 147 подтверждённых багов в GCC и LLVM. Это были не игрушечные программы. Это были реальные баги miscompilation, когда корректная C-программа, пропущенная через оптимизирующий компилятор, порождала некорректный машинный код. Некоторые из этих багов существовали годами. Metamorphic relations были простыми: если вы вручную делаете inline функции, оптимизированный выход должен вести себя так же, как оригинал. Если вы переставляете независимые операторы, результат не должен меняться. Разработчики компиляторов подтвердили и исправили эти баги.

Компиляторы шейдеров Vulkan в Google

Команда GraphicsFuzz в Google внедрила рандомизированный metamorphic testing в продакшен для набора тестов на соответствие Khronos Vulkan. Они генерировали случайные фрагментные шейдеры, применяли трансформации, сохраняющие семантику (например, оборачивание выражений в тождественные функции или добавление мёртвого кода), и сравнивали отрендеренные изображения на разных компиляторах и GPU. Когда два предположительно эквивалентных шейдера давали разные пиксели, они находили баг компилятора. Команда построила целый пайплайн под названием gfauto для редукции, дедупликации и репорта этих случаев. Они нашли баги в экосистеме инструментов, которые трансформируют, оптимизируют и валидируют шейдеры Vulkan, включая продакшен-драйверы, поставляемые конечным пользователям.

Симуляторы ADAS, используемые автомобильными OEM

Команда протестировала три популярные платформы симуляции ADAS — Simulink, CarMaker и 51Sim-One Cloud — сфокусировавшись на их системах помощи удержания полосы движения (Lane Keeping Assist Systems). Обычные тест-кейсы проходили на всех трёх платформах. Никаких проблем. Затем команда применила геометрические metamorphic relations: отзеркаливала дорожную сцену по горизонтали, поворачивала позицию транспортного средства, применяла аффинные трансформации к разметке полосы. Выходные данные должны были трансформироваться предсказуемо. Они не трансформировались. Баги были выявлены на всех трёх платформах. Компании MathWorks и IPG Automotive позже подтвердили проблемы. Это те же самые платформы, которые используются для валидации ПО перед его установкой в транспортные средства.

Дефект self-driving car в том же классе

В одном из самых тревожных случаев исследователи применили metamorphic testing к системе обнаружения объектов для автономных транспортных средств и нашли баг в пайплайне восприятия. Система не могла корректно классифицировать пешеходов при определённых преобразованных входных данных. Они сообщили об этом. Баг, который они нашли, относился к тому же классу дефектов, который был замешан в смертельных self-driving car столкновениях с пешеходами.

Компромисс: relations зависят от предметной области

Metamorphic testing мощен, но он не бесплатен. Сложная часть — это выявление хороших metamorphic relations. Плохое отношение даёт ложную уверенность. Отношение, которое слишком слабое, не поймает баги. Отношение, которое слишком сильное, будет падать на корректном поведении из-за шума floating-point или недетерминизма.

Проектирование relations требует предметных знаний. Для алгоритма кратчайшего пути хорошие relations включают: стоимость пути A->B должна равняться B->A в ненаправленном графе; добавление константы к весу каждого ребра должно добавлять эту константу, умноженную на количество рёбер, к общей стоимости пути. Для алгоритма сортировки: переворачивание отсортированного списка и его сортировка должны дать обратный от исходного отсортированного списка; каждый элемент в выходных данных должен присутствовать во входных с той же частотой.

Вы не можете переиспользовать одни и те же relations в несвязанных системах. Это и есть цена.

Арифметика floating-point — ещё одна ловушка. Многие relations предполагают точное равенство, но 0.1 + 0.2 != 0.3 в IEEE 754. Вам нужны сравнения с допуском, и выбор правильного допуска — это сама по себе проблема. Слишком жёсткий — и вы получите ложные срабатывания. Слишком мягкий — и вы пропустите реальные баги.

Как добавить metamorphic testing в ваш codebase

Вам не нужен фреймворк. Вам нужна дисциплина.

Начните с функций в вашем codebase, у которых нет oracle. ML-инференс, алгоритмы оптимизации, геометрические вычисления, статистические агрегации и код симуляции — всё это кандидаты. Для каждого спросите: что должно быть верно относительно выходных данных, если я изменю входные определённым, предсказуемым образом?

Пишите по одной metamorphic relation на тестовую функцию. Называйте её понятно. Запускайте в CI рядом с вашими юнит-тестами. Когда relation падает, относитесь к этому точно так же, как к любому другому падению теста.

Вот чуть более реалистичный пример тестирования функции поиска пути:

import math

def shortest_path_cost(graph, start, end):
    """Returns the cost of the shortest path. Assume implemented."""
    pass

def test_shortest_path_undirected_symmetry():
    """MR: In an undirected graph, path cost A->B equals B->A."""
    graph = {
        'A': [('B', 3.0), ('C', 1.0)],
        'B': [('A', 3.0), ('C', 1.0)],
        'C': [('A', 1.0), ('B', 1.0)],
    }
    ab = shortest_path_cost(graph, 'A', 'B')
    ba = shortest_path_cost(graph, 'B', 'A')
    assert math.isclose(ab, ba, rel_tol=1e-9), f"Symmetry failed: {ab} != {ba}"

def test_shortest_path_subpath():
    """MR: The shortest path cost cannot exceed any specific path's cost."""
    graph = {
        'A': [('B', 2.0), ('C', 10.0)],
        'B': [('C', 2.0)],
        'C': [],
    }
    cost = shortest_path_cost(graph, 'A', 'C')
    assert cost <= 10.0, f"Subpath MR failed: {cost} > 10.0"
    assert math.isclose(cost, 4.0, rel_tol=1e-9), f"Expected 4.0, got {cost}"

Вы тестируете не сам алгоритм. Вы тестируете вашу реализацию этого алгоритма.

FAQ

Заменяет ли metamorphic testing юнит-тесты?

Нет. Он дополняет их. Используйте юнит-тесты, когда знаете ожидаемый выход. Используйте metamorphic tests, когда не знаете.

Могу ли я использовать это для ML-моделей?

Да, и это одна из самых активных областей исследований. Relations вроде «поворот изображения кошки всё ещё должен классифицироваться как кошка» — это metamorphic relations. Исследователи находили проблемы надёжности моделей и разрывы в fairness, используя этот подход.

Как мне узнать, что моя metamorphic relation верна?

Вы не доказываете это. Вы рассуждаете от спецификации или от математических свойств предметной области. Если ваша relation сама по себе багованная, вы получите ложные срабатывания. Начинайте с очевидных свойств и добавляйте новые по мере роста уверенности.

А что с flaky-тестами?

Недетерминированные системы (вероятностные алгоритмы, конкурентный код, системы с таймаутами) усложняют metamorphic testing. Вам может понадобиться запускать несколько прогонов или использовать статистические relations вместо точного равенства.

Начните с одной relation

Вам не нужна докторская степень, чтобы использовать это. Выберите одну функцию в вашей системе, которую вы сейчас пропускаете при тестировании, потому что проверка выходных данных слишком сложна. Напишите одну metamorphic relation. Запустите её. Если хотите углубиться, инструментарий gfauto команды GraphicsFuzz открыт, а обзор ACM авторов Segura et al. каталогизирует relations по десяткам предметных областей.

Эта техника нашла 147 багов в компиляторах, подтверждённые дефекты в платформах автомобильной симуляции и выявила класс отказов восприятия в самоуправляемых автомобилях до того, как они выехали на дорогу. Баги реальны. Единственный вопрос — ищете ли вы их.