System, Method and Apparatus for Staged Goal-oriented Dynamic Analysis with Applications in Security Testing
Publication Date: 2016-Oct-09
The IP.com Prior Art Database
Our invention first detects code locations that are potentially relevant (e.g. security critical operation), and then coerces execution into reaching them. On violation we check the feasibility of the execution by modeling it as a constraint system, solvable using state-of-the-art constraint solvers. Our invention allows pruning uninteresting code branches. This saves redundant calls to the constraint solver - the main bottleneck of symbolic execution solutions.
Page 01 of 3
System, , Applications in Security Testing
Increasing Code Coverage in Software Testing via Constraint Solving
Code coverage is perhaps the most fundamental metric to reason about the
usefulness of analysis and testing tools. If a given property is tested - for example presence/
absence of security vulnerabilities - then failing to check that property along a given code branch may give the developer a false sense of confidence that the program is behaving correctly, while in fact the property is violated along the unexplored code path.
Increasing code coverage is therefore obviously desirable, but at the same time, there are obvious costs. Trying to traverse every code path complicates the analysis and also has serious
impact on performance. This suggests that an effective solution to the coverage problem should
first "guess" the code paths of interest, and then focus its effort only on those paths. Background art. There are several popular methods in existence to increase code coverage. A notable approach, known as concolic execution [Concolic1, Concolic2], is to exhaustively explore code branches using a combination of symbolic execution [Symbolic] and concrete input values. Another approach is random testing [Random], which simply utilizes random inputs as a means to fuzz the program, thereby discovering bugs.
Summary. Unlike these existing approaches, which simply attempt to maximize coverage, we propose in this invention a novel method to select code paths of interest, validate their
relevance to the property under test, and then synthesize inputs that traverse these paths (if possible). This enables a cost-efficient and systematic means to increase coverage only where useful.
The key insight underlying our invention is to break the coverage challenge into two
subproblems: First, we detect code locations that are potentially relevant (e.g., a statement performing a security-critical operation, if the goal is to test for security violations). We then coerce execution into reaching the chosen location. That is, we instrument the subject program to transition into appropriate branches even if normally execution would proceed differently.
If the resulting (infeasible) execution suggests that the property might be violated, then we model that execution as a constraint system, where the free variables are input fields (and potentially also the execution schedule in the case of a parallel program). We then discharge
the constraints to an off-the-shelf constraint solver, such as Z3, which either fails to find an input that feasibly induces the given path or synthesizes such an input in case of success .
A main saving enabled by our invention, which is the most significant bottleneck in dynamic analysis (e.g. in the form of symbolic execution), is the need to use nontrivial constraint solving to reach the different code branches with the goal of perfect coverage. We obviate this heavyweight mode of reasoning by instead di...