第五回の連載では湯本が確立したテスト手法であるIDAU法のテストプロセスをツール実装し検証した研究について説明しました。第六回では、前回記事の中で述べた仮説の一つである、IDAU法をソースコードレベルのテストに適用するために独自の拡張を加えた、Code Based IDAU法(CB-IDAU)の研究について説明したいと思います。
IDAU法の課題とCB-IDAU法の仮説のおさらい
前回の第五回の記事において、湯本が確立したIDAU法をツール実装し自動化する際に確認された課題と、その解決案の一つとして導き出したCB-IDAU法の仮説について、再度、説明します。
IDAU法が対象としていたテスト工程は、結合テストやシステムテストなどのテストの後工程を対象として開発されたテスト手法であり、テストのためのインプット情報は、フロー図や機能設計書などの自然言語で記載されたドキュメントを、テスターが読み込むことでテスト項目作成に必要となる、機能とデータの操作情報の組み合わせを特定するものでした。IDAU法は、テスト技法としては、矛盾なく確立した手法ですが、自動化やツール化という観点では、テストのためのインプット情報の収集が人間系での手作業にならざるを得ないため、効率性や正確性の観点で課題がありました。そこで、前回の連載で記載したように、テストのインプット情報を機械的に入手可能な、ソースコードレベルのテストにIDAU法を応用することで、これらの課題を克服しつつ、新しいCB-IDAU法の仮説を提案しました。図1にIDAUとCB-IDAU法のアプローチの違いについて図示します。IDAU法では、システムの機能単位でのデータ操作をテスト観点としているのに対して、CB-IDAU法ではプログラムのコードの依存関係とデータ操作をテスト観点としている違いがあります。
仮説実現のための課題と対策
CB-IDAU法は、ソースコードレベルのテストにIDAU法を適用したものであり、データ操作に関する情報を網羅的に抽出した後、拡張CRUD図に基づいて、テスト項目として抽出する対を特定するプロセスに違いはありませんが、大量のプログラムの呼出関係から、自動的に且つ正確にデータ操作に関する情報を抽出するために、主にテストのためのインプット情報を取得する事前処理のプロセスがIDAU法とは大きく異なっています。何故なら、単にIDAU法をソースコードレベルのテストに応用すると言っても、以下のような課題があり、それらの課題を解決するための手法を取り入れる必要があるためです。
- 課題1. プログラミング言語依存性
ソースコードを構成するプログラム言語はPython, Java, C言語のように様々な種類のプログラミング言語が存在し、データを呼出し操作する記述はそれぞれに異なるため、どのようにしてプログラミング言語の違いを吸収するのか？
- 課題2. CRUD操作とプログラム呼出関係のマッピング
ソースコードにおいてデータを操作するための記述は多様性があり、どのようにして最終的に全てのデータ操作のソースコードを、CRUDの４種類のデータ操作にマッピングするのか？
- 課題3. 大量な呼出関係からのテストケースの抽出方法
膨大な数に登るソースコードの呼出関係を、どのようにして網羅的に解析して、最終的なテストケースの抽出を行うのか？
CB-IDAU法の研究においては、これらの課題の克服のために、以下のような対策を行いました。
- 課題1と課題2の対策：３番地中間言語の採用
ソースコードを３番地コードの中間言語に変換し、プログラミング言語非依存で、解析可能な有限の命令情報に集約することで、これらの課題を克服しました。
現存するプログラミング言語の全ての構文や命令セットに対して、解析可能な機能を実装することは現実的に不可能です。そのため、この問題を解決するための一つの手段として、解析対象となるプログラミング言語を、抽象化された中間言語に変換した後に、具体的なコード解析を行う手法が考えられます。中間言語とはIntermediate Languageと呼ばれており、プログラミング言語のコンパイラが、人間が記述したソースコードからCPUが実行可能なマシン語に変換する前に、コンパイラの変換効率を上げるためにソースコードを最適化する際に用いられます。例えば、Javaではバイトコード、C言語ではオブジェクトコードなどが中間言語として利用されています。そして、これらの中間言語が持つ表現形式のことを、Intermediate Representation (IR)と呼びます。このIRの種類の一つとして、３番地コード Three Address Codeと呼ばれる形式のものがあり、以下のような処理構造のみでプログラムの処理を表現する方式です。全てのプログラミングの処理を論理的な最小構造に分解すると、この３番地コードのIR形式のみで構成されることが知られています。
X = Z 処理 Y
この３番地コードIR形式を採用した、具体的な中間言語の一つにJimpleと呼ばれる中間言語があります。Jimpleではこの処理にあたるオペランドの種類が46個と有限であり、本研究では、これらのオペランドの操作に対してCRUDを定義することで、大量のソースコードの処理に対して自動的にCRUD情報の抽出を実現しました。各オペランドの説明等については、ソフトウェアテストのスコープからは外れてしまう内容のため、ここでは省略します。
- 課題3の対策：グラフ構造モデリングと探索アルゴリズム
ソースコードをCall Graph (CG)及びControl Flow Graph (CFG)として、数学的なノードとエッジの２つから構成されるグラフデータ構造として表現することで、グラフ探索による正確かつ網羅的な解析を可能としました。CB-IDAUの研究では、ソースコードを3番地コードの中間言語であるJimpleに変換し最適化された後に、CGとCFGを生成しています。ソースコードの情報をグラフデータ構造として解析ツール内部で保持することにより、大量のデータ操作に関する情報や依存関係の処理を、CB-IDAU法の実装ツール内部で扱い易くします。この３番地コードIR形式を採用した、具体的な中間言語の一つにJimpleと呼ばれる中間言語があります。本研究では、ソースコードをJimpleに変換して、操作に対してCRUDを定義することで自動的にCRUD情報を抽出するようにしました。実際に研究のサンプルコードとして用いたJavaプログラムをJimpleに変換して生成したCFGの例を図2に示します。
本研究では、JavaのコードからJimpleへの変換、CGとCFGの生成については、オープンソースライブラリのSootを用いました。また、グラフ構造の描画については、代表的なグラフ描画オープンソースである、graphvizとigraphを用いました。
CB-IDAU法のテストプロセスと実装
CB-IDAU法のテストプロセスについて以下に概要を図3に記載するとともに、それぞれのテストプロセスについて説明します。実際のCB-IDAU法の研究論文では11個のテストプロセスを詳細に記載していますが、本連載では図3に示す５つのプロセスで説明します。
- プロセス1. 中間言語への変換
テスト対象となるソースコードを解析して3番地コードの中間言語であるJimpleコードに変換します。これは前述したプログラミング言語の依存問題を排除するために、最初の段階で全てのプログラムを中間言語に変換しています。
- プロセス2. CG生成と共有データの特定
生成したJimpleコードからCGを生成します。CGはJavaであればクラス内部またはクラス間のメソッド呼出関係をグラフ構造データとして表現したものです。CGから複数の処理から操作されるデータ(変数)を抽出します。図4に実際のCB-IDAU法の研究においてサンプルコードとして用いた複数の処理から操作されるデータ(変数)を持つプログラムのUML図を記載します。SharedVarXクラスと、SharedVarYクラスが持つデータ(変数)が、CallerFromAクラスとCallerFromBクラスの複数の処理から呼び出されているテスト対象のサンプルプログラムになっています。
実際には図5と図6に示すCGを作成して、メソッド間の呼出関係に着目したグラフデータを抽出して解析することで、対象となるデータ(変数)と操作(メソッド)を抽出します。
- プロセス3. CFG生成とCRUD属性情報の付与
生成したJimpleコードから共有されるデータ(変数)に対して操作を行なっているメソッドに対して、CFGを作成します。CFGはメソッド内部のソースコードの呼出関係をグラフ構造データとして表現しています。さらに、CFGの各ノードに対してCRUD情報を属性情報として付与します。図7に図4で示したプログラム内で、データ(変数)のDelete操作を行なっているメソッドのCFGを示します。
- プロセス4. CFG経路の探索
生成したCFGの始点から終点に至るまでの経路探索を行います。探索アルゴリズムの実装としては基本的な幅優先探索を用いています。経路探索の計算量を削減する工夫としては、これまでの説明で触れた通り「CFGは共有されるデータを操作するメソッドに絞り込んで生成」「CRUDマトリクスを抽出ルールとして利用」が該当します。図8にテスト対象全体のコードのCG, CFGとデータ(変数)の経路を探索するイメージ図を示します.
図8では３つの機能実装メソッドである、{fai, fbj, fbk}が、データDxに対して操作を行う経路として存在しています。３つの操作のうち、Readはテストケース抽出の順序組合の対象とはならないことがIDAU法のテスト抽出定義から既知であるため、fbjは解析対象から除外します。赤色のエッジとノードを持つ残り２つのメソッドのCFGに対して、パス探索を行います。各CFGには２つの経路があるため、合計４個のパスが探索により抽出され、そのうち２つの経路がデータDxに対してDelete, Createの処理を行なっていることが抽出されます。この探索プロセスを全てのCFGに対して大規模に実施することにより、テスト対象とするソフトウェア全体のIDAU法を適用するために必要なCRUD情報を抽出します。
- プロセス5. テストケース抽出
上図8の例では、２つの赤色の部分グラフが、Delete -> Createの順番でデータDxに操作を行う可能性が抽出できています。この組合せを図右側のIDAUが定める拡張CRUD図のテストケース抽出条件と照らし合わせると、赤丸で示したようにテストケースの抽出条件に該当するため、このCRUD操作を行うソースコードの実行経路の組み合わせをテストケースとして抽出することが出来ます。このプロセスを、図4で示したサンプルプログラムに適用すると、図7のCFGが持つ経路の内、図9で示す経路がテストケース対象の経路の一つであることが抽出できます。
このように、経路探索した多くの経路をCRUDマトリクスのルールに沿って抽出することでIDAUのカバレッジ基準を満たすテストケースをもれなく抽出できます。
CB-IDAU法の検証実験
CB-IDAU法の研究では、前述のテストプロセスとサンプルプログラムを用いて、ソースコードのJimple変換からテストケース抽出に至るまでのCB-IDAU法のためのテストツールをJavaで実装しています。本章では、このCB-IDAU法を実装したツールを使って、実際に存在するオープンソースソフトウェアのソースコードに対して、CB-IDAU法の有効性を検証実験した内容を説明します。
- テスト対象
テスト対象としてJavaフレームワークのオープンソースである、TomcatとTerasolunaのJavaソースコードを検証実験の対象としました。各Step数、メソッド数、フィールド数は以下になります。実際にCB-IDAU実装ツールでテストケースを抽出するまでに要した時間もExecution Time(Hour)として記載します。プログラム実行に用いた計算機ハードウェア環境は以下の条件のものを利用しました。グラフの探索処理を実行する必要があるため、ある程度スペックの高い計算機環境と長時間計算が必要になります。
– CPU: Intel Core i9-9900K @ 3.60 GHz, 8 cores, 16 threads
– Memory: 65,779,516 kB
– OS: Ubuntu 18.04Ubuntu 18.04.4 LTS
– Disk: 2.5 Tbyte SSD
表1 テスト対象ソースコードの内訳
CB-IDAU法の検証では、パス網羅テスト(C1)を比較対象として用いました。表1に示す２つのテスト対象ソースコードに対して、C1テストとCB-IDAU法を適用した結果得られたCFGの経路数を以下の表2に示します。
- 実行結果
表2 抽出CFG経路数
CFGのパス数をテストケース数と置き換えると、全網羅テストするのに必要なテストケースから、Tomcat, Terasolunaのどちらの例も、おおよそ半分のテストケース数にまでCB-IDAU法により絞り込む事が可能である事が分かりました。
まとめ
今回は、IDAU法をソースコードレベルのテストに適用した、CB-IDAU法について説明しました。CB-IDAU法によりテスケースの効率的な抽出が可能である事が分かりました。しかし、表1のExecution Time(計算時間)に示した通り、CB-IDAU法を用いてテストケースを抽出したTomcatの例では、104時間もの計算時間が必要である等、まだ多くの課題があることも分かりました。
CB-IDAU法では、ソースコードにIDAU法を適用するために、CG、CFG、グラフ探索処理のように数学的グラフデータ構造に基づいたモデル化と処理が必要となり、それらを実装してきました。次回の連載では、これら生成したグラフデータを活用した副次的な応用研究の一つとして、数学的なグラフ特徴量を応用したソフトウェアバグ予測を行うテスト手法の説明を行います。
第1回：バージョンアップ開発や派生開発のときの影響範囲をテストしていますか？
第2回：バージョンアップ開発や派生開発のときの影響範囲をテストしていますか？
第3回：バージョンアップ開発や派生開発のときの影響範囲をテストしていますか？
第4回：バージョンアップ開発や派生開発のときの影響範囲をテストしていますか？
