投审稿平台


投稿指南
下载专区
地  址:北京市海淀区中关村科学院
南路6号中国科学院计算所342号 [地图]
《计算机辅助设计与图形学学报》编辑部
邮政编码:100190
电  话:010-62562491
          010-62600342
订阅信息
ISSN      1003-9775
CN        11-2925/TP
邮发代号:82-456
单    价:80.00元
全年订价:960.00元
在线期刊

测试用例自动生成中等式约束处理算法

张 博1), 邢 颖2), 宫云战1), 贾 薇1)
1) (北京邮电大学网络与交换技术国家重点实验室 北京 100876)2) (北京邮电大学自动化学院 北京 100876)
分类号: TP311.5
出版年,卷(期):页码: 2017 , 29 ( 9 ): 1740-1749 张博new
摘要: 为了解决测试用例自动生成中等式约束的求解问题, 提出一种加入等式处理策略的分支限界搜索算法. 首先将线性代数中判定线性方程组是否有解的方法引入分支限界测试用例生成框架之中; 然后在已有算法模型的基础上提出集成等式处理分支限界搜索算法, 以支持多种变量类型的等式处理; 最后将等式约束分为等式无解、等式多解和等式唯一解三大类进行处理, 包含了等式约束求解问题的所有情况. 实验结果表明, 文中算法可以实现对一部分不可达路径的检测, 在很大程度上减少测试用例生成的时间并提高覆盖率; 对大工程的测试以及同开源约束求解工具Choco的对比实验, 也证明了该算法可以提升测试效率.
关键词: 约束满足问题; 线性代数; 不可达路径; 分支限界
The Algorithm to Solve Equation Constraints in Automatic Test Data Generation
Zhang Bo1), Xing Ying2), Gong Yunzhan1), and Jia Wei1)
1) (State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876) 2) (Automation School, Beijing University of Posts and Telecommunications, Beijing 100876)
abstract: This paper proposes the branch and bound algorithm that integrates the method of equation dealing to solve equation constraints in automatic test data generation. Firstly, the method in linear algebra that judges whether a linear equation set is solvable is introduced to the branch and bound test data generation framework. Secondly, branch and bound algorithm that integrates the method of equation dealing is proposed to support various types of variables. Finally, equality constraints are divided into three categories: unsolvable, multiple solutions and single solution that included all conditions. Experimental results show that, the proposed algorithm can not only detect a part of the infeasible path, but also reduce the time consumption of test case generation as well as increase coverage. The testing on large projects and the comparison experiment with the open source constraint solver Choco show that the algorithm can improve the testing efficiency.
keyword: constraint satisfaction problem; linear algebra; infeasible path; branch and bound
 
Copyright © 2004《计算机辅助设计与图形学学报》版权所有
电话:010-62600342 传真:010-62562491
E_mail:jcad@ict.ac.cn