組み合わせインタラクションテストにおけるBDDを用いた制約処理法の性能評価

坂野 宏樹  中川 博之  小島 英春  土屋 達弘  

誌名
電子情報通信学会論文誌 D   Vol.J98-D   No.3   pp.384-395
発行日: 2015/03/01
Online ISSN: 1881-0225
論文種別: 特集論文 (学生論文特集)
専門分野: ソフトウェア工学
キーワード: 
組み合わせインタラクションテスト,  制約処理,  BDD,  SATソルバ,  

本文: PDF(862.7KB)
>>論文を購入


あらまし: 
本研究では,組み合わせインタラクションテストにおけるテストケース生成での制約処理について注目する.制約処理とは,テストケース生成時にテストケース若しくはテストケースの一部(インタラクション)が制約に違反していないかどうかを判定し,違反するものを除去する処理を指す.制約処理の手法は様々あるが,現在はSATソルバを用いた制約処理法が主に利用されている.本研究では,制約処理をBDD (Binary Decision Diagram)を用いて実装した場合の制約処理の性能を評価する.BDDは論理関数を無閉路有向グラフ(DAG)でコンパクトに表現するデータ構造であり,グラフのパス長に対して線形で判定できるため,高速な制約判定が期待できる.本研究では,代表的なテストケース生成ツールであるCASAを用い,CASAの制約処理部をBDDに書き換え,書き換え前のSATソルバを用いた制約処理との性能を比較した.本評価実験から,制約処理の前処理において,BDDの方が従来のSATソルバよりも高速な制約判定が可能であることが確認できた.