# An Approach for Detecting Feasible Paths Based on Minimal SSA Representation and Symbolic Execution
## 4 Detection Methodology
### Avoid Duplicated Feasible Paths
The source code of each program in C and PHP is publicly available ([[https://github.com/Amarashdeh/FP-PHP-C-TestPrograms](https://github.com/Amarashdeh/FP-PHP-C-TestPrograms)]([https://github.com/Amarashdeh/FP-PHP-C-TestPrograms](https://github.com/Amarashdeh/FP-PHP-C-TestPrograms)), accessed on 1 April 2021). The entire experiment was conducted on the operating platform Windows 10, 8 GB RAM, Intel i5-7200U CPU. PHP version 7.4 was used to build the proposed approach with XAMPP local server version 7.4. ### Performance Evaluation Metrics

The proposed approach started by analyzing the source code to generate an AST. Then, the AST was converted to a minimal SSA form, which is the form that helps to reduce the instructions in the normal SSA form. Two well-defined algorithms were used for the symbolic inputs' assignments and the path generation including the condition extractor. The entire process of generating the feasible paths was conducted automatically, which means that no human action is needed for generating the path conditions. A path weight method was proposed to avoid detecting duplicated feasible paths. The last stage \begin{table}
\begin{tabular}{l l l l l} \hline \hline
**Program** & **LoC** & **B** & **Description** & **F** & **Refs.** \\ \hline eR1985 & 18 & 3 & (Expt) Raises one integer to the power of the other. & 5 & [42; 43; 44] \\ fcB2002 & 21 & 4 & (Floatcomp) Compares three floating point numbers & 5 & [43; 44; 45; 46; 47] \\  & & & and has some selections. & \\ gA2008 & 16 & 3 & Finds the greatest common divisor between any & 5 & [43; 44; 48; 49] \\ rA2008 & 16 & 3 & Finds the remainder in integer division. & 4 & [43; 44; 46; 48; 50; 51] \\  & & & Determines whether three given numbers that & 4 & [43; 44; 46; 47; 48; 51] \\ tA2008 & 14 & 3 & represent three lengths on a plane form a scalene, & 4 & [43; 44; 46; 47; 48; 51] \\  & & & isosceles, equilateral, or not a triangle. & \\ tM2004 & 20 & 4 & (Triangle) Classifies three numbers representing & 7 & [43; 44; 47] \\  & & & isosceles, right, iso-right, or equilateral. & \\ ttB2002 & 38 & 7 & (Tritype) Accepts three integers representing sides of & 8 & [43; 44; 47] \\ \hline \hline \end{tabular}

* LoC: Lines of Codes, B: the number of branches of each program, Description: a description of each program, F: the number of feasible paths (non-duplicated paths), Refs: reference(s) of each program.

\end{table} 
Table 2: Test programs. checks the paths' conditions by using the Z3 solver. The results of the Z3 solver show the satisfiability of each path and the values of each symbolic input that could satisfy the condition if it is a feasible path. The proposed approach's performance was assessed based on the number of feasible paths detected, the number of duplicated paths detected, and the time required to generate paths. \"Recall\" measures the percentage between the number of feasible paths correctly detected and the actual number of feasible paths existing in the source code. \"DuplicatedPathsPercentage\" measures the percentage between the number of duplicated paths detected and the total number of paths detected in the program. The precision and recall rates were calculated with Equations (2) and (3), respectively. \[Recall=\frac{F_{Detected}-F_{False}}{F_{True}} \tag{2}\]

\[DuplicatedPathsPercentage=\frac{DF_{Detected}}{F_{Detected}}, \tag{3}\]

where \(F_{Detected}\) denotes the number of feasible paths detected and \(F_{True}\) denotes the number of feasible paths that exist in the detected program; \(F_{False}\) denotes the number of feasible paths detected that are infeasible in reality; \(DF_{Detected}\) denotes the number of duplicated feasible paths detected. The evaluation of the time required to generate the paths was performed using the PHP built-in function microtime(), which is a function that returns the current Unix timestamp in microseconds [55].