{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:14:01Z","timestamp":1750306441862,"version":"3.41.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,12,2]],"date-time":"2015-12-02T00:00:00Z","timestamp":1449014400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100005416","name":"Research Council of Norway","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Research Fund, Luxembourg"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Softw. Eng. Methodol."],"published-print":{"date-parts":[[2015,12,2]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/2818640","type":"journal-article","created":{"date-parts":[[2015,12,4]],"date-time":"2015-12-04T13:43:07Z","timestamp":1449236587000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Combining Genetic Algorithms and Constraint Programming to Support Stress Testing of Task Deadlines"],"prefix":"10.1145","volume":"25","author":[{"given":"Stefano Di","family":"Alesio","sequence":"first","affiliation":[{"name":"Simula Research Laboratory and University of Luxembourg, Lysaker, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lionel C.","family":"Briand","sequence":"additional","affiliation":[{"name":"University of Luxembourg, Luxembourg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shiva","family":"Nejati","sequence":"additional","affiliation":[{"name":"University of Luxembourg, Luxembourg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnaud","family":"Gotlieb","sequence":"additional","affiliation":[{"name":"Simula Research Laboratory, Lysaker, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,12,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.infsof.2008.12.005"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1990.113766"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISORC.2011.28"},{"volume-title":"Principles of Constraint Programming","author":"Apt Krzysztof","key":"e_1_2_1_4_1","unstructured":"Krzysztof Apt . 2003. Principles of Constraint Programming . Cambridge University Press . Krzysztof Apt. 2003. Principles of Constraint Programming. Cambridge University Press."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1985793.1985795"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-005-3968-2"},{"volume-title":"Proceedings of the IEEE Workshop on Real-Time Operating Systems and Software.","author":"Audsley Neil C.","key":"e_1_2_1_7_1","unstructured":"Neil C. Audsley , Alan Burns , Mike F. Richardson , and Andy J. Wellings . 1991. Real-time scheduling: The deadline-monotonic approach . In Proceedings of the IEEE Workshop on Real-Time Operating Systems and Software. Neil C. Audsley, Alan Burns, Mike F. Richardson, and Andy J. Wellings. 1991. Real-time scheduling: The deadline-monotonic approach. In Proceedings of the IEEE Workshop on Real-Time Operating Systems and Software."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/S11241-005-4686-1"},{"key":"e_1_2_1_9_1","volume-title":"Claude Le Pape, and Wim Nuijten","author":"Baptiste Philippe","year":"2001","unstructured":"Philippe Baptiste , Claude Le Pape, and Wim Nuijten . 2001 . Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems. Springer . Philippe Baptiste, Claude Le Pape, and Wim Nuijten. 2001. Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems. Springer."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1985793.1985930"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1363686.1363847"},{"volume-title":"Software Testing Techniques","author":"Beizer B.","key":"e_1_2_1_12_1","unstructured":"B. Beizer . 2002. Software Testing Techniques . Dreamtech Press . B. Beizer. 2002. Software Testing Techniques. Dreamtech Press."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/HICSS.2005.296"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10710-006-9003-9"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1049\/cce:20000101"},{"key":"e_1_2_1_16_1","volume-title":"Principles and Practice of Constraint Programming--CP","author":"Cambazard Hadrien","year":"2004","unstructured":"Hadrien Cambazard , Pierre-Emmanuel Hladik , Anne-Marie D\u00e9planche , Narendra Jussien , and Yvon Trinquet . 2004. Decomposition and learning for a hard real time task allocation problem . In Principles and Practice of Constraint Programming--CP 2004 . Springer , 153--167. Hadrien Cambazard, Pierre-Emmanuel Hladik, Anne-Marie D\u00e9planche, Narendra Jussien, and Yvon Trinquet. 2004. Decomposition and learning for a hard real time task allocation problem. In Principles and Practice of Constraint Programming--CP 2004. Springer, 153--167."},{"volume-title":"Tools for Practical Software Verification","author":"Clarke Edmund M.","key":"e_1_2_1_17_1","unstructured":"Edmund M. Clarke , William Klieber , Milo\u0161 Nov\u00e1\u010dek , and Paolo Zuliani . 2012. Model checking and the state explosion problem . In Tools for Practical Software Verification . Springer , 1--30. Edmund M. Clarke, William Klieber, Milo\u0161 Nov\u00e1\u010dek, and Paolo Zuliani. 2012. Model checking and the state explosion problem. In Tools for Practical Software Verification. Springer, 1--30."},{"volume-title":"Model-Based Design for Embedded Systems","author":"David Alexandre","key":"e_1_2_1_18_1","unstructured":"Alexandre David , Jacob Illum , K. Larsen , and Arne Skou . 2010. Model-based framework for schedulability analysis using UPPAAL 4.1 . In Model-Based Design for Embedded Systems . CRC Press . Alexandre David, Jacob Illum, K. Larsen, and Arne Skou. 2010. Model-based framework for schedulability analysis using UPPAAL 4.1. In Model-Based Design for Embedded Systems. CRC Press."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1068009.1068185"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICST.2012.171"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISSRE.2013.6698915"},{"volume-title":"Principles and Practice of Constraint Programming","author":"Alesio Stefano Di","key":"e_1_2_1_23_1","unstructured":"Stefano Di Alesio , Shiva Nejati , Lionel Briand , and Arnaud Gotlieb . 2014. Worst-case scheduling of software tasks -- A constraint optimization model to support performance testing . In Principles and Practice of Constraint Programming . Springer . Stefano Di Alesio, Shiva Nejati, Lionel Briand, and Arnaud Gotlieb. 2014. Worst-case scheduling of software tasks -- A constraint optimization model to support performance testing. In Principles and Practice of Constraint Programming. Springer."},{"volume-title":"Handbook of Metaheuristics","author":"Focacci Filippo","key":"e_1_2_1_24_1","unstructured":"Filippo Focacci , Fran\u00e7ois Laburthe , and Andrea Lodi . 2003. Local search and constraint programming . In Handbook of Metaheuristics . Springer , 369--403. Filippo Focacci, Fran\u00e7ois Laburthe, and Andrea Lodi. 2003. Local search and constraint programming. In Handbook of Metaheuristics. Springer, 369--403."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Gordon Fraser Andrea Arcuri and Phil McMinn. 2015. A memetic algorithm for whole test suite generation. J. Syst. Softw. 103 (2015) 311--327.  Gordon Fraser Andrea Arcuri and Phil McMinn. 2015. A memetic algorithm for whole test suite generation. J. Syst. Softw. 103 (2015) 311--327.","DOI":"10.1016\/j.jss.2014.05.032"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2007.05.037"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1134285.1134504"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-011-9261-y"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2009.71"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00450-013-0251-7"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2007.02.032"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1177\/003754979406200405"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1080\/02522667.1996.10699291"},{"volume-title":"The Art of Computer Systems Performance Analysis","author":"Jain R.","key":"e_1_2_1_34_1","unstructured":"R. Jain . 2008. The Art of Computer Systems Performance Analysis . John Wiley & Sons . R. Jain. 2008. The Art of Computer Systems Performance Analysis. John Wiley & Sons."},{"volume-title":"Real-Time Systems: Design Principles for Distributed Embedded Applications","author":"Kopetz Hermann","key":"e_1_2_1_35_1","unstructured":"Hermann Kopetz . 2011. Real-Time Systems: Design Principles for Distributed Embedded Applications . Springer . Hermann Kopetz. 2011. Real-Time Systems: Design Principles for Distributed Embedded Applications. Springer."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01929-6_12"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2010.07.026"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the CP97 Workshop on Industrial Constraint-Directed Scheduling. Citeseer.","author":"Pape Claude Le","year":"1997","unstructured":"Claude Le Pape and Philippe Baptiste . 1997 . An experimental comparison of constraint-based algorithms for the preemptive job shop scheduling problem . In Proceedings of the CP97 Workshop on Industrial Constraint-Directed Scheduling. Citeseer. Claude Le Pape and Philippe Baptiste. 1997. An experimental comparison of constraint-based algorithms for the preemptive job shop scheduling problem. In Proceedings of the CP97 Workshop on Industrial Constraint-Directed Scheduling. Citeseer."},{"key":"e_1_2_1_39_1","unstructured":"Fan Liu Ajit Narayanan and Quan Bai. 2000. Real-Time Systems. Citeseer.  Fan Liu Ajit Narayanan and Quan Bai. 2000. Real-Time Systems. Citeseer."},{"key":"e_1_2_1_40_1","unstructured":"C. D. Locke D. R. Vogel L. Lucas and J. B. Goodenough. 1990. Generic Avionics Software Specification. Technical Report. DTIC document.  C. D. Locke D. R. Vogel L. Lucas and J. B. Goodenough. 1990. Generic Avionics Software Specification. Technical Report. DTIC document."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1100.0446"},{"key":"e_1_2_1_42_1","volume-title":"UPPAAL: Herschel-Planck case study. In Leveraging Applications of Formal Methods, Verification, and Validation","author":"Miku\u010dionis M.","year":"2010","unstructured":"M. Miku\u010dionis , K. G. Larsen , J. I. Rasmussen , B. Nielsen , A. Skou , S. U. Palm , J. S. Pedersen , and P. Hougaard . 2010 . Schedulability analysis using UPPAAL: Herschel-Planck case study. In Leveraging Applications of Formal Methods, Verification, and Validation . Springer , 175--190. M. Miku\u010dionis, K. G. Larsen, J. I. Rasmussen, B. Nielsen, A. Skou, S. U. Palm, J. S. Pedersen, and P. Hougaard. 2010. Schedulability analysis using UPPAAL: Herschel-Planck case study. In Leveraging Applications of Formal Methods, Verification, and Validation. Springer, 175--190."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(97)00031-2"},{"volume-title":"The Art of Software Testing","author":"Myers Glenford J.","key":"e_1_2_1_44_1","unstructured":"Glenford J. Myers , Corey Sandler , and Tom Badgett . 2011. The Art of Software Testing . John Wiley & Sons . Glenford J. Myers, Corey Sandler, and Tom Badgett. 2011. The Art of Software Testing. John Wiley & Sons."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33666-9_48"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2006.10.010"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the ACES-MB Workshop. 129","author":"Peraldi-Frati Marie-Agn\u00e0s","year":"2008","unstructured":"Marie-Agn\u00e0s Peraldi-Frati and Yves Sorel . 2008 . From high-level modelling of time in MARTE to real-time scheduling analysis . In Proceedings of the ACES-MB Workshop. 129 . Marie-Agn\u00e0s Peraldi-Frati and Yves Sorel. 2008. From high-level modelling of time in MARTE to real-time scheduling analysis. In Proceedings of the ACES-MB Workshop. 129."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61551-2_86"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/11890584_1"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1188895.1188909"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/647485.726320"},{"volume-title":"Identifying Malicious Code Through Reverse Engineering","author":"Singh Abhishek","key":"e_1_2_1_52_1","unstructured":"Abhishek Singh . 2009. Identifying Malicious Code Through Reverse Engineering . Springer Science & Business Media , Advances in Information Security. Vol. 44 . Abhishek Singh. 2009. Identifying Malicious Code Through Reverse Engineering. Springer Science & Business Media, Advances in Information Security. Vol. 44."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02341920"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0165-6074(94)90080-9"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICAS.2006.53"},{"volume-title":"Constraint-Based Local Search","author":"Hentenryck Pascal Van","key":"e_1_2_1_56_1","unstructured":"Pascal Van Hentenryck and Laurent Michel . 2009. Constraint-Based Local Search . The MIT Press . Pascal Van Hentenryck and Laurent Michel. 2009. Constraint-Based Local Search. The MIT Press."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.888628"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1347375.1347389"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0360-8352(02)00065-7"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.487"}],"container-title":["ACM Transactions on Software Engineering and Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818640","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2818640","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:42:49Z","timestamp":1750225369000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818640"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,2]]},"references-count":59,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,12,2]]}},"alternative-id":["10.1145\/2818640"],"URL":"https:\/\/doi.org\/10.1145\/2818640","relation":{},"ISSN":["1049-331X","1557-7392"],"issn-type":[{"type":"print","value":"1049-331X"},{"type":"electronic","value":"1557-7392"}],"subject":[],"published":{"date-parts":[[2015,12,2]]},"assertion":[{"value":"2014-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}