PaperlayerView exact revision on arXiv

Source-linked AI summary

A Comparison of 10 Sampling Algorithms for Configurable Systems

Flávio Medeiros, Christian Kästner, Márcio Ribeiro, Rohit Gheyi, Sven Apel

arXiv:1602.02052v3cs.SE

TL;DR

Configurable systems have exponentially large configuration spaces, making exhaustive analysis impractical and configuration-related faults difficult to detect. This paper compares 10 sampling algorithms, finding that larger samples generally detect more faults, while simple small samples are often most efficient.

  • Problem

    Exponential configuration spaces make exhaustive analysis infeasible, while faults arising only from particular option combinations are difficult to find.

  • Method

    The study compares 10 sampling algorithms using a corpus of configuration-related faults and evaluates fault detection, sample size, and efficiency.

  • Results

    All algorithms detected more than 66% of faults; six-wise detected the most, while most-enabled-disabled, pair-wise, and statement-coverage were most efficient.

  • Takeaways & Limitations

    Sampling algorithms trade fault-detection capability against sample-set size, with simple algorithms such as most-enabled-disabled offering strong efficiency in most contexts.

  • Takeaways & Limitations

    The findings cannot be generalized to systems whose variability is implemented through mechanisms other than conditional compilation.

Abstract

from arXiv · show

Almost every software system provides configuration options to tailor the system to the target platform and application scenario. Often, this configurability renders the analysis of every individual system configuration infeasible. To address this problem, researchers have proposed a diverse set of sampling algorithms. We present a comparative study of 10 state-of-the-art sampling algorithms regarding their fault-detection capability and size of sample sets. The former is important to improve software quality and the latter to reduce the time of analysis. In a nutshell, we found that sampling algorithms with larger sample sets are able to detect higher numbers of faults, but simple algorithms with small sample sets, such as most-enabled-disabled, are the most efficient in most contexts. Furthermore, we observed that the limiting assumptions made in previous work influence the number of detected faults, the size of sample sets, and the ranking of algorithms. Finally, we have identified a number of technical challenges when trying to avoid the limiting assumptions, which questions the practicality of certain sampling algorithms.

1. INTRODUCTION

Configurable systems make exhaustive quality assurance infeasible, motivating sampling algorithms that trade sample-set size against fault-detection capability. This study compares 10 algorithms and examines how realistic analysis information changes their effectiveness and practicality.

  • Motivation: Exponential configuration spaces make analyzing every configuration infeasible, especially when faults occur only in particular option combinations.The Linux Kernel alone has more than 12 thousand compile-time configuration options.
  • Motivation: Sampling selects a subset of configurations for individual analysis, but fault-detection effectiveness depends substantially on the selection algorithm.Sampling enables reuse of mature single-configuration quality-assurance tools.
  • Study design: The study compares 10 sampling algorithms and 35 algorithm combinations using sample-set size and fault-detection capability as primary dimensions.It evaluates 135 known configuration-related faults in 24 open-source C systems.
  • Findings: All algorithms detected more than 66% of configuration-related faults, while larger sample sets generally detected more faults.Simple algorithms with small samples, particularly most-enabled-disabled, were most efficient in many scenarios.
  • Realistic assumptions: Constraints, header files, build-system information, and global analysis substantially affect algorithm performance and can make several algorithms infeasible in practice.These factors can also change the efficiency ranking of sampling algorithms.
  • Findings: The study identifies algorithm combinations that balance sample-set size and fault-detection capability under different assumptions.The authors specifically support efficient trade-offs such as most-enabled-disabled.

2. CONFIGURATION-RELATED FAULTS

Configuration-related faults may appear only in particular combinations of options, while conventional analysis tools inspect one preprocessed configuration at a time. Sampling can reduce the search space, but some algorithms cannot expose faults requiring mixed option states.

  • Configuration variability: Conditional compilation generates distinct system configurations by enabling or disabling configuration options.The Libpng example has four configurations from SPLT and POINTER.
  • Configuration-related faults: The Libpng fault occurs when SPLT is enabled and POINTER is disabled, producing a compilation error because variable p is undeclared.The fault is therefore tied to a specific combination of option states.
  • Configuration-related faults: Standard C analysis tools operate on one preprocessed configuration at a time and therefore do not expose faults absent from the selected configuration.Other configurations of the same code can compile without warning or error.
  • Sampling: Sampling algorithms analyze only selected configurations, so most-enabled-disabled misses the Libpng fault because it tests only all-enabled and all-disabled states.The fault requires enabling one option while disabling another.
  • Research context: Prior sampling research often assumes per-file analysis and ignores constraints, header files, and build-system information.The study evaluates these assumptions rather than treating them as universally realistic.

