Generating combinatorial test suite using combinatorial optimization

ISCAS OpenIR

	Generating combinatorial test suite using combinatorial optimization
	Zhang, Zhiqiang (1); Yan, Jun (3); Zhao, Yong (5); Zhang, Jian (1); Zhang, Zhiqiang
	2014
发表期刊	Journal of Systems and Software
ISSN	1641212
卷号	98 页码:191-207
摘要	Combinatorial testing (CT) is an effective technique to test software with multiple configurable parameters. It is used to detect interaction faults caused by the combination effect of parameters. CT test generation aims at generating covering arrays that cover all t-way parameter combinations, where t is a given covering strength. In practical CT usage scenarios, there are usually constraints between parameters, and the performance of existing constraint-handling methods degrades fast when the number of constraints increases. The contributions of this paper are (1) we propose a new one-test-at-a-time algorithm for CT test generation, which uses pseudo-Boolean optimization to generate each new test case; (2) we have found that pursuing the maximum coverage for each test case is uneconomic, and a possible balance point is to keep the approximation ratio in [0.8,0.9]; (3) we propose a new self-adaptive mechanism to stop the optimization process at a proper time when generating each test case; (4) extensive experimental results show that our algorithm works fine on existing benchmarks, and the constraint-handling ability is better than existing approaches when the number of constraints is large; and (5) we propose a method to translate shielding parameters (a common type of constraints) into normal constraints.; Combinatorial testing (CT) is an effective technique to test software with multiple configurable parameters. It is used to detect interaction faults caused by the combination effect of parameters. CT test generation aims at generating covering arrays that cover all t-way parameter combinations, where t is a given covering strength. In practical CT usage scenarios, there are usually constraints between parameters, and the performance of existing constraint-handling methods degrades fast when the number of constraints increases. The contributions of this paper are (1) we propose a new one-test-at-a-time algorithm for CT test generation, which uses pseudo-Boolean optimization to generate each new test case; (2) we have found that pursuing the maximum coverage for each test case is uneconomic, and a possible balance point is to keep the approximation ratio in [0.8,0.9]; (3) we propose a new self-adaptive mechanism to stop the optimization process at a proper time when generating each test case; (4) extensive experimental results show that our algorithm works fine on existing benchmarks, and the constraint-handling ability is better than existing approaches when the number of constraints is large; and (5) we propose a method to translate shielding parameters (a common type of constraints) into normal constraints.
收录类别	SCI ; EI
关键词	Combinatorial Testing Test Generation Combinatorial Optimization
部门归属	(1) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, China; (2) University of Chinese Academy of Sciences, China; (3) Technology Center of Software Engineering, Institute of Software, Chinese Academy of Sciences, China; (4) State Key Laboratory of Rail Traffic Control and Safety, Beijing Jiaotong University, China; (5) Department of Computer Science, College of Engineering and Applied Science, University of Colorado at Colorado Springs, United States
语种	英语
WOS记录号	WOS:000344421900012
引用统计
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/16791
专题	中国科学院软件研究所
通讯作者	Zhang, Zhiqiang
推荐引用方式 GB/T 7714	Zhang, Zhiqiang ,Yan, Jun ,Zhao, Yong ,et al. Generating combinatorial test suite using combinatorial optimization[J]. Journal of Systems and Software,2014,98:191-207.
APA	Zhang, Zhiqiang ,Yan, Jun ,Zhao, Yong ,Zhang, Jian ,&Zhang, Zhiqiang.(2014).Generating combinatorial test suite using combinatorial optimization.Journal of Systems and Software,98,191-207.
MLA	Zhang, Zhiqiang ,et al."Generating combinatorial test suite using combinatorial optimization".Journal of Systems and Software 98(2014):191-207.