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

Memory errors in C programs are the root causes of many defects and vulnerabilitiesin 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 tounguided and overly conservative instrumentation. With the massive growth ofsoftware nowadays, such inefficiency prevents testing with comprehensive programinputs, leaving some input-specific memory errors undetected.This thesis presents novel techniques to address the efficiency problem by eliminatingsome unnecessary instrumentation guided by static analysis. Targeting twomajor types of memory errors, the research has developed two tools, Usher andWPBound, both implemented in the LLVM compiler infrastructure, to acceleratethe dynamic detection.To facilitate efficient detection of undefined value uses, Usher infers the definednessof values using a value-flow graph that captures def-use information forboth top-level and address-taken variables interprocedurally, and removes unnecessaryinstrumentation by solving a graph reachability problem. Usher works wellwith any pointer analysis (done a priori) and enables advanced instrumentationreducingoptimizations.For efficient detection of spatial errors (e.g., bu↵er overflows), WPBound enhances the performance by reducing unnecessary bounds checks. The basic ideais to guard a bounds check at a memory access inside a loop, where the guard iscomputed outside the loop based on the notion of weakest precondition. The falsehoodof 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 implementationwith a set of C benchmarks. Their e↵ectiveness is demonstrated withsignificant speedups over the state-of-the-art tools