Bottom-up program analysis has been traditionally easy to parallelize because functions without caller-callee relations can be analyzed independently. However, such function-level parallelism is significantly limited by the calling dependence – functions with caller-callee relations have to be analyzed sequentially because the analysis of a function depends on the analysis results, a.k.a., function summaries, of its callees. We observe that the calling dependence can be relaxed in many cases and, as a result, the parallelism can be improved.
In this paper, we present Cheetah, a framework of bottom-up data flow analysis, in which the analysis task of each function is elaborately partitioned into multiple sub-tasks to generate pipelineable function summaries. These sub-tasks are pipelined and run in parallel without any additional synchronization, even though the calling dependence exists. We formalize our idea under the IFDS/IDE framework and have implemented an application to checking null-dereference bugs in C/C++ programs.
We evaluate Cheetah on a series of standard benchmark programs and open-source projects, which demonstrates significant speedup over a conventional parallel design.
Fri 10 JulDisplayed time zone: (UTC) Coordinated Universal Time change
08:05 - 09:05
|Conquering the Extensional Scalability Problem for Value-Flow Analysis FrameworksTechnical|
|Pipelining Bottom-up Data Flow AnalysisTechnical|
|An Empirical Validation of Oracle ImprovementJ1|
|Is Static Analysis Able to Identify Unnecessary Source Code?J1|
Roman Haas CQSE GmbH, Rainer Niedermayr CQSE GmbH, Tobias Roehm CQSE GmbH, Sven Apel Saarland UniversityPre-print
|Memory and Resource Leak Defects and Their Repairs in Java ProjectsJ1|
|Towards Understanding and Detecting Fake Reviews in App StoresJ1|