# An Approach for Detecting Feasible Paths Based on Minimal SSA Representation and Symbolic Execution
## 4 Detection Methodology
### Minimal and Pruned SSA form  
The SSA [39] form is a property of intermediate representations. This property ensures that each variable is defined and written only once. As a result, programs in SSA form encode explicit data flow relations. Figure 5 illustrates an example of the SSA form and \(\phi\) function.  
To understand the reasoning behind the SSA representation, a straight-line code is an appropriate way to begin. Figure 5 shows that a unique name is provided for every assignment made to a variable, and wherever the assignment is used, it is renamed to a new assignment name. The majority of programs comprise join and branch nodes. A unique assignment form referred to as the phi function (\(\phi\)) was used at the join nodes. The operands of the \(\phi\) function represent the assignments to V that reach the join. Any further use of Y is considered a use of V\({}_{5}\). The previous variable Y is replaced with new variables V\({}_{3}\), V\({}_{4}\), and V\({}_{5}\). All uses of V\({}_{i}\) are arrived upon by a single assignment to V\({}_{i}\). A single assignment to V\({}_{i}\) can be found in the complete code, which simplifies the record maintenance process for numerous optimizations.  
Figure 4: The framework of the proposed scheme.  
In this paper, we use the algorithm from [PERSON] et al. [11] to generate the minimal SSA form, where they used on-the-fly optimizations with an SSA compiler to decrease the number of \(\phi\) functions. Initially, a mathematical simplification is employed where the constructors pertaining to the IR node are subject to peephole optimizations and output simpler nodes wherever feasible. Considering an example, the mathematical expression X-X always amounts to zero. Furthermore, common subexpression removal, reuse of the present values identified using local values, and an evaluation of the constants during compilation are performed--for example, \(2\times 3\) may be optimized as 6. Finally, the local variables may have unnecessary arguments that must be removed (X = Y is one such example). The SSA form does not require assignments of this form; hence, it is feasible to use the right-hand side value directly. The effectiveness of such optimizations is depicted in Figure 6.  
The minimal static single assignment (MSSA) form before the application of on-the-fly optimizations is depicted in Figure 6b. When the optimizations are enabled, the initial difference is observed when value V\({}_{1}\) is constructed. Here, any comparison with zero will return false; therefore, the value is simpler during arithmetic simplification. During the next step, constant propagation converts a comparison with zero returning false. Now, the state at the jump condition is false; therefore, it is feasible to omit the code inside the \"then\" block. Concerning the \"else\" block, copy propagation is conducted by assigning V\({}_{0}\) to Y. Along the same lines, V\({}_{5}\) vanishes and, ultimately, the code returns V\({}_{0}\). The optimized SSA form of the code is illustrated in Figure 6c. It may be observed from the example that the run-time optimizations suggested by [PERSON] et al. [11] may potentially reduce the instruction count and \(\phi\) functions in the SSA form. After finding the minimal SSA form of the PHP source code, the next section describes the symbolic execution stage.  
Figure 5: An example of program code converted to SSA form.  
Figure 6: Converting a program code to Minimal SSA form. (**a**) Program code. (**b**) SSA form before on-the-fly optimizations. (**c**) Optimized SSA form of the code.