JCUnitのリファイン(0.3.0)リリース

JCUnitの設計をリファインし、機能を根本的なものに限った0.3.0をリリースした。
今回は「制約」を取り扱うための機能を実装した。
また、Annotationの役割・用語を整理した。
MavenのCoordinateは以下のとおり。

<dependency>
<groupId>com.github.dakusui</groupId>
<artifactId>jcunit</artifactId>
<version>[0.3.0,]</version>
</dependency>

以前のバージョンとの互換性は無いので注意して欲しい。
詳しくはREADME.mdに書いてあるので読んでみてほしい。

https://github.com/dakusui/jcunit/blob/develop/README.md(英語)

内部の設計を見直した結果、ロジックが首尾一貫した結果、生成するテスト件数を最適化することができたようだ。

benchmark1_3$4 :(testcases, remainders, time(sec))=( 9, 0, 0.000000)
benchmark2_3$13 :(testcases, remainders, time(sec))=( 20, 0, 0.028000)
benchmark3_4$15_3$17_2$20 :(testcases, remainders, time(sec))=( 43, 0, 4.591000)
benchmark4_4$1_3$30_2$35 :(testcases, remainders, time(sec))=( 29, 0, 7.428000)
benchmark5_2$100 :(testcases, remainders, time(sec))=( 18, 0, 23.120000)
benchmark6_10$20 :(testcases, remainders, time(sec))=( 248, 0, 2.870000)

