Abstract
Memory errors in C programs are the root causes of many defects and vulnerabilities
in software engineering. Among the available error detection techniques,
dynamic analysis is widely used in industries due to its high precision. Unfortunately,
existing approaches su↵er from considerable runtime overheads, owing to
unguided and overly conservative instrumentation. With the massive growth of
software nowadays, such inefficiency prevents testing with comprehensive program
inputs, leaving some input-specific memory errors undetected.
This thesis presents novel techniques to address the efficiency problem by eliminating
some unnecessary instrumentation guided by static analysis. Targeting two
major types of memory errors, the research has developed two tools, Usher and
WPBound, both implemented in the LLVM compiler infrastructure, to accelerate
the dynamic detection.
To facilitate efficient detection of undefined value uses, Usher infers the definedness
of values using a value-flow graph that captures def-use information for
both top-level and address-taken variables interprocedurally, and removes unnecessary
instrumentation by solving a graph reachability problem. Usher works well
with any pointer analysis (done a priori) and enables advanced instrumentationreducing
optimizations.
For efficient detection of spatial errors (e.g., bu↵er overflows), WPBound enhances the performance by reducing unnecessary bounds checks. The basic idea
is to guard a bounds check at a memory access inside a loop, where the guard is
computed outside the loop based on the notion of weakest precondition. The falsehood
of the guard implies the absence of out-of-bounds errors at the dereference,
thereby avoiding the corresponding bounds check inside the loop.
For each tool, this thesis presents the methodology and evaluates the implementation
with a set of C benchmarks. Their e↵ectiveness is demonstrated with
significant speedups over the state-of-the-art tools.