{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T18:52:11Z","timestamp":1777488731444,"version":"3.51.4"},"reference-count":81,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,7,9]],"date-time":"2022-07-09T00:00:00Z","timestamp":1657324800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Priv. Secur."],"published-print":{"date-parts":[[2022,11,30]]},"abstract":"<jats:p>Fuzz testing repeatedly assails software with random inputs in order to trigger unexpected program behaviors, such as crashes or timeouts, and has historically revealed serious security vulnerabilities. In this article, we present HotFuzz, a framework for automatically discovering Algorithmic Complexity (AC) time and space vulnerabilities in Java libraries. HotFuzz uses micro-fuzzing, a genetic algorithm that evolves arbitrary Java objects in order to trigger the worst-case performance for a method under test. We define Small Recursive Instantiation (SRI) as a technique to derive seed inputs represented as Java objects to micro-fuzzing. After micro-fuzzing, HotFuzz synthesizes test cases that triggered AC vulnerabilities into Java programs and monitors their execution in order to reproduce vulnerabilities outside the fuzzing framework. HotFuzz outputs those programs that exhibit high resource utilization as witnesses for AC vulnerabilities in a Java library. We evaluate HotFuzz over the Java Runtime Environment (JRE), the 100 most popular Java libraries on Maven, and challenges contained in the DARPA Space and Time Analysis for Cybersecurity (STAC) program. We evaluate SRI\u2019s effectiveness by comparing the performance of micro-fuzzing with SRI, measured by the number of AC vulnerabilities detected, to simply using empty values as seed inputs. In this evaluation, we verified known AC vulnerabilities, discovered previously unknown AC vulnerabilities that we responsibly reported to vendors, and received confirmation from both IBM and Oracle. Our results demonstrate that micro-fuzzing finds AC vulnerabilities in real-world software, and that micro-fuzzing with SRI-derived seed inputs outperforms using empty values in both the temporal and spatial domains.<\/jats:p>","DOI":"10.1145\/3532184","type":"journal-article","created":{"date-parts":[[2022,5,20]],"date-time":"2022-05-20T12:27:44Z","timestamp":1653049664000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["HotFuzz: Discovering Temporal and Spatial Denial-of-Service Vulnerabilities Through Guided Micro-Fuzzing"],"prefix":"10.1145","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5918-2983","authenticated-orcid":false,"given":"William","family":"Blair","sequence":"first","affiliation":[{"name":"Boston University, Boston, MA, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6727-1452","authenticated-orcid":false,"given":"Andrea","family":"Mambretti","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5311-451X","authenticated-orcid":false,"given":"Sajjad","family":"Arshad","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0478-4610","authenticated-orcid":false,"given":"Michael","family":"Weissbacher","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6968-0273","authenticated-orcid":false,"given":"William","family":"Robertson","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9988-6873","authenticated-orcid":false,"given":"Engin","family":"Kirda","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5038-2682","authenticated-orcid":false,"given":"Manuel","family":"Egele","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,9]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"2006. The Java Virtual Machine Specification. Retrieved July 16 2021 from https:\/\/docs.oracle.com\/javase\/specs\/jvms\/se8\/html\/index.html."},{"key":"e_1_3_2_3_2","unstructured":"2006. The JVM Tool Interface (JVM TI): How VM Agents Work. Retrieved July 16 2021 from https:\/\/www.oracle.com\/technetwork\/articles\/javase\/index-140680.html."},{"key":"e_1_3_2_4_2","unstructured":"2015. JSON-Java Project. Retrieved July 16 2021 from https:\/\/stleary.github.io\/JSON-java\/."},{"key":"e_1_3_2_5_2","unstructured":"2018. CVE-2018-1517. Retrieved July 16 2021 from https:\/\/cve.mitre.org\/cgi-bin\/cvename.cgi?name=CVE-2018-1517."},{"key":"e_1_3_2_6_2","unstructured":"2018. CVE-2018-5390. Retrieved July 16 2021 from https:\/\/nvd.nist.gov\/vuln\/detail\/CVE-2018-5390#vulnCurrentDescriptionTitle."},{"key":"e_1_3_2_7_2","unstructured":"2019. Arithmetic in JDK BigDecimal. Retrieved July 16 2021 from https:\/\/hg.openjdk.java.net\/jdk8u\/jdk8u-dev\/jdk\/file\/d13abc740e42\/src\/share\/classes\/java\/math\/BigDecimal.java#l4464."},{"key":"e_1_3_2_8_2","unstructured":"2019. CVE-2019-6486. Retrieved July 16 2021 from https:\/\/cve.mitre.org\/cgi-bin\/cvename.cgi?name=CVE-2019-6486."},{"key":"e_1_3_2_9_2","unstructured":"2019. Oracle Critical Patch Update Advisory - January 2019. Retrieved July 16 2021 from https:\/\/www.oracle.com\/technetwork\/security-advisory\/cpujan2019-5072801.html."},{"key":"e_1_3_2_10_2","unstructured":"2021. CVE-2021-22312. Retrieved July 16 2021 from https:\/\/cve.mitre.org\/cgi-bin\/cvename.cgi?name=CVE-2021-22312."},{"key":"e_1_3_2_11_2","unstructured":"https:\/\/cve.mitre.org\/cgi-bin\/cvename.cgi?name=CVE-2021-25252 2021 CVE-2021-25252"},{"key":"e_1_3_2_12_2","unstructured":"2021. CVE-2021-3492. Retrieved July 16 2021 from https:\/\/cve.mitre.org\/cgi-bin\/cvename.cgi?name=CVE-2021-3492."},{"key":"e_1_3_2_13_2","unstructured":"2021. JSONML Tutorials Point. Retrieved July 16 2021 from https:\/\/www.tutorialspoint.com\/org_json\/org_json_jsonml.htm."},{"key":"e_1_3_2_14_2","unstructured":"2021. libFuzzer \u2013 A library for coverage-guided fuzz testing. Retrieved July 16 2021 from https:\/\/llvm.org\/docs\/LibFuzzer.html."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2019.23371"},{"key":"e_1_3_2_16_2","volume-title":"Proceedings of the Asia-Pacific Software Engineering Conference","author":"Awadhutkar Payas","year":"2017","unstructured":"Payas Awadhutkar, Ganesh Ram Santhanam, Benjamin Holland, and Suresh Kothari. 2017. Intelligence amplifying loop characterizations for detecting algorithmic complexity vulnerabilities. In Proceedings of the Asia-Pacific Software Engineering Conference."},{"key":"e_1_3_2_17_2","volume-title":"Proceedings of the Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering","author":"Babi\u0107 Domagoj","year":"2019","unstructured":"Domagoj Babi\u0107, Stefan Bucur, Yaohui Chen, Franjo Ivan\u010di\u0107, Tim King, Markus Kusano, Caroline Lemieux, L\u00e1szl\u00f3 Szekeres, and Wei Wang. 2019. Fudge: Fuzz driver generation at scale. In Proceedings of the Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering."},{"key":"e_1_3_2_18_2","unstructured":"Scott Behrens and Bryan Payne. 2016. Starting the Avalanche: Application DDoS In Microservice Architectures. Retrieved July 16 2021 from https:\/\/medium.com\/netflix-techblog\/starting-the-avalanche-640e69b14a06."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2020.24415"},{"key":"e_1_3_2_20_2","article-title":"Add an assertion in ByteVector.enlarge()","author":"Bruneton Eric","year":"2021","unstructured":"Eric Bruneton. 2021. Add an assertion in ByteVector.enlarge(). Retrieved August 28, 2021 from https:\/\/gitlab.ow2.org\/asm\/asm\/-\/commit\/cf20d046cab42e80866d8557e1b4ba4d47186300.","journal-title":"https:\/\/gitlab.ow2.org\/asm\/asm\/-\/commit\/cf20d046cab42e80866d8557e1b4ba4d47186300"},{"key":"e_1_3_2_21_2","volume-title":"Proceedings of the Adaptable and Extensible Component Systems","author":"Bruneton Eric","year":"2002","unstructured":"Eric Bruneton, Romain Lenglet, and Thierry Coupaye. 2002. ASM: A code manipulation tool to implement adaptable systems. In Proceedings of the Adaptable and Extensible Component Systems."},{"key":"e_1_3_2_22_2","volume-title":"Proceedings of the USENIX Security Symposium","author":"Bulekov Alexander","year":"2022","unstructured":"Alexander Bulekov, Bandan Das, Stefan Hajnoczi, and Manuel Egele. 2022. Morphuzz: Bending input space to fuzz virtual devices. In Proceedings of the USENIX Security Symposium."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63390-9_4"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2012.31"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2015.50"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2018.23159"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/1988042.1988046"},{"key":"e_1_3_2_28_2","volume-title":"Proceedings of the USENIX Security Symposium","author":"Crosby Scott A.","year":"2003","unstructured":"Scott A. Crosby and Dan S. Wallach. 2003. Denial of service via algorithmic complexity attacks. In Proceedings of the USENIX Security Symposium."},{"key":"e_1_3_2_29_2","volume-title":"Proceedings of the International Conference on Information Systems Architecture and Technology","author":"Czubak Adam","year":"2016","unstructured":"Adam Czubak and Marcin Szymanek. 2016. Algorithmic complexity vulnerability analysis of a stateful firewall. In Proceedings of the International Conference on Information Systems Architecture and Technology."},{"key":"e_1_3_2_30_2","volume-title":"Proceedings of the European Conference on Object-Oriented Programming","author":"Dietrich Jens","year":"2017","unstructured":"Jens Dietrich, Kamil Jezek, Shawn Rasheed, Amjed Tahir, and Alex Potanin. 2017. Evil pickles: DoS attacks based on object-graph engineering. In Proceedings of the European Conference on Object-Oriented Programming."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.5555\/2810085"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00040"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2568225.2568273"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134103"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48234-2_11"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31424-7_64"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183440.3183476"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/SCAM.2016.23"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813606"},{"key":"e_1_3_2_40_2","volume-title":"Proceedings of the USENIX Security Symposium","author":"Ispoglou Kyriakos","year":"2020","unstructured":"Kyriakos Ispoglou, Daniel Austin, Vishwath Mohan, and Mathias Payer. 2020. Fuzzgen: Automatic fuzzer generation. In Proceedings of the USENIX Security Symposium."},{"key":"e_1_3_2_41_2","volume-title":"Proceedings of the NASA Formal Methods Symposium","author":"Jayaraman Karthick","year":"2009","unstructured":"Karthick Jayaraman, David Harvison, Vijay Ganesh, and Adam Kiezun. 2009. jFuzz: A concolic whitebox fuzzer for java. In Proceedings of the NASA Formal Methods Symposium."},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3138820"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38631-2_11"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243804"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICPC.2016.7503727"},{"key":"e_1_3_2_46_2","article-title":"Using the ASM framework to implement common Java bytecode transformation patterns","author":"Kuleshov Eugene","year":"2007","unstructured":"Eugene Kuleshov. 2007. Using the ASM framework to implement common Java bytecode transformation patterns. Aspect-Oriented Software Development.","journal-title":"Aspect-Oriented Software Development"},{"key":"e_1_3_2_47_2","unstructured":"laf intel. 2016. Circumventing Fuzzing Roadblocks with Compiler Transformations. Retrieved July 16 2021 from https:\/\/lafintel.wordpress.com\/."},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3213846.3213874"},{"key":"e_1_3_2_49_2","volume-title":"Proceedings of the USENIX Security Symposium","author":"Livshits V. Benjamin","year":"2005","unstructured":"V. Benjamin Livshits and Monica S. Lam. 2005. Finding security vulnerabilities in java applications with static analysis. In Proceedings of the USENIX Security Symposium."},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49674-9_26"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10664-015-9413-5"},{"key":"e_1_3_2_52_2","unstructured":"Microsoft. 2015. Microsoft Security Risk Detection. Retrieved July 16 2021 from https:\/\/www.microsoft.com\/en-us\/security-risk-detection\/."},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/96267.96279"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.5555\/1855768.1855773"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3213846.3213868"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3167132.3167289"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293882.3330576"},{"key":"e_1_3_2_58_2","volume-title":"Proceedings of the USENIX Security Symposium","author":"Pellegrino Giancarlo","year":"2015","unstructured":"Giancarlo Pellegrino, Davide Balzarotti, Stefan Winter, and Neeraj Suri. 2015. In the compression hornet\u2019s nest: A security study of data compression in network services. In Proceedings of the USENIX Security Symposium."},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00056"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134073"},{"key":"e_1_3_2_61_2","volume-title":"Proceedings of the USENIX Security Symposium","author":"Ramos David A.","year":"2015","unstructured":"David A. Ramos and Dawson R. Engler. 2015. Under-constrained symbolic execution: Correctness checking for real code. In Proceedings of the USENIX Security Symposium."},{"key":"e_1_3_2_62_2","unstructured":"Guido Ranken. 2018. libFuzzer Java. Retrieved July 16 2021 from https:\/\/github.com\/guidovranken\/libfuzzer-java."},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2017.23404"},{"key":"e_1_3_2_64_2","volume-title":"Proceedings of the USENIX Security Symposium","author":"Rebert Alexandre","year":"2014","unstructured":"Alexandre Rebert, Sang Kil Cha, Thanassis Avgerinos, Jonathan Foote, David Warren, Gustavo Grieco, and David Brumley. 2014. Optimizing seed selection for fuzzing. In Proceedings of the USENIX Security Symposium."},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP40001.2021.00066"},{"key":"e_1_3_2_66_2","volume-title":"Proceedings of the Java Virtual Machine Research and Technology Symposium","author":"Russell Kenneth B.","year":"2001","unstructured":"Kenneth B. Russell and Lars Bak. 2001. The hotspot serviceability agent: An out-of-process high-level debugger for a java virtual machine. In Proceedings of the Java Virtual Machine Research and Technology Symposium."},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-72598-7_13"},{"key":"e_1_3_2_68_2","volume-title":"Proceedings of the USENIX Annual Technical Conference","author":"Serebryany Konstantin","year":"2012","unstructured":"Konstantin Serebryany, Derek Bruening, Alexander Potapenko, and Dmitriy Vyukov. 2012. AddressSanitizer: A fast address sanity checker. In Proceedings of the USENIX Annual Technical Conference."},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134105"},{"key":"e_1_3_2_70_2","unstructured":"Google Open Source. 2021. OSS-Fuzz. Retrieved July 16 2021 from https:\/\/github.com\/google\/oss-fuzz."},{"key":"e_1_3_2_71_2","volume-title":"Proceedings of the USENIX Security Symposium","author":"Staicu Cristian-Alexandru","year":"2018","unstructured":"Cristian-Alexandru Staicu and Michael Pradel. 2018. Freezing the web: A study of ReDoS vulnerabilities in javascript-based web servers. In Proceedings of the USENIX Security Symposium."},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2016.23368"},{"key":"e_1_3_2_73_2","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454084"},{"key":"e_1_3_2_74_2","unstructured":"EJ Technologies. 2015. Java Profiler. Retrieved July 16 2021 from https:\/\/www.ej-technologies.com\/products\/jprofiler\/overview.html."},{"key":"e_1_3_2_75_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54580-5_2"},{"key":"e_1_3_2_76_2","volume-title":"Proceedings of the International Symposium on Code Generation and Optimization","author":"Toffola Luca Della","year":"2018","unstructured":"Luca Della Toffola, Michael Pradel, and Thomas R. Gross. 2018. Synthesizing programs that expose performance bottlenecks. In Proceedings of the International Symposium on Code Generation and Optimization."},{"key":"e_1_3_2_77_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276990"},{"key":"e_1_3_2_78_2","doi-asserted-by":"publisher","DOI":"10.1145\/3377811.3380396"},{"key":"e_1_3_2_79_2","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516736"},{"key":"e_1_3_2_80_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54580-5_1"},{"key":"e_1_3_2_81_2","doi-asserted-by":"publisher","DOI":"10.1145\/2950290.2950340"},{"key":"e_1_3_2_82_2","unstructured":"Micha\u0142 Zalewski. 2014. American Fuzzy Lop Technical Details. Retrieved May 14 2022 from https:\/\/lcamtuf.coredump.cx\/afl\/technical_details.txt."}],"container-title":["ACM Transactions on Privacy and Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3532184","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3532184","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:42Z","timestamp":1750183782000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3532184"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,9]]},"references-count":81,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,11,30]]}},"alternative-id":["10.1145\/3532184"],"URL":"https:\/\/doi.org\/10.1145\/3532184","relation":{},"ISSN":["2471-2566","2471-2574"],"issn-type":[{"value":"2471-2566","type":"print"},{"value":"2471-2574","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,9]]},"assertion":[{"value":"2021-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}