テストデータ生成系 Korel 法 の調査第一回 – テストデータ生成系の概要

はじめに

テストデータ生成系と呼ばれるものは世間に澤山あるが、 我々は Korel 法というものに着目し、その実装と評価を行ってみたので、 これから何回かに分けて紹介したい。

今回はテストデータ生成系のサーベイ結果をまとめる。 サーベイは主にこの分野のサーベイ論文 [2][11][14] を起点とした。

言うまでもなく「完全な」テストデータ生成系は理論的に作成不可能である。 そんな処理系があれば、明らかにチュリングマシンの停止問題が解けてしまうことになる。 一方で、プログラムのテストは非常に面倒な作業であり、 不完全であっても、ある程度テストを助けてくれるような処理系が存在すればすばらしいことであり、 現在まで多くの研究がなされてきている。

プログラム解析について

ここでは、テストデータ生成系の基礎的な技術要素であるプログラム解析について 簡単に説明する。 元来、プログラム解析技術はコンパイラの分野で育まれてきたものであり、 ソースコードの意味を様々な視点で解析することで、 よりよい機械語を生成するために使われてきている。

そして、現在ではテストデータ生成やリバースエンジニアリングを含む SE の広い分野で、 基礎的な技術要素として使われている。 データ生成系に関連する用語と意味を以下にまとめる。

  1. フローグラフ

    プログラム解析を行う場合、解析に向いたデータ構造として使われる 有向グラフであり、各文をノードとし、そこからその次に実行され得る文への リンクを持つデータ構造である。

  2. データーフロー解析

    フローグラフの構造を基に、データの定義と参照の関係を静的に解析する もの(さまざまな種類がある)を一般的にデーターフロー解析という。

  3. データー依存解析

    データーフロー解析の一つ。 ある文 S1 で定義された変数が別の文 S2 で参照され得る場合、S1 から S2 へのデータ依存があるという。

  4. 制御依存解析

    例えば if (x<0) a++ という条件文では、 xa にはデータ依存関係は無いが、それでも a++ という文は 制御の流れを支配する x に依存する。このような依存関係を 調べる解析を制御依存解析という。

  5. プログラムスライス

    データ依存関係と制御依存関係を合併した関係は、プログラムの挙動の 依存関係を正確に表している。この関係から、プログラムのある注目点 に関係する部分のみを残し、他の部分を削るプログラムスライスという 手法が提案された[16][12]。本来は プログラムのデバッグのために提案された手法であるが、プログラム解析 一般に援用することが出来る。プログラムスライスの応用を概観するには [18]が良い。

  6. 動的データ依存解析

    プログラムの具体的な実行系列に対して行うデータ依存解析である。 例えば A[i+j] = 0 という代入文で、静的解析では一般に i+j の値は分からないので A のどこかに代入された、 と扱わざるをえないが、動的解析では実際にプログラムを実行した 結果 i+j = 2 ということが分かり、 A[2] に代入された ことが分かる。動的解析は配列を含むテストデータ生成では不可欠である。

  7. 動的プログラムスライス

    動的データ依存解析と制御依存解析から、特定のデータに対して 意味を変えないように行うプログラムスライスを動的スライス という[9][4][10]。

テストデータ生成系の外部仕様の種別

この分野のサーベイ論文 [2][11][14]によると、 代表的な外部仕様は以下の二つに大別される。外部仕様の名称であるが、 なぜか「指向」(oriented) という用語が使われるようなので、 ここでもそれに従う。

  1. パス指向

    パスとは、プログラムの実行に伴い実行される文の列であり、 具体的には文の行番号の列を意味する。パス指向とは、 プログラムに対して期待する特定のパスを指定し、そのパスを再現 するようなデータを自動生成するものである。

  2. ゴール指向

    これはパスではなく、特定の文を指定し、その文が実行されるような データを自動生成するものである。この場合、指定された文へ至るパス は任意であり、可能な一つが選ばれることになる。

一見、 1. の方が複雑な処理に思えるが、 実際には次に実行すべきゴールが逐次指定されているので、 最終ゴールのみ指定される 2. の方が難しい問題である。 しかし、テストデータ生成系を利用する立場からは、明らかに 2. の方が使いやすい。2. については、 特定のゴールへ至るパスをまず発見する部分、 すなわちパス選択系 (path selector) を別に設けることによりゴール指向が実現する。 ただし、これらを完全に分離することは無理であり、現在のゴール指向では それらがある意味一体化された chaining 法[3]が基本的である。

                 ゴール指向  =  パス指向  +  パス選択系

