Classification Tree Method

The Classification Tree Method is a method for test design, as it is used in different areas of software development (e.g. embedded systems …). It has been developed by Grimm and Grochtmann in 1993^[1] . Classification Trees in terms of the Classification Tree Method must not be confused with decision trees.

The classification tree method consists of two mayor steps:

1. Identification of test relevant aspects (so called classifications) and their corresponding values (called classes) as well as
2. Combination of different classes from all classifications into test cases.

The identification of test relevant aspects usually follows the (functional) specification (e.g. requirements, uses cases …) of the system under test. These aspects form the input and output data space of the test object.

The second step of test design then follows the principles of combinatorial test design.

While the method can be applied using a pen and a paper, the usual way involves the usage of the Classification Tree Editor, a software tool implmenting the classification tree method.

Background

The classification tree method (CTM) introduced the following advantages over the Category Partion Method^[2] (CPM) by Olstrad and Balcer:

• Notation: CPM only had a textual notation, whereas CTM uses a graphical, tree-shaped representation.
• Refinements Selecting one representative might have an influence on the occurrence of other representatives.

CPM only offers restrictions to handle this scenario.

CTM allows modeling of hierarchical refinements in the classification tree, also called implicit dependencies.

• Tool support: The tool presented by Ostrand and Balcer only supported test case generation, but not the partitioning itself.

Grochtmann and Wegener presented their tool, the Classification Tree Editor (CTE) which supports both partitioning as well as test case generation.^[3]

Application

Prerequisites for applying the CTM is the selection (or definition) of a system under test. The CTM is a black-box testing method and supports any type of system under test. This includes (but is not limited to) hardware systems, integrated hardware-software systems, plain software systems, including embedded software, user interfaces, operating systems, parsers, and others (or subsystems of mentioned systems).

With a selected system under test, the first step of the classification tree method is the identification of test relevant aspects. Any system under test can be described by a set of classifications, holding both input and output parameters. (Input paramters can also include environments states, pre-conditions and other, rather uncommon parameters). Each classification can have any number of disjoint classes, describing the occurrence of the parameter. The selection of classes typically followes the principle of equivalence partitioning for abstract test cases and boundary-value analysis for concrete test cases. All classifications together form the classification tree. For semantic purpose, classifications can be grouped into compositions.

The maximum number of test cases is the Cartesian product of all classes of all classifications in the tree, quickly resulting in large numbers for realistic test problems. The minimum number of test cases is the number of classes in the classification with the most containing classes.

In the seconds step, test cases are composed by selecting exactly one class from every classification of the classification tree. While the selection of test cases originally^[1] was a manual task to be performed by the test engineer, later versions of the classification tree editor include automated all-pairs testing and test prioritization.

Example

For a database system, test design has to be performed. Applying the first the classification tree method, the identification of test relevant aspects gives the classifications: User Privilege, Operation and Access Method. For the User Privileges, two classes can be identified: Regular User and Administrator User. Their are three Operations: Add, Edit and Delete. For the Access Method, again three classes are identified: Native Tool, Web Browser, API. The Web Browser class is further refined with the test aspect Brand, three possible classes are included here: Internet Explorer, Mozilla Firefox, and Apple Safari.

The first step of the classification tree method now is complete. Of course, there are further possible test aspects to include, e.g. access speed of the connection, number of database records present in the database, etc. Using the graphical representaion in terms of a tree, the selected aspects and their corresponding values can quickly be reviewed.

For the statistics, there are 30 possible test cases in total (2 privileges * 3 operations * 5 access methods). For minimum coverage, 5 test cases are sufficient, as there are 5 access methods (and access method is the classification with the highest number of disjoint classes).

In the second step, three test cases have been manually selected:

1. A regular user adds a new data set to the database using the native tool.
2. An administrator user edits an existing data set using the Firefox browser.
3. A regular user deletes a data set from the database using the API.

Enhancements

Classification Tree Method for Embedded Systems

The classification tree method first was intended for the design and specification of abstract test cases. With the classification tree method for embedded systems^[4], test implementation can also be performed. Several addtional features are integrated with the method:

1. In addition to atomic test cases, test sequences containing of several test steps can be specified.
2. A concrete timing (e.g. in Seconds, Minutes ...) can be specified for each test step.
3. Signal transitions (e.g. linear, spline, sine ...) between selected classes of different test steps can be specified.
4. A distinction between event and state can be modelled, represented by different visual marks in a test.

The module and unit testing tool Tessy relies on this extention.

Dependency Rules and Automated Test Case Generation

One way of modelling constraints is using the refinement mechanism in the classification tree method. This, however, does not allow for modelling constraints between classes of different classifications. Lehmann and Wegener introduced Dependency Rules with their incarnation of the CTE.^[5]

Advantages

Disadvantages

References

1. Grochtmann, Matthias (1993). "Classification Trees for Partition Testing". Software Testing, Verification & Reliability. 3 (2): 63–82. doi:10.1002/stvr.4370030203. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
2. Ostrand, T. J. (1988). "The category-partition method for specifying and generating fuctional tests". Communications of the ACM. 31 (6): 676–686. doi:10.1145/62959.62964. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
3. Grochtmann, Matthias (1995). "Test Case Design Using Classification Trees and the Classification-Tree Editor CTE". Proceedings of the 8th International Software Quality Week(QW '95), San Francisco, USA. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
4. Conrad, Mirko (1 October 2006). "An Extension of the Classification-Tree Method for Embedded Systems for the Description of Events". Electronic Notes in Theoretical Computer Science. 164 (4): 3–11. doi:10.1016/j.entcs.2006.09.002. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
5. Lehmann, Eckard (2000). "Test Case Design by Means of the CTE XL" (PDF). Proceedings of the 8th European International Conference on Software Testing, Analysis & Review (EuroSTAR 2000). {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)