日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集

オブジェクト指向プログラミングにおける内部状態を考慮したテストケース自動生成手法
高松 宏樹

佐藤 晴彦

小山 聡

栗原 正仁

ソフトウェアテストは，プログラムの動作を検証し，仕様通りに実装されているかを確認する手法として広く用いられているが，ソフトウェアの大規模化に伴いテスト工程のコストが増大しており，テストケースを自動生成する技術が注目されている．オブジェクト指向プログラミングにおけるテストでは従来のテストデータを生成する手法とは異なり，事前メソッド列（Method Sequence）が必要となる．事前メソッド列を含むテストケースを自動生成するツールの一つに Seeker があるが，Seeker では複数の変数を変更しなければ実行できないパスを通るテストケースを生成することができない．そこで，本論文では，複数の変数を変更する必要がある場合にも適切なテストケースを生成する手法を提案し．実装した．また，複数のオープンソースプロジェクトに対して．Seeker と提案手法をそれぞれ適用し，比較実験を行うことで，本研究の有用性を示す．

出しを含むテストケースを生成することができない．

1 はじめにそこで，本研究では，Seeker を拡張することにより，オブジェクト指向プログラムのテストにおいては，複数の変数を考慮したメソッド呼び出しを含むテストインスタンスの状態についてのアサーション（真であケース自動生成手法を提案し，実装した．また，候補るべき命題）の真偽を検証するコードを実行する前となるメソッドの数が膨大になり，現実的な実行時間に，インスタンスの状態を適切な状態に変化させるたでテストケースの自動生成を行うことができないこめの一連の適切なメソッド呼び出しを行う必要があとが予測できるため，本研究では，メソッドそれぞれる．そのため，オブジェクト指向プログラミングにおに評価値を与え，探索空間の削減を行うことにより，けるテストケース自動生成を行うためには，入出力のこの問題を解決した．

データだけではなく，メソッド呼び出しのコードも生

本論文の構成は以下の通りである．2 節では関連研成しなければならない．このようなテストケースの自究について説明し，3 節で既存手法の問題点と，その動生成を行うため，プログラムの静的解析と動的解解決策としての提案手法について述べ，4 節では提案

析を組み合わせた動的記号実行 (Dynamic Symbolic手法を適用した予備実験について説明・実験結果の考Execution, DSE) という手法が注目を集めている．

察を行い，5 節でまとめを行う．

このようなテストケースの自動生成を行うツールの一つに Seeker [6] がある．だが，Seeker は，ある実

2 関連研究行パスを通るための条件式を満たすために複数の変2. 1 動的記号実行数を操作する必要がある場合に，適切なメソッド呼び

動的記号実行はテストで行う具体的な値を用いたテ

Automated Test Case Generation Considering Object
States in Object-Oriented Programming
Hiroki Takamatsu, Haruhiko Sato, Satoshi Oyama,
Masahito Kurihara, 北 海 道 大 学 大 学 院 情 報 科 学 研
究科, Graduate School of Information Science andTechnology, Hokkaido University.

ストと，記号実行を組み合わせたテストケース自動生成手法の一つである．具体的な値 (Concrete Value)を用いたテストと記号実行 (Symbolic Execution) [1]を組み合わせることから，Concolic Testing [4] とも呼ばれる．DSE では，ある関数について，プログラム中の条件式を一階述語論理式に変換し，それを SMT能なパスについてテストケースを生成する

ソルバ (Satisfiability Modulo Theories Solver，背景3. DSE で実行できなかったパスの条件式につい理論付き SAT ソルバ) [11] を用いて解くことにより，て，式を満たすために値を変更しなければならな条件式を満たすような各変数の割り当てを決定する．

い変数 (目標フィールド) を特定する．

この値を用いることで，それぞれ異なった実行パスを通ることができる．

4. 目標フィールドをメンバ変数として持つクラスの継承・包含関係を解析する．

