基于有穷状态模型的测试生成-副本.ppt

基于有穷状态模型的测试生成,讲解人：郑腾飞,第3章,Foundations of Software Testing,3.1 软件设计与测试,图 3-1 简化的软件开发过程,3.2 有穷状态机,FSM包括一个有穷状态集合、一个输入集合、一个起始状态以及一个可用状态图定义的转换函数。,3.2 有穷状态机,例3.1 考虑一个具有3路旋转开关的台灯。当开关被旋转到某位置时，台灯处于OFF状态。顺时针旋转开关到下一个位置，台灯的状态变为ON_DIM，再次顺时针旋转一下开关，台灯的状态变为ON_BRIGHT。最后，再顺时针旋转一下开关，台灯的状态又变回OFF。这个旋转开关充当了输入设备，控制台灯的状态。台灯状态随着开关位置变化而变化的情况可采用如图3-2a所示的状态图进行说明。 台灯具有OFF、ON_DIM、ON_BRIGHT这3个状态以及1个输入。注意，尽管从台灯用户的角度看，台灯只能顺时针旋转到下一个位置，但台灯开关有3个不同的位置（刻槽）。这样，“顺时针旋转开关一个刻槽”就是唯一的输入。假设开关可以反时针旋转，那么台灯就有两个输入，一个对应顺时针旋转。台灯的状态任然是3个，但其状态图如图3-2b所示。,如果一个FSM不将状态转换与任何操作关联在一起，称作Moore机。 如果一个FSM将每个状态转换都与操作关联在一起，称作Mealy机。 无论是Moore机，还是Mealy机，FSM包括一个有穷状态集合、一个输入集合、一个起始状态以及一个可用状态图定义的转换函数。,3.2.1 用输入序列激活FSM,在大多数实际情况下，FSM都是用取自输入字符集的一串输入字符来激活。例如，假设台灯的状态图3-2b所示，其当前状态为ON_BRIGHT,接收到的输入串为r，则 r=Turn_CCW Turn_CCW Turn_CW 采用图3-2b中的转换函数，很容易验证r使台灯从状态ON_BRIGHT转换到ON_DIM。这个转换可用下面的转换序列表示： (ON_BRIGHT, Turn_CCW)= ON_DIM (ON_DIM, Turn_CCW)= OFF (OFF, Turn_CW)=ON_DIM 为简便起见，用符号 ,表示“长度大于等于的输入串z使FSM从状态 转换到 ”。这样，针对图3-2b所示的状态图，有(ON_BRIGHT, r)= ON_DIM。,3.2.2 转换函数和输出函数的表格表示,表格可以用来表示转换函数和输出函数O。该表格由两个子表组成，左边的子表是输出输出或操作子表，右边的子表是下个状态子表。子表的每一行都用FSM的状态进行标注。输出子表的项表示在给定状态下FSM针对接收到的单个输入应完成的操作；下个状态子表中的项表示自给定状态下FSM针对接收到的单个输入应转换到的状态。 例3.3 下表说明如何表示DIGDEC机的转换函数和输出函数。,3.2.3 FSM的特征,完全定义的FSM 如果M是FSM，从它的每一个状态出发， 对每个输入符号都存在一个转换，则称该FSM M是完全定义的。 如图3-2a所示。 强联通的FSM 如果M是FSM，它的每一对状态 都存在一个输入串使M从状态 转换到 ，则称该FSM M是强连通的。 如图3-2b所示。 最小机 如果FSM M的状态数量少于或等于其他任何与其等价的FSM，则称M是最小机。,3.3 符合性测试,在通信协议测试领域广泛采用“符合性测试”这个术语。如果通信协议的某个实现通过了一系列的从协议规范设计出来的测试，就称协议的该实现符合协议的规范。,3.3.1 重置输入,给定测试用例集合T= ，测试过程如下： 1）将IUT置于初始状态；对T中的每个测试用例重复下面的步骤。 2）从T中选择下一个测试用例，将其应用于IUT；观察IUT的运行结果，并与图3-7中所示的预期输出进行比较；如果IUT产生的输出与预期输出不一致，则称IUT失效。 3）通过运用重置输入操作，将IUT置回初始状态，重复上面的步骤，使IUT准备好接收T中的下一个测试用例。 通常假设重置输入操作产生的是一个null输出。相对于其控制规范：FSM M=(X,Y,Q, ,O) 为了测试IUT，其输入字符集和输出字符集分别扩展为： X=XRe Y=Ynull 其中，Re代表重置输入，null代表相应的输出。,3.3.2 测试的难题,设M是FSM设计的形式化表示。设R代表需求，从R可以导出M。R和M常常作为生成测试用例以及判定输出的结果的基础。 测试的难题在于判断IUT与M是否是等价的。等价性可用IUT和M的I/O行为来定义。 如图3-7所示，测试IUT与M的等价性，要求对IUT执行一系列从M导出的测试用例，并将观察到的结果与预期的结果进行比较。,3.4 故障模型,FSM是一种表示根据给定需求集合R构造出来的设计。 设 是想要满足R 中需求的设计，即设计规范，用来指导软件的实现。设 表示想要满足R中需求、并用 导出的具体实现。 测试的任务是判断 是否满足需求R。 给定T，用每个测试用例t(tT)测试 ，并将 的运行结果与测试用例t在初始状态激活 所得的预期结果进行比较。 在理想情况下：通过用从 导出的部分测试用例t(tT)测试 ，就能检测出 中的所有错误。这是很难实的，其中的原因是设计规范 的可能实现数量是无限的，造成可能在 中引入大量各种各样的错误。 面对这种现实，提出了故障模型。故障模型定义了一些在 中可能出现的故障类型。在给定故障模型的情况下，测试的目标就是：当用T对 进行测试时，要确保 中含有的属于故障模型类型的任何故障都要检测出来。,操作错误 在状态转换时产生的输出中任何错误称为操作。 转换错误 从一个状态到下一个状态转换中的任何错误称为转换错误。 冗余错误 在实现中可能会引入额外的状态。 状态确实错误 缺失状态是另一种类型的错误。,3.4 故障模型,3.4.1 FSM的变体,给定一个设计 ，区分软件实现与设计规范的一个方法就是采用变体。 所谓 的变体，就是通过一次或多次引入一个或多个错误而得到的一个FSM。 图3-11所示为两个变体。,例3.6 设图3-12中M表示正确的设计，假设每次只能想M引入一个错误。通过引入操作错误，分别得到图3-12中的变体 。考虑每个状态又两个转换，通过引入转换错误，得到另外4个变体 。,3.4.2 故障覆盖率,判断测试用例集质量的一个方法就是计算它对具体的实现 能检测出多少错误。用测试用例集的故障覆盖率评价设计方法。 ：用于生成测试用例集的FSM M的一阶变体总数。 ：与M等价的变体数量。 ：能用测试用例集T将其与M区分开的变体数量，其中T使用某些测试生成方法产生的。 针对设计规范M以及实现的集合I(M)，用FC(T,M)表示测试用例集T的故障覆盖率，计算方法如下：,3.5 特征集,大多数从FSM生成测试的方法都使用了一个称作特征集的重要集合。该集合一般表示为W，通常称作W集。 设M=(X,Y,Q, ,O)，是完全定义的最小机，M的特征集W是一个输入串的有限集合，对于M中的任意一对状态 和 ，在W中至少存在一个输入串能将 和 区分开。假设 和 是Q中的状态，那么在W中存在一个输入s使得 。,例3.7 考虑FSM M=(X,Y,Q, ,O)，其中X=a，b，Y=0，1,Q = ， 是初始状态，状态转换函数与输出函数O如图3-13所示。该FSM的W集如下： W=a，aa，aaa，baaa 判断W是否真的是M的特征集，考虑串baaa，容易验证：当M处于初始状态 用baaa激活时，输出序列为1101；当M处于状态 用baaa激活时，输出序列为1100。因此， ，这意味着baaa将状态 和 分开了。,在给定FSM M=(X,Y,Q, ,O)的情况下，对于有穷状态机Q中的两个状态 和 ，若不存在 ，使得 ，那么称 与 是k等价的。 给定FSM M=(X,Y,Q, ,O)，Q的一个k等价划分记为 ，是n个有穷状态集 的集合，满足: 1) ； 2) 对于1jn， 中的状态都是k等价的； 3) 对于ij，如果 ，那么 与 必定是k可划分的。,3.5.1 k等价划分的构造,3.8.2 UIO串,3.8.2 UIO串,3.8.2 UIO串,3.8.2 UIO串,3.6 W方法,W方法用来从FSM M构造测试集。这样生成的测试集是一个向程序输入的输入串的有穷集合，程序的控制结构用M进行模拟。,3.6.1 W方法,为了有效地工作，W方法做了如下假设： 1）M是确定的、完全定义的、联通的最小机。 2）M开始于一个固定的初始状态。 3）M可以准确地重置到初始状态。 4）M与IUT具有相同的输入字符集。 给定FSM M=(X,Y,Q, ,O)，W方法包括下列步骤： 步骤1 估计正确设计中的最大状态数。 步骤2 构造M的特征集。 步骤3 构造M的测试树（testing tree），并确定转换覆盖率集P。 步骤4 构造集合Z。 步骤5 PZ就是预期的测试集。,3.6.2 最大状态数,由于没有得到具体需求规格说明的正确设计或正确实现，因此有必要估计正确设计中的最大状态数。在最坏的情况下，即无论任何有关正确设计或实现的信息，可以假定最大状态数与M中的状态数一样。,3.6.3 转换覆盖集的计算,用P表示FSM M=(X,Y,Q, ,O)的转换覆盖集，定义如下：设 是M中的两个状态， ,P由形如s、x的输入串组成，其中 ， ；空字符也属于P。现在用M的测试树来构造P。 首先，FSM的测试树构造如下： 1）初始状态 是测试树的根节点(第1层)。 2）假设测试树已构造到第k层，第k+1层构造如下： 从第k层选择一个节点n，如果n出现在从第1层到第k-1的任何一层中，则将n作为叶节点，并不再对该节点进行扩展；如果n不是叶节点，那么对于每个xX，若有(n，x)=m，则从节点n新增一条到节点m的分支，并将该分支标注为x。这个步骤重复进行，直到第k层所有的节点都被处理完为止。,例3.11 首先，测试树只有根结点初始状态 ，这是测试树的第1层。接着由于 ，因此，增加两个结点 、 作为第2层，从 到 和 的分支分别标注意a和b。 在第2层，首先考虑结点 。由于结点 已经在第1层出现过，则在这层的结点 就是叶结点，不再进行扩展。再考虑结点 ，由于 ， ，因此增加两个结点 和 作为第3层，从 到 、 分支分别标注意b和a。 重复上面的步骤，每步骤完成一个层次。当到第6层时：结点 、 都是叶结点，不在扩展。这样，就得到M的测试树，如图3-14所示。,测试树构造出来后，通过连接测试树子路径上的标注符号就得到转换覆盖集P。测试树子路径就是从测试树根节点开始，终止于测试树任何结点的一条路径。通过遍历图3-14中测试树的所有子路径，得到转换覆盖集： P=,a，b，bb，ba，bab，baa，baab，baaa，baaab，baaaa,3.6.4 构造集合Z,当给定输入字符集X合特征集W时，可以直接构造Z。假设IUT中估计的状态数是m，设计规范中的状态数是n，Z的计算如下： 当m=n时(即IUT的状态数与设计规范的状态数相同)，Z=W;当mn时， 其中， =，符号“”代表连接运算。,3.6.5 导出测试集,在构造出P和Z之后，很容易获得测试集T，T= PZ,3.6.5 导出测试集,在构造出P和Z之后，很容易获得测试集T，T= PZ。 例3.12 假设正确设计或IUT中的状态数与图3-13所示的设计中的状态数相同，因此，m=n=5，这导致：Z=W=a，aa，aaa，baaa 将P与Z连接起来，得到所要的测试集： T=PZ=, a, b, bb, bab, baa, baab, baaa, baaab, baaaaa, aa, aaa, baaa = a，aa，aaa，baaa， aaaa，abaaa， ba，baa，bbaaa， bba，bbaa，bbbaaa， baaaa，babaaa， baba，babaa，babbaaa， baaaaa，baabaaa， baaba，baabaa，baabbaaa， baaaaaa，baaabaaa， baaaba，baaabaa，baaabbaaa， baaaaaaa，baaaabaaa ,3.6.6 采用W方法测试,为了测试针对设计规范M的IUT ，对每个测试输入执行如下步骤： 1）给定测试输入t，通过设计规范导出预期结果M(t)。 2）求出在初始状态处用t激活IUT的实际结果 。 3）若 ，则在IUT中还未发现缺陷。若 ，则意味着在M正确的情况下，IUT中可能存在缺陷。 注意：实际结果和预期结果不一致，并不意味着IUT中一定存在缺陷。 若我们假设: (a)设计规范M是正确的； (b) 的导出过程没有错误； (c) 之间的比较也是正确的； 那么， 意味着设计规范或IUT中一定存在缺陷。,例3.13 用W方法测试图3-13所示的设计。假设设计规范也用FSM的形式给出且是“正确的设计”。,考虑两个可能的IUT。设计规范M如图3-15a，IUT 分别表示两个错误的设计，如图3-15b、c所示。为了测试 针对 M正确与否，输入例3.2中导出的测试集T中的每个测试用例。选择t=baaaaaa作为测试输入，得到： 输入串baaaaaa检测出了 中的一个转换错误。 接着，测试 针对M是否正确。选择t=baaba作为测试输入，得到： 输入串baaba检测出了 中的一个操作错误。加上前面t=baaaaaa检测到的转换错误，用测试集T中的输入串baaaaaa和baaba就能检测出两个IUT中的错误。,3.7 部分W方法,部分W方法，也叫作Wp方法。 类似于W方法，因为测试集也是从完全定义的、连通的最小机FSM中构造出来的。但是，用Wp方法生成的测试集常常比用W方法生成的测试集小。测试集的裁减是这样的实现的：将测试生成过程换分为两个阶段，在第二阶段中采用的是状态等价集 ，而不是特征集W。 定义FSM M=(X,Y,Q, ,O)的状态覆盖集S：S是一个输入串的有穷非空集合，其中每一个元素都属于 X；对于任意 ，存在 ，满足 。 可以看出状态覆盖集是转换覆盖集的子集，并且不唯一。 注意：空字符集属于S，它覆盖了初始状态，按照状态转换的定义， 。,例3.15 在例3.11中，为图3-13所示的FSM M构造了下面的转换覆盖集： P=，a，b，bb，ba，bab，baa，baab，baaa，baaab，baaaa P的子集构成了M的一个状态覆盖集： S= ，b，ba，baa，baaa,现在来说明如何用Wp方法生成测试集。 设M是设计规范的FSM的表现形式，针对其测试IUT。假设M包含你、个状态，IUT包含m个状态。用Wp生成的测试集T包含两个子集 。,假设M包含的状态数与IUT相同，集m=n，下面构造 。 Wp方法(采用Wp方法生成测试集的过程) 步骤 1 计算M的转换覆盖集P、状态覆盖集S、特征集W、状态等价集 。 步骤2 。 步骤3 设是M的所有状态等价集的集合,= 。 步骤4 设R= 是所有属于转换覆盖集P但不属于状 态覆盖集S的输入串的集合，R=P-S。另外，如果 ，则 。 步骤5 ， 是状态 的状态等价集， 。 其中 操作符称作部分串连接操作符。,例3.8 说明用Wp方法生成测试集。考虑用图3-13中的FSM作为设计规范M。列举生成测试集T所需的各种集合如下：,W=a，aa，aaa，baaa, P=，a，b，bb，ba，baa，bab，baab，baaa，baaab，baaa, S=，b，ba，baa，baaa, =baaa，aa，a, =baaa，aa，a, =a，aa, =a，aaa, =a，aaa 根据步骤2计算: =a，aa，aaaa，ba，baa，baaa，bbaaa，baaaa，babaaa，baaaaa，baabaaa，baaaaaa，baaabaaa 根据步骤4得到： R=P-S=a，bb，bab，baab，baaab，baaaa 根据步骤4和图3-13，R中输入串的状态转换：,采用步骤5得： 预期的测试集是：,3.7.1 采用m=n的Wp方法测试,Wp方法包括两个阶段： 第1阶段 采用 中的测试用例测