AuthorsS. Di Alesio
TitleGenerating Worst-case Schedules with Constraint Optimization – An Approach to Support Software Performance Testing
AfilliationSoftware Engineering, Software Engineering, Software Engineering
Project(s)The Certus Centre (SFI)
Publication TypeTalks, invited
Year of Publication2015
Location of TalkThe 14th INFORMS Computing Society Conference (ICS'15)

To be deemed safe for operation, safety-critical Real-Time Embedded Systems (RTES) must satisfy strict performance requirements constraining how quickly the system must react to external inputs. Stress testing such systems is crucial, because their correct behavior has to be ensured even under the worst operating conditions. In this presentation, we address the derivation of worst case schedules for RTES tasks with respect to three common classes of performance requirements, namely task deadlines, response time, and CPU usage. Specifically, we re-express this worst-case analysis as a Constrained Optimization Problem (COP) that mimics a task priority-based preemptive scheduler over the space of system inputs. The solutions to this COP are input combinations that maximize the chance to violate performance requirements, thus defining a worst case scenario. These combinations in turn characterize stress test cases that once executed push the system to its worst performance. Our preliminary validation in several case studies showed that the COP effectively generates test cases maximizing deadline misses, response time, and CPU usage. Ongoing and future work on this topic involves combining Constraint Programming with Evolutionary Algorithms in order to efficiently generate highly diverse solutions, i.e., test cases stressing the system in different worst-case scenarios.

Citation Key23563