2022/10/26 by Jiangchao Liu, Jierui Liu, Liu, Jiangchao +11
Computer Science · #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Security and Verification in Computing #Software System Performance and Reliability #Software Testing and Debugging Techniques
paper · pdf · doi:10.48550/arxiv.2210.14436
openalex publication_date 2022/10/26 · openalex created_date 2022/11/02 · openalex updated_date 2026/07/28
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.