A HYBRID BACKTRACKING ALGORITHM FOR AUTOMATIC TEST DATA GENERATION

作者：Xing, Ying^*; Gong, Yunzhan; Zhou, Xiaoguang; Wang, Ludi; Yang, Mengke; Zhang, Chi; Dong, Yukun

来源：Tehnicki Vjesnik, 2017, 24(3): 761-768.

DOI：10.17559/TV-20170324111348

• automatic test data generation
• backtracking
• closure
• conflict-directed backjumping
• forward checking

As a fundamental issue in software testing, automatic test data generation is of crucial importance, which is essentially a constraint satisfaction problem and solved by search algorithms. In our previous research, branch and bound was proposed as our constraint solver and the look-ahead methods were elaborated. Based on interval arithmetic and symbolic execution, this paper focuses on the look-back or backtracking method, which is the hybridization of forward checking and conflict-directed backjumping, with the aim of improving the efficiency of backtracking in the search procedure. The closures of variables are used to facilitate the localization of the conflicts which cause dead ends. Empirical experiments prove the effectiveness of the proposed hybrid backtracking method and its applicability in engineering.

• 出版日期2017-6
• 单位北京邮电大学; 网络与交换技术国家重点实验室; 中国石油大学（北京）