# Analyzing and Discovering Spatial Algorithm Complexity Vulnerabilities in Recursion
## 3 Background
### Algorithm Complexity Vulnerability
#### 3.2.2 Java Language Features  
* Java recursion, Java method recursion and stack overflow. In particular. In the design of algorithm, there will be many structures such as loop, iteration, recursion, and so on [32]. These structures facilitate software development and program understanding, but at the same time, they also bring some hidden dangers of security and reliability. There may be many problems with the loop structure, such as undefined boundaries [15]. In our work, we focus on the problem of recursive reference, because compared with other loop structures, its code is simpler, and it will consume more resources and have greater impact in case of problems, which is also relatively neglected by existing work. The default method stack size of Java generally only supports about 2000 method recursion calls, beyond which the stack overflow exception will be triggered. If the class methods are recursive methods, by constructing specific parameters, class methods can perform deep recursion and trigger stack overflow.
* Java exception and error handling mechanism. In Java, the program may encounter various exceptions when running, such as divide by zero exception, null pointer exception, array out of bounds exception, etc. [33]. When these exceptions occur, the program will stop execution and throw exceptions. If the exception is not handled, the program will terminate execution. Such handling mechanism is a very important part of Java, for it can help us catch and handle various exceptions in programs. Although errors should not be captured in general, but for some web applications, security frameworks and custom exception handlers, developers may need to capture and handle errors when developing some frameworks or underlying components to better handle errors and ensure program stability, especially components on third-party repositories and the cloud. Apache Tomcat and Spring framework are the two typical examples. However, there are still many programs in open-source repositories that have not considered catching and handling possible ACVs during the design phase.  
As shown in Figure 1, this is our overall threat model, with the bolded parts representing the concepts and threat types provided in this paper. Open-source code repositories such as Maven provide **third-party components** for developers to download and customize to build applications. Suppose the average **AC** of a certain algorithm in such a component is _O(nlogn)_. However, due to careless coding or malicious tampering by developers, the component may have **ACV**. Attackers can exploit this vulnerability by initiating **ACA**, constructing malicious inputs, satisfying **input sanitization** conditions, and leveraging programming **language features** to trigger the vulnerability. This could lead to direct attacks on the component or the entire application through the component. The attacker could reach the upper limit of **hard resource constraints** or exhaust all resources without limits, resulting in an actual algorithmic complexity far exceeding _O(nlogn)_.  
Figure 1: Threat model described based on concepts we proposed.