北京航空航天大学学报 ›› 2019, Vol. 45 ›› Issue (5): 919-929.doi: 10.13700/j.bh.1001-5965.2018.0531

• 论文 • 上一篇    下一篇

基于无关变量分离的EFSM测试数据进化生成

潘雄, 郝帅, 苑政国, 宋凝芳   

  1. 北京航空航天大学 仪器科学与光电工程学院, 北京 100083
  • 收稿日期:2018-09-07 出版日期:2019-05-20 发布日期:2019-05-21
  • 通讯作者: 潘雄.E-mail:08768@buaa.edu.cn E-mail:08768@buaa.edu.cn
  • 作者简介:潘雄 男,博士,高级工程师,硕士生导师。主要研究方向:软件可靠性、数字系统可靠性;郝帅 男,硕士研究生。主要研究方向:软件测试、软件可靠性;苑政国 男,博士研究生。主要研究方向:形式验证、软件可靠性;宋凝芳 女,博士,研究员。主要研究方向:惯性技术、空间光电信息系统。

Evolutionary generation of test data for EFSM based on irrelevant variable separation

PAN Xiong, HAO Shuai, YUAN Zhengguo, SONG Ningfang   

  1. School of Instrumentation and Optoelectronic Engineering, Beihang University, Beijing 100083, China
  • Received:2018-09-07 Online:2019-05-20 Published:2019-05-21

摘要: 扩展有限状态机(EFSM)相比于有限状态机(FSM)能够更加精确地刻画系统的动态行为,因而广泛作为各种控制流与数据流系统的测试模型。在EFSM模型的测试中,使用搜索的方法获得触发目标测试路径的测试数据是近年来的一个研究热点。为进一步提高搜索效率,在遗传算法(GA)的基础上提出一种自动分离测试路径中无关输入变量的方法,该方法通过分析模型中变量与迁移间的关系,判定不影响子路径中谓词条件的无关输入变量,进而从个体中将其分离以实现搜索空间的自动缩减,提升测试数据生成效率。对几种具有不同复杂度的基准EFSM模型进行实验后的结果表明,该方法生成有效测试数据的成功率均达到98.2%以上,且与未分离输入变量的遗传算法相比,所需平均迭代次数减少44.7%~85.9%,平均运行时间减少24.1%~85.5%。

关键词: 软件测试, 扩展有限状态机(EFSM), 测试数据生成, 遗传算法(GA), 空间缩减, 无关变量分离

Abstract: Extended finite state machine (EFSM), a more accurate test model than finite state machine (FSM), has been widely used to describe dynamic behavior of system, and thus has been taken as the test model of various control flow and data flow systems. For EFSM model test, using search method to obtain test data to trigger a given test path has become a research hotspot in recent years. In order to improve the search efficiency, this paper proposed a method that originates from genetic algorithm (GA) and can automatically separate irrelevant input variables in a test path. By analyzing the relationship between variables and state transitions in EFSM and separating irrelevant input variables from the individual that does not affect the transition's guard in the sub-test path, the new method reduced the search space and enhanced the efficiency of test data generation. The experimental results on various complex benchmark EFSM models show that the success rate of the new method to generate effective test data is larger than 98.2%. Compared to the traditional genetic algorithm, the average number of iterations of the new method is reduced by 44.7%-85.9% and the average running time is reduced by 24.1%-85.5%.

Key words: software testing, extended finite state machine (EFSM), test data generation, genetic algorithm (GA), space reduction, irrelevant variable separation

中图分类号: 


版权所有 © 《北京航空航天大学学报》编辑部
通讯地址:北京市海淀区学院路37号 北京航空航天大学学报编辑部 邮编:100191 E-mail:jbuaa@buaa.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发