Classification Trees in Practice
Applying the classification tree method in practice means handling impossible class combinations, judging the quality of a tree, and using tools that generate combination tables. This page covers the three, plus the pitfalls newcomers meet.
1. Constraints: removing impossible combinations
Real input spaces contain combinations that cannot occur, such as an empty array in which a value occurs twice. Constraints are rules that forbid class combinations; their handling went through three generations:
| Generation | Mechanism | Source |
|---|---|---|
| Textual annotations | [error], [single], [if …] on choices | category-partition [1] |
| Boolean dependency rules | rules between classes, such as “array size 0 ⇒ occurrences none” | CTE XL [2] |
| Numerical constraints | linear expressions such as a + b > c, checked with a SAT solver (a program that decides whether a logical formula can be satisfied) | CTE XL [3] |
Example. For count(array, value), classifications for array size (0, 1, more), occurrences (none, one, more) and order (sorted, unsorted) give 3 × 3 × 2 = 18 combinations. Rules remove the impossible ones: size 0 allows only “none” and has no order (1 combination); size 1 allows only “none” or “one” and counts as sorted (2); size more than 1 keeps all 3 × 2 = 6. The table shrinks from 18 to 9 rows.
A generator meeting a conflict can avoid it, replace a value, merge parameters or split the model. Comparing these over 3,854 generated test suites, Grindal et al. found that avoiding conflicting combinations during generation gave the smallest suites while keeping coverage [4].
2. Measuring the quality of a tree
Chen et al. measure a tree by the share of the combinations it can generate that are legitimate, that is, possible in the real input domain [5]. Duplicated subtrees are the main cause of waste. In their bonus-program example, restructuring the tree raised this effectiveness from 0.17 to 0.40 [6], [7].
3. Tools
The Classification Tree Editor CTE XL added dependency rules and automatic generation of tables by the minimality criterion (every class at least once), the maximality criterion (every permitted combination) and t-wise coverage (every combination of classes from any t classifications; t = 2 is pairwise testing); in some industrial uses its rules cut the theoretically possible test cases by more than 90% [2]. Numerical constraints checked with a SAT solver were added to CTE XL [3]; its successor TESTONA adds a built-in constraint solver, uses the rules as test oracles and generates test scripts [8].
4. Probing questions and novice pitfalls
Classifications are found with probing questions: what are the inputs, what in the environment matters, which values are treated differently, where are the boundaries, and what can go wrong? For count(array, value), “does the array size change the processing?” yields size (0, 1, more), “does order matter?” yields order, and “how often does the value occur?” yields occurrences.
Five pitfalls recur with newcomers. The first and third rest on the only controlled study, in which 104 full-time and 58 part-time students learned CTM in a two-hour lecture and a one-hour workshop [9].
| Pitfall | Sign | Mitigation |
|---|---|---|
| 1. Infeasible combinations | impossible rows; the disadvantage named most often (60% of full-time students) | dependency rules (§1) |
| 2. Missing classifications | an aspect found only after a failure | the probing questions above |
| 3. Subjectivity | two testers build different trees for one specification (named by 25%) | compare trees by effectiveness (§2) [5] |
| 4. Flat trees | every classification at the root; many constraints | group aspects under compositions |
| 5. Skipping boundary values | classes but no class edges tested | add the boundary values as classes |
In the same study, 70% of the full-time students preferred CTM afterwards; the part-time students’ own suites, written before the training, detected on average 55% of the faulty programs. Industrially, an airfield lighting system of about 2,700 C modules was tested with 263 CTM test cases [10].
When to use these tools — and when not
- Use a tool once a tree has more than a handful of classifications: by hand, generation and constraint checks become error-prone.
- Use dependency rules instead of hand-deleting rows, so the reasons stay documented.
- Do not trust a generated table blindly: it is only as good as the tree and the rules.
Limitations
A large tree with many constraints is itself a specification that can be wrong, and nobody tests the tree. Tools come mainly from one group of companies, so independent evaluations are scarce.
How solid is this?
- What is solid. The Yu et al. figures are measured [9], but on students, not professionals; pitfalls 2, 4 and 5 are teaching experience, not measured.
- What is contested. The industrial reports are case descriptions from the method’s developers and tool vendors [10], [2]; the “more than 90%” reduction is relative to all theoretically possible combinations, not to a test suite a tester would actually write.
References
- T. J. Ostrand and M. J. Balcer,“The Category-Partition Method for Specifying and Generating Functional Tests,” in Communications of the ACM, 1988, pp. 676–686. doi: 10.1145/62959.62964.
- E. Lehmann and J. Wegener,“Test Case Design by Means of the CTE XL,” in Proceedings of EuroSTAR 2000, 2000.
- P. M. Kruse, J. Bauer, and J. Wegener,“Numerical Constraints for Combinatorial Interaction Testing,” in Proceedings of ICST 2012, 2012. doi: 10.1109/ICST.2012.170.
- M. Grindal, J. Offutt, and J. Mellin,“Managing Conflicts When Using Combination Strategies to Test Software,” in Proceedings of the 18th Australian Software Engineering Conference (ASWEC), 2007, pp. 255–264. doi: 10.1109/ASWEC.2007.27.
- T. Y. Chen, P. L. Poon, and T. H. Tse,“An Integrated Classification-Tree Methodology for Test Case Generation,” International Journal of Software Engineering and Knowledge Engineering, vol. 10, no. 6, 2000, doi: 10.1142/S0218194000000353.
- T. Y. Chen, P. L. Poon, and T. H. Tse,“A New Restructuring Algorithm for the Classification-Tree Method,” in Proceedings of STEP 1999, 1999. doi: 10.1109/STEP.1999.798484.
- T. Y. Chen, P. L. Poon, and T. H. Tse,“Classification-Tree Restructuring Methodologies: A New Perspective,” IEE Proceedings – Software, vol. 149, no. 2, 2002, doi: 10.1049/IP-SEN:20020335.
- P. M. Kruse,“Test Oracles and Test Script Generation in Combinatorial Testing,” in Proceedings of ICSTW 2016, 2016. doi: 10.1109/ICSTW.2016.11.
- Y. T. Yu, S. P. Ng, P. L. Poon, and T. Y. Chen,“On the Testing Methods Used by Beginning Software Testers,” Information and Software Technology, vol. 46, no. 4, 2004, doi: 10.1016/S0950-5849(03)00198-8.
- M. Grochtmann and K. Grimm,“Classification Trees for Partition Testing,” Software Testing, Verification and Reliability, vol. 3, no. 2, pp. 63–82, 1993, doi: 10.1002/stvr.4370030203.
Disclaimer: AI is used for text summarization, polishing and explaining. Authors have verified all facts and claims. In case of an error, feel free to file an issue.