Classification Tree Method


The Classification Tree Method is a method for test design, as it is used in different areas of software development.
It was developed by Grimm and Grochtmann in 1993.
Classification Trees in terms of the Classification Tree Method must not be confused with decision trees.
The classification tree method consists of two major steps:
  1. Identification of test relevant aspects and their corresponding values as well as
  2. Combination of different classes from all classifications into test cases.
The identification of test relevant aspects usually follows the specification 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 implementing the classification tree method.

Application

Prerequisites for applying the classification tree method is the selection of a system under test.
The CTM is a black-box testing method and supports any type of system under test. This includes hardware systems, integrated hardware-software systems, plain software systems, including embedded software, user interfaces, operating systems, parsers, and others.
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.
.
Each classification can have any number of disjoint classes, describing the occurrence of the parameter.
The selection of classes typically follows the principle of equivalence partitioning for abstract test cases and boundary-value analysis for concrete test cases.
Together, all classifications 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 second step, test cases are composed by selecting exactly one class from every classification of the classification tree.
The selection of test cases originally was a manual task to be performed by the test engineer.

Example

For a database system, test design has to be performed.
Applying 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.
There 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 representation 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. For minimum coverage, 5 test cases are sufficient, as there are 5 access methods.
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

Background

The CTM introduced the following advantages over the Category Partition Method by Ostrand and Balcer:

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, test implementation can also be performed. Several additional features are integrated with the method:
  1. In addition to atomic test cases, test sequences containing several test steps can be specified.
  2. A concrete timing can be specified for each test step.
  3. Signal transitions 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 extension.

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 based on Boolean expressions with their incarnation of the CTE. Further features include the automated generation of test suites using combinatorial test design.

Prioritized Test Case Generation

Recent enhancements to the classification tree method include the prioritized test case generation: It is possible to assign weights to the elements of the classification tree in terms of occurrence and error probability or risk. These weights are then used during test case generation to prioritize test cases. Statistical testing is also available by interpreting the element weights as a discrete probability distribution.

Test Sequence Generation

With the addition of valid transitions between individual classes of a classification, classifications can be interpreted as a state machine, and therefore the whole classification tree as a Statechart. This defines an allowed order of class usages in test steps and allows to automatically create test sequences. Different coverage levels are available, such as state coverage, transitions coverage and coverage of state pairs and transition pairs.

Numerical Constraints

In addition to Boolean dependency rules referring to classes of the classification tree, Numerical Constraints allow to specify formulas with classifications as variables, which will evaluate to the selected class in a test case.

Classification Tree Editor

The Classification Tree Editor is a software tool for test design that implements the classification tree method.
Over the time, several editions of the CTE tool have appeared, written in several programming languages and developed by several companies.

CTE 1

The original version of CTE was developed at Daimler-Benz Industrial Research facilities in Berlin.
It appeared in 1993 and was written in Pascal. It was only available on Unix systems.

CTE 2

In 1997 a major re-implementation was performed, leading to CTE 2. Development again was at Daimler-Benz Industrial Research. It was written in C and available for win32 systems.
CTE 2 was later licensed to Razorcat for inclusion with the module and unit testing tool Tessy.
The classification tree editor for embedded systems also based upon this edition.

CTE XL

In 2000, Lehmann and Wegener introduced Dependency Rules with their incarnation of the CTE, the CTE XL. Further features include the automated generation of test suites using combinatorial test design.
Development was performed by DaimlerChrysler. CTE XL was written in Java and was supported on win32 systems.
CTE XL was available for download free of charge.
In 2008, Berner&Mattner acquired all rights on CTE XL and continued development till CTE XL 1.9.4.

CTE XL Professional

Starting in 2010, CTE XL Professional was developed by Berner&Mattner. A complete re-implementation was done, again using Java but this time Eclipse-based. CTE XL Professional was available on win32 and win64 systems.
New developments included:
In 2014, Berner&Mattner started releasing its classification tree editor under the brand name .
A is still available for download free of charge, however, with reduced functionality.

Versions

VersionDateCommentWritten inOS
CTE 1.01993Original Version, limited to 1000 test cases PascalUnix
CTE 2.01998Windows Version, unlimited number of test casesCUnix, win32
CTE XL 1.02000Dependency Rules, Test Case GenerationJavawin32
CTE XL 1.62006Last Version by Daimler-BenzJavawin32
CTE XL 1.82008Development by Berner&MattnerJavawin32
CTE XL 1.92009Last Java-only VersionJavawin32
CTE XL Professional 2.12011-02-21First Eclipse-based Version, Prioritized Test Case Generation, Deterministic Test Case Generation, Requirements-Tracing with DOORSJava 6, Eclipse 3.5win32
CTE XL Professional 2.32011-08-02QualityCenter integration, Requirements Coverage Analysis and Traceability Matrix, APIJava 6, Eclipse 3.6win32
CTE XL Professional 2.52011-11-11Test Result Anotation, MindMap importJava 6, Eclipse 3.6win32, win64
CTE XL Professional 2.72012-01-30Bug fix releaseJava 6, Eclipse 3.6win32, win64
CTE XL Professional 2.92012-06-08Implicit Mark Mode, Default classes, Command Line InterfaceJava 6, Eclipse 3.7win32, win64
CTE XL Professional 3.12012-10-19Test Post-Evaluation, Test Sequence Generation, Numerical ConstraintsJava 6, Eclipse 3.7win32, win64
CTE XL Professional 3.32013-05-28Test Coverage Analysis, Variant Management, Equivalence Class TestingJava 6, Eclipse 3.7win32, win64
CTE XL Professional 3.52013-12-18Boundary Value Analysis Wizard, Import of AUTOSAR and MATLAB modelsJava 7, Eclipse 3.8win32, win64
TESTONA 4.12014-09-22Bug fix releaseJava 7, Eclipse 3.8win32, win64
TESTONA 4.32015-07-08Generation of Executable Test Scripts, Import of Test ResultsJava 7, Eclipse 3.8win32, win64
TESTONA 4.52016-01-21Enhanced Export Facilities, GUI ImprovementsJava 7, Eclipse 3.8win32, win64
TESTONA 5.12016-07-19Bug fix release, Switch to Java 8, Eclipse 4.5Java 8, Eclipse 4.5win32, win64

Advantages