沈 晴，牟永敏

北京信息科技大学 计算机学院，北京 100101

1 引言

软件测试可以提高软件的可靠性[1]。在软件开发周期，软件测试是软件开发过程中不可或缺的环节，如果利用人工的方法实现测试需求，会耗费大量人力物力，所需成本占比高达50%以上，因此研究人员致力于实现自动化测试，降低软件测试成本。随着软件规模日趋大型化和复杂化，及时发现并修复软件中存在的错误可以很大程度上避免软件使用过程中发生故障带来的损失，但同时也给软件测试带来进一步的挑战，自动化测试的重要性日益凸显。其中，测试用例对保证软件测试的充分性和可靠性有着重要影响，一组合理的测试用例可以帮助测试人员找出程序中的错误。人工设计测试用例需要测试人员具备丰富的经验，且不可避免地受到人为因素影响，可能无法保证测试的充分性，因此，测试用例自动生成技术对提高软件测试的效率有着重要意义。根据测试方法的不同，可以分为四大类型：随机测试方法、基于搜索的测试方法、模型检测测试方法以及符号执行测试方法[2]。

1983年Bird等人[3]提出随机法，易于实现且十分高效，一些研究会将它作为基准方法之一[4]，但对于较为复杂的程序，随机法很难达到较高的覆盖率。为保证测试用例均匀地分布在搜索空间，提出自适应随机测试方法[5]，但覆盖率低的问题依然存在。基于搜索的测试用例自动生成方法[6]将测试用例自动生成问题转化为函数优化问题，并利用遗传算法[7]、粒子群优化算法[8]、蚁群算法[9]以及一些优化后的进化算法[10]等来寻找最优解。……