An Improved Meta-heuristic Search for Constrained Interaction Testing

Combinatorial interaction testing (CIT) is a cost-effective sampling technique for discovering interaction faults in highly configurable systems. Recent work with greedy CIT algorithms efficiently supports constraints on the features that can coexist in a configuration. But when testing a single sys...

Full description

Saved in:
Bibliographic Details
Main Authors: Garvin, B.J., Cohen, M.B., Dwyer, M.B.
Format: Conference Proceeding
Language:English
Subjects:
combinatorial interaction testing
Computer science
constrained covering arrays
Costs
Greedy algorithms
highly-configurable software
Performance evaluation
Runtime
Sampling methods
Simulated annealing
Software engineering
Software testing
System testing
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Combinatorial interaction testing (CIT) is a cost-effective sampling technique for discovering interaction faults in highly configurable systems. Recent work with greedy CIT algorithms efficiently supports constraints on the features that can coexist in a configuration. But when testing a single system configuration is expensive, greedy techniques perform worse than meta-heuristic algorithms because they produce larger samples. Unfortunately, current meta-heuristic algorithms are inefficient when constraints are present. We investigate the sources of inefficiency, focusing on simulated annealing, a well-studied meta-heuristic algorithm. From our findings we propose changes to improve performance, including a reorganized search space based on the CIT problem structure. Our empirical evaluation demonstrates that the optimizations reduce run-time by three orders of magnitude and yield smaller samples. Moreover, on real problems the new version compares favorably with greedy algorithms.
DOI:10.1109/SSBSE.2009.25