Item Details

Parallel Path-Based Static Analysis

Parthasarathy, Mitali; Le, Wei; Soffa, Mary
Format
Report
Author
Parthasarathy, Mitali
Le, Wei
Soffa, Mary
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.
Language
English
Date Received
20121029
Published
University of Virginia, Department of Computer Science, 2010
Published Date
2010
Collection
Libra Open Repository
Logo for In CopyrightIn Copyright

Availability

Access Online