{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T18:51:25Z","timestamp":1777488685914,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":57,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,10,30]],"date-time":"2017-10-30T00:00:00Z","timestamp":1509321600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-13-18415"],"award-info":[{"award-number":["CNS-13-18415"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,10,30]]},"DOI":"10.1145\/3133956.3134073","type":"proceedings-article","created":{"date-parts":[[2017,10,27]],"date-time":"2017-10-27T12:48:18Z","timestamp":1509108498000},"page":"2155-2168","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":127,"title":["SlowFuzz"],"prefix":"10.1145","author":[{"given":"Theofilos","family":"Petsios","sequence":"first","affiliation":[{"name":"Columbia University, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jason","family":"Zhao","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angelos D.","family":"Keromytis","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suman","family":"Jana","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,10,30]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"#800564 - PHP5: trivial hash complexity DoS attack - Debian Bug report logs. https:\/\/bugs.debian.org\/cgi-bin\/bugreport.cgi?bug=800564."},{"key":"e_1_3_2_2_2_1","unstructured":"attackercan\/regexp-security-cheatsheet. https:\/\/github.com\/attackercan\/regexp-security-cheatsheet\/tree\/master\/RegexpSecurityParser\/WAF-regexps."},{"key":"e_1_3_2_2_3_1","unstructured":"bk2204\/php-hash-dos: A PoC hash complexity DoS against PHP. https:\/\/github.com\/bk2204\/php-hash-dos."},{"key":"e_1_3_2_2_4_1","unstructured":"bzip2. http:\/\/www.bzip.org\/1.0.3\/html\/index.html."},{"key":"e_1_3_2_2_5_1","unstructured":"Controlling backtracking. https:\/\/msdn.microsoft.com\/en-us\/library\/dsy130b4(v=vs.110).aspx#controlling_backtracking."},{"key":"e_1_3_2_2_6_1","unstructured":"CVE-2011--5021. http:\/\/cve.mitre.org\/cgi-bin\/cvename.cgi?name=CVE-2011--5021."},{"key":"e_1_3_2_2_7_1","unstructured":"CVE-2013--2099. http:\/\/cve.mitre.org\/cgi-bin\/cvename.cgi?name=CVE-2013--2099."},{"key":"e_1_3_2_2_8_1","unstructured":"CVE-2015--2526. http:\/\/cve.mitre.org\/cgi-bin\/cvename.cgi?name=CVE-2015--2526."},{"key":"e_1_3_2_2_9_1","unstructured":"gnulib\/qsort.c at master coreutils\/gnulib. https:\/\/github.com\/coreutils\/gnulib\/blob\/master\/lib\/qsort.c."},{"key":"e_1_3_2_2_10_1","unstructured":"Hash algorithm and collisions - PHP Internals Book. http:\/\/www.phpinternalsbook.com\/hashtables\/hash_algorithm.html."},{"key":"e_1_3_2_2_11_1","unstructured":"honggfuzz. https:\/\/github.com\/google\/honggfuzz."},{"key":"e_1_3_2_2_12_1","unstructured":"https:\/\/opensource.apple.com\/source\/xnu\/xnu-1456.1.26\/bsd\/kern\/qsort.c. https:\/\/opensource.apple.com\/source\/xnu\/xnu-1456.1.26\/bsd\/kern\/qsort.c."},{"key":"e_1_3_2_2_13_1","unstructured":"libc\/stdlib\/qsort.c. https:\/\/sourceforge.net\/u\/lluct\/me722-cm\/ci\/f3ae3e66860629a7ebe223fdda3fdc8ffbdd9c6d\/tree\/bionic\/libc\/stdlib\/qsort.c."},{"key":"e_1_3_2_2_14_1","unstructured":"libFuzzer - a library for coverage-guided fuzz testing - LLVM 3.9 documentation. http:\/\/llvm.org\/docs\/LibFuzzer.html."},{"key":"e_1_3_2_2_15_1","unstructured":"NetBSD: qsort.c v 1.13 2003\/08\/07. http:\/\/cvsweb.netbsd.org\/bsdweb.cgi\/src\/lib\/libc\/stdlib\/qsort.c."},{"key":"e_1_3_2_2_16_1","unstructured":"NVD - CVE-2012--2098. https:\/\/nvd.nist.gov\/vuln\/detail\/CVE-2012--2098."},{"key":"e_1_3_2_2_17_1","unstructured":"NVD - CVE-2013--4287. https:\/\/nvd.nist.gov\/vuln\/detail\/CVE-2013--4287."},{"key":"e_1_3_2_2_18_1","unstructured":"PCRE - Perl Compatible Regular Expressions. http:\/\/www.pcre.org\/."},{"key":"e_1_3_2_2_19_1","unstructured":"PHP Vulnerability May Halt Millions of Servers - PHP Classes. https:\/\/www.phpclasses.org\/blog\/post\/171-PHP-Vulnerability-May-Halt-Millions-of-Servers.html."},{"key":"e_1_3_2_2_20_1","unstructured":"Regular expression denial of service - redos - owasp. https:\/\/www.owasp.org\/index.php\/Regular_expression_Denial_of_Service_-_ReDoS."},{"key":"e_1_3_2_2_21_1","unstructured":"SantizerCoverage - Clang 4.0 documentation. http:\/\/clang.llvm.org\/docs\/SanitizerCoverage.html."},{"key":"e_1_3_2_2_22_1","unstructured":"Stack exchange network status - outage postmortem - july 20 2016. http:\/\/stackstatus.net\/post\/147710624694\/outage-postmortem-july-20--2016."},{"key":"e_1_3_2_2_23_1","unstructured":"syzkaller. https:\/\/github.com\/google\/syzkaller."},{"key":"e_1_3_2_2_24_1","unstructured":"Why does stack overflow use a backtracking regex implementation? - meta stack overflow. https:\/\/meta.stackoverflow.com\/questions\/328376\/why-does-stack-overflow-use-a-backtracking-regex-implementation."},{"key":"e_1_3_2_2_25_1","volume-title":"Analyzing catastrophic backtracking behavior in practical regular expression matching. arXiv preprint arXiv:1405.5599","author":"Berglund M.","year":"2014","unstructured":"Berglund, M., Drewes, F., and van der Merwe, B. Analyzing catastrophic backtracking behavior in practical regular expression matching. arXiv preprint arXiv:1405.5599 (2014)."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.2002.1181582"},{"key":"e_1_3_2_2_27_1","volume-title":"OASIcs-OpenAccess Series in Informatics","volume":"15","author":"Betts A.","year":"2010","unstructured":"Betts, A., Merriam, N., and Bernat, G. Hybrid measurement-based WCET analysis at the source level using object-level traces. In OASIcs-OpenAccess Series in Informatics (2010), vol. 15, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2009.10"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2015.50"},{"key":"e_1_3_2_2_30_1","volume-title":"Introduction to algorithms","author":"Cormen T. H.","year":"2001","unstructured":"Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to algorithms, vol. 6. MIT press Cambridge, 2001."},{"key":"e_1_3_2_2_31_1","first-page":"3","volume-title":"Proceedings of the 12th Conference on USENIX Security Symposium -","volume":"12","author":"Crosby S. A.","year":"2003","unstructured":"Crosby, S. A., and Wallach, D. S. Denial of service via algorithmic complexity attacks. In Proceedings of the 12th Conference on USENIX Security Symposium - Volume 12 (Berkeley, CA, USA, 2003), SSYM'03, USENIX Association, pp. 3--3."},{"key":"e_1_3_2_2_32_1","first-page":"151","volume-title":"Proceedings of the 2008 Network and Distributed Systems Symposium (NDSS)","volume":"8","author":"Godefroid P.","year":"2008","unstructured":"Godefroid, P., Levin, M. Y., Molnar, D. A., et al. Automated Whitebox Fuzz Testing. In Proceedings of the 2008 Network and Distributed Systems Symposium (NDSS) (2008), vol. 8, pp. 151--166."},{"key":"e_1_3_2_2_33_1","first-page":"49","volume-title":"22nd USENIX Security Symposium (USENIX Security '13)","author":"Haller I.","year":"2013","unstructured":"Haller, I., Slowinska, A., Neugschwandtner, M., and Bos, H. Dowsing for Overflows: A Guided Fuzzer to Find Buffer Boundary Violations. In 22nd USENIX Security Symposium (USENIX Security '13) (Washington, D.C., 2013), USENIX, pp. 49--64."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCAM.2016.23"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2345156.2254075"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSBSE.2009.20"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38631-2_11"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065010.1065034"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(19990410)29:4%3C341::AID-SPE237%3E3.0.CO;2-R"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2931037.2931066"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2010.5462149"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818000.2818031"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2017.27"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA.2000.896433"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA.1999.811296"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2017.23404"},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2771783.2771816"},{"key":"e_1_3_2_2_49_1","first-page":"167","volume-title":"International Conference on Security and Privacy in Communication Systems","author":"Shenoy G. S.","year":"2012","unstructured":"Shenoy, G. S., Tubella, J., and Gonz\u00e1lez, A. Improving the resilience of an IDS against performance throttling attacks. In International Conference on Security and Privacy in Communication Systems (2012), Springer, pp. 167--184."},{"key":"e_1_3_2_2_50_1","first-page":"1190","volume-title":"IDS Against Algorithmic Complexity Attacks. In Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2012","author":"Shenoy G. S.","year":"2012","unstructured":"Shenoy, G. S., Tubella, J., and Gonz'lez, A. Hardware\/Software Mechanisms for Protecting an IDS Against Algorithmic Complexity Attacks. In Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2012 IEEE 26th International (2012), IEEE, pp. 1190--1196."},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSAC.2006.17"},{"key":"e_1_3_2_2_52_1","unstructured":"Song L. and Lu S. Performance Diagnosis for Inefficient Loops. Under Submission."},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2016.23368"},{"key":"e_1_3_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/icc.2011.5962718"},{"key":"e_1_3_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-0135-2_12"},{"key":"e_1_3_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008096431840"},{"key":"e_1_3_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54580-5_1"},{"key":"e_1_3_2_2_58_1","unstructured":"Zalewski M. American Fuzzy Lop. http:\/\/lcamtuf.coredump.cx\/afl\/. endthebibliography"}],"event":{"name":"CCS '17: 2017 ACM SIGSAC Conference on Computer and Communications Security","location":"Dallas Texas USA","acronym":"CCS '17","sponsor":["SIGSAC ACM Special Interest Group on Security, Audit, and Control"]},"container-title":["Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3133956.3134073","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3133956.3134073","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3133956.3134073","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:03Z","timestamp":1750212663000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3133956.3134073"}},"subtitle":["Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities"],"short-title":[],"issued":{"date-parts":[[2017,10,30]]},"references-count":57,"alternative-id":["10.1145\/3133956.3134073","10.1145\/3133956"],"URL":"https:\/\/doi.org\/10.1145\/3133956.3134073","relation":{},"subject":[],"published":{"date-parts":[[2017,10,30]]},"assertion":[{"value":"2017-10-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}