An Integrated Static and Dynamic Program Analysis Framework for Checking Concurrency-Related Programming Errors

Today, the growing popularity of the multi-core/multi-processor hardware has forced many programs to be well-written concurrent programs. However, developing concurrent programs is intrinsically difficult. Concurrency introduces the possibility of errors that do not exist in sequential programs. The dissertation presents an integrated static and dynamic program analysis framework to address these concurrent errors.;First, it presents a scalable hybrid approach that integrates static and dynamic analyses to detect the concurrency errors including the notorious data race and atomicity violation. In the integrated approach, we first perform static analysis to obtain summaries of synchronizations and accesses to shared variables. The static summaries are then instantiated with runtime values during dynamic executions to speculatively approximate the behaviors of branches that are not taken. To reduce the overhead and make the analysis scalable, we designed and implemented a distributed monitoring and analysis framework in which the runtime monitoring and analysis are carried out on two separate machines which communicated to each other using the network. We designed and implemented this hybrid approach in a tool called DHAVE and evaluated it on several benchmarks. Compared to dynamic analysis, the hybrid approach is able to detect atomicity violations and other concurrency errors in unexecuted parts of the code efficiently. Compared to static analysis, the hybrid approach produces fewer false alarms and is more accurate.;The second part of the dissertation presents a self adaptive monitoring (SAM) framework that include several novel compile-time and run-time instrumentation and monitoring optimization techniques that aim to significantly reduce the overhead of dynamic analysis on multithreaded programs. SAM (Self-Adaptive Monitoring) can selectively turn off excessive monitoring on a repeatedly executed code region if the current program context has been determined to be redundant, which may assist many existing dynamic detection tools to improve their performance. Specifically, we approximate the program context for each code region as a set of concurrent context variables, which include path-critical variables and all shared variables accessed in that region. The path-critical variables are inferred by an extended use-def dataflow analysis, and the shared variables for each code region are identified using our prior hybrid thread-based escape analysis. We have implemented the tool in Java and evaluated it on a set of real world programs. Our experimental results show that it significantly reduces the runtime overhead of the dynamic atomicity violation detection while roughly keeping the accuracy and soundness of underlying runtime detection tools.;Finally, the dissertation describes a static analysis assisted dynamic program analysis that can reveal concurrency errors in the programs written using the OpenMP specification that is widely used in the scientific community. To detect race conditions, we first conduct an intraprocedural static analysis on the OpenMP programs to identify the variables that are likely to be involved in race conditions (including flush errors). The static analysis results are then used to guide the program instrumentation for the dynamic analysis. Finally, a lockset-based dynamic algorithm is applied on the running program to filter and refine the error report. Our experimental evaluation over several micro benchmarks and real-world applications shows that the hybrid approach imposes very light-weight performance overhead over the target programs while removing many spurious reported errors from the static lockset analysis.