経路依存フローグラフを用いたInfeasible Path検出における計算量削減法

概要

論文の詳細を見る
どのような入力を与えても決して実行されることのない計算経路は実行不可能経路(Infeasible Path:IP)と呼ばれる.IP検出により,テストデータの効率的な作成や,プログラムの修正による影響波及領域の,より厳密な検出が可能となる.我々は,先に,経路依存フローグラフ(PDFG)を用いたIP検出法を提案するとともに,プロトタイプにより計算時間を評価した).本手法では,各計算経路に対して経路条件(PC)と呼ぶ式を作成した後,各PCが充足可能か判定する.そして,経路PのPCが充足可能でないとき,PをIPと判定する.しかし,本手法では,分岐文の数が多くなると,すべての経路に対する充足判定に必要な計算を実用的な時間内に行えないという問題がある.このため,本稿では,以下の計算量削減法を提案する.(1)プログラム・スライシング技法を用いて,PCを作成すべき経路の数を削減する.(2)変数に着目してPCを長さの短い式に分割し,各式について充足可能か判定することにより,充足判定の計算量を削減する.(3)索表計算(tabulation)を用いて,同一の式に対する充足判定の計算を重複させない
一般社団法人情報処理学会の論文
1994-03-07