Accelerating Dynamic Detection of Memory Errors for C Programs via Static Analysis

Download files
Access & Terms of Use
open access
Copyright: Ye, Ding
Altmetric
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.
Persistent link to this record
Link to Publisher Version
Link to Open Access Version
Additional Link
Author(s)
Ye, Ding
Supervisor(s)
Xue, Jingling
Creator(s)
Editor(s)
Translator(s)
Curator(s)
Designer(s)
Arranger(s)
Composer(s)
Recordist(s)
Conference Proceedings Editor(s)
Other Contributor(s)
Corporate/Industry Contributor(s)
Publication Year
2015
Resource Type
Thesis
Degree Type
PhD Doctorate
UNSW Faculty
Files
download public version.pdf 1.52 MB Adobe Portable Document Format
Related dataset(s)