{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T10:03:16Z","timestamp":1770458596001,"version":"3.49.0"},"publisher-location":"Cham","reference-count":48,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030714994","type":"print"},{"value":"9783030715007","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,20]],"date-time":"2021-03-20T00:00:00Z","timestamp":1616198400000},"content-version":"vor","delay-in-days":78,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Modern RESTful services expose RESTful APIs to integrate with diversified applications. Most RESTful API parameters are weakly typed, which greatly increases the possible input value space. This poses difficulties for automated testing tools to generate effective test cases to reveal web service defects related to parameter validation. We call this phenomenon the type collapse problem. To remedy this problem, we introduce FET (Format-encoded Type) techniques, including the FET, the FET lattice, and the FET inference to model fine-grained information for API parameters. Enhanced by FET techniques, automated testing tools can generate targeted test cases. We demonstrate Leif, a trace-driven fuzzing tool, as a proof-of-concept implementation of FET techniques. Experiment results on 27 commercial services show that FET inference precisely captures documented parameter definitions, which helps Leif to discover 11 new bugs and reduce <jats:inline-formula><jats:alternatives><jats:tex-math>$$72\\% \\sim 86\\%$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                    <mml:mrow>\n                      <mml:mn>72<\/mml:mn>\n                      <mml:mo>%<\/mml:mo>\n                      <mml:mo>\u223c<\/mml:mo>\n                      <mml:mn>86<\/mml:mn>\n                      <mml:mo>%<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:math><\/jats:alternatives><\/jats:inline-formula> fuzzing time as compared to state-of-the-art fuzzers.<\/jats:p>","DOI":"10.1007\/978-3-030-71500-7_3","type":"book-chapter","created":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T13:12:14Z","timestamp":1616159534000},"page":"46-66","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Bootstrapping Automated Testing for RESTful Web Services"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7209-2771","authenticated-orcid":false,"given":"Yixiong","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9890-8196","authenticated-orcid":false,"given":"Zhanyao","family":"Lei","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5899-0295","authenticated-orcid":false,"given":"Mingyuan","family":"Xia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2730-2319","authenticated-orcid":false,"given":"Zhengwei","family":"Qi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,20]]},"reference":[{"key":"3_CR1","unstructured":"AppSpider. https:\/\/www.rapid7.com\/products\/appspider"},{"key":"3_CR2","unstructured":"BurpSuite. https:\/\/portswigger.net\/burp"},{"key":"3_CR3","unstructured":"Fuzzapi. https:\/\/github.com\/Fuzzapi\/fuzzapi"},{"key":"3_CR4","unstructured":"TnT-Fuzzer. https:\/\/github.com\/Teebytes\/TnT-Fuzzer"},{"key":"3_CR5","unstructured":"CVE-2018-1257. Available from MITRE, CVE-ID CVE-2018-1257 (Dec\u00a06 2017), https:\/\/cve.mitre.org\/cgi-bin\/cvename.cgi?name=CVE-2018-1257"},{"key":"3_CR6","unstructured":"CVE-2018-1275. Available from MITRE, CVE-ID CVE-2018-1275 (Dec\u00a06 2017), https:\/\/cve.mitre.org\/cgi-bin\/cvename.cgi?name=CVE-2018-1275"},{"key":"3_CR7","unstructured":"CVE-2017-18349. Available from MITRE, CVE-ID CVE-2017-18349 (Oct\u00a023 2018), https:\/\/cve.mitre.org\/cgi-bin\/cvename.cgi?name=CVE-2017-18349"},{"key":"3_CR8","unstructured":"CVE-2018-15756. Available from MITRE, CVE-ID CVE-2018-15756 (Aug\u00a023 2018), https:\/\/cve.mitre.org\/cgi-bin\/cvename.cgi?name=CVE-2018-15756"},{"key":"3_CR9","unstructured":"CVE-2020-5397. Available from MITRE, CVE-ID CVE-2020-5397 (Jan\u00a03 2020), https:\/\/cve.mitre.org\/cgi-bin\/cvename.cgi?name=CVE-2020-5397"},{"key":"3_CR10","unstructured":"CVE-2020-5398. Available from MITRE, CVE-ID CVE-2020-5398 (Jan\u00a03 2020), https:\/\/cve.mitre.org\/cgi-bin\/cvename.cgi?name=CVE-2020-5398"},{"key":"3_CR11","unstructured":"CVE-2020-5421. Available from MITRE, CVE-ID CVE-2020-5421 (Jan\u00a03 2020), https:\/\/cve.mitre.org\/cgi-bin\/cvename.cgi?name=CVE-2020-5421"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Arcuri, A.: RESTful API automated test case generation with EvoMaster. ACM Trans. Softw. Eng. Methodol. 28(1), 3:1\u20133:37 (2019), https:\/\/doi.org\/10.1145\/3293455","DOI":"10.1145\/3293455"},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"Atlidakis, V., Godefroid, P., Polishchuk, M.: RESTler: Stateful REST API fuzzing. In: Atlee, J.M., Bultan, T., Whittle, J. (eds.) Proceedings of the 41st International Conference on Software Engineering, ICSE 2019, Montreal, QC, Canada, May 25-31, 2019. pp. 748\u2013758. IEEE\/ACM (2019), https:\/\/doi.org\/10.1109\/ICSE.2019.00083","DOI":"10.1109\/ICSE.2019.00083"},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"Aycock, J.: A brief history of just-in-time. ACM Comput. Surv. 35(2), 97\u2013113 (2003), https:\/\/doi.org\/10.1145\/857076.857077","DOI":"10.1145\/857076.857077"},{"key":"3_CR15","unstructured":"Baker, P., Dai, Z.R., Grabowski, J., Schieferdecker, I., Williams, C.: Model-driven Testing: Using the UML Testing Profile. Springer Science & Business Media (2007)"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Berners-Lee, T., Fielding, R., Masinterm, L.: RFC3986: Uniform Resource Identifier (URI): Generic Syntax. Internet Engineering Task Force (Jan 2005), https:\/\/www.rfc-editor.org\/info\/rfc3986","DOI":"10.17487\/rfc3986"},{"key":"3_CR17","unstructured":"Breslaw, D., Bekerman, D.: How Mirai uses STOMP protocol to launch DDoS attacks. Tech. rep., Imperva Inc. (Nov15 2016), https:\/\/www.imperva.com\/blog\/mirai-stomp-protocol-ddos\/"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"Chandrashekhar, R., Mardithaya, M., Thilagam, S., Saha, D.: SQL injection attack mechanisms and prevention techniques. In: International Conference on Advanced Computing, Networking and Security. pp. 524\u2013533. Springer (2011)","DOI":"10.1007\/978-3-642-29280-4_61"},{"key":"3_CR19","unstructured":"Chen, Y., Yang, Y., Lei, Z., Xia, M., Qi, Z.: The public dataset of Leif evaluation (Jan 2021), https:\/\/doi.org\/10.6084\/m9.figshare.12377150"},{"key":"3_CR20","unstructured":"Chen, Y., Yang, Y., Lei, Z., Xia, M., Qi, Z.: The ubiquitous FET lattice model and verification (Jan 2021), https:\/\/doi.org\/10.6084\/m9.figshare.13622720"},{"key":"3_CR21","unstructured":"Chodorow, K.: MongoDB: The Definitive Guide: Powerful and Scalable Data Storage. O\u2019Reilly Media, Inc. (2013)"},{"key":"3_CR22","unstructured":"Cortesi, A., Hils, M., Kriechbaumer, T.: MitmProxy: A free and open source interactive HTTPS proxy (2010), https:\/\/mitmproxy.org"},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"Cotroneo, D., Iannillo, A.K., Natella, R.: Evolutionary fuzzing of android OS vendor system services. Empirical Software Engineering 24(6), 3630\u20133658 (2019), https:\/\/doi.org\/10.1007\/s10664-019-09725-6","DOI":"10.1007\/s10664-019-09725-6"},{"key":"3_CR24","doi-asserted-by":"crossref","unstructured":"Cousot, P., Cousot, R.: Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In: Graham, R.M., Harrison, M.A., Sethi, R. (eds.) Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, Los Angeles, California, USA, January 1977. pp. 238\u2013252. ACM (1977), https:\/\/doi.org\/10.1145\/512950.512973","DOI":"10.1145\/512950.512973"},{"key":"3_CR25","unstructured":"Cox, N.: Directory Services: Design, Implementation and Management. Elsevier (2001)"},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"Ed-Douibi, H., Izquierdo, J.L.C., Cabot, J.: Automatic generation of test cases for REST APIs: A specification-based approach. In: 22nd IEEE International Enterprise Distributed Object Computing Conference, EDOC 2018, Stockholm, Sweden, October 16-19, 2018. pp. 181\u2013190. IEEE Computer Society (2018), https:\/\/doi.org\/10.1109\/EDOC.2018.00031","DOI":"10.1109\/EDOC.2018.00031"},{"key":"3_CR27","doi-asserted-by":"crossref","unstructured":"Fertig, T., Braun, P.: Model-driven testing of RESTful APIs. In: Gangemi, A., Leonardi, S., Panconesi, A. (eds.) Proceedings of the 24th International Conference on World Wide Web Companion, WWW 2015, Florence, Italy, May 18-22, 2015 - Companion Volume. pp. 1497\u20131502. ACM (2015), https:\/\/doi.org\/10.1145\/2740908.2743045","DOI":"10.1145\/2740908.2743045"},{"key":"3_CR28","unstructured":"Fielding, R.: Representational state transfer. Architectural Styles and the Design of Netowork-based Software Architecture pp. 76\u201385 (2000)"},{"key":"3_CR29","unstructured":"Goessner, S.: JSONPath - XPath for JSON. http:\/\/goessner.net\/articles\/JsonPath p.\u00a048 (2007)"},{"key":"3_CR30","unstructured":"Google: Android Monkey. https:\/\/developer.android.com\/studio\/test\/monkey"},{"key":"3_CR31","unstructured":"Hafif, O., Spiderlabs, T.: Reflected file download: A new web attack vector. Trustwave. Retrieved March 15, \u00a02016 (2014), https:\/\/bit.ly\/2F8YZEp"},{"key":"3_CR32","unstructured":"Hao, M.: Fastjson 1.2.68 and earlier remote code execution vulnerability threat alert. Tech. rep., NSFOCUS, Inc. (Jun 2020), https:\/\/bit.ly\/3iG0jwh"},{"key":"3_CR33","doi-asserted-by":"crossref","unstructured":"Jensen, S.H., M\u00f8ller, A., Thiemann, P.: Type analysis for JavaScript. In: Palsberg, J., Su, Z. (eds.) Static Analysis, 16th International Symposium, SAS 2009, Los Angeles, CA, USA, August 9-11, 2009. Proceedings. Lecture Notes in Computer Science, vol.\u00a05673, pp. 238\u2013255. Springer (2009), https:\/\/doi.org\/10.1007\/978-3-642-03237-0_17","DOI":"10.1007\/978-3-642-03237-0_17"},{"key":"3_CR34","unstructured":"Joy, B., Steele, G., Gosling, J., Bracha, G.: The Java language specification (2000)"},{"key":"3_CR35","doi-asserted-by":"crossref","unstructured":"Klyne, G., Newman, C.: RFC3339: Date and Time on the Internet: Timestamps. Internet Engineering Task Force (Jul 2002), https:\/\/www.rfc-editor.org\/info\/rfc3339","DOI":"10.17487\/rfc3339"},{"key":"3_CR36","doi-asserted-by":"crossref","unstructured":"Martin-Lopez, A., Segura, S., Ruiz-Cort\u00e9s, A.: A catalogue of inter-parameter dependencies in RESTful web APIs. In: Yangui, S., Rodriguez, I.B., Drira, K., Tari, Z. (eds.) Service-Oriented Computing - 17th International Conference, ICSOC 2019, Toulouse, France, October 28-31, 2019, Proceedings. Lecture Notes in Computer Science, vol. 11895, pp. 399\u2013414. Springer (2019), https:\/\/doi.org\/10.1007\/978-3-030-33702-5_31","DOI":"10.1007\/978-3-030-33702-5_31"},{"key":"3_CR37","unstructured":"M\u00f8ller, A., Bakic, A., Moran, J., et al.: Package dk.brics.automaton. Aarhus University (Jul\u00a04 2017), https:\/\/www.brics.dk\/automaton\/"},{"key":"3_CR38","unstructured":"M\u00f8ller, A., Schwartzbach, M.I.: Static program analysis. Notes. Feb (2012)"},{"key":"3_CR39","unstructured":"Morlitz, D.: HTTP archive file (May 2002), US Patent App. 09\/726,985"},{"key":"3_CR40","unstructured":"OAI (OpenAPI Initiative): The OpenAPI specification. https:\/\/github.com\/OAI\/OpenAPI-Specification"},{"key":"3_CR41","unstructured":"Open API CSA Working Group: Open API survey report. Tech. rep., Cloud Security Alliance (Sep 2019), https:\/\/cloudsecurityalliance.org\/blog\/2019\/09\/11\/open-api-survey-report\/"},{"key":"3_CR42","unstructured":"Ouyang, L.: Bayesian inference of regular expressions from human-generated example strings. CoRR abs\/1805.08427 (2018), http:\/\/arxiv.org\/abs\/1805.08427"},{"key":"3_CR43","doi-asserted-by":"crossref","unstructured":"Pham, V., B\u00f6hme, M., Roychoudhury, A.: Model-based whitebox fuzzing for program binaries. In: Lo, D., Apel, S., Khurshid, S. (eds.) Proceedings of the 31st IEEE\/ACM International Conference on Automated Software Engineering, ASE 2016, Singapore, September 3-7, 2016. pp. 543\u2013553. ACM (2016), https:\/\/doi.org\/10.1145\/2970276.2970316","DOI":"10.1145\/2970276.2970316"},{"key":"3_CR44","doi-asserted-by":"crossref","unstructured":"Raychev, V., Vechev, M.T., Krause, A.: Predicting program properties from \u201cbig code\u201d. In: Rajamani, S.K., Walker, D. (eds.) Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2015, Mumbai, India, January 15-17, 2015. pp. 111\u2013124. ACM (2015), https:\/\/doi.org\/10.1145\/2676726.2677009","DOI":"10.1145\/2676726.2677009"},{"key":"3_CR45","doi-asserted-by":"crossref","unstructured":"Scheurer, D., H\u00e4hnle, R., Bubel, R.: A general lattice model for merging symbolic execution branches. In: Ogata, K., Lawford, M., Liu, S. (eds.) Formal Methods and Software Engineering - 18th International Conference on Formal Engineering Methods, ICFEM 2016, Tokyo, Japan, November 14-18, 2016, Proceedings. Lecture Notes in Computer Science, vol. 10009, pp. 57\u201373 (2016), https:\/\/doi.org\/10.1007\/978-3-319-47846-3_5","DOI":"10.1007\/978-3-319-47846-3_5"},{"key":"3_CR46","doi-asserted-by":"crossref","unstructured":"Thompson, K.: Programming techniques: Regular expression search algorithm. Commun. ACM 11(6), 419\u2013422 (Jun 1968), https:\/\/doi.org\/10.1145\/363347.363387","DOI":"10.1145\/363347.363387"},{"key":"3_CR47","doi-asserted-by":"crossref","unstructured":"Vu, H., Fertig, T., Braun, P.: Towards model-driven hypermedia testing for RESTful systems. In: Majchrzak, T.A., Traverso, P., Krempels, K..H., \u00e9\u00a0rie Monfort, V. (eds.) Proceedings of the 13th International Conference on Web Information Systems and Technologies, WEBIST 2017, Porto, Portugal, April 25-27, 2017. pp. 340\u2013343. SciTePress (2017), https:\/\/doi.org\/10.5220\/0006353403400343","DOI":"10.5220\/0006353403400343"},{"key":"3_CR48","doi-asserted-by":"crossref","unstructured":"Yuan, Q., Wu, J., Liu, C., Zhang, L.: A model driven approach toward business process test case generation. In: Liu, C., Ricca, F. (eds.) Proceedings of the 10th IEEE International Symposium on Web Systems Evolution, WSE 2010, 3-4 October 2008, Beijing, China. pp. 41\u201344. IEEE Computer Society (2008), https:\/\/doi.org\/10.1109\/WSE.2008.4655394","DOI":"10.1109\/WSE.2008.4655394"}],"container-title":["Lecture Notes in Computer Science","Fundamental Approaches to Software Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-71500-7_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,20]],"date-time":"2021-03-20T00:13:55Z","timestamp":1616199235000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-71500-7_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030714994","9783030715007"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-71500-7_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"20 March 2021","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":"Luxembourg City","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 March 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 April 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fase2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2021\/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":"52","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":"16","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":"31% - 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":"5,5","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 conference changed to an online format due to the COVID-19 pandemic.","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)"}}]}}