{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,8]],"date-time":"2025-11-08T12:47:41Z","timestamp":1762606061312},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2013,9,1]],"date-time":"2013-09-01T00:00:00Z","timestamp":1377993600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Form. Asp. Comput."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>\n            Given a finite state machine denoting the\n            <jats:italic>specification<\/jats:italic>\n            of a system, finding some short interaction sequences capable of reaching some\/all states or transitions of this machine is a typical goal in testing methods. If these sequences are applied to an\n            <jats:italic>implementation under test<\/jats:italic>\n            , then equivalent states or transitions would be reached and observed in the implementation\u2014provided that the implementation were actually defined as the specification. We study the problem of finding such sequences in the case where configurations previously traversed can be\n            <jats:italic>saved<\/jats:italic>\n            and\n            <jats:italic>restored<\/jats:italic>\n            (at some cost). In general, this feature enables sequences to reach the required parts of the machine in less time, because some repetitions can be avoided. However, we show that finding optimal sequences in this case is an NP-hard problem. We propose an heuristic method to approximately solve this problem based on an evolutionary computation approach, in particular\n            <jats:italic>river formation dynamics<\/jats:italic>\n            (RFD). Given\n            <jats:italic>finite state machine<\/jats:italic>\n            specifications and sets of states\/transitions to be reached, we apply RFD to construct testing plans reaching these configurations. Experimental results show that being able to load previously traversed states generally reduces the time needed to cover the target configurations.\n          <\/jats:p>","DOI":"10.1007\/s00165-011-0206-3","type":"journal-article","created":{"date-parts":[[2012,1,18]],"date-time":"2012-01-18T08:08:37Z","timestamp":1326874117000},"page":"743-768","source":"Crossref","is-referenced-by-count":13,"title":["Testing restorable systems: formal definition and heuristic solution based on river formation dynamics"],"prefix":"10.1145","volume":"25","author":[{"given":"Pablo","family":"Rabanal","sequence":"first","affiliation":[{"name":"Dept. Sistemas Inform\u00e1ticos y Computaci\u00f3n, Facultad de Inform\u00e1tica, Universidad Complutense de Madrid, 28040, Madrid, Spain"}]},{"given":"Ismael","family":"Rodr\u00edguez","sequence":"additional","affiliation":[{"name":"Dept. Sistemas Inform\u00e1ticos y Computaci\u00f3n, Facultad de Inform\u00e1tica, Universidad Complutense de Madrid, 28040, Madrid, Spain"}]},{"given":"Fernando","family":"Rubio","sequence":"additional","affiliation":[{"name":"Dept. Sistemas Inform\u00e1ticos y Computaci\u00f3n, Facultad de Inform\u00e1tica, Universidad Complutense de Madrid, 28040, Madrid, Spain"}]}],"member":"320","reference":[{"key":"e_1_2_1_2_1_2","doi-asserted-by":"crossref","unstructured":"Alba E Chicano JF (2007) Ant colony optimization for model checking. In: EUROCAST\u201907. LNCS vol 4739 pp 523\u2013530","DOI":"10.1007\/978-3-540-75867-9_66"},{"key":"e_1_2_1_2_2_2","unstructured":"Aho A Dahbura A Lee D Uyar M\u00dc (1988) An optimization technique for protocol conformance test generation based on UIO sequences and Rural Chinese Postman tours. In: Protocol specification testing and verification PSTV\u201988. North-Holland Amsterdam pp 75\u201386"},{"key":"e_1_2_1_2_3_2","unstructured":"Antoniol G Di Penta M Harman M (2004) A robust search-based approach to project management in the presence of abandonment rework error and uncertainty. In: IEEE software metrics symposium METRICS\u201904. IEEE Computer Society New York pp 172\u2013183"},{"key":"e_1_2_1_2_4_2","doi-asserted-by":"crossref","unstructured":"Alba E Troya JM (1996) Genetic algorithms for protocol validation. In: Parallel problem solving from nature PPSN\u201996. LNCS vol 1141. Springer Berlin pp 870\u2013879","DOI":"10.1007\/3-540-61723-X_1050"},{"key":"e_1_2_1_2_5_2","doi-asserted-by":"publisher","DOI":"10.1049\/sej.1991.0040"},{"key":"e_1_2_1_2_6_2","unstructured":"Burgess CJ Lefley M (2005) Can Genetic Programming improve Software Effort Estimation? A Comparative Evaluation. In: Machine learning applications in software engineering: series on software engineering and knowledge engineering vol 16. World Scientific Publishing Co. Singapore pp 95\u2013105"},{"key":"e_1_2_1_2_7_2","unstructured":"Bottaci L (2002) Instrumenting programs with flag variables for test data search by genetic algorithms. In: Conference on genetic and evolutionary computation GECCO\u201902. Morgan Kaufmann Publishers Inc. Menlo Park pp 1337\u20131342"},{"key":"e_1_2_1_2_8_2","doi-asserted-by":"crossref","unstructured":"Brinksma E Tretmans J (2001) Testing transition systems: an annotated bibliography. In: 4th summer school on modeling and verification of parallel processes MOVEP\u201900. LNCS vol 2067. Springer Berlin pp 187\u2013195","DOI":"10.1007\/3-540-45510-8_9"},{"key":"e_1_2_1_2_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1978.231496"},{"key":"e_1_2_1_2_10_2","doi-asserted-by":"crossref","unstructured":"Chen K Jiang F Huang C-D (2006) A new method of generating synchronizable test sequences that detect output-shifting faults based on multiple UIO sequences. In: Proceedings of the 2006 ACM symposium on applied computing SAC\u201906. ACM New York pp 1791\u20131797","DOI":"10.1145\/1141277.1141697"},{"key":"e_1_2_1_2_11_2","doi-asserted-by":"crossref","unstructured":"Cohen M Kooi SB Srisa-an W (2006) Clustering the heap in multi-threaded applications for improved garbage collection. In: Conference on genetic and evolutionary computation GECCO\u201906. ACM New York pp 1901\u20131908","DOI":"10.1145\/1143997.1144314"},{"key":"e_1_2_1_2_12_2","volume-title":"Linear programming and extensions. Rand corporation research study","author":"Dantzig GB","year":"1963"},{"key":"e_1_2_1_2_13_2","doi-asserted-by":"crossref","unstructured":"Doerner K Gutjahr WJ (2003) Extracting test sequences from a Markov software usage model by ACO. In: Conference on genetic and evolutionary computation part II GECCO\u201903. LNCS vol 2724. Springer Berlin pp 2465\u20132476","DOI":"10.1007\/3-540-45110-2_150"},{"key":"e_1_2_1_2_14_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxl003"},{"key":"e_1_2_1_2_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/975277"},{"key":"e_1_2_1_2_16_2","unstructured":"Dahbura A Uyar M\u00dc (1995) Optimal test sequence generation for protocols: the Chinese Postman algorithm applied to Q.931. in: Conformance testing methodologies and architectures for OSI protocols. IEEE Computer Society Press New York pp 347\u2013351"},{"key":"e_1_2_1_2_17_2","doi-asserted-by":"crossref","unstructured":"Edelkamp S Lluch-Lafuente A Leue S (2001) Directed explicit model checking with HSF-SPIN. In: SPIN workshop on model checking of software SPIN\u201901. LNCS vol 2057. Springer Berlin pp 57\u201379","DOI":"10.1007\/3-540-45139-0_5"},{"key":"e_1_2_1_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2002.1049402"},{"key":"e_1_2_1_2_19_2","doi-asserted-by":"crossref","unstructured":"Gaudel M-C (1995) Testing can be formal too. In: 6th CAAP\/FASE theory and practice of software development TAPSOFT\u201995 LNCS vol 915. Springer Berlin pp 82\u201396","DOI":"10.1007\/3-540-59293-8_188"},{"key":"e_1_2_1_2_20_2","doi-asserted-by":"crossref","unstructured":"Godefroid P Khurshid S (2002) Exploring very large state spaces using genetic algorithms. In: Conference on tools and algorithms for the construction and analysis of systems TACAS\u201902. LNCS vol 2280. Springer Berlin pp 266\u2013280","DOI":"10.1007\/3-540-46002-0_19"},{"key":"e_1_2_1_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1970.222975"},{"key":"e_1_2_1_2_22_2","doi-asserted-by":"crossref","unstructured":"Harman M (2007) The current state and future of search based software engineering. In: Workshop on the future of software engineering FOSE\u201907 pp 342\u2013357","DOI":"10.1109\/FOSE.2007.29"},{"key":"e_1_2_1_2_23_2","doi-asserted-by":"crossref","unstructured":"Hennie FC (1964) Fault detecting experiments for sequential circuits. In: Annual IEEE symposium on foundations of computer science pp 95\u2013110","DOI":"10.1109\/SWCT.1964.8"},{"key":"e_1_2_1_2_24_2","unstructured":"Harman M Hierons RM Proctor M (2002) A new representation and crossover operator for search-based optimization of software modularization. In: Conference on genetic and evolutionary computation GECC0\u201902. Morgan Kaufmann Publishers Menlo Park pp 1351\u20131358 Inc"},{"key":"e_1_2_1_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/606612.606615"},{"key":"e_1_2_1_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2004.85"},{"key":"e_1_2_1_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/1538942.1538944"},{"key":"e_1_2_1_2_28_2","first-page":"226","article-title":"A theoretical and empirical study of search-based testing: local, global, and hybrid search","volume":"99","author":"Harman M","year":"2009","journal-title":"IEEE Trans Softw Eng"},{"key":"e_1_2_1_2_29_2","volume-title":"Adaptation in natural and artificial systems","author":"Holland JH","year":"1975"},{"key":"e_1_2_1_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10515-009-0061-0"},{"key":"e_1_2_1_2_31_2","doi-asserted-by":"crossref","unstructured":"Huang G-D Wang F (2005) Automatic test case generation with region-related coverage annotations for real-time systems. In: Symposium on automated technology for verification and analysis ATVA\u201905. LNCS vol 3707. Springer Berlin pp 144\u2013158","DOI":"10.1007\/11562948_13"},{"key":"e_1_2_1_2_32_2","doi-asserted-by":"crossref","unstructured":"Ipate F Banica L (2007) W-method for hierarchical and communicating finite state machines. In: IEEE international conference on industrial informatics vol 2. IEEE Computer Society New York pp 891\u2013896","DOI":"10.1109\/INDIN.2007.4384891"},{"key":"e_1_2_1_2_33_2","volume-title":"Evolutionary computation: a unified approach","author":"De Jong KA","year":"2006"},{"key":"e_1_2_1_2_34_2","doi-asserted-by":"publisher","DOI":"10.1002\/stvr.4370020405"},{"key":"e_1_2_1_2_35_2","doi-asserted-by":"crossref","unstructured":"Langdon WB Harman M Jia Y (2009) Multi-objective higher order mutation testing with genetic programming. In: Testing: academic and industrial conference\u2014practice and research techniques TAIC-PART\u201909. IEEE Computer Society New York pp 21\u201329","DOI":"10.1109\/TAICPART.2009.18"},{"key":"e_1_2_1_2_36_2","unstructured":"Lam CP Xiao J Li H (2007) Ant colony optimisation for generation of conformance testing sequences using a characterising set. In: IASTED conference on advances in computer science and technology. ACTA Press Mexico pp 140\u2013146"},{"key":"e_1_2_1_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.263756"},{"key":"e_1_2_1_2_38_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.14.4.699"},{"key":"e_1_2_1_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.272431"},{"key":"e_1_2_1_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/5.533956"},{"key":"e_1_2_1_2_41_2","doi-asserted-by":"crossref","unstructured":"Lehre PF Yao X (2008) Crossover can be constructive when computing unique input output sequences. In: International conference on simulated evolution and learning SEAL\u201908. LNCS vol 5361. Springer Berlin pp 595\u2013604","DOI":"10.1007\/978-3-540-89694-4_60"},{"key":"e_1_2_1_2_42_2","unstructured":"Miller RE Arisha KA (2001) Fault coverage in networks by passive testing. In: International conference on internet computing IC\u20192001. CSREA Press USA pp 413\u2013419"},{"key":"e_1_2_1_2_43_2","doi-asserted-by":"publisher","DOI":"10.1002\/stvr.294"},{"key":"e_1_2_1_2_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.988709"},{"key":"e_1_2_1_2_45_2","doi-asserted-by":"publisher","DOI":"10.1063\/1.1699114"},{"key":"e_1_2_1_2_46_2","doi-asserted-by":"crossref","unstructured":"Petrenko A (2001) Fault model-driven test derivation from finite state models: Annotated bibliography. In: 4th summer school on modeling and verification of parallel processes MOVEP\u201900. LNCS vol 2067. Springer Berlin pp 196\u2013205","DOI":"10.1007\/3-540-45510-8_10"},{"key":"e_1_2_1_2_47_2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1689(199912)9:4<263::AID-STVR190>3.0.CO;2-Y"},{"key":"e_1_2_1_2_48_2","doi-asserted-by":"crossref","unstructured":"Petrenko A Yevtushenko N von Bochmann G (1996) Fault models for testing in context. In: Formal description techniques for distributed systems and communication protocols (IX) and protocol specification testing and verification (XVI). Chapman & Hall London pp 163\u2013178","DOI":"10.1007\/978-0-387-35079-0_10"},{"key":"e_1_2_1_2_49_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jlap.2007.03.002"},{"key":"e_1_2_1_2_50_2","doi-asserted-by":"crossref","unstructured":"Rodr\u00edguez I (2009) A general testability theory. In: International conference on concurrency theory CONCUR\u201909. LNCS vol 5710. Springer Berlin pp 572\u2013586","DOI":"10.1007\/978-3-642-04081-8_38"},{"key":"e_1_2_1_2_51_2","doi-asserted-by":"crossref","unstructured":"Rabanal P Rodr\u00edguez I Rubio F (2007) Using river formation dynamics to design heuristic algorithms. In: Unconventional computation UC\u201907. LNCS vol 4618. Springer Berlin pp 163\u2013177","DOI":"10.1007\/978-3-540-73554-0_16"},{"key":"e_1_2_1_2_52_2","doi-asserted-by":"crossref","unstructured":"Rabanal P Rodr\u00edguez I Rubio F (2008) Finding minimum spanning\/distances trees by using river formation dynamics. In: Ant colony optimization and swarm intelligence ANTS\u201908. LNCS vol 5217. Springer Berlin pp 60\u201371","DOI":"10.1007\/978-3-540-87527-7_6"},{"key":"e_1_2_1_2_53_2","doi-asserted-by":"crossref","unstructured":"Rabanal P Rodr\u00edguez I Rubio F (2009) Applying river formation dynamics to solve NP-complete problems. In: Chiong R (ed) Nature-inspired algorithms for optimisation. Studies in computational intelligence vol 193. Springer Berlin pp 333\u2013368","DOI":"10.1007\/978-3-642-00267-0_12"},{"key":"e_1_2_1_2_54_2","doi-asserted-by":"crossref","unstructured":"Rabanal P Rodr\u00edguez I Rubio F (2009) A formal approach to heuristically test restorable systems. In: International colloquium on theoretical aspects of computing ICTAC\u201909. LNCS vol 5684. Springer Berlin pp 292\u2013306","DOI":"10.1007\/978-3-642-03466-4_19"},{"key":"e_1_2_1_2_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/318951.319003"},{"key":"e_1_2_1_2_56_2","doi-asserted-by":"publisher","DOI":"10.1016\/0169-7552(88)90064-5"},{"key":"e_1_2_1_2_57_2","unstructured":"Sidhu D Leung T-K (1988) Fault coverage of protocol test methods. In: Networks: evolution or revolution. Seventh annual joint conference of the IEEE computer and communications societies INFOCOM \u201988. IEEE Computer Society New York pp 80\u201385"},{"key":"e_1_2_1_2_58_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.16602"},{"key":"e_1_2_1_2_59_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480192239190"},{"key":"e_1_2_1_2_60_2","doi-asserted-by":"crossref","unstructured":"Srivastava PR Rai VK (2009) An ant colony optimization approach to test sequence generation for control flow based software testing. In: Information systems technology and management. Communications in computer and information science vol 31. Springer Berlin pp 345\u2013346","DOI":"10.1007\/978-3-642-00405-6_40"},{"key":"e_1_2_1_2_61_2","unstructured":"Tassey G (2002) The economic impacts of inadequate infrastructure for software testing. Technical report National Institute of Standards and Technology"},{"key":"e_1_2_1_2_62_2","doi-asserted-by":"publisher","DOI":"10.1016\/0140-3664(87)90104-6"},{"key":"e_1_2_1_2_63_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018551716639"},{"key":"e_1_2_1_2_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/267580.267590"}],"container-title":["Formal Aspects of Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00165-011-0206-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00165-011-0206-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1007\/s00165-011-0206-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T15:57:17Z","timestamp":1641484637000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1007\/s00165-011-0206-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":64,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.1007\/s00165-011-0206-3"],"URL":"https:\/\/doi.org\/10.1007\/s00165-011-0206-3","relation":{},"ISSN":["0934-5043","1433-299X"],"issn-type":[{"value":"0934-5043","type":"print"},{"value":"1433-299X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9]]}}}