Search Results

Documents authored by Dimovski, Aleksandar S.

Document
DOI: 10.4230/LIPIcs.ECOOP.2024.12
Mutation-Based Lifted Repair of Software Product Lines

Authors: Aleksandar S. Dimovski

Published in: LIPIcs, Volume 313, 38th European Conference on Object-Oriented Programming (ECOOP 2024)

Abstract
This paper presents a novel lifted repair algorithm for program families (Software Product Lines - SPLs) based on code mutations. The inputs of our algorithm are an erroneous SPL and a specification given in the form of assertions. We use variability encoding to transform the given SPL into a single program, called family simulator, which is translated into a set of SMT formulas whose conjunction is satisfiable iff the simulator (i.e., the input SPL) violates an assertion. We use a predefined set of mutations applied to feature and program expressions of the given SPL. The algorithm repeatedly mutates the erroneous family simulator and checks if it becomes (bounded) correct. Since mutating an expression corresponds to mutating a formula in the set of SMT formulas encoding the family simulator, the search for a correct mutant is reduced to searching an unsatisfiable set of SMT formulas. To efficiently explore the huge state space of mutants, we call SAT and SMT solvers in an incremental way. The outputs of our algorithm are all minimal repairs in the form of minimal number of (feature and program) expression replacements such that the repaired SPL is (bounded) correct with respect to a given set of assertions. We have implemented our algorithm in a prototype tool and evaluated it on a set of #ifdef-based C programs (i.e., annotative SPLs). The experimental results show that our approach is able to successfully repair various interesting SPLs.
Cite as

Aleksandar S. Dimovski. Mutation-Based Lifted Repair of Software Product Lines. In 38th European Conference on Object-Oriented Programming (ECOOP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 313, pp. 12:1-12:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dimovski:LIPIcs.ECOOP.2024.12,
  author =	{Dimovski, Aleksandar S.},
  title =	{{Mutation-Based Lifted Repair of Software Product Lines}},
  booktitle =	{38th European Conference on Object-Oriented Programming (ECOOP 2024)},
  pages =	{12:1--12:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-341-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{313},
  editor =	{Aldrich, Jonathan and Salvaneschi, Guido},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2024.12},
  URN =		{urn:nbn:de:0030-drops-208613},
  doi =		{10.4230/LIPIcs.ECOOP.2024.12},
  annote =	{Keywords: Program repair, Software Product Lines, Code mutations, Variability encoding}
}
Document
Artifact
DOI: 10.4230/DARTS.10.2.5
Mutation-Based Lifted Repair of Software Product Lines (Artifact)

Authors: Aleksandar S. Dimovski

Published in: DARTS, Volume 10, Issue 2, Special Issue of the 38th European Conference on Object-Oriented Programming (ECOOP 2024)

Abstract
In this work, we describe the installation, usage, and evaluation results of the tool SPLAllRepair, which is introduced by the paper "Mutation-based Lifted Repair of Software Product Lines". We provide step-by-step instructions on how to download, run, and compare the tool’s outputs to outputs described in the paper. The tool implements a novel lifted repair algorithm for program families (Software Product Lines - SPLs) based on code mutations. The inputs of our algorithm are an erroneous SPL and a specification given in the form of assertions. We use variability encoding to transform the given SPL into a single program, called family simulator, which is translated into a set of SMT formulas whose conjunction is satisfiable iff the simulator (i.e. the input SPL) violates an assertion. We use a predefined set of mutations applied to feature and program expressions of the given SPL. The algorithm repeatedly mutates the erroneous family simulator and checks if it becomes (bounded) correct. The outputs are all minimal repairs in the form of minimal number of (feature and program) expression replacements such that the repaired SPL is (bounded) correct with respect to a given set of assertions. We present the experimental results showing that our approach is able to successfully repair various interesting #ifdef-based C SPLs.
Cite as

