3. 马尔可夫链 是一种以统计理论为基础的统计模型，可以描述软件的使用 在软件统计测试中得到了广泛应用。马尔可夫链实际上是一种迁移具有概率特征的有限状态机，不仅可以根据状态间迁移概率自动产生测试例，还可以分析测试结果对软件性能指标和可靠性指标等进行度量[5,6]。另外，马尔可夫链模型适用于对多种软件进行统计测试，并可以通过仿真得到状态和迁移覆盖的平均期望时间，有利于在开发早期对大规模软件系统进行测试时间和费用的规划。马尔可夫链是统计测试的基本模型，在净室软件工程中得到了深入研究，在微软、Raytheon及美国联邦航空署(FAA）都得到了成功应用[7]。马尔可夫链可以用随机迁移矩阵或者带迁移概率的状态迁移图表示。基于马尔可夫链的测试充分性准则一般要求测试过程中对马尔可夫链迁移的覆盖与实际使用相同[6]。
4. 文法模型 可以描述程序的语法。由于不同的文法等价于不同的状态机 因此也可以视为状态机模型的变体。有关基于文法的测试可见文[8]，这方面研究工作相对较少。
2.3建模标准
随着系统的增长，建模是捕获和再利用有关系统知识的一个非常经济的手段。对于一个测试团队来说，这些信息是非常宝贵的：一个测试工程师了解被测系统的行为需要占据的工作量，一旦这个信息被理解，该如何保存给下一个工程师、下一个版本或者更改要求呢？如果你处于测试的设计阶段，那么你是幸运的。但是更常见的是，这些信息被埋藏在一个测试脚本中，一旦改变或者丢失就只能等待重新发现。
测试团队通过给系统构建一个给予指定输入得到所需行为的模型，可以获得有重用的最大优势就是这些工作都不会丢失。一旦这个测试周期停止，下一周期就可以迅速开始。如果该产品具有新的功能，它们可以逐步加入到模型中；如果产品的质量需要提高，那么模型需要改善和扩大测试；如果有新的人员加入到测试团队中，他们可以通过回顾模型迅速投入进来。
一旦你决定想要为被测系统建模，下一步建模的时候要思考这个系统管理的数据、执行的操作和与它通信的子系统。下面给出几条原则：
1．抽象原则，通常不把输入、输出纳入到模型中。 2．模型与被测系统不必完全一致。
4
3
基于模型的测试的基本过程及支持工具
3.1基于模型的测试的基本过程
基于模型的测试的基本过程共有6个步骤，如图2.1所示，其步骤如下： 1．分析被测系统
首先分析被测软件的系统特性，主要分析的是开发方式，主要有所采用的开发技术(面向对象、面向过程)，开发语言，开发系统环境等。然后根据分析结果，结合各个模型的特性选择合适的模型作为测试用例生成的模型。
2．建立抽象模型
根据所选择的模型对被测软件进行建模，可以进一步分析该模型是否适合软件。模型选择和建立模型可能是个反复的过程，只有在充分了解该软件系统的特点和各个模型的特点才可能为软件系统建立最恰当的模型。这个模型是一个抽象模型，因为它应该比待测软件系统（通常被称为System Under Test，简称SUT）本身更小，更简单，它只关注关键环节。建立完成后，需要检查该模型与所期望的行为是否一致。
3．生成抽象测试
从模型生成抽象测试，必须选择一些测试选择标准，因为通常有无限多的可能的测试。比如使用有限状态机FSM模型时，根据一定的覆盖准则遍历状态间的迁移所获得的转换路径就是测试路径，而且在使用FSM模型时选择不同的测试覆盖准则所产生的测试用例是不同的。
4．具体化抽象测试
基于模型的测试的第四步是把高层的抽象测试转化为可执行的具体测试。主要有两种方法：(1)使用模板和映射抽象测试的变换工具；(2)通过一些环绕在SUT和代码实现间的适配器。
5．执行具体测试
基于模型的测试的第五步是在被测系统上执行具体的测试用例，不管是在在线的还是离线的基于模型的测试，都可以使用测试执行工具和方法。
6．分析测试结果
得到测试结果后，必须确定产生该故障的原因并采取纠正措施，因为有可能是建模时的缺陷模型导致的测试用例本身故障。然后根据测试结果和分析结果，评估被测软件的质量，并且指出出错的地方和提出改进的意见和建议。
5
反馈需求分析反馈模型反馈抽象测试具体化生成测试输入序列执行测试预期测试输出观察分析结果反馈被测系统
图2.1 基于模型的测试过程
3.2支持工具
基于模型的软件测试必须有相关工具支持。当前支持基于模型的软件测试工具中比较具有代表性的有：
1) 支持状态机模型的工具。包括，Software Engineering Technology 的测试工具
toolSET_Certify运行于RISC6OOO和 SUN 平台；现在此工具属于 G-Lab，并已经提供了对统计测试的支持；IBM 的 GOTCHA,可以根据用户事先确定的测试充分性准则进行基于软件状态模型的测试例生成； IBM的TCBean 是一个提供测试脚本管理功能的基于状态机的测试引擎。
2) 支持马尔可夫链模型的工具。包括，Cleanroom Software Engineering 的
CleanTest，支持统计测试，是商用的使用模型及统计测试例生成工具；IBM 的 Cleanroom Certification Assistant， 可以自动化统计验证过程，通过使用概率分布产生测试例，并对测试结果进行分析。
3) 对UML模型提供测试支持的工具。包括， SilverMark公司针对IBM 公 司
的 VisualAge 开发的支持测试用例生成和回归测试的 TestMetor 和 UML designer Connection。
4) 对统计测试结果进行分析的工具。包括 AT&ST 的软件可靠性工程工具箱和
美国海军水面战中心开发的 SMERFS，均提供多种时间域和区间域模型进行可靠性估计; 美国空军喷气动力实验室开发的 CASRE，支持可靠性估计和预测。
6
4
分类
本文通过七个维度对基于模型的测试方法进行描述。并对每一个维度探讨了
可能取值。
4.1 模型主体
模型主体包括SUT模型和SUT所处环境模型。目前基于模型的软件测试中往往两者都同时考虑。SUT模型的作用包括：(1)作为SUT的oracle(因为SUT包含了预期行为)；(2)利用结构信息产生测试用例。SUT所处环境模型用于限制SUT模型的可能输出。
4.2 模型冗余程度
基于模型的测试可以被应用到不同的场景。大致说来，主要区别在用于测试和用于实现的模型间的冗余程度。文献[9]中描述了两个可能场景。第一个场景中模型被用来同时产生测试用例和系统实现。该场景中用于产生代码的模型必须描述详细，但对测试用例生成来说确需要抽象级别更高的模型。第二个场景是：模型仅用于产生测试用例。该模型根据规约文档生成，而SUT则是手工实现。我们可以使用该模型作为系统的规约补充，但其相当复杂。往往需要补充文档辅助才能使用。
4.3 模型特征
模型特征与非确定性、时序问题、模型的连续性或事件离散性有关。非确定性在SUT和模型中均会发生。时序问题一般与实时系统相关。而就动态性而言。模型可能是离散的、连续的或两者综合。基于模型的软件测试过去往往关注离散模型，但连续或者混合模型目前在嵌入式系统中得到广泛使用和研究。不同的模型特征将影响对模型表示法的选择、测试用例的生成和执行。
4.4 模型表示法
目前存在大量模型范式对SUT进行建模，根据[10]获得如下的分类： 1) 基于状态的表示法：针对变量集和修改变量的操作对系统进行建模，变量集代表系统内部状态的一个快照，操作通过前置条件和后置条件定义。典型代表为Z、B、VDM和JML。
2) 基于Transition的表示法：描述不同系统状态间的transition。采用类似FSM的形式进行表示。结点代表系统的状态，边代表系统的操作或行为。目
7
前常通过添加数据变量、采用分层的机器和机器之间的并行来加强表示能力。典型代表为Statecharts．hbeled transition system和I／O automata。 3) 基于历史的表示法：通过描述随着时间的推移，行为允许的轨迹对系统进行建模。可以使用不同的类型的时间记号(离散或连续，线性或分支，点或区间等)，导致了不同类型的时序逻辑。
4) 函数表示法：将系统描述为数学函数集。有可能是一阶的也有可能是多阶的。但该类表示法较为抽象和难于使用。所以在基于模型的测试中使用并不多。
5) 操作表示法：认为系统是可执行进程集，进程间并行执行。该表示法适合描述分布式系统或通讯协议。典型代表是进程代数或者Petrinet。 6) 随机表示法：通过基于事件或者输入值的概率模型来描述系统，更倾向于为环境建模。例如使用Markov chain为期望的用户操作版本建模．据此产生的测试用例集可以体现用户的实际使用场景。
4.5 测试用例选择标准
测试用例选择标准可以辅助测试用例的生成。目前并不存在一个最优标准。普遍使用的标准包括：
1) 结构化模型覆盖标准：标准充分利用了模型结构信息，例如在基于transition的模型中。采用与图相关的覆盖标准来生成测试用例。
2) 数据覆盖标准：标准主要关注如何从大规模数据空间里面选择典型取值。常见的方式是等价类划分和边界值分析。
3) 基于需求的覆盖标准：当模型的元素与SUT的非形式化需求相关时，需要基于需求的覆盖标准。例如：需求数量可能与UML状态图的transition有关。
4) Ad—hoc测试用例规约：除了模型，测试工程师可以依据经验，用形式化的表示方法编写必须覆盖的测试用例规约。指定对应的测试用例。
5) 随机标准：大部分用于环境模型。因为是环境决定了SUT的使用方式。行为概率直接用模型表示。产生的测试用例反应了用户的实际操作情况。
6) 基于缺陷的标准：适用于SUT模型。最常见的基于缺陷的覆盖标准是变异覆盖。包括对模型进行变异、产生测试用例用于区分变异模型和原有模型。
4.6 测试用例生成技术
目前在给定SUT模型和测试用例规约下。主要包括如下技术：
8