# テストの理論：網羅基準・同値分割と境界値・突然変異テスト > テストが示せることと示せないことを定理として整理する。有限のテストの不完全性、網羅基準の包含関係と検出力の違い、MC/DC に要るテストの数、境界値テストが検出を保証する誤りのモデル、ペアワイズ網羅の大きさの上下界、突然変異テストを証明し、pytest と coverage.py の実行例で確かめる。 > https://rikai.mugen-giken.com/computer-science/software-design-testing/testing-theory ## 0. この記事の要点 プログラムを作ったあと、「テストが全部通ったから大丈夫」と言ってよいのでしょうか。テストは有限個の入力しか試せないので、通ったことと正しいことのあいだには隙間があります。この記事は、その隙間に何があるのかを、「どこを実行したか」「どの入力を選んだか」「わざと壊したら気づくか」という 3 つの見方で整理します。読み終えると、網羅率の数字やテストの設計法が、それぞれ何を保証して何を保証しないかを説明できるようになります。 - 入力が無限にあるとき、どんな有限のテスト集合にも、**全部に合格して仕様に違反するプログラム**があります。テストは誤りの存在を示せますが、不在は示せません。 - 誤り（故障）が失敗として観測されるには、その箇所に**到達**し、状態が**感染**し、出力まで**伝播**し、オラクル（出力が合格かどうかを判定する仕組み）がそれを見ている必要があります。網羅率が保証するのは到達までです。 - 網羅基準には包含関係（経路網羅 ⇒ 分岐網羅 ⇒ 文網羅、MC/DC ⇒ 条件網羅かつ分岐網羅）がありますが、**包含は検出力の大小を意味しません**。強い基準を満たすテスト集合が見逃す誤りを、弱い基準を満たす別のテスト集合が見つけることがあります。 - $n$ 個の条件からなる判定の MC/DC（各条件が単独で判定の結果を変えることを、テストで実際に見せる基準）には少なくとも $n + 1$ 個のテストが要り、各条件が 1 回ずつ現れる式ではちょうど $n + 1$ 個で足ります。全組合せは $2^n$ 個です。 - 境界値テスト（各境界の値と、その 1 つ手前）は、「実装の切り替わり点の数が仕様と同じ以下」というモデルの中の誤りを**すべて**検出します。モデルの外の誤りは見逃します。 - $k$ 個の因子（各 $v$ 値）のすべての 2 因子の組合せは、$v^k$ 個ではなく高々 $\lceil 2v^2 \ln k \rceil + v^2$ 個のテストで網羅できます。 ## 1. 動機 [契約による設計](/computer-science/software-design-testing/contracts-and-invariants) では、プログラムが契約を満たすことを証明する方法を見ました。同時に、その判定に機械的な近道がないこと（）も見ました。実際の開発では、証明されるプログラムはごく一部で、大半の品質はテストに支えられています。 テストについては、経験則がたくさん語られます。「網羅率 80% を目指す」「境界を狙え」「組合せはペアワイズで十分」。これらは便利ですが、どれも「なぜそれで足りるのか」「何を見逃すのか」が付いていません。網羅率 100% のテストが通ったあとで不具合が見つかったとき、経験則は何も説明してくれません。 この記事では、テストの設計法を**定理**として述べ直します。定理の形にすると、主張にはかならず仮定が付きます。「境界値テストは誤りを検出する」は、誤りがある種類に限られるという仮定のもとでだけ正しい。その仮定（誤りのモデル）を明示することが、テスト設計の根拠を持つということです。逆に、仮定の外にある誤りは、その方法では見つからないと分かります。テストの方法は 1 つでは足りず、性質の違う方法を組み合わせる理由がここにあります。 E. W. Dijkstra は 1970 年前後に、テストは誤りがあることを示すのには使えるが、無いことを示すのには使えない、という趣旨の言葉を残しました。この記事はまずそれを命題として証明し（第 2 節）、そのうえで「では有限のテストで何が言えるのか」を順に見ていきます。 ## 2. テストで言えること ### 2.1. テスト集合とオラクル 仕様と実装の定義は前章のもの（）を使います。仕様は、約束の範囲 $D \subseteq X$ と、許される入出力の関係 $S \subseteq X \times Y$ の組 $(D, S)$ で、実装は $X$ から $Y$ への部分関数 $f$ でした。 仕様 $(D, S)$ を固定する。 - **テストケース**とは、入力 $x \in D$ をいう。空でない有限集合 $T \subseteq D$ を**テスト集合**という。 - **オラクル**とは、関係 $O \subseteq X \times Y$ をいう。$(x, y) \in O$ は「入力 $x$ に対する出力 $y$ を合格とする」ことを表す。$O \cap (D \times Y) = S \cap (D \times Y)$ のとき $O$ は**正確**であるといい、$S \cap (D \times Y) \subseteq O$ のとき $O$ は**健全**である（正しい出力を不合格にしない）という。 - 実装 $f$ がオラクル $O$ のもとでテスト集合 $T$ に**合格する**とは、すべての $x \in T$ について $f(x)$ が定まり、$(x, f(x)) \in O$ であることをいう。そうでないとき、$T$ は $f$ の誤りを**検出する**という。 「期待値と比べる」テストは、$O = \{(x, y) \mid y = \text{期待値}(x)\}$ というオラクルです。「例外が出なければ合格」というテストは、$O$ がほとんどすべての出力を含む、健全ですが正確からほど遠いオラクルです。オラクルの強さは、第 2.2 節で網羅率と同じくらい効いてくることが分かります。 仕様 $(D, S)$ を満たす実装 $f$ が存在するとし、$T \subseteq D$ をテスト集合、$O$ を正確なオラクルとする。 1. ある $x^{*} \in D \setminus T$ と $y^{*} \in Y$ について $(x^{*}, y^{*}) \notin S$ であるとする。このとき、$T$ に合格し、仕様 $(D, S)$ を満たさない実装 $g$ が存在する。$g$ は、$f$ に「入力が $x^{*}$ と等しいか」を調べる分岐を 1 つ足したものにとれる。 2. とくに $D$ が無限集合で、$S$ がどの入力についても何らかの出力を禁じている（すべての $x \in D$ に $(x, y) \notin S$ となる $y$ がある）ならば、どんなテスト集合 $T$ についても (1) の $g$ が存在する。 3. 逆に $D$ が有限で $T = D$ ならば、「$f$ が $T$ に合格する」ことと「$f$ が仕様を満たす」ことは同値である。 (1) $g$ を $$ g(x) = \begin{cases} y^{*} & (x = x^{*}) \\ f(x) & (x \ne x^{*}) \end{cases} $$ と定めます。$x \in T$ なら $x \ne x^{*}$（$x^{*} \notin T$）なので $g(x) = f(x)$ で、$f$ は仕様を満たすので $f(x)$ は定まり $(x, f(x)) \in S$、$O$ は正確なので $(x, g(x)) \in O$ です。よって $g$ は $T$ に合格します。一方 $x^{*} \in D$ で $(x^{*}, g(x^{*})) = (x^{*}, y^{*}) \notin S$ なので、$g$ は仕様を満たしません。 (2) $T$ は有限、$D$ は無限なので $D \setminus T$ は空でありません。$x^{*} \in D \setminus T$ を 1 つとり、仮定から $(x^{*}, y^{*}) \notin S$ となる $y^{*}$ をとれば、(1) の仮定が満たされます。 (3) $f$ が $T = D$ に合格するとは、すべての $x \in D$ で $f(x)$ が定まり $(x, f(x)) \in O$ となることです。$O$ は正確なので、$x \in D$ については $(x, f(x)) \in O$ と $(x, f(x)) \in S$ が同値です。これは $f$ が仕様を満たすことの定義です。 (1) の $g$ は作為的に見えますが、現実の誤りの多くはこの形をしています。特定の入力（$0$、空の列、うるう年、最大値）だけで誤る実装は、その入力がテスト集合に入っていなければ見つかりません。前章の言葉でいえば、違反入力の集合 $V$ がテスト集合 $T$ と交わらない、ということです（ (1)）。 (3) は、入力が有限なら全数テストが証明になることを言っています。ただし「有限」はすぐに手に負えなくなります。32 ビットの整数 2 つを受け取る関数の入力は $2^{64} \approx 1.8 \times 10^{19}$ 個で、1 秒に $10^9$ 個を試しても $1.8 \times 10^{10}$ 秒、およそ 585 年かかります。全数テストが現実的なのは、8 ビットの演算や、状態数の少ない有限状態機械などに限られます。 したがって、テストの理論の問いは「どのテスト集合 $T$ を選ぶか」になります。 は、仮定なしにはどの $T$ も不十分だと言っています。以下の各節は、**誤りについての仮定**を置くと、ある $T$ で十分になる（あるいは、ならない）という形の主張です。 ### 2.2. 故障・誤り状態・失敗 誤りが「ある」ことと、テストで「見える」ことのあいだには、いくつもの段があります。それを述べるために、プログラムを制御フローグラフとして定めます。 先に小さな例で感覚をつかんでおきます。`y = x * 2` と書くべきところを `y = x + 2` と書いてしまったとします。誤りのある行を実行しても（到達）、$x = 2$ では両方とも $4$ で、値は正しいままです。$x = 3$ では $5$ と $6$ になり、値が食い違います。さらにその値が最後の出力に影響して初めて、テストの不合格として見えます。以下の定義は、この「行に着く、値がおかしくなる、出力に出る」という段を厳密に言い直したもので、制御フローグラフは if 文やループを、文と判定を頂点、実行の順序を矢印とする図で表したものです。 **制御フローグラフ**によるプログラム $p$ とは、次のものの組をいう。 - 有向グラフ $G = (N, E)$（）と、**入口** $s \in N$、**出口** $t \in N$。$t$ の出次数は $0$。 - 状態の集合 $\Sigma$、入力から初期状態への写像 $\mathrm{in} : X \to \Sigma$、状態から出力への写像 $\mathrm{out} : \Sigma \to Y$。 - $t$ 以外の各頂点 $n$ は**文**か**判定**のどちらかである。文 $n$ は出次数が $1$ で、写像 $a_n : \Sigma \to \Sigma$（文の効果）をもつ。判定 $n$ は出次数が $2$ で、2 本の辺に $1$（真）と $0$（偽）のラベルが付き、写像 $d_n : \Sigma \to \{0, 1\}$ をもつ。$d_n$ は、**条件** $c_{n,1}, \ldots, c_{n,k} : \Sigma \to \{0, 1\}$ とブール関数 $\varphi_n : \{0, 1\}^k \to \{0, 1\}$（）によって $d_n(\sigma) = \varphi_n(c_{n,1}(\sigma), \ldots, c_{n,k}(\sigma))$ と表されているとする。 入力 $x$ に対する**実行**とは、次で定まる列 $(n_0, \sigma_0), (n_1, \sigma_1), \ldots$ をいう。$n_0 = s$、$\sigma_0 = \mathrm{in}(x)$。$n_i$ が文なら $\sigma_{i+1} = a_{n_i}(\sigma_i)$ で、$n_{i+1}$ は $n_i$ から出る辺の先。$n_i$ が判定なら $\sigma_{i+1} = \sigma_i$ で、$n_{i+1}$ はラベル $d_{n_i}(\sigma_i)$ の辺の先。$n_L = t$ となったら実行は終わり、$p(x) = \mathrm{out}(\sigma_L)$ を出力とする。このとき頂点の列 $\pi_p(x) = (n_0, \ldots, n_L)$ は $s$ から $t$ への歩道（）で、これを $x$ の**実行経路**という。$t$ に至らないとき $p(x)$ は定まらない。 頂点・辺・$s$ から $t$ への歩道が、ある $x \in D$ の実行経路に現れる（歩道の場合は実行経路に等しい）とき、それは**実行可能**であるという。 if 文は判定 1 つと 2 つの枝、ループは判定から自分に戻る閉路になります。`a and b` のような複合条件は、1 つの判定の中の条件 $c_1 = a$、$c_2 = b$ と $\varphi(c_1, c_2) = c_1 \wedge c_2$ です。この記事では、判定に入ったら条件はすべて評価されるものとします（短絡評価をする言語でも、条件に副作用がなければ判定の真偽は変わりません）。 $p_0$ を仕様を満たすプログラム、$p$ を、$p_0$ と同じグラフをもち、1 つの頂点 $n$ の写像（$a_n$ または $d_n$）だけが異なるプログラムとする。$n$ を $p$ の**故障**（fault）という。入力 $x \in D$ について、$p$ の実行を $(n_i, \sigma_i)$、$p_0$ の実行を $(n^0_i, \sigma^0_i)$ とする。 - **到達**: $n$ が実行経路 $\pi_p(x)$ に現れる。 - **感染**: ある $i$ で、$(n_j, \sigma_j) = (n^0_j, \sigma^0_j)$（$j \le i$）、$n_i = n$、かつ $(n_{i+1}, \sigma_{i+1}) \ne (n^0_{i+1}, \sigma^0_{i+1})$ となる。このとき $(n_{i+1}, \sigma_{i+1})$ を**誤り状態**（error）という。 - **伝播**: $p(x) \ne p_0(x)$（一方だけが定まらない場合を含む）。これを**失敗**（failure）という。 の状況で、入力 $x$ について伝播が起きるならば感染が起き、感染が起きるならば到達が起きる。とくに、$n$ が $\pi_p(x)$ に現れなければ、$p$ と $p_0$ の $x$ に対する実行は一致し、$p(x) = p_0(x)$ である。この主張は $p_0$ が仕様を満たすことを使わず、同じグラフをもち 1 つの頂点 $n$ の写像だけが異なる任意の 2 つのプログラムについて成り立つ。 感染が起きるなら、定義の $i$ について $n_i = n$ なので、$n$ は $\pi_p(x)$ に現れます。これが「感染 ⇒ 到達」です。 「伝播 ⇒ 感染」を対偶で示します。感染が起きないとします。すべての $i$ について $(n_i, \sigma_i) = (n^0_i, \sigma^0_i)$ であることを、$i$ についての帰納法（）で示します。$i = 0$ では、どちらも $(s, \mathrm{in}(x))$ です。$i$ まで一致しているとします。$n_i \ne n$ なら、$p$ と $p_0$ は頂点 $n_i$ で同じ写像をもつので、同じ状態 $\sigma_i$ から同じ $(n_{i+1}, \sigma_{i+1})$ に進みます。$n_i = n$ なら、感染が起きないという仮定から $(n_{i+1}, \sigma_{i+1}) = (n^0_{i+1}, \sigma^0_{i+1})$ です。したがって 2 つの実行は列として一致し、一方が $t$ に至れば他方も同じ状態で $t$ に至り、出力は等しく、一方が $t$ に至らなければ他方も至りません。よって伝播は起きません。 最後の主張は、到達しなければ感染せず、いま示したとおり実行が一致することから従います。 逆向きは成り立ちません。到達しても感染しないことがあり（`x * 2` を `x + 2` と誤っても $x = 2$ では同じ値）、感染しても伝播しないことがあります（誤った中間値が、あとの計算で使われない・打ち消される）。前章の表明つき二分探索の例では、$140$ 個の入力のうち $84$ 個で誤った枝に到達して状態が感染し（`hi` が正しい値より $1$ 小さくなります。同じ入力で数え直した値です）、そのうち返り値まで伝播したのは $15$ 個でした。 実装 $f$ がすべての $x \in D$ で停止して値を返すとする。オラクル $O$ が $\{(x, f(x)) \mid x \in D\} \subseteq O$ を満たすならば、$f$ はどんなテスト集合 $T$ にも合格する。とくに「例外を出さずに値を返せば合格」とするオラクル $O = D \times Y$ のもとでは、仕様を満たさない $f$ も、実行可能な経路をすべて通るテスト集合に合格する。 $x \in T \subseteq D$ とします。$f(x)$ は定まり、仮定から $(x, f(x)) \in O$ です。これがすべての $x \in T$ で成り立つので、 の定義により $f$ は $T$ に合格します。$O = D \times Y$ は $\{(x, f(x)) \mid x \in D\}$ を含むので、後半はその特別な場合です。$T$ がどの経路を通るかは、この議論に現れません。 自明な命題ですが、実務では見落とされがちです。「関数を呼んで、例外が出ないことだけを確かめる」テストは、網羅率の数字を上げますが、到達・感染・伝播の 3 条件がすべてそろった入力でも失敗を報告しません。**網羅率はテストの入力の側の指標で、オラクルの側については何も測っていない**のです。前章の のように途中に表明を置くことは、オラクルを強めて、伝播する前の誤り状態を見えるようにすることにあたります。正しい出力が分からない関数にどうオラクルを与えるかは、次章の性質ベーステストの主題です。 ## 3. 構造に基づく網羅基準 ### 3.1. 定義 「プログラムのどこを実行したか」でテスト集合の十分さを測る基準を定めます。以下、プログラム $p$ はすべての $x \in D$ で停止するとします。 MC/DC の「独立対」は、`a and b` で考えると分かりやすくなります。$(a, b) = (1, 1)$ では判定は真、$a$ だけを $0$ にした $(0, 1)$ では偽になります。ほかの条件 $b$ を固定したまま $a$ だけを変えて結果が変わる、この 2 つのテストが $a$ の独立対です。同様に $(1, 1)$ と $(1, 0)$ が $b$ の独立対で、3 つのテスト $(1, 1)$、$(0, 1)$、$(1, 0)$ で両方の条件の独立対がそろいます。 $p$ を制御フローグラフによるプログラム、$T$ をテスト集合とする。$T$ の実行で判定 $n$ を訪れたときの条件の値の組 $(c_{n,1}(\sigma), \ldots, c_{n,k}(\sigma))$ の全体を $U_n(T) \subseteq \{0, 1\}^k$ と書く。 - **文網羅**: 実行可能な頂点はすべて、ある $x \in T$ の実行経路に現れる。 - **分岐網羅**: 実行可能な辺はすべて、ある $x \in T$ の実行経路に現れる。 - **条件網羅**: 各判定 $n$ の各条件 $c_{n,i}$ について、$D$ の入力の実行でその条件が値 $b \in \{0, 1\}$ をとることがあるなら、$U_n(T)$ にも第 $i$ 成分が $b$ の元がある。 - **MC/DC**（改良条件判定網羅）: 分岐網羅を満たし、さらに各判定 $n$ の各条件 $c_{n,i}$ について、$u$ と $u'$ が第 $i$ 成分だけで異なり $\varphi_n(u) \ne \varphi_n(u')$ となる $u, u' \in U_n(D)$ が存在するなら、そのような $u, u'$ が $U_n(T)$ の中にも存在する。この組 $(u, u')$ を条件 $c_{n,i}$ の**独立対**という。 - **経路網羅**: 実行可能な $s$ から $t$ への歩道はすべて、ある $x \in T$ の実行経路に等しい。 基準 $\mathsf{A}$ が基準 $\mathsf{B}$ を**包含する**とは、どんなプログラム $p$ と入力の範囲 $D$ についても、$\mathsf{A}$ を満たすテスト集合がすべて $\mathsf{B}$ を満たすことをいう。 どの基準も「実行可能な」ものだけを対象にしています。決して実行されないコード（到達不能な枝）まで要求すると、100% がそもそも達成できないからです。MC/DC の独立対は、「ほかの条件を固定したまま、その条件だけを変えると判定の結果が変わる」ことを実際に見せるテストの組です。航空機搭載ソフトウェアの指針 DO-178 が、もっとも重要度の高いソフトウェアに要求している基準として知られています。 ### 3.2. 包含関係
経路網羅 MC/DC 分岐網羅 条件網羅 文網羅
1. 経路網羅は分岐網羅を包含し、分岐網羅は文網羅を包含する。 2. MC/DC は分岐網羅を包含する。また、各判定の各条件が独立対をもつ（ の $U_n(D)$ の中に独立対がある）プログラムについては、MC/DC を満たすテスト集合は条件網羅を満たす。 3. 逆向きの包含はどれも成り立たない。すなわち、文網羅は分岐網羅を、分岐網羅は経路網羅を、分岐網羅と条件網羅の両方を満たすことは MC/DC を、包含しない。 4. 条件網羅は分岐網羅を包含せず、分岐網羅は条件網羅を包含しない。経路網羅は条件網羅を包含しない。 (1) $T$ が経路網羅を満たすとし、$e$ を実行可能な辺とします。$e$ はある $x \in D$ の実行経路 $\pi_p(x)$ に現れます。$\pi_p(x)$ は実行可能な歩道なので、経路網羅により $\pi_p(x) = \pi_p(x')$ となる $x' \in T$ があり、$e$ は $\pi_p(x')$ に現れます。よって分岐網羅を満たします。 $T$ が分岐網羅を満たすとし、$n$ を実行可能な頂点とします。$n = s$ なら、$T$ は空でないので、どの $x \in T$ の実行経路も $s$ から始まり、$n$ を含みます。$n \ne s$ なら、$n$ を含む実行経路 $\pi_p(x)$（$x \in D$）の中で $n$ の直前の頂点から $n$ への辺 $e$ は実行可能で、分岐網羅により $e$ はある $x' \in T$ の実行経路に現れます。その経路は $e$ の終点 $n$ を含みます。よって文網羅を満たします。 (2) 前半は MC/DC の定義に分岐網羅が含まれていることによります。後半。判定 $n$ の条件 $c_{n,i}$ をとります。仮定から $U_n(D)$ の中に独立対があるので、MC/DC により $U_n(T)$ の中にも独立対 $(u, u')$ があります。$u$ と $u'$ は第 $i$ 成分で異なるので、一方の第 $i$ 成分は $0$、他方は $1$ です。よって $c_{n,i}$ は $T$ の実行で $0$ と $1$ の両方の値をとり、条件網羅の要求が満たされます。 (3)(4) それぞれ、小さな反例を挙げます。入力はブール値の組とし、すべての組が $D$ に属するとします。 **文網羅だが分岐網羅でない。** `if a: x = 1` のあとに `return` が続くプログラム（else の枝がない）。$T = \{a = 1\}$ は判定・代入・出口をすべて通りますが、判定から代入を飛ばして進む偽の辺を通りません。その辺は $a = 0$ で通るので実行可能です。 **分岐網羅だが経路網羅でない。** `if a: ... else: ...` のあとに `if b: ... else: ...` が続くプログラム。$T = \{(a, b) = (1, 1), (0, 0)\}$ は 4 本の枝をすべて通りますが、実行可能な経路は $(a, b)$ の 4 通りに対応して 4 本あり、そのうち 2 本しか通りません。 **条件網羅だが分岐網羅でない。** 判定が `a and b` 1 つのプログラム。$T = \{(1, 0), (0, 1)\}$ では $a$ も $b$ も両方の値をとりますが、判定は 2 回とも偽で、真の辺を通りません。 **分岐網羅だが条件網羅でない。** 判定が `a or b` 1 つのプログラム。$T = \{(1, 0), (0, 0)\}$ では判定は真と偽の両方になりますが、$b$ は $0$ しかとりません。 **分岐網羅かつ条件網羅だが MC/DC でない。** 判定が `a and b` 1 つのプログラム。$T = \{(1, 1), (0, 0)\}$ は判定の両方の結果と、各条件の両方の値を与えます。しかし $U(T) = \{(1, 1), (0, 0)\}$ の 2 元は 2 つの成分で異なるので、独立対になりません。$a$ の独立対 $((1, 1), (0, 1))$ は $U(D)$ にあるので、MC/DC は満たされません。 **経路網羅だが条件網羅でない。** 同じく判定が `a and b` 1 つのプログラム。実行可能な経路は真の側と偽の側の 2 本で、$T = \{(1, 1), (1, 0)\}$ は両方を通りますが、$a$ は $1$ しかとりません。 (2) の条件網羅についての仮定は、条件どうしに依存があって独立対が存在しない場合（たとえば `x > 0 and x > 5` の 1 つ目の条件は、2 つ目が真なら必ず真です）を除くためのものです。 包含関係は「強い基準を満たせば弱い基準も満たす」と言っているだけです。「強い基準を満たすテスト集合のほうが多くの誤りを見つける」とは言っていません。次の命題がその違いです。 ### 3.3. 包含は検出力の大小ではない 1. 分岐網羅は文網羅を包含するが、あるプログラムについて、分岐網羅を満たすテスト集合 $T_{\mathsf{A}}$ が検出しない誤りを、文網羅を満たす（分岐網羅は満たさない）テスト集合 $T_{\mathsf{B}}$ が検出することがある。 2. 経路網羅を満たすテスト集合が、正確なオラクルのもとで検出しない誤りがある。 (1) 整数 $x$ を受け取り $2x$ を返す、という仕様に対する次のプログラムを考えます。 ```python def double(x): y = x * x # 誤り: 正しくは 2 * x big = False if x > 1: big = True # 大きい入力の印（戻り値には使わない） return y ``` 出力が誤るのは $x^2 \ne 2x$、すなわち $x \notin \{0, 2\}$ のときです。$T_{\mathsf{A}} = \{0, 2\}$ は、$x = 0$ で判定の偽の辺、$x = 2$ で真の辺を通るので、すべての辺を通り、分岐網羅を満たします。出力は $0$ と $4$ で、どちらも正しい値 $2x$ に等しく、正確なオラクルのもとで合格します。$T_{\mathsf{B}} = \{3\}$ は、すべての文と判定を通るので文網羅を満たし、判定の偽の辺を通らないので分岐網羅は満たしません。出力は $9$ で、正しい値 $6$ と異なり、誤りを検出します。 (2) 整数 $a, b$ を受け取り、$b \ne 0$ なら商 $a / b$ を、$b = 0$ なら $0$ を返す、という仕様に対して、プログラム `def ratio(a, b): return a / b` を考えます。$b = 0$ のときの分岐が欠けています。このプログラムの制御フローグラフには判定がなく、$s$ から $t$ への歩道は 1 本だけです。$T = \{(1, 2)\}$ はその経路を通るので経路網羅を満たし、出力 $1/2$ は正しいので合格します。しかし $(a, b) = (1, 0)$ では例外が発生して値を返さず、仕様を満たしません。 (1) は、網羅基準が「どこを通るか」だけを決めて「どの値で通るか」を決めないことから生じます。同じ基準を満たすテスト集合はたくさんあり、誤りを見つけるものと見つけないものが混ざっています。包含関係は基準どうしの関係で、個々のテスト集合どうしの関係ではありません。 (2) は、構造に基づく基準に共通の盲点です。**書かれていないコードは網羅できません。** 欠けている分岐、考慮されていない入力の種類は、プログラムの構造をいくら調べても現れません。これを見つけるには、プログラムではなく仕様の側から入力を選ぶ必要があり、それが第 4 節の同値分割です。 ### 3.4. MC/DC に要るテストの数 1 つの判定に条件が $n$ 個あるとき、条件の値の組合せは $2^n$ 通りです。全部を試す基準（複合条件網羅）は $n$ が大きいと現実的でありません。MC/DC が使われるのは、$n$ にほぼ比例する個数で済むからです。 $n \ge 1$ とし、$\varphi : \{0, 1\}^n \to \{0, 1\}$ をブール関数とする。$U \subseteq \{0, 1\}^n$ が、各 $i = 1, \ldots, n$ について第 $i$ 変数の独立対（第 $i$ 成分だけで異なり $\varphi$ の値が異なる 2 元）を含むとする。 1. $|U| \ge n + 1$ である。 2. $\varphi$ が、変数 $x_1, \ldots, x_n$ がそれぞれちょうど 1 回現れる、$\wedge$・$\vee$・$\lnot$ による式で表されるならば、各変数の独立対を含む $U$ で $|U| = n + 1$ のものが存在する。 証明の方針は次のとおりです。独立対を「2 つのテストを結ぶ線」とみなすと、条件が $n$ 個なら線が $n$ 本引かれます。この線が輪をつくらないことを示し、輪のない図では線の本数より点の数が必ず多いことを使うと、テストの数が $n + 1$ 以上になると分かります。 (1) 各 $i$ について、$U$ に含まれる第 $i$ 変数の独立対を 1 つ選び $\{u_i, u_i'\}$ とします。$U$ を頂点集合とし、この $n$ 個の対を辺とする無向グラフ $H$ を考えます。対 $\{u_i, u_i'\}$ は第 $i$ 成分だけで異なる 2 元なので、$i$ が違えば別の辺で、辺はちょうど $n$ 本です。 $H$ に閉路がないことを示します。閉路 $w_0, w_1, \ldots, w_L = w_0$（$L \ge 3$、辺はすべて異なる）があったとします。辺 $\{w_{j-1}, w_j\}$ が第 $i_j$ 変数の対だとすると、$w_j$ は $w_{j-1}$ の第 $i_j$ 成分を反転したものです。辺がすべて異なるので $i_1, \ldots, i_L$ は相異なり、$w_L$ は $w_0$ の第 $i_1, \ldots, i_L$ 成分をそれぞれ 1 回ずつ反転したものになります。よって $w_L \ne w_0$ で、矛盾です。 閉路のないグラフでは、辺の数は頂点の数より小さいことを示します。辺を 1 本も引かない状態では、連結成分は頂点の数 $|U|$ 個です。辺を 1 本ずつ加えていくと、加える辺の両端は別の連結成分に属します（同じ成分に属していれば、その成分の中の道と合わせて閉路ができます）。したがって辺を 1 本加えるごとに連結成分は 1 つ減り、$n$ 本加えたあとの連結成分の数は $|U| - n$ です。これは $1$ 以上なので $|U| \ge n + 1$ です。 (2) 式の構造についての帰納法で、次の主張を示します。 > 変数がそれぞれちょうど 1 回現れる式 $\psi$（変数の個数 $m \ge 1$）に対し、各変数の独立対を含む $m + 1$ 元の集合 $U_\psi \subseteq \{0, 1\}^m$ が存在する。 このような $U_\psi$ は、$m \ge 1$ なので独立対を少なくとも 1 つ含み、したがって $\psi$ の値が $1$ になる元と $0$ になる元の両方を含みます。 $\psi = x$（変数 1 つ）のとき、$U_\psi = \{(0), (1)\}$ が $x$ の独立対そのものです。 $\psi = \lnot \psi_1$ のとき、$\psi$ と $\psi_1$ は同じ変数をもち、$\psi(u) \ne \psi(u')$ は $\psi_1(u) \ne \psi_1(u')$ と同値なので、$U_\psi = U_{\psi_1}$ でよい。 $\psi = \psi_1 \wedge \psi_2$ のとき、変数は 1 回ずつしか現れないので、$\psi_1$ の変数（$m_1$ 個）と $\psi_2$ の変数（$m_2$ 個）は重ならず、$m = m_1 + m_2$ です。$\{0, 1\}^m$ の元を、$\psi_1$ の変数への割り当て $u$ と $\psi_2$ の変数への割り当て $w$ の組 $(u, w)$ と書きます。帰納法の仮定の $U_{\psi_1}$、$U_{\psi_2}$ から、$\psi_1(t_1) = 1$ となる $t_1 \in U_{\psi_1}$ と、$\psi_2(t_2) = 1$ となる $t_2 \in U_{\psi_2}$ を選び、 $$ U_\psi = \{(u, t_2) \mid u \in U_{\psi_1}\} \cup \{(t_1, w) \mid w \in U_{\psi_2}\} $$ とおきます。2 つの集合の共通部分は $(t_1, t_2)$ の 1 元なので、$|U_\psi| = (m_1 + 1) + (m_2 + 1) - 1 = m + 1$ です。$\psi_1$ の変数 $x_i$ について、$U_{\psi_1}$ の中の独立対を $(u, u')$ とすると、$(u, t_2)$ と $(u', t_2)$ は $x_i$ の成分だけで異なり、$\psi(u, t_2) = \psi_1(u) \wedge 1 = \psi_1(u)$、$\psi(u', t_2) = \psi_1(u')$ で値が異なります。よって $\psi$ についての独立対です。$\psi_2$ の変数についても、$(t_1, w)$ と $(t_1, w')$ が同じ理由で独立対になります。 $\psi = \psi_1 \vee \psi_2$ のときは、$\psi_1(f_1) = 0$、$\psi_2(f_2) = 0$ となる $f_1 \in U_{\psi_1}$、$f_2 \in U_{\psi_2}$ を選び、$U_\psi = \{(u, f_2)\} \cup \{(f_1, w)\}$ とします。$\psi(u, f_2) = \psi_1(u) \vee 0 = \psi_1(u)$ なので、同じ議論が通ります。 (1) の証明は、独立対を辺とみると**木（森）**になる、という観察です。(2) の構成は、部分式ごとの木を 1 点で貼り合わせて、全体を 1 本の木にしています。$n + 1$ 個と $2^n$ 個の差は、$n = 10$ で $11$ 個と $1024$ 個、$n = 20$ で $21$ 個と約 $10^6$ 個です。 (2) は、同じ条件が式の中に 2 回以上現れる場合や、条件どうしに依存がある場合を扱っていません。一般の $\varphi$ について言えるのは、独立対を 1 組ずつ素朴に集めれば $2n$ 個で足りる、という上界です。著者が総当たりで調べた範囲（すべての変数に依存する 3 変数の関数 218 個と、すべての変数に依存する 4 変数の単調な関数 114 個）では、どの関数も $n + 1$ 個で足りましたが、これは小さい場合の観察であって、一般の主張ではありません。 グレゴリオ暦のうるう年の判定は `(y % 4 == 0 and y % 100 != 0) or y % 400 == 0` です。条件を $A$: `y % 4 == 0`、$B$: `y % 100 != 0`、$C$: `y % 400 == 0` とすると、$\varphi(A, B, C) = (A \wedge B) \vee C$ で、各変数が 1 回ずつ現れます。 により、MC/DC には少なくとも $4$ 個のテストが要ります。 ただし 3 つの条件は独立ではありません。$400$ の倍数は $4$ の倍数かつ $100$ の倍数なので、$C = 1$ なら $A = 1$、$B = 0$ です。$4$ の倍数でなければ $100$ の倍数でも $400$ の倍数でもないので、$A = 0$ なら $B = 1$、$C = 0$ です。実際に現れる $(A, B, C)$ は次の 4 通りだけです。 | 年 | $A$ | $B$ | $C$ | 判定 | |---|---|---|---|---| | 2023 | 0 | 1 | 0 | 偽 | | 2024 | 1 | 1 | 0 | 真 | | 1900 | 1 | 0 | 0 | 偽 | | 2000 | 1 | 0 | 1 | 真 | 2023 と 2024 は $A$ だけが異なり判定が変わるので $A$ の独立対、2024 と 1900 は $B$ の独立対、1900 と 2000 は $C$ の独立対です。4 つの年が、2023 — 2024 — 1900 — 2000 という 1 本の道（木）でつながっています。下界の $n + 1 = 4$ 個がちょうど達成され、しかも実際に現れる組合せはこの 4 通りで尽きているので、この判定については MC/DC が複合条件網羅と一致しています。「うるう年のテストは 4 つの年で行う」という経験則の根拠です。 ### 3.5. 経路の数 1. 条件分岐（判定 1 つと、真の側・偽の側それぞれ 1 つの文、合流点）を $n$ 個直列につないだ制御フローグラフには、入口から出口への歩道がちょうど $2^n$ 本ある。$i$ 番目の判定が入力の第 $i$ ビットを調べるなら、そのすべてが実行可能である。 2. ループを含むプログラムでは、実行可能な経路が無限にありうる。 3. $\mathcal{L}$ をチューリング完全なプログラミング言語とする。$\mathcal{L}$ のプログラムとその中の文が与えられたとき、その文が実行可能（ある入力で実行される）かどうかは決定可能でない。プログラムから実行可能な文の個数（文網羅の「100%」の分母）を計算するアルゴリズムも存在しない。 (1) $n$ についての帰納法（）で示します。$n = 1$ のとき、入口の判定から真の側の文を通って合流点（出口）に至る歩道と、偽の側を通る歩道の $2 = 2^1$ 本です。$n$ 個のときに $2^n$ 本とし、$n + 1$ 個つないだグラフを考えます。入口から出口への歩道は、最初の $n$ 個の部分を通り抜ける歩道（$n$ 番目の合流点まで。帰納法の仮定から $2^n$ 本）と、最後の条件分岐を通り抜ける歩道（$2$ 本）を、$n$ 番目の合流点でつないだものです。組合せは自由なので $2^n \times 2 = 2^{n+1}$ 本です。グラフに閉路はないので、歩道はこれで尽きます。 入力を $(x_1, \ldots, x_n) \in \{0, 1\}^n$ とし、$i$ 番目の判定が $x_i = 1$ を調べるなら、入力 $x$ の実行経路は各 $i$ で $x_i$ の側を通ります。$2^n$ 個の入力が相異なる $2^n$ 本の歩道を与えるので、すべてが実行可能です。 (2) 非負整数 $x$ を受け取り、`while x > 0: x = x - 1` を実行するプログラムを考えます。入力 $x = k$ の実行経路は、ループ本体の文をちょうど $k$ 回通ります。$k$ が違えば経路の長さが違うので、$k = 0, 1, 2, \ldots$ に対応する実行経路は相異なり、無限個あります。 (3) 停止問題の集合 $K$（）からの帰着です。番号 $e$ が与えられたとき、入力を無視して「機械 $M_e$ を入力 $e$ で模倣し、模倣が止まったら文 $\ell$ を実行して終わる」プログラム $q_e$ を機械的に作ります（$\mathcal{L}$ はチューリング完全なので模倣が書けます）。文 $\ell$ が実行されるのは模倣が止まるとき、すなわち $e \in K$ のときで、そのときに限ります。文の実行可能性を判定するアルゴリズムがあれば、$q_e$ と $\ell$ に使うことで $e \in K$ かどうかを判定できますが、$K$ は決定可能でないので（）、そのようなアルゴリズムは存在しません。 個数について。$q_e$ から文 $\ell$ を取り除いたプログラムを $q_e'$ とします。$\ell$ は模倣のあとにあるので、$\ell$ 以外の文が実行されるかどうかは $q_e$ と $q_e'$ で同じです。したがって、実行可能な文の個数は、$e \in K$ なら $q_e$ のほうが $q_e'$ より $1$ 多く、$e \notin K$ なら等しくなります。個数を計算するアルゴリズムがあれば、$q_e$ と $q_e'$ の個数を比べることで $e \in K$ かどうかを判定できてしまい、やはり矛盾です。 (3) は、網羅率の数字の読み方に関わります。実際の計測ツールは、実行可能かどうかを判定できないので、**すべての**文・分岐を分母にします。到達不能なコードがあれば 100% にはならず、「残りの数 % は到達不能だから問題ない」のか「テストが足りない」のかは、人が 1 つずつ判断するしかありません。 ## 4. 仕様から入力を選ぶ：同値分割と境界値 構造に基づく基準は、書かれたコードから出発するので、書かれていない場合分けを見つけられませんでした（ (2)）。仕様から出発する方法がこれを補います。 仕様 $(D, S)$ に対して、$D$ の分割 $D = D_1 \sqcup \cdots \sqcup D_r$（互いに交わらない空でない部分集合への分割）で、仕様が各 $D_j$ の入力を「同じ扱い」にしているものを**同値分割**といい、各 $D_j$ を**同値クラス**という。各同値クラスから少なくとも 1 つの入力を選んだテスト集合は、同値分割を**網羅する**という。 $D \subseteq \mathbb{Z}$ で、同値クラスが区間であるとき、あるクラスの最小の元を**境界**という。各境界 $b$ について $b$ と $b - 1$（境界の値と、その 1 つ手前）をテストに含める方法を**境界値分析**という。 「同じ扱い」は仕様の読み方に依存する言葉で、数学的な定義ではありません。同値分割は、「実装は、同じクラスの入力をすべて同じように（正しく、または誤って）処理する」という**一様性の仮定**のもとでだけ、各クラス 1 点で十分だと言えます。この仮定は定理ではなく、破れる例はすぐに作れます（クラスの中の 1 点だけを特別扱いする実装）。それでも同値分割が有用なのは、仕様を読んでクラスを列挙する作業が、実装に欠けている場合分けを見つけるからです。 一様性の仮定がもっとも破れやすいのがクラスの境目です。`<` と `<=` の書き間違い、$1$ ずれた定数。境界値分析はここを狙います。次の定理は、境界値分析が**どんな誤りを確実に検出するか**を述べます。 $m \ge 1$ とし、整数 $b_1 \lt b_2 \lt \cdots \lt b_m$ と、出力 $y_0, y_1, \ldots, y_m \in Y$ で $y_{j-1} \ne y_j$（$j = 1, \ldots, m$）を満たすものをとる。$b_0 = -\infty$、$b_{m+1} = +\infty$ として、仕様の関数 $g : \mathbb{Z} \to Y$ を $$ g(x) = y_j \qquad (b_j \le x \lt b_{j+1}) $$ で定める。関数 $p : \mathbb{Z} \to Y$ について、$p(x - 1) \ne p(x)$ となる整数 $x$ を $p$ の**切り替わり点**という。テスト集合を $T = \{b_j - 1,\ b_j \mid j = 1, \ldots, m\}$ とする。 1. $p : \mathbb{Z} \to Y$ の切り替わり点が $m$ 個以下で、すべての $x \in T$ について $p(x) = g(x)$ ならば、$p = g$ である。 2. 整数 $c_1, \ldots, c_m$ と出力 $z_0, \ldots, z_m$ による「$x \lt c_1$ なら $z_0$、そうでなく $x \lt c_2$ なら $z_1$、……、どれでもなければ $z_m$」という形の実装は、$c_j$ と $z_j$ が何であっても切り替わり点が $m$ 個以下である。したがって、境界の値のずれ（$c_j \ne b_j$）、不等号の等号の有無の誤り（$x \lt b_j$ を $x \le b_j$ と書く。これは $c_j = b_j + 1$ にあたる）、出力の取り違え（$z_j \ne y_j$）は、いくつ重なっていても、$T$ によってすべて検出される。 3. 切り替わり点が $m + 1$ 個以上ある実装には、$T$ に合格して $g$ と異なるものがある。 (1) 各 $j = 1, \ldots, m$ について、$b_{j-1} \lt b_j$ で整数なので $b_{j-1} \le b_j - 1 \lt b_j$ であり（$j = 1$ のときは $b_0 = -\infty$）、$g(b_j - 1) = y_{j-1}$、$g(b_j) = y_j$ です。$b_j - 1, b_j \in T$ なので、仮定から $p(b_j - 1) = y_{j-1} \ne y_j = p(b_j)$ で、$b_j$ は $p$ の切り替わり点です。$b_1, \ldots, b_m$ は相異なる $m$ 個の切り替わり点で、$p$ の切り替わり点は $m$ 個以下なので、$p$ の切り替わり点は $b_1, \ldots, b_m$ で尽きます。 $b_j \le x \lt b_{j+1}$（$1 \le j \le m$）とします。$b_j \lt x' \le x$ となる整数 $x'$ は切り替わり点でないので $p(x' - 1) = p(x')$ で、これを $x' = b_j + 1, \ldots, x$ に順に使うと $p(x) = p(b_j) = y_j = g(x)$ です。$x \lt b_1$ のときは、$x \lt x' \le b_1 - 1$ となる $x'$ が切り替わり点でないので、$p(x) = p(b_1 - 1) = y_0 = g(x)$ です。よって $p = g$ です。 (2) この実装を $p$ とし、$J(x)$ を「$x \lt c_j$ となる最小の $j$ から $1$ を引いた数（そのような $j$ がなければ $m$）」とすると、$p(x) = z_{J(x)}$ です。$x \le x'$ ならば、$x' \lt c_j$ となる $j$ は $x \lt c_j$ も満たすので、$x'$ についての最小の $j$ は $x$ についての最小の $j$ 以上で、$J(x) \le J(x')$ です。$J$ は $\{0, 1, \ldots, m\}$ に値をとる広義単調増加な関数なので、$J(x - 1) \ne J(x)$ となる $x$ は $m$ 個以下です（そのたびに値が $1$ 以上増え、増える幅の合計は $m$ 以下）。$p$ の切り替わり点では $J$ の値が変わっているので、$p$ の切り替わり点も $m$ 個以下です。 挙げた 3 種類の誤りはどれもこの形の実装です。$x \le b_j$ は整数については $x \lt b_j + 1$ と同値なので $c_j = b_j + 1$ にあたります。誤った実装 $p$ は $g$ と異なるので、(1) の対偶により、$p(x) \ne g(x)$ となる $x \in T$ があります。 (3) $x^{\circ} \gt b_m$ を 1 つとり、$y' \ne y_m$ を 1 つとって（$y_{m-1} \ne y_m$ なので $Y$ は 2 元以上を含みます）、$p(x) = g(x)$（$x \lt x^{\circ}$）、$p(x) = y'$（$x \ge x^{\circ}$）と定めます。$T$ の元はすべて $b_m$ 以下なので $p$ は $T$ 上で $g$ と一致しますが、$p(x^{\circ}) = y' \ne y_m = g(x^{\circ})$ です。$p$ の切り替わり点は $b_1, \ldots, b_m, x^{\circ}$ の $m + 1$ 個です。 「境界を狙え」という経験則が、仮定つきの定理になりました。仮定は**切り替わり点の数**です。実装が仕様と同じ個数の場合分けでできているかぎり、境界の位置や不等号や出力値をどう間違えても、$2m$ 個のテストで必ず見つかります。逆に、実装が余分な場合分けをもつとき（特定の値の特別扱い、大きな値での桁あふれ）は保証の外です。(3) の例は「最後のクラスの奥のほうで壊れる」実装で、境界の近くだけを調べるテストには見えません。 テスト点の選び方も定理の一部です。「境界の値と、その 1 つ手前」の代わりに「境界の値と、その 1 つ先」（$b_j$ と $b_j + 1$）を選ぶと、$c_j = b_j - 1$ という誤りを見逃すことがあります。たとえば境界が 1 つ（$m = 1$）のとき、$p(b_1) = y_1 = g(b_1)$、$p(b_1 + 1) = y_1 = g(b_1 + 1)$ で、どちらも正しいからです（誤るのは、テストに入っていない $b_1 - 1$ だけです）。境界をまたぐ 2 点を選ぶことが効いています。
5 6 12 13 64 65 無料 子ども 大人 シニア
仕様: 入場料は、6 歳未満は無料、6 歳以上 13 歳未満は子ども料金、13 歳以上 65 歳未満は大人料金、65 歳以上はシニア料金。境界は $b_1 = 6$、$b_2 = 13$、$b_3 = 65$ で、$m = 3$ です。 のテスト集合は $T = \{5, 6, 12, 13, 64, 65\}$ の 6 点です。 - `age <= 6` と書いた実装（$c_1 = 7$）は、$\mathrm{age} = 6$ で無料と答え、検出されます。 - 子どもと大人の料金を取り違えた実装は、$\mathrm{age} = 6$（または $12$、$13$、$64$）で検出されます。 - 境界を $60$ と思い込んだ実装（$c_3 = 60$）は、$\mathrm{age} = 64$ でシニア料金と答え、検出されます。 - 「100 歳以上は無料」という仕様にない特別扱いを入れた実装は、切り替わり点が 4 個で、$T$ に合格します。 最後の誤りを見つけるのは、境界値分析ではなく、「仕様にない場合分けがコードにある」ことを見つける方法、つまり構造に基づく網羅（その分岐が一度も実行されないことが分岐網羅の計測で分かります）です。仕様からのテストとコードからのテストは、互いの盲点を補います。 G. Myers が『The Art of Software Testing』の冒頭に置いた問題です。3 つの整数 $a, b, c$ を受け取り、それを辺の長さとする三角形が「正三角形」「二等辺三角形」「不等辺三角形」のどれかを答える（三角形にならなければそう答える）。出力は 4 種類ですが、同値クラスは 4 つでは足りません。仕様を読むと少なくとも次のクラスが見つかります。 - 入力が不正: どれかが $0$ 以下。 - 三角形にならない: 最大の辺が残りの 2 辺の和以上（$a \ge b + c$、$b \ge a + c$、$c \ge a + b$ の 3 通り）。 - 正三角形: $a = b = c$。 - 二等辺三角形: 等しい 2 辺の選び方で 3 通り（$a = b \ne c$、$a = c \ne b$、$b = c \ne a$）。 - 不等辺三角形。 境界は「三角形になる・ならない」の境目 $a = b + c$ です。$(a, b, c) = (3, 1, 2)$ は $a = b + c$ でつぶれた三角形（面積 $0$）で、三角形ではありません。$(3, 2, 2)$ は $a = b + c - 1$ で二等辺三角形です。`a > b + c` と `a >= b + c` を取り違えた実装は、$(3, 1, 2)$ のように $a = b + c$ となる入力でだけ誤ります。境界値分析は、この 1 次元ではない境界にも「境界の上の点と、すぐ隣の点」という形で使えますが、 の保証は 1 変数の区間の場合のものです。多変数では、境界の上の点が無数にあり、どの点を選ぶかに追加の判断が要ります。 引数の並べ替えで 3 通りずつあるクラスを 1 通りしか試さないのは、よくある見落としです。`a == b` だけを調べて `b == c` を調べ忘れた実装は、$(2, 2, 3)$ では正しく、$(3, 2, 2)$ で誤ります。 ## 5. 組合せテスト 設定項目がたくさんあるシステムでは、入力は「各因子の値の組」です。因子が $k$ 個、各因子の値が $v$ 通りなら、全組合せは $v^k$ 通りです。$v = 3$、$k = 20$ で約 $3.5 \times 10^9$ 通りになります。経験的に、不具合の多くは 1 つか 2 つの因子の値の組合せで起きるとされます。そこで「どの 2 因子についても、値の組合せがすべて現れる」テスト集合を考えます。 $k \ge 2$、$v \ge 2$ とする。**因子**が $k$ 個あり、各因子が $v$ 個の値 $\{0, 1, \ldots, v - 1\}$ をとるとする。テストは $\{0, \ldots, v - 1\}^k$ の元である。テスト集合 $T$ が**ペアワイズ網羅**（2 因子間網羅）であるとは、すべての因子の組 $i \lt j$ とすべての値の組 $(a, b)$ について、$t_i = a$ かつ $t_j = b$ となる $t \in T$ が存在することをいう。このような $T$ の元を行として並べた配列を（強さ 2 の）**被覆配列**といい、最小の大きさを $N(k, v)$ と書く。 $k \ge 2$、$v \ge 2$ とする。 1. $N(k, v) \ge v^2$。 2. $N(k, v) \ge \log_v k$。 3. $N(k, v) \le \bigl\lceil v^2 \ln \tfrac{k(k-1)}{2} \bigr\rceil + v^2 \le \lceil 2 v^2 \ln k \rceil + v^2$。この大きさのテスト集合は、「未網羅の組をもっとも多く網羅するテストを 1 つずつ足す」貪欲法で得られる。 証明の方針は次のとおりです。下界は「数えるべき組の個数」と「列の相異なり方」から素朴に出ます。上界は、無作為に選んだテストが未網羅の組の $1/v^2$ を平均して網羅することを使い、未網羅の組が毎回この割合ずつ減っていくことから、$\ln k$ に比例する個数で尽きると示します。 網羅すべき対象は、四つ組 $(i, a, j, b)$（$i \lt j$、$a, b \in \{0, \ldots, v - 1\}$）です。これを単に**組**と呼び、テスト $t$ が $t_i = a$、$t_j = b$ を満たすとき $t$ は組 $(i, a, j, b)$ を網羅するといいます。組の総数は $M = \binom{k}{2} v^2$ です。 (1) 因子 $1$ と $2$ だけを見ます。値の組 $(a, b)$ は $v^2$ 通りあり、1 つのテストは $(t_1, t_2)$ の 1 通りしか与えません。$v^2$ 通りすべてを網羅するには $v^2$ 個以上のテストが要ります。 (2) $T$ をペアワイズ網羅なテスト集合、$N = |T|$ とし、$T$ の元を $t^{(1)}, \ldots, t^{(N)}$ と並べます。因子 $i$ の**列**を $\mathrm{col}_i = (t^{(1)}_i, \ldots, t^{(N)}_i) \in \{0, \ldots, v - 1\}^N$ とします。$i \ne j$ で $\mathrm{col}_i = \mathrm{col}_j$ とすると、どのテストでも因子 $i$ と $j$ の値が等しく、組 $(i, 0, j, 1)$ が網羅されません。よって $k$ 個の列は相異なり、列の候補は $v^N$ 通りなので $k \le v^N$、すなわち $N \ge \log_v k$ です。 (3) まず、次を示します。 > 組の集合 $R$ が空でなければ、$R$ の組を $|R| / v^2$ 個以上網羅するテストが存在する。 各テスト $t$ が網羅する $R$ の組の個数を $n(t)$ とし、全テストにわたる和 $\sum_t n(t)$ を 2 通りに数えます。組 $(i, a, j, b)$ を 1 つ固定すると、それを網羅するテストは、因子 $i$ と $j$ の値が決まり、残りの $k - 2$ 個の因子の値が自由なので、$v^{k-2}$ 個です。よって $\sum_t n(t) = |R| \, v^{k-2}$ です。テストは全部で $v^k$ 個なので、$n(t)$ の平均は $|R| v^{k-2} / v^k = |R| / v^2$ で、平均以上の値をとる $t$ が少なくとも 1 つあります。（これは、テストを一様に無作為に選んだときに網羅される組の個数の期待値が $|R| / v^2$ であることを、数え上げで言い直したものです。） 貪欲法を考えます。未網羅の組の集合を $R_0$（すべての組、$|R_0| = M$）から始め、各段で、$R_{s}$ の組をもっとも多く網羅するテストを 1 つ選んで加え、網羅された組を除いたものを $R_{s+1}$ とします。いま示したことから、$R_s$ が空でなければ、選ばれるテストは $|R_s| / v^2$ 個以上を網羅するので $$ |R_{s+1}| \le |R_s| \Bigl(1 - \frac{1}{v^2}\Bigr) $$ です。また、選ばれるテストが網羅する組の個数は、正の数 $|R_s| / v^2$ 以上の整数なので $1$ 以上です。$R_s$ が空でないかぎり、各段で少なくとも $1$ 個の組が網羅されます。 $s$ についての帰納法（）により $|R_s| \le M (1 - 1/v^2)^s$ です。$\theta = 1/v^2 \in [0, 1]$ について $(1 - \theta)^s \le e^{-\theta s}$ が成り立つので（ の 1）、$|R_s| \le M e^{-s / v^2}$ です。$s_1 = \lceil v^2 \ln (M / v^2) \rceil$ とおくと（$M / v^2 = k(k-1)/2 \ge 1$ なので $s_1 \ge 0$）、 $$ |R_{s_1}| \le M e^{-s_1 / v^2} \le M e^{-\ln (M / v^2)} = v^2 $$ です。残りは $v^2$ 個以下で、以後は各段で $1$ 個以上が網羅されるので、高々 $v^2$ 段で $R_s$ は空になります。得られたテスト集合はペアワイズ網羅で、大きさは $s_1 + v^2 = \lceil v^2 \ln \frac{k(k-1)}{2} \rceil + v^2$ 以下です。$\frac{k(k-1)}{2} \le k^2$ なので $\ln \frac{k(k-1)}{2} \le 2 \ln k$ で、2 つ目の不等式が従います。 全組合せ $v^k$ は $k$ について指数的に増えますが、ペアワイズ網羅は $\ln k$ に比例する個数で足ります。$v = 2$ のとき、(2) の下界 $\log_2 k$ と (3) の上界 $8 \ln k + 4$ は、どちらも $\log k$ の定数倍です。$v = 2$ のときの $N(k, 2)$ の正確な値は、G. Katona と、D. Kleitman・J. Spencer が 1973 年に独立に決定しています。(3) の証明の議論（平均以上のものが存在する、という数え上げ）は、D. Cohen らが 1997 年にテスト生成の道具 AETG の論文で使ったものです。 OS が 3 種類（O0, O1, O2）、ブラウザが 3 種類（B0, B1, B2）、表示言語が 3 種類（L0, L1, L2）の組合せは $27$ 通りです。OS の番号 $i$、ブラウザの番号 $j$ に対して言語を $(i + j) \bmod 3$ とした次の 9 個で、ペアワイズ網羅になります。 | テスト | OS | ブラウザ | 言語 | |---|---|---|---| | 1 | O0 | B0 | L0 | | 2 | O0 | B1 | L1 | | 3 | O0 | B2 | L2 | | 4 | O1 | B0 | L1 | | 5 | O1 | B1 | L2 | | 6 | O1 | B2 | L0 | | 7 | O2 | B0 | L2 | | 8 | O2 | B1 | L0 | | 9 | O2 | B2 | L1 | OS とブラウザの組は、$(i, j)$ の 9 通りがそのまま並んでいます。OS と言語については、$i$ を固定すると $j \mapsto (i + j) \bmod 3$ が $\{0, 1, 2\}$ の置換なので、各 $i$ について 3 つの言語がすべて現れます。ブラウザと言語も同じです。$9 = v^2$ は (1) の下界に一致するので、これ以上は減らせません。 この表が保証するのは、**2 つの因子の値の組合せで起きる不具合は必ずどれかのテストで起きる**ことです。3 つの因子がそろったときにだけ起きる不具合（O1 かつ B1 かつ L0）は、27 通りのうち 9 通りしか試していないので、見逃すことがあります。実際、この表に (O1, B1, L0) はありません。 (3) の貪欲法は、全 $v^k$ 個のテストから最良のものを選ぶので、$k$ が大きいとそのままでは実行できません。次のコードは、未網羅の組を 1 つ含む候補を無作為に 50 個作り、その中で最良のものを選ぶ簡略版です（定理の上界は保証されませんが、毎回少なくとも 1 つの組を網羅するので必ず止まります）。 ```python # Python 3.12.14（標準ライブラリのみ）。乱数種は 20261008 import math import random from itertools import combinations, product def pairs_of(test): """テスト（長さ k の組）が網羅する (因子 i, 値 a, 因子 j, 値 b) の集合""" return {(i, test[i], j, test[j]) for i, j in combinations(range(len(test)), 2)} def greedy_pairwise(k, v, candidates=50, seed=20261008): """候補を candidates 個ずつ無作為に作り、未網羅の組を最も多く網羅するものを足していく。""" rng = random.Random(seed) uncovered = {(i, a, j, b) for i, j in combinations(range(k), 2) for a, b in product(range(v), repeat=2)} tests = [] while uncovered: i, a, j, b = min(uncovered) # 未網羅の組を 1 つ必ず含める（毎回 1 つ以上減る） best, gain = None, -1 for _ in range(candidates): t = [rng.randrange(v) for _ in range(k)] t[i], t[j] = a, b g = len(pairs_of(t) & uncovered) if g > gain: best, gain = tuple(t), g tests.append(best) uncovered -= pairs_of(best) return tests v = 3 print(" k 貪欲法 下界 v^2 上界 ceil(2 v^2 ln k) + v^2 全組合せ v^k") for k in (5, 10, 20): tests = greedy_pairwise(k, v) covered = set().union(*(pairs_of(t) for t in tests)) assert len(covered) == math.comb(k, 2) * v * v # すべての組を網羅したことの検算 bound = math.ceil(2 * v * v * math.log(k)) + v * v print(f"{k:3d} {len(tests):8d} {v * v:10d} {bound:28d} {v ** k:14d}") ``` ```text k 貪欲法 下界 v^2 上界 ceil(2 v^2 ln k) + v^2 全組合せ v^k 5 15 9 38 243 10 18 9 51 59049 20 26 9 63 3486784401 ``` 因子が 5 個から 20 個に増えると、全組合せは $243$ から約 $3.5 \times 10^9$ に増えますが、ペアワイズ網羅のテストは $15$ 個から $26$ 個に増えるだけです。どの $k$ でも、得られた大きさは定理の下界 $9$ と上界のあいだにあります。上界はかなり余裕のある評価だと分かります。 ## 6. 突然変異テスト 網羅基準は「テストがコードのどこを通ったか」を測りました。突然変異テストは「コードを少し壊したら、テストは気づくか」を測ります。これはオラクルの強さも込みの指標です（ の弱いオラクルは、何を壊しても気づきません）。 プログラム $p$ に小さな構文上の変更（演算子の置き換え、定数の変更、文の削除など）を 1 か所加えたプログラム $p'$ を、$p$ の**突然変異体**という。変更を 2 か所以上加えたものを**高次の**突然変異体という。 $p$ が合格しているテスト集合 $T$ について、ある $x \in T$ で $p'$ が不合格になるとき、$T$ は $p'$ を**殺す**という。オラクルが出力を $p$ の出力と比べるものであれば、これは「ある $x \in T$ で $p'(x) \ne p(x)$」と同じである。 すべての $x \in D$ で $p'(x) = p(x)$（一方が定まらなければ他方も定まらない）である突然変異体を**等価**であるという。突然変異体の集合 $\mathcal{P}$ に対する $T$ の**突然変異スコア**を $$ \frac{T \text{ が殺す } \mathcal{P} \text{ の元の個数}}{\mathcal{P} \text{ の中の等価でない元の個数}} $$ と定める。 等価な突然変異体はどんなテストでも殺せないので、分母から除きます。ここに突然変異テストの実務上の困難があります。 1. $p$ を制御フローグラフによるプログラム、$n$ をその文とし、$n$ の効果 $a_n$ を恒等写像に置き換えた突然変異体を $p_{-n}$ とする。テスト集合 $T$ が（$p$ の出力と比べるオラクルのもとで）$p_{-n}$ を殺すならば、$n$ はある $x \in T$ の $p$ での実行経路に現れる。したがって、文の削除による突然変異体のうち等価でないものをすべて殺すテスト集合は、削除すると振る舞いが変わる文をすべて実行する。 2. $\mathcal{L}$ をチューリング完全なプログラミング言語とする。$\mathcal{L}$ のプログラムとその突然変異体が等価であるかどうかは決定可能でない。したがって、突然変異スコアの分母を計算するアルゴリズムは存在しない。 (1) $p$ と $p_{-n}$ は同じグラフをもち、頂点 $n$ の写像だけが異なります。$T$ が $p_{-n}$ を殺すので、$p_{-n}(x) \ne p(x)$ となる $x \in T$ があります。$n$ が $\pi_p(x)$ に現れないとすると、 の最後の主張（2 つのプログラムの役割を入れ替えて使います）により、$p$ と $p_{-n}$ の $x$ に対する実行は一致し、$p_{-n}(x) = p(x)$ となって矛盾します。よって $n$ は $\pi_p(x)$ に現れます。 後半。文 $n$ の削除で振る舞いが変わるとは、$p_{-n}$ が等価でないことです。$T$ が等価でない削除の突然変異体をすべて殺すなら、そのような各 $n$ について、いま示したとおり $n$ を実行する $x \in T$ があります。 (2) (3) と同じ帰着です。番号 $e$ に対して、入力を無視して「機械 $M_e$ を入力 $e$ で模倣し、止まったら $0$ を返す」プログラム $r_e$ と、その最後の定数を $1$ に変えた突然変異体 $r_e'$ を作ります。$e \in K$ なら $r_e$ は $0$ を、$r_e'$ は $1$ を返すので等価でなく、$e \notin K$ ならどちらもどの入力でも止まらないので等価です。等価性を判定するアルゴリズムがあれば $K$ の補集合が、したがって $K$ が決定可能になり、停止問題の決定不能性（）に反します。分母は等価でない突然変異体の個数で、$\mathcal{P} = \{r_e'\}$ の場合にこれを計算できれば等価性が判定できるので、計算するアルゴリズムはありません。 (1) は、突然変異テストが文網羅より強いことを示しています。文を実行するだけでなく、その文の効果が出力に現れる入力をテストがもっていて、かつオラクルがそれを見ている必要があるからです。(2) は、健全な静的検査が不完全になること（）と同じ根をもつ限界です。実務では、殺せなかった突然変異体を人が 1 つずつ見て、等価なのかテストが足りないのかを判断します。 2 月の日数を返す関数に、文網羅・分岐網羅・MC/DC を満たすテスト集合を 1 つずつ用意します。 ```python # feb.py def february_days(y): """西暦 y 年（グレゴリオ暦）の 2 月の日数を返す。""" days = 28 if (y % 4 == 0 and y % 100 != 0) or y % 400 == 0: days = 29 return days ``` ```python # test_feb.py — Python 3.12.14 / pytest 9.1.1 / coverage 7.16.2 import pytest from feb import february_days EXPECTED = {2024: 29, 2023: 28, 1900: 28, 2000: 29} T1 = [2024] # 文網羅 T2 = [2024, 2023] # 分岐網羅 T3 = [2023, 2024, 1900, 2000] # MC/DC @pytest.mark.parametrize("y", T1) def test_t1(y): assert february_days(y) == EXPECTED[y] @pytest.mark.parametrize("y", T2) def test_t2(y): assert february_days(y) == EXPECTED[y] @pytest.mark.parametrize("y", T3) def test_t3(y): assert february_days(y) == EXPECTED[y] ``` `coverage run --branch --include=feb.py -m pytest -q test_feb.py -k test_t1` のあと `coverage report -m` を実行し、`test_t2`、`test_t3` についても同じことをしました。3 回の出力から `feb.py` の行を抜き出して並べます（見出しは 1 回だけ示し、合計の行は省きました。表の体裁と分岐の書き方 `5->7` は coverage.py の版で変わることがあり、ここに示すのはコードの先頭に書いた版での出力です）。 ```text == test_t1 Name Stmts Miss Branch BrPart Cover Missing ---------------------------------------------------- feb.py 5 0 2 1 86% 5->7 == test_t2 feb.py 5 0 2 0 100% == test_t3 feb.py 5 0 2 0 100% ``` `T1` は文をすべて実行しますが（`Miss` が 0）、5 行目の判定から 7 行目へ飛ぶ偽の辺（`5->7`。行番号は先頭のコメント行 `# feb.py` を 1 行目として数えたもの）を通っていません。`T2` と `T3` は、coverage.py の測る文と分岐については同じ 100% です。coverage.py は MC/DC を測らないので、**網羅率の数字では `T2` と `T3` は区別できません**。 次に、手で作った 6 個の突然変異体を、それぞれのテスト集合が殺すかどうかを調べます。 ```python # Python 3.12.14（標準ライブラリのみ） import inspect import feb from test_feb import EXPECTED, T1, T2, T3 MUTANTS = [ # (名前, 置き換える文字列, 置き換えたあとの文字列) ("M1 初期値を 29 に", "days = 28", "days = 29"), ("M2 days = 29 を削除", " days = 29", " pass"), ("M3 and を or に", "and", "or"), ("M4 != を == に", "y % 100 != 0", "y % 100 == 0"), ("M5 400 の条件を削除", " or y % 400 == 0", ""), ("M6 == 0 を <= 0 に", "y % 4 == 0", "y % 4 <= 0"), ] source = inspect.getsource(feb.february_days) def build(old, new): assert source.count(old) == 1 env = {} exec(source.replace(old, new), env) return env["february_days"] def killed(f, tests): return any(f(y) != EXPECTED[y] for y in tests) print(f"{'突然変異体':<22}{'T1':>4}{'T2':>4}{'T3':>4} 1583〜2400 年で元と異なる年の数") totals = [0, 0, 0] for name, old, new in MUTANTS: f = build(old, new) row = [killed(f, T) for T in (T1, T2, T3)] totals = [t + r for t, r in zip(totals, row)] diff = sum(f(y) != feb.february_days(y) for y in range(1583, 2401)) print(f"{name:<22}" + "".join(f"{'殺す' if r else '-':>4}" for r in row) + f" {diff}") print(f"{'殺した数':<22}" + "".join(f"{t:>4}" for t in totals)) ``` ```text 突然変異体 T1 T2 T3 1583〜2400 年で元と異なる年の数 M1 初期値を 29 に - 殺す 殺す 619 M2 days = 29 を削除 殺す 殺す 殺す 199 M3 and を or に - 殺す 殺す 619 M4 != を == に 殺す 殺す 殺す 202 M5 400 の条件を削除 - - 殺す 3 M6 == 0 を <= 0 に - - - 0 殺した数 2 4 5 ``` 読み取れることを 4 つ挙げます。 1. 文網羅の `T1` は 6 個中 2 個しか殺しません。`M1`（いつも 29 を返す）は、うるう年だけのテストでは見えません。 2. `M2` は文の削除で、`T1` が殺しています。 (1) のとおり、`T1` は `days = 29` を実行しています。 3. `M5`（400 年の規則を忘れる）を殺すのは、MC/DC の `T3` だけです。`M5` が元と異なるのは 818 年のうち 3 年（1600、2000、2400 年）だけで、 の $C$ の独立対（1900 年と 2000 年）がちょうどこれを捉えます。網羅率が同じ 100% の `T2` は見逃します。 4. `M6` は等価な突然変異体です。Python の `y % 4` は $0$ 以上なので、`== 0` と `<= 0` は同じです。どのテストも殺せません。突然変異スコアは、等価なものを除いて、`T1` が $2/5$、`T2` が $4/5$、`T3` が $5/5$ です。`M6` が等価だと気づかずに分母に入れると `T3` は $5/6$ となり、存在しないテストを探し続けることになります。 突然変異テストは「単純な誤りを検出できるテストは、複雑な誤りも検出できるだろう」という見込みに支えられています。これは**結合効果仮説**と呼ばれ、R. DeMillo、R. Lipton、F. Sayward が 1978 年に述べました。A. Offutt の実験（1992 年）など、多くの場合に成り立つという実証的な報告がありますが、定理ではありません。 プログラム $p$、その突然変異体 $p_1$、$p_2$、両方の変更を加えた高次の突然変異体 $p_{12}$、テスト集合 $T$ であって、$T$ は $p_1$ と $p_2$ をどちらも殺すが、$p$ と等価でない $p_{12}$ を殺さないものが存在する。 ブール値 $a, b$ を受け取るプログラム $p(a, b) = a \wedge b$（`return a and b`）をとります。$p_1(a, b) = \lnot a \wedge b$（$a$ に否定を挿入）、$p_2(a, b) = a \wedge \lnot b$（$b$ に否定を挿入）、$p_{12}(a, b) = \lnot a \wedge \lnot b$ とし、$T = \{(0, 1), (1, 0)\}$ とします。値を表にします。 | $(a, b)$ | $p$ | $p_1$ | $p_2$ | $p_{12}$ | |---|---|---|---|---| | $(0, 1)$ | 0 | 1 | 0 | 0 | | $(1, 0)$ | 0 | 0 | 1 | 0 | | $(1, 1)$ | 1 | 0 | 0 | 0 | | $(0, 0)$ | 0 | 0 | 0 | 1 | $p_1$ は $(0, 1)$ で、$p_2$ は $(1, 0)$ で $p$ と異なるので、$T$ はどちらも殺します。$p_{12}$ は $T$ の 2 点でどちらも $p$ と同じ値 $0$ をとるので、殺されません。$p_{12}$ は $(1, 1)$ で $p$ と異なるので等価ではありません。 2 つの誤りが、テストに使った入力の上で互いを打ち消しています。$T$ に $(1, 1)$ を加えれば 3 つとも殺せます。$\{(0, 1), (1, 0), (1, 1)\}$ は、 の構成が $a \wedge b$ に与える MC/DC のテスト集合です。 ## 7. テストの単位とテストダブル ここまでは、テストの対象を 1 つの関数として扱いました。実際のプログラムは、ほかのモジュールを呼び出します。 1 つのモジュール（関数・クラス）を、それが依存するほかのモジュールから切り離して調べるテストを**単体テスト**、複数のモジュールを組み合わせて調べるテストを**結合テスト**という。単体テストで、依存先のモジュールの代わりに使う簡単な代用品を**テストダブル**という。決まった値を返すだけのものを**スタブ**、呼び出されたこと・引数を記録して検査できるものを**モック**、簡略化した本物の実装（メモリ上のデータベースなど）を**フェイク**という。 テストダブルを使う理由は、速さ・決定性・故障の局所化です。依存先がネットワークやデータベースなら、本物を使うテストは遅く、外部の状態に左右されます。一方で、ダブルを使ったテストが通ることが、本物と組み合わせたときにも正しいことを意味するかは、別の問題です。 前章の言葉で言えば、依存先の操作 $m$ の呼び出しは $\mathtt{call}\ m$ で、本物の実装とテストダブルは 2 つの解釈 $\mathcal{M}$、$\mathcal{M}'$ です。呼び出し側の正しさが契約表 $\mathcal{C}$ から導かれているなら、$\mathcal{C}$ を満たすどの解釈のもとでも呼び出し側は正しい（）。しかしテストは証明ではなく、$\mathcal{M}'$ のもとでの有限個の実行です。ダブルが、本物の返しうる結果の一部しか返さない（エラーを返さない、空の結果を返さない、順序が決まっている）なら、呼び出し側がそれらを正しく扱うかは調べられていません。**単体テストが通り、結合テストで落ちる**とき、原因はたいてい、ダブルが本物の契約と食い違っているか、契約の許す振る舞いの一部しか演じていないかのどちらかです。ダブルと本物の両方に同じテスト（契約のテスト）を走らせることが、この食い違いを減らします。 **網羅率と欠陥検出の関係。** 網羅率の高いテスト集合ほど多くの誤りを見つけるのか、という問いには実証研究が多数あります。L. Inozemtseva と R. Holmes（2014 年）は、テスト集合の大きさの影響を除くと網羅率と突然変異スコアの相関は弱い、と報告しました。 と は、相関が弱くなりうる理由を与えています。 **テストの優先順位づけ。** 全部のテストを毎回走らせられないとき、どの順に走らせるかという問題があります（G. Rothermel らの研究、2001 年）。継続的インテグレーションの章で、テストの選択として触れます。 **記号実行。** 入力を記号のまま実行し、経路ごとの条件を制約として集めて、その経路を通る入力を制約ソルバで求める方法です（J. King、1976 年）。実際の実行と組み合わせたコンコリックテスト（P. Godefroid らの DART、2005 年）は、 の経路の爆発と、制約が解けない場合の扱いが課題になります。 ## 8. 演習 判定 `a and (b or c)` について、 (2) の証明の構成にしたがって、MC/DC を満たす 4 個の条件の組 $(a, b, c)$ を作れ。各条件の独立対を示せ。 $\psi_2 = b \vee c$ から作ります。$U_b = \{(0), (1)\}$、$U_c = \{(0), (1)\}$ で、$\vee$ の構成では偽になる元 $f_1 = (b = 0)$、$f_2 = (c = 0)$ を選び、 $$ U_{\psi_2} = \{(b, 0) \mid b \in U_b\} \cup \{(0, c) \mid c \in U_c\} = \{(0, 0), (1, 0), (0, 1)\} $$ です。次に $\psi = a \wedge \psi_2$。$U_a = \{(0), (1)\}$ から真になる元 $t_1 = (a = 1)$、$U_{\psi_2}$ から真になる元 $t_2 = (1, 0)$ を選び、 $$ U_\psi = \{(a, 1, 0) \mid a \in \{0, 1\}\} \cup \{(1, b, c) \mid (b, c) \in U_{\psi_2}\} = \{(0, 1, 0),\ (1, 1, 0),\ (1, 0, 0),\ (1, 0, 1)\} $$ です。判定の値は順に $0, 1, 0, 1$ です。独立対は、$a$: $(0, 1, 0)$ と $(1, 1, 0)$（値 $0$ と $1$）、$b$: $(1, 1, 0)$ と $(1, 0, 0)$（値 $1$ と $0$）、$c$: $(1, 0, 0)$ と $(1, 0, 1)$（値 $0$ と $1$）。全組合せは $8$ 通りで、その半分で済んでいます。 整数 $x$ の符号を返す関数（$x \lt 0$ なら $-1$、$x = 0$ なら $0$、$x \gt 0$ なら $1$）について、次に答えよ。 1. の $m$、$b_j$、$y_j$ と、テスト集合 $T$ を求めよ。 2. 実装 `if x < 0: return -1` / `elif x <= 1: return 0` / `else: return 1` は $T$ で検出されるか。 3. $T$ に合格するが仕様を満たさない実装を 1 つ挙げ、定理のどの仮定が破れているかを述べよ。 1. 仕様は $x \lt 0$ で $-1$、$0 \le x \lt 1$ で $0$、$1 \le x$ で $1$ なので、$m = 2$、$b_1 = 0$、$b_2 = 1$、$(y_0, y_1, y_2) = (-1, 0, 1)$ です。$T = \{b_1 - 1, b_1, b_2 - 1, b_2\} = \{-1, 0, 0, 1\} = \{-1, 0, 1\}$ の 3 点です。 2. この実装は $c_1 = 0$、$c_2 = 2$（$x \le 1$ は $x \lt 2$）の形で、切り替わり点は $0$ と $2$ の 2 個です。$x = 1$ で $0$ を返し、正しい値 $1$ と異なるので、$T$ の点 $1$ で検出されます。定理 (2) のとおりです。 3. たとえば「$x = 100$ のときだけ $0$ を返し、ほかは正しい」実装。$T$ の 3 点では正しいので合格しますが、$x = 100$ で誤ります。切り替わり点は $0, 1, 100, 101$ の 4 個で、$m = 2$ 個以下という (1) の仮定が破れています。32 ビット整数で $-x$ を計算する実装が $x = -2^{31}$ でだけ誤る、というのも同じ種類の誤りです。 各因子が 2 値（$v = 2$）のとき、次を示せ。 1. $N(3, 2) = 4$。 2. $N(4, 2) = 5$。 **準備。** 4 個のテストからなるペアワイズ網羅なテスト集合を考えます。因子 $i \lt j$ について、4 通りの値の組 $(0, 0), (0, 1), (1, 0), (1, 1)$ がすべて現れる必要があり、テストは 4 個なので、各組が**ちょうど 1 回**ずつ現れます。とくに、各因子の列（長さ 4 のビット列）には $1$ がちょうど 2 個あります。また、ある因子の値 $0$ と $1$ の名前を入れ替えても、ペアワイズ網羅であることは変わりません。そこで、各因子について必要なら名前を入れ替え、1 番目のテストがすべて $0$ であるとしてよい。すると各因子の列は、2〜4 番目のテストのうちちょうど 2 つで $1$ になります。その 2 つの選び方は $\{2, 3\}$、$\{2, 4\}$、$\{3, 4\}$ の 3 通りです。2 つの因子の列が同じなら組 $(0, 1)$ が現れないので、列は相異なります。したがって因子は 3 個以下です。 (1) (1) より $N(3, 2) \ge 4$。上の 3 通りの列を因子 1, 2, 3 に割り当てたテスト集合 $$ (0, 0, 0),\ (1, 1, 0),\ (1, 0, 1),\ (0, 1, 1) $$ は、どの 2 因子についても、列が「ちょうど 1 つのテストで両方 $1$」「それぞれ片方だけ $1$ のテストが 1 つずつ」「1 番目のテストで両方 $0$」となるので、ペアワイズ網羅です。よって $N(3, 2) = 4$。 (2) 準備で示したとおり、4 個のテストでは因子は 3 個までなので、$N(4, 2) \ge 5$ です。5 個のテスト $$ (0, 0, 0, 0),\ (0, 1, 1, 1),\ (1, 0, 1, 1),\ (1, 1, 0, 1),\ (1, 1, 1, 0) $$ を考えます。2〜5 番目のテストは、それぞれ 1 つの因子だけが $0$ です。因子 $i \lt j$ について、$i$ だけが $0$ のテストが $(0, 1)$、$j$ だけが $0$ のテストが $(1, 0)$、残りの 2 つのテストが $(1, 1)$、1 番目のテストが $(0, 0)$ を与えます。よってペアワイズ網羅で、$N(4, 2) = 5$ です。全組合せは $16$ 通りです。 整数のリストを昇順に並べ替える関数 `sort` のテストで、オラクルを次の 3 通りにする。それぞれについて、テスト集合をどう選んでも検出できない誤った実装を 1 つずつ挙げよ（存在しない場合はそう答えよ）。 - (a) 例外を出さずにリストを返せば合格。 - (b) 返されたリストが昇順なら合格。 - (c) 返されたリストが昇順で、入力の並べ替え（同じ要素を同じ個数ずつ含む）なら合格。 (a) 入力をそのまま返す実装。例外は出ず、リストを返すので、 のとおり、どんなテスト集合にも合格します。 (b) つねに空のリストを返す実装。空のリストは昇順です。重複を取り除いてから並べる実装も、返すリストは昇順なので合格します。どちらも「昇順である」というオラクルが受け入れる出力しか返さないので、どの入力でも検出されません。 (c) 存在しません。昇順で入力の並べ替えであるリストは、入力から一意に決まります（同じ多重集合を昇順に並べる方法は 1 通り）。したがってこのオラクルは正確で、誤った実装には、不合格になる入力が必ずあります。ただし、その入力がテスト集合に入っているかは別の問題で、 により、有限のテスト集合ごとに、それに合格する誤った実装があります。(b) と (c) の違いは、次章で「性質の組が仕様を決めているか」という問題として扱います。 ## 参考文献 1. P. Ammann, J. Offutt, *Introduction to Software Testing*, 2nd ed., Cambridge University Press, 2016 — 到達・感染・伝播のモデル、網羅基準と包含関係、突然変異テスト。 2. G. J. Myers, C. Sandler, T. Badgett, *The Art of Software Testing*, 3rd ed., Wiley, 2011 — 三角形の問題、同値分割と境界値分析。 3. E. W. Dijkstra, "Notes on structured programming", in O.-J. Dahl, E. W. Dijkstra, C. A. R. Hoare, *Structured Programming*, Academic Press, 1972 — テストで示せることについての指摘。 4. K. J. Hayhurst, D. S. Veerhusen, J. J. Chilenski, L. K. Rierson, *A Practical Tutorial on Modified Condition/Decision Coverage*, NASA/TM-2001-210876, 2001 — MC/DC の定義と独立対の作り方。 5. D. M. Cohen, S. R. Dalal, M. L. Fredman, G. C. Patton, "The AETG system: An approach to testing based on combinatorial design", *IEEE Transactions on Software Engineering* 23 (1997), 437–444 — ペアワイズ網羅の貪欲法と対数の上界。 6. R. A. DeMillo, R. J. Lipton, F. G. Sayward, "Hints on test data selection: Help for the practicing programmer", *Computer* 11(4) (1978), 34–41 — 突然変異テストと結合効果仮説。 7. L. Inozemtseva, R. Holmes, "Coverage is not strongly correlated with test suite effectiveness", *Proceedings of the 36th International Conference on Software Engineering (ICSE)*, 2014 — 網羅率と検出力の実証研究。