基于语句占优关系和两阶段遗传算法的高阶变异测试方法

摘要

本发明公布了一种基于语句占优关系和两阶段遗传算法的高阶变异测试方法，目的是提高高阶变异测试的有效性和质量。首先，基于程序的占优关系树，来确定高阶变异的语句选择问题，从而保障位于同一个高阶变异体中的所有变异语句都被执行；然后，建立所需的目标函数，对高阶变异体的优劣进行度量；最后，设计了一种包含两个交替进化过程的遗传算法来生成高质量的高阶变异体，从而揭示程序所包含的复杂缺陷。该方法不但可以减少高阶变异体的数量，还可以保证高阶变体具有好的性能，对提高高阶变异测试的有效性和可行性具有重要意义。

主权项

一种基于语句占优关系和两阶段遗传算法的高阶变异测试方法，其特征在于如下步骤：步骤1：提出基于语句占优关系的变异语句选择方法，保障位于同一个高阶变异体中的所有变异语句都被执行；步骤2：给出一种新的高阶变异体评价方法，保障生成的高阶变异体比起低价变异体具有更好的检错能力；设T是一个已有测试数据集，是按照步骤1所选择的变异语句，那么令则Z是T的一个子集，且Z所包含的测试数据能够覆盖所有的变异语句；利用Z所包含的测试数据对高阶变异体的性能进行评价；设是对语句进行变异得到的一阶变异体，M_k是组合在一起得到的k阶变异体；令kill_Z{M}表示Z中能够杀死M的测试数据所构成的集合；定义M_k的适应度如下:该公式的含义为：高阶变异体的适应度为杀死该高阶变异体的测试数据的个数与杀死构成该高阶变异体的一阶变异体的个数的比值；由定义，一个高阶变异体的适应值落在区间[0,+∞)上；当适应值大于1时，该高阶变异体比一阶变异体更容易被杀死，因此，对测试没有任何价值；当高阶变异体的适应值从1变化到0时，其性能逐步提高；如果高阶变异体的适应值为0，就将其看做等价变异体；步骤3：设计了一种包含两个交替进化过程的遗传算法，来生成高质量的高阶变异体，从而揭示程序所包含的复杂缺陷；所述包含两个交替进化过程的遗传算法，包括以下步骤：步骤3.1：个体表示方法在遗传算法中，所求问题的一个可能解称为一个个体；个体是指高阶变异体；为了准确表示一个高阶变异体，需要确定变异语句和变异算子；(1)变异语句表示方法设变异路径为P，P包含m条语句，分别记为s₁,s₂,…,s_m；从s₁,s₂,…,s_m中选出k条语句进行变异，其中k≥2,从而生成一个高阶变异体；定义一旦选定k条语句进行变异，则可得到一个(0,1)字符串(λ₁,…,λ_m)，使得另一方面，如果并且则用字符串(λ₁,…λ_m)来表示选择语句来进行变异；(2)变异算子表示方法假设每个变异语句都有n个变异算子可供选择，定义：γ_i＝j,如果第i个变异语句选择了第j个变异算子，则可得到一个长为k的向量(γ₁,…,γ_k)，代表k个变异语句分别使用第γ₁,…,γ_k个变异算子进行变异；如果不同语句使用的变异算子的个数不同，那么采用合理的方法进行转化；记Γ＝(γ₁,…,γ_k)，则用表示通过对语句分别实施第δ₁,…,δ_k个变异算子所生成的k阶变异体M_k；也记M_k＝(λ₁,…,λ_m|δ₁,…,δ_k)；步骤3.2：进化算子设计方法每个个体能够分为两个完全不同的部分，所述步骤3.2设计了两个相互交替的进化过程，分别实现个体不同部分的进化；两个进化过程的区别主要体现在实施交叉和变异算子的部位和策略不同，而选择算子并没有本质区别；(1)选择算子采用轮盘赌方法进行个体选择，并使用贪心策略；首先，根据适应值选择5％的个体直接进入下一代种群；同时，把这部分个体投入交叉池；然后，采用轮盘赌策略再选择50％的个体进入交叉池；(2)交叉算子采用单点交叉算子对个体进行交叉；首先，随机选择交叉点；然后，让该交叉点前或后的两个个体的部分结构进行互换，并生成两个新个体；第一个阶段：该阶段对个体第一部分进行交叉；设：为两个个体；随机选择一个交叉点，记为c₁，其中1≤c₁≤m‑1；让个体individual⁽¹⁾和individual⁽²⁾的第一部分在第c₁个基因位后进行交叉，从而生成两个新的个体：需要说明的是，如果或者那么individual⁽³⁾或者individual⁽⁴⁾将不能表示k阶变异体；在这种情况下，需要对个体进行修正；假设(λ₁,…,λ_m|δ₁,…,δ_k)是一个个体；如果λ₁+…+λ_m<k，那么将(λ₁,…,λ_m)中最前面的(λ₁+…+λ_m)‑k个字符1改为0；反之，如果λ₁+…+λ_m>k，则将(λ₁,…,λ_m)中最前面的 k‑(λ₁+…+λ_m)个字符0改为1；这样，则可以保证(λ₁,…,λ_m|δ₁，…,δ_k)是k阶变异体；第二个阶段：该阶段对个体第二部分进行交叉；设：为两个个体；随机选择一个交叉点，记为c₂，其中1≤c₂≤k‑1；让个体individual⁽¹⁾和individual⁽²⁾的第二部分在第c₂个基因位后进行交叉，从而生成两个新的个体：(3)变异算子采用单点变异算子对个体进行变异；首先，随机选择一个变异点；然后，用一个新的值替换该变异点的值，从而得到一个新个体；第一个阶段：该阶段对个体第一部分进行变异；设：individual＝(λ₁,…,λ_m|δ₁,…,δ_k)是一个个体；随机选择一个变异点，记为c₁，其中1≤c₁≤m，如果个体individual第一部分第c₁个基因位的值是1，则变为0；如果是0，则变为1，从而生成一个新的个体；第二个阶段：该阶段对个体第二部分进行变异；设：individual＝(λ₁,…,λ_m|δ₁,…,δ_k)为一个个体；随机选择一个交叉点，记为c₂，其中1≤c₂≤k，让个体individual第二部分第c₂个基因位的值随机替换为中的某个值，从而生成一个新的个体；步骤3.3：算法终止条件本算法的终止条件包含两方面内容：一是针对每条占优路径运行遗传算法的的终止条件，二是针对整个被测程序搜索过程的终止条件；针对每条占优路径运行遗传算法的的终止条件当前进化达到一定代数；针对整个被测程序搜索过程的终止条件是所有占优路径都得到遍历。