TY - JOUR
T1 - Combining genetic algorithms and constraint programming to support stress testing of task deadlines
AU - Di Alesio, Stefano
AU - Briand, Lionel C.
AU - Nejati, Shiva
AU - Gotlieb, Arnaud
PY - 2015/11
Y1 - 2015/11
N2 - Tasks in real-time embedded systems (RTES) are often subject to hard deadlines that constrain how quickly the system must react to external inputs. These inputs and their timing vary in a large domain depending on the environment state and can never be fully predicted prior to system execution. Therefore, approaches for stress testing must be developed to uncover possible deadline misses of tasks for different input arrival times. In this article, we describe stress-test case generation as a search problem over the space of task arrival times. Specifically, we search for worst-case scenarios maximizing deadline misses, where each scenario characterizes a test case. In order to scale our search to large industrial-size problems, we combine two state-of-the-art search strategies, namely, genetic algorithms (GA) and constraint programming (CP). Our experimental results show that, in comparison with GA and CP in isolation, GA+CP achieves nearly the same effectiveness as CP and the same efficiency and solution diversity as GA, thus combining the advantages of the two strategies. In light of these results, we conclude that a combined GA+CP approach to stress testing is more likely to scale to large and complex systems. 2015 Copyright is held by the owner/author(s).
AB - Tasks in real-time embedded systems (RTES) are often subject to hard deadlines that constrain how quickly the system must react to external inputs. These inputs and their timing vary in a large domain depending on the environment state and can never be fully predicted prior to system execution. Therefore, approaches for stress testing must be developed to uncover possible deadline misses of tasks for different input arrival times. In this article, we describe stress-test case generation as a search problem over the space of task arrival times. Specifically, we search for worst-case scenarios maximizing deadline misses, where each scenario characterizes a test case. In order to scale our search to large industrial-size problems, we combine two state-of-the-art search strategies, namely, genetic algorithms (GA) and constraint programming (CP). Our experimental results show that, in comparison with GA and CP in isolation, GA+CP achieves nearly the same effectiveness as CP and the same efficiency and solution diversity as GA, thus combining the advantages of the two strategies. In light of these results, we conclude that a combined GA+CP approach to stress testing is more likely to scale to large and complex systems. 2015 Copyright is held by the owner/author(s).
KW - Constraint programming
KW - Genetic algorithms
KW - Real-time systems
KW - Search-based software testing
KW - Stress testing
KW - Task deadline
UR - http://www.scopus.com/inward/record.url?scp=84952064666&partnerID=8YFLogxK
U2 - 10.1145/2818640
DO - 10.1145/2818640
M3 - Article
AN - SCOPUS:84952064666
SN - 1049-331X
VL - 25
JO - ACM Transactions on Software Engineering and Methodology
JF - ACM Transactions on Software Engineering and Methodology
IS - 1
M1 - 4
ER -