## 3 Design
### The Difficulty of State Space Explosion Mitigation  
In Section 2, we briefly discuss the causes of state space explosions. When a symbolic execution reaches repeated code, it forks itself at the branch in the repeated code, and the more times the repeated code is executed, the more the program execution state is forked. This repeated code will cause a state space explosion. One of the most straightforward ideas to mitigate the state space explosion is to symbolic execution of the repeated code only a minimum number of times when the symbolic execution enters the repeated code. The state space explosion of the symbolic execution is mitigated by reducing the state generated in the repeated code by exiting it as soon as possible. The core idea of this approach is that the state space of a program may be infinite; however, the number of basic blocks must be finite. If the states caused by repeated code are eliminated, then the states generated by a finite number of basic blocks must also be finite. Thus, it will not lead to a state space explosion. However, this approach will severely reduce the path exploration capability of the symbolic execution. This reduction in path exploration capability will affect the performance of path exploration more severely than the state space explosion. We made some modifications to the example used in Section 2. In Listing 2, we set \"function one\" to be executed when \"j\" is greater than 10. If our symbolic execution tool only performs the minimum repeated code exploration. When the initial value of \"i\" is set to 10, the repeated code will only be executed 5 times. The maximum value of \"j\" is 5, which does not satisfy the constraint that \"j\" is greater than 10 for the execution of \"function one\". This causes the symbolic execution to fail to detect the state of \"function one\", resulting in a reduction in path exploration capability. ```
1 intmain(intargc,char*argv[])
2{
3 unsignedinti=(unsignedint)argv[1];
4 unsignedintj=0;
5 if(i>10)return0;
6 while(i<15){
7 do_something();
8 if(j>10)function_one();
9i++
10j++;
11}
12 return0;
13}
```  
Listing 2: State space explosion with a reachable edge. We could propose a new idea on this base. We determine whether it is necessary to explore the repeated code by identifying whether there are any unexecuted edges following the repeated code. In this way, the repeated code can be explored continuously while \"function one\" is not executed, and further exploration of the repeated code can be stopped when \"function one\" is executed. By exploring the repeated code only a meaningful (new paths can be found) number of times, the number of state spaces is reduced while ensuring accuracy. However, this idea is still not effective in mitigating the state space explosion when used in practice. We have made some more modifications to the example we used in Listing 2. In Listing 3, we set \"function two\" to be executed when \"k\" is greater than 20. Therefore, \"k\" cannot be greater than 20. There is an edge following the repeated code that can never be reached. This makes the exploration of symbolic execution to try to find the \"function two\" meaningless and hard to terminate. Symbolic execution tools still encounter the problem of exploding state spaces. Therefore, we need a more precise approach that can effectively reduce the state space explosion of the symbolic execution without losing its path exploration capability. We propose a technique based on abstract syntax tree analysis that allows classifying the program execution states into different priorities. By classifying the states with different priorities, the symbolic execution can be more focused on the states that are more likely to discover new paths. Moreover, low-priority states will be difficult to be executed or even delete, thus avoiding state space explosion and saving memory space.