Handling Cyclic Reinforcement of Lattice Values in Incremental Dependency-driven Static Analysis

Nowadays, many developers heavily rely on feedback from bug-detection tools to help ensure the quality of the code they produce. Such tools are underlain by static analysis. It is, however, critical for analysis results to be produced fast. To this end, incremental static analysis can be used. Upon a program change, an incremental analysis updates the previous results rather than recomputing the results from scratch.

Incremental static analyses may suffer from cyclic reinforcement of lattice values, where the computation of some values within the analysis relies on the values themselves, due to the abstractions made by the analysis. This can cause the incremental analysis to produce less precise results, reducing its usability.

In this work, we provide a solution to cyclic reinforcement of lattice values for incremental dependency-driven analyses. We compute the information flow within the analysis and show how this information flow can be used to detect cyclic reinforcements. We establish a criterion to detect when a cyclic reinforcement contains outdated information that needs to be removed, and show how precision can be regained. Our results show that using our method, an incremental analysis produces results matching a from-scratch analysis for all but one benchmark program, at the cost of a performance hit in some cases.