Parallel Path-based Static AnalysisReport
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)
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