Что на самом деле даёт differential testing

Можно доверять differential testing без формального доказательства, но только если точно понимать, где оно даёт сбой.

Эта слабость называется common-mode failure. Когда каждая реализация спецификации делает одно и то же неверное предположение, они все соглашаются, и ваш test harness засчитывает это как pass. N-version programming не защищает от плохой спецификации.

Differential testing работает путём запуска нескольких независимых реализаций одной спецификации на одном и том же input. Если их outputs расходятся, по крайней мере одна содержит баг. Если они согласны, вы предварительно считаете это good.

Это мощно, потому что устраняет необходимость в test oracle. Oracle — это source of truth, который знает правильный ответ для каждого input. Для сложных систем oracles часто сложнее построить, чем саму систему. Налоговый движок, физическая симуляция или декодер протокола могут тестироваться на consistency задолго до того, как вы сможете доказать, каким должен быть каждый output.

Но предварительность имеет значение. Agreement доказывает только consistency. Оно не доказывает correctness.

Почему agreement — это не correctness

Режим отказа, о котором все узнают в теории, но забывают на практике, — это common-mode fault. Когда ошибка берёт начало в самой спецификации или в shared assumption, которую все команды реализации делают независимо, каждая version выдаёт один и тот же неверный ответ.

Спецификация не обязана быть явно ошибочной. Достаточно, чтобы она была ambiguous на edge case, который человеческий мозг разрешает одинаково.

Представьте спецификацию функции, вычисляющей площадь простого многоугольника из списка вершин. Спецификация даёт shoelace formula. В ней не упоминается vertex ordering.

Три команды реализуют её. Все три предполагают counter-clockwise ordering, потому что именно так нарисован пример на диаграмме. Clockwise inputs дают отрицательную площадь в raw formula. Все три тихо оборачивают результат в abs(), потому что площадь должна быть положительной. Они согласны на каждом test case.

Но спецификация никогда не говорила, что clockwise неверен. Реализации consistent и ошибочны по умолчанию (omission). Differential testing даёт им всем greenlight.

Три реализации, одна ambiguous spec

Вот конкретный пример, который можно запустить. Спецификация гласит: «Разберите duration string и верните общее количество секунд. Duration состоит из одной или нескольких components. Каждая component — это positive integer, за которым следует буква единицы измерения: h для часов, m для минут, s для секунд.»

Три команды получают эту спецификацию и пишут свои parsers.

import re

def parse_duration_a(s):
    """Team A: regex approach."""
    if not isinstance(s, str):
        raise TypeError("input must be a string")
    m = re.fullmatch(r"(?:(\d+)h)?(?:(\d+)m)?(?:(\d+)s)?", s)
    if not m or not any(m.groups()):
        raise ValueError(f"invalid duration: {s}")
    h, mn, sec = (int(x or 0) for x in m.groups())
    return h * 3600 + mn * 60 + sec

def parse_duration_b(s):
    """Team B: left-to-right scanner."""
    if not isinstance(s, str):
        raise TypeError("input must be a string")
    total = 0
    i = 0
    while i < len(s):
        j = i
        while j < len(s) and s[j].isdigit():
            j += 1
        if j == i:
            raise ValueError(f"expected number at position {i}")
        num = int(s[i:j])
        if j >= len(s):
            raise ValueError(f"missing unit after {num}")
        unit = s[j]
        if unit == 'h':
            total += num * 3600
        elif unit == 'm':
            total += num * 60
        elif unit == 's':
            total += num
        else:
            raise ValueError(f"invalid unit: {unit}")
        i = j + 1
    return total

def parse_duration_c(s):
    """Team C: state machine with duplicate detection."""
    if not isinstance(s, str):
        raise TypeError("input must be a string")
    total = 0
    seen = set()
    i = 0
    while i < len(s):
        j = i
        while j < len(s) and s[j].isdigit():
            j += 1
        if j == i:
            raise ValueError("expected number")
        num = int(s[i:j])
        if j >= len(s):
            raise ValueError("missing unit")
        unit = s[j]
        if unit in seen:
            raise ValueError(f"duplicate unit: {unit}")
        seen.add(unit)
        i = j + 1
        if unit == 'h':
            total += num * 3600
        elif unit == 'm':
            total += num * 60
        elif unit == 's':
            total += num
        else:
            raise ValueError(f"invalid unit: {unit}")
    return total

Теперь запускаем differential test harness, который подаёт одни и те же inputs всем трём и помечает disagreements.

def differential_test(implementations, inputs):
    for case in inputs:
        results = []
        errors = []
        for impl in implementations:
            try:
                results.append(impl(case))
            except Exception as e:
                errors.append(type(e).__name__)
        if errors:
            if len(errors) == len(implementations) and len(set(errors)) == 1:
                print(f"ALL ERROR on {case!r}: {errors[0]}")
            else:
                print(f"MIXED on {case!r}: results={results}, errors={errors}")
        else:
            if len(set(results)) == 1:
                print(f"AGREE on {case!r}: {results[0]}")
            else:
                print(f"DISAGREE on {case!r}: {results}")

IMPLS = [parse_duration_a, parse_duration_b, parse_duration_c]

