# An Approach for Detecting Feasible Paths Based on Minimal SSA Representation and Symbolic Execution
## 4 Detection Methodology
### Symbolic Interpreter  
During the generation of the SSA form, and once any superglobal variable or any uninitialized variable is detected, we assign a symbolic input for that variable. PHP has several in-built variables called superglobal variables. These variables store the input from the external user, which is unpredictable. Hence, the values are kept symbolic. In the scope of this study, all superglobal variables of the PHP language are considered [40]. A full symbolic execution assignment algorithm for the symbolic interpreter is shown in Algorithm 1.  
```
input :SSA form output :SSA form with symbolic inputs \(\overline{\text{SGV}}\)[] \(\leftarrow\) list of all super global variable in PHP \(\overline{\text{SGD}}\)[] \(\leftarrow\) list of all super global variables detected \(\overline{\text{CBV}}\)[] \(\leftarrow\) list of the current block variables whilevariable\(\in\)MSSAdo ifvariable is NULLthen // uninitialized/unknown variables \(\overline{\text{CBV}}\)\(\leftarrow\) symbolic input elseifvariable inSGVthen // super global variable ifvariable inSGDthen // ifdefined before \(\overline{\text{CBV}}\)\(\leftarrow\) SGD[variable] else \(\overline{\text{CBV}}\)\(\leftarrow\) symbolic input \(\overline{\text{SGD}}\)\(\leftarrow\) symbolic input endif endif endwhile
```  
**Algorithm 1**Symbolic Interpreter Algorithm.  
For instance, \"Sname = $_POST['username']\" points to the value inputted by the external user using the POST technique; hence, the value is not known. Consequently, \"Sname\" is allotted the symbolic value \"postsymbolicusername\". Once the symbolic value is assigned for the superglobal variable, this variable is stored in an array so that we can notice if the same superglobal variable is assigned for another variable. Meanwhile, if we detect the use of a variable that has not been defined before, we assign a symbolic value \"undefinedsymbolic\" for that variable. The complete process of assigning symbolic values to superglobal variables and uninitialized variables is presented in Algorithm 1.  
To solve the loop heuristically, we provide a symbolic input for every loop condition variable present in the loop that is being assessed (loop condition), which allows the loop to be evaluated symbolically under the given inputs. Figure 7 illustrates the previous example code in Figure 1 with a while loop; this shows the assignment of a symbolic input for the loop condition to be executed symbolically.  
The loop in Figure 7 is defined at Line 6 with the condition ($i < 3), which means the loop iteration will continue to execute until the condition terminates. In the loop body, a another condition ($a > $b | | $a < $c) is defined inside the \"if\" statement at Line 7, which it will execute in each iteration of the loop (3 times during every run of the example program). To avoid the repetition of the loop iteration, a symbolic input (\(S\)) was assigned for the loop condition ($i < 3). Afterwards, the symbolic loop condition ($i < 5) was added for each path inside the loop, and the logical operator \"AND\" (&\(\varepsilon\)) was added to ensure that the path condition of the loop was satisfied and executed at least once.  
Since our approach focused on detecting new feasible paths and avoiding duplicated paths, rather than keeping the loop traverse for n number of iterations in the next stage (Section 4.4), our approach prepared the loop with symbolic inputs. This helped with path generation and constrained the extractor algorithm to connect the symbolic loop condition with the path conditions inside the loop body.