- Title
- Towards More Efficient Meta-heuristic Algorithms for Combinatorial Test Generation
- Creator
- Lin, Jinkun; Cai, Shaowei; Luo, Chuan; Lin, Qingwei; Zhang, Hongyu
- Relation
- 27th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE ’19). Proceedings of the 27th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE ’19) (Tallinn, Estonia 26-30 August, 2019) p. 212-222
- Publisher Link
- http://dx.doi.org/10.1145/3338906.3338914
- Publisher
- ACM
- Resource Type
- conference paper
- Date
- 2019
- Description
- Combinatorial interaction testing (CIT) is a popular approach to detecting faults in highly configurable software systems. The core task of CIT is to generate a small test suite called a t-way covering array (CA), where t is the covering strength. Many meta-heuristic algorithms have been proposed to solve the constrained covering array generating (CCAG) problem. A major drawback of existing algorithms is that they usually need considerable time to obtain a good-quality solution, which hinders the wider applications of such algorithms. We observe that the high time consumption of existing meta-heuristic algorithms for CCAG is mainly due to the procedure of score computation. In this work, we propose a much more efficient method for score computation. The score computation method is applied to a state-of-the-art algorithm TCA, showing significant improvements. The new score computation method opens a way to utilize algorithmic ideas relying on scores which were not affordable previously. We integrate a gradient descent search step to further improve the algorithm, leading to a new algorithm called FastCA. Experiments on a broad range of real-world benchmarks and synthetic benchmarks show that, FastCA significantly outperforms state-of-the-art algorithms for CCAG algorithms, in terms of both the size of obtained covering array and the run time.
- Subject
- combinatorial interaction testing; covering array generation; local search
- Identifier
- http://hdl.handle.net/1959.13/1445185
- Identifier
- uon:42524
- Identifier
- ISBN:9781450355728
- Language
- eng
- Reviewed
- Hits: 473
- Visitors: 473
- Downloads: 1
| Thumbnail | File | Description | Size | Format |
|---|