{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T00:09:51Z","timestamp":1725926991624},"reference-count":53,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2021,10,8]],"date-time":"2021-10-08T00:00:00Z","timestamp":1633651200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/L016427\/1"],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000848","name":"University of Edinburgh","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000848","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Software Testing Verif & Rel"],"published-print":{"date-parts":[[2022,1]]},"abstract":"Summary<\/jats:title>Model\u2010based development is a popular development approach in which software is implemented and verified based on a model of the required system. Finite state machines (FSMs) are widely used as models for systems in several domains. Validating that a model accurately represents the required behaviour involves the generation and execution of a large number of input sequences, which is often an expensive and time\u2010consuming process. In this paper, we speed up the execution of input sequences for FSM validation, by leveraging the high degree of parallelism of modern graphics processing units (GPUs) for the automatic execution of FSM input sequences in parallel on the GPU threads. We expand our existing work by providing techniques that improve the performance and scalability of this approach. We conduct extensive empirical evaluation using 15 large FSMs from the networking domain and measure GPU speed\u2010up over a 16\u2010core CPU, taking into account total GPU time, which includes both data transfer and kernel execution time. We found that GPUs execute FSM input sequences up to 9.28\u00d7 faster than a 16\u2010core CPU, with an average speed\u2010up of 4.53\u00d7 across all subjects. Our optimizations achieve an average improvement over existing work of 58.95%<\/jats:italic>for speed\u2010up and scalability to large FSMs with over 2K states and 500K transitions. We also found that techniques aimed at reducing the number of required input sequences for large FSMs with high density were ineffective when applied to all\u2010transition pair coverage, thus emphasizing the need for approaches like ours that speed up input execution.<\/jats:p>","DOI":"10.1002\/stvr.1796","type":"journal-article","created":{"date-parts":[[2021,10,10]],"date-time":"2021-10-10T05:50:09Z","timestamp":1633845009000},"update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["GPU acceleration of finite state machine input execution: Improving scale and performance"],"prefix":"10.1002","volume":"32","author":[{"ORCID":"http:\/\/orcid.org\/0000-0003-3804-8088","authenticated-orcid":false,"given":"Vanya","family":"Yaneva","sequence":"first","affiliation":[{"name":"School of Informatics The University of Edinburgh Edinburgh UK"}]},{"given":"Ajitha","family":"Rajan","sequence":"additional","affiliation":[{"name":"School of Informatics The University of Edinburgh Edinburgh UK"}]},{"given":"Christophe","family":"Dubach","sequence":"additional","affiliation":[{"name":"School of Computer Science McGill University Montr\u00e9al Quebec Canada"}]}],"member":"311","published-online":{"date-parts":[[2021,10,8]]},"reference":[{"key":"e_1_2_10_2_1","unstructured":"RajanA.Coverage metrics for requirements\u2010based testing.Ph.D. Thesis University of Minnesota 2009."},{"key":"e_1_2_10_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.533956"},{"key":"e_1_2_10_4_1","unstructured":"MathWorks.Simulink 2020.https:\/\/uk.mathworks.com\/products\/simulink.html(visited on 19\/05\/2020)."},{"key":"e_1_2_10_5_1","unstructured":"IBM.Rational Rhapsody 2020.https:\/\/www.ibm.com\/products\/systems-design-rhapsody(visited on 19\/05\/2020)."},{"key":"e_1_2_10_6_1","unstructured":"Sparx Systems.Enterprise Architect 2020.http:\/\/www.sparxsystems.com\/(visited on 19\/05\/2020)."},{"key":"e_1_2_10_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146238.1146242"},{"key":"e_1_2_10_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/HASE.2007.57"},{"key":"e_1_2_10_9_1","unstructured":"Keysight Technologies.Company website 2020.https:\/\/www.keysight.com\/(visited on 19\/05\/2020)."},{"key":"e_1_2_10_10_1","unstructured":"LehaneAR KirkhamAJA BarfordLA.Digital triggering using finite state machines.Google Patents 2016.https:\/\/www.google.ch\/patents\/US20160085223. US Patent App. 14\/957 491."},{"key":"e_1_2_10_11_1","doi-asserted-by":"crossref","unstructured":"YanevaV KapoorA RajanA DubachC.Accelerated finite state machine test execution using GPUs. In2018 25th Asia\u2010Pacific Software Engineering Conference (APSEC):Nara Japan 2018;109\u2013118.","DOI":"10.1109\/APSEC.2018.00025"},{"key":"e_1_2_10_12_1","unstructured":"Snort.Network intrusion detection and prevention system 2020.http:\/\/snort.org\/(visited on 19\/05\/2020)."},{"key":"e_1_2_10_13_1","doi-asserted-by":"crossref","unstructured":"YanevaV RajanA DubachC.Compiler\u2010assisted test acceleration on GPUs for embedded software. InProceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis ISSTA 2017.ACM:New York NY USA 2017;35\u201345.","DOI":"10.1145\/3092703.3092720"},{"key":"e_1_2_10_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2642937.2642957"},{"key":"e_1_2_10_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/5397.5399"},{"key":"e_1_2_10_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/AERO.2001.931304"},{"key":"e_1_2_10_17_1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400882618-006"},{"key":"e_1_2_10_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWCT.1964.8"},{"key":"e_1_2_10_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/b137241"},{"key":"e_1_2_10_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.272431"},{"key":"e_1_2_10_21_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxv041"},{"key":"e_1_2_10_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxw004"},{"key":"e_1_2_10_23_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxw069"},{"key":"e_1_2_10_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.infsof.2020.106297"},{"key":"e_1_2_10_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.649519"},{"key":"e_1_2_10_26_1","unstructured":"2004 Springer Q Guo RM Hierons M Harman K Derderian Computing unique input\/output sequences using genetic algorithms. In Proceedings of the 3rd International Workshop on Formal Approaches to Testing of Software (FATES 2003) Montreal Canada Volume 2931 of LNCS 169 184"},{"key":"e_1_2_10_27_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxl003"},{"key":"e_1_2_10_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1978.231496"},{"key":"e_1_2_10_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.87284"},{"key":"e_1_2_10_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.265636"},{"key":"e_1_2_10_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2002.1049402"},{"key":"e_1_2_10_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-40914-2_4"},{"key":"e_1_2_10_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.559807"},{"key":"e_1_2_10_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2002.1032630"},{"key":"e_1_2_10_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2006.80"},{"key":"e_1_2_10_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00165-009-0135-6"},{"key":"e_1_2_10_37_1","doi-asserted-by":"crossref","unstructured":"OffuttAJ XiongY LiuS.Criteria for generating specification\u2010based tests. InProceedings of the 5th International Conference on Engineering of Complex Computer Systems ICECCS '99.IEEE Computer Society:Washington DC USA 1999;119\u2013129.","DOI":"10.1109\/ICECCS.1999.802856"},{"volume-title":"Testing Object\u2010Oriented Systems: Models, Patterns, and Tools","year":"1999","author":"Binder RV","key":"e_1_2_10_38_1"},{"key":"e_1_2_10_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2004.1317431"},{"key":"e_1_2_10_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2016.2539964"},{"issue":"4","key":"e_1_2_10_41_1","first-page":"1029","article-title":"\u2010branching UIO sequences for partially specified observable non\u2010deterministic FSMs","volume":"47","author":"El\u2010Fakih K","year":"2019","journal-title":"IEEE Trans Softw Eng"},{"key":"e_1_2_10_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2016.2532869"},{"key":"e_1_2_10_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3051121"},{"key":"e_1_2_10_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2482767.2482791"},{"key":"e_1_2_10_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISPASS.2009.4919649"},{"key":"e_1_2_10_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1880153.1880157"},{"key":"e_1_2_10_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87403-4_7"},{"key":"e_1_2_10_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2011.6114181"},{"issue":"4","key":"e_1_2_10_49_1","first-page":"37","article-title":"Test case generation for transition\u2010pair coverage using Scatter Search","volume":"4","author":"Blanco R","year":"2010","journal-title":"Int J Software Eng It's Appl"},{"issue":"2","key":"e_1_2_10_50_1","first-page":"67","article-title":"Regression testing minimization, selection and prioritization: a survey","volume":"22","author":"Yoo S","year":"2012","journal-title":"STVR"},{"key":"e_1_2_10_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2007.38"},{"key":"e_1_2_10_52_1","unstructured":"YanevaV.GPU acceleration of FSM validation test execution: artifacts 2020.https:\/\/github.com\/wyaneva\/gpu-fsm-validation-artifacts"},{"key":"e_1_2_10_53_1","unstructured":"EstesW.Flex: a fast scanner generator 2020.https:\/\/github.com\/westes\/flex(visited on 19\/05\/2020)."},{"key":"e_1_2_10_54_1","unstructured":"SentovichEM SinghKJ LavagnoL MoonC MurgaiR SaldanhaA et al.SIS: a system for sequential circuit synthesis. In UCB\/ERL M92\/41 EECS Department University of California Berkeley 1992."}],"container-title":["Software Testing, Verification and Reliability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/stvr.1796","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/stvr.1796","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/stvr.1796","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T17:05:52Z","timestamp":1725901552000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/stvr.1796"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,8]]},"references-count":53,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["10.1002\/stvr.1796"],"URL":"https:\/\/doi.org\/10.1002\/stvr.1796","archive":["Portico"],"relation":{},"ISSN":["0960-0833","1099-1689"],"issn-type":[{"type":"print","value":"0960-0833"},{"type":"electronic","value":"1099-1689"}],"subject":[],"published":{"date-parts":[[2021,10,8]]},"assertion":[{"value":"2021-05-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-08-04","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}