Metamorphic Testing を試す

Metamorphic Testing は、Chen らによって提案されたソフトウェアテスト手法です*1。以下に示す第二著者のウェブページからテクニカルレポートをダウンロードできます*2。今回は、テクニカルレポートで用いられている例を実装しながら Metamorphic Testing について簡単に説明し、また、Metamorphic Testing によるバグ検出を実際に試してみます。
https://www.cse.ust.hk/~scc/publ/publ.html

プログラムの準備と単体テストの作成

Metamorphic Testing を試す例題として、ダイクストラ法で無向グラフの最短経路を求めるプログラムを実装します。これは、テクニカルレポートの 3.3 節で挙げられている例です*3。shortestDist 関数は、無向グラフ $graph の頂点 $x から頂点 $y に至る最短経路を出力します。$graph は二次元配列として、$graph[$i][$j] が頂点 $i と頂点 $j の距離を表すこととします*4。

<?php
namespace MetamorphicTesting;

class ShortestPath
{
    public function shortestDist($x, $y, $graph)
    {
        $n = count($graph);

        $visited = [$x];
        $prevs = array_fill(0, $n, $x);
        $distances = $graph[$x];

        $k = $x;
        while ($k != $y) {
            $minDistance = PHP_INT_MAX;
            for ($i = 0; $i < $n; $i++) {
                if (in_array($i, $visited)) continue;
                if ($distances[$i] < $minDistance) {
                    $minDistance = $distances[$i];
                    $k = $i;
                }
            }
            $visited[] = $k;
            for ($i = 0; $i < $n; $i++) {
                if (in_array($i, $visited)) continue;
                if (($newDistance = $distances[$k] + $graph[$k][$i]) < $distances[$i]) {
                    $distances[$i] = $newDistance;
                    $prevs[$i] = $k;
                }
            }
        }

        $shortestPath = [];
        for ($i = $y; $i != $x; $i = $prevs[$i]) {
            $shortestPath[] = $i;
        }
        $shortestPath[] = $x;
        $shortestPath = array_reverse($shortestPath);

        return [$distances[$y], $shortestPath];
    }
}

まず、以下に示す小さなグラフでプログラムの動作を確認します。このグラフで頂点 2 から頂点 4 への最短経路は 2, 3, 1, 4 と辿った場合で、このときの経路長は 6 になります。
f:id:y_uti:20181124190105p:plain

このことをテストケースとして実装してみます。$graph が頂点間の距離を表します。ただし、辺のない頂点間は距離を 100 として表現しました。PHPUnit で実行すると、このテストは正しくパスします。

<?php
namespace MetamorphicTesting;

use MetamorphicTesting\ShortestPath;

class ShortestPathTest extends \PHPUnit\Framework\TestCase
{
    public function testShortestDist()
    {
        $graph = [  /* 0    1    2    3    4 */
            /* 0 */ [  0,   2,   5,   5, 100],
            /* 1 */ [  2,   0, 100,   3,   2],
            /* 2 */ [  5, 100,   0,   1, 100],
            /* 3 */ [  5,   3,   1,   0,   8],
            /* 4 */ [100,   2, 100,   8,   0],
        ];

        [$distance, $path] = (new ShortestPath())->shortestDist(2, 4, $graph);

        $this->assertEquals(6, $distance);
        $this->assertEquals([2, 3, 1, 4], $path);
    }
}

Metamorphic Testing によるテストケースの作成

さて、このテストケースに対してはプログラムは正しく最短経路を計算できましたが、これだけでは確信を持てないので、ほかにも大小さまざまなグラフで動作を確認したいところです。ところが、大きなグラフに対しては、プログラムが計算した結果が正しいかどうかを判断できないという問題が生じます。たとえば次のような単体テストを考えます。

<?php
    ...
    public function testShortestDistUsingLargeGraph()
    {
        // ランダムに頂点数 100 のグラフを作成して、起点と終点を適当に選ぶ
        $graph = $this->buildRandomGraph(100, 12345);
        $x = rand(0, 99);
        $y = rand(0, 99);

        [$distance, $path] = (new ShortestPath())->shortestDist($x, $y, $graph);

        // $this->assertEquals(???, $distance);
        // $this->assertEquals(???, $path);

        echo $distance;
        echo json_encode($path);
    }

    private function buildRandomGraph($n, $seed)
    {
        mt_srand($seed);

        // 頂点数 $n のグラフを作る。頂点間の距離は 1000 で初期化する
        $graph = array_fill(0, $n, array_fill(0, $n, 1000));
        for ($i = 0; $i < $n; $i++) {
            $graph[$i][$i] = 0;
        }

        // 20% の確率で頂点間の距離を rand(1, 100) に設定する
        for ($i = 0; $i < $n; $i++) {
            for ($j = $i + 1; $j < $n; $j++) {
                if (rand(0, 4) == 1) {
                    $graph[$i][$j] = $graph[$j][$i] = rand(1, 100);
                }
            }
        }

        return $graph;
    }

