Reviser – Incremental Analysis

ReviserReviser is an algorithm for incrementally and efficiently updating static analysis results when the target program changes. Conducting static analyses, for instance scanning an Android application for private data leaks, can be a highly time-consuming undertaking on large code bases, especially if very precise analysis algorithms are used. While investing this effort once is acceptable, it can easily be too expensive to conduct such analyses on a regular basis, for instance whenever an update to the respective app is released. However, such updates are frequent and analysis results computed for one version do not necessarily remain valid for the next version. Therefore, if a new version of the target program is released, e.g., a bug in the app is fixed, one previously had to perform all these computations anew to check whether required or expected properties still hold despite the high computational cost.

With Reviser, one can now automatically extract the changed parts of the program and analyze only those together with their respective dependencies instead of re-analyzing the complete application. Since Reviser works at the level of the IDE solver, it can be applied to every IDE-based analysis, requiring only minor changes to the implementation of the analysis. Incrementally updating only the changed parts can save up to 80% of the time that would be required for a full recomputation while still maintaining an often negligible overhead as our experiments have shown.

Reviser has been implemented on top of Soot and Heros and is available as a open source project on Github:

Reviser has been accepted for publication at ICSE 2014:

Reviser: Efficiently Updating IDE-/IFDS-Based Data-Flow Analyses in Response to Incremental Program Changes (Steven Arzt, Eric Bodden), 2014 International Conference on Software Engineering (ICSE), To appear.

A technical report is also available. It gives additional details:
Efficiently updating IDE-based data-flow analyses in response to incremental program changes (Steven Arzt, Eric Bodden), Technical report TUD-CS-2013-0253, EC SPRIDE, 2013.