Parallel Path-based Static Analysis

Authors:Parthasarathy, Mitali, Department of Computer ScienceUniversity of Virginia Le, Wei, Department of Computer ScienceUniversity of Virginia Soffa, Mary, Department of Computer ScienceUniversity of Virginia

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.

All rights reserved (no additional license for public reuse)
Source Citation:

Parthasarathy, Mitali, Wei Le, and Mary Soffa. "Parallel Path-based Static Analysis." University of Virginia Dept. of Computer Science Tech Report (2010).

University of Virginia, Department of Computer Science
Published Date: