1.一种结合关键点概率与路径相似度的多路径覆盖方法，其特征在于，包括以下步骤：步骤一，基于关键点路径获取被测程序的理论路径；随机生成测试数据集，运行被测程序，得到该数据集对应的覆盖路径并定义为易覆盖路径；通过不可达路径自动检测模型探测到的路径，定义为不可达路径；将剩余理论路径，定义为难覆盖路径；根据生成的易覆盖路径，计算路径中关键点的关键点概率，将难覆盖路径作为目标路径，生成覆盖难覆盖路径的测试数据；

步骤二，统计易覆盖路径中的关键点被覆盖情况，计算关键点概率以及个体对生成覆盖目标路径测试数据的贡献度；将个体贡献度作为适应度函数权重，调整多种群遗传算法的适应度函数；根据关键点概率对目标路径进行排序，排序后优先级高的目标路径对应的子种群在测试数据生成过程中优先执行；

步骤三，利用多种群遗传算法生成覆盖目标路径的测试数据；采用个体信息共享策略，实现各子种群之间的信息交互，但各子种群的个体不参与其它子种群的进化；子种群覆盖其目标路径后，继续尝试覆盖与该目标路径相似度高的其它目标路径，以提高种群中的个体信息的利用率；

步骤四，多路径覆盖测试数据生成；采用改进的多种群遗传算法，对选出的多条目标路径，求解覆盖这些路径的测试数据；

其中，步骤一中的所述关键点概率的计算步骤如下：

对被测程序输入m组测试数据in=(l1,l2, lm)，其中li，1≤i≤m为一组输入向量，为种群中的个体，得到m条覆盖路径集Pcover={P1,P2,…,Pm}，程序中每个分支子关键点Nj，1≤j≤n被路径覆盖的概率，记为G(Nj)；

利用随机生成的测试数据集，及其对应的易覆盖路径，统计易覆盖路径集中的关键点被路径覆盖的情况，如式(1)所示： (1)

其中，Pi∈Pcover，再得到覆盖矩阵，记为Cover，如式(2)所示： (2)

其中，覆盖矩阵的行表示执行被测程序得到的m条覆盖路径P1,P2,…,Pm，列表示路径中的n个关键点N1,N2,…,Nn；

根据覆盖矩阵Cover，得到覆盖关键点Nj的路径数记为Sj，如式(3)所示： (3)

被测程序的关键点概率G(Nj)，表示如式(4)所示：

(4)

由式(4)可知，关键点被易覆盖路径覆盖的次数越多，关键点概率越高，表示该关键点越容易被覆盖；

步骤二中的所述个体贡献度的计算步骤如下：

个体数为m的种群中的个体li，1≤i≤m，对于进化生成覆盖目标路径集Ptar={P1,P2,P3,…,Pn}的目标路径Pk，1≤k≤n的测试数据所做出的贡献，即为个体li对应的覆盖路径P(li)与目标路径Pk相同关键点的关键点概率之和，记为Con (li,Pk)；

根据关键点概率，将个体的贡献度Con (li,Pk)表达成如式(5)所示： (5)

其中，e为自然底数，Nj∈(P(li)∩Pk)，G(Nj)为Nj的关键点概率；

在多种群遗传算法进化过程中，一个关键点的关键点概率越高，则该关键点越容易被易覆盖路径覆盖；当个体li对应的覆盖路径P(li)与目标路径Pk相同关键点的关键点概率越高，表示该个体对于生成难覆盖的目标路径所能做出的贡献越低；则关键点概率与个体贡献度之间的关系成反比；

步骤三中的所述适应度函数的计算步骤如下：

个体数为m的种群中的个体li，1≤i≤m的适应度函数由其层接近度、分支距离及个体贡献度组成的，记为F(li)；

个体li的层接近度为li对应覆盖路径P(li)与目标路径集Ptar={P1,P2,P3,…,Pn}中的目标路径Pj，1≤j≤n相同的关键点个数，除以路径Pj的关键点数，记为approach_level(li,Pj)；个体li的分支距离参考已有的分支谓词的分支距离计算函数及复合谓词的计算方法，记为branch_distance(li,Pj)；为了权衡分支距离与层接近度的大小，并统一为最大化运算，将分支距离规范化表示为 ；个体li对于目标路径Pj的贡献度Con(li,Pj)作为适应度函数的权重；适应度函数F(li)表达成如式(8)所示： (8)

对于目标路径集Ptar={P1,P2,…,Pn}中的每条路径Pj，1≤j≤n，对被测程序输入一组测试数据lj=(sj1,sj2,…,sjm)能够覆盖路径Pj时，目标函数fj= F(lj)取得最大值；多路径覆盖问题要求寻找至少k个测试数据，使其能够分别覆盖这k个目标路径，则问题转化成求解f1,f2,…,fk最大值的优化问题，f1,f2,…,fk最大值的优化如式(9)所示： (9)

其中，Pj∈Ptar；

各个目标函数都对应一条目标路径，目标函数之间相互独立，对于每个目标函数对应于一组测试数据；多路径覆盖问题的最终数学模型表达式如式(10)所示： (10)

在式(10)中，最终数学模型由k个函数构成，每个函数对应一个优化问题，每个优化问题对应一个覆盖目标路径的测试数据；