このテストケースを実行したところ、echo ステートメントの出力として、経路長 22, 最短経路 13, 38, 99, 22, 35, 59 という結果が得られました。ところが、この結果が正しいのかどうかがわかりません。つまり、100 頂点という大きなグラフでは、最初の 5 頂点のグラフのように正しい結果を人手で設定するのは困難で、単体テストで結果を検証できません。

Metamorphic Testing は、このような問題へのアプローチとして、テストの入力を変更したときに出力が満たすべき性質を考え、プログラムがその性質を確かに満たしていることをテストします。このような性質を Metamorphic Relation と名付けています。以下では、具体的な例を用いて説明します。

たとえば先ほどの実行では、経路長 22, 最短経路 13, 38, 99, 22, 35, 59 という結果が得られました。ということは、同じグラフで起点と終点を入れ替えれば、経路長は変わらず 22, 最短経路は反転されて 59, 35, 22, 99, 38, 13 という結果が得られるはずです。これはテストケースとして次のように実装できます。

<?php
    ...
    public function testShortestDistMR1()
    {
        $object = new ShortestPath();

        $graph = $this->buildRandomGraph(100, 12345);
        $x = rand(0, 99);
        $y = rand(0, 99);

        [$distance0, $path0] = $object->shortestDist($x, $y, $graph);

        [$distance1, $path1] = $object->shortestDist($y, $x, $graph);

        $this->assertEquals($distance0, $distance1);
        $this->assertEquals(array_reverse($path0), $path1);
    }

テクニカルレポートでは、最短経路を求める例について以下の 5 種類の Metamorphic Relation を挙げています*5。

起点と終点を反転しても同じ経路長を返す
最短経路の途中に含まれる任意の頂点を $z とすると、「$x から $z の経路長 + $z から $y の経路長」が元の経路長と一致する
これを反転した「$y から $z の経路長 + $z から $x の経路長」も元の経路長と一致する
最短経路で $x の次の頂点を $u, $y の手前の頂点を $v とすると、「$x と $u の距離 + $u から $v の経路長 + $v と $y の距離」が元の経路長と一致する
上記で $u と $v の起点と終点を反転した「$x と $u の距離 + $v から $u の経路長 + $v と $y の距離」も元の経路長と一致する

このうち一番目は既に実装しました。残りの 4 種類も次のように簡単に実装できます*6。なお、テストケースでは最短経路の内容も確認するように実装を追加しています。

<?php
    ...
    public function testShortestDistMR2()
    {
        $object = new ShortestPath();

        $graph = $this->buildRandomGraph(100, 12345);
        $x = rand(0, 99);
        $y = rand(0, 99);

        [$distance0, $path0] = $object->shortestDist($x, $y, $graph);

        $z = $path0[rand(1, count($path0) - 2)];
        [$distance1, $path1] = $object->shortestDist($x, $z, $graph);
        [$distance2, $path2] = $object->shortestDist($z, $y, $graph);

        $this->assertEquals($distance0, $distance1 + $distance2);
        $this->assertEquals($path0, array_merge($path1, array_slice($path2, 1)));
    }

    public function testShortestDistMR3()
    {
        $object = new ShortestPath();

        $graph = $this->buildRandomGraph(100, 12345);
        $x = rand(0, 99);
        $y = rand(0, 99);

        [$distance0, $path0] = $object->shortestDist($x, $y, $graph);

        $z = $path0[rand(1, count($path0) - 2)];
        [$distance1, $path1] = $object->shortestDist($y, $z, $graph);
        [$distance2, $path2] = $object->shortestDist($z, $x, $graph);

        $this->assertEquals($distance0, $distance1 + $distance2);
        $this->assertEquals(array_reverse($path0), array_merge($path1, array_slice($path2, 1)));
    }

    public function testShortestDistMR4()
    {
        $object = new ShortestPath();

        $graph = $this->buildRandomGraph(100, 12345);
        $x = rand(0, 99);
        $y = rand(0, 99);

        [$distance0, $path0] = $object->shortestDist($x, $y, $graph);

        $u = $path0[1];
        $v = $path0[count($path0) - 2];
        [$distance1, $path1] = $object->shortestDist($u, $v, $graph);

        $this->assertEquals($distance0, $graph[$x][$u] + $distance1 + $graph[$v][$y]);
        $this->assertEquals($path0, array_merge([$x], $path1, [$y]));
    }

    public function testShortestDistMR5()
    {
        $object = new ShortestPath();

        $graph = $this->buildRandomGraph(100, 12345);
        $x = rand(0, 99);
        $y = rand(0, 99);

        [$distance0, $path0] = $object->shortestDist($x, $y, $graph);

        $u = $path0[1];
        $v = $path0[count($path0) - 2];
        [$distance1, $path1] = $object->shortestDist($v, $u, $graph);

        $this->assertEquals($distance0, $graph[$x][$u] + $distance1 + $graph[$v][$y]);
        $this->assertEquals(array_reverse($path0), array_merge([$y], $path1, [$x]));
    }

