考虑条件覆盖的EFSM路径的测试数据生成

可在www.sciencedirect.com在线获取理论计算机科学电子笔记309（2014）13-29www.elsevier.com/locate/entcs考虑条件覆盖的EFSM路径公正路1、2号上海大学邮编：200072苏州职业大学计算机工程学院苏州215104淮口苗3号上海大学邮编：200072上海市计算机软件测试评估重点实验室上海201114摘要基于模型的测试用例生成已成为一个研究热点，而测试数据的自动生成是该领域的难点本文采用扩展有限状态机（EFSM）表示系统模型，并采用遗传算法生成EFSM路径的测试数据。当计算个体的适合度时，考虑个体的分支距离和未覆盖条件的比率实验结果表明，该方法具有更好的效果，可以得到更高质量的关键词：EFSM，测试数据，遗传算法，条件覆盖1介绍软件测试是一种有效的软件质量保证技术。在软件测试中，我们首先为被测系统设计由有限个输入和输出序列组成的测试用例，然后在被测系统上执行每个测试用例，并观察执行结果。最后对执行结果进行了比较1本工作得到了国家自然科学基金项目（No.61073050和No.61170044）的资助。2 电子邮件地址：lugz@shu.edu.cn3电子邮件：hkmiao@shu.edu.cnhttp://dx.doi.org/10.1016/j.entcs.2014.12.0031571-0661/© 2014作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。14G. Lu，H.Miao/Electronic Notes in Theoretical Computer Science 309（2014）13与测试用例中声明的预期结果一致。如果执行结果等于预期结果，我们说测试用例通过，否则失败。测试成本可能占整个软件开发成本的50%。因此，我们必须开发方法来降低与测试过程相关的成本。由于手工测试效率低、易出错、不可复制，增加了软件测试成本。自动化测试是一个必然的趋势，基于模型的测试是目前的研究热点。在基于模型的测试中，需要使用形式化模型来描述系统规格，并根据给定的测试准则生成测试用例。可用于指定被测系统的两种模型是有限状态机（FSM）[1]和扩展有限状态机（EFSM）[2]。FSM由一组有限的状态和转换组成。状态机中的转换包括四个部分：进入状态、退出状态、输入和输出。有限状态机只能对系统的控制部分进行建模。EFSM用变量扩展了FSM。EFSM中的转换也可以有谓词（保护条件）和操作（赋值），因此EFSM可以指定系统的控制部分和数据部分。由于EFSM可以描述系统的数据部分，而本文的目的是为从形式化模型中得到的测试用例生成测试数据，因此我们选择EFSM对被测系统进行建模。FSM和EFSM的覆盖准则主要有状态覆盖、变迁覆盖和变迁对覆盖。状态覆盖要求EFSM的所有状态都应该由测试用例来执行。转换覆盖要求EFSM的所有转换都由测试用例执行。转换对覆盖率要求测试用例必须执行所有相邻的转换对变迁覆盖准则比状态覆盖准则更强，即满足变迁覆盖准则的测试用例必须满足状态覆盖准则。转换对覆盖准则比转换覆盖准则更强，即测试用例执行了系统的所有转换对，就一定执行了系统的所有转换。在EFSM中，每个测试用例都定义了一个转换路径（transition path，TP），它由一系列通过EFSM的转换例如，转换覆盖要求EFSM的每个转换至少由对应于测试用例的TP执行因此，当从EFSM模型生成测试用例时，我们应该首先生成一组满足给定覆盖标准的TP，然后生成可以触发这些TP的测试用例。然而，转换可能包含保护条件和操作，从EFSM生成的TP可能是不可行的。贸易点的可行性超出了本文的范围。我们只为这些可行的TP生成测试数据。即使一条路径是可行的，它仍然很难找到测试数据来执行它。因为TP中的输入变量的范围通常很大，但满足保护条件的变量值集可能很小。生成测试数据的方法有两种：基于约束的测试（CBT）[3]和基于搜索的测试（SBT）[4]。基于约束的方法采用符号执行的方式来获取路径约束，而路径约束只与输入参数有关。然后使用约束求解器求解每个路径约束，G. Lu，H.Miao/Electronic Notes in Theoretical Computer Science 309（2014）1315测试数据满足约束条件。基于搜索的方法类似于基于约束的方法，也需要首先得到路径约束。不同之处在于，基于搜索的测试将测试数据的生成转化为函数优化，通过搜索算法得到最佳拟合度（拟合度为0）的个体作为测试数据。该函数优化问题可以采用遗传算法、蚁群算法、粒子群算法等元启发式算法求解。本文采用扩展有限状态机（EFSM）对被测系统进行建模，并采用遗传算法生成EFSM路径的测试数据。 分析了Kalaji [5]提出的拟合函数，并通过一个小例子说明了Kalaji和Lefticaru [15]提出的方法的不足之处。 为了解决存在的问题 在Kalaji的方法中，我们提出了一个新的拟合函数来生成EFSM路径的测试数据。这个新的拟合函数将分支距离与未覆盖条件的比率相结合，以计算个体的拟合度。从平均生成次数、成功率和测试数据的平均条件违反率等方面对Kalaji函数进行了改进。在实验中，我们使用三个EFSM模型来比较我们的方法和Kalaji的论文的其余部分组织如下：第2节介绍了相关工作，第3节说明了背景，第4节提供了我们提出的方法，第5节是实验和结果分析，第6节是结论部分。2相关作品在此之前[6-8]已经有很多关于程序测试数据生成的研究但是，从EFSM模型生成测试数据的工作相对较少。J.Zhang等[13]提出了一种面向路径的测试数据生成方法，首先利用符号执行推导出路径约束，然后利用约束求解器求解路径约束，最后得到测试数据。该方法的局限性在于不能处理非线性约束。R.Lefticaru et al. [14]给出了一种获取路径输入序列的拟合度评估方法，Tracey提出的拟合度函数被应用于路径的每个过渡，并且通过将路径中的每个过渡视为关键节点来定义路径的拟合度。它的局限性在于，它要求每一个过渡都不能包括内在的道路，否则特雷西的适合性就不能用在他的方法中。A.S. Kalaji等人[5]使用遗传算法生成EFSM的测试数据，拟合函数由分支距离和逼近水平组成。这种拟合函数可能会丢弃拟合较好的测试数据， 并且不 能对距 离极差 区间 相同距 离的测 试数据 给出相 同的选 择概率 。R.Lefticaru等人[15]还改进了Kalaji16G. Lu，H.Miao/Electronic Notes in Theoretical Computer Science 309（2014）13每个子路径的适合性。他们的方法奖励满足更多路径约束的个体，这与我们的方法相似。其缺点是仍然存在Kalaji方法中的问题3预赛3.1扩展有限状态机一个有限状态机由一组有限的状态、转换、输入和输出组成。由于有限状态机不能指定系统的数据部分，我们使用扩展的有限状态机来建模被测系统。EFSM通过上下文变量、谓词和操作扩展了FSM。EFSM是一个六元组（S，s0，V，I，O，T），其中S是一组有限的状态，s0是初始状态，V是上下文变量的有限集合，I是输入的有限集合，O是输出的有限集合，T是转换的有限集合。 过渡t∈T是一个五元组（ss，i，g，op，se），其中ss是t的源状态，i∈I是可能与输入参数相关联的输入，g是一个逻辑表达式，称为guard condition，op是由赋值语句或输出语句组成的操作，se是t的目标状态。 如果状态是s，则输入是i， 满足保护条件，则触发转换t=（ss，i，g，op，se），同时执行op中的操作，EFSM转换到状态se。g和op都可以包含输入参数和上下文变量。在这里，我们只考虑确定性EFSM。EFSM是确定性的，如果对于离开状态的相同输入的转换，一次只满足一个转换的保护条件[16]。关于EFSM的定义和细节可以在[2]中找到3.2符号执行符号执行[17]是一种静态分析程序的方法。它用符号值代替实值来执行程序，结果是符号表达式。理解输入和输出之间的关系是有用的。当符号执行用于测试数据生成时，测试数据生成问题可以转化为求解符号表达式的问题，该符号表达式是由使用符号值执行路径而产生的例如，给定转移路径t1t2t3，每个转移上的谓词是x>0，y15和z≥10分开我们用符号a、b和c分别代替变量x、y和z。在使用符号值执行路径之后，我们获得符号表达式 a >0且D b 15且D c≥ 10。 路径测试数据的生成问题t1t2t3现在转换为寻找符号的解决方案的问题表达式a>0AN D b 15AN D c≥ 10。G. Lu，H.Miao/Electronic Notes in Theoretical Computer Science 309（2014）13173.3数据流依赖性虽然EFSM中存在输入变量和上下文变量，但符号表达式通常仅由输入变量表示。路径中的上下文变量必须使用数据流依赖性分析由相应的值和输入变量替换。给定一个变量v，如果它是变迁t中的一个输入参数，或者在变迁t的一个运算中被赋值，那么v被称为在t中定义的，记为def（t）。如果v在谓词（p-use）或转换t的操作中被引用，则v被称为在t中使用，写作use（t）。给定两个过渡之间的路径ti和tj，v∈def（ti）和v∈use（tj），如果v在ti之后和tj之前没有定义，则从ti到tj的路径是v的明确路径。（ti，tj）形成v的定义-使用对，并且在ti和tj之间存在数据流依赖性[18]。在获得每个转换上的上下文变量的数据流依赖性之后，这些上下文变量被它们所依赖的值和输入参数使用向后替换来替换。后向替换处理路径中从后向前的过渡，用变量依赖的定义替换过渡中使用的变量，最终路径表达式是仅由输入变量表示的符号表达式3.4遗传算法遗传算法（Genetic Algorithm，GA）是从生物进化规律演化而来的一种随机化方法该算法具有并行和全局寻优能力，能够自动获得和引导最优搜索空间，并自适应调整搜索方向。遗传算法的这些特性在组合优化、机器学习等领域得到了广泛的应用。目前，它已被应用于软件测试，特别是基于搜索的软件测试。遗传算法（GA）[19]是一种强大的元启发式技术。在遗传算法中，候选解（也称个体）称为由基因组成的染色体.GA循环由主要算子组成：评估、选择、交叉和变异。GA使用拟合函数评估每个个体的拟合度。在对个人进行评估后，根据适合性进行选择。当根据选择策略选择个体作为父个体时，应用交叉算子来生成新的个体。变异算子是另一种可以用来产生新个体的方法，它一次只作用于一个个体，随机改变个体的一些基因的值基于搜索的软件测试将软件测试问题转化为优化问题。在基于搜索的测试中，为了生成EFSM路径的测试数据，需要利用数据流依赖分析计算每条路径的符号表达式，然后将符号表达式作为一个待求解的函数，利用遗传算法搜索最优解。测试数据对应于个体。首先，我们需要使用遗传算法提供的编码机制对测试数据进行编码。的编码18G. Lu，H.Miao/Electronic Notes in Theoretical Computer Science 309（2014）13表1Tracey等人提出的拟合计算。后卫健身计算布尔型IfT RUE then 0 elseka==bIfabs（a−b）== 0 then 0 elseabs（a−b）+k a！=b Ifabs（a−b）！= 0 then 0 elseka bIfa−b 0 then 0 else（a−b）+ka≤bIf（a−b）≤0 then 0 else（a−b）+k a>bIfb−a 0 then 0 else（b−a）+ka≥bIf（b−a）≤0 then 0 else（b−a）+ka否定向内移动并传播到候选解具有二进制编码、整数值编码和实值编码。在本文中，我们使用实值编码来表示测试数据。我们使用一种称为拟合函数的评估方法来衡量每个测试数据的好坏。拟合函数为每个测试数据分配一个正数，这个数字估计它距离触发路径的可接受解有多远。优化问题通常是最小化问题，拟合度较低的测试数据在确定了测试数据的表示形式和定义了适应度函数后，我们可以用遗传算法生成EFSM路径的测试数据4所提出的方法Kajaji的拟合函数是Wegener方法的扩展[5]。Kalaji分支距离为aTracey等人所包含的适合性评价方法，详情见表1。例如，对于条件x>0，如果（0−x）0，则其分支距离为0，这说明x的当前值满足给定条件。<如果（0−x）≤0，则分支距离不为零（分支距离是（0−x）+k，k >0是一个常数），它反映了所选值与实现条件的接近方法层次是由Wegener提出的。它测量测试数据与执行目标语句的接近程度。距离的计算方法是从距离目标的关键节点数中减去1。关键节点是一个条件语句，在该条件语句处，执行流程可以转向。 而且这种方法一次只能对付一个目标。Kalaji改进了Wegener的方法，定义了一个转换的接近水平，即从目标转换的临界转换数中减去1，并以类似于嵌套IF语句的方式操纵一条包含多个转换的路径。卡拉吉的G. Lu，H.Miao/Electronic Notes in Theoretical Computer Science 309（2014）1319拟合函数如下：norm（分支距离）=1−1。05-（分支距离）（1）函数距离=范数（分支距离）+转变接近水平（2）转变接近水平= NumOfCriticalT transwayFromT target-1（3）路径适应性=范数（函数距离）（4）等式（1）中的norm（）是归一化函数。分支距离被归一化为范围[0.1]。路径的适合性可以以与Wegener为嵌套预测提出的方法类似的方式推导。给定路径，通过应用Wegener方法（等式2）针对具有保护条件的每个转变计算函数距离。（2））。然后，具有保护条件的任何转变被认为是临界转变，并且因此转变接近水平的值通过从远离目标转变的临界转变的数量中减去1来导出（等式10）。（三））。最后，路径拟合度是过渡接近水平和分支距离的归一化值之和。在EFSM中，转换的保护条件可以通过逻辑运算符AND和OR连接。由AND运算符连接的保护条件可以表示为嵌套的IF语句。如果保护条件由OR运算符连接，则可以将转换分割为等于OR运算符的数量+1的转换数量，并且我们可以分别计算每个转换的适合性，并且保护条件的适合性是转换中的最小适合性。例如，我们采用Kalaji如果0≤x如果x≤15result= 0 //候选解是可接受的解否则result=norm（x−15）端elseresult =norm（0−x）+1end我们假设有两个输入x=− 1和x= 16。根据Kalaji当x= 16时，满足条件0≤x，但不满足x≤15，因此谓词的适合性是result=norm（1）。在事实上，距离区间[0，15]的距离-1和16都是1，它们应该具有相同的拟合度，并且在遗传算法中具有相同的选择概率。当用Kalaji的方法评估它们的适合性时，适合性是不相等的。x= 16具有较低的拟合度，因此可以选择它来生成新的个体。然后我们使用Lefticaru方法计算当输入为x = − 1和x = 16时路径的拟合度我们可以得到与Kalaji方法相同的结果接下来，让我们考虑另一种情况。路径中有两个变迁t1和t2，t1上的谓词是x1≥ 16AND x2≤ 9，t2上的谓词是x3≥ 7 AND x4≤ 0，使用Kalaji方法计算的路径的适合性如果x1≥ 1620G. Lu，H.Miao/Electronic Notes in Theoretical Computer Science 309（2014）13如果x2≤ 9如果x3≥ 7如果x4≤ 0结果= 0elseresult=norm （ x4−0）endelse结果 =norm（7−x 3）+1endelseresult =norm （ x2− 9 ）+2 endelse结果 =norm（16−x 1）+3end我们假设有两个输入（x1，x 2，x 3，x 4）=（15， 8， 8，− 1）和（x1，x2，x 3，x 4）=（17， 10， 6， 1）。第一个输入满足除第一个之外的所有条件，第二个输入只满足第一个条件。第一个输入结果=norm（1）+3，第二个输入的适合性是结果=norm（1）+2，因此第二个输入被选为父个体的概率高于第一个输入。只有变量x1的值在第一个输入中不满足，而除了x1之外的所有变量的值在第二个输入中都不满足，所以我们可以从第一个输入中得到可接受的解决方案实际上比从第二个输入中更容易。当输入为（x 1，x 2，x 3，x 4）=（15，8，8，− 1）和（x 1，x 2，x 3，x 4）=（17，10，6，1）时，我们也使用莱夫卡鲁方法计算路径的拟合度 我们可以看到t1和t2是独立的。所以有两个独立的子路径，可以分别计算每个子路径的适合度。第一个输入的拟合度是result=norm（1）+1，第二个输入的拟合度是result= 2norm（1）+1。 第一个输入被选为父个体比第二个输入高，因为第一个输入满足的条件比第二个输入多。第二个是拟合度较低。虽然Lefticaru方法的结果与实际情况相符，但它对每条独立子路的拟合计算采用了类似于Kakaji方法的IF嵌套形式，但Lefticaru方法仍然存在Kalaji方法存在的问题，不能总是找到路集中的独立路，当路集中没有独立路时，Lefticaru方法的结果与Kalaji方法相同。因此，我们没有比较我们的方法与Lefticaru为了解决上述Kalaji方法的问题我们的拟合函数将分支距离与未覆盖条件的比率相结合。假设路径中出现的条件数是n，一个人不满足的条件个数是m（m≤n），我们的拟合函数可以表示如下：G. Lu，H.Miao/Electronic Notes in Theoretical Computer Science 309（2014）1321M未覆盖条件比率=n布勒姆（五）路径适应性=i=1范数（分支距离i）（六）+未覆盖条件比率在我们的方法中，路径中转换的保护条件不表示为嵌套的IF语句，而是表示为并行形式。并且AND运算符所连接的保护条件也表示为并行形式，而不是嵌套的IF形式。由运算符OR连接的保护条件被分割成单独的转换，并且保护条件的适合性是这些转换中的最小适合性。我们使用我们提出的方法来计算谓词0≤x和D x≤第15话转型T这个谓词有两个条件：如果0≤x结果1 = 0else结果 1 =norm（0−x）+1/ 2end如果x≤15结果2 = 0else结果 2 =norm（x−15）+ 1/ 2end结果=结果 1+结果 2这里，我们仍然假设有两个输入x=− 1和x= 16。 根据我们的拟合函数，当x=− 1时，不满足条件0≤x，结果1 =norm（1）+ 1/ 2，满足条件x≤15，结果2 = 0，最终拟合是结果=norm（1）+ 1/ 2。当x= 16时，满足条件0≤x，结果1 = 0，不满足条件x≤15，结果2 =norm（1）+ 1/ 2，谓词的适合性是结果=norm（1）+1/ 2。因此，两个输入具有相同的fitness当两个人离值域的边界有相同的距离时，我们的拟合函数赋予他们相同的拟合度，他们被选中的概率也相同我们重写另一个例子，这是由Kalaji的方法计算上述使用我们的方法。这个例子中的谓词有四个条件，适合性可以计算如下：如果x1≥ 16结果1 = 0else结果 1 =norm（16−x 1）+1/4 end如果x2≤ 9结果2 = 0else结果 2 =norm（x2− 9）+1/4 end如果x3≥ 7结果3 = 022G. Lu，H.Miao/Electronic Notes in Theoretical Computer Science 309（2014）13else结果 3 =norm（7−x 3）+1/4 end如果x4≤ 0结果4 = 0else结果 4 =norm（x4− 0）+1/ 4end结果=结果 1+结果 2+结果 3+结果 4我们仍然假设有两个输入（x1，x 2，x 3，x 4）=（15， 8， 8，− 1）和（x1，x 2，x 3，x 4）=（17， 10， 6， 1）。第一个输入的拟合度是result=norm（1）+1/ 4，第二个输入的拟合度是result= 3/norm（1）+ 3/ 4。所以第一个输入比第二个输入有更高的概率被选为亲本个体，这符合事实。当个体满足更多的条件时，即条件的未覆盖率较低时，我们的拟合函数赋予它较低的拟合度，它被选中的概率较高。我们的方法的步骤如下：1. 通过符号执行和数据流依赖分析，获得EFSM中每个迁移路径的路径约束。路径约束只包含输入变量。2. 使用并行IF语句表示路径约束。路径约束由AND操作符链接的每个转换上的保护条件组合而成。根据我们的方法，这些保护条件被表示为并行IF语句，并且每个保护条件中由AND操作符连接的条件也被表示为并行形式，但是每个由OR操作符连接的保护条件被分割成单独的转换，并且保护条件的适合性是这些转换中的最小适合性3. 使用遗传算法为每条EFSM路径生成测试数据。在遗传算法中，我们使用本节中提出的拟合函数来评估测试数据的拟合度。我们用一个例子来解释我们的方法。T.g和T.op分别表示转变T的保护条件和操作。假设有一条路径t1t2t3t4。t1.g为T rue，t1.op为v1 =pv 1AN D v 2 =pv 2AN D v 3=pv 3AN D v 4 =pv 4，t2.g为v1≥ 11AN D v 1≤ 25AN D v 2≥ 50AN D v 2≤ 85，t3.g为v3≥ 11AN D v3 ≤ 25，t4.g是v4≥ 36或 v4≤ 10，并且t2，t3和t4的运算都是NULL。根据数据流相关性分析，t2，t3和t4依赖于t1.在这些转换的保护条件中出现的上下文变量应该由在t1的操作中定义的定义来代替，然后路径约束为pv1≥11AN D pv 1≤ 25AN D pv 2≥ 50AN D pv 2≤ 85AN D pv 3≥ 11AN D pv 3≤25AN D（pv4≥ 36或pv 4≤ 10）。因为由OR链接的警戒条件操作被划分为单独的转换，并且当只要有一个单独的转换的条件被满足时，保护条件被满足则上述路径约束的条件的数量为7。在遗传算法中，为路径t1t2t3t4生成的测试数据的拟合度可以计算如下：如果pv1≥ 11G. Lu，H.Miao/Electronic Notes in Theoretical Computer Science 309（2014）1323结果1 = 0else结果 1 =norm（11−pv 1）+1/7 end如果pv1≤ 25结果2 = 0else结果 2 =norm（pv1− 25）+1/7 end如果pv2≥ 50结果3 = 0否则结果3 =norm（50 −pv 2）+ 1/7 end如果pv2≤ 85结果4 = 0else结果 4 =norm（pv2 −85）+ 1/7 end如果pv3≥ 11结果5 = 0else结果 5 =norm（11−pv 3）+ 1/ 7end如果pv3≤ 25结果6 = 0else结果 6 =norm（pv3− 25）+1/ 7end如果pv4≥ 36结果7 = 0else结果 7 =norm（36−pv 4）+1/7 end如果pv4≤ 10结果8 = 0else结果 8 =norm（pv4− 10）+1/ 7end如果结果7≤结果 8结果 9 =结果 7否则结果9 =结果 8结束结果1+结果 2+结果 3+结果 4+结果 5+结果 6+结果 95实验结果在本节中，我们使用我们提出的方法生成三个EFSM的测试数据，并将结果与使用Kalaji方法生成的测试数据进行比较。实验在三种不同的EFSM上进行：飞行安全系统EFSM、运输协议EFSM和升力系统EFSM [5]，见图1。24G. Lu，H.Miao/Electronic Notes in Theoretical Computer Science 309（2014）13这些EFSM的跃迁的详细说明可以在文献[5]中看到为了与Kalaji的方法进行比较，我们从三个因素对结果进行了第一个因素是成功生成满足所有条件的测试数据的平均代数。第二个因素是生成测试数据的成功率，当这两种方法有时只能生成测试数据，而不是100%满足所有条件。当该方法能够在一次运行中生成满足所有条件的测试数据时，我们说该方法在这次运行中是成功最后一个是当两种方法都只能生成不满足所有条件的测试数据时，测试数据违反约束的平均比率。我们的方法和Kalaji的都是通过使用遗传算法和直接搜索算法的Mathlab 7.0实现的。个体采用实值编码表示，选择随机一致作为选择策略，交叉函数采用离散度，交叉概率为0.8，变异函数为高斯函数，种群规模为20，各变量的初始范围为[0...100]。当拟合值达到0或达到最大1000代时，搜索将终止。我们对每个过渡路径重复搜索十次，并计算十次运行的平均值。根据该过渡准则，可以生成20条飞行安全系统EFSM过渡路径。生成测试数据的平均代数见图2（a）。除p2， p17， p18， p19， p20， p21外，这两种方法生成测试数据的平均代数相等，约为52。这是因为这些路径的条件很简单，只涉及单个变量。在这种情况下，这两种方法的性能相同。当生成路径p2， p17， p18， p19，p20， p21的测试数据时这两种方法都只能产生测试数据，有时不满足这些路径的所有条件，在十个运行，但我们的方法产生测试数据的成功率图2（b）显示了这两种方法生成六条路径测试数据的成功率。这两种方法有时只能生成不满足这些路径的所有条件的测试数据的原因是这些路径中的条件更复杂并且涉及更多变量。Kalaji的方法赋予不满足外部条件的个体更高的适应性。而这个个体可能满足更多的内部条件，并且可以从这个个体生成可接受的解，但是它可能被Kalaji的方法丢弃，这导致了不良的优化拟合，并且只能生成不满足这些具有更复杂条件的路径的所有条件的测试数据。我们的方法考虑了个体的条件覆盖率，覆盖率越高的个体被赋予的适应度越低，我们的方法将选择不满足外部条件但满足更多内部条件的个体来生成最优解。因此，我们的方法的平均代数高于Kalaji的，我们的方法的成功率也高于Kalaji的。类似地，我们可以根据转换为G. Lu，H.Miao/Electronic Notes in Theoretical Computer Science 309（2014）1325(a) 简单的空中安全系统EFSM（b）II类运输协议EFSM(c)提升系统EFSM图1.EFSM示例标准生成这些路径的测试数据的平均代数如图2（c）所示。两种方法都能生成满足除p8以外所有条件的测试数据，且平均生成次数几乎相同。这两种方法只能生成不满足p8的10次运行中所有条件的测试数据的原因是p8中的条件包括等式Sendsq==T Rsq。由于方程的值域只有一个值，遗传算法的搜索过程不能收敛，很难产生满足方程的测试数据。提升系统EFSM中有24条路径。遗传算法只能生成p1和p2的测试数据.对于其他路径，两种方法每次运行都只能生成不满足所有条件的测试数据，但平均生成次数要高于Kalaji26G. Lu，H.Miao/Electronic Notes in Theoretical Computer Science 309（2014）13(a) Avg.用于生成飞行器安全系统EFSM(b) 飞机安全系统EFSM其原因类似于飞行安全系统EFSM中的解释。为了分析这两种方法对于每次运行只能得到不满足所有条件的测试数据的路径的优缺点，我们用两种方法产生的测试数据违反条件的平均比率来比较KalajiKalaji方法的平均条件违反率在80%以上，而我们的方法的平均条件违反率约为10%，即我们的方法产生的测试数据只违反方程，其他条件都满足。我们用路径中条件的平均违规率来衡量这两种方法生成的测试数据的质量，测试数据的平均违规率越低，其质量越高。从图2（e）可以看出，我们的方法生成的测试数据的质量比Kalaji的好得多我们以路径p3生成的测试数据为例。Kalaji和我们的方法在一次运行中生成的测试数据如表2所示。路径约束为Pos≥0AN D Pos≤ 15AN D Pos 1≥ 0AN D Pos 1≤15AN D w≥ 15AN D w≤250AN DPf== 1AN D Ph≥ 10AN D Ph≤ 35AN D Ps≥ 0AN D Ps≤ 2。路径约束中有11个条件，用Kalaji方法生成的10组测试数据平均违反的条件数是10，所以平均违规率约为91%。只有涉及变量w的条件才被满足。因为变量w的取值范围是[15，250]，所以搜索范围更大，条件更容易满足。用该方法生成的10组测试数据的平均违规率为1.2，即平均违规率为11%。 除方程中包含的变量外，所有变量的值都满足条件。当然，Kalaji的方法将约束表示为嵌套形式，而我们的方法将约束表示为并行形式，当外部条件不满足时，Kalaji的方法计算拟合度，忽略内部条件，而我们的方法计算拟合度，直到所有条件都被分析。所以我们的方法比卡拉吉在Kalaji的论文中G. Lu，H.Miao/Electronic Notes in Theoretical Computer Science 309（2014）1327(c) Avg.生成II类传输协议EFSM(d) Avg.生成电梯系统EFSM(e) Avg.升力系统EFSM图二. EFSM示例我们6结论提出了一种考虑条件覆盖的EFSM路径测试数据生成方法。本文分析了Kalaji(i) 对于只涉及简单约束或单变量的路径，我们的方法生成测试数据的平均代数与Kalaji的方法相同(ii) 对于约束条件较复杂或涉及变量较多的路径，本文方法生成测试数据的成功率高于Kalaji(iii) 对于包含方程的路径，两种方法每次运行都只能生成不满足所有条件的测试数据。我们使用测试数据的条件平均违规率来衡量质量28G. Lu，H.Miao/Electronic Notes in Theoretical Computer Science 309（2014）13表2为路径p3方法测试输入（变量pos、pos1、w、pf、ph、ps）卡拉吉15.39133,62.62504,-15.91648,38.15217,-27.55513,218.8589215.03939,193.80234,-194.5176,60.37151,-38.02112,-193.3718115.11819,-490.47645,-2.95238,230.43769,182.22669,165.3294115.92332,138.21063,228.69416,240.67647,-28.72298,-126.498215.22626,468.96021,18.46922,272.68582,82.63248,315.8070912.92843,-0.7445,176.06993,50.38237,65.32962,-38.2819817.2368,22.55876,25.68157,67.54142,99.38773,65.6634515.31331,106.59772,-49.16128,135.67515,45.85847,210.1908215.14702,-218.11485,-31.06423,44.1253,355.31375,7.5733815.75495,56.36216,0.49388,17.74789,94.31005,30.0455我们的方法13.0755,11.14832,98.09096,0.22852,16.54342,14.6925311.42778,12.57557,46.22755,6.93122,33.77576,22.610436.37736,12.92,28.05086,-1.02062,24.39492,24.680394.01898,9.33363,121.56839,1.95281,32.42047,3.631252.83836,2.15866,158.08038,7.75823,18.10003,8.244538.75266,11.77969,99.40202,4.88325,34.42408,5.563860.51374,5.91561,38.51984,0.51857,11.3195,10.720434.95459,13.66483,64.21061,1.68918,8.12128,3.316419.10128,19.74321,15.68837,1.81516,18.73419,8.2455514.48655,4.13108,47.01741,6.09891,27.96837,24.43352在两种方法生成的测试数据中，我们的方法生成的测试数据的质量要远远高于Kalaji最后，Kalaji引用[1] 安德鲁斯，A.一、J.O. J. T. Alexander，Testing Web applications by modeling with FSM，Softwareand System Modeling。4（2005），326[2] 扬河，巴西-地Z. Y. Chen和B.W. Xu等人，G. Lu，H.Miao/Electronic Notes in Theoretical Computer Science 309（2014）1329via Automatic Path Feasibility Analysis，”In Proc. of the 2011 IEEE 13th International Symposium onHigh-Assurance Systems Engineering（HASE 2011）. IEEE计算机协会，（2011），17[3] Gotlieb，A.，B. Botella和M.陈文辉，自动测试数据生成技术，北京大学出版社，2001。23（1998），53-62.[4] McMinn，P.，基于搜索的软件测试数据生成：一项调查，软件测试，验证和可靠性杂志。14（2004），105[5] Kalaji，A.美国，R. M. Hierons和S. Swift，一种基于搜索的集成方法，用于扩展有限状态机（EFSM）模型的自动测试，信息和软件技术。53（2011），1297-1318。[6] 古普塔，N.，A. P. Mathur和M. L.宋文龙，使用迭代松弛法自动生成测试数据，ACM SIGSOFT软件工程笔记。23（1998），231-244.[7] Korel，B.，自动软件测试数据生成，IEEE软件工程汇刊16（1990），870[8] 弗格森河，和B.陈文辉，软件测试数据生成的链接方法，软件工程与方法学报。5（1996），63-86.[9] 米勒，J.，M. Reformat和H.张，基于遗传算法和程序依赖图的测试数据自动生成，信息与软件技术。48（2006），586[10] Ayari，K.，S. Bouktif和G. Antonym，（2007），1074[11]布兰科河，J. Tuya和B.Adenso-Daz，使用分散搜索方法的自动测试数据生成，信息和软件技术。51（2009），708[12] 帕尔加斯河P.，M. Harrold和R. R. Peck，使用遗传算法的测试数据生成，软件测试，验证和可靠性杂志。9（1999），263[13] 张杰，C. Xu和X. L.王文生，“以符号执行与约束求解技术产生路径导向的测试资料”，第二届国际软体工程与形式化方法会议论文集（SEF