Software Fault Interactions and Implications for Software Testing (D. Richard Kuhn)

# 論文紹介

D. Richard Kuhn の Software Fault Interactions and Implications for Software Testing (ソフトウェア故障の相互作用とソフトウェアテストへの影響)という論文を読んだ。

[KUHN, D. Richard; WALLACE, Dolores R.; GALLO, Albert M. Software fault interactions and implications for software testing. IEEE transactions on software engineering, 2004, 30.6: 418-421.](https://scholar.google.co.jp/scholar?hl=ja&as_sdt=0%2C5&q=Software+Fault+Interactions+and+Implications+for+Software+Testing+Kuhn&btnG=)

本論文は、組み合わせテストをどこまで網羅的にすればよいかを調べたものである。
たとえば、ソフトウェアへの入力が20個あり、それぞれ10個の値を取りうる場合、組み合わせの総数は`10^20`もあり、すべてのテストは困難である。

そこで、Kuhnは、先行研究も参照しつつ、自らNASAの不具合報告書の事例を調べてソフトウェア故障と故障に関連するパラメータの数の関係を整理した。

その結果、開発フェーズやシステムの特性によらず、おおむね `4 <= n <= 6`個までのパラメータの組み合わせを網羅的にテストすれば必要十分だろうと結論づけた。

本論文は、943 回（2022年7月24日時点）引用されており、かなり著名な論文である。

# 論文概要

## 1. はじめに

* 限られたコストと期間ですべてのパターンを網羅したテストは実現困難。
* 少ないパラメータの組み合わせで不具合が不具合が発生することがわかっていれば、組み合わせ数を減らしても擬似的に網羅的テストが行える。
* このパラメータの組み合わせ数をFTFI (failure-triggering fault interaction; 故障誘発性障害相互作用)数と呼ぶ。

## 2. 関連研究

* 実データを用いて障害の特徴を調査した先行研究は3つしかない。
    * Nairらは、2つの既知の欠陥を有する画面を持つ小さなソフトウェアを例として、組み合わせテストについてケーススタディをした。この結果、ペアワイズテストが欠陥を検出するのに十分であった。
    * Wallanceらは、医療機器の15年あいだのリコール342件のデータを調べた。すべてのペアをテストする、つまり `FTFI = 2` でテストすれば97%の欠陥を検出可能で、最大で`FTFI = 4`あることがわかった。
    * Kuhn and Reilly は、Firefox と Apacheのバグレポートを調べ、 `FTFI <= 2`が70%以上あり、最大で`FTFI = 5`であることがわかった。
* さらに3つの先行研究がある。
    * Smithらは、NASAでRAX(Remote Agent Experiment)というエキスパートシステムに対して、ペアワイズテストを実行し、不具合を分類し、整理した。
    * Panらは、POSIX OSのモジュールのエラーを調べて、`FTFI = 1`で80%以上のエラーが発生していることを確認した。

| FTFI No. | RAX<br/>convergence | RAX<br/>correctness | RAX<br/>interf | RAX<br/>engine | POSIXモジュール | 医療機器 | ブラウザ | サーバー | NASA GSFC |
| -------- | ------------------- | ------------------- | -------------- | -------------- | --------------- | -------- | -------- | -------- | --------- |
| 1        | 61                  | 72                  | 48             | 39             | 82              | 66       | 29       | 42       | 68        |
| 2        | 97                  | 82                  | 54             | 47             |                 | 97       | 76       | 70       | 93        |
| 3        | *                   | *                   | *              | *              | *               | 99       | 95       | 89       | 98        |
| 4        | *                   | *                   | *              | *              | *               | 100      | 97       | 96       | 100       |
| 5        | *                   | *                   | *              | *              | *               |          | 99       | 96       |           |
| 6        | *                   | *                   | *              | *              | *               |          | 100      | 100      |           |

`*` はレポートされていない意味

## 3. 実証データ

* 先行研究に加えて、NASA GSFC(Goddard Space Flight Center)で開発された分散システムのエラーレポート 329 件を解析した。
* 解析の結果次のことがわかった。
    * FTFIは冪乗則に従う。つまり、FTFIが大きくなるほど急激に件数が減る。
    * 開発中のバグと出荷後のバグのFTFIの傾向には、明確な違いが見られなかった。

## 4. テストへの示唆

* v個の値（水準値）を取りうる k 個のパラメータ（因子）から n (k < n) 個を抽出してテストをすることを n-tuple と呼ぶ。
* n-tuple のテスト件数は、 `C(k, n) * v^n` となる。ここで、`C(k, n) = k!/(n!(k-n)!)`。
* `N = 10^x`のテストケースでカバーできる水準値の最大値は、`v <= N^(1/n)`と計算できる。テスターがテストケースのケース数を見積もる際に役立つ。

## 5. 結論

* すべての調査において、FTFI数はせいぜい4〜6個までと少なかった。
* おおむねFTFIが `4 <= n <= 6`までの範囲でテストをすれば十分だろうと思われる。