WCA: A weighting local search for constrained combinatorial test optimization

作     者：Fu, Yingjie Lei, Zhendong Cai, Shaowei Lin, Jinkun Wang, Haoran 

作者机构：Chinese Acad Sci Inst Software State Key Lab Comp Sci Beijing Peoples R China Univ Chinese Acad Sci Sch Comp & Control Engn Beijing Peoples R China 

出 版 物：《INFORMATION AND SOFTWARE TECHNOLOGY》 (信息与软件技术)

年 卷 期：2020年第122卷

页      面：106288-000页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Microsoft Research Asia [FY20-Research-Sponsorship-255] Youth Innovation Promotion Association, Chinese Academy of Sciences Beijing Academy of Artificial Intelligence (BAAI) 

主　　题：Combinatorial interaction testing Covering array generation Local search Weighting mechanism Search-based software testing 

摘      要：Context: Covering array generation (CAG) is the core task of Combinatorial interaction testing (CIT), which is widely used to discover interaction faults in real-world systems. Considering the universality, constrained covering array generation (CCAG) is more in line with the characteristics of applications, and has attracted a lot of researches in the past few years. Objective: In CIT, a covering array (CA) with smaller size means lower cost of testing, particularly for the systems where the execution of a test suite is time consuming. As constraints between parameters are ubiquitous in real systems, this work is dedicated to more efficient algorithms for CCAG. Specifically, we aim to develop a heuristic search algorithm for CCAG, which allows generating CAs with smaller size in a limited time when compared with existing algorithms. Method: We propose a weighting local search algorithm named WCA, which makes use of weights associated with the tuples and dynamically adjusts them during the search, helping the algorithm to avoid search stagnation. As far as we know, this is the first weighting local search for solving CCAG. Results: We apply WCA to a wide range of benchmarks, including real-world ones and synthetic ones. The results show that WCA achieves a significant improvement over three state-of-the-art competitors in 2-way and 3-way CCAG, in terms of both effectiveness and efficiency. The importance of weighting is also reflected by the experimental comparison between WCA and its alternative algorithm without the weighting mechanism. Conclusion: WCA is an effective heuristic algorithm for CCAG to obtain smaller CAs efficiently, and the weighting mechanism plays a crucial role.