# Analyzing and Discovering Spatial Algorithm Complexity Vulnerabilities in Recursion
## 5 Evaluation
### Result and Analysis
#### 5.2.3 RQ3: Verification and Exploitation  
As mentioned earlier, the vulnerability analysis method and detection model we propose can detect vulnerabilities related to recursive structures with almost no false positives. This is because the vulnerability chains we filter meet the following characteristics: they have the potential to directly or indirectly trigger an unending recursion, are externally reachable, and are not captured by the exception and error handling mechanism. Therefore, based on the understanding of the conditions that trigger recursion and the argument processing context, it is possible to rapidly construct and exploit payloads for these vulnerabilities. Following our proposed Recursion-Guided payload generation method, and using our publicly disclosed vulnerability CVE-2022-45685 [41] shown in Listing 3 as an example, we illustrate the rapid construction of a payload. In the vulnerability source code, \"JSONTokener\" in Line 3 acts as the cursor for the input string. First, we analyze the logic of the recursive method's parameter processing by examining the call chain from new \"JSONObject\" to the next new \"JSONObject\", which involves all the processing statements for \"JSONTokener\" as shown in Line 8-Line 22 and Line 32-42. Next, based on these processing statements, we construct the initial actual parameter that can trigger the recursive loop, which is \"{1(\". Then, we iteratively process this actual parameter. Following the characteristics of function recursion in Java, we construct a method that can trigger recursion 10,000 times, which is achieved by repeating \"{1(\" ten thousand times. This results in the final payload. Overall, our method of vulnerability payload generation is capable of rapid construction based on the characteristics of recursive structures in call chains and the conditions that trigger recursion. Analysts with a fundamental understanding of code can quickly verify vulnerabilities and write the corresponding payloads. All 8 publicly disclosed CVE vulnerabilities can be found in references [40; 41; 42; 43; 44; 45; 46; 47; 48]. ```
1 publicclassJSONObjectimplementsSerializable{
2//
3 publicJSONObject(JSONTokenerx)throwsJSONException{
4 this();
5 charc;
6 Stringkey;
7
8 if(x.nextClean()!='{'{'}throwx.syntaxError(*AJSONObjecttextmustbeginwith'{'{'{'{'}}};{'{'}}}}
11
12 for(;;){
13c=x.nextClean();
14 switch(c){
15 case0:
16 throwx.syntaxError(\"AJSONObjecttextmustendwith'{'{'{'{'}}};{'{'}};{'}};{'}};{'}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}



discovery method. We have only proposed an accurate model for detecting algorithmic complexity vulnerabilities in recursive structures. In the future, we could develop more models to discover more exploitation patterns of algorithmic complexity vulnerabilities, even other vulnerabilities. Secondly, regarding the generation of vulnerability payloads, we currently employ a semi-automated method limited by the lack of Java dynamic symbolic execution tools, requiring significant manual intervention. In the future, we could consider delving into fully automated payload generation to improve the efficiency of vulnerability verification and exploitation. Finally, we will continue to delve deeper into our research on the same type of vulnerability detecting methods between different programming languages, utilizing a unified intermediate representation to detect ACVs and other type of vulnerabilities related to program logic. Supervision, B.C. ; methodology, Z.W., D.B. and W.T. ; writing--original draft preparation, Z.W. ; writing--review and editing, Z.W., W.T. and D.B. ; software, D.B. ; All authors have read and agreed to the published version of the manuscript. This research received no external funding. Not applicable. Publicly available datasets were analyzed in this study. These data can be found here: [[https://mvnrepository.com/](https://mvnrepository.com/)]([https://mvnrepository.com/](https://mvnrepository.com/)) (accessed on 8 January 2024), including _org.apache.pdfbox_, _org.apache.sling.commons.json_, _jettison_, _intool_, _int4j_.