Abstract
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 \(72\% \sim 86\%\) fuzzing time as compared to state-of-the-art fuzzers.
Chapter PDF
Similar content being viewed by others
References
AppSpider. https://www.rapid7.com/products/appspider
BurpSuite. https://portswigger.net/burp
Fuzzapi. https://github.com/Fuzzapi/fuzzapi
TnT-Fuzzer. https://github.com/Teebytes/TnT-Fuzzer
CVE-2018-1257. Available from MITRE, CVE-ID CVE-2018-1257 (Dec 6 2017), https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2018-1257
CVE-2018-1275. Available from MITRE, CVE-ID CVE-2018-1275 (Dec 6 2017), https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2018-1275
CVE-2017-18349. Available from MITRE, CVE-ID CVE-2017-18349 (Oct 23 2018), https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2017-18349
CVE-2018-15756. Available from MITRE, CVE-ID CVE-2018-15756 (Aug 23 2018), https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2018-15756
CVE-2020-5397. Available from MITRE, CVE-ID CVE-2020-5397 (Jan 3 2020), https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2020-5397
CVE-2020-5398. Available from MITRE, CVE-ID CVE-2020-5398 (Jan 3 2020), https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2020-5398
CVE-2020-5421. Available from MITRE, CVE-ID CVE-2020-5421 (Jan 3 2020), https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2020-5421
Arcuri, A.: RESTful API automated test case generation with EvoMaster. ACM Trans. Softw. Eng. Methodol. 28(1), 3:1–3:37 (2019), https://doi.org/10.1145/3293455
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–758. IEEE/ACM (2019), https://doi.org/10.1109/ICSE.2019.00083
Aycock, J.: A brief history of just-in-time. ACM Comput. Surv. 35(2), 97–113 (2003), https://doi.org/10.1145/857076.857077
Baker, P., Dai, Z.R., Grabowski, J., Schieferdecker, I., Williams, C.: Model-driven Testing: Using the UML Testing Profile. Springer Science & Business Media (2007)
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
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/
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–533. Springer (2011)
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
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
Chodorow, K.: MongoDB: The Definitive Guide: Powerful and Scalable Data Storage. O’Reilly Media, Inc. (2013)
Cortesi, A., Hils, M., Kriechbaumer, T.: MitmProxy: A free and open source interactive HTTPS proxy (2010), https://mitmproxy.org
Cotroneo, D., Iannillo, A.K., Natella, R.: Evolutionary fuzzing of android OS vendor system services. Empirical Software Engineering 24(6), 3630–3658 (2019), https://doi.org/10.1007/s10664-019-09725-6
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–252. ACM (1977), https://doi.org/10.1145/512950.512973
Cox, N.: Directory Services: Design, Implementation and Management. Elsevier (2001)
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–190. IEEE Computer Society (2018), https://doi.org/10.1109/EDOC.2018.00031
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–1502. ACM (2015), https://doi.org/10.1145/2740908.2743045
Fielding, R.: Representational state transfer. Architectural Styles and the Design of Netowork-based Software Architecture pp. 76–85 (2000)
Goessner, S.: JSONPath - XPath for JSON. http://goessner.net/articles/JsonPath p. 48 (2007)
Google: Android Monkey. https://developer.android.com/studio/test/monkey
Hafif, O., Spiderlabs, T.: Reflected file download: A new web attack vector. Trustwave. Retrieved March 15, 2016 (2014), https://bit.ly/2F8YZEp
Hao, M.: Fastjson 1.2.68 and earlier remote code execution vulnerability threat alert. Tech. rep., NSFOCUS, Inc. (Jun 2020), https://bit.ly/3iG0jwh
Jensen, S.H., Møller, 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. 5673, pp. 238–255. Springer (2009), https://doi.org/10.1007/978-3-642-03237-0_17
Joy, B., Steele, G., Gosling, J., Bracha, G.: The Java language specification (2000)
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
Martin-Lopez, A., Segura, S., Ruiz-Cortés, 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–414. Springer (2019), https://doi.org/10.1007/978-3-030-33702-5_31
Møller, A., Bakic, A., Moran, J., et al.: Package dk.brics.automaton. Aarhus University (Jul 4 2017), https://www.brics.dk/automaton/
Møller, A., Schwartzbach, M.I.: Static program analysis. Notes. Feb (2012)
Morlitz, D.: HTTP archive file (May 2002), US Patent App. 09/726,985
OAI (OpenAPI Initiative): The OpenAPI specification. https://github.com/OAI/OpenAPI-Specification
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/
Ouyang, L.: Bayesian inference of regular expressions from human-generated example strings. CoRR abs/1805.08427 (2018), http://arxiv.org/abs/1805.08427
Pham, V., Böhme, 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–553. ACM (2016), https://doi.org/10.1145/2970276.2970316
Raychev, V., Vechev, M.T., Krause, A.: Predicting program properties from “big code”. 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–124. ACM (2015), https://doi.org/10.1145/2676726.2677009
Scheurer, D., Hähnle, 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–73 (2016), https://doi.org/10.1007/978-3-319-47846-3_5
Thompson, K.: Programming techniques: Regular expression search algorithm. Commun. ACM 11(6), 419–422 (Jun 1968), https://doi.org/10.1145/363347.363387
Vu, H., Fertig, T., Braun, P.: Towards model-driven hypermedia testing for RESTful systems. In: Majchrzak, T.A., Traverso, P., Krempels, K..H., é rie 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–343. SciTePress (2017), https://doi.org/10.5220/0006353403400343
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–44. IEEE Computer Society (2008), https://doi.org/10.1109/WSE.2008.4655394
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2021 The Author(s)
About this paper
Cite this paper
Chen, Y., Yang, Y., Lei, Z., Xia, M., Qi, Z. (2021). Bootstrapping Automated Testing for RESTful Web Services. In: Guerra, E., Stoelinga, M. (eds) Fundamental Approaches to Software Engineering. FASE 2021. Lecture Notes in Computer Science(), vol 12649. Springer, Cham. https://doi.org/10.1007/978-3-030-71500-7_3
Download citation
DOI: https://doi.org/10.1007/978-3-030-71500-7_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-71499-4
Online ISBN: 978-3-030-71500-7
eBook Packages: Computer ScienceComputer Science (R0)