Parallel Path-based Static Analysis

Report
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
Abstract:

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.

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

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

Publisher:
University of Virginia, Department of Computer Science
Published Date:
2010