CASES = [
    "1h30m",      # normal
    "90m",        # single unit
    "30m1h",      # out of order
    "1h2h",       # duplicate unit
    "0h",         # zero is not positive
    "1.5h",       # decimal
    "1H",         # wrong case
]

differential_test(IMPLS, CASES)

Запуск даёт следующий результат:

AGREE on '1h30m': 5400
AGREE on '90m': 5400
MIXED on '30m1h': results=[5400, 5400], errors=['ValueError']
MIXED on '1h2h': results=[10800], errors=['ValueError', 'ValueError']
AGREE on '0h': 0
ALL ERROR on '1.5h': ValueError
ALL ERROR on '1H': ValueError

Harness ловит реальные проблемы. На 30m1h regex команды A отклоняет out-of-order input, в то время как команды B и C принимают его. На 1h2h scanner команды B тихо складывает оба часа, в то время как duplicate detection команды C выдаёт ошибку. Это именно те баги, которые differential testing должен находить.

Но посмотрите на 0h. Спецификация говорила «positive integer». Ноль не является positive. Все три реализации принимают его, потому что ни одна из команд не написала validation для требования, которое звучало очевидно, но не было enforced. Они согласны, поэтому test passes. Это common-mode failure, скрывающийся на виду.

То же самое происходит с 1H. Все три отклоняют его, потому что спецификация показывала lowercase units. Но если спецификация подразумевала case-insensitive matching, каждая implementation ошибочна, и они ошибаются вместе.

Как сделать differential testing менее ошибочным

Нельзя полностью устранить common-mode failures без формального доказательства. Но можно сделать их менее вероятными.

Диверсифицируйте implementation strategies, а не только персонал. Если каждая команда использует один и тот же algorithm из одного и того же учебника, вы не построили diversity. Вы построили latency. Заставьте одну команду использовать state machine, другую — parser generator, третью — recursion. Разные algorithms дают сбой на разных inputs.

Используйте разные programming languages. Общие баги standard library — классический common-mode failure. Если каждая implementation использует один и тот же JSON parser или одну и ту же floating-point math library, они разделяют её баги.

Добавьте adversarial oracle. Поручите кому-то находить inputs, где спецификация ambiguous. Их задача — заставить реализации disagree. Inputs, которые разделяют их, — это самые ценные tests, которые вы напишете.

Фаззите агрессивно. Agreement на горстке hand-picked examples — слабое доказательство. Agreement на миллионе randomly generated inputs — более сильное. Fuzzing обнаруживает углы input space, которые ни одна из команд не рассматривала.

Тестируйте саму спецификацию. Пишите явные negative tests для требований вроде «positive integer» и проверяйте, что хотя бы одна implementation отклоняет их. Если все три принимают invalid input, ваша спецификация нуждается в ужесточении, а не ваш код.

Когда differential testing достаточно

Differential testing не заменяет formal verification. Это filter. Он ловит implementation bugs дёшево и рано, прежде чем вы инвестируете в proof.

Вопрос не в том, можно ли ему доверять. Вопрос в том, для чего ему можно доверять. Можно доверять ему находить disagreements. Нельзя доверять ему находить universal agreement при наличии плохой спецификации.

Если вы строите safety-critical software, differential testing — это предварительный шаг. Запустите его, исправьте disagreements, затем подвергните спецификацию model checker или proof assistant. Если вы строите web service, differential testing может быть всей уверенностью, которая вам нужна для feature branch. Proof пропорционален ставкам.

Если сегодня вы запускаете N-version test suite, добавьте ещё один test case. Найдите input, который спецификация чётко не определяет. Пропустите его через ваши реализации. Если все согласны, вы нашли не хороший test. Вы нашли дыру в спецификации.

Баги, которые вас убивают, — не те, где ваши реализации disagree. Это те, где они согласны по неверной причине.

Часто задаваемые вопросы

Что такое differential testing?

Differential testing — это техника, при которой несколько независимых реализаций одной спецификации выполняются с идентичными inputs. Их outputs сравниваются. Disagreements выявляют баги без необходимости в предварительном source of truth для каждого input.

Что такое common-mode failure в ПО?

Common-mode failure происходит, когда несколько независимых components дают сбой на одном и том же input по одной и той же underlying reason. В N-version programming это обычно происходит, когда спецификация ambiguous и каждая команда разрешает эту неоднозначность одинаково.

Чем differential testing отличается от property-based testing?

Property-based testing проверяет, что outputs удовлетворяют общим правилам, например «сортировка списка никогда не меняет его длину». Differential testing проверяет, что несколько реализаций дают один и тот же output. Две техники дополняют друг друга. Property-based testing находит logic errors. Differential testing находит inconsistencies.

Могу ли я использовать LLMs для генерации diverse implementations для differential testing?

Можете, но будьте осторожны. Models, обученные на overlapping corpora, склонны производить код с correlated failure modes. Недавние исследования предполагают co-error rates между 15% и 30% для AI-generated components. Если вы используете LLMs, запрашивайте genuinely different algorithms и languages. Коллекция семантически идентичных rewrites не является diversity.