ALGORITHMS

The study compares sampling algorithms by their fault-detection tradeoffs, sample-set sizes, and sensitivity to assumptions in configurable C systems. It introduces algorithms ranging from t-wise and statement-coverage to simple enabled/disabled strategies and random sampling.

  • Study design: The study evaluates sampling algorithms using sample-set size and fault-detection capability as dependent variables.The experimental design compares algorithms across software systems and measures how many faults and configurations they identify or select.
  • Study design: The first study compares algorithms under favorable assumptions, while the second examines constraints, header files, build-system information, and global analysis.The two-step design separates baseline tradeoffs from the influence of assumptions often neglected in prior work and practice.
  • Sampling algorithms: t-wise sampling covers all combinations of t configuration options, with sample-set sizes increasing as t increases.Pair-wise sampling checks every pair, whereas three-wise through six-wise sampling require progressively larger sample sets.
  • Sampling algorithms: Statement-coverage selects configurations that enable each optional-code block at least once.The implementation used in the study selects configurations to cover optional code, rather than detecting dead code.
  • Sampling algorithms: Most-enabled-disabled uses two configurations regardless of the number of options, enabling all options in one and disabling all in the other when unconstrained.One-disabled disables one option at a time, while one-enabled enables one option at a time.
  • Sampling algorithms: Random sampling generates a specified maximum number n of distinct configurations per file by randomly assigning true or false to each option.If exhaustive enumeration requires fewer configurations than n, random sampling selects all configurations.

4. DETECTING FAULTS

The study compares sampling algorithms by the faults they detect and the sample-set sizes they require, using a corpus of known configuration-related faults. Results show a tradeoff: larger samples generally detect more faults, while some small-set algorithms are more efficient.

  • Study design: The first study evaluated 10 sampling algorithms on 135 known faults from 24 open-source systems under favorable assumptions.The analysis excluded constraints, global analysis, build-system information, and header files, and performed per-file comparisons.
  • Corpus of faults: 83% of faults involved one or two configuration options, while less than 5% involved more than four options.The corpus included faults requiring enabling options, disabling options, or both.
  • Fault detection: All algorithms detected more than 66% of faults; six-wise detected the highest number, while statement-coverage detected the lowest.Statement-coverage missed 45 faults requiring specific combinations of enabled and disabled options.
  • Fault detection: All t-wise algorithms detected more than 92% of the 135 faults, with five-wise and six-wise detecting all faults.Random sampling detected 124 faults, or 92%, on average across runs.
  • Sample size: Sample sets ranged from 1.3 to 10 configurations per file, with most-enabled-disabled smallest and six-wise largest.Six-wise required more than 500K sampled configurations across all projects, while random selected 2.6 samples per file on average.
  • Efficiency: Most-enabled-disabled, pair-wise, and statement-coverage were the most efficient algorithms, while some combinations balanced sample size and fault detection.Efficiency reflects the number of configurations that must be checked per detected fault; the study also analyzed 35 algorithm combinations and their Pareto front.

5. EFFECTS OF ASSUMPTIONS

Lifting assumptions about constraints, headers, global scope, and build systems changes fault detection, sample-set size, and algorithm feasibility or ranking. More realistic analyses can substantially increase computational costs and make several algorithms impractical.

  • Constraints: Three-wise and higher t-wise sampling was intractable for the Linux Kernel, including memory exhaustion with 120 Gb RAM.Pair-wise sampling also detected fewer faults after constraint-aware heuristics failed to cover all valid option pairs.
  • Constraints: 0.75 seconds per file with constraints versus 0.04 seconds without constraints increased Linux Kernel analysis from 15 minutes to over 4 hours.
  • Global Analysis: Global analysis can detect faults spanning multiple files but causes an option explosion, making t-wise and statement-coverage sample sets too large.No t-wise algorithm produced global sample sets at the scale of the subject systems.
  • Header Files: 238 header-derived configuration options were added per Linux Kernel file on average, compared with 3 options when headers were ignored.Sample sets grew for all algorithms except most-enabled-disabled, and some algorithms became infeasible.
  • Build-System Information: 97% of Linux Kernel files and 80% of BusyBox files are compiled only in certain configurations, showing the build system’s strong influence on configurability.Including build-system information reduced single-option-detectable faults from 40% to 17%, while sample-set sizes increased slightly.

