# Analyzing and Discovering Spatial Algorithm Complexity Vulnerabilities in Recursion
## 1 Introduction  
An algorithmic complexity vulnerability is an inappropriate design or implementation of algorithmic logic that can lead to attackers carefully constructing malicious inputs, triggering abnormal resource consumption or time consumption, and resulting in a denial of service [1]. The most typical such kind of denial of service (DoS) attack is Zip bomb [2], such as 42.zip [3], which may appear to be only 42 KB, but after decompression, it can scale to several PB of data, causing enormous pressure on the decompression program and resources, resulting in spatial ACV. The Regular Expression Denial of Service (ReDoS) vulnerability [4; 5; 6; 7; 8; 9], is another type of vulnerability caused by improper filtering rules on regular expressions, allowing attackers to consume a significant amount of time and resources for software or library regular matching operations by submitting specific inputs. The recent occurrence in Ruby, such as CVE-2023-36617 [10], is a typical example. As above, compared to traditional memory crash vulnerabilities that can be tested through blind fuzzing methods, algorithm complexity vulnerabilities are more closely integrated with algorithm design and implementation, which leads to traditional blind fuzzing methods being more inefficient. At the same time, due to the extensive use of open-source components including logging framework and blockchain smart contrast provided by third-party repositories in modern software development, such as Maven and GitHub, software developers unintentionally introduce code with algorithmic complexity vulnerabilities developed by others, further expanding the threats of ACV. This also makes it difficult for existing analysis methods to analyze algorithmic complexity vulnerabilities hidden in open-source components. At present, researchers have proposed solutions to the above problems. [PERSON] et al., proposed Acquirer [11], which combines static and dynamic methods to generate control flow and data flow graphs of the program, identify potential algorithm complexity issues, and use dynamic testing techniques to verify the resource consumption of the program, thereby discovering and verifying temporal ACVs. [PERSON] et al. proposed DIS-COVER [12], a static analysis tool that calculates the time complexity of a loop by analyzing the number of iterations in the loop, internal operations in the loop body, and nested structures. [PERSON] et al., proposed HotFuzz [13], which compensates for the shortcomings of traditional fuzzing methods in discovering ACVs by introducing temporal and spatial guidance, in order to discover more spatial and temporal features associated with different inputs. Through directional fuzzing testing, more ACVs are discovered. [PERSON] et al., proposed a dynamic path search approach that combines dynamic symbol execution and constraint-based path exploration techniques to explore the execution path of a program, and detects ACVs based on path coverage information and pathological inputs [14]. In order to address the challenges faced by detecting ACV and address the gap in related field mentioned above, we propose a three-step ACV detection and verification workflow. First, we propose a static analysis method based on analyzing Java bytecode, analyzing various complex iterations and other conditional operations, APIs such as I/O, exception handling mechanisms, etc., in order to provide detailed information for analysts to perform high-level abstraction and filter suspicious vulnerability code call chains. Secondly, to compensate for the shortcomings of existing ACV detecting models, a brand new Java ACV model related to exception handling mechanism in deep recursion process is proposed. The existing methods have strong randomness and require a large amount of manual verification, ignore the underlying causes of vulnerabilities, such as Java language features, which reduces the efficiency of analysis. Finally, we propose a ACV verification and payload generation method.