この記事は圧倒的令和ッ！！ぴょこりんクラスタ Advent Calendar 2019のために書いたものです。ちなみにこのAdvent Calendarが何なのかについては、主催者による紹介記事を見てください。

この記事について

何を思ったかソフトウェアテストについてちょこっと調べたので、その結果をまとめる。

はじめに

ソフトウェアテストは、趣味でコード書いていたりするとあまり関わらない分野であると思う。自分の場合、過去に家計簿システムを作ったが、そこでも特にテストらしいテストは書かず、つど適当にデバッグして終えた。

しかし、テストを書かなくていいのは趣味の範囲までである。ソフトウェアを製品として送り出す場合、品質を保証するという観点からテストは欠かせない。品質が特に重要な場合、ISOのような標準規格でどのようなテストをしなければならないかを定められていることも有る。例えば、自動車機能安全規格ISO26262では、ユニットテストにおいて、C0カバレッジ、C1カバレッジ、 MC/DCを100%達成する必要がある*1。自動車ほど頑張らないかもしれないが、それでも似たような基準を満たす必要があるところは多いだろう。ちなみに、C0カバレッジ、C1カバレッジ、MC/DCの意味は以下の通り。

C0カバレッジ: 全ての命令、つまり、全てのソースコードの行のうち、少なくとも1回実行されたものの割合。
C1カバレッジ: それぞれの判定における、それぞれの条件で、全て可能な結果を少なくとも1回は取ったものの割合。
MC/DC(Model Condition Decision Coverage): 以下を満たす*2ものの割合。
- プログラムの全入口／出口を少なくとも1回はテストすること
- プログラムの判定に含まれる全条件は可能な値を少なくとも1回はテストすること
- プログラムの全判定は可能値を少なくとも1回はテストすること
- プログラムの判定の全条件は判定の出力に独立して影響することを示すこと

これらの基準を満たすようなユニットテストを人間の手で書くのは大変である。極端な例だが、以前少し話題になったこのソースコードを見てみれば、上記の条件を満たすことが結構大変かもしれないと感じられるかも知れない。要は、条件分岐が多いような複雑なソースコードの場合、そもそも人手でユニットテストを書くというのは重労働だ。ユニットテストですら重労働、いわんや結合テスト(関数単体でなく、必要に応じて関数を結合してテストを行うこと)、統合テスト(システムとしてテストをすること)をや、というのは想像に難くない。重労働なんて定性的なことを言っても仕方ないので数字を出すと、ソフトウェア開発データ白書2018-2019によれば、ソフトウェア開発にかかるコストのうち、だいたい4割超がテスト(結合テストと統合テスト。ユニットテストは分類にないので、設計工程に含まれている？) に割かれている。半分くらいテストしているというわけだ。

今回は、こんな大変なテストで楽をするための技術について調べた結果をざっとまとめる。

ソフトウェアテスト技術の分類*3

ソフトウェアテストと一口に言っても、目的は様々である。ユニットテストはその部品が期待通り動作するか、結合テストはあるユニットが他のユニットと連動した際に期待通り動作するか、統合テストは、ユニットをシステムとして組み上げたときに、期待通りの動作ができるか、など。他にも、実際に意図通りに動作するかを顧客にテストしてもらう受け入れテストや、期待通りの性能が出せるかの性能テストなんてのもある。偉大な先達は、これらの共通点を"observing a sample of executions"と表現し、以下のとおり4W2Hで整理してくれた*4。

WHY: なぜやるのか？バグを見つけるためなのか、リリース判定するためなのか、はたまたUIのユーザビリティを見るものか？この観点は、テストオラクル(多少不正確かも知れないがテストの期待値と言い換えてもよいはず)の生成技術に関わるもの。
HOW: どのサンプルを観察するのか、また、そのサンプルはどうやって選ぶのか？この観点は、テストの入力をどうするか、どうやってテストをするのか、いくつかあるテストのうち何を選択するか、の技術に関わるもの。
HOW MUCH: サンプルをどれくらい取ればよいか、また、得たサンプルのうちどれくらい採用すればよいか？この観点は、テストの選択、停止ルール、十分性評価の技術に関わるもの。一般には、カバレージ分析や信頼性測定がよく使われる手法。
WHAT: 何を実行するか？一部に注目して実行するか、または全体を通して実行するか？この観点は、テストの粒度を決める技術や、大きなシステムをテストできるようにするスタブなどのテスト支援技術に関わるもの。
WHERE: どこで実行するか？開発現場か、シミュレーション環境か、はたまた実環境か？何を実行するかとも関係がある観点。この観点は、組み込みソフトウェアのテストに特に関わる。
WHEN: プロダクト・ライフサイクルのどこでやるか？一般には早く実施するほど、問題への対策が低コストで済むと言われているが、実環境でなければわからないこともある。

