{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T05:19:13Z","timestamp":1743139153371,"version":"3.40.3"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031308253"},{"type":"electronic","value":"9783031308260"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T00:00:00Z","timestamp":1681948800000},"content-version":"vor","delay-in-days":109,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Bounded exhaustive input generation (BEG) is an effective approach to reveal software faults. However, existing BEG approaches require a precise specification of the <jats:italic>valid<\/jats:italic> inputs, i.e., a , that must be provided by the user. Writing s for BEG is challenging and time consuming, and they are seldom available in software.<\/jats:p><jats:p>In this paper, we introduce , an efficient approach that employs routines from the API of the software under test to perform BEG. Like API-based test generation approaches,  creates sequences of calls to methods from the API, and executes them to generate inputs. As opposed to existing BEG approaches,  does not require a  to be provided by the user. To make BEG from the API feasible,  implements three key pruning techniques: <jats:italic>(i)<\/jats:italic> discarding test sequences whose execution produces exceptions violating API usage rules, <jats:italic>(ii)<\/jats:italic> state matching to discard test sequences that produce inputs already created by previously explored test sequences, and <jats:italic>(iii)<\/jats:italic> the automated identification and use of a subset of methods from the API, called <jats:italic>builders<\/jats:italic>, that is sufficient to perform BEG.<\/jats:p><jats:p>Our experimental assessment shows that \u2019s efficiency and scalability is competitive with existing BEG approaches, without the need for s. We also show that  can assist the user in finding flaws in s, by (automatically) comparing inputs generated by  with those generated from a . Using this approach, we revealed several errors in s taken from the assessment of related tools, demonstrating the difficulties of writing precise s for BEG.<\/jats:p>","DOI":"10.1007\/978-3-031-30826-0_6","type":"book-chapter","created":{"date-parts":[[2023,4,19]],"date-time":"2023-04-19T18:02:59Z","timestamp":1681927379000},"page":"111-132","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Bounded Exhaustive Input Generation from Program APIs"],"prefix":"10.1007","author":[{"given":"Mariano","family":"Politano","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valeria","family":"Bengolea","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Facundo","family":"Molina","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nazareno","family":"Aguirre","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcelo F.","family":"Frias","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pablo","family":"Ponzio","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,4,20]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"Abad, P., Aguirre, N., Bengolea, V.S., Ciolek, D.A., Frias, M.F., Galeotti, J.P., Maibaum, T., Moscato, M.M., Rosner, N., Vissani, I.: Improving test generation under rich contracts by tight bounds and incremental SAT solving. In: Sixth IEEE International Conference on Software Testing, Verification and Validation, ICST 2013, Luxembourg, Luxembourg, March 18-22, 2013. pp. 21\u201330. IEEE Computer Society (2013)","DOI":"10.1109\/ICST.2013.46"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Ammann, P., Offutt, J.: Introduction to Software Testing. Cambridge University Press, Cambridge (2016)","DOI":"10.1017\/9781316771273"},{"key":"6_CR3","unstructured":"Andoni, A., Daniliuc, D., Khurshid, S., Marinov, D.: Evaluating the \"small scope hypothesis\". Tech. rep., MIT CSAIL (10 2002)"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Boyapati, C., Khurshid, S., Marinov, D.: Korat: automated testing based on java predicates. In: Frankl, P.G. (ed.) Proceedings of the International Symposium on Software Testing and Analysis, ISSTA 2002, Roma, Italy, July 22-24, 2002. pp. 123\u2013133. ACM (2002)","DOI":"10.1145\/566172.566191"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Braione, P., Denaro, G., Mattavelli, A., Pezz\u00e8, M.: Combining symbolic execution and search-based testing for programs with complex heap inputs. In: Bultan, T., Sen, K. (eds.) Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis, Santa Barbara, CA, USA, July 10 - 14, 2017. pp. 90\u2013101. ACM (2017)","DOI":"10.1145\/3092703.3092715"},{"key":"6_CR6","unstructured":"Cadar, C., Dunbar, D., Engler, D.R.: KLEE: unassisted and automatic generation of high-coverage tests for complex systems programs. In: Draves, R., van Renesse, R. (eds.) 8th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2008, December 8-10, 2008, San Diego, California, USA, Proceedings. pp. 209\u2013224. USENIX Association (2008)"},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"Chen, T.Y., Kuo, F.C., Liu, H., Poon, P.L., Towey, D., Tse, T.H., Zhou, Z.Q.: Metamorphic testing: A review of challenges and opportunities. ACM Comput. Surv. 51(1) (jan 2018)","DOI":"10.1145\/3143561"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Christakis, M., Godefroid, P.: Proving memory safety of the ANI windows image parser using compositional exhaustive testing. In: D\u2019Souza, D., Lal, A., Larsen, K.G. (eds.) Verification, Model Checking, and Abstract Interpretation - 16th International Conference, VMCAI 2015, Mumbai, India, January 12-14, 2015. Proceedings. Lecture Notes in Computer Science, vol.\u00a08931, pp. 373\u2013392. Springer (2015)","DOI":"10.1007\/978-3-662-46081-8_21"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Deng, X., Robby, Hatcliff, J.: Kiasan: A verification and test-case generation framework for java based on symbolic execution. In: Leveraging Applications of Formal Methods, Second International Symposium, ISoLA 2006, Paphos, Cyprus, 15-19 November 2006. p.\u00a0137. IEEE Computer Society (2006)","DOI":"10.1109\/ISoLA.2006.60"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Fraser, G., Arcuri, A.: Evosuite: automatic test suite generation for object-oriented software. In: Gyim\u00f3thy, T., Zeller, A. (eds.) SIGSOFT\/FSE\u201911 19th ACM SIGSOFT Symposium on the Foundations of Software Engineering (FSE-19) and ESEC\u201911: 13th European Software Engineering Conference (ESEC-13), Szeged, Hungary, September 5-9, 2011. pp. 416\u2013419. ACM (2011)","DOI":"10.1145\/2025113.2025179"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Gligoric, M., Gvero, T., Jagannath, V., Khurshid, S., Kuncak, V., Marinov, D.: Test generation through programming in UDITA. In: Kramer, J., Bishop, J., Devanbu, P.T., Uchitel, S. (eds.) Proceedings of the 32nd ACM\/IEEE International Conference on Software Engineering - Volume 1, ICSE 2010, Cape Town, South Africa, 1-8 May 2010. pp. 225\u2013234. ACM (2010)","DOI":"10.1145\/1806799.1806835"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Godefroid, P., Klarlund, N., Sen, K.: DART: directed automated random testing. In: Sarkar, V., Hall, M.W. (eds.) Proceedings of the ACM SIGPLAN 2005 Conference on Programming Language Design and Implementation, Chicago, IL, USA, June 12-15, 2005. pp. 213\u2013223. ACM (2005)","DOI":"10.1145\/1065010.1065036"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Godefroid, P., Levin, M.Y., Molnar, D.A.: SAGE: whitebox fuzzing for security testing. Commun. ACM 55(3), 40\u201344 (2012)","DOI":"10.1145\/2093548.2093564"},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Godefroid, P., Sen, K.: Combining model checking and testing. In: Clarke, E.M., Henzinger, T.A., Veith, H., Bloem, R. (eds.) Handbook of Model Checking, pp. 613\u2013649. Springer (2018)","DOI":"10.1007\/978-3-319-10575-8_19"},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Iosif, R.: Symmetry reduction criteria for software model checking. In: Bosnacki, D., Leue, S. (eds.) Model Checking of Software, 9th International SPIN Workshop, Grenoble, France, April 11-13, 2002, Proceedings. Lecture Notes in Computer Science, vol.\u00a02318, pp. 22\u201341. Springer (2002)","DOI":"10.1007\/3-540-46017-9_5"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Khurshid, S., Marinov, D.: Checking java implementation of a naming architecture using testera. Electron. Notes Theor. Comput. Sci. 55(3), 322\u2013342 (2001)","DOI":"10.1016\/S1571-0661(04)00260-9"},{"key":"6_CR17","unstructured":"Liskov, B., Guttag, J.: Program Development in Java: Abstraction, Specification, and Object-Oriented Design. Addison-Wesley Longman Publishing Co., Inc., USA, 1st edn. (2000)"},{"key":"6_CR18","doi-asserted-by":"crossref","unstructured":"Luckow, K.S., Pasareanu, C.S.: Symbolic pathfinder v7. ACM SIGSOFT Softw. Eng. Notes 39(1), \u00a01\u20135 (2014)","DOI":"10.1145\/2557833.2560571"},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"Ma, L., Artho, C., Zhang, C., Sato, H., Gmeiner, J., Ramler, R.: GRT: an automated test generator using orchestrated program analysis. In: Cohen, M.B., Grunske, L., Whalen, M. (eds.) 30th IEEE\/ACM International Conference on Automated Software Engineering, ASE 2015, Lincoln, NE, USA, November 9-13, 2015. pp. 842\u2013847. IEEE Computer Society (2015)","DOI":"10.1109\/ASE.2015.102"},{"key":"6_CR20","unstructured":"Marinov, D., Khurshid, S.: Testera: A novel framework for automated testing of java programs. In: 16th IEEE International Conference on Automated Software Engineering (ASE 2001), 26-29 November 2001, Coronado Island, San Diego, CA, USA. p.\u00a022. IEEE Computer Society (2001)"},{"key":"6_CR21","doi-asserted-by":"crossref","unstructured":"Molina, F., Ponzio, P., Aguirre, N., Frias, M.: EvoSpex: An evolutionary algorithm for learning postconditions. In: Proceedings of the 43rd ACM\/IEEE International Conference on Software Engineering ICSE 2021, Virtual (originally Madrid, Spain), 23-29 May 2021 (2021)","DOI":"10.1109\/ICSE43902.2021.00112"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"Myers, G.J., Sandler, C., Badgett, T.: The Art of Software Testing. Wiley Publishing, 3rd edn. (2011)","DOI":"10.1002\/9781119202486"},{"key":"6_CR23","doi-asserted-by":"crossref","unstructured":"Pacheco, C., Lahiri, S.K., Ernst, M.D., Ball, T.: Feedback-directed random test generation. In: 29th International Conference on Software Engineering (ICSE 2007), Minneapolis, MN, USA, May 20-26, 2007. pp. 75\u201384. IEEE Computer Society (2007)","DOI":"10.1109\/ICSE.2007.37"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"Pham, L.H., Le, Q.L., Phan, Q., Sun, J.: Concolic testing heap-manipulating programs. In: ter Beek, M.H., McIver, A., Oliveira, J.N. (eds.) Formal Methods - The Next 30 Years - Third World Congress, FM 2019, Porto, Portugal, October 7-11, 2019, Proceedings. Lecture Notes in Computer Science, vol. 11800, pp. 442\u2013461. Springer (2019)","DOI":"10.1007\/978-3-030-30942-8_27"},{"key":"6_CR25","unstructured":"Politano, M., Bengolea, V., Molina, F., Aguirre, N., Frias, M.F., Ponzio, P.: Efficient Bounded Exhaustive Input Generation from Program APIs paper\u2019s artifact. https:\/\/doi.org\/10.5281\/zenodo.7574758"},{"key":"6_CR26","unstructured":"Politano, M., Bengolea, V., Molina, F., Aguirre, N., Frias, M.F., Ponzio, P.: Efficient Bounded Exhaustive Input Generation from Program APIs paper\u2019s website. https:\/\/sites.google.com\/view\/bounded-exhaustive-api"},{"key":"6_CR27","doi-asserted-by":"crossref","unstructured":"Ponzio, P., Bengolea, V.S., Politano, M., Aguirre, N., Frias, M.F.: Automatically identifying sufficient object builders from module apis. In: H\u00e4hnle, R., van\u00a0der Aalst, W.M.P. (eds.) Fundamental Approaches to Software Engineering - 22nd International Conference, FASE 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Prague, Czech Republic, April 6-11, 2019, Proceedings. Lecture Notes in Computer Science, vol. 11424, pp. 427\u2013444. Springer (2019)","DOI":"10.1007\/978-3-030-16722-6_25"},{"key":"6_CR28","doi-asserted-by":"crossref","unstructured":"Robby, Dwyer, M.B., Hatcliff, J., Iosif, R.: Space-reduction strategies for model checking dynamic software. Electron. Notes Theor. Comput. Sci. 89(3), 499\u2013517 (2003)","DOI":"10.1016\/S1571-0661(05)80009-X"},{"key":"6_CR29","doi-asserted-by":"crossref","unstructured":"Rosner, N., Bengolea, V., Ponzio, P., Khalek, S.A., Aguirre, N., Frias, M.F., Khurshid, S.: Bounded exhaustive test input generation from hybrid invariants. SIGPLAN Not. 49(10), 655\u2013674 (oct 2014)","DOI":"10.1145\/2714064.2660232"},{"key":"6_CR30","doi-asserted-by":"crossref","unstructured":"Rosner, N., Geldenhuys, J., Aguirre, N., Visser, W., Frias, M.F.: BLISS: improved symbolic execution by bounded lazy initialization with SAT support. IEEE Trans. Software Eng. 41(7), 639\u2013660 (2015)","DOI":"10.1109\/TSE.2015.2389225"},{"key":"6_CR31","unstructured":"Rosner, N., Pombo, C.G.L., Aguirre, N., Jaoua, A., Mili, A., Frias, M.F.: Parallel bounded verification of alloy models by transcoping. In: Cohen, E., Rybalchenko, A. (eds.) Verified Software: Theories, Tools, Experiments - 5th International Conference, VSTTE 2013, Menlo Park, CA, USA, May 17-19, 2013, Revised Selected Papers. Lecture Notes in Computer Science, vol.\u00a08164, pp. 88\u2013107. Springer (2013)"},{"key":"6_CR32","unstructured":"Siddiqui, J.H., Khurshid, S.: An empirical study of structural constraint solving techniques. In: Breitman, K.K., Cavalcanti, A. (eds.) Formal Methods and Software Engineering, 11th International Conference on Formal Engineering Methods, ICFEM 2009, Rio de Janeiro, Brazil, December 9-12, 2009. Proceedings. Lecture Notes in Computer Science, vol.\u00a05885, pp. 88\u2013106. Springer (2009)"},{"key":"6_CR33","doi-asserted-by":"crossref","unstructured":"Sullivan, K.J., Yang, J., Coppit, D., Khurshid, S., Jackson, D.: Software assurance by bounded exhaustive testing. In: Avrunin, G.S., Rothermel, G. (eds.) Proceedings of the ACM\/SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2004, Boston, Massachusetts, USA, July 11-14, 2004. pp. 133\u2013142. ACM (2004)","DOI":"10.1145\/1007512.1007531"},{"key":"6_CR34","doi-asserted-by":"crossref","unstructured":"Visser, W., Mehlitz, P.C.: Model checking programs with java pathfinder. In: Godefroid, P. (ed.) Model Checking Software, 12th International SPIN Workshop, San Francisco, CA, USA, August 22-24, 2005, Proceedings. Lecture Notes in Computer Science, vol.\u00a03639, p.\u00a027. Springer (2005)","DOI":"10.1007\/11537328_5"},{"key":"6_CR35","doi-asserted-by":"crossref","unstructured":"Visser, W., Pasareanu, C.S., Pel\u00e1nek, R.: Test input generation for java containers using state matching. In: Pollock, L.L., Pezz\u00e8, M. (eds.) Proceedings of the ACM\/SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2006, Portland, Maine, USA, July 17-20, 2006. pp. 37\u201348. ACM (2006)","DOI":"10.1145\/1146238.1146243"},{"key":"6_CR36","unstructured":"Xie, T., Marinov, D., Notkin, D.: Rostra: A framework for detecting redundant object-oriented unit tests. In: 19th IEEE International Conference on Automated Software Engineering (ASE 2004), 20-25 September 2004, Linz, Austria. pp. 196\u2013205. IEEE Computer Society (2004)"}],"container-title":["Lecture Notes in Computer Science","Fundamental Approaches to Software Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-30826-0_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,22]],"date-time":"2023-05-22T22:01:59Z","timestamp":1684792919000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-30826-0_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031308253","9783031308260"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-30826-0_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"20 April 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FASE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Fundamental Approaches to Software Engineering","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paris","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 April 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 April 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fase2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2023\/fase","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"50","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"24% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6-7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The proceedings also include 2 tool papers, 2 NIER papers, and 2 competition papers","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}