Hybrid top-down and bottom-up interprocedural analysis
Abstract
Interprocedural static analyses are broadly classified into top-down and bottom-up, depending upon how they compute, instantiate, and reuse procedure summaries. Both kinds of analyses are challenging to scale: top-down analyses are hindered by ineffective reuse of summaries whereas bottom-up analyses are hindered by inefficient computation and instantiation of summaries. This paper presents a hybrid approach Swift that combines top-down and bottom-up analyses in a manner that gains their benefits without suffering their drawbacks. Swift is general in that it is parametrized by the top-down and bottom-up analyses it combines. We show an instantiation of Swift on a type-state analysis and evaluate it on a suite of 12 Java programs of size 60-250 KLOC each. Swift outperforms both conventional approaches, finishing on all the programs while both of those approaches fail on the larger programs.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 05, 2014
- Source ID
- 10.1145/2666356.2594328
Entities
People
- Hongseok Yang
- Mayur Naik
- Ravi Mangal
- Xin Zhang
Organizations
- Defense Advanced Research Projects Agency
- Engineering and Physical Sciences Research Council
- Georgia Tech
- National Science Foundation
- University of Oxford