Metamorphic testingはGCCとLLVMで147件の確認済みバグ、自動車OEMが使用する商用ADASシミュレータの欠陥、そして歩行者を轢き殺す8日前に自動運転車の認識システムにおいて致命的な欠陥を発見した。この手法は学術的に聞こえるが、バグは学術的ではない。
問題はoracle problemだ。多くのプログラムにおいて、入力を実行することはできても、出力が正しいかを独立して検証することはできない。1万ノードの道路網を通る正確な最短経路は何か？このcompiler optimizationは意味を保っているか？このMLモデルの分類は実際に正しいか？わからない。従来のunit testingはここで機能不全に陥る。expectedが何であるべきかわからないのに、assertEquals(expected, actual)を書くことはできないからだ。
Metamorphic testingはそもそも出力をチェックしないことで、この問題を迂回する。出力同士の関係性をチェックするのだ。
Metamorphic testingとは何か
Metamorphic testingは、入力を関連する入力に変換し、両方をプログラムに通して、2つの出力が既知の数学的または論理的な関係に従うことを表明する手法である。この関係性をmetamorphic relationと呼ぶ。
プログラムが数値のリストの平均を計算する場合、テストのために[4.2, 1.7, 9.3, 2.1]の正確な平均を知る必要はない。リストをシャッフルしても同じ結果が出ること、すべての要素を2倍にすれば平均も2倍になることを知るだけでよい。これらがmetamorphic relationである。
最初の入力を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が実際の本番ソフトウェアで本物のバグを発見した記録された事例を示す。
GCCとLLVMの147件のバグ
研究者たちはmetamorphic testingをC compiler optimization pipelinesに適用し、GCCとLLVM全体で147件の確認済みバグを発見した。これらはおもちゃのプログラムではなかった。正しいCプログラムがoptimizing compilerを通すと不正な機械語コードを生成する、実際のmiscompilationバグであった。これらのバグの中には数年間存在していたものもあった。metamorphic relationsは単純なものだった：関数を手動でinline化しても、最適化された出力は元と同じ動作をするはずだ。独立した文の順序を入れ替えても、結果は変わらないはずだ。コンパイラ開発者たちはこれらのバグを確認し、修正した。
GoogleのVulkanシェーダコンパイラ
GoogleのGraphicsFuzzチームは、Khronos Vulkan Conformance Test Suite向けにランダム化されたmetamorphic testingを本番環境に導入した。ランダムなfragment shadersを生成し、意味保存変換（式をidentity functionsで囲む、dead codeを追加するなど）を適用し、異なるコンパイラとGPU間でレンダリングされた画像を比較した。2つの理論的に等価なシェーダが異なるピクセルを生成したとき、コンパイラバグを発見したことになる。チームはgfautoと呼ばれるパイプライン全体を構築し、これらのケースを縮小、重複排除、報告した。Vulkanシェーダを変換、最適化、検証するツールのエコシステム、エンドユーザーに出荷された本番ドライバーを含め、バグを発見した。
自動車OEMが使用するADASシミュレータ
あるチームは、3つの人気のあるADASシミュレーションプラットフォームであるSimulink、CarMaker、51Sim-One Cloudをテストし、それぞれのレーンキープアシストシステムに焦点を当てた。通常のテストケースは3つのプラットフォームすべてでパスした。全く問題はなかった。そこでチームは幾何学的なmetamorphic relationsを適用した：道路シーンを水平方向にミラーリングし、車両位置を回転させ、車線標示にaffine transformationsを適用する。出力は予測可能な形で変換されるはずだった。しかしそうはならなかった。3つのプラットフォームすべてでバグが明らかになった。MathWorksとIPG Automotiveは後にこれらの問題を確認した。これらは、車両に搭載される前にソフトウェアを検証するために使用されるのと同じプラットフォームである。
同じクラスの self-driving car の欠陥
最も深刻な事例の一つで、研究者たちは自動運転車の物体検出システムにmetamorphic testingを適用し、認識パイプラインのバグを発見した。システムは特定の変換された入力の下で歩行者を正しく分類できなかった。彼らは報告した。彼らが発見したバグは、致命的な self-driving car 歩行者衝突と関連付けられている同じクラスの欠陥であった。
トレードオフ：関係性はドメイン固有である
Metamorphic testingは強力だが、タダではない。難しいのは、優れたmetamorphic relationsを特定することだ。悪い関係性は偽の自信を与える。弱すぎる関係性はバグを捉えられない。強すぎる関係性は、floating-pointのノイズや非決定論性によって正しい動作でも失敗する。
関係性の設計にはドメイン知識が必要だ。最短経路アルゴリズムの場合、優れた関係性には以下が含まれる：無向グラフにおいて、A→Bの経路コストはB→Aと等しくなるはずだ；すべての辺の重みに定数を加えると、総経路コストにその定数と辺の数を掛けた値が加わるはずだ。ソートアルゴリズムの場合：ソート済みリストを逆順にしてからソートすると、元のソート済みリストの逆順が得られるはずだ；出力のすべての要素は、入力に同じ頻度で現れるはずだ。
無関係なシステム間で同じ関係性を再利用することはできない。それが代償だ。
Floating-point演算はもう一つの落とし穴だ。多くの関係性は正確な等価性を前提とするが、IEEE 754では0.1 + 0.2 != 0.3である。許容誤差に基づく比較が必要であり、適切な許容誤差を選ぶこと自体が問題だ。厳しすぎると偽陽性が出る。緩すぎると本物のバグを見逃す。
codebaseにmetamorphic testingを追加する方法
フレームワークは不要だ。規律が必要だ。
codebase内でoracleを持たない関数から始める。ML inference、optimization algorithms、geometric computations、statistical aggregations、simulation codeはすべて候補だ。それぞれについて、入力を特定の予測可能な方法で変更した場合、出力について何が真であるべきかを問う。
テスト関数ごとに1つのmetamorphic relationを書く。明確に命名する。unit testsと並行してCIで実行する。関係性が失敗したら、他のテストの失敗とまったく同じように扱う。
以下に、pathfinding関数をテストするやや現実的な例を示す。
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はunit testsを代替するのか？
いいえ。補完するものだ。予想される出力がわかっているときはunit testsを使う。わからないときはmetamorphic testsを使う。
MLモデルにこれを使えるか？
はい、そしてそれは最も活発な研究分野の一つだ。「猫の画像を回転させても猫として分類されるはず」といった関係性はmetamorphic relationsである。研究者たちはこのアプローチを用いて、モデルの信頼性の問題や公平性の格差を発見してきた。
自分のmetamorphic relationが正しいかどうかをどうやって知るか？
証明はしない。仕様またはドメインの数学的性質から論じる。関係性自体にバグがあれば、偽陽性が出る。明白な性質から始め、自信がついたら徐々に追加する。
不安定なテストはどうか？
非決定論的システム（確率的アルゴリズム、並列コード、タイムアウトを持つシステム）はmetamorphic testingを困難にする。複数回の試行を実行する必要があるかもしれないし、正確な等価性ではなくstatistical relationsを使う必要があるかもしれない。
1つの関係性から始めよう
これを使うのにPhDは不要だ。システム内で、出力の検証が難しすぎるために現在テストをスキップしている関数を1つ選ぶ。1つのmetamorphic relationを書く。実行する。さらに深く知りたい場合、GraphicsFuzzチームのgfauto toolingはオープンソースであり、SeguraらによるACM surveyは数十のドメインにわたる関係性をカタログ化している。
この手法は147件のコンパイラバグを発見し、自動車シミュレーションプラットフォームの確認済み欠陥を明らかにし、自動運転車が道路に出る前に認識の故障のクラスを暴き出した。バグは本物だ。唯一の問題は、あなたがそれらを探しているかどうかだけだ。