| 主权项 |
一种基于遗传算法的MC/DC测试数据自动生成方法，其特征在于：包括以下几个步骤：步骤一：对被测程序进行静态分析，产生控制流图、数据流图、抽象语法树和抽象分析树；步骤二：生成MC/DC测试用例预期结果集；步骤2.1：从抽象分析树中提出条件节点，这些条件节点构成了抽象分析树的叶子，每一个叶子就是一个变量，用N表示提取的叶子变量的个数；步骤2.2：构建真值表，对N个叶子变量，有2N种排列组合；步骤2.3：用数字0和1填充真值表；步骤2.4：针对真值表中的每一行：步骤2.4.1：将真值表当前行中的布尔值对应分配给抽象分析树的每一个叶子变量；步骤2.4.2：自底向上评价各个条件节点的布尔值，直到抽象分析树的顶端，最终所得的抽象分析树的顶端的条件节点的布尔值就是这个判定语句的输出结果值；步骤2.4.3：用输出结果值填充真值表的输出列；步骤2.5：针对每一个叶子变量，寻找其测试用例，并添加到每个叶子变量的MC/DC测试用例集中：步骤2.5.1：为每一个叶子变量建立一对空的MC/DC测试用例集；步骤2.5.2：在真值表中，寻找其他叶子变量值固定，只有目标叶子变量改变的两行；步骤2.5.3：比较步骤2.5.2中的两行的输出结果值，如果两行的输出结果值不同，则这两行就是目标叶子变量的一对测试用例，将这两行以成对的形式添加到步骤2.5.1中建立的MC/DC测试用例集中；步骤2.6：将每一个叶子变量的MC/DC测试用例集合并，得到测试用例集，并最小化测试用例集；步骤三：对被测程序进行代码插桩；首先遍历抽象语法树找到插桩的位置，判断是否是插桩点，如果不是插桩点，返回继续遍历抽象语法树寻找找到插桩位置；如果是插桩点，则植入检查语句，然后直接在抽象语法树上以子树的形式植入代码的语法树片段，判断插桩是否完成，如已完成，则被测程序编译运行；如未完成，返回继续遍历抽象语法树找到插桩的位置，直至完成插桩；步骤四：构造适应度函数；步骤4.1：建立控制依赖关系适应度函数：步骤4.1.1：通过被测程序的控制流图，获得每一个判定的控制依赖关系集合；控制依赖用来描述一个目标节点y的执行关于其前面分支节点输出的依赖性，当每一条从目标节点y到出口节点e的路径都包含节点z时，称节点z被目标节点y后置控制；任意节点x，两个节点（y，x）之间可以构成一个分支路径，当每一条从目标节点y到出口节点e的通过（y，x）分支路径都包括节点z时，称节点z后置控制一个分支（y，x）；当节点z后置控制y的一个分支，且节点z不后置控制节点y，称节点z控制依赖于目标节点y，控制依赖关系是从结构关系角度衡量当前输入测试数据距离抵达目标的逼近程度，通过控制流图中目标与执行偏离条件节点间的关键节点计算得到；步骤4.1.2：建立控制依赖关系适应度函数：控制依赖关系适应度函数包含了控制依赖关系集合中各分支节点的目标函数，建立控制依赖关系适应度函数为：ControlDepFittestdata＝dependentdecisions‑executeddecisions （1）其中，dependentdecisions为目标的控制依赖关系集合中的控制节点数；executeddecisions表示以当前测试数据为输入；ControlDepFittestdata表示控制依赖关系适应度函数；如果控制依赖关系适应度函数值为0，则测试数据能够到达目标判定；如果控制依赖关系适应度函数值大于0，则测试数据在某处偏离了目标节点，通过控制依赖关系适应度函数的值，得到偏离节点divergednode；步骤4.2：建立数据依赖关系适应度函数：定义pn为问题节点，S为用来储存一个给定节点的依赖关系的集合，以pn和S作为获取数据依赖关系适应度函数方法的输入，DepSets用来储存当前搜集到的存在依赖关系的节点集合，PV用来存储问题节点使用的变量，S和DepSets被初始化为空集，获取一个节点的依赖关系适应度函数的方法为：步骤4.2.1：获取问题节点pn的控制依赖关系集合ControlDep（pn）赋给S，并将pn使用的变量UsedVariables（pn）加到PV中；步骤4.2.2：对于PV中的每一个变量pv，获取pv的最后定义集合lastDefs；（a）对于lastDefs中每一个最后定义ld，获取ld的控制依赖关系集合ControlDep（ld），并将其与S合并，得到扩展的S，然后将ld使用的变量UsedVariables（ld）添加到一个新建的PVnew中；（b）对于ControlDep（ld）中的每一个控制节点cd，获取它使用的变量UsedVariables（ld），并添加到步骤4.2.2（a）建立的PVnew集合中；步骤4.2.3：对于PV中的每一个变量pv，迭代获取PV依赖关系集S(ld)，首先获得PV中的第一个变量，获取其依赖关系集S(ld)，返回步骤4.2.2，然后获取PV中的下一个变量，直至完成PV中所有的变量，结束迭代，并将S(ld)添加到DepSets中；步骤4.2.4：建立用于定义适应度函数的依赖关系集合：定义DepFit为适应度函数依赖关系集合，对于DepSets中的每一个子集si：（a）添加si到DepFit中；（b）判断DepSets中每一个非si的子集sj，与si是否存在then、else的分支冲突，如果不存在，则合并两个子集si、sj，得到新的子集Si,j，并将Si,j添加到DepFit中；如果存在then、else的分支冲突则不能合并，将si、sj都添加到DepFit中；步骤4.2.5：建立数据依赖关系适应度函数：建立数据依赖关系集合后，用计算控制依赖关系适应度函数的方法得到数据依赖关系适应度函数；步骤4.3：建立分支适应度函数：当测试数据抵达目标时，用分支距离来度量测试数据是否满足期望测试用例，通过计算分支距离度量测试数据距离期望测试用例的逼近程度，如果测试数据到达目标判定，但是不满足任一个MC/DC测试用例，那么每一个测试数据的接近水平都为0，但分支距离不为0；如果测试抵达目标并实现一个测试用例，那么它的分支距离和接近水平都为0；计算出来的分支距离的大小用来评价哪一个测试数据更接近于满足期望的分支测试用例；步骤五：在MC/DC测试用例、适应度函数公式和执行插桩代码的基础上，随机产生测试数据，并在这些测试数据上执行插桩后的被测程序，获得适应度值，同时检验是否满足预期执行的路径；如果满足，则进入步骤七；否则进入步骤六；计算接近水平适应度函数ApproachLevelFitness，如果ApproachLevelFitness为0，则测试数据到达目标；然后在目标判定处，计算分支距离BranchFitness，如果ApproachLevelFitness和BranchFitness都为0，则测试数据达到MC/DC测试目标，否则，测试数据的适应度函数值等于ApproachLevelFitness+normalized(BranchFitness)，normalized(BranchFitness)表示对分支距离BranchFitness的标准化，具体的计算过程为：步骤5.1：按照步骤二的方法生成MC/DC测试用例预期结果集；步骤5.2：按照步骤4.1和步骤4.2的方法获得依赖关系集合，包括控制依赖集和数据依赖集；步骤5.3：针对每一个目标判定，随机生成测试数据Ta和测试数据Tb；步骤5.4：按照步骤4.1中的计算方法，根据依赖关系集合，分别计算测试数据Ta和测试数据Tb的控制依赖适应度函数和数据依赖适应度函数；步骤5.5：按照步骤4.3中的计算方法，分别计算测试数据Ta和测试数据Tb的分支距离；步骤5.6：进行分支距离的标准化BranchFitness(Ta)normalised，计算公式为： <mrow> <mi>BranchFitness</mi> <msub> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mi>a</mi> </msub> <mo>)</mo> </mrow> <mi>normalised</mi> </msub> <mo>=</mo> <mfrac> <mrow> <mi>BranchFitness</mi> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mi>a</mi> </msub> <mo>)</mo> </mrow> </mrow> <mrow> <mi>BranchFitness</mi> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mi>a</mi> </msub> <mo>)</mo> </mrow> <mo>+</mo> <mi>BranchFitness</mi> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mi>b</mi> </msub> <mo>)</mo> </mrow> </mrow> </mfrac> </mrow>其中，BranchFitness(Ta)表示测试数据Ta的分支距离，BranchFitness(Tb)表示测试数据Tb的分支距离；步骤5.7：总适应度函数值Fitness(T)为：Fitness(T)＝ApproachLevelFitness(T)+BranchFitness(T)normalized其中，ApproachLevelFitness(T)表示测试数据T的接近水平适应度函数；BranchFitness(T)normalized表示测试数据T的分支距离的标准化值；步骤5.8：根据总适应度函数值比较这两个测试数据哪个更接近于达到判定目标；步骤5.9：若ApproachLevelFitness和BranchFitness都为0，则测试数据达到MC/DC测试目标，进入步骤七，否则，进入步骤六；步骤六：根据得到的适应度值，使用遗传算法的选择、交叉、变异等遗传操作，生成新的测试数据，并返回步骤五，计算新生成的测试数据的适应度值；步骤6.1：选择编码策略，把参数集合X和域转换为位串结构空间S；采用整型和实型混合的方式编码染色体，问题的参数直接转换为染色体上的基因，参数的个数转换为染色体长度，各参数的取值区间映射为各基因的取值范围，具体过程如下：设求解问题包含n个输入变量X1,X2,...,Xn，首先，用等价类划分和边界值分析方法处理参数的值域，其中Yi(1≤i≤n)表示参数Xi(1≤i≤n)可以取值的有限离散点的集合，|Yi|表示集合的大小，建立问题解空间和染色体空间的映射关系，染色体表示为：X＝(X1,X2,...,Xn)→C＝(C1,C2,...,Cn) （2）其中，C为染色体空间解空间中的解，X为问题空间的解；步骤6.2：设计和选择遗传操作，包括种群大小，选择、交叉、变异方法，以及确定交叉概率pc和变异概率pm等遗传参数；步骤6.2.1：执行排序选择策略和精英保留策略：执行排序选择策略的具体过程为：（a）根据适应值的大小，降序排列种群中的所有个体；（b）设计概率分配表，根据适应值大小，升序分配每个个体的概率值；（c）每个个体被遗传到下一代的概率由步骤（b）中分配的概率值决定，再基于这些概率值，用轮盘赌选择法选择被淘汰和被复制的染色体；经过一轮排序选择策略后，会得到一个新的种群，然后在这个新的种群基础上再执行精英保留策略，具体过程为：（a）根据适应度函数值的大小从经过排序选择策略后得到的新种群即当前种群中获取最佳个体和最差个体；（b）如果当前种群的最佳个体的适应度高于此前获得的出现的最佳个体的适应度，则用当前群体的最佳个体替换此前出现的最佳个体；（c）保持迄今出现的最佳个体状态不变，将其完整的遗传到下一代种群中；步骤6.2.2：交叉操作和变异操作采用自适应的交叉概率pc和变异概率pm，根据群体平均适应值及当前群体最优个体适应值来自动调整交叉概率pc和变异概率pm；fmax表示某一代种群中最优个体的适应度，Favg表示该代群体的平均适应度，最优个体的适应度与该代群体的平均适应度的差值Δ＝fmax‑Favg，则当Δ越小，表示种群个体之间的适应度差别越小，说明种群此时达到局部最优的可能性较大，过早收敛的可能性也越大；当Δ越大，表示个体之间的适应度差别越大，交叉概率pc和变异概率pm由Δ来决定，pc和pm的计算公式为：pc＝k1/Δ （3）pm＝k2/Δ （4）其中，k1和k2分别为交叉概率调整系数和变异概率调整系数；步骤6.3：随机初始化生成种群P；步骤6.4：计算种群P中个体位串解码后的适应度值；步骤6.5：按照遗传策略，将步骤6.2中设计的各遗传操作作用于种群，经过选择、交叉和变异后，形成了新一代种群；步骤6.6：带着新产生的染色体即测试数据返回步骤五，计算其适应度值，判断其性能是否满足指标，或者是否已完成预定迭代次数，若不满足并且没有完成迭代次数，则进入步骤6.1，遗传算法从编码操作开始，对新产生的种群重新进行选择复制、交叉和变异，不断迭代；若满足指标或已完成迭代次数则直接进入步骤七；步骤七：运行结束，得到合适的测试数据。 |