今回は、HOWの観点のうち、特にテスト自動化技術に着目する(というか調査したのがここというだけで、他が重要でないというわけではない)。

テスト自動化技術について

テスト自動化技術は、さらに以下の3つに分類できる。

テスト実行・結果確認の自動化
テスト環境構築の自動化
テスト入力生成の自動化

御存知の通り、完全なるテスト自動化は未だ達成できていない。しかし、ユニットテストに関しては技術開発が進んできており、一般に使えるツールもそれなりにある。例えば、テスト環境構築の一部*5とテスト実行・結果確認を支援してくれるツールとして、 xUnitフレームワークや、 Google Testが挙げられるだろう。

テスト入力生成の自動化はというと、こちらは現在も活発に研究がなされている。テスト入力生成には3つのアプローチがある。

ランダムベースのアプローチ: ランダムに入力を作るアプローチ。DART *6と呼ばれる技術が有名。DARTでは、関数のインタフェースを静的解析技術で抽出し、ランダムに生成したテストケースを入力して自動でテストを行う技術である。
モデルベースのアプローチ: ソフトウェアの振る舞いモデルや、仕様の形式記述をベースにテストを生成する技術*7。このアプローチでは、シンボリック実行と呼ばれる技術が有名。シンボリック実行は、ソースコードを静的解析して実行パスを抽出し、各パスを通すにはどのような入力を与えればよいかを SATソルバを用いて求めることで、テスト入力を生成する*8。シンボリック実行では、実際にソフトウェアは実行されず、あくまで形式的に検証する。網羅性という観点では大変効果的な手法であるが、経路数の爆発等で実適用への大きな壁がある。経路数の爆発を抑えるため、一部の入力をランダムベースのアプローチで生成するコンコリックテスト(シンボリック実行に、一部具体的な値を用いて実際にプログラムを動作させる)と呼ばれる技術の研究が行われている。シンボリック実行の他にも、有界モデル検査(モデルの状態遷移を一定範囲に抑えて検査する技術)を利用してテスト生成する技術もある*9。
サーチベースドソフトウェアテスティング: 何らかの評価関数(例えば、C1カバレージ)を予め定義し、それがよくなる方向に入力を生成する技術。入力生成には、遺伝的アルゴリズムのようなメタヒューリスティクス *10を応用している。

今回調べたのはサーチベースドソフトウェアテスティングのため、以降はこれについて述べる。

サーチベースドソフトウェアテスティングの現在

サーチベースドソフトウェアテスティング(長いのでSBSTと略す)の実装のうち、最も有名なツールの1つはEvoSuiteと言えるだろう。 EvoSuiteは、Java向けのユニットテストを生成してくれるツールであり、コンペでよい成績*11を残している優秀なツールである。 EvoSuiteはチュートリアルも充実しているため、Javaほぼ初心者の自分でも、チュートリアルを1から順にやっていくだけで簡単にユニットテストが自動生成できる(なので、この記事中で使い方に関するものは記載しない)。

EvoSuiteは優秀であり、ソフトウェアテストを作成するための作業時間を短縮できるという結果も示されているが*12、 EvoSuiteが苦手とすること、改善すべきこともまだまだたくさんある。いくつかを抜粋したものを以下に箇条書きで示し、関連しそうな最近の研究についても軽く述べる。

評価関数の最適化方法の改善
マルチスレッドのような並列動作プログラムのテスト生成
現実のバグを見つけること

評価関数の最適化方法の改善

SBSTは、すごくざっくり言えば、評価関数の出力をよくするように入力を調整する技術だと言うことができる。 Generating Test Input with Deep Reinforcement Learningでは、その最適化に強化学習を応用したものが報告されている。ただ、現時点ではものすごく効果が出たというわけではなく、定式化をして簡単な評価をするにとどまっている様子。

マルチスレッドプログラム向けのテスト生成

