# An Approach for Detecting Feasible Paths Based on Minimal SSA Representation and Symbolic Execution
## 1 Introduction  
Web applications are now considered one of the standard channels in the World Wide Web for representing data and executing service launches. These resources include social media, finance, education, banking, news pages, TV channels, etc. Web applications store sensitive data, which hackers can steal and gain monetary benefits from. Thus, to identify the vulnerability of web applications, a static analysis explores the web application's source code [1]. Static analysis has the potential to observe every possible path in an application through scrutiny of the source code. However, covering all web application paths during testing leads a false positive result [2, 3]. False positives are results that are safe but are reported to be vulnerabilities, and thus, execution would not occur, despite the type of user input. In addition, researchers have stated that programmers should distinguish which paths can be executed and that the test cases should be implemented on feasible paths only [4, 5]. A feasible path is defined as any path on which test cases can be executed. Detection of feasible paths can help decrease the false positive rate of the results of static analyses and, thus, further improve the detection rate for different threats. In addition, detectingthe same feasible paths (duplicated paths) from test cases more than once provides a false number of threats existing in the program. Detection of feasible paths can be achieved by generating test cases of the source code to identify the executable paths among the others. Symbolic execution is a basic approach commonly used in various fields, such as software testing and reverse engineering [6; 7; 8]. The idea is to execute a program with a symbolic representation of inputs instead of concrete values. The symbol signifies symbolic and concrete values that may be understood from the symbol. Some symbolic execution engines have been deployed. Prominent examples are MultiSE [6], KLEE [7], and Java PathFinder (Jpf) [8]. However, all of these studies focused on the intermediate representation (IR) to convert the source code to a simple form for analysis, such as the static single assignment (SSA) form. Nevertheless, there is significant inflation in the IR code, where new constructions correspond to function abstractions. For instance, the code written for the Low-Level Virtual Machine (LLVM) occupies 600 lines, despite the simplicity of the example [9; 10]. The analysis of this code was time-consuming, as would be the case for similar examples. Meanwhile, [PERSON] et al. [11] presented an SSA constriction algorithm to produce a minimal and pruned SSA form. They established that the algorithm they designed builds minimal and trimmed SSA form, which helps decrease the instructions in the SSA form to be analyzed. Therefore, this paper aims to reinforce the improvements in the static analysis results by proposing a new approach for detecting feasible paths based on minimal SSA representation and symbolic execution. The proposed approach was constructed in such a way that it can (i) detect the total quantity of feasible paths in the source code, (ii) avoid detecting duplicated feasible paths, and (iii) decrease the time required to generate the paths. In addition, IR and binary generation tools and libraries are not commonly accessible for all programming languages, such as Hypertext Preprocessor (PHP), thereby significantly reducing the applicability of current symbolic execution systems [12]. Therefore, our approach was implemented and tested on PHP as the most popular web application technology [13]. The rest of the paper is structured as follows: Section 2 provides background information on static analysis and symbolic execution, followed by related studies in Section 3. Section 4 elucidates the proposed detection approach of feasible paths. Section 5 presents the experimental outcomes of the proposed approach and comparisons with related work. Section 6 highlights the threats to validity.