期刊文献+

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

The Algorithm to Solve Equation Constraints in Automatic Test Data Generation
下载PDF
导出
摘要 为了解决测试用例自动生成中等式约束的求解问题,提出一种加入等式处理策略的分支限界搜索算法.首先将线性代数中判定线性方程组是否有解的方法引入分支限界测试用例生成框架之中;然后在已有算法模型的基础上提出集成等式处理分支限界搜索算法,以支持多种变量类型的等式处理;最后将等式约束分为等式无解、等式多解和等式唯一解三大类进行处理,包含了等式约束求解问题的所有情况.实验结果表明,文中算法可以实现对一部分不可达路径的检测,在很大程度上减少测试用例生成的时间并提高覆盖率;对大工程的测试以及同开源约束求解工具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.
作者 张博 邢颖 宫云战 贾薇 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)
出处 《计算机辅助设计与图形学学报》 EI CSCD 北大核心 2017年第9期1740-1749,共10页 Journal of Computer-Aided Design & Computer Graphics
基金 国家"八六三"高技术研究发展计划(2012AA011201) 国家自然科学基金(91318301)
关键词 约束满足问题 线性代数 不可达路径 分支限界 constraint satisfaction problem linear algebra infeasible path branch and bound
  • 相关文献

参考文献2

二级参考文献29

  • 1Ball T,Rajamani S K.The SLAM project:debugging system software via static analysis[C]//Proceedings of the 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages.New York:ACM Press,2002:1-3.
  • 2Bush W R,Pincus J D,Sielaff D J.A static analyzer for finding dynamic programming errors[J].Software:Practice & Experience,2000,30(7):775-802.
  • 3Chelf B,Engler D,Hallem S.How to write system-specific,static checkers in metal[C]//Proceedings of the 4th ACM SIGPLAN SIGSOFT Workshop on Program Analysis for Software Tools and Engineering.New York:ACM Press,2002:51-60.
  • 4Hallem S,Chelf B,Xie Y C,et al.A system and language for building system-specific,static analyses[C]//Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation.New York:ACM Press,2002:69-82.
  • 5Emanuelsson P,Nilsson U.A comparative study of industrial static analysis tools[M]//Lecture Notes in Computer Science.Heidelberg:Springer,2008,217:5-21.
  • 6Banning J P.An efficient way to find the side effects of procedure calls and the aliases of variables[C]//Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages.New York:ACM Press,1979:29-41.
  • 7Cooper K D,Kennedy K.Interprocedural side-effect analysis in linear time[J].ACM SIGPLAN Notices,2004,39(4):219-228.
  • 8Cooper K D,Kennedy K.Efficient computation of flow-insensitive interprocedural summary information-a correction[J].ACM SIGPLAN Notices,1988,23(4):35-42.
  • 9Mohd-Saman M Y,Evans D J.Inter-procedural analysis for parallel computing[J].Parallel Computing,1995,21(2):315-338.
  • 10Emami M,Ghiya R,Hendren L J.Context-sensitive interprocedural points-to analysis in the presence of function pointers[C]//Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation.New York:ACM Press,1994:242-256.

共引文献3

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部