automatic verification of optimization algorithms: a case study of a quadratic assignment problem solver

ISCAS OpenIR

	automatic verification of optimization algorithms: a case study of a quadratic assignment problem solver
	Merkel Robert; Wang Daoming; Lin Huimin; Chen Tsong Yueh
	2011
发表期刊	International Journal of Software Engineering and Knowledge Engineering
ISSN	0218-1940
卷号	21 期号:2 页码:289-307
摘要	Metamorphic testing is a technique for the verification of software output without a complete testing oracle. Mathematical optimization, implemented in software, is a problem for which verification can often be challenging. In this paper, we apply metamorphic testing to one such optimization problem, the quadratic assignment problem (QAP). From simple observations of the properties of the QAP, we describe how to derive a number of metamorphic relations useful for verifying the correctness of a QAP solver. We then compare the effectiveness of these metamorphic relations, in "killing" mutant versions of an exact QAP solver, to a simulated oracle. We show that metamorphic testing can be as effective as the simulated oracle for killing mutants. We examine the relative effectiveness of different metamorphic relations, both singly and in combination, and conclude that combining metamorphic relations can be significantly more effective than using a single relation. © 2011 World Scientific Publishing Company.; Metamorphic testing is a technique for the verification of software output without a complete testing oracle. Mathematical optimization, implemented in software, is a problem for which verification can often be challenging. In this paper, we apply metamorphic testing to one such optimization problem, the quadratic assignment problem (QAP). From simple observations of the properties of the QAP, we describe how to derive a number of metamorphic relations useful for verifying the correctness of a QAP solver. We then compare the effectiveness of these metamorphic relations, in "killing" mutant versions of an exact QAP solver, to a simulated oracle. We show that metamorphic testing can be as effective as the simulated oracle for killing mutants. We examine the relative effectiveness of different metamorphic relations, both singly and in combination, and conclude that combining metamorphic relations can be significantly more effective than using a single relation. © 2011 World Scientific Publishing Company.
收录类别	EI ; SCI
关键词	Computer Software Selection And Evaluation Optimization Verification
部门归属	(1) Faculty of Information Technology Monash University Clayton VIC 3800 Australia; (2) Institute of Software Chinese Academy of Sciences 4 South Fourth Street Zhong Guan Cun Beijing 10090 China; (3) Centre for Software Analysis and Testing Swinburne University of Technology John Street Hawthorn 3122 Australia
学科领域	Computer Science ; Engineering
资助者	National Natural Science Foundation of China60721061; Australian Research Council (ARC)LX0776490
语种	英语
WOS记录号	WOS:000293093800007
引用统计	被引频次：4[WOS] [WOS记录] [WOS相关记录]
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/16011
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Merkel Robert,Wang Daoming,Lin Huimin,et al. automatic verification of optimization algorithms: a case study of a quadratic assignment problem solver[J]. International Journal of Software Engineering and Knowledge Engineering,2011,21(2):289-307.
APA	Merkel Robert,Wang Daoming,Lin Huimin,&Chen Tsong Yueh.(2011).automatic verification of optimization algorithms: a case study of a quadratic assignment problem solver.International Journal of Software Engineering and Knowledge Engineering,21(2),289-307.
MLA	Merkel Robert,et al."automatic verification of optimization algorithms: a case study of a quadratic assignment problem solver".International Journal of Software Engineering and Knowledge Engineering 21.2(2011):289-307.