# An Approach for Detecting Feasible Paths Based on Minimal SSA Representation and Symbolic Execution
## 4 Detection Methodology
### Avoid Duplicated Feasible Paths
The algorithm that we used to generate the minimal SSA form by [PERSON] et al. [11] reduced the number of instructions in the program. Table 5 shows the number of instructions (#I) and the time required for each program to generate its paths (T) in seconds. The time shown in Table 5 excludes the SMT solver's time to check the satisfiability of each path because many studies have already been conducted to compare the SMT solver's time and performance [56; 57; 58]. \begin{table}
\begin{tabular}{l l l l} \hline \hline
**Metric** & **KLEE** & **SDART** & **Our Approach** \\ \hline Recall & 92.1\% & 60.5\% & 92.1\% \\ Duplicated paths & 26.6\% & 14.8\% & 0\% \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Summary of KLEE, SDART, and our approach’s results. \begin{table}
\begin{tabular}{l l l l l l l l} \hline \hline \multirow{2}{*}{**Program**} & \multirow{2}{*}{**\#TFP**} & \multicolumn{2}{c}{**KLEE**} & \multicolumn{2}{c}{**SDART**} & \multicolumn{2}{c}{**Our Approach**} \\ \cline{3-8}  & & **\#FD** & **\#DFD** & **\#FD** & **\#DFD** & **\#FD** & **\#DFD** \\ \hline eR1985 & 5 & 7 & 3 & 1 & 0 & 4 & 0 \\ fcB2002 & 5 & 6 & 1 & 5 & 1 & 5 & 0 \\ gA2008 & 5 & 4 & 0 & 2 & 0 & 4 & 0 \\ rA2008 & 4 & 3 & 0 & 3 & 0 & 3 & 0 \\ tA2008 & 4 & 8 & 4 & 6 & 2 & 4 & 0 \\ tM2004 & 7 & 8 & 1 & 4 & 0 & 7 & 0 \\ ttB2002 & 8 & 9 & 1 & 6 & 1 & 8 & 0 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Results of detected feasible paths and duplicated paths. The comparison of the number of constructed instructions (#I) indicates that the proposed approach generated fewer constructions than KLEE. The number of instructions generated by the programs depends on the LoC of each program and the number of conditions inside each branch. For example, the instructions in programs that have multiple conditions at the same branch (such as ftB2002, tA2008, and ttB2002) are more numerous than those in programs that have one condition inside the same branch. In addition, the results in Table 4 indicate that the proposed approach reduced the time for generating the paths. The last program (ttB2002) had more branches than the other programs. It had seven branches, five of which contained at least more than two conditions at the same branch. LLVM generated 190 instructions, and KLEE traversed all of these instructions to generate paths in 0.433 s. Meanwhile, our proposed approach generated 155 instructions under the same program and consumed a total of 0.293 s to generate the paths. From these results, we can assume that the proposed approach is efficient at reducing the time required to generate paths. ### Large Scale Programs

Our proposed approach is evaluated with a large set of test cases. This evaluation is carried out to prove that the proposed approach is capable of detecting feasible paths without any duplications from the PHP program. The proposed approach was implemented with 893,575 LoC in 10 WordPress plugins [59] as shown in Table 6, where the first column shows the plugins' names, with the plugin versions tested by each proposed approach in the second column. Column three shows the number of PHP files in each plugin, followed by the line of code (LoC) for each plugin. The number of constructed instructions and analyzed branches are shown in the fifth and sixth columns, respectively. The detected feasible paths (#FD) among each plugin are shown in the seventh column, followed by the detected duplicated feasible paths (#DFD). Lastly, the time required to generate the paths is shown in the last column. We deployed the Cloc ([[https://github.com/AllDanial/cloc](https://github.com/AllDanial/cloc)]([https://github.com/AllDanial/cloc](https://github.com/AllDanial/cloc)); accessed on 14 April 2021) tool to count the number of PHP files and LoC in every plugin. Cloc has been utilized in recent studies for similar metrics [60; 61; 62]. Table 6 shows that the proposed approach detects, in total, 152,669 new feasible paths (Total #FD) within 646.06 s (Total #T(s)), where each path has its own weight (unique weight).