DSE に関する研究は近年盛んに行われており，実装

5. メソッド呼び出しグラフを構築し，目標フィーには，Sen らによる CUTE/jCUTE [4] を始め，Till-ルドの値を変更し得るメソッドを抽出する．

mann らによる Pex [7] などがある．

6. 抽出したメソッドを事前メソッド列に追加して，新たなテストケースの候補とし，2. に戻る．

2. 2 事前メソッド列

まず始めに，DSE により多くの実行パスを通るよ

オブジェクト指向言語におけるテストケース自動生

うに，テスト対象コードを引数を変更して繰り返し成では従来とは異なる問題が生じている．オブジェク

実行することで，テストケースの自動生成を行う．そト指向プログラミングでは，引数として，ある特定のの後，実行できなかったパスについて，そのパスを通状態のオブジェクトを要求することやテスト対象オブるための条件式を満たすために変更しなければならジェクトの状態を変化させる必要があるなど，テストない変数 (これを目標フィールド (target field) とすを行うにあたって，テスト対象メソッドを呼び出す以る) の特定と，目標フィールドが属するオブジェクト外の処理を必要とすることが多い．このようなテストの依存関係を表す Field Hierarchy の構築を行う．そに必要な処理を行うメソッド呼び出し系列を本研究でして，目標フィールドの値を変更し得るメソッドを事は事前メソッド列と呼ぶ．この問題により，従来のテ前メソッド列に追加する候補として抽出し，新たな事ストデータのみを生成する手法では，高品質なテスト前メソッド列を生成する．生成した事前メソッド列をを生成することができないため，事前メソッド列を含含むテストケースを用いて，再度，DSE によるテスむインスタンスの状態を考慮したテストケース自動トケースの生成を行う．この操作を繰り返し行うこと生成手法が必要とされている．このようなテストケーで，インスタンスを特定の状態に変化させなければ通ス自動生成ツールには Seeker や tpalus [10] がある．

ることのできない実行パスについてもテストケースを生成することができる．

2. 3 Seeker
前述した事前メソッド列の問題を解決するため

3 提案手法に Microsoft Research で開発されたツールの一つに前述した Seeker では，未実行パスの条件式に複数Seeker がある．Seeker は DSE を基盤として，プロの変数が関係していた場合に，適切な事前メソッド列グラムの動的解析と静的解析を組み合わせることでを生成できないという問題が挙げられる．そこで，そ事前メソッド列を含むテストケースの自動生成を行うのような場合にも，各目標フィールドについて，そのC#言語向けのツールである．

値を変更し得るメソッド群を候補として抽出し，条件

本研究では，提案手法を Seeker の拡張として実装を満たすようなメソッド呼び出しの組み合わせを探索したため，ここではまず Seeker の事前メソッド列生することにより，事前メソッド列を生成する手法を提成アルゴリズムについて述べる．手順は以下の通りで案する．

ある．

1. テスト対象メソッドを呼び出すだけのテストケースを生成する

2. DSE を行い，引数の値を変更することで実行可

3. 1 アルゴリズム
ここでは，提案手法のアルゴリズムを述べる．提案
手法では，既存手法である Seeker のアルゴリズムのうち，静的解析を行う処理を拡張し，未実行パスの条るため，フィットネス関数により算出した評価値を事

件式に複数の変数が関係していた場合に，それらの前メソッド列の優先度として利用した．優先度の高い変数すべてを目標フィールドとし，それぞれの値を変順に候補メソッドを追加し，新規事前メソッド列を生更し得るメソッドを候補メソッドとする．このとき，成する．これにより，無駄なテストケースを生成するメソッド呼び出しの組み合わせ数が膨大になることことを防ぎ，より効率的にテストケースの生成を行うが予想されるため，その後に，候補となる事前メソッことができると考えられる．

ド列の削減，評価値を元にした事前メソッド列の優先度付けを行うこととした．以下で，それぞれの処理に4 予備実験