以前(http://jcunit.hatenablog.jp/entries/2014/03/15)の生成結果と比較すると、(3)を除いてすべての項目で生成テスト件数の改善が見られる。
一方、処理時間は長くなっている。これは設計の改善によってオブジェクトの生成が増えたことによるのだろう（整数で識別していた因子をオブジェクトで表現したりなど）。とはいえ、実用の範囲と言えるかな。経験が不足しているので確かなことは言えないが。

「制約」の実装。

「制約」機能実装のために、"Combinatorial TestCases with Constraints"*1と"Constructing Interaction Test Suites for Highly-Configurable Systems in the Presence of Constraints: A Greedy Approach"*2から辿って"Interaction Testing of Highly-Configurable Systems in the Presence of Constraints"*3を読む。

そして以下の言及を発見。

Asking if a configuration exists satisfying a set of constraints is NP-Hard. *4

いっそNP困難と分かっているのなら、むしろアプローチの仕方がすっきりするというものだ。
が、問題の文献*4"Prioritized interaction testing for pair-wise coverage with seeding and constraints"は19.95USD。たけえ。

*1:http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6221818

*2:http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=4564473&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D4564473

*3:http://cse.unl.edu/~myra/papers/issta71-cohen.pdf

*4:http://www.sciencedirect.com/science/article/pii/S0950584906000401

JCUnitに必要なもの。

この三連休は、文献[1][2]を読んだりのんびり散歩していたりしたのだが、PICTの完成度をまずは目指さないとなとの思いを新たにした。
PICTに比較してJCUnitに欠けているものはおおよそ以下の機能だろう。

1. 「制約(constraints)」機能
2. 因子の階層
3. Negative testの生成
4. 任意強度でのテスト生成

思うに、重要度もこの順。
因子の階層（パラメタを入れ子にする機能。単体テストの範囲ではあまり気にしなくていいかもしれない）とNegativeテスト（異常系用のテスト生成。でも現行の機能でもめんどくさいながらもできる）は実装もそれほど難しくなさそう。で、あると非常に便利。しかし、なんといってもConstraintを実装しないと実用的なシーンではかなり辛い。と、思う。

無論、当初から、「制約」「禁則」と呼ばれる概念を全く意識していなかったわけでもない。"RuleSetBuilder"を用いて、テストの実行時に入力値・出力値の妥当性を検査するRuleを定義する仕組みが実装済みだ。

しかし、現状では生成されたテストを実行する際に評価されるのであって、生成されるべきテストを定義づける（制約を破ったテストを作らないようにする）ために使うことはできていない。

まずはここをなんとか完成させよう。ここを乗り越えれば、視界が大きく開けるはずだ。
そして、

1. テスト件数の最適化

という一番楽しい部分に取り組むのだ。

• 参考文献

1. Pairwise Testing in the Real World: Practical Extensions to Test-Case Scenarios, http://msdn.microsoft.com/en-us/library/cc150619.aspx
2. Combinatorial test cases with constraints in software systems, http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6221818

PICTや他のシステムとの比較

PICTというMicrosoftの製品があることをJaSSTで知り合った方から教えていただいた。
PICTについては以下で詳しく述べられているのだが、

http://msdn.microsoft.com/en-us/library/cc150619.aspx

世間で出回っている様々な製品が与えられた条件に対して、何件でAllpairのテストを出力するかを比較する表が掲載されていた。
（実はこれのおかげで、JCUnitが出力するテスト件数がどうも多すぎることも分かり、改良も行った）

私が実装したのはIPOと呼ばれる　All-pair生成アルゴリズムだが、このアルゴリズムには三箇所ほど、実装のやり方によって生成されるテストケースの大きさや、生成に要する時間といったことに影響が生じるポイントがある。
以下の３つだ。

1. 各因子をどういう順番で処理するか？
2. 水平方向にテストケースを拡張するとき、選択すべき水準が複数あるときにどれを選ぶか？
3. 垂直方向にテストケースを拡張するとき、どの水準を選んでも良い時にどれを選ぶか？

ちなみに、このアルゴリズムの詳細については"Foundations of Software Testing: Fundamental Algorithms and Techniques"( Aditya P. Mathur)という本の4.11に詳述されている。

最初の項目、因子の順序については、また改めて報告したい。
今回は、２つ目と３つ目について行った実験について。
今回はこの２つについて、都合３種類の方式を用意した。
選択すべき水準が複数ある・どれを選んでも良い時は以下のうちのどれかを行う。

1. 最初に見つかったものを選ぶ。(Naive)
2. Tripleをもっとも多く網羅するものを選ぶ。(Greedy)
3. どれでもいいものの中で偏りがでないように、呼び出しごとにカウンタをインクリメントし、可能な候補の数で割った余りを用いて選ぶ。(Modulo)

これらのそれぞれと他システムとの比較も合わせて示した表が以下だ。

#	Task	JCUnit(Naive)	JCUnit(Greedy)	JCUnit(Modulo)	AETG	PairTest	TConfig	CTS	Jenny	DDA	AllPairs	PICT
1	3^4	9	9	9	9	9	9	9	11	?	9	9
2	3^13	27	22	25	15	17	15	15	18	18	17	18
3	4^15 3^17 2^20	73	39	41	41	34	40	39	38	35	34	37
4	4^1 3^30 2^35	52	31	31	28	26	30	29	28	27	26	27
5	2^100	22	20	18	10	15	14	10	16	15	14	15
6	10^20	286	255	273	180	212	231	210	193	201	197	210

Naiveはいささか、他システムに比べテストケースが多い。Greedyは他システムに対してそれほど遜色がない。その一方で、#5では20分近くかかっている。これはたまらん。
「値が偏るから、垂直方向への拡張が増えるんじゃないの？」という単純な疑問を持ったので試してみたModuloが思いの他バランスがよい。

１００件が１０００件になるとさすがに管理が面倒なので辛いのだが、なんとかまあ、許容範囲と言える気もする。

もうちょっといろいろいじってみようっと。

てごろなSUT(Software Under Test)ないかな。

いままで、dog foodingというか、JCUnitの使い勝手を確認するためにthumbnailatorを対象にテストを実装してきた。
これまでの成果は逐次ブログのエントリにまとめて、ここで報告していこうと思う。

が、そろそろ別のプロダクトを対象にテストを書いて、応用例の幅を広げたいと思う。
手頃なSUTがあるといいのだが、、、。

JCUnitの名前の由来

JCUnitの名前の由来

大した話では無いのだけれど、今日はJCUnitの名前の由来など。
数学で使う組み合わせ記号nCkになぞらえて、JUnitで自動的にいろんな組み合わせをテストしてくれるという意味で、JCUnitとつけました。
そんなわけでトップに掲げているロゴでもJとUnitは少し小さいんですね。

ほんとに大したこと無い話でごめんなさい。

いわゆる禁則処理。

「パラメタ不正や禁則に違反する入力を組み合わせ試験に用いると、組み合わせ網羅率の低下につながる。」

というのは、特にHAYST法関連の書籍や研究でよく見かける主張だ。

ここでいう禁則処理とは、句読点や記号を行頭に置かないために行末にぶら下げる処理のことではない。
ある機能への入力として禁じられた値や値の組み合わせのことだ。

たとえば、印刷機能だったら「プリンタ機種Aでは、両面印刷はサポートされていない」だとか計算機だったら「１２ケタ以上の入力は許されていない」だとかだ。

しかし、なんだか妙な話にも聞こえる。
ソフトウェアの機能というものは、入力チェックも含んだものではないのか？間違った入力に対して「そんな入力はダメだ！」というのもそのソフトウェアの機能の一部ではないのか？
だとしたら、HAYST法関連の書籍が言うとおりに、「許容されない」値やその組み合わせをテストから取り除いてしまったら、「入力チェックが正しく行われる」というソフトウェアの重要な特性が全くテストされないことになってしまう。

まあ、組み合わせテストを行う際の暗黙の了解として、「正常な出力を期待するべき組み合わせが正しく動作することを確認するのが目的」と考えるべきだろう。
で、正常な出力を期待するべき組み合わせ自体がおびただしい数にのぼる。
だから、正常な出力を確認できる様々な組み合わせを慎重に選ぶ。これがPairwiseやHAYST法のアプローチ。

ところが、パラメタ異常は一個か二個のパラメタが不正な値を取ることで、本来テストしたい機能本体の論理が全く実行されなくなってしまう。
そのテストケースは異常ではない（＝テストしたい、そのために慎重に選ばれた）パラメタ値も含んでいる。こうした異常ではない、せっかくペア網羅率が上がるように選んだパラメタ値が無駄になってしまうのだ。こうして異常な一個か二個のパラメタのためにペア網羅率が低下してしまうのだ。

より正確に言うなら、ソフトウェア全体としてみれば、ペア網羅率は低下していない。しかし、「本来テストしたいソフトウェア機能本体」に着目するとそれはぐっと低下している。

なので、「禁則違反となるような値や値の組み合わせは可能な限り取り除いてから、組み合わせテストを生成・設計しましょう」というノウハウにたどり着くわけだ。
そしてこれは「入力チェックが正しく行われる」「必要に応じてエラーを返す」という処理は別立てで考えるべきだということでもある。

さてJCUnitではどうしようか？

「禁則違反」を回避するような、テストケース集合を生成する方法を何かしら作る必要がある。
単独のパラメタが禁則違反になる場合なら、そもそもドメインから取り除いておけばよい。２値の組み合わせが禁則を犯す場合には、その組み合わせは予め網羅済みとしておけば良さそうな気がする。（このへん、以前紹介したPairwise生成アルゴリズムの内部に関わるので詳細は省略）
３値以上の組み合わせが禁則を犯す場合にはどうするべきか？レアケースとしてその場合は「已むを得ない」としてもいいような気がするが悩ましいところだ。