テストアルゴリズムの改善: ソフトウェアテストにおける数学的アプローチ

新しいテスト設計方法論は、必ずしも同時に登場するとは限りません。現代のテスト実践の重要な部分は、数学的モデルを適応させる際の綿密な理論的および実験的作業を通じて進化してきました。優れたテスターになるために数学者である必要はありませんが、テスト方法の背後にある理論的基礎を理解することは有益です。

カバレッジの最大化とテストケースの数の最小化

数学的ロジックを適用して、システムのコード カバレッジを最適化できます。条件に 2 つの分岐と長い論理式を含む "if" ステートメントを使用した簡単な例を考えてみましょう。

 if ( (& a2) & (!(a2 || a4) ) || a3 ) { # action 1 } else { # action 2 }

両方の分岐をカバーするには、式の構造を理解する必要があります。何ができるだろうかと疑問に思う人もいるかもしれない。このコード部分 (論理式) は常に徹底的にテストでき、結果として 16 回のテストが行われます。ただし、これはかなりの量であるため、検査数を減らす努力が必要です。テストの数は、修正条件/判定カバレッジ (MC/DC) 法を使用して減らすことができます (11 ～ 12 個のテストが生成されます)。ブランチ カバレッジがリスクのテストに十分である場合、必要なテストは 2 つだけですが、どれがテストであるかは不明です。

この問題を解決するには、ブール代数を論理式に適用します。

 if( (& a2) & (! (a2 || a4) ) || a3 ) = = ( (& a2) & ( (!a2 || !a4) ) || a3 ) = = ( a1 & a2 & !a2 & !a4 || a3 ) = = 0 || a3 = a3

元の式を変形すると、実際に真理値に影響を与える変数a3は 1 つだけであることがわかります。その結果、テスト ケースの取得が簡単になります (1 つはa3 == falseです)。さらに、1 つの変数のみに依存する複雑な論理式があるのは奇妙であるため、コードが最適化されていないことが明らかになります。残念ながら、このような状況は現実には非常に一般的であり、ここで示した例は比較的簡単です。

結論は：

• 徹底的なテストを使用する場合は 2 つのテスト

• MC/DC法による2試験

• ブランチカバレッジが適用されるかどうかの 2 つのテスト

  
  

一般に、論理式は代数、数学的手法、アルゴリズムを使用して簡略化 (最小化) できます。同様の方法が少なくとも 3 つあります。上で説明したように、ブール代数を使用した直接変換は常に機能します。数学と論理だけでなく、ドメインの特性にも依存して、特定のドメインの特性を考慮した式最小化の方法を見つけて適用することができます。

ペアごとのテストの最適化

ペアワイズ テスト方法では、入力パラメータの考えられるすべての組み合わせを徹底的なテスト (時間とリソースを大量に消費する可能性がある) でテストするのではなく、各パラメータ値がすべての値と組み合わされるようにテスト セットを設計する方法でテスト セットを生成します。少なくとも 1 回はテストされた他のパラメータの値。これにより、テスト ケースの数が大幅に削減されます。

これは十分に確立されており、よく使用される方法です。ただし、残念ながら、システムが複雑になるにつれて、この方法が常に機能するとは限りません。疑問が生じます。多数の入力パラメータを持つ複雑なシステムを徹底的にテストするには、ペアワイズ テストで十分ですか?この疑問は、米国国立標準技術研究所 (NIST) を含む多くのテスト専門家や研究者の興味をそそりました。

• Pairwise finds 65-97% of errors
• 3-way finds 89-99% of errors
• 4-way finds 96-100% of errors
• 5-way finds 96-100% of errors
• 6-way finds 100% of errors

研究によると、ペアワイズテストでは 65 ～ 97% のケースでエラーが見つかります。パラメーターのペアではなく、3 つまたは 4 つを組み合わせる、つまり k ウェイ テストを使用し始めると、より多くのテストが得られますが、より多くのエラーも捕らえられます。

たとえば、システムにそれぞれ 3 つの値を持つ 2 つのパラメーターと、それぞれ 2 つの値を持つ 3 つのパラメーターがあるとします。

• Pairwise: 10 tests with 14% coverage
• 3-way: 18 tests with 25% coverage
• 4-way: 36 tests with 50% coverage
• 5-way: 72 tests with 100% coverage

満足のいくレベルのテスト カバレッジと許容可能なテスト ケースの数を選択できます。

ペアワイズの基礎は、値の n タプル (ペア、トリプル、クアドルプルなど) を同じ回数含む直交配列です。

ペアワイズおよび k-way テストの通常の基礎はOA(N, V^k, t)です。

• N は行数です

• k は列の数です

• V は列内の異なる値の数です

• t は強度です (ペアワイズの場合は t=2)

  
  

OA では、t 列の各セットには、すべての t タプルが同じ回数だけ含まれます。

直交行列の代わりに、カバー行列を使用することをお勧めします。これらの行列は、値の各セットが「同じ回数」ではなく少なくとも 1 回出現するという点で直交行列とは異なります。この場合、テストの数はわずかに少なくなります。行列をカバーすると不正確なテスト ケースが発生する可能性がありますが、全体としてテスト プロセスははるかに高速になります。したがって、テストプロセスが大幅に簡素化されます。

CA(N, V^k, t)、ここで:

• N は行数です
• k は列の数です
• V は列内の異なる値の数です
• t は強度です (ペアワイズの場合は t=2)

CA では、t 列の各セットにすべての t タプルが少なくとも 1 回含まれます。カバー行列を使用すると、テストの数を大幅に増やすことなく、ペアごとのテストから k-way テストに移行できます。

システム状態と変化するシステム状態のテスト

通常 (ほぼ常に)、システムには「動作中」と「動作していない」という 2 つ以上の状態があります。在庫注文がある州の一部を考えてみましょう。株の売買注文は、取引が完了するまでに一連の状態を経る必要があります。まず注文が作成され、次に取引所によって確認され、その後多数の少額の購入取引が行われ、最後に必要な量の株式が売買されます。株式注文のすべての状態は取引システムに反映され、当然のことながら、すべての遷移と状態をテストする必要があります。

ほとんどの場合、すべての状態またはすべての遷移がテストされますが、多くの場合、両方が検証されます。完全にカバーすることは可能ですが、時間と費用がかかり、リソースが大量に消費されます。

グラフと有限オートマトン

巡回セールスマン (commi voyager) 問題と de Bruijn アルゴリズムを考えてみましょう。このアルゴリズムにより、グラフ内を横断してグラフを完全にカバーできる最適な、または十分に最適な短いパスのセットを取得できることを理解するだけで十分です (厳密に言えば、同様のことを達成する他のアルゴリズムを使用することも、別のアルゴリズムを発明することもできます)カスタムアルゴリズム)。