おいて，既存手法とは異なる処理を説明する．

本実験では，複数のオープンソースプロジェクトに

3. 1. 1 静的解析

既存研究と提案手法をそれぞれ適用することで，提静的解析のステップでは，既存手法のアルゴリズム案手法の有用性を評価することを目的とする．このを基本として，条件式に複数の変数が関係していたとき，より良いテストケースが生成されていることときに，それらすべてを目標フィールドとして選び，を検証する方法として，テストの質を表す代表的なそれぞれについて，Field Hierarchy の構築とメソッ指標である分岐網羅率を用いた．一般に，分岐網羅率ド呼び出しグラフの作成を行う．この操作により，複が高いほど，良いテストであると言われている．今数の変数を変更しなければ条件式を真にできない場回の予備実験では，既存研究と同様に，4 つのオー合にも適切な事前メソッド列を生成することが可能にプンソースプロジェクトに提案手法を適用した．実なる．

験対象となるオープンソースプロジェクトは，Dsa

3. 1. 2 候補の削減[5], QuickGraph [3], xUnit [9], NUnit [2] の 4 つであ提案手法では，複数の変数について候補となるメる．提案手法は，ソースコードが公開されている既存ソッドを取得することにより，生成する事前メソッド研究を拡張する形で C#で実装した．評価に際して，列の数が膨大になることが考えられる．例えば，目標実行時間と分岐網羅率を計測し，提案手法の有用性をフィールドとなるものが 2 つあり，その値を変更する考察した．

メソッドがそれぞれ 10 個あるとする．このとき，次本実験を行うにあたって，各設定値は既存研究とのステップで新たに生成される事前メソッド列の数は同様に以下のように設定した．また，実行環境は，20 個である．さらにメソッド呼び出しが必要となる

Windows Vista SP2 32bit，CPU は Intel Core2Duo

場合に，同様の候補メソッドから事前メソッド列を生2.53GHz，RAM4GB である．

成すると，既存の事前メソッド列 20 個 × 候補メソッ• タイムアウト時間: 500 秒 (デフォルト: 120 秒)

ドの総数 20 個の計 400 個であり，組み合わせの数が• SMT ソルバのタイムアウト時間: 10 秒 (デフォ

爆発的に増加する．そのため，提案手法では，予め指定した数を事前メソッド列の上限とし，探索空間の削減を行うこととした．この際，動的解析時にフィットネス関数 [8] により算出した，各事前メソッド列の評

ルト: 2 秒)• 新規テストが生成されない場合の連続試行回数:
214748367 (デフォルト: 100)
• 最大試行回数: 214748367 (デフォルト: 100)価値を利用する．新たに候補メソッドを追加する際に，既存の事前メソッド列の数が上限値を超えていた

4. 1 結果

場合，評価値の低いものから削除する．

すべてのプロジェクトについて，提案手法を用いた3. 1. 3 事前メソッド列の優先度付け

場合に，既存手法よりも 1%から 5%程度，分岐網羅既存の事前メソッド列に候補メソッドを追加する際率が向上することが確認できた．また，提案手法でに，未実行パスの条件式を満たすために有望と思われは，実行時間が既存手法の 1.5 倍から 2 倍となった．

る事前メソッド列から新規の事前メソッド列を生成す

特に，QuickGraph については，実行時間の伸びに対して，分岐網羅率の向上幅が著しく小さいという結果ロジェクトを対象として，既存手法との比較実験をになった．

行った結果，実行時間とテストの質のトレードオフにはなるものの，提案手法により，分岐網羅率が上が4. 2 考察り，テストの質が向上することを示した．同時に，適本実験の結果より，考察を行う．まず，すべてのプ用するプロジェクトの特徴により，提案手法を用いるロジェクトについて分岐網羅率の向上が認められるもことにより認められる効果に差異が生じることを見のの，その向上幅は小さい．このことから，プロジェいだした．

