# Analyzing and Discovering Spatial Algorithm Complexity Vulnerabilities in Recursion
## 2 Related Work  
[PERSON] et al. [12; 15] noted that fully automated detection of algorithmic complexity vulnerabilities is not feasible. Therefore, they proposed a tool named DISCOVER to assist in detecting these vulnerabilities. Their workflow mainly consists of three stages: First, they automate loop feature description based on the Termination Dependence Graph (TDG) and Loop Projected Control Graph (LPCG). Subsequently, they filter for suspicious loop patterns and further provide a catalog of loops to users for interactive auditing. [PERSON] et al. [13] introduced HotFuzz, a Guided Micro-Fuzzing method designed to discover Algorithm Denial-of-Service vulnerabilities. They utilized genetic algorithms to evolve arbitrary Java objects, aiming to trigger the worst-case performance of target methods. They defined Small Recursive Instantiation (SRI) to derive seed inputs represented as Java objects for micro-fuzzing. Additionally, they employed EyeVM to track and analyze the root causes of these vulnerabilities. [PERSON] et al. [16] introduced a pattern fuzzing method named Singularity, aimed at uncovering the worst-case scenarios in given applications. The authors initially proposed a Domain Specific Language-style approach, namely the Recurrent Computation Graph (RCG) computational model, to express input patterns. Furthermore, they utilized a genetic programming (GP) algorithm to manipulate RCGs for solving optimization problems, thus generating more effective input patterns that trigger the worst performance. They discovered availability vulnerabilities in real-world applications such as Google Guava and JGraphT. [PERSON] et al. [11] proposed a hybrid method for detecting algorithmic complexity vulnerabilities. This approach initially employs static methods to analyze loops and recursive structures in the target Java source code, identifying potentially vulnerable loop constructs. It then utilizes context information to guide critical path instrumentation, and constructs test cases based on branch strategies. By employing dynamic selective symbolic execution for path searching, it discovers cases that exhibit abnormal resource consumption, thereby uncovering time complexity-related algorithmic complexity vulnerabilities. [PERSON] et al. [17] proposed a hybrid method that combines fuzz testing and symbolic execution to detect time and space complexity algorithmic vulnerabilities. The main contribution of this method lies in its initial development of a fuzz testing approach, aimed at enhancing coverage and exploring paths with high resource consumption. To improve the efficiency of fuzz testing, a symbolic execution technique is employed. On the one hand, this technique explores potential high resource consumption paths through symbolic execution. On the other hand, it guides fuzz testing to generate samples that satisfy branch conditions, thereby enhancing the effectiveness of the approach. [PERSON] et al. [18] proposed a method for detecting and exploiting vulnerabilities related to ReDoS. They developed a tool named Revealer, which also combines static and dynamic analyses. Initially, they use static analysis tools to locate potentially vulnerable structures in regular expressions. Subsequently, they dynamically validate whether these vulnerable structures can be triggered. The dynamic method employed by the authors differs from fuzz testing and is a relatively precise method of generating regular expressions. They achieved performance improvements and detected a large number of new vulnerabilities. To sum up, current work in analyzing algorithmic complexity vulnerabilities mainly includes two major approaches, i.e., static method and dynamic method. Static methods are exemplified by loop characteristic analysis, which involves modeling and analyzing loop features in algorithms to identify vulnerable loop patterns [12; 15; 19; 20].