{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T15:34:05Z","timestamp":1784302445035,"version":"3.55.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,1,25]],"date-time":"2019-01-25T00:00:00Z","timestamp":1548374400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Austrian National Research Network","award":["S11403-N23"],"award-info":[{"award-number":["S11403-N23"]}]},{"DOI":"10.13039\/501100001821","name":"Vienna Science and Technology Fund","doi-asserted-by":"crossref","award":["VRG11-005"],"award-info":[{"award-number":["VRG11-005"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004955","name":"\u00d6sterreichische Forschungsf\u00f6rderungsgesellschaft","doi-asserted-by":"crossref","award":["853308"],"award-info":[{"award-number":["853308"]}],"id":[{"id":"10.13039\/501100004955","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2019,1,31]]},"abstract":"<jats:p>This work introduces a heuristic-guided branching search algorithm for model-based, mutation-driven test-case generation. The algorithm is designed towards the efficient and computationally tractable exploration of discrete, non-deterministic models with huge state spaces. Asynchronous parallel processing is a key feature of the algorithm. The algorithm is inspired by the successful path planning algorithm Rapidly exploring Random Trees (RRT). We adapt RRT in several aspects towards test-case generation. Most notably, we introduce parametrized heuristics for start and successor state selection, as well as a mechanism to construct test cases from the data produced during the search.<\/jats:p>\n          <jats:p>We implemented our algorithm in the existing test-case generation framework MoMuT. We present an extensive evaluation of the proposed heuristics and parameters of the algorithm, based on a diverse set of demanding models obtained in an industrial context. In total, we continuously utilized 128 CPU cores on three servers for several weeks to gather the experimental data presented. We show that branching search works well and the use of multiple heuristics is justified. With our new algorithm, we are now able to process models consisting of over 2,300 concurrent objects. To our knowledge, there is no other mutation-driven test-case generation tool that is able to process models of this magnitude.<\/jats:p>","DOI":"10.1145\/3289256","type":"journal-article","created":{"date-parts":[[2019,1,28]],"date-time":"2019-01-28T14:01:39Z","timestamp":1548684099000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Model-based, Mutation-driven Test-case Generation Via Heuristic-guided Branching Search"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3618-2251","authenticated-orcid":false,"given":"Andreas","family":"Fellner","sequence":"first","affiliation":[{"name":"AIT Austrian Institute of Technology, TU Wien, Vienna Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Willibald","family":"Krenn","sequence":"additional","affiliation":[{"name":"AIT Austrian Institute of Technology, Vienna Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rupert","family":"Schlick","sequence":"additional","affiliation":[{"name":"AIT Austrian Institute of Technology, Vienna Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4409-8487","authenticated-orcid":false,"given":"Thorsten","family":"Tarrach","sequence":"additional","affiliation":[{"name":"AIT Austrian Institute of Technology, Vienna Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Georg","family":"Weissenbacher","sequence":"additional","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,1,25]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Modeling in Event-B\u2014System and Software Engineering","author":"Abrial Jean-Raymond"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 2015 IEEE 8th International Conference on Software Testing, Verification and Validation (ICST\u201915)","author":"Aichernig B."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09099-3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/stvr.1522"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2014.05.004"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2011.6095077"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1062455.1062530"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/857076.857077"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800221.806716"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/648084.761190"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 42nd IEEE Conference on Decision and Control","volume":"1","author":"Branicky Michael S."},{"key":"e_1_2_1_12_1","volume-title":"Model-based Testing of Reactive Systems: Advanced Lectures","author":"Broy Manfred"},{"key":"e_1_2_1_13_1","volume-title":"Sayward","author":"Budd Timothy A.","year":"1979"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2009.02.022"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1978.231496"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1368088.1368099"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353673.1353681"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/360933.360975"},{"key":"e_1_2_1_19_1","volume-title":"Deshmukh","author":"Dreossi Tommaso","year":"2015"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3127041.3127049"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2006.1641879"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/QSIC.2011.19"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2011.93"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.624304"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064978.1065036"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Christoph Hilken and Jan Peleska. 2015. Model-based testing against complex SysML models. In Proceedings of the Formal Modeling and Verification of Cyber-Physical Systems and the 1st International Summer School on Methods and Tools for the Design of Digital Systems Rolf Drechsler and Ulrich K\u00fchne (Eds.). Springer 284--286.  Christoph Hilken and Jan Peleska. 2015. Model-based testing against complex SysML models. In Proceedings of the Formal Modeling and Verification of Cyber-Physical Systems and the 1st International Summer School on Methods and Tools for the Design of Digital Systems Rolf Drechsler and Ulrich K\u00fchne (Eds.). Springer 284--286.","DOI":"10.1007\/978-3-658-09994-7_14"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1982.235571"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2008.4650993"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2932431.2932469"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2010.62"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2635868.2635929"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.57624"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 8th International Conference on Formal Methods for Components and Objects (FMCO\u201909)","author":"Krenn Willibald"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation (ICRA\u201900)","volume":"2","author":"James"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 2nd IEEE \/ ACM International Symposium on Code Generation and Optimization (CGO\u201904)","author":"Lattner Chris"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2015.49"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2011.6100092"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177730491"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1077276.1077279"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1297846.1297902"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2007.37"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1062455.1062529"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41135-4_1"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1450058.1450088"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-013-0291-0"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/521138.786846"},{"key":"e_1_2_1_50_1","first-page":"103","article-title":"Test generation with inputs, outputs and repetitive quiescence","volume":"17","author":"Tretmans Jan","year":"1996","journal-title":"Softw. Concept. Tools"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1002\/stvr.456"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISSRE.2013.6698890"},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the Annual Conference on Genetic and Evolutionary Computation (GECCO\u201902)","volume":"2","author":"Wegener Joachim","year":"2002"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1068009.1068188"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3289256","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3289256","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:43:38Z","timestamp":1750207418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3289256"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,25]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1,31]]}},"alternative-id":["10.1145\/3289256"],"URL":"https:\/\/doi.org\/10.1145\/3289256","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,25]]},"assertion":[{"value":"2018-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}