Aleksandar S. Dimovski. Mutation-Based Lifted Repair of Software Product Lines (Artifact). In Special Issue of the 38th European Conference on Object-Oriented Programming (ECOOP 2024). Dagstuhl Artifacts Series (DARTS), Volume 10, Issue 2, pp. 5:1-5:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{dimovski:DARTS.10.2.5,
  author =	{Dimovski, Aleksandar S.},
  title =	{{Mutation-Based Lifted Repair of Software Product Lines (Artifact)}},
  pages =	{5:1--5:5},
  journal =	{Dagstuhl Artifacts Series},
  ISBN =	{978-3-95977-342-3},
  ISSN =	{2509-8195},
  year =	{2024},
  volume =	{10},
  number =	{2},
  editor =	{Dimovski, Aleksandar S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.10.2.5},
  URN =		{urn:nbn:de:0030-drops-209036},
  doi =		{10.4230/DARTS.10.2.5},
  annote =	{Keywords: Program repair, Software Product Lines, Code mutations, Variability encoding}
}
Document
Artifact
DOI: 10.4230/DARTS.7.2.6
Lifted Static Analysis of Dynamic Program Families by Abstract Interpretation (Artifact)

Authors: Aleksandar S. Dimovski and Sven Apel

Published in: DARTS, Volume 7, Issue 2, Special Issue of the 35th European Conference on Object-Oriented Programming (ECOOP 2021)

Abstract
In this article, we describe the usage and evaluation results of the tool DSPLNum²Analyzer introduced by the paper "Lifted Static Analysis of Dynamic Program Families by Abstract Interpretation". We provide step-by-step instructions on how to download, install, run, and compare the tool’s outputs to outputs described in the paper. DSPLNum²Analyzer is a research prototype lifted static analyzer based on abstract interpretation designed for performing numerical static analysis of dynamic C program families.
Cite as

Aleksandar S. Dimovski and Sven Apel. Lifted Static Analysis of Dynamic Program Families by Abstract Interpretation (Artifact). In Special Issue of the 35th European Conference on Object-Oriented Programming (ECOOP 2021). Dagstuhl Artifacts Series (DARTS), Volume 7, Issue 2, pp. 6:1-6:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{dimovski_et_al:DARTS.7.2.6,
  author =	{Dimovski, Aleksandar S. and Apel, Sven},
  title =	{{Lifted Static Analysis of Dynamic Program Families by Abstract Interpretation (Artifact)}},
  pages =	{6:1--6:6},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2021},
  volume =	{7},
  number =	{2},
  editor =	{Dimovski, Aleksandar S. and Apel, Sven},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.7.2.6},
  URN =		{urn:nbn:de:0030-drops-140303},
  doi =		{10.4230/DARTS.7.2.6},
  annote =	{Keywords: Dynamic program families, Static analysis, Abstract interpretation, Decision tree lifted domain}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2021.14
Lifted Static Analysis of Dynamic Program Families by Abstract Interpretation

Authors: Aleksandar S. Dimovski and Sven Apel

Published in: LIPIcs, Volume 194, 35th European Conference on Object-Oriented Programming (ECOOP 2021)

Abstract
Program families (software product lines) are increasingly adopted by industry for building families of related software systems. A program family offers a set of features (configured options) to control the presence and absence of software functionality. Features in program families are often assigned at compile-time, so their values can only be read at run-time. However, today many program families and application domains demand run-time adaptation, reconfiguration, and post-deployment tuning. Dynamic program families (dynamic software product lines) have emerged as an attempt to handle variability at run-time. Features in dynamic program families can be controlled by ordinary program variables, so reads and writes to them may happen at run-time. Recently, a decision tree lifted domain for analyzing traditional program families with numerical features has been proposed, in which decision nodes contain linear constraints defined over numerical features and leaf nodes contain analysis properties defined over program variables. Decision nodes partition the configuration space of possible feature values, while leaf nodes provide analysis information corresponding to each partition of the configuration space. As features are statically assigned at compile-time, decision nodes can be added, modified, and deleted only when analyzing read accesses of features. In this work, we extend the decision tree lifted domain so that it can be used to efficiently analyze dynamic program families with numerical features. Since features can now be changed at run-time, decision nodes can be modified when handling read and write accesses of feature variables. For this purpose, we define extended transfer functions for assignments and tests as well as a special widening operator to ensure termination of the lifted analysis. To illustrate the potential of this approach, we have implemented a lifted static analyzer, called DSPLNum²Analyzer, for inferring numerical invariants of dynamic program families written in C. An empirical evaluation on benchmarks from SV-COMP indicates that our tool is effective and provides a flexible way of adjusting the precision/cost ratio in static analysis of dynamic program families.
Cite as

