随着软件复杂性的增长、软件不断向其它领域的渗透及对软件可靠性要求的增加,如何保证软件的质量和可信性变得越来越困难,相应的成本也不断增加。早期的研究表明测试成本已经占软件开发总成本的50%以上,未经充分测试的软件会带来严重的经济影响。基于模型的测试是指由软件的行为模型产生测试用例,再测试实际的软件实现是否与模型一致。模型描述了软件“做什么”而不是“怎么做”,因此由模型导出测试用例时不必考虑到程序的具体实现。过去,一些基于模型的测试生成方法和测试准则已被相继提出。例如W方法、UIO方法、DS方法、状态覆盖准则、迁移覆盖准则和迁移对覆盖准则等等。然而,由于测试意图的不同,上述这些测试生成方法和测试准则并不能解决所有的问题且具有一定的局限性。例如,虽然W方法具有很强的错误探测能力,但该方法生成的测试序列包含大量的冗余,导致测试成本的急剧增加。为此,PW方法和R-PW方法被相继提出。这些方法具有与W方法相同的测试效率,同时可减少测试序列中的冗余。然而这些被提议的方法同样也有其自身的缺点,例如实现算法的效率问题。本文主要研究基于FSM模型的测试用例生成和测试用例优化。采用的建模语言为有限状态机。本文的研究成果同样适用于带标签迁移系统(LTS)、约束逻辑程序和Petri网等。基于状态机的理论,本文提出了一整套基于FSM模型的测试用例生成及测试优化的理论和技术。首先本文研究了基于模型的测试理论,包括三种主要的建模语言(约束逻辑程序、有限状态机、标签迁移系统)的理论基础。其中重点是介绍了有限状态机的原理,由有限状态机产生测试用例的前提和假设,常见基于模型的测试生成方法的理论基础,测试覆盖准则及它们适用范围,并对现有测试覆盖准则进行了一定的理论评估。另外还介绍了常用的测试优化技术等。接着本文讨论了现有的一些基于模型的测试生成算法及满足测试覆盖准则的一些经典算法,并分析了不同算法的时间效率和空间效率。针对现有的特征集合和迁移覆盖集合的算法效率过低问题,提出了两个改进算法,并采用形式方法给出了这两个算法的理论支持,最后实验对比了这两个算法与现有算法的效率。软件测试的目的是用最小的成本测试软件中的每一部分。然而,实际软件测试中,穷尽测试软件中的每一部分是不现实的。因此需要对测试成本和测试效率进行权衡。依据程序中80%的错误来源于20%的代码原理,本文提出了确定性有限状态机的最小测试成本迁移覆盖准则。由该准则产生一组测试序列集合具备完备性、无冗余或冗余较小、集合较小、测试序列总长度较短,有效的平衡了测试成本和测试效率。在针对复杂系统进行测试时,本文建议采用正则表达式来描述系统的有限状态机模型,再对正则表达式进行有效分解,获取相关的子正则表达式,最后由子正则表达式产生相关的测试用例。该方法的重点及难点是如何获取正则表达式的有效分解,使得测试用例来源于被分解的正则表达式与来源于原表达式的测试用例具有相同的错误探测能力。这种测试生成方法与最小测试成本迁移覆盖相互补充,弥补了最小测试成本迁移覆盖对FSM模型中循环部分测试不足的问题。为解决测试序列集合中的冗余问题,本文也提出了解决方案。一类是针对由某个测试覆盖准则产生测试用例时存在冗余问题的解决。本文将一个测试序列看成一个字符串,利用字符串匹配的方式约简冗余的字符,同时增加满足该覆盖准则的必要约束条件,保留满足约束条件的冗余,删除不满足约束条件的冗余。随后设计了一组转换规则,将约简后的无效测试片段转换成有效的测试序列。为设计有效测试用例,本文建议首先采用逻辑运算进行约简,再采用了逻辑覆盖准则设计测试用例。随后本文讨论了现有的逻辑覆盖准则,分析了逻辑覆盖准则与测试用例生成之间的关系,并提出了一种新的逻辑覆盖准则(TTJ准则)。最后本文开发了一个基于FSM模型的测试生成工具。该工具整合了上述所有的测试生成及测试优化算法。利用该工具,能建立软件系统的可视化FSM模型,并能由该模型产生有效的测试用例。