Complex software systems often provide a large number of parameters so that users can configure them for their specific application scenarios. However, configuration tuning requires a deep understanding of the software system, far beyond the abilities of typical system users. To address this issue, many existing approaches focus on exploring and learning good performance estimation models. The accuracy of such models often suffers when the number of available samples is small, a thorny challenge under a given tuning-time constraint. By contrast, we hypothesize that good configurations often share certain hidden structures. Therefore, instead of trying to improve the performance estimation of a given configuration, we focus on capturing the hidden structures of good configurations and utilizing such learned structure to generate potentially better configurations. We propose ACTGAN to achieve this goal. We have implemented and evaluated ACTGAN using 17 workloads with eight different software systems. Experimental results show that ACTGAN outperforms default configurations by 76.22% on average, and six state-of-the-art configuration tuning algorithms by 6.58%-64.56%. Furthermore, the ACTGAN-generated configurations are often better than those used in training and show certain features consisting with domain knowledge, both of which supports our hypothesis.

Liang Bao

School of Computer Science and Technology, XiDian University

Xin Liu

Department of Computer Science, University of California, Davis

Fangzheng Wang

School of Computer Science and Technology, XiDian University

Baoyin Fang

School of Computer Science and Technology, XiDian University

Nowadays software tends to come in many different, yet similar variants, often derived from a common codebase 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 paper, we present a novel methodology, called SiMPOSE, 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 SiMPOSE 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 SiMPOSE 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 SiMPOSE constitutes, in most cases, the best efficiency/effectiveness trade-off.

Link to Publication: https://dl.acm.org/citation.cfm?doid=3343019.3313789

Dennis Reuling

Software Engineering Group, University of Siegen

Germany

Udo Kelter

Software Engineering Group, University of Siegen

Johannes Bürdek

TU Darmstadt, Real-time Systems Lab

Malte Lochau

TU Darmstadt

Code snippets are prevalent, but are hard to reuse because they often lack an accompanying environment configuration. Most are not actively maintained, allowing for drift between the most recent possible configuration and the code snippet as the snippet becomes out-of-date over time. Recent work has identified the problem of validating and detecting out-of-date code snippets as the most important consideration for code reuse. However, determining if a snippet is correct, but simply out-of-date, is a non-trivial task. In the best case, breaking changes are well documented, allowing developers to manually determine when a code snippet contains an out-of-date API usage. In the worst case, determining if and when a breaking change was made requires an exhaustive search through previous dependency versions.

We present V2, a strategy for determining if a code snippet is out-of-date by detecting discrete instances of configuration drift, where the snippet uses an API which has since undergone a breaking change. Each instance of configuration drift is classified by a failure encountered during validation and a configuration patch, consisting of dependency version changes, which fixes the underlying fault. V2 uses feedback-directed search to explore the possible configuration space for a code snippet, reducing the number of potential environment configurations that need to be validated. When run on a corpus of public Python snippets from prior research, V2 identifies 248 instances of configuration drift.

Eric Horton

North Carolina State University

United States

Chris Parnin

NCSU

United States

Unexpected interactions among features induce most bugs in a configurable software system. Exhaustively analyzing all the exponential number of possible configurations is prohibitively costly. Thus, various sampling techniques have been proposed to systematically narrow down the exponential number legal configurations to be analyzed. Since analyzing all selected configurations can require a huge amount of effort, fault-based configuration prioritization, that helps detect faults earlier, can yield practical benefits in quality assurance. In this paper, we propose CoPro, a novel formulation of feature-interaction bugs via common program entities enabled/disabled by the features. Leveraging from that, we develop an efficient feature-interaction-aware configuration prioritization technique for a configurable system by ranking the configurations according to their total number of potential bugs. We conducted several experiments to evaluate CoPro on the ability to detect configuration-related bugs in a public benchmark. We found that CoPro outperforms the state-of-the-art configuration prioritization techniques when we add them on advanced sampling algorithms. In 78% of the cases, CoPro ranks the buggy configurations at the top 3 positions. Interestingly, CoPro is able to detect 17 not-yet-discovered feature-interaction bugs

Son Nguyen

The University of Texas at Dallas

United States

Hoan Anh Nguyen

Amazon

United States

Ngoc Tran

University of Texas at Dallas

Hieu Tran

The University of Texas at Dallas

United States

Tien N. Nguyen

University of Texas at Dallas

United States

The significant rise in the complexity and configurations of software systems potentially requires a large number of test cases to test configurations of the systems. To deal with this challenge, we present a novel automated approach (termed as SBI) to implant existing test cases of software systems with the functionality to cover untested configurations of the software system; thus significantly reducing the effort to write new test cases to test the untested configurations. Our automated approach consists of two keys steps implemented into software components termed as Test Case Analyzer and Test Case Implanter. Test Case Analyzer automatically analyzes the code of test cases and generates a program dependence graph required by the second component. Test Case Implanter is implemented with a multi-objective search approach that searches for the most suitable test cases for implantation using search operators (i.e., selection, crossover, and mutation operators) followed by implanting the selected test cases by applying mutation operations focusing on adding, modifying, or deleting the test case source code. To guide the search, we defined various objectives: number of configuration variable values covered, pairwise coverage of parameter values of test API commands, number of implanted test cases, number of changed statements, and estimated execution time.
To assess the cost-effectiveness of our approach, we applied it to one industrial case study of video conferencing system and one open source case study. We experimented our approach (i.e., SBI) with three search algorithms: Non-dominated Sorting Genetic Algorithm II (NSGA-II), weight-based genetic algorithm (WGA), and random search (RS). In general, we found that the implanted test cases with SBI using the three algorithms had significantly higher configuration coverage than the original test cases for both case studies. When comparing the three algorithms with our approach, we found that NSGA-II performed the best. Specifically, SBI with NSGA-II managed to achieve, on average 19.3% higher number of configuration variable values and 57.0% higher pairwise coverage of parameter values of test API commands.

Link to Publication: https://www.sciencedirect.com/science/article/abs/pii/S0950584919300540

Dipesh Pradhan

Simula Research Laboratory, Norway

Shuai Wang

Hong Kong University of Science and Technology

Tao Yue

Nanjing University of Aeronautics and Astronautics & Simula Research Laboratory

China

Shaukat Ali

Simula Research Lab

Marius Liaaen

Cisco Systems

Norway