Analyzing and Discovering Spatial Algorithm Complexity Vulnerabilities in Recursion

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.

Keywords

• spatial algorithm complexity vulnerability
• recursion structure
• call chain