クトの多くでは，問題点として挙げた未実行パスの条今後は，提案手法の改善のため，事前メソッド列の件式に複数の目標フィールドが関係しているケース

評価値を算出するフィットネス関数の改良や，事前メが少ないということや，候補メソッドの選定の際に，ソッド列に追加する候補となるメソッドのより効率的適切な事前メソッド列を棄却してしまっていることがな削減方法を提案していきたい．

考えられる．提案手法を適用することによるテストの質の向上は小さいものの，既存手法では同じ時間

参 考 文 献をかけた場合でも，同様の効果は得られない．そのた[ 1 ] King, J. C.: Symbolic execution and program
testing, Commun. ACM, Vol. 19, No. 7(1976),
pp. 385–394.
[ 2 ] NUnit: http://www.nunit.com/.
[ 3 ] QuickGraph, G. D. S. and for .NET, A.: http://quickgraph.codeplex.com/.
[ 4 ] Sen, K. and Agha, G.: CUTE and jCUTE:Concolic Unit Testing and Explicit Path ModelChecking Tools, Computer Aided Verification, Ball,
T. and Jones, R.(eds.), Lecture Notes in Computer Science, Vol. 4144, Springer Berlin Heidelberg, 2006, pp. 419–423.
[ 5 ] Structures, D. and (DSA), A.: http://dsa.
codeplex.com/.
[ 6 ] Thummalapenta, S., Xie, T., Tillmann, N.,de Halleux, J., and Su, Z.: Synthesizing method sequences for high-coverage testing, SIGPLAN Not.,
Vol. 46, No. 10(2011), pp. 189–206.
[ 7 ] Tillmann, N. and Halleux, J.: Pex―White Box
Test Generation for .NET, Tests and Proofs, Beckert, B. and Hhnle, R.(eds.), Lecture Notes in Computer Science, Vol. 4966, Springer Berlin Heidelberg, 2008, pp. 134–153.
[ 8 ] Xie, T., Tillmann, N., de Halleux, P., andSchulte, W.: Fitness-Guided Path Exploration in
Dynamic Symbolic Execution, Proc. the 39th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN 2009), JuneJuly 2009, pp. 359–368.
[ 9 ] xUnit.net Unit testing framework for C# and.NET: http://xunit.codeplex.com/.
[10] Zhang, S., Saﬀ, D., Bu, Y., , and Ernst, M. D.:
Combined Static and Dynamic Automated TestGeneration, Proc. 11th International Symposium
on Software Testing and Analysis (ISSTA 2011),
2011.
[11] 梅村晃広: SAT ソルバ・SMT ソルバの技術と応用, コンピュータ ソフトウェア, Vol. 27, No. 3(2010),
pp. 24–35.

め，提案手法には有用性があると考えられるが，実行時間とテストの質のトレードオフとなる．
また，QuickGraph のように，実行時間の伸びに対して，分岐網羅率の向上幅が小さいプロジェクトは，あるメソッドに様々なオブジェクトが関係しており，依存関係が複雑になっているものが多い．このような場合は，ある条件式を満たすために必要となる操作が多く，かつ，事前メソッド列が複雑になり，組み合わせの数が膨大になる傾向があるため今回のような結果になったと考えられる．
さらに，提案手法では，事前メソッド列の評価値を算出する際に，条件式が整数型の比較以外の場合は32 ビット整数型の最大値 (214748367) と定義している．そのため，事前メソッド列の評価値が適切ではなく，有望な事前メソッド列の候補が削除されている可能性がある．

5 おわりにオブジェクト指向プログラミングにおけるテストでは，事前メソッド列が必要となるため，これまで事前メソッド列を含む様々なテストケース自動生成手法が提案されている．そこで，本研究では，ある条件式を満たすために複数の変数を操作する必要がある場合に適切な事前メソッド列を含むテストケースを自動生成する手法を提案した．
また，提案手法を実装し，4 つのオープンソースプ