Testing C Programs for Vulnerability Using Trace-Based Symbolic Execution and Satisfiability Analysis

Security testing has gained significant attention recently due to the huge number of attacks against software systems. This paper presents a novel security testing method using trace-based symbolic execu-tion and satisfiability analysis. It reuses test cases generated from traditional functional testing to produce execution traces. An execution trace is a sequence of program statements exercised by a test case. Each execution trace is symbolically executed to produce program constraints and security constraints. A pro-gram constraint is a constraint imposed by program logic on program variables. A security constraint is a condition on program variables that must be satisfied to ensure system security. A security vulnerability exists if there is an assignment of values to program variables that satisfies the program constraint but violates the security constraint. This assignment of values is used to generate test cases to uncover the security vulnerability. One novelty of this method is a test model that unifies program constraints and security constraints such that formal reasoning can be applied to detect vulnerabilities. Another nov-elty is attribute-based analysis that abstracts program variables and functions for effective and efficient symbolic execution. A tool named SecTAC has been implemented and applied to 14 benchmark pro-grams and 3 moderate size open-source programs. The experiment shows that SecTAC quickly detects all reported vulnerabilities and 15 new ones that have not been detected previously. The merits of the proposed method are threefold. First, trace-based symbolic execution reduces the search space greatly as compared to conventional symbolic execution. Second, attribute-based analysis tracks more useful information about program variables and functions than previous methods, resulting in more effective detection of vulnerabilities. Third, it is efficient and effective as the experiment result indicates.