# Analyzing and Discovering Spatial Algorithm Complexity Vulnerabilities in Recursion
## 4 Methodology
### Model-Based Vulnerable Call Chain Search
#### 4.3.1 Class Method Recursive Structure  
In order to improve the simplicity, efficiency and maintainability of the code, Java introduces class methods. Furthermore, class methods have two designs: recursive and non recursive. Recursive design can handle a large number of algorithmic logic problems with simple code by calling itself (as shown in Listing 2). However, because each recursive call needs to save the context information, when the recursive depth is too large, it may lead to frequent method calls and stack operations, resulting in stack overflow ACVs. ```
1 publicclassFactorialCalculator{
2 publicintfactorial(intn){//&recursivemethodforcalculatingfactorial
3 if(n<=1){
4 return1;
5}else{
6 returnn*factorial(n-1);//Recursivecall
7}
8}
9 publicstaticvoidmain(String[]args){
10//CreateaninstanceofFactorialCalculator
11 FactorialCalculatorcalculator=newFactorialCalculator();
12 intnumber=5;
13 intresult=calculator.factorial(number);
14 System.out.println(\"Factorialof\"+number+\"is:\"+result);
15}
16}
17}
```
Figure 3: (**a**) Direct recursion and (**b**) indirect recursion (for readability, we use PowerPoint to redraw the vulnerable recursion examples according to the generated call graph). Most of the existing ACV detecting and even most vulnerability detecting methods only support basic data types. Taking the vulnerability detecting method based on symbolic execution technology as an example, most of the existing symbolic execution vulnerability detecting methods for Java language only support basic data types, such as int and char, while it is difficult to solve constraints for complex data types such as String or Object, thus is not possible to better detect vulnerabilities related to class methods. Therefore, at this stage, we mainly adopt static call chain feature analysis instead of symbolic execution, supplementing the analysis of class methods recursion and then supporting the subsequent vulnerability verification and utilization. Our algorithm, as outlined in the pseudocode in Algorithm 1, is implemented using the Soot framework. We start by acquiring all ActiveBodies from the JAR file. For each unit within an ActiveBody, we analyze its type of call (Line 5). If these calls are of the InvokeStmt type or the AssignStmt type, and contain a method call (Line 6), we then conduct further analysis: we examine the method call, and if it is not within an exception handling block (Line 9, will be detailed described in Section 4.3.3), we proceed to check the stack used for storing method calls. If recursive calls are detected (Line 12), and there are no limits on recursion depth (Line 13, will be detailed described in Section 4.3.2), we record the current call stack. If no recursive calls are found, we push non-basic class methods and non-abstract methods onto the stack and recursively analyze the called method (Line 19). ```
1:JAR file of the project to be tested
2:Vulnerable recursive structures
3:use Soot framework to analyze Jar File to get \(sootMethod\) object
4:initialize \(sootMethodStack\) to store \(sootMethod\)
5:\(body\leftarrow\) retrieve all active body of \(sootMethod\)
6:if unable to retrieve, exit
7:for each \(unit\) in the method's \(body\)do
8:if\(unit\) is a instance of (\(InvokeStmt\) or (\(AssignStmt\) containing \(InvokeExpr\))) then
9:\(calledMethod\leftarrow\) Extract the called method from the \(unit\)
10:endif
11:if the \(calledmethod\) is within an exception handling block then
12: skip to the next \(unit\)
13:endif
14:if\(sootMethodStack\) contains \(calledmethod\)then
15:if the \(calledmethod\) does not have a recursion depth limitation then
16: record the current \(sootMethodStack\) for analysis
17:endif
18:elseifhen
19:if the \(calledmethod\) is neither a basic class method nor a abstract method then
20: add the called method to the \(sootMethodStack\)
21: recursively analyze the \(calledmethod\)
22: remove the method from the stack after analysis
23:endif
24:endif
25:endfor
```
**Algorithm 1** Discovering all vulnerable recursive structures.