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

The Algorithm to Solve Equation Constraints in Automatic Test Data Generation

作　　者：张博 邢颖[2] 宫云战[1] 贾薇 Zhang Bo;Xing Ying;Gong Yunzhan;Jia Wei(State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876;Automation School, Beijing University of Posts and Telecommunications, Beijing 100876)

机构地区：[1]北京邮电大学网络与交换技术国家重点实验室,北京100876 [2]北京邮电大学自动化学院,北京100876

出　　处：《计算机辅助设计与图形学学报》2017年第9期1740-1749,共10页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家"八六三"高技术研究发展计划(2012AA011201);国家自然科学基金(91318301)

摘　　要：为了解决测试用例自动生成中等式约束的求解问题,提出一种加入等式处理策略的分支限界搜索算法.首先将线性代数中判定线性方程组是否有解的方法引入分支限界测试用例生成框架之中;然后在已有算法模型的基础上提出集成等式处理分支限界搜索算法,以支持多种变量类型的等式处理;最后将等式约束分为等式无解、等式多解和等式唯一解三大类进行处理,包含了等式约束求解问题的所有情况.实验结果表明,文中算法可以实现对一部分不可达路径的检测,在很大程度上减少测试用例生成的时间并提高覆盖率;对大工程的测试以及同开源约束求解工具Choco的对比实验,也证明了该算法可以提升测试效率.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.

关 键 词：约束满足问题 线性代数 不可达路径 分支限界 

分 类 号：TP311.5[自动化与计算机技术—计算机软件与理论]