Page 198 - 《软件学报》2025年第10期

郑炜 等: 基于抽象语法树变异的漏洞样本生成方法 4595

文选择 Eclipse CDT 作为抽象语法树的生成工具, 并针对 Eclipse CDT 生成的抽象语法树的节点存储问题进行了
优化.
2) 抽象语法树的变异. 本文通过对 UAF 到 CUAF 两种漏洞之间的演化规律进行研究得出了 5 种包含漏洞特
征的变异算子. 将这 5 种变异算子和 5 种普通变异算子组合在一起, 研究他们在抽象语法树层面的变异规则和变
异方式, 最终实现在抽象语法树层面的变异.
3) 变异策略的优化. 无效样本指的是在变异过程中生成的样本中, 不满足目标条件或者不包含期望的特征的
样本. 由于传统模糊变异测试在使用变异算子变异时采用随机变异的方式, 生成的无效变异体比较多, 效率低. 本
文提出一种根据关联度来对不同变异算子的执行频率进行选择的算法 MOPSG. 该方法的核心是根据每个变异算
子权重动态调整变异算子执行次数和顺序, 找到最佳的变异算子执行次序后进行抽象语法树级别的变异, 从而针
对某一漏洞模式推断出其漏洞演化路径, 满足在产生尽可能少的样本量的情况下涵盖漏洞样本. 在该方法的基础
上对执行变异策略过程中通过采用固定关键算子顺序、部分子树截断两个启发式方法对变异顺序和次数进行限
制, 有效降低无效变异样本数量.
2.1 基于抽象语法树的漏洞样本生成方法
本节首先对 Eclipse CDT 工具生成的抽象语法树进行深入分析, 研究其结构和使用所存在的问题, 针对这些
问题对抽象语法树进行优化. 然后对 UAF 漏洞和 CUAF 漏洞之间的演化规律进行总结得出 5 种漏洞特征相关的
变异算子, 再加上模糊变异中的 5 种普通变异算子一共 10 种变异算子. 根据这 10 种变异算子的变异规则, 对抽象
语法树进行不同的变异操作, 最终生成变异体. 整体工作流程如图 3 所示.

逻辑转化

谓词集合 变异算子集合
抽象语法树集合 变异优化 变异样本集合
AST生成
和优化
源代码切片 抽象语法树集合
图 3 抽象语法树变异和优化流程

2.2 基于 Eclipse CDT 抽象语法树的优化

由于使用 Eclipse CDT 无法直接生成抽象语法树文本, 而是得到经过解析后的编译单元 IASTTranslationUnit,
这个编译单元中包含了解析源程序过后的全部信息, 不仅仅包括语法树, 还有注释信息、头文件、偏移量等其他
信息, 这些信息对后面抽象语法树的节点分析和变异没有作用, 还占用语法树的存储空间. 另外, IASTTranslation-
Unit 编译单元获取子节点的方式为 IASTNode[] children = node.getChildren(), 从代码中可以看出, 一个 node 节点
通过 getChildren 方法获取它的子节点, 而其子节点的存储方式为对象数组 IASTNode[], 使用这种存储方式来对节
点进行插入删除操作需要移动大量数组元素, 在变异的过程中效率比较低. 本文针对以上问题, 设计了一种方法来对
原本编译单元里节点存储结构进行优化, 每个节点除了保存原抽象语法树节点中的全部语法信息外, 再分配一个
抽象语法树中唯一的数字标志值用于变异时对节点进行定位, 最后将各节点存储到链 4 式结构的抽象语法树中.
对 Eclipse CDT 抽象语法树的具体优化过程如算法 1 所示, 在执行算法之前会自定义一个节点结构, 包括节
点 id, 节点名 name, 节点值 value 以及一个子节点列表 sonList. 该优化算法的输入抽象语法树 T, 输出为抽象语法
树 T′, 算法中主要包括了 3 个方法, 第 1 个是 setNode 方法, 该方法是将原抽象语法树的节点作为输入参数, 通过
节点获取到节点名 NodeName 和节点值 NodeValue, 根据节点名和节点值生成一个节点 id, 最后将这 3 个值输入
到新的节点结构中并返回一个新节点 (算法中 1–7 行). 第 2 个方法为 getTree, 该方法是对编译单元 IASTTransla-
tionUnit 的根节点下的子节点进行深度优先遍历, 对遍历访问到的每一个正常节点, 首先获取该节点的子节点列
表, 作为下一次深度优先遍历的输入, 然后对该节点使用 setNode 方法获取一个新节点, 将新节点 newNode, 根节
点 rootNode, 以及当前节点的父节点 curNodeFatherId 都输入到 insert 方法中来构建新的抽象语法树, 当所有节点