Analyzing and Discovering Spatial Algorithm Complexity Vulnerabilities in Recursion
Source abstract
Abstract
The algorithmic complexity vulnerability (ACV) that may lead to denial of service attacks greatly disrupts the security and availability of applications, and due to the widespread use of third-party libraries, its impact may be amplified through the software supply chain. The existing work in the field is dedicated to abstract loop or iterative patterns and fuzzing the entire application to discover algorithm complexity vulnerabilities, but they still face efficiency and effectiveness issues. Our research focuses on: (1) proposing a representation and extraction method for code features related to algorithmic complexity vulnerabilities, helping analysts quickly understand program logic; (2) providing a new ACV detecting model, focusing on the spatial complexity anomalies caused by deep recursion structures, and proposing a new filtering method; and (3) aiming at the difficulty of efficiently generating complex-data-type-related payloads using existing symbol execution techniques, a call-chain-guided payload construction method is proposed. We tested third-party components in the open-source Java Maven Repository, identified many unexposed vulnerabilities, and eight of them received Common Vulnerabilities and Exposures (CVE) identifiers, and demonstrated that our method can discover more algorithmic complexity vulnerabilities compared to existing tools with better performance.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Advanced Malware Detection Techniques · Software Engineering Research · Software Testing and Debugging Techniques
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Cyberspace Security, Beijing University of Posts and Telecommunications, Bejing 100876, China
References (48)
Show source-provided references
1. (2024, January 08). Algorithmic Complexity Vulnerabilities: An Introduction. Available online: https://twosixtech.com/blog/algorithmic-complexity-vulnerabilities-an-introduction/.
2. (2024, January 08). Zip Bomb. Available online: https://en.wikipedia.org/wiki/Zip_bomb.
3. (2024, January 08). 42.zip. Available online: https://www.unforgettable.dk/.
4. (2024, January 08). Regular Expression Denial of Service—ReDoS. Available online: https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS.
5. Lopez, J., Huang, X., and Sandhu, R. (2013, January 3–4). Static Analysis for Regular Expression Denial-of-Service Attacks. Proceedings of the International Conference on Network and System Security, Madrid, Spain.
6. Static Detection of DoS Vulnerabilities in Programs That Use Regular Expressions
7. Davis, J., Coghlan, C., Servant, F., and Lee, D. (2018, January 4–9). The impact of regular expression denial of service (ReDoS) in practice: An empirical study at the ecosystem scale. Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, Lake Buena Vista, FL, USA.10.1145/3236024.3236027 ↗
8. Wang, X., Zhang, C., Li, Y., Xu, Z., Huang, S., Liu, Y., Yao, Y., Xiao, Y., Zou, Y., and Liu, Y. (2023, January 22–24). Effective ReDoS Detection by Principled Vulnerability Modeling and Exploit Generation. Proceedings of the 2023 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA.10.1109/SP46215.2023.10179328 ↗
9. Staicu, C.A., and Pradel, M. (2018, January 15–17). Freezing the web: A study of ReDoS vulnerabilities in Javascript-based web servers. Proceedings of the 27th USENIX Conference on Security Symposium (SEC’18), Baltimore, MD, USA.
10. (2024, January 08). CVE-2023-36617 Detail, Available online: https://nvd.nist.gov/vuln/detail/CVE-2023-36617.
11. Liu, Y., and Meng, W. (2022, January 7–11). Acquirer: A Hybrid Approach to Detecting Algorithmic Complexity Vulnerabilities. Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (CCS ’22), Los Angeles, CA, USA.10.1145/3548606.3559337 ↗
12. Awadhutkar, P., Santhanam, G.R., Holland, B., and Kothari, S. (2019, January 26–30). DISCOVER: Detecting Algorithmic Complexity Vulnerabilities. Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE 2019), Tallinn, Estonia.10.1145/3338906.3341177 ↗
13. HotFuzz: Discovering Temporal and Spatial Denial-of-Service Vulnerabilities Through Guided Micro-Fuzzing10.1145/3532184 ↗
14. CVFuzz: Detecting Complexity Vulnerabilities in OpenCL Kernels via Automated Pathological Input Generation10.1016/j.future.2021.09.006 ↗
15. Awadhutkar, P., Santhanam, G.R., Holland, B., and Kothari, S. (2017, January 4–8). Intelligence amplifying loop characterizations for detecting algorithmic complexity vulnerabilities. Proceedings of the 2017 IEEE 24th Asia-Pacific Software Engineering Conference (APSEC), Nanjing, China.
16. Wei, J., Chen, J., Feng, Y., Ferles, K., and Dillig, I. (2018, January 4–9). Singularity: Pattern Fuzzing for Worst Case Complexity. Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE 2018), Lake Buena Vista, FL, USA.10.1145/3236024.3236039 ↗
17. Noller, Y., Kersten, R., and Păsăreanu, C.S. (2018, January 16–21). Badger: Complexity Analysis with Fuzzing and Symbolic Execution. Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2018), Amsterdam, The Netherlands.10.1145/3213846.3213868 ↗
18. Liu, Y., Zhang, M., and Meng, W. (2021, January 24–27). Revealer: Detecting and Exploiting Regular Expression Denial-of-Service Vulnerabilities. Proceedings of the 2021 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA.10.1109/SP40001.2021.00062 ↗
19. Xie, X., Chen, B., Liu, Y., Le, W., and Li, X. (2016, January 13–18). Proteus: Computing Disjunctive Loop Summary via Path Dependency Analysis. Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE 2016), Seattle, WA, USA.10.1145/2950290.2950340 ↗
20. Aït-Ameur, Y., and Crăciun, F. (2022). Theoretical Aspects of Software Engineering, Proceedings of the 16th International Symposium (TASE 2022), Cluj-Napoca, Romania, 8–10 July 2022, Springer.10.1007/978-3-031-10363-6 ↗
21. Toffola, L.D., Pradel, M., and Gross, T.R. (2018, January 24–28). Synthesizing programs that expose performance bottlenecks. Proceedings of the 2018 International Symposium on Code Generation and Optimization (CGO 2018), Vienna, Austria.10.1145/3179541.3168830 ↗
22. Nguyen, T., Ishimwe, D., Malyshev, A., Antonopoulos, T., and Phan, Q.S. (2020, January 9). Using dynamically inferred invariants to analyze program runtime complexity. Proceedings of the 3rd ACM SIGSOFT International Workshop on Software Security from Design to Deployment (SEAD 2020), Virtual.10.1145/3416507.3423189 ↗
23. Shen, Y., Jiang, Y., Xu, C., Yu, P., Ma, X., and Lu, J. (2018, January 3–7). ReScue: Crafting regular expression DoS attacks. Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering (ASE ’18), Montpellier, France.10.1145/3238147.3238159 ↗
24. Holland, B., Santhanam, G.R., Awadhutkar, P., and Kothari, S. (2016, January 2–3). Statically-Informed Dynamic Analysis Tools to Detect Algorithmic Complexity Vulnerabilities. Proceedings of the 2016 IEEE 16th International Working Conference on Source Code Analysis and Manipulation (SCAM), Raleigh, NC, USA.10.1109/SCAM.2016.23 ↗
25. (2024, January 08). Algorithmic Complexity. Available online: https://devopedia.org/algorithmic-complexity.
26. (2024, January 08). Algorithmic Complexity. Available online: https://viterbi-web.usc.edu/~adamchik/15-121/lectures/Algorithmic%20Complexity/complexity.html.
27. (2024, January 08). Algorithmic Complexity Attack. Available online: https://en.wikipedia.org/wiki/Algorithmic_complexity_attack.
28. Crosby, S.A., and Wallach, D.S. (2003, January 4–8). Denial of Service via Algorithmic Complexity Attacks. Proceedings of the 12th Conference on USENIX Security Symposium (SSYM’03), Washington, DC, USA.
29. Grzech, A., Świątek, J., Wilimowska, Z., and Borzemski, L. (2017). Information Systems Architecture and Technology, Proceedings of the 37th International Conference on Information Systems Architecture and Technology—ISAT 2016—Part II, Karpacz, Poland, 18–20 September 2016, Springer.10.1007/978-3-319-46586-9 ↗
30. (2024, January 08). How to Use Input Sanitization to Prevent Web Attacks. Available online: https://www.esecurityplanet.com/endpoint/prevent-web-attacks-using-input-sanitization/.
31. Barlas, E., Du, X., and Davis, J.C. (2022, January 25–27). Exploiting input sanitization for regex denial of service. Proceedings of the 44th International Conference on Software Engineering (ICSE ’22), Pittsburgh, PA, USA.10.1145/3510003.3510047 ↗
32. (2024, January 08). Recursion in Java. Available online: https://www.geeksforgeeks.org/recursion-in-java/.
33. (2024, January 08). Exceptions in Java. Available online: https://www.geeksforgeeks.org/exceptions-in-java/.
34. Vallée-Rai, R., Co, P., Gagnon, E., Hendren, L., Lam, P., and Sundaresan, V. (2010, January 1–4). Soot: A Java Bytecode Optimization Framework. Proceedings of the CASCON First Decade High Impact Papers (CASCON ’10), Toronto, ON, Canada.10.1145/1925805.1925818 ↗
35. (2024, January 08). soot-oss/soot. Available online: https://github.com/soot-oss/soot.
36. Evil Pickles: DoS Attacks Based on Object-Graph Engineering
37. Burnim, J., Juvekar, S., and Sen, K. (2009, January 16–24). WISE: Automated test generation for worst-case complexity. Proceedings of the 2009 IEEE 31st International Conference on Software Engineering, Vancouver, BC, Canada.10.1109/ICSE.2009.5070545 ↗
38. Luckow, K., Kersten, R., and Păsăreanu, C. (2017, January 13–17). Symbolic Complexity Analysis Using Context-Preserving Histories. Proceedings of the 2017 IEEE International Conference on Software Testing, Verification and Validation (ICST), Tokyo, Japan.10.1109/ICST.2017.13 ↗
39. Chechik, M., and Raskin, J.F. (2016). Tools and Algorithms for the Construction and Analysis of Systems, Proceedings of the 22nd International Conference, TACAS 2016, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2016, Eindhoven, The Netherlands, 2–8 April 2016, Springer.10.1007/978-3-662-49674-9 ↗
40. (2024, January 08). oss-fuzz. Available online: https://github.com/google/oss-fuzz.
41. (2024, January 08). CVE-2022-45685. Available online: https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2022-45685.
42. (2024, January 08). CVE-2022-45690. Available online: https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2022-45690.
43. (2024, January 08). CVE-2022-45688. Available online: https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2022-45688.
44. (2024, January 08). CVE-2022-41404. Available online: https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2022-41404.
45. (2024, January 08). CVE-2022-47937. Available online: https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2022-47937.
46. (2024, January 08). CVE-2022-45687. Available online: https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2022-45687.
47. (2024, January 08). CVE-2022-45693. Available online: https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2022-45693.
48. (2024, January 08). CVE-2022-45689. Available online: https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2022-45689.