Aleksandar S. Dimovski and Sven Apel. Lifted Static Analysis of Dynamic Program Families by Abstract Interpretation. In 35th European Conference on Object-Oriented Programming (ECOOP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 194, pp. 14:1-14:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{dimovski_et_al:LIPIcs.ECOOP.2021.14,
  author =	{Dimovski, Aleksandar S. and Apel, Sven},
  title =	{{Lifted Static Analysis of Dynamic Program Families by Abstract Interpretation}},
  booktitle =	{35th European Conference on Object-Oriented Programming (ECOOP 2021)},
  pages =	{14:1--14:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-190-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{194},
  editor =	{M{\o}ller, Anders and Sridharan, Manu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2021.14},
  URN =		{urn:nbn:de:0030-drops-140572},
  doi =		{10.4230/LIPIcs.ECOOP.2021.14},
  annote =	{Keywords: Dynamic program families, Static analysis, Abstract interpretation, Decision tree lifted domain}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2015.247
Variability Abstractions: Trading Precision for Speed in Family-Based Analyses

Authors: Aleksandar S. Dimovski, Claus Brabrand, and Andrzej Wasowski

Published in: LIPIcs, Volume 37, 29th European Conference on Object-Oriented Programming (ECOOP 2015)

Abstract
Family-based (lifted) data-flow analysis for Software Product Lines (SPLs) is capable of analyzing all valid products (variants) without generating any of them explicitly. It takes as input only the common code base, which encodes all variants of a SPL, and produces analysis results corresponding to all variants. However, the computational cost of the lifted analysis still depends inherently on the number of variants (which is exponential in the number of features, in the worst case). For a large number of features, the lifted analysis may be too costly or even infeasible. In this paper, we introduce variability abstractions defined as Galois connections and use abstract interpretation as a formal method for the calculational-based derivation of approximate (abstracted) lifted analyses of SPL programs, which are sound by construction. Moreover, given an abstraction we define a syntactic transformation that translates any SPL program into an abstracted version of it, such that the analysis of the abstracted SPL coincides with the corresponding abstracted analysis of the original SPL. We implement the transformation in a tool, that works on Object-Oriented Java program families, and evaluate the practicality of this approach on three Java SPL benchmarks.
Cite as

Aleksandar S. Dimovski, Claus Brabrand, and Andrzej Wasowski. Variability Abstractions: Trading Precision for Speed in Family-Based Analyses. In 29th European Conference on Object-Oriented Programming (ECOOP 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 37, pp. 247-270, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{dimovski_et_al:LIPIcs.ECOOP.2015.247,
  author =	{Dimovski, Aleksandar S. and Brabrand, Claus and Wasowski, Andrzej},
  title =	{{Variability Abstractions: Trading Precision for Speed in Family-Based Analyses}},
  booktitle =	{29th European Conference on Object-Oriented Programming (ECOOP 2015)},
  pages =	{247--270},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-86-6},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{37},
  editor =	{Boyland, John Tang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2015.247},
  URN =		{urn:nbn:de:0030-drops-52253},
  doi =		{10.4230/LIPIcs.ECOOP.2015.247},
  annote =	{Keywords: Software Product Lines, Family-Based Program Analysis, Abstract Interpretation}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact