中国邮电高校学报(英文)

中国邮电高校学报(英文) ›› 2014, Vol. 21 ›› Issue (2): 91-97.doi: 10.1016/S1005-8885(14)60291-0

• Others • 上一篇    下一篇

Intelligent test case generation based on branch and bound

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

  1. 北京邮电大学
  • 收稿日期: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. 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

摘要：

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:

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.

Key words:

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

版权所有 © 2020 中国邮电高校学报(英文)编辑部　
　 地址：北京邮电大学图书馆1层119 室　邮政编码：100081
Tel：86-010-62282493　Fax： 86-010-62283461　E-mail: jchupt@bupt.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn