「制約」の実装。

「制約」機能実装のために、"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があるといいのだが、、、。