Hybrid Inlining: A Compositional and Context Sensitive Static Analysis Framework

Jiangchao Liu, Jierui Liu, Peng Di, Diyu Wu, Hengjie Zheng, Alex X. Liu, Jingling XuearXiv 2022 · OpenReview

TL;DR

This paper introduces "Hybrid Inlining," a novel static analysis framework that combines the precision of top-down analysis with the scalability of compositional analysis. By selectively inlining only "critical" statements that require context sensitivity and summarizing others, it achieves precise inter-procedural analysis with minimal performance overhead, making it practical for large industrial applications.

What Problem Does This Paper Address?

Static analysis, particularly for inter-procedural analysis (understanding how different functions interact), is crucial for finding bugs and ensuring software correctness. The gold standard for precision is "context-sensitive" analysis, which considers the specific calling context of a function. However, traditional top-down context-sensitive analyses achieve this by inlining the entire code of called functions, leading to a combinatorial explosion of code to analyze ("statement explosion"), making them impractical for large software.

On the other hand, "compositional" (bottom-up) analyses summarize functions and reuse these summaries, which scales much better. The trade-off is a loss of precision because these summaries are often computed without considering specific calling contexts. This paper addresses the challenge of achieving both high precision and scalability in inter-procedural static analysis.

Methods

The core innovation is Hybrid Inlining. The authors observe that in compositional analysis, only a small subset of statements ("critical statements") truly lose precision when summarized without context. These are typically statements where the outcome depends heavily on the specific calling environment (e.g., virtual method calls, array accesses with variable indices).

Hybrid Inlining works by:

  1. Identifying Critical Statements: Statements that are sensitive to context are identified.
  2. Hybrid Summarization: For a given procedure, non-critical statements are summarized as usual (efficiently). Critical statements, however, are not immediately summarized. Instead, they are kept as explicit statements within the procedure's "hybrid summary."
  3. Lazy Propagation and Summarization: These critical statements are then propagated to the caller's context. The analysis continues to propagate them until the context is deemed "adequate" (meaning further propagation won't yield more precision). At this point, the critical statement is finally summarized using the accumulated context.
  4. Context Ready Predicates: To avoid propagating critical statements all the way to the root of the call graph (which would negate scalability benefits), the authors introduce "context ready predicates." These predicates determine when a critical statement's context is sufficient for precise summarization, allowing it to be summarized locally.

This approach effectively "inlines" only the critical parts of a function when and where they are needed, while summarizing the rest, thus balancing precision and performance.

Datasets

The paper evaluates its approach using:

  • Dacapo Benchmark Suite: A collection of 10 open-source Java programs.
  • Real Industrial Benchmarks: 10 large financial transaction system modules.
  • PointerBench: A micro-benchmark suite for pointer analysis with ground truth.

Key Insights and Ideas

  • Not all statements need context sensitivity: The key insight is that precision gains from context sensitivity are not uniformly distributed across all statements. Focusing analysis effort only on the "critical" statements is sufficient for high precision.
  • Compositional analysis can be made strictly context-sensitive: By selectively inlining critical statements, the authors demonstrate that compositional analysis can achieve the precision of top-down context-sensitive analysis without sacrificing scalability.
  • Lazy summarization is key: Propagating critical statements until their context is "adequate" (rather than always to the root) allows for localized precision gains and avoids unnecessary computation.
  • Context ready predicates enable practical trade-offs: These predicates allow the system to decide when to stop propagating critical statements, offering a tunable knob for balancing performance and precision.

Key Results

  • Precision: Hybrid Inlining (HI3 and HIA configurations) achieved the highest precision on the PointerBench micro-benchmark suite, outperforming even selective top-down analyses like Zipper and SELECTX.
  • Performance: On Dacapo benchmarks, Hybrid Inlining (HI2 and HIA) incurred only a 27.0% and 64.5% average time overhead compared to context-insensitive analysis, respectively, while significantly reducing polymorphic call-sites. On industrial applications, HIA showed a mere 1% average time overhead and was even faster than the compositional baseline in 6 out of 10 cases.
  • Scalability: The framework successfully analyzed large industrial applications in minutes on a personal laptop.

Limitations and Future Work

  • Memory Occupation (Flow-Sensitive Analysis): The authors note that for flow-sensitive analysis, hybrid summaries can become large, potentially leading to memory concerns. This is addressed by the flow-insensitive version.
  • Heuristic for Critical Statement Propagation: In the HIA configuration, a heuristic is used to limit the propagation of critical statements if their number exceeds a threshold, which might trade off some precision for performance.
  • Future Work: The paper suggests that the framework is general and can be applied to various top-down and compositional analyses. Further exploration of context ready predicates and their impact on performance/precision trade-offs is implied. The authors also mention the possibility of "k-limit Hybrid Inlining" where critical statements are propagated for a fixed number of steps.

Summary updated

Abstract

Context sensitivity is essential for achieving the precision in inter-procedural static analysis. To be (fully) context sensitive, top-down analysis needs to fully inline all statements of the callees at each callsite, leading to statement explosion. Compositional analysis, which inlines summaries of the callees, scales up but often loses precision, as it is not strictly context sensitive. We propose a compositional and strictly context sensitive framework for static analysis. This framework is based on one key observation: a compositional static analysis often loses precision only on some critical statements that need to be analyzed context sensitively. Our approach hybridly inlines the critical statements and the summaries of non-critical statements of each callee, thus avoiding the re-analysis of non-critical ones. In addition, our analysis lazily summarizes the critical statements, by stopping propagating the critical statements once the calling context accumulated is adequate. Hybrid Inlining can be as precise as context sensitive top-down analysis. We have designed and implemented a pointer analysis based on this framework. It can analyze large Java programs from the Dacapo benchmark suite and industry in minutes. In our evaluation, compared to context insensitive analysis, Hybrid Inlining just brings 65% and 1% additional time overhead on Dacapo and industrial applications respectively.
BibTeX
@misc{liu2022hybrid,
  author = {Jiangchao Liu and Jierui Liu and Peng Di and Diyu Wu and Hengjie Zheng and Alex X. Liu and Jingling Xue},
  title = {{Hybrid Inlining: A Compositional and Context Sensitive Static Analysis Framework}},
  year = {2022},
  eprint = {2210.14436},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2210.14436},
}
Figure