EFSM模型字符串测试数据自动生成研究

作     者：刘宜桦 

作者单位：北京化工大学 

学位级别：硕士

导师姓名：尤枫

授予年度：2014年

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：扩展有限状态机 符号执行 遗传算法 测试数据生成 字符串 字符串距离 

摘      要：随着软件应用领域的不断扩展和软件规模的不断扩大,如果软件质量得不到保证,就可能会造成巨大的人身和财产损失。软件测试是保证软件可靠性和安全性的重要技术手段,而测试数据自动生成方法是重要的测试技术之一。但是现有的测试生成大多数只考虑整数类型和布尔类型,很少考虑字符串类型。 字符串测试数据自动生成是软件测试目前的研究难点,目前尚没有很好的解决方法。本文提出了一种将符号执行约束求解与遗传算法相结合实现基于EFSM模型的字符串测试数据自动生成方法。首先将测试数据候选字符集中的字符通过取余编码转换为整数,然后将目标路径上字符串约束转换成整数约束,通过约束求解获得中间解,最后采用遗传算法生成字符串测试数据。在遗传算法中适应度函数的选择是针对字符串变量的,主要与字符串距离相关。但是现有的字符串距离的比较方法如海明距离、编辑距离和字符距离都存在不足。本文通过分析这三种方法的不足,提出了一种新的字符串距离比较方法,这种方法能很好的克服现有方法的不足。 实验结果表明,本文提出的字符串测试数据自动生成方法,相比单纯的遗传算法和模拟退火算法在生成字符串测试数据的效率上提高了很多,并且随着字符串长度的增加,运行时间呈指数的减少。对于本文提出的新的字符串距离比较计算方法,相比编辑距离和字符距离,减少了字符串测试数据生成时间。