Page 253 - 《软件学报》2025年第10期
P. 253

4650                                                      软件学报  2025  年第  36  卷第  10  期


                 收集  MDP  交互后的累积奖励      ∆r, 则“灵敏度”的计算公式为:

                                                               |r −∆r|
                                                     Sensitivity =                                    (1)
                                                               ∥∆s∥ 2
                 其中, r 是不添加扰动时的累积奖励. “灵敏度”越高, 表示所选种子触发失效事故的可能性越高. 每轮测试首先选择
                 尚未测试的“灵敏度”最高的种子, 然后根据原始数据的类型将随机噪声添加到初始状态来施加突变, 例如, 将                              N(0, 1)
                 的高斯浮点数添加到       ADS  环境中车辆的初始位置. 随机变异同时还要满足一些简单的约束, 以确保变异的初始状
                 态是有效的和可解的       (例如, 一开始不会发生事故). 变异后的状态作为初始状态输入待测试的算法模型.
                  3.2.2    反馈分析算法
                    反馈分析的目的是识别可能暴露新覆盖模式                 (譬如软件测试中的探索路径) 的新种子, 回馈给模糊测试以发
                 现更多的缺陷. 在离散的深度神经网络            (deep neural network, DNN) 的模糊测试中, 通行的方法是度量给定输入在
                 DNN  中的神经元覆盖度. 但对于连续决策模型, 其中策略学习模型都是黑盒子, 这个方法是不适用的. IIFuzzing
                 考虑状态序列的差异性和累积奖励, 作为判断某序列的初始状态是否加入种子库的依据. 我们参考                               MDPFuzz 提出
                 基于概率密度的状态新鲜度          (Freshness) 度量算法  [9] . Freshness 的工作原理是首先根据现有的状态序列估计一个
                 概率密度函数, 然后将新的状态序列与现有序列进行比较, 再根据概率密度函数计算新序列的密度. 如果新序列的
                 密度较低, 则表明它没有被现有序列覆盖. 也就是说, 低密度表示高新鲜度, 即由该变异种子派生的状态序列和之
                 前的状态序列越不同, 也意味着该变异种子应该加入种子库. 此外, 累积奖励越高表明模型完成任务的可能性越
                 高, 相反累积奖励越低则表示该序列触发失效事故的可能性较高, IIFuzzing                   综合考虑两个指标将越不同          (高新鲜
                 度) 且越容易触发失效事故        (低累积奖励) 的序列的初始状态作为新种子加入种子库.
                    在我们的实验环境中, 仅通过上述基础的模糊测试框架生成的测试序列大都不能触发失效事故                                  (详情见第
                 4.5.4  节的结果分析). 这是因为在测试过程中         MDP  过程是一个黑盒子, 且初始种子变异具有局限性, 导致无法大
                 量稳定地生成具有挑战性的测试场景. 为解决该问题, 我们提出了惰性序列预测模型.
                  3.3   惰性序列预测模型
                    既然很多测试序列都不会触发失效事故, 那么我们是否可以打破                      MDP  的黑盒子, 提前预判后续测试动作触
                 发失效事故的可能性, 中止那些不太可能触发失效事故的测试序列                      (称为惰性序列) 呢? 为此, IIFuzzing   构建了一
                 个惰性序列预测模型        InertS-Pred. IIFuzzing  设置一个干预时间点  (参见第  3.4  节), 然后在该时间点, InertS-Pred  分
                 析已产生的状态序列, 预测该序列是否为惰性序列. InertS-Pred            主要包括    3  部分.
                  3.3.1    状态序列归一化表示
                    从  MDP  得到的状态序列是一种高维数据, 其形式为            t×s 的多变量时间序列. 由不同长度的多个时间步的状态组
                 成, 每个时间步的状态都是        s 维向量. 我们采用无监督和可扩展的表示学习方法              [35,36] , 构建了一个可扩张卷积的深度
                 卷积神经网作为本方法的表示学习模型, 该模型可以将不固定长度的高维数据表示转化为固定维数的向量. 我们用数
                 据训练该模型, 在    t 时刻, 将该时刻前的状态序列       {s 0 , s 1 ,..., s t−1 } 输入训练好的表示学习模型, 得到归一化的向量表示.
                  3.3.2    基于密度聚类状态序列
                    显然, 任何一款有质量的软件或者算法, 其成功的概率都是远远大于失效的概率. 对基于                           MDP  的连续决策算
                 法, 仿真测试时, 成功完成任务的轮次也是远远大于失效的轮次. 社会学上有一种普遍的观点, 认为“成功大都相似,
                 失败却各有理由”, 我们的基本假设是: 成功完成任务的状态序列可能呈现相似的模式且聚集在高密度区域, 触发失
                 效事故的序列则呈现明显不同的模式且分布在低密度的外围边界区域. 我们分析了不同测试环境下状态序列在干
                 预点时的密度聚类分布情况, 其结论也很好地印证了上述假设                    (详情见第   4.5.4  节的结果分析). 基于此, 我们使用基
                 于密度的状态序列聚类算法, 利用分层密度空间聚类方法                  (hierarchical density-based spatial clustering of applications
                 with noise, HDBSCAN) [37] 对上一步得到的状态序列的归一化表示进行聚类. 我们基于现有的算法包开发了该模块.
                    IIFuzzing  的目标是尽可能早地预测出可能触发失效事故的序列. 我们首先利用历史数据                       (带有是否触发事故
                 的标签) 训练模型, 通过在不同时间步的历史状态序列数据拟合以确定每个聚类中的最小成员数和最优干预点. 关
                 于干预点选择的细节见第         3.4  节.
   248   249   250   251   252   253   254   255   256   257   258