マルチスレッドプログラムは、当然ながらシングルスレッドプログラムよりも設計・テスト作成が難しいので、マルチスレッドプログラム向けのテスト入力生成技術も研究されている。 Effectiveness and Challenges in Generating Concurrent Tests for Thread-Safe Classesでは、世の中にある並列動作プログラム向けのテスト入力生成ツールについて、現実のバグを見つけられるかどうかを評価した論文である*13。論文で評価した技術を以下に箇条書きでまとめる。並行動作するプログラムの動作パターン数の爆発をどう抑えるかというところでみんな苦労している。

評価対象の分類とツール名
- random based techniques：ランダムな関数コールシーケンスと入力を生成し、テストするアプローチ。テストオラクルには、linearizability*14を利用。難しい解析をせずに入力が作れるところが利点。欠点は、ランダムに入力生成するので、狙ってケースを作成できない点である。
  - BALLERINA(ICSE 2012): 計算量を減らすために、同時に動作するスレッドは2つだけ、かつ、スレッド間で共有するオブジェクトは1つだけ、という仮定を置いてモデル化。さらにテストオラクルをクラスタリングし、判定にかかる計算量を減らした。
  - CONTEGE(PLDI 2012): 基本的にはBALLERINAと同じだが、こちらはlinearizabilityをうまく判定する機構を作った様子。BALLERINAよりもfalse alarmを減らした。
- coverage based techniques: ランダムに生成していると冗長なパターンが増えて効率が悪いので、重複しないように、つまり、スレッド間のインターリービングパターンのカバレージを増やすようにテストケースを生成するもの。なお、このインターリービングカバレージの計算の効率化が技術課題。そもそもカバレージ計算が難しく、考慮しなければいけない事項が落ちがちというのが悩みどころ。
  - consuite(ICST 2013): EvoSuiteを拡張し、並行テストの生成をできるようにしたもの。カバレージとして満たすべきところを統計的に算出し*15、テスト対象を絞るもの。共有メモリのコンテキストを考慮しないため、特定のケースのエラーしか報告できない。また、共有メモリへのアクセス順序が保証できない。
  - AutoConTest(ICSE 2016): consuiteの改善。共有メモリのコンテキストを意識したインターリービングカバレージ計算ができるようになった。
  - covcon(ICSE 2017): 並行実施されるメソッドペア集合の頻度情報を収集。特に頻度の低いものについてテストを生成することで高速化。
- sequential-test-based techniques: 検出するバグの種別を絞ることで計算量を減らすアプローチ。並列動作を並列動作のままモデル化するのではなく、直列化*16をしているので、モデル化としては不十分というところがつらい点。また、こういうモデル化をしたとしても、計算は相変わらず大変である。
  - OMEN: deadlock検出
  - NARADA: データ競合
  - INTRUDER: atomicity違反
  - MINION: assertion違反

評価の結果、上記のどれか1つでもバグを検出できた件数は、8件/47件であった。原因分析の結果は以下の通りで、なかなか厳しい。

原因1: 現実と仮定が合っていない。いずれも2つのメソッド、1つの共有オブジェクトという仮定をおいているが、現実と離れている。
原因2: 環境依存。DB接続とか、固有のファイルが必要とかでバグが再現しない。concurrentな環境だと mockがうまく使えなかったりするらしい。
原因3: wait-notify機構に未対応

現実のバグを見つけることについて

マルチスレッドプログラムのバグを見つけるのが難しいことはわかったが、シングルスレッドプログラムではどうか？そんな疑問に答えてくれるのがUsing Search-Based Test Generation to Discover Real Faults in Guavaである。この論文では、EvoSuiteを用いて、Google作のJavaライブラリであるGuava*17のリアルバグを検出できるかどうかを評価した。結果、3件/9件のバグを検出できた。検出できなかった原因の分析は以下の通り。

入力に特殊な値が求められるもの(論文中の例: 1文字の文字列に対して、マッチしない正規表現パターンを適用してsplitしようとすると、空文字列が返ってくる)
特定のデータ型でのみバグが発現するもの
複雑なクラスのインスタンスが入力として与えられるもの
特定のメソッドコール列が必要なもの(論文中の例: 優先度付きキューに対し、add/removeを繰り返していると、正しいものがremoveできなくなる)

試しに、"1文字の文字列に対して～"の例を見てみたが、人間がソースコードを見ても理解するのが大変であった。そもそも、何が特殊かを判断する基準をどう定義するかが難しい問題であり、これを見つけるのは難しいだろうなあ・・・