Standard

Incrementalizing Lattice-Based Program Analyses in Datalog. / Szabo, Tamas; Bergmann, Gábor; Erdweg, Sebastian; Voelter, Markus.

In: Proceedings of the ACM on Programming Languages, Vol. 2, No. OOPSLA, 139, 2018, p. 1-29.

Research output: Contribution to journalArticleScientificpeer-review

Harvard

Szabo, T, Bergmann, G, Erdweg, S & Voelter, M 2018, 'Incrementalizing Lattice-Based Program Analyses in Datalog' Proceedings of the ACM on Programming Languages, vol. 2, no. OOPSLA, 139, pp. 1-29. https://doi.org/10.1145/3276509

APA

Szabo, T., Bergmann, G., Erdweg, S., & Voelter, M. (2018). Incrementalizing Lattice-Based Program Analyses in Datalog. Proceedings of the ACM on Programming Languages, 2(OOPSLA), 1-29. [139]. https://doi.org/10.1145/3276509

Vancouver

Szabo T, Bergmann G, Erdweg S, Voelter M. Incrementalizing Lattice-Based Program Analyses in Datalog. Proceedings of the ACM on Programming Languages. 2018;2(OOPSLA):1-29. 139. https://doi.org/10.1145/3276509

Author

Szabo, Tamas ; Bergmann, Gábor ; Erdweg, Sebastian ; Voelter, Markus. / Incrementalizing Lattice-Based Program Analyses in Datalog. In: Proceedings of the ACM on Programming Languages. 2018 ; Vol. 2, No. OOPSLA. pp. 1-29.

BibTeX

@article{032637234cdd446f879203ed6404cc85,
title = "Incrementalizing Lattice-Based Program Analyses in Datalog",
abstract = "Program analyses detect errors in code, but when code changes frequently as in an IDE, repeated re-analysis from-scratch is unnecessary: It leads to poor performance unless we give up on precision and recall. Incremental program analysis promises to deliver fast feedback without giving up on precision or recall by deriving a new analysis result from the previous one. However, Datalog and other existing frameworks for incremental program analysis are limited in expressive power: They only support the powerset lattice as representation of analysis results, whereas many practically relevant analyses require custom lattices and aggregation over lattice values. To this end, we present a novel algorithm called DRedL that supports incremental maintenance of recursive lattice-value aggregation in Datalog. The key insight of DRedL is to dynamically recognize increasing replacements of old lattice values by new ones, which allows us to avoid the expensive deletion of the old value. We integrate DRedL into the analysis framework IncA and use IncA to realize incremental implementations of strong-update points-to analysis and string analysis for Java. As our performance evaluation demonstrates, both analyses react to code changes within milliseconds.",
author = "Tamas Szabo and G{\'a}bor Bergmann and Sebastian Erdweg and Markus Voelter",
year = "2018",
doi = "10.1145/3276509",
language = "English",
volume = "2",
pages = "1--29",
journal = "Proceedings of the ACM on Programming Languages",
issn = "2475-1421",
number = "OOPSLA",

}

RIS

TY - JOUR

T1 - Incrementalizing Lattice-Based Program Analyses in Datalog

AU - Szabo, Tamas

AU - Bergmann, Gábor

AU - Erdweg, Sebastian

AU - Voelter, Markus

PY - 2018

Y1 - 2018

N2 - Program analyses detect errors in code, but when code changes frequently as in an IDE, repeated re-analysis from-scratch is unnecessary: It leads to poor performance unless we give up on precision and recall. Incremental program analysis promises to deliver fast feedback without giving up on precision or recall by deriving a new analysis result from the previous one. However, Datalog and other existing frameworks for incremental program analysis are limited in expressive power: They only support the powerset lattice as representation of analysis results, whereas many practically relevant analyses require custom lattices and aggregation over lattice values. To this end, we present a novel algorithm called DRedL that supports incremental maintenance of recursive lattice-value aggregation in Datalog. The key insight of DRedL is to dynamically recognize increasing replacements of old lattice values by new ones, which allows us to avoid the expensive deletion of the old value. We integrate DRedL into the analysis framework IncA and use IncA to realize incremental implementations of strong-update points-to analysis and string analysis for Java. As our performance evaluation demonstrates, both analyses react to code changes within milliseconds.

AB - Program analyses detect errors in code, but when code changes frequently as in an IDE, repeated re-analysis from-scratch is unnecessary: It leads to poor performance unless we give up on precision and recall. Incremental program analysis promises to deliver fast feedback without giving up on precision or recall by deriving a new analysis result from the previous one. However, Datalog and other existing frameworks for incremental program analysis are limited in expressive power: They only support the powerset lattice as representation of analysis results, whereas many practically relevant analyses require custom lattices and aggregation over lattice values. To this end, we present a novel algorithm called DRedL that supports incremental maintenance of recursive lattice-value aggregation in Datalog. The key insight of DRedL is to dynamically recognize increasing replacements of old lattice values by new ones, which allows us to avoid the expensive deletion of the old value. We integrate DRedL into the analysis framework IncA and use IncA to realize incremental implementations of strong-update points-to analysis and string analysis for Java. As our performance evaluation demonstrates, both analyses react to code changes within milliseconds.

U2 - 10.1145/3276509

DO - 10.1145/3276509

M3 - Article

VL - 2

SP - 1

EP - 29

JO - Proceedings of the ACM on Programming Languages

T2 - Proceedings of the ACM on Programming Languages

JF - Proceedings of the ACM on Programming Languages

SN - 2475-1421

IS - OOPSLA

M1 - 139

ER -

ID: 52210265