• まず、システムの初期状態を取得し、頂点が元のグラフの遷移に対応する新しいグラフを構築します。
• 次に、新しいグラフの頂点、つまり古いグラフの遷移をカバーします。
• 一部のパスは明らかですが、非常に短いことがわかります (これはシステムの状態と遷移をテストするのに非常に便利です)。
• 他のパスの構築を続けます。その結果、長すぎる可能性があります (これは良くありません)。

状況を分析するために次の例を考えてみましょう。

テスターは3人います。最初のテストは最初のテストを実行し、2 番目のテストは 2 番目のテストを実行し、3 番目のテストは 3 番目のテストを実行します。最初の 2 つのテストは、パスが短いため (最初の 2 つのパスが非常に短いため、3 番目のテストと比較して) 非常に早く完了しますが、最後のテストは非常に長い時間がかかります (3 番目のパスは非常に短いため)。長さ）。

de Bruijn アルゴリズムを適用すると、3 番目のシーケンスをいくつかの短いシーケンスに「カット」でき、すべてのテストの実行を効率的に並列化できます。

最終的にはより多くのテストが必要になる可能性がありますが、並列実行の場合はテストが短いため、テストははるかに速く終了します。

さらに、テストの数が増えると、より柔軟にテストを実行できます。すべてのテストを同時に実行することも、興味のない、重要性の低いテストを削除することもできます。システムの最も重要な状態を通過するテストには、より高い優先順位を割り当てることができます。アルゴリズムの結果を活用する方法はたくさんあります。

さらに、アルゴリズムはドメイン固有のものを使用しません。システムの完全に抽象的な状態と遷移を処理します。

この手法では、アルゴリズムの使用方法に大きく依存します。最も極端なケースでは、テスターは状態間の遷移の背後にあるロジックについて何も知らない可能性があります。このような状況では、状態遷移の長いチェーンはアルゴリズムによっていくつかの短いチェーンに「切断」されます。これらの連鎖の中には、無意味なものになる場合もあります。したがって、取得されたチェーンは合理的であるか、テストにとって重要で意味のあるものであるかを評価する必要があります。無意味で重要ではありませんが、システムの状態を変更する可能性のあるパスにより、システムのどの部分を変更する必要があるかを理解することができ、正確にどの部分が明らかになるかがわかります。

主要な結論は次のように考えられます。

• 論理式を最小限に抑えるアルゴリズムにより、最小限の労力で最大限のテスト カバレッジが得られます。最小化アルゴリズムを使用することは必ずしも必要というわけではありません。時間の無駄になる場合もあります。普遍的なアプローチが存在します。
• 完全なテスト カバレッジは、並列化、自動化、柔軟性、独立性が容易な短いテスト ケースの小さなセットで達成できます。
• 実際の状況でのアプリケーションの使用状況に関する統計を分析することで、既存のテスト設計手法を最適化および適応させ、必要なテスト カバレッジを達成して、アプリケーションの品質を保証することができます。
• ペアワイズ テストを変更すると、標準アルゴリズムよりもテスト範囲が広がり、ほぼ同じリソースを使用して、より詳細なテストが可能になります。
• 一部のアルゴリズムは、標準のテスト設計手法の効率が低い場合に効果的である可能性があります。
• 組み合わせテスト設計手法の失敗にはいくつかの課題があります。
• 得られたアルゴリズムはさまざまなシステムに簡単に適応でき、その分野に関する特別な知識は必要ありません。

小さな欠点としては、次の点に注目する価値があります。

• 一部のアルゴリズムは効果的ですが、すべてのケースに関連するわけではありません。多くの状況では、標準的なテスト設計手法が同等、または場合によってはそれ以上に効果的です。
• アルゴリズムを適用するには、ある程度の数学的知識が必要であり、場合によっては適用にさらに時間がかかるため、多くの状況で重要な要素になる可能性もあります。