Detect Program Vulnerabilities Using Trace-based Security Testing

Abstract

Software vulnerabilities are program flaws that can be exploited by attackers to compromise the security of a software system. Although many approaches have been proposed to detect or prevent software attacks, software security incidents continue to occur every year. Security testing aims at detecting program vulnerabilities through a set of test cases and has shown to be effective to detect program vulnerabilities. The primary challenge is how to efficiently produce test cases that are highly effective in detecting vulnerabilities. This dissertation proposes trace-based security testing approaches towards addressing some fundamental challenges in security testing.The first study is to use trace-based symbolic execution and satisfiability analysis to detect C program vulnerabilities. A security testing model is proposed to unify program states and security requirements into logical expressions. Specifically, program constraints (PC), i.e., all possible values of program variables at a given point in an execution, are derived from symbolic execution on the trace. Security constraints (SC), i.e., secure values of program variables at security critical points of the program, are derived from security knowledge. Both PC and SC are represented in first order logic. Therefore, the satisfiability of PC and the negation of SC indicates a program vulnerability. A tool named SecTAC has been developed and applied to test several open source C programs. Many known and unknown vulnerabilities have been detected.The second study is a novel fuzzing approach that aims to test deep program semantics through the analysis of program execution trace. Intuitively, program execution trace reflects the semantics of program input data from the program's point of view. This study proposes a test case similarity metric to model the semantic similarity between well-formed input data and its mutations. Such similarity is used to direct a two-stage fuzzing process to produce more test cases that are more likely to explore deep program semantics. A prototype tool named SimFuzz is developed to test real programs, and the experimental result shows that deep program semantics can be extensively tested compared to traditional fuzzing approaches.The third study is to utilize end user data for security testing as well as provide timely protection to end users. The idea is to monitor how program paths are explored by benign user data or malicious exploits. Once a new path is being explored, it is sent to testing site for security testing using trace-based security testing. Several techniques are proposed to make the system feasible in practice. First, tree-based bit tracing is proposed to reduce user site overhead and preserve user privacy. Second, conditional runtime monitor is proposed to ensure user security while reduce latency. Third, test decomposition is proposed to reduce space overhead. A prototype system named SecTOD has been developed and applied to test the Apache server program. The result shows that it is effective in terms of vulnerability detection and efficient in terms of computation and space overhead.Overall, this dissertation proposes trace-based security testing and studies techniques to (1) reuse existing test cases for security testing (2) extensively test deep program semantics (3) utilize end user data for security testing as well as protect end user security. These studies show that trace-based security testing approach is a promising technique for security testing in terms of the effectiveness and efficiency.