Differential Testingが実際にもたらすもの
形式的証明がなくてもdifferential testingを信頼できるが、その前提はどこで破綻するかを正確に理解していることだ。
その弱点はcommon-mode failureと呼ばれる。specificationのすべての実装が同じ誤った仮定をした場合、それらはすべて合意し、test harnessは合格と判定する。N-version programmingはbad specに対しては保護してくれない。
Differential testingは、同じspecificationの複数の独立した実装を同じ入力に対して実行することで機能する。出力が不一致なら、少なくとも1つにバグがある。一致すれば、暫定的に正しいとみなす。
これは強力なのは、test oracleが不要になるからだ。oracleは、すべての入力に対する正解を知る真実のソースである。複雑なシステムでは、oracleを構築する方がシステム自体を構築するよりも難しいことが多い。tax engine、physics simulation、protocol decoderは、すべての出力が何であるべきかを証明できるようになるずっと前から、一貫性のためにテストできる。
だが、その暫定性は重要だ。合意は一貫性を証明するだけで、正しさを証明するわけではない。
なぜ合意は正しさではないのか
理論では誰もが学び、実践では誰もが忘れるfailure modeがcommon-mode faultだ。エラーがspecification自体に起因する場合、またはすべての実装チームが独立して行う共通の仮定に起因する場合、すべてのバージョンが同じ間違った答えを生み出す。
specが明らかに間違っている必要はない。人間の脳が同じように解決するedge caseで曖昧であれば十分だ。
頂点のリストから単純な多角形の面積を計算する関数のspecificationを想像してほしい。specはshoelace formulaを提供するが、vertex orderingについては一切言及しない。
3つのチームが実装する。3チームすべてがcounter-clockwise orderingを仮定する。なぜなら、例の図がそのように描かれているからだ。clockwiseの入力は、raw formulaでは負の面積を生み出す。3チームすべて、面積は正でなければならないという理由で、静かに結果を abs() でラップする。すべてのtest caseで一致する。
だが、specはclockwiseが無効だと言ったわけではない。実装は一貫しており、欠落によって間違っている。differential testingはそれらすべてに合格を出す。
3つの実装、1つの曖昧なSpec
以下は実行できる具体的な例だ。specificationにはこう書かれている。「duration stringをパースし、合計秒数を返す。durationは1つ以上のcomponentからなる。各componentは正の整数に続くunit letterである。hは時間、mは分、sは秒を表す。」
3つのチームがこのspecを受け取り、それぞれ独自のparserを書く。
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次に、3つすべてに同じ入力を与え、不一致をflagするdifferential test harnessを実行する。
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': ValueErrorharnessは本物の問題を捉える。30m1h では、Team Aのregexが順序が狂った入力を拒否する一方、Team BとCは受け入れる。1h2h では、Team Bのscannerが静かに両方の時間を足す一方、Team Cのduplicate detectionはエラーを発生させる。これらはまさにdifferential testingが見つけるべきバグだ。
だが 0h を見てほしい。specificationには「positive integer」と書かれていた。ゼロは正ではない。3つの実装すべてがこれを受け入れる。なぜなら、どのチームも、自明に聞こえたが実際には施行されていない要件のvalidationを書かなかったからだ。それらは一致するので、テストは通過する。これは平然と隠れているcommon-mode failureだ。
1H でも同じことが起きる。3つすべてがこれを拒否する。なぜなら、specは小文字のunitを示していたからだ。だが、もしspecがcase-insensitive matchingを意図していたら、すべての実装が間違っており、それらは一緒に間違っている。
Differential Testingをより間違いにくくする方法
形式的証明なしにcommon-mode failureを完全に排除することはできない。だが、発生確率を下げることはできる。
人だけでなく、実装戦略を多様化する。すべてのチームが同じ教科書から同じalgorithmを使うなら、多様性は構築されていない。latencyを構築しているだけだ。1つのチームにはstate machineを、もう1つにはparser generatorを、3つ目にはrecursionを使わせる。異なるalgorithmは異なる入力で失敗する。
異なるprogramming languagesを使う。共通のstandard libraryのバグは古典的なcommon-mode failureだ。すべての実装が同じJSON parserや同じfloating-point math libraryを使うなら、それらはそのバグを共有する。
adversarial oracleを加える。誰かに、specificationが曖昧になる入力を見つけるよう割り当てる。彼らの仕事は、実装を不一致にすることだ。それらを分断する入力は、あなたが書く最も価値のあるテストだ。
積極的にfuzzする。handfulの手選びの例での合意は弱い証拠だ。100万のランダムに生成された入力での合意はより強い。fuzzingは、どのチームも考慮しなかったinput spaceの隅を発見する。
specification自体をテストする。「positive integer」のような要件に対して明示的なnegative testsを書き、少なくとも1つの実装がそれらを拒否することを確認する。3つすべてが無効な入力を受け入れるなら、codeではなくspecを厳密化する必要がある。
Differential Testingで十分な場合
Differential testingはformal verificationの代わりではない。それはfilterだ。証明に投資する前に、安価かつ早期にimplementation bugsを捉える。
問うべきは、それを信頼できるかどうかではない。それを何のために信頼できるか、ということだ。不一致を見つけることは信頼できる。bad specがある状況で普遍的な合意を見つけることは信頼できない。
safety-critical softwareを構築しているなら、differential testingは予備的なステップだ。実行し、不一致を修正し、次にspecificationをmodel checkerやproof assistantにかける。web serviceを構築しているなら、differential testingはfeature branchに必要な信頼性のすべてかもしれない。証明はリスクに比例する。
今日N-version test suiteを実行しているなら、もう1つtest caseを追加しろ。specificationが明確に定義していない入力を見つける。それを実装に通す。すべてが一致するなら、良いテストを見つけたわけではない。specificationの穴を見つけたのだ。
致命的なバグは、実装が不一致になるものではない。間違った理由で一致するものなのだ。
よくある質問
Differential testingとは何か
Differential testingは、同じspecificationの複数の独立した実装を同一の入力で実行する手法である。出力が比較される。不一致は、すべての入力に対する事前に存在する真実のソースを必要とせずにバグを明らかにする。
ソフトウェアにおけるcommon-mode failureとは何か
common-mode failureは、複数の独立したcomponentが同じ入力で同じ根本的な理由により失敗するときに発生する。N-version programmingでは、これは通常、specificationが曖昧で、すべてのチームがその曖昧さを同じ方法で解決したときに起こる。
Differential testingとproperty-based testingの違いは何か
Property-based testingは、出力が一般的なルールを満たすかを確認する。たとえば「リストをソートしても長さは変わらない」。differential testingは、複数の実装が同じ出力を生み出すかを確認する。2つの手法は互いに補完する。property-based testingはlogic errorsを見つける。differential testingはinconsistenciesを見つける。
LLMを使ってdifferential testing用の多様な実装を生成できるか
できるが、注意が必要だ。重複するcorporaで訓練されたモデルは、相関したfailure modesを持つコードを生成する傾向がある。最近の研究では、AI生成のcomponentにおけるco-error rateは15%から30%の間にあることが示唆されている。LLMを使う場合は、本当に異なるalgorithmやlanguageを求めるpromptを出す。意味的に同一のrewriteの集合は、diversityではない。