テストデータ生成系 Korel 法 の調査第二回 – プロトタイプ言語 P

プロトタイプ言語 P

前回はテストデータ生成系と呼ばれるものついて、ざっと俯瞰してみたが、 今回は Korel 法に基づいたテストデータ生成系の手法を実装し実験するために設計した、 小さなプロトタイプ言語 (P 言語) と、 代表的なプログラム静的解析の一つであるプログラムスライスについて説明する。

以下に P 言語の言語仕様を示す。

以下の構文表記を使う。

  (X)           - グループ化
  X|Y           - 選択
  [X]           - 1 回以下の繰り返し
  {X}           - 0 回以上の繰り返し
  {X ! Y}       - X Y を 0 回以上の繰り返し、最後は ! の前(X) で終わる列
                  e.g. {a b ! c d} -> a b c d a b c d ... a b
以下具象構文。

                            /* Declarations */

    <Program>       : <Ident> <ParamList> <BlockStmt>

    <ParamList>     : '(' {<VarDecl> ! ','} ')'

    <VarDecl>       : <Type> <Ident>

    <Type>          : <PrimitiveType> [ '[' <Expr> ']' ]
    <PrimitiveType> : int
                    | string
                    | date

                            /* Statements */

    <Stmt>          : <VarDeclStmt>
                    | <ExprStmt>
                    | <IfStmt>
                    | <WhileStmt>
                    | <BlockStmt>
                    | <EmptyStmt>

    <VarDeclStmt>   : <VarDecl> ';'
    <ExprStmt>      : <Expr> ';'
    <IfStmt>        : if (<Expr>) <Stmt> [else <Stmt>]
    <WhileStmt>     : while (<Expr>) <Stmt>
    <BlockStmt>     : '{' {<Stmt>} '}'
    <EmptyStmt>     : ';'

                            /* Expressions */

    <Expr>          : <AssignExpr>
    <AssignExpr>    : <ArefCallExpr> ['=' <CmpExpr>]
    <CmpExpr>       : {<AddExpr> ! '<'|'<='|'>'|'>='|'=='|'!='}
    <AddExpr>       : {<MulExpr> ! '+'|'-'}
    <MulExpr>       : {<ArefCallExpr> ! '*'|'/'}
    <PreExpr>       : ['+'|'-'] <PreExpr>
                    | <ArefCallExpr>

    <ArefCallExpr>  : <ArefExpr>
                    | <CallExpr>

    <ArefExpr>      : <FactorExpr> '[' <Expr> ']'

    <CallExpr>      : <FactorExpr> '(' <ExprList> ')'

    <ExprList>      : {<Expr> ! ','}

    <FactorExpr>    : <Ident>
                    | <IntLiteral>
                    | <StrLiteral>
                    | '(' <Expr> ')'

P はプロトタイプ言語ではあるが、 データ生成の本質的な部分をカバーするため、一次元配列もサポートしている。 P 言語をテストデータ生成系の観点で一般のプログラミング言語と比較した場合に 問題となる相違点は以下の通り。

  1. 制御構造が if と while のみ
  2. 手続き呼び出しが無い
  3. 浮動少数型が無い
  4. 文字列型(の自動生成)が無い
  5. レコード型が無い
  6. 動的な配列型が無い
  7. 参照型が無い
  8. OS とのやりとり(ファイルシステム、DB、ネット、etc.)が無い

テストデータ生成系で必要となるプログラム解析機能として、 P 言語処理系では、 静的データ依存解析、制御依存解析、動的データ依存解析を実装した。

静的プログラムスライス

Korel 法に限らず、いづれのテストデータ生成手法においても、 静的プログラムスライスと呼ばれる手法 (上記静的データ依存解析と制御依存解析を利用する) は有効である。 分かりやすい例として、以下に P 言語処理系を使ったスライスのデモを示す。

