Combinatorial state transition testing for embedded systems.
High test coverage achieved quickly!
Combinatorial state transition tests are recommended in many standards for safety-critical systems. However, they are an excellent method for all embedded systems to achieve high test coverage quickly and in a structured way.
Methods for deriving test cases
The best known methods for deriving test cases are equivalence classes and boundary value analysis. Typically, they are used in unit tests in conjunction with code coverage measurements (C0, C1, …) to check the completeness of the tests. However, asynchronous, concurrent components, as used in embedded systems, can only be tested very poorly with synchronous, sequential unit tests. These test methods are also hardly suitable for integration or system tests based on hardware or software in the loop.
Combinatorial state transition tests are less widely used. However, they offer excellent possibilities to test complex, concurrent software with high coverage. One is able to define a path coverage for the state space of the application under test (n-switch). The test cases required for this can be derived or generated manually. By using the method appropriately, even tests for data combinatorics (n-wise) can be performed.
The methodology of combinatorial state transition tests with path coverage
Combinatorial state transition tests as black box tests first define all externally accessible states of the system under test (SUT) in a state transition diagram. Transitions describe all state transitions between system states. Each path from the initial state (initial) to the final state (end) is a possible test path and thus a possible test case. To achieve complete transition and state coverage (0-switch), the paths of all generated test cases together must have passed through each transition at least once.
Higher coverages define the combination of consecutive transitions:
- 0-switch: each transition has been traversed at least 1 time. This coverage contains the complete coverage of the states.
- 1-switch: All combinations of two consecutive transitions.
- n-switch: All combinations of n+1 consecutive transitions.
Due to the high path coverage, the tests can detect many problems. An example of this are sporadically occurring race conditions. These are difficult to detect with most other methods.
The figure shows a simplified state transition test for an ATM. The colored arrows represent different execution paths and thus test cases for the state transition test. To achieve complete transition and state coverage (coverage n-switch=0), 7 test cases are required here. For higher coverage, significantly more test cases must be generated.
Data Combinatorics
Combinatorial state transition tests are also good for testing data combinatorics. In the example, all combinations of two parameters with three values each are tested against each other. This corresponds to the pairwise test. Combinations of more parameters (n-wise) can also be generated easily. The necessary values of the individual parameters can be derived well with equivalence classes and limit analysis.
Combining and generating data and path coverage.
One can also combine the coverage of data and paths well. Thus, in the example, all flow paths (n-switch) are tested for all combinations of 3 parameters (n-wise).
Since the large number of necessary test cases can hardly be developed manually, the use of suitable tools with test case generators is recommended for larger coverages.
Analysis and documentation
Different views can be used to analyze, understand and document the generated test cases.
- Execution trees provide an overview of all generated test paths and their different sequences.
- Sequence diagrams represent in great detail individual test sequences and their interaction with the System under Test (SUT). A target/actual comparison of the sequences enables quick analysis and isolation of error causes.
Execution tree and sequence diagram for test cases
Conclusion
State transition tests are a structured method for developing tests for concurrent embedded systems.
State transition tests enable the development of combinatorial test cases for high path and data coverages.
Low coverages can be developed manually. For higher coverages, the use of tools is recommended.