テストデータ生成系の実装の種別

上記の外部仕様に対して、どのようにテストデータを生成するのかという 手法としては以下のものがある。

  1. ランダム法

    ランダムにテストデータを生成し、多くのパスを通すという素朴な 手法である。単純にカバレージを上げるには、この手法は簡単であるが、 そこへ至るデータがランダムな生成では不可能という場合も多い。

  2. 記号実行法

    特定のパスあるいはゴールへ至る条件を記号実行により制約として求め、 最後にその制約を解くというアプローチであり、70 年代によく研究されて いたという。しかし記号実行は基本的に静的な解析であり、 実行時の具体的な値が定まらないと検索範囲が膨大になり実用的ではない。

  3. Korel 法

    上記の記号実行法では配列等、実際的なプログラムに現れるデータを 生成することは困難であるという視点から、Korel は[5] で 以下のようなアプローチを提案した。 これは以下のようなアイディアに基づく。

    1. 具体的なデータでプログラムを何度も実行させつつ、データを修正
    2. 動的データ依存解析に基づくデータ検索ヒューリスティック
  4. Genetic Algorithm 法

    ランダム法に近いが、GA 等の AI 的検索手法を援用して精度を上げるという 試みである[1][13]。ただし、論文では ごく小さなプログラム例しかなく、またランダム法との比較のみであり、 現時点ではまだまだ研究段階であると思われた。

Korel 法の概要

ここではテストデータ自動生成系の代表的な手法 [5] を簡単に説明する。

以下のプログラムは与えられた配列 A を step 刻みで low から high まで調べ、 その間の最大、最小値を求めるものである。

 1:  get(low, high, step, A)
 2:  min = A[low];
 3:  max = A[low];
 4:  i = low + step;
 5:  while (i < high) {
 6:    if (max < A[i])
 7:        max = A[i];
 8:    if (min > A[i])
 9:        min = A[i];
10:    i = i + step; }
11:  put(min,max);

このプログラムと指定実行パス <1,2,3,4,5,6,8,10,5,6,8,9,10,5,11> に対 するデーター生成過程は以下のようになる。

プログラムの入力は配列変数 A[1],A[2],...,A[100], high, step, low である。 まず、これらにランダムな「初期値」として以下を設定する。

A[1]=1,A[2]=2,...,A[100]=100, high=93, step=12, low=39

実行させてみると、文 6 の条件 (max \(\leq\) A[i]) が真となり、<1,2,3,4,5,6, の次が文 7 となって失敗する。

失敗個所が成功するには F(X) = A[i]-max としたとき、 F(X) \(\leq\) 0 となればよい。 F を分岐関数という。1

X = A[1],A[2],...,A[100], high, step, low なので、検索範囲は膨大になるが、 このような処理を全体が成功するまで繰り返すと、以下のようなデータが見つかる。

 A[1]=1, ... A[39]=51, ... ,A[63]=-37, high=67, step=12, low=39

このような素朴な方法では変数の依存関係を無視しているため、 条件 F に全く関係の無い変数群まで変化させており、非効率である。 [5] では静的プログラムスライス [16][12] 及び動的プログラム解析[9][4]により、 F に関係する変数を絞り込むことで効率的な検索が可能であるとしている。

特に、大きなサイズの配列に対しては、具体的な添え字の値を利用する解析、 すなわち動的なプログラム解析が重要である。 例えば上記で初期値から出発し、 F で失敗した時点までの動的なデータ依存解析を行えば、 F に関連している変数 X = A[39], A[51], step, low のみであり、 この変数のみの組み合わせを考えればよいことが分かる。2

この例から明らかなように、テストデータの自動生成ではプログラム解析により 検索範囲を絞り込むことは「必須」である。しかし一方で検索範囲を絞り込んだり、 あるいはリスクファクタといった補助情報を提供するための解析自体に時間が 掛かっては元も子もない。すなわち適当なトレードオフが重要である。 これは後に我々の実験結果からも明らかになる。

ゴール指向のテストデータ生成系について

ゴール指向のテストデータ生成系はパス指向のアルゴリズムの拡張であり、 Chaining 法 [6][3] が代表的手法である。

