Page 137 - 《软件学报》2025年第5期
P. 137

孙百才 等: 代理辅助多任务进化优化引导的             MPI 程序路径覆盖测试用例生成                              2037



                                   ∗                        NumPath  表示基本目标路径数. 关于表         1  中的每一被测
                 本目标路径集为      B = {P |np = 1,2,...,NumPath}  , 其中,
                                   np
                 MPI 程序, 得到的基本目标路径集包括相应            MPI 程序中的所有分支和语句. 鉴于此, 当将所提方法应用于测试每
                 一被测   MPI 程序的基本目标路径集时, 得到的实验结果将会令人信服和具有可扩展性.
                    为更好地理解拉丁超立方采样, 这里给出使用该采样方法的原因和工作原理, 其中, 原因为拉丁超立方采样能
                 够高效地生成样本, 这些样本均匀分布于多维决策空间的超立方体中, 且无需获知决策空间确切的概率分布. 工作
                 原理为: (1) 假设决策空间有      A  个维度, 则将每个维度划分为        B  个子区间; (2) 在每维度决策空间的每一子区间内
                 随机采样一个值, 用于组成一个子区间采样集合; (3) 在每一子区间采样集合中不放回抽取一个值, 用于组成一个
                 样本, 直至每一子区间采样集合变为空集.
                    考虑到文献     [17] 使用拉丁超立方体采样获得了         50  个测试输入, 并证明这些数量的测试输入能够满足               MPI 程
                 序输入域的均匀分布特性. 鉴于此, 本文设置           InSize=50. 此外, 为设置代理模型更新阈值      UpdGen , 这里将沿用文献   [29]
                                               UpdGen = 20 , 也就是说, 当每一优化任务中种群进化         20  代数后, 将更新相
                 中所设定的代理模型更新阈值, 即设定
                 应的代理模型.
                    在每一测试用例生成优化任务中, 需要基于进化算法来求解相应的优化模型. 考虑到差分进化算法                               (differential
                 evolution, DE) 具有结构简单、容易实现、收敛快速、鲁棒性强等优点, 且在国际演化计算竞赛中, 差分进化算法
                 被证明是速度最快的进化算法           [37] , 因此, 本文采用  DE  来求解每条目标子路径对应的优化模型. 针对差分进化算
                 法  DE  的参数设置, 这里沿用文献      [38] 中设置的相关参数, 主要包括: 种群规模为          100, 最大进化代数    MaxGen 等于
                 1 500, 缩放因子和交叉概率分别为        0.5  和  0.9.
                    为了验证    RQ1  到  RQ2, 本文使用了以下两个指标: 路径覆盖率和时间消耗. 路径覆盖率反映了有效性, 是指当
                 使用所提方法或对比方法生成覆盖基本目标路径集合的测试用例时, 生成的测试用例所覆盖的目标路径数与目标
                 路径总数的比率. 时间消耗反映了效率, 效率是指在应用所提方法或对比方法生成覆盖基本目标路径集合的测试
                 用例时, 花费的时间或达到最大进化代数的时间. 显然, 路径覆盖率越高, 方法的时间消耗越低, 该方法就越有利.
                 为了减少随机因素对所提出方法或对比方法性能的影响, 每个方法对每一被测                           MPI 程序的基本目标路径集独立
                 运行  20  次. 注意, 每次运行所提方法或对比方法的任务是生成期望的测试用例集, 该用例集能够覆盖每一被测
                 MPI 程序的基本目标路径集.
                    当分别使用所提方法与对比方法生成期望的测试用例时, 会得到两组指标值. 考虑到                           Welch’s t-test 对于两组
                 指标值数目不等、两组指标值方差不同等情况下的均值检验都很稳健, 而对于两组指标值方差相等的情况下也可
                 以与  Student’s t-test 输出一样的结果, 因此, 我们采用    Welch’s t-test 来检验解析这两组指标的均值是否有显著差
                 别, 并取显著性水平为      0.05. 如果  P  的值小于  0.05, 那么, 所提方法与对比方法具有明显差别.

                 3.4   实验结果与分析
                    (1) 验证  RQ1
                    为了验证    RQ1, 我们分别运行本文所提方法和          Approach-SingTask, 以生成覆盖每一被测程序的基本目标路径
                 集的期望测试用例, 并计算        20  次运行的平均路径覆盖率和平均时间消耗. 表             2  列出了这两种测试用例生成方法的
                 实验结果. 该表中, 第     1  和第  2  行是平均路径覆盖率; 第     3  行是两种方法的平均路径覆盖率百分比差异, 由              u −u
                                                                                                     ∗
                          ∗  u 分别是所提方法和                      的平均路径覆盖率; 第         和第   行是这两种方法的平均
                 计算, 其中   u  和                Approach-SingTask                4     5
                 时间消耗; 第   6  行是平均时间消耗的约减率, 其由         (v−v )/v×100% 计算, 其中  v  和   分别是所提方法和     Approach-
                                                                                v
                                                           ∗
                                                                             ∗
                 SingTask  的平均时间消耗.
                    由表  2  的第  1–3  行可知: (1) 对于  7  个被测  MPI 程序, 所提方法和  Approach-SingTask  的平均路径覆盖率的平
                 均值分别为    87.9%  和  72.2%; (2) 对于所有被测程序, 提出方法和     Approach-SingTask  的平均路径覆盖率的平均百
                 分比差为   15.7%. 以上数据表明, 基于多任务进化优化的测试用例生成可以显著提高路径覆盖率.
                    从表  2  的第  4–6  行可以看出: (1) 对于  7  个被测  MPI 程序, 所提方法和   Approach-SingTask  的平均时间消耗的
                 平均值分别为     81 165.8 min  和  130 994.6 min; (2) 面向所有被测  MPI 程序, 使用所提方法和  Approach-SingTask, 平
   132   133   134   135   136   137   138   139   140   141   142