6. THREATS TO VALIDITY

The study’s validity is constrained by its fault corpus and by its focus on systems using conditional compilation. The authors address corpus concerns through bias avoidance and a complementary automated bug-finding experiment.

  • The results cannot be generalized to systems that implement variability mechanisms other than conditional compilation.
  • The fault corpus may be biased toward popular system configurations because it was partially mined from software repositories.The authors note that they cannot know all faults in a system and therefore cannot establish a fully representative corpus.
  • A complementary Cppcheck experiment produced comparable results, triangulating the corpus-based findings despite introducing false-positive threats.

7. GUIDANCE FOR PRACTITIONERS

The study offers context-dependent guidance rather than a universally best sampling algorithm. Practitioners should balance analysis speed against fault minimization and account for realistic assumptions.

  • No sampling algorithm is optimal for all systems and conditions, so practitioners should use the results to identify plausible candidates for their scenario.
  • Small-sample algorithms may suit early development, whereas larger samples may be preferred before release to minimize configuration-related faults.
  • Under constraints, headers, and global analysis, simple algorithms such as most-enabled-disabled are recommended because many alternatives become intractable.

8. RELATED WORK

Prior work studied preprocessor usage, configuration faults, sampling strategies, and variability-aware analysis, but often omitted realistic C-system complexities. This study fills that comparison gap by evaluating sampling algorithms under influential assumptions.

  • Empirical studies linked undisciplined C-preprocessor use to configuration-related problems and motivated sampling-based fault detection.
  • Earlier fault studies found that most configuration-related faults involve only a few options, consistent with this study’s findings.
  • Prior sampling research proposed t-wise, statement-coverage, and one-disabled strategies, but often ignored constraints, headers, or build-system information.
  • Variability-aware analyses examine configurations simultaneously but face setup difficulties, narrow detectable-fault classes, and false positives.
  • This study complements prior sample-based and variability-aware comparisons by evaluating sampling algorithms while examining the assumptions used in earlier studies.

9. CONCLUDING REMARKS

The study compares sampling effort and fault-detection capability across 10 algorithms, then examines how analysis information and assumptions affect those tradeoffs. Its findings are intended to help developers choose algorithms and analysis information while recognizing practical costs.

  • 10 sampling algorithms were compared using sample sizes and fault-detection capabilities across 135 known faults in 24 open-source C systems.
  • At least 66% of the 135 known faults were covered by every algorithm under the first study’s assumptions.
  • Considering constraints reduces false positives but increases sample-generation costs, while global analysis and header files can make most algorithms practically infeasible.
  • Build-system information requires difficult analysis and adds some configuration options but produces no significant changes.
  • The findings support selecting sampling algorithms and analysis information by weighing effort against fault-detection capability.

A. CPPCHECK WARNINGS

This experiment compares sampling algorithms using Cppcheck warnings rather than a corpus of known faults. It uses the tool as an automated proxy for configuration-related fault detection across sampled configurations.

  • The experiment compares the RQ1–3 sampling algorithms using a static-analysis tool instead of a corpus of known faults.
  • Cppcheck runs on each sampled configuration of each file, and warnings occurring in every configuration are discarded as non-configuration-related.
  • The study uses a fresh set of configurable C systems that does not overlap with Study 1’s corpus.

A.1 Results and Discussion

Cppcheck detected configuration-specific warnings across sampled configurations, with larger samples generally finding more warnings but differing in efficiency. The results largely confirm Study 1 while exposing costs associated with broader analysis.

  • Results and Discussion: 96 configuration-related warnings occurred in 77 distinct files; every algorithm detected more than 70%, but none detected all warnings.
  • Results and Discussion: Combinations C2 and C3 reported all 96 warnings, while C2, C3, C5, and C6 formed the Pareto Front.
  • Results and Discussion: Sample sets ranged from 1.3 to 13.2 configurations per file, with six-wise selecting the most and one-enabled and one-disabled the fewest configurations.
  • Results and Discussion: Global analysis and header-file inclusion can make sampling practically infeasible for most algorithms because they greatly enlarge the considered configuration space and sample sets.
  • Results and Discussion: The efficiency ranking was one-enabled, statement-coverage, one-disabled, pair-wise, most-enabled-disabled, three-wise, random, four-wise, five-wise, and six-wise.
  • Results and Discussion: Using Cppcheck and known-fault corpora produced essentially the same fault-detection results, increasing confidence through triangulation.
Loading 1602.02052v3…