状態のあるコードに対するテストの自動生成 - 西尾泰和のはてなダイアリー

BLUE*アルゴリズムを実装してみたので、せっかくだからテストの自動生成をやってみた。

今回テスト対象にするコードの仕様は

開く、閉じる、書き込む、の3つの操作ができる
開いてないのに書き込んだり閉じたりしたらエラーになる

というもの

そしてこちらがそれの「バグのある実装」：

class Target(object):  # bad impl.
    def __init__(self):
        self.opened = False
        self.closed = False

    def open(self):
        self.opened = True

    def write(self):
        if not self.opened:
            raise RuntimeError
        if self.closed:
            raise RuntimeError

    def close(self):
        if not self.opened:
            raise RuntimeError
        self.closed = True

まずは手動でテストを書く。e_plusは「エラーにならないはずの操作」で、e_minusは「エラーになるはずの操作」、open, close, writeがそれぞれo, c, wと略されている。

e_plus = ['o', 'oc', 'ow', 'owc', 'oww', 'owwc', 'owww']
e_minus = ['c', 'w', 'ocw']

このテストをBLUE*に食わせると、その条件をみたすようなDFAが作られる。

これを幅優先探索してテストケースを生成し、それをDFAと実際の実装の両方に食わせて、結果が異なるものを探す。

まず4つ目の候補でミスマッチが見つかった。openしてまたopenした際に、DFAは「エラーになるべき」と主張しているが、実装はエラーにならない、とのこと。うん、それは仕様には明確には書かれていない。今回はエラーになるべきと判断したことにする。仕様に追記して実装を修正しよう。

4: for input ['o', 'o']: dfa said False, but target said True

実装を修正。

    def open(self):
        if self.opened:
            raise RuntimeError
        self.opened = True

再度実行。今度は8番目の候補でミスマッチが見つかった。曰く「openしてcloseした後、さらにcloseした場合、DFAはエラーを期待したが、実装はそうなってない」とのこと。閉じているものを再度閉じた時にエラーになるべきかどうかは仕様に明記されていない。これはエラーになるべきと判断して、実装を修正する。

8: for input ['o', 'c', 'c']: dfa said False, but target said True

勘の良い人は気づいていたと思うけど「開いているか、開いてないか」の2状態を管理したいだけなのにclosedなんてフラグは必要ないわけだよね。

class Target(object):
    def __init__(self):
        self.opened = False

    def open(self):
        if self.opened:
            raise RuntimeError
        self.opened = True

    def write(self):
        if not self.opened:
            raise RuntimeError

    def close(self):
        if not self.opened:
            raise RuntimeError
        self.opened = False

実装を修正したので再度探索を実行。

今度は「openしてcloseした後openした場合、DFAはエラーになると期待したが実装はそうではない」とのこと。閉じた後再度開けるのかどうかも仕様には明記されていないな。これは開けるという仕様にする。つまり、これはDFAの側が間違っている。こういう場合は「それはエラーにならないのが正しいんだよ」とe_plusに追加して教えてやる。

7: for input ['o', 'c', 'o']: dfa said False, but target said True

ocooは成功すると思ったらしいが、でもこれはエラーになるのが正しい。これは「エラーになるのが正しいんだよ」とe_minusに追加して教えてやる。

13: for input ['o', 'c', 'o', 'o']: dfa said True, but target said False

これも実装が正しい。

16: for input ['o', 'w', 'c', 'o']: dfa said False, but target said True

これも実装が正しい。

34: for input ['o', 'w', 'w', 'w', 'o']: dfa said True, but target said False

そうすると探索プログラムが「長さ20以下の入力列について、ミスマッチは見つかりませんでした」と報告してくる。めでたしめでたし。

長さ20以下の操作列をテスト、ってことで素朴に全探索してたら3 ** 20で3486784401個あるんだけども、こちらではエラーになるパスより先は探索しないので53130個で済んでいる。何も考えずにランダムにテストするのに比べると6万倍の高速化ですな。一方人間の記述としては正のテストが9個、負のテストが5個なのでその記述から約4000倍のテストが生成されていることになる。

この時のDFAはこんな感じになっている。人間が書いたら3と5はくっつけると思うけど、まあ間違ってはいない。

今回は入力にノイズが入っていないが、BLUE*自体はノイズのある列からどうやってDFAを推定するか、というアルゴリズムなので近いうちにノイズのある例で使ってみたい。

参考文献

"BLUE*: a Blue-Fringe Procedure for Learning DFA with Noisy Data" by M Sebban, J Janodet, F Tantini
"From Test Cases to FSMs: Augmented Test-driven Development and Property Inference" by Thomas Arts and Simon Thompson