Supporting Stress Testing in Real-Time Systems with Constraint Programming

Failures in safety-critical Real-Time Embedded Systems (RTES) could result in catastrophic consequences for the system itself, its users, and the environment. Therefore, these systems are subject to strict performance requirements specifying constraints on real-time properties such as task deadlines, response time and CPU usage. Lately, RTES have been shifting towards multi-threaded application design, highly configurable operating systems, and multi-core architectures for computing platforms. The concurrent nature of their operating environment also entails that the order of external events triggering RTES tasks is often unpredictable. Such complexity in the system architecture, concurrency, and environment renders performance testing increasingly challenging. Specifically, computing input combinations that are intended to violate performance requirements, i.e., stress testing, is one of the preferred ways for verifying RTES performance. These input combinations are referred to as stress test cases, and, upon execution, are predicted to result in worst-case scenarios with respect to a performance requirement. In RTES, stress test cases are usually characterized by sequences of arrival times for aperiodic tasks in the subject system. Generating stress test cases is challenging because it is hard to predict how a particular sequence of arrival times will affect the system performance, and because the set of all arrival times for aperiodic tasks quickly grows as the system size increases. For this reason, search strategies based on Genetic Algorithms (GA) have been used to find stress test cases with high chances of violating performance requirements. For practical use, software testing has to accommodate time and budget constraints. In the context of stress testing, it is essential to investigate the trade-off between the time needed to generate test cases (efficiency), their capability to reveal scenarios that violate performance requirements (effectiveness), and to cover different scenarios where these violations arise (diversity). Even though GA are efficient, and capable of finding diverse solutions, they explore only part of the search space, and their effectiveness depends on configuration parameters. This aspect justifies considering alternative strategies, such as Constraint Programming (CP), that explore the search space completely. Furthermore, to enable effective industrial application, stress testing has to be capable of seamless integration in the development cycle of companies. Therefore, it is both important to capture specific system and contextual properties in a conceptual model, and to map such conceptual model in a standard Model Driven Engineering (MDE) language such as UML/MARTE. In this thesis, we address the challenges above by presenting a practical approach, based on CP, to support performance stress testing in RTES. Specifically, we make the following contributions: (1) a conceptual model, mapped to UML/MARTE, which captures the abstractions required to generate stress test cases, (2) a constraint optimization model to generate such test cases, and (3) a combined GA+CP stress testing strategy that achieves a practical trade-off between efficiency, effectiveness and diversity. The validation of our work shows that (1) the conceptual model can be applied with a reasonable overhead in an industrial settings, (2) CP is able to effectively identify worst-case scenarios with respect to task deadlines, response time, and CPU usage, and (3) the combined GA+CP strategy is more likely than GA and CP in isolation to scale to large and complex systems. The work in this thesis opens up the exploration of further directions, involving the use of multi-objective optimization to generate stress test cases that simultaneously exercise different performance properties of the system, and of MiniMax analysis to derive design and configuration guidelines that minimize the risk to violate performance requirements at runtime