A Sliding-Window Algorithm for On-The-Fly Interprocedural Program Analysis

Program analysis plays an important role in finding software flaws. Due to dynamic language features like late binding, there are many program analysis problems for which one could not assume a prior program control flow, e.g., Java points-to analysis, the disassembly of binary codes with indirect jumps, etc. In this work, we give a general formalization of such kind of on-the-fly interprocedural program analysis problems, and present a sliding-window algorithm for it in the framework of weighted pushdown systems. Our sliding window algorithm only consists of a series of local static analyses conducted on an arbitrary number of program methods, which does not sacrifice the precision of the whole program analysis at the manageable cost of caching intermediate analysis results during each iteration. We have implemented and evaluated the sliding-window algorithm by instantiating the framework with Java points-to analysis as an application. Our empirical study showed that the analysis based on the sliding-window algorithm always outperforms the whole program analysis on runtime efficiency and scalability.