ITU

Variability abstractions for lifted analyses

Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-review

Standard

Variability abstractions for lifted analyses. / Dimovski, Aleksandar; Brabrand, Claus; Wasowski, Andrzej.

In: Science of Computer Programming, Vol. 159, 2018, p. 1-27.

Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-review

Harvard

APA

Vancouver

Author

Bibtex

@article{09e50a2b5a8f47158b49f135adba9dab,
title = "Variability abstractions for lifted analyses",
abstract = "Family-based (lifted) static analysis for “highly configurable programs” (program families) is capable of analyzing all variants at once without generating any of them explicitly. It takes as input only the common code base, which encodes all variants of a program family, and produces precise analysis results corresponding to all variants. However, the computational cost of the lifted analysis still depends inherently on the number of variants, which is in the worst case exponential in the number of statically configurable options (features). For a large number of features, the lifted analysis may be too costly or even infeasible. In this work, we introduce variability abstractions defined as Galois connections, which simplify variability away from program families based on -s. Then, we use abstract interpretation as a formal method for the calculational-based derivation of abstracted lifted analyses, which are sound by construction.Our approach for abstracting lifted analysis is orthogonal to the particular program analysis chosen as a client. While a single program analysis operates on program states and depends on language-specific constructs, the lifted analysis assumes that a single program analysis already exists and lifts its results to all variants of the analyzed program family. Variability abstractions aim to reduce this variability-specific component of the lifted analysis, which handles variability and -s. Furthermore, given the “orthogonality” of variability abstractions to the rest of the analysis (its language-specific component), we can implement abstractions as a preprocessor. In particular, given an abstraction we define a syntactic transformation, which translates any program family into an abstracted version of it, such that the analysis of the abstracted program family coincides with the corresponding abstracted analysis of the original program family. We have implemented the proposed approach, and we evaluate its practicality on three Java benchmarks. The evaluation shows that abstractions yield significant performance gains, especially for families with higher variability.",
keywords = "Program families, Static analysis, Abstract interpretation",
author = "Aleksandar Dimovski and Claus Brabrand and Andrzej Wasowski",
year = "2018",
doi = "10.1016/j.scico.2017.12.012",
language = "English",
volume = "159",
pages = "1--27",
journal = "Science of Computer Programming",
issn = "0167-6423",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Variability abstractions for lifted analyses

AU - Dimovski, Aleksandar

AU - Brabrand, Claus

AU - Wasowski, Andrzej

PY - 2018

Y1 - 2018

N2 - Family-based (lifted) static analysis for “highly configurable programs” (program families) is capable of analyzing all variants at once without generating any of them explicitly. It takes as input only the common code base, which encodes all variants of a program family, and produces precise analysis results corresponding to all variants. However, the computational cost of the lifted analysis still depends inherently on the number of variants, which is in the worst case exponential in the number of statically configurable options (features). For a large number of features, the lifted analysis may be too costly or even infeasible. In this work, we introduce variability abstractions defined as Galois connections, which simplify variability away from program families based on -s. Then, we use abstract interpretation as a formal method for the calculational-based derivation of abstracted lifted analyses, which are sound by construction.Our approach for abstracting lifted analysis is orthogonal to the particular program analysis chosen as a client. While a single program analysis operates on program states and depends on language-specific constructs, the lifted analysis assumes that a single program analysis already exists and lifts its results to all variants of the analyzed program family. Variability abstractions aim to reduce this variability-specific component of the lifted analysis, which handles variability and -s. Furthermore, given the “orthogonality” of variability abstractions to the rest of the analysis (its language-specific component), we can implement abstractions as a preprocessor. In particular, given an abstraction we define a syntactic transformation, which translates any program family into an abstracted version of it, such that the analysis of the abstracted program family coincides with the corresponding abstracted analysis of the original program family. We have implemented the proposed approach, and we evaluate its practicality on three Java benchmarks. The evaluation shows that abstractions yield significant performance gains, especially for families with higher variability.

AB - Family-based (lifted) static analysis for “highly configurable programs” (program families) is capable of analyzing all variants at once without generating any of them explicitly. It takes as input only the common code base, which encodes all variants of a program family, and produces precise analysis results corresponding to all variants. However, the computational cost of the lifted analysis still depends inherently on the number of variants, which is in the worst case exponential in the number of statically configurable options (features). For a large number of features, the lifted analysis may be too costly or even infeasible. In this work, we introduce variability abstractions defined as Galois connections, which simplify variability away from program families based on -s. Then, we use abstract interpretation as a formal method for the calculational-based derivation of abstracted lifted analyses, which are sound by construction.Our approach for abstracting lifted analysis is orthogonal to the particular program analysis chosen as a client. While a single program analysis operates on program states and depends on language-specific constructs, the lifted analysis assumes that a single program analysis already exists and lifts its results to all variants of the analyzed program family. Variability abstractions aim to reduce this variability-specific component of the lifted analysis, which handles variability and -s. Furthermore, given the “orthogonality” of variability abstractions to the rest of the analysis (its language-specific component), we can implement abstractions as a preprocessor. In particular, given an abstraction we define a syntactic transformation, which translates any program family into an abstracted version of it, such that the analysis of the abstracted program family coincides with the corresponding abstracted analysis of the original program family. We have implemented the proposed approach, and we evaluate its practicality on three Java benchmarks. The evaluation shows that abstractions yield significant performance gains, especially for families with higher variability.

KW - Program families

KW - Static analysis

KW - Abstract interpretation

U2 - 10.1016/j.scico.2017.12.012

DO - 10.1016/j.scico.2017.12.012

M3 - Journal article

VL - 159

SP - 1

EP - 27

JO - Science of Computer Programming

JF - Science of Computer Programming

SN - 0167-6423

ER -

ID: 82396842