信息化技术的快速发展使得软件系统的规模越来越大、更新换代的速度越来越快,开发过程中引入错误的可能性也越来越大。为了尽可能地减少在软件产品中的错误,研究者和开发者们提出了许多软件质量保障手段,然而到目前为止,软件测试仍然是保证软件质量和可靠性的最重要也是最有效的方法,对于保证和提高软件产品的质量起着不可替代的重要作用,并逐渐受到人们越来越多的重视。软件测试是一项耗时且开销巨大的工作,使用自动化测试方法可以提高测试效率、减少测试代价。自动化测试已经成为当前软件测试发展的趋势,而其中一个关键就是自动化测试用例生成。自动化生成测试用例的一种常用方法是创建软件的测试模型,并在模型的基础上自动化生成测试用例。扩展有限状态机(EFSM)模型以表达能力强、易于理解的特性使得在当前的测试研究领域受到了更多的关注。在扩展有限状态机模型中,测试数据的生成还存在许多挑战,并且通常和路径的可行性紧密相关,目前已经存在一些关于这方面的研究,但总体来说基于EFSM模型的测试数据生成技术仍然很不成熟。此外,目前的研究中较少考虑最终的测试用例集优化问题,对于测试预言(Test Oracle)自动化生成的研究也还相对较少。针对上述问题,本文提出一种基于EFSM模型的自动化测试用例生成方法(ATGEM)。为了解决不可行路径问题,我们提出了一种路径可行性度量方法来预测路径的可行性概率,使得在测试数据生成过程中尽可能避开不可行路径,提高生成的效率。为了生成能够触发可行路径的测试数据及相关的预言信息,我们通过开发可执行模型来获取运行时反馈信息,在此基础上提出了一种新的适应度函数(Fitness Function),并利用分散搜索(Scatter Search, SS)算法在排序后的候选路径集中挑选可行路径并自动生成相应的测试用例。可执行模型定义了模型的动态行为,并通过使用语义执行使得静态模型具有类似动态程序的执行能力。利用可执行模型可以获得运行时反馈信息计算适应度函数,就可以忽略不同数据类型带来的差异性问题,使得该适应度函数能够使用在多种数据类型中,因此适用范围较广。可执行模型带来的另一个优点是可以在模型动态执行过程中自动化的生成预言信息。以往的研究表明,数量较少但较长的测试用例优于数量较多但较短的测试用例,更容易发现系统中的错误。因此,在ATGEM方法还利用以上几个子方法迭代来寻找一个具有较长路径和较小路径数量的较优可行路径集合。在提出以上的路径可行性度量方法时,虽然已经考虑了路径长度和可行性评估值的平衡问题,但仍然不够精确。由于路径的长度和可行性相互矛盾,找到较优可行路径集问题可以转化为一个优化平衡的问题。因此我们提出了一种基于多目标优化(Multi-objective Optimization)的新方法ATGEMmot,并提出了两个对应的适应度函数来获取Pareto前沿解集。为了验证提出的ATGEM和ATGEMmop方法,我们设计了一系列的实验,将提出的两种方法应用于多个EFSM模型,用来检验两种方法中测试用例生成、路径可行性度量方法和路径集多目标优化方法的有效性及效率,并实际检验模型中的不可行路径的数量,分析原因。实验结果表明ATGEM方法在路径可行性度量、生成较优可行路径子集、生成测试数据和预言信息达到指定覆盖方面是行之有效的。在测试数据生成方面,与现有方法相比,ATGEM方法在总体上具有更好的效率。ATGEMmop方法与ATGEM方法相比,除了时间效率上略有下降,其它指标上都占有优势,在生成具有较少数量、较长路径的较优测试用例集方面具有更好的表现。