Item Details

Parallel Path-based Static Analysis

Parthasarathy, Mitali; Le, Wei; Soffa, Mary
Parthasarathy, Mitali
Le, Wei
Soffa, Mary
Multicore architectures are widely used in research and in- dustry today. The innovations in parallel computer architec- tures create an opportunity for the development of software solutions that exploit the available parallelism. Static pro- gram analysis is a well-explored area of research which has many applications including detecting software vulnerabil- ities, test case generation, debugging and program paral- lelization. For many types of static analysis, scalability is an important concern. In prior research, the performance of static analysis has been improved with techniques such as exploring a limited portion of the search space, flow- insensitivity, context-insensitivity, abstraction and the use of heuristics. Many of these techniques can be viewed as trade-offs that sacrifice precision in favor of scalability and practical applicability. Previous work has demonstrated that demand-driven query propagation is an effective and efficient static analysis tech- nique that is more scalable than current techniques. In this research, we present a version of the demand-driven tech- nique that is multithreaded to further increase scalability. The key idea that underlying our approach is that query- based demand-driven analysis exhibits significant opportu- nities for parallelization because queries typically have few dependencies. We present a parallel algorithm for statically detecting buffer overflows and evaluate its feasibility in a path-based static analysis framework called Marple. We implemented the scheme using Microsoft Phoenix [Phoenix connect] and Marple [W. Le and M. L. Soffa, 2009], a tool produced at University of Virginia.
University of Virginia, Department of Computer Science, 2010
Published Date
Libra Open Repository
Logo for In CopyrightIn Copyright


Access Online