Search-Based Software Testing
(SBST) is an approach that uses a metaheuristic optimising search technique, e.g. a genetic algorithm (GA), to solve problems in software testing, e.g. to automate a testing task. Search-based approaches have been successfully applied across the spectrum of test case design methods. Problems in the domain of software verification and validation include generating test data, prioritising test cases, minimising test suites, optimising software test oracles, reducing human oracle cost, verifying software models, testing service-orientated architectures, constructing test suites for interaction testing, and validating real-time properties (such as the temporal property), among others.
Search-based temporal testing, in particular, applies an optimisation algorithm to automatically search for test inputs that will produce extreme execution times, e.g. either the longest or the shortest duration. The aim is to discover whether such test inputs can cause the system to violate its temporal requirements.
Worst-Case Execution Time
In many real-time embedded systems, timing issues are crucially important. Producing outputs too early or too late may be fatal to human life, especially in safety-critical systems, such as avionics and automotive systems. The correctness of system function, therefore, depends not only on logical correctness but also on temporal correctness, i.e. the time when the results are produced.
In order to verify the temporal behaviour of real-time systems, timing analysis is typically the principal timing-related safety evidence. In particular, the worst-case execution time (WCET) of each task is generally sought. However, execution times of a task may vary depending on the input data and different behaviour of the environment. More specifically, technical characteristics, such as multicore architectures, as well as the use of parallelism, distribution and fault-tolerant mechanisms, lead to non-deterministic behaviour and consequently complicate the exact determination of the WCET.
My PhD research investigated the application of a variety of search-based techniques for generating sequences of test inputs, which may give rise to extreme behaviour of fundamental mathematical functions running on a non-deterministic environment of a real multicore platform.
Overall, the findings suggest that various forms of search-based approaches are effective in generating test inputs exhibiting extreme execution times on the embedded multicore environment. All previous work in temporal testing has evolved test data directly; this is not essential. In my thesis work, one novel proposed approach, i.e. the use of search to discover high performing biased random sampling regimes (which we call ‘dependent input sampling strategies’), has proved particularly effective. Shifting the target of search from test data itself to strategies proves particularly well-motivated for attaining extreme execution times. Finally, we present also preliminary results on the use of so-called ‘hyper-heuristics’, which can be used to form optimal hybrids of optimisation techniques.
An extensive comparison of direct approaches to establishing a baseline is followed by reports of research into indirect approaches and hyper-heuristics. The shift to strategies from direct data can be thought of as a leap in abstraction level for the underlying temporal test data generation problem. The shift to hyper-heuristics aims to boost the level of optimisation technique abstraction. The former is more fully worked out than the latter and has proved a significant success. For the latter only preliminary results are available; as will be seen from this work as the whole computational requirements for research experimentation are significant.
For further details, the reader is referred to the original article.