Mutation Testing によるバグの検出力の確認

最後に、これらのテストケースがバグを検出できるかどうかを mutation testing で確認してみます*7。Infection を用いた mutation testing の実行結果は以下のとおりでした。

25 mutations were generated:
      16 mutants were killed
       0 mutants were not covered by tests
       5 covered mutants were not detected
       0 errors were encountered
       4 time outs were encountered

Metrics:
         Mutation Score Indicator (MSI): 80%
         Mutation Code Coverage: 100%
         Covered Code MSI: 80%

検出に失敗した 5 種類の mutants を列挙します。このうち、インデックスの誤りについては、最短経路に頂点 0 を含むテストデータを適切に作成すれば発見できます。距離の比較に等号を含めるかどうかは、どちらでも最短経路を戻すことに変わりはないので、テストケースの不足による見逃しではありません。

[11 行目] $prevs の初期化時にインデックスを 1 から始める (頂点 0 の $prev が初期化されない)

-        $prevs = array_fill(0, $n, $x);
+        $prevs = array_fill(1, $n, $x);

[17 行目] ループカウンタを 1 から始める (頂点 0 が無視される)

-            for ($i = 0; $i < $n; $i++) {
+            for ($i = 1; $i < $n; $i++) {

[19 行目] 距離の比較に等号を含める (距離が等しい場合に後勝ちになる)

-                if ($distances[$i] < $minDistance) {
+                if ($distances[$i] <= $minDistance) {

[25 行目] ループカウンタを 1 から始める (頂点 0 が無視される)

-            for ($i = 0; $i < $n; $i++) {
+            for ($i = 1; $i < $n; $i++) {

[27 行目] 距離の比較に等号を含める (距離が等しい場合に後勝ちになる)

-                if (($newDistance = $distances[$k] + $graph[$k][$i]) < $distances[$i]) {
+                if (($newDistance = $distances[$k] + $graph[$k][$i]) <= $distances[$i]) {

実は今回の例では、最初に作成した 5 頂点のグラフに対する単体テストだけで mutation testing を行っても次の結果になりました。Metamorphic Testing は単体テストを含めた一般的なテスト手法を代替するようなものではなく、一般的なテストはしっかり用意したうえで、それを補強する役割を持つものなのだと思います。

25 mutations were generated:
      15 mutants were killed
       0 mutants were not covered by tests
       6 covered mutants were not detected
       0 errors were encountered
       4 time outs were encountered

Metrics:
         Mutation Score Indicator (MSI): 76%
         Mutation Code Coverage: 100%
         Covered Code MSI: 76%

なお、単体テストで発見できなかった mutants のうち、先に列挙した 5 種類以外の残り一つは次のとおりです。これは、最短経路に頂点 ($n - 1) を含むテストデータを適切に作成すれば発見できます。

-        $prevs = array_fill(0, $n, $x);
+        $prevs = array_fill(-1, $n, $x);

*1:T. Y. Chen, S. C. Cheung and S. M. Yiu, Metamorphic Testing: A New Approach for Generating Next Test Cases, Technical Report HKUST-CS98-01, Department of Computer Science, The Hong Kong University of Science and Technology, 1998.

*2:この記事を作成した時点では、ウェブページ内のリスト項目の 207 番にあります。

*3:テクニカルレポートにはバグを含むコードが示されていますが、この記事の実装ではバグは除去しています。また、最短距離のほかに最短経路を出力するように、実装を追加しています。

*4:$graph[$i][$i] = 0 とします。また、無向グラフであるので $graph[$i][$j] = $graph[$j][$i] が成立することとします。

*5:テクニカルレポートの Table 3 にまとめられています。

*6:ただし簡単のため、$x と $y の最短経路が [$x, $y] になるケースを無視しています。乱数の seed によってはそのような経路が得られることもあり、その場合にはテストケースは正しく動作しません。

*7:PHP での mutation testing については前回の記事を参照してください。

y_uti のブログ

統計、機械学習、自然言語処理などに興味を持つエンジニアの技術ブログです

プログラムの準備と単体テストの作成

Metamorphic Testing によるテストケースの作成

Mutation Testing によるバグの検出力の確認