步骤三中的所述个体信息共享的具体步骤如下：

对于种群集pop={pop1,pop2,…,popn}，第I，1≤I≤n个子种群popI={lI1,lI2,…,lIm}中的个体lIJ，1≤J≤m，首先判定个体lIJ，1≤J≤m是否为对应适应度函数max(FI)的最优解，然后判断个体lIJ，1≤J≤m是否为其它子种群对应适应度函数max(Fk)，1≤k≤n且k≠I的最优解，在判断个体lIJ，1≤J≤m是否为max(Fk)的最优解时，只需判断个体lIJ穿越的路径P(lIJ)是否为目标路径Pk，不需要计算Fk(lIJ)，即个体lIJ，1≤J≤m不参与子种群popk的进化过程，个体不在多个子种群间进行迁移，只进行信息共享；

步骤三中的所述路径相似度的计算步骤如下：

目标路径集Ptar={P1,P2,P3,…,Pn}中的目标路径Pj，1≤j≤n与目标路径Pk，1≤k≤n且k≠j相同的关键点个数，与路径Pj，Pk的最大关键点个数之比，记为Pro(Pj,Pk)；

统计目标路径Pj与目标路径Pk关键点异同情况，如式(6)所示：

(6)

其中，Nji为路径Pj的第i个关键点，Nki是为路径Pk的第i个关键点；

根据路径相同序列长度，可以得到路径相似度Pro(Pj,Pk)，如式(7)所示： (7)

其中，len(Pj)表示路径Pj的关键点个数，len(Pk)表示路径Pk的关键点个数，max(len(Pj),len(Pk))表示路径Pj及路径Pk较大关键点个数。

2.如权利要求1所述的结合关键点概率与路径相似度的多路径覆盖方法，其特征在于，步骤四中的所述多路径覆盖测试数据生成的具体步骤如下：步骤4‑1，对被测程序进行插桩处理，初始化参数，包括子种群数n，子种群中个体数m，终止代数，种群进化需要的选择、交叉和变异概率值，并采用二进制格式编码个体；

步骤4‑2，完成改进的多种群进化；

步骤4‑3，若目标路径P被全部覆盖，则表明算法完成任务，终止程序执行，或种群进化代数超出阈值。

3.如权利要求2所述的结合关键点概率与路径相似度的多路径覆盖方法，其特征在于，步骤4‑2中的所述改进的多种群进化的具体步骤如下：步骤4‑2‑1，对任意属于排序后的目标路径集Ptar={P1,P2,P3,…,Pn}的目标路径Pi，随机生成个体数为m的子种群popi，对第i个种群popi，计算该种群中个体覆盖第i条路径的适应度值的最大值max(Fi(ini))，如果存在个体的适应度值达到最大值，说明该个体覆盖目标路径Pi，将Pi从目标路径集中移除，若不是则对该种群执行选择、交叉、变异遗传操作；

步骤4‑2‑2，popi中个体除了判定是否是yi=max(Fi(ini))的最优解，还需要判定是否是yk ，k≠i的最优解，如果popi中个体能够覆盖第k条目标路径，则popk终止；

步骤4‑2‑3，当i≠n时，popi需要继续对与该子种群对应的目标路径Pi的相似路径尝试覆盖，如果找到覆盖第j，j≠i& j>i条路径的个体，将popj及路径Pj移除，直到完成尝试对所有相似目标路径覆盖后，终止popi的执行。

4.一种结合关键点概率与路径相似度的多路径覆盖的系统，其用于实现如权利要求1‑

3任一项所述的结合关键点概率与路径相似度的多路径覆盖方法，其特征在于，该系统包括：关键点路径获取模块，用于将理论路径分类为易覆盖路径、难覆盖路径和不可达路径，并根据易覆盖路径的计算路径中的关键点概率；

计算关键点概率和个体对生成覆盖目标路径测试数据贡献度模块，首先利用个体贡献度作为适应度函数权重，调整多种群遗传算法的适应度函数，并根据关键点概率对目标路径进行排序，在此后的模块中，应当优先执行排序后优先级高的目标路径对应的子种群；

生成覆盖目标路径的测试数据模块，用于利用个体信息共享策略，实现各子种群之间的信息交互，并在子种群覆盖其目标路径后，仍继续尝试覆盖与该目标路径相似度高的其它目标路径；

多路径覆盖测试数据生成模块，用于利用改进的多种群遗传算法，对选出的多条目标路径，求解覆盖这些路径的测试数据。

5.如权利要求4所述的结合关键点概率与路径相似度的多路径覆盖的系统，其特征在于，所述关键点包括分支关键点、分支子关键点、普通关键点、起始关键点s及终止关键点e，分支关键点对应控制流图中有两个直接后继节点的节点；分支关键点的两个直接后继节点为分支子关键点；普通关键点既是分支关键点，也是其它分支关键点的分支子关键点；所述关键点路径采用被测程序的分支子关键点进行描述：关键点路径P={s,N,e}，其中N={N1,N2,…,Nn}为分支子关键点集合，s为起始关键点，e为终止关键点；所述关键点路径表达式是将关键点图中所有关键点用数学运算符连接起来的表达式，其中,兄弟关键点之间表示为相加的“或”关系，普通关键点与其分支子关键点之间表示为相乘的“与”关系。