Stress Testing of Task Deadlines: A Constraint Programming Approach

Safety-critical Real Time Embedded Systems (RTESs)
are usually subject to strict timing and performance requirements
that must be satisfied for the system to be deemed safe. In this
paper, we use effective search strategies that aim at finding worst
case scenarios with respect to deadline misses. Such scenarios can
in turn be used to test the target RTES and ensure that, even
under worst case conditions, it satisfies its timing requirements.
Specifically, we develop a solution based on Constraint Programming
(CP) to automate the generation of test cases that reveal,
or are likely to, task deadline misses. We evaluate it through
a comparison with a recent, state-of-the-art approach based on
Genetic Algorithms (GA). In particular, we compare CP and GA
in five industry-inspired case studies for efficiency, effectiveness,
and scalability. Our experimental results show that, on the largest
and more complex case studies, CP performs significantly better
than GA. Since CP has interesting properties, such as guaranteeing
complete search when there is sufficient time, and enables the
definition of effective heuristics to converge faster towards optimal
solutions, we conclude that our results are encouraging and suggest
this is an advantageous solution for the stress testing of RTESs with
respect to timing constraints.