Large Spurious Cycles in Global Static Analyses and Their Algorithmic Mitigation

Abstract. We present a simple algorithmic extension of the classical call-strings approach to mitigate substantial performance degradation caused by spurious interprocedural cycles. Spurious interprocedural cy-cles are, in a realistic setting, key reasons for why approximate call-return semantics in both context-sensitive and-insensitive static analysis can make the analysis much slower than expected. In the traditional call-strings-based context-sensitive static analysis, be-cause the number of distinguished contexts must be finite, multiple call-contexts are inevitably joined at the entry of a procedure and the output at the exit is propagated to multiple return-sites. We found that these multiple returns frequently create a single large cycle (we call it “butter-fly cycle”) covering almost all parts of the program and such a spurious cycle makes analyses very slow and inaccurate. Our simple algorithmic technique (within the fixpoint iteration algo-rithm) identifies and prunes these spurious interprocedural flows. The technique’s effectiveness is proven by experiments with a realistic C ana-lyzer to reduce the analysis time by 7%-96%. Since the technique is algo-rithmic, it can be easily applicable to existing analyses without changing the underlying abstract semantics, it is orthogonal to the underlying abstract semantics ’ context-sensitivity, and its correctness is obvious.