Intelligent test case generation based on branch and bound

doi:10.1016/S1005-8885(14)60291-0

Acta Metallurgica Sinica(English letters) ›› 2014, Vol. 21 ›› Issue (2): 91-97.doi: 10.1016/S1005-8885(14)60291-0

Intelligent test case generation based on branch and bound

邢颖,宫云战,王雅文,张旭舟

北京邮电大学

收稿日期:2013-09-26 修回日期:2013-12-31 出版日期:2014-04-30 发布日期:2014-04-30
通讯作者: 邢颖 E-mail:lovelyjamie@yeah.net
基金资助:
基于群体智能的多Agent协作模型与适应性行为研究;国家“八六三”高技术研究发展计划

Intelligent test case generation based on branch and bound

1. State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China 2. School of Electronic and Information Engineering, Liaoning Technical University, Huludao 125105, China 3. State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China

Received:2013-09-26 Revised:2013-12-31 Online:2014-04-30 Published:2014-04-30
Contact: Ying Xing E-mail:lovelyjamie@yeah.net

摘要/Abstract

摘要：

Path-oriented test case generation is in essence a constraint satisfaction problem (CSP) solved by search strategies, among which backtracking algorithms are widely used. In this article, the backtracking algorithm branch and bound (BB) is introduced to generate path-oriented test cases automatically. A model based on state space search is proposed to construct the search tree dynamically. The BB is optimized from two perspectives. Variable permutation with a heuristic rule to break ties is adopted for the branching operation, and interval computation with analysis on the monotony of branching conditions is utilized for the bounding operation. Empirical experiments show that the proposed method performs well with linear complexity, and reaches 100% coverage on some benchmark programs with an advantage over some static and dynamic algorithms.

关键词:

test case generation, constraint satisfaction problem, branch and bound, state space search

Abstract:

Key words:

test case generation, constraint satisfaction problem, branch and bound, state space search

参考文献

1. Shan J H, Wang J, Qi Z C. Survey on path-oriented automatic generation of test case. Acta Electronica Sinica, 2004, 32(1): 109-113 (in Chinese)

2. King J C. Symbolic execution and program testing. Communications of the ACM, 1976, 19(7): 385-394

3. Wang Y W, Gong Y Z, Xiao Q, et al. Variable range analysis on interval computation. Journal of Beijing University of Posts and Telecommunications, 2009, 32(3): 36-41 (in Chinese)

4. Sharma C, Sabharwal S, Sibal R. A survey on software testing techniques using genetic algorithm. International Journal of Computer Science Issues, 2013, 10(1): 381-393

5. Mao C Y, Yu X X, Chen J F. Generating test data for structural testing based on ant colony optimization. Proceedings of the 12th International Conference on Quality Software (QSIC’12), Aug 27-29, 2012, Xi'an, China. Piscataway, NJ, USA: IEEE, 2012: 98-101

6. Tracey N, Clark J, Mander K. Automated program flaw finding using simulated annealing. ACM SIGSOFT Software Engineering Notes, 1998, 23(2): 73-81

7. Eiben A E, Ruttkay Z. Constraint-satisfaction problems. New York, NY, USA: IOP Publishing Ltd , 1997

8. Lisgara E G, Karolidis G I, Androulakis G S. Advancing the backtrack optimization technique to obtain forecasts of potential crisis periods. Applied Mathematics, 2012, 3(10A):1538-1551

9. Szer D, Charpillet F, Zilberstein S. MAA*: a heuristic search algorithm for solving decentralized POMDPs. Proceedings of the 21st Conference on Uncertainty in Arti?cial Intelligence (UAI’05), Jul 26-29, 2005, Edinburgh, UK. Arlington, VA, USA: AUAI, 2005: 576-583

10. Gao L B, Mishra S K, Shi J M. An extension of branch-and-bound algorithm for solving sum-of-nonlinear-ratios problem. Optimization Letters, 2012, 6(2): 221-230

11. Frost D, Dechter R. Look-ahead value ordering for constraint satisfaction problems. Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI’95): Vol 1, Aug 20-25, 1995, San Francisco, CA, USA: Morgan Kaufmann, 1995: 572-578

12. Chen X G, Van Beek P. Conflict-directed backjumping revisited. Journal of Artificial Intelligence Research, 2001, 14: 53-81

13. Gallagher M J, Narasimhan V L. Adtest: a test data generation suite for ADA software systems. IEEE Transactions on Software Engineering, 1997, 23(8): 473-484

14. Zhao R L, Harman M, Li Z. Empirical study on the efficiency of search based test generation for EFSM models. Proceedings of the 3rd International Conference on Software Testing, Verification, and Validation Workshops (ICSTW’10), Apr 7-9, 2010, Paris, France. Piscataway, NJ, USA: IEEE, 2010: 222-231

15. Wang Y W, Gong Y Z, Xiao Q, et al. A method of variable range analysis based on abstract interpretation and its applications. Acta Electronica Sinica, 2011, 39(2): 293-303 (in Chinese)

16. Gupta N, Mathur A P, Soffa M L. Automated test data generation using an iterative relaxation method. ACM SIGSOFT Software Engineering Notes. 1998, 23(6): 231-244

17. Wang Y W, Gong Y Z, Xiao Q. A Method of test case generation based on necessary interval set. Journal of Computer-aided Design & Computer Graphics, 2013, 25(4): 550-556 (in Chinese)

18. Bouchachia A. An immune genetic algorithm for software test data generation. Proceedings of the 7th International Conference on Hybrid Intelligent Systems (HIS’07), Sep 17-19, 2007, Kaiserslautern, Germany. Washington, DC, USA: IEEE Computer Society, 2007: 84-89

19. Alba E, Chicano F. Observations in using parallel and sequential evolutionary algorithms for automatic software testing. Computers & Operators Research, 2008, 35(10): 3161-3183

20. Ammann P, Offutt J. Introduction to software testing. New York, NY, USA: Cambridge University Press, 2008:132

Intelligent test case generation based on branch and bound

Intelligent test case generation based on branch and bound

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价