以下は Unix の wc コマンドと同様のプログラムである。 簡単のため、入力は str 変数に設定されている値としている。

 1:  wc() {
 2:    string str;
 3:    int len;
 4:    int i;
 5:    int inw;
 6:    int nl;
 7:    int nw;
 8:    int nc;
 9:    int c;
10:  
11:    // This str simulates input stream
12:    // terminated by '.'
13:    str = "abc\ndef ght\njkl\n.";
14:    len = strlen(str);
15:    i = 0;
16:  
17:    inw = 0;
18:    nl = 0;
19:    nw = 0;
20:    nc = 0;
21:  
22:    c = sref(str,i);
23:    i = i+1;
24:  
25:    while (c != '.') {
26:      nc = nc + 1;
27:      if (c == '\n')
28:        nl = nl + 1;
29:      if (c==' ')
30:        inw = 0;
31:      else if (c=='\n')
32:        inw = 0;
33:      else if (inw == 0) {
34:        inw = 1;
35:        nw = nw + 1;
36:      }
37:      c = sref(str,i);
38:      i = i+1;
39:    }
40:  
41:    println("Lines: ",nl);
42:    println("Words: ",nw);
43:    println("Chars: ",nc); << ここに注目してスライス
44:  }

ここで、最後の文字カウント出力文に注目してプログラムスライスを行ってみる。 即ち、このプログラムから文字数をカウントする部分のみを抽出するのである。

P プログラムはまず構文解析により抽象構文 (AST) に変換される。

次に P 処理系は、AST を、以下のような有向グラフ表現「フローグラフ」に変換する。 各ノードは次の情報を持つ。

ソース行番号: 定義変数:=参照変数 [制御依存情報]      ; 制御依存情報とは制御依存解析のための補助情報である

./flow-graph.png

上図で例へば、ソース行番号 37 において、 stri が参照され、 c が定義されており、 ソース行番号 25 からの制御依存 (ControlDependency) がある事を示している。

フローグラフを元に、プログラムスライスではまずデータ依存解析を行う。 データ依存解析とは、ある命令を実行後、 その命令の効果(変数への代入)が直接影響を及ぼす命令を調べる解析である。

./data-dependency.png

./data-dependency-2.png

./data-dependency-3.png

プログラムスライスで次に必要なのが、制御依存解析である。 制御依存解析とは、ある条件分岐を含む命令の実行結果が、 他の命令の実行に直接影響を及ぼすような関係を調べるものである。

./control-dependency.png

上記の二つの依存関係を合併したものをプログラム依存情報といい、 この関係のグラフを PDG (Program Dependence Graph) という。 解析処理自体は、単に上記の二つの依存関係をマージするだけである。

./program-dependency.png

この PDG の典型的な利用方法が、すなわちプログラムスライシングである。 PDG はプログラムのデータと制御の依存関係を正確に反映しているので、 ある命令 (スライス基準) を指定し、それに「影響を与えない」部分を削ることが出来る。 そのためには、一旦 PDG を逆の関係にした以下のグラフを作っておけば、 あとはスライス基準 (下図では printChars) からグラフをたどり、到達しなかった部分を捨てればよい。

./slice-dependency.png

得られたスライスプログラムは以下のようになる。

13:      str = "abc\ndef ght\njkl\n.";
15:      i = 0;                       
20:      nc = 0;                      
22:      c = sref(str,i);             
23:      i = i+1;                      
25:      while (c != '.') {            
26:        nc = nc + 1;                
37:        c = sref(str,i);            
38:        i = i+1;                    
43:      println("Chars: ",nc);        

このように、プログラムスライスを用いれば、 テストデータ自動生成を考える際の場合の数を極端に減らす事ができ、有效である。 しかし配列が単一の変数として扱われるため、 配列の添え字がシビアに影響するプログラムに対しては精度が悪い。 一般に静的解析では配列の扱いが難しく、厳密な解析は不可能である。 配列の各要素に立ち入った解析には、 具体的なデータによるプログラムの実行過程に基づいた動的解析が必要となる。

次回は、 P 言語の動的データ依存解析について解説する。

Author: Abe Seika

Date: 2013-06-21T16:50+0900

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

© Mathematical Systems Inc. 2013