ただし、 今回の我々の実験では、ゴール指向のテストデータ生成系の実装までは至らなかったので、割愛する。

次回豫告

次回は、今回の実験のために設計した プロトタイプ言語 P と 静的プログラムスライスの例 について述べる。乞う御期待。

Footnotes:

1 しかし、実際には F(X) \(\leq\) 0 をクリアするだけでは不十分である。 変数の値の組み合わせ X は、現時点まで成功してきたパス選択の全てに関わっているので、 これまでの成功していた選択を破壊しないという制約下で F(X) \(\leq\) 0 をクリアしなければならない。 そしてこの条件がクリアされたら、さらに次の条件 F'(X) \(\leq\) 0 をクリアしていかねばならない。
このような状況を考慮し、 この時点で単に F(X) \(\leq\) 0 を満たす組み合わせを見つけて先に進むのではなく、 可能なかぎり F(X) \(<<\) 0 となる X すなわち、 F(X) を最小化する最適化問題により X を求めて、 先に進むというヒューリスティックが使われる。
Korel 法はしばしば、テストデータ生成問題を最適化問題に変換する手法と表現されるが、 それはこのヒューリスティックによる最適化問題への変換を指している。

2 さらに、Korel 法では動的解析の過程で、 各変数が目的の条件式に至るまでの途中の条件式に影響を与える度合を計算する。 この度合をリスクファクタと呼ぶ。このファクタは変数を動かす順序付けに利用される。 直感的にはリスクファクタが高い変数はなるべく動かさない方が安全である。

References

[1] et al. Christoph C. Michael. Genetic algorithms for dynamic test data generation. ASE, 1997. [ bib ]
[2] Jon Edvardsson. A survey on automatic test data generation. In The 2nd Conf. on Computer Science and Engineering, 1999. [ bib ]
[3] Roger Ferguson and Bogdan Korel. The chaining approach for software test data generation. ACM Trans. Softw. Eng. Methodol., 5:63-86, 1996. [ bib ]
[4] Joseph R. Horgan Hiralal Agrawal. Dynamic program slicing. ACM SIGPLAN Notices, 25, 1990. [ bib ]
[5] Bogdan Korel. Automated software test data generation. IEEE Transactions on Software Engineering, pages 870-879, 1990. [ bib ]
[6] Bogdan Korel. A dynamic approach of test data generation. In Conference on Software Maintenance, 1990. [ bib ]
[7] Bogdan Korel. Automated test data generation for programs with procedures. ISSTA, 21, 1996. [ bib ]
[8] Bogdan Korel and Ali M. Al-Yami. Assertion-oriented automated test data generation. ICSE, pages 71-80, 1996. [ bib ]
[9] Bogdan Korel and Janusz Laski. Dynamic program slicing. Information Processing Letters, 29:155-163, 1988. [ bib ]
[10] Bogdan Korel and Jurgen Rilling. Dynamic program slicing methods. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.167.3388. [ bib ]
[11] Shahid Mahmood. A systematic review of automated test data generation techniques. Master's thesis, 2007. [ bib ]
[12] K. Ottenstein and L. Ottenstein. The program dependence graph in a software development environment. In Prodeedings of the ACM SIGSOFT/SIGPLAN, pages 177-184, 1984. [ bib ]
[13] Pargas Roy; Harrold Mary; Peck Robert. Test data generation using genetic algorithms. Journal of Software Testing, Verification and Reliability, 1999. [ bib ]
[14] Hitesh Tahbildar and Bichitra Kalita. Automated software test data generation: Direction of research. IJCSES, 2, 2011. [ bib ]
[15] Andrew W.Appel. Modern Compiler Implementation in ML. Cambridge Univ. Press, 1998. [ bib ]
[16] Mark Weiser. Program slices when debugging. CACM, 25:446-452, 1982. [ bib ]
[17] Ruilian Zhao and Michael R. Lyu. Character string predicate based automatic software test data generation. In Third International Conference on Quality Software, 2003. [ bib ]
[18] 下村隆夫. プログラムスライシング技術と応用. 共立出版, 1995. [ bib ]

This file was generated by bibtex2html 1.96.

Author: Abe Seika

Date: 2013-06-11T10:24+0900

Generated by Org version N/A-fixup with Emacs version 24

© Mathematical Systems Inc. 2013