Automated N-way Program Merging for Facilitating Family-based Analyses of Variant-rich Software
| Autor: | Udo Kelter, Johannes Bürdek, Dennis Reuling, Malte Lochau |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Theoretical computer science
business.industry Computer science 020207 software engineering Context (language use) 02 engineering and technology Base (topology) Automaton Set (abstract data type) Software Factor (programming language) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing business Representation (mathematics) computer computer.programming_language Abstraction (linguistics) |
| Zdroj: | ACM Transactions on Software Engineering and Methodology. 28:1-59 |
| ISSN: | 1557-7392 1049-331X |
| DOI: | 10.1145/3313789 |
| Popis: | Nowadays software tends to come in many different, yet similar variants, often derived from a common code base via clone-and-own. Family-based-analysis strategies have recently shown very promising potential for improving efficiency in applying quality-assurance techniques to such variant-rich programs, as compared to variant-by-variant approaches. Unfortunately, these strategies require a single program representation superimposing all program variants in a syntactically well-formed, semantically sound, and variant-preserving manner, which is usually not available and manually hard to obtain in practice. In this article, we present a novel methodology, called S i MPOSE, for automatically generating superimpositions of existing program variants to facilitate family-based analyses of variant-rich software. To this end, we propose a novel N-way model-merging methodology to integrate the control-flow automaton (CFA) representations of N given variants of a C program into one unified CFA representation. CFA constitute a unified program abstraction used by many recent software-analysis tools for automated quality assurance. To cope with the inherent complexity of N-way model-merging, our approach (1) utilizes principles of similarity-propagation to reduce the number of potential N-way matches, and (2) enables us to decompose a set of N variants into arbitrary subsets and to incrementally derive an N-way superimposition from partial superimpositions. We apply our tool implementation of S i MPOSE to a selection of realistic C programs, frequently considered for experimental evaluation of program-analysis techniques. In particular, we investigate applicability and efficiency/effectiveness trade-offs of our approach by applying S i MPOSE in the context of family-based unit-test generation as well as model-checking as sample program-analysis techniques. Our experimental results reveal very impressive efficiency improvements by an average factor of up to 2.6 for test-generation and up to 2.4 for model-checking under stable effectiveness, as compared to variant-by-variant approaches, thus amortizing the additional effort required for merging. In addition, our results show that merging all N variants at once produces, in almost all cases, clearly more precise results than incremental step-wise 2-way merging. Finally, our comparison with major existing N-way merging techniques shows that S i MPOSE constitutes, in most cases, the best efficiency/effectiveness trade-off. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|