(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210284682.8 (22)申请日 2022.03.22 (71)申请人 南京大学 地址 210023 江苏省南京市栖霞区仙林大 道163号 (72)发明人 张天　潘敏学　陈佳一　 (74)专利代理 机构 南京知识律师事务所 32 207 专利代理师 张苏沛 (51)Int.Cl. G06F 8/41(2018.01) G06F 8/30(2018.01) G06F 40/30(2020.01) (54)发明名称 基于c和c++软件的依赖结构的文件特征表 示方法 (57)摘要 本发明公开一种基于c和c++软件的依赖结 构的文件特征表示方法， 该方法包括文件依赖图 提取、 随机游走采样和模型训练三个步骤： 使用 clang和llvm分析技术， 构造c和c++软件的层 次 化的文件依赖图； 使用随机游走策略， 在文件依 赖图上采集节点序列集合； 构造图表示学习模 型， 并基于节点序列集合对模型进行训练， 从而 获得文件的特征表示。 本方法基于依赖分析技术 和图表示学习技术， 可以充分提取局部图结构信 息， 并生成文 件的特征向量。 权利要求书2页 说明书6页 附图2页 CN 114610321 A 2022.06.10 CN 114610321 A 1.一种基于c和c++软件的依赖结构的文件特征表示方法， 其特征在于， 所述方法包含 如下步骤： 步骤1)， 使用clang和l lvm分析技术， 构造c和c++软件的层次化的文件依赖图； 步骤2)， 使用有偏的随机游走策略， 在文件依赖图上进行节点序列采样， 得到文件节点 序列集合； 步骤3)， 构造图表示学习模型， 并基于节点序列集合对模型进行训练， 从而得到文件的 特征表示。 2.根据权利要求1所述的基于c和c++软件的依赖结构的文件特征表示方法， 其特征在 于， 所述步骤1)包 含以下子步骤： 步骤11)， 使用clang分析代码中的#i nclude语句， 并提取头文件依赖； 步骤12)， 使用clang将c和c+ +软件中的源文件编译为 llvm的中间表示文件； 步骤13)， 使用llvm分析步骤12)获取的中间表示文件， 提取源文件包含的符号定义与 外部符号使用； 步骤14)， 根据步骤13)中的外部符号使用， 定位到定义了对应外部符号的其他源文件， 并以此构造源文件依赖； 步骤15)， 根据步骤11)和步骤15)分别提取的头文件依赖和源文件依赖， 构造层次化的 文件依赖图， 用于步骤2)的输入。 3.根据权利要求1所述的基于c和c++软件的依赖结构的文件特征表示方法， 其特征在 于， 所述步骤2)包 含以下子步骤： 步骤21)， 指定随机游走的步长 ι、 每个节点上的采样次数η 以及控制节点选择概率的超 参数p、 q； 步骤22)， 取文件依赖图中的一个节点作为 起始节点； 步骤23)， 计算当前节点的直接邻居中各个节点的迁移概率， 并随机选择一个节点作为 下一个访问的节点； 步骤24)， 重复步骤23)， 直到节点序列长度等于 ι， 得到一条节点序列； 步骤25)， 重复步骤2 2)—步骤24)， 直到图中的每 个节点上都经 过采样； 步骤26)， 重复步骤2 2)—步骤25)， 直到图中的每 个节点的采样次数达 到 η； 步骤27)， 得到一组节点序列集 合， 用于步骤3)的输入。 4.根据权利要求1所述的基于c和c++软件的依赖结构的文件特征表示方法， 其特征在 于， 所述步骤3)包 含以下子步骤： 步骤31)， 构造图表示学习模型， 并设置训练轮数γ与节点上 下文宽度ω； 步骤32)， 从步骤2)中输出的节点序列集 合中取一条节点序列； 步骤33)， 取节点序列中的一个节点作为中心节点， 获得左右长度为ω范围内的非本节 点作为该节点的上 下文； 步骤34)， 根据节点的上下文， 使用层次化softmax算法计算上下文中的各节点与中心 节点的共现概 率， 然后计算目标函数并使用反向传播 算法优化模型； 步骤35)， 重复步骤3 3)—步骤34)， 直到该节点序列中的所有节点经 过训练； 步骤36)， 重复步骤32)—步骤34)， 直到所有节点序列都经 过训练； 步骤37)， 重复步骤32)—步骤3 6)， 直到训练轮数满足γ。权　利　要　求　书 1/2 页 2 CN 114610321 A 25.根据权利要求3所述的基于c和c++软件的依赖结构的文件特征表示方法， 其特征在 于， 所述步骤23)的迁移概 率计算公式为： 其中E是依赖图的边集； Z是标准化系数； πtx是未标准化的迁移概率， 定义为πtx＝α(v, x)*ω(t,x)， 由于文件依赖图为无权图， 有 πtx＝αpq(v,x)， 所述αpq(v,x)定义如下： 其中t是随机游走当前所在节点， v是上一次访问的节点， 调整超参数p和q可以控制随 机游走的倾向性， p越大， 游走过程更倾向于向外部探索， q越大， 则探索范围越趋近于初始 节点的小范围局部图。 6.根据权利要求4所述的基于c和c++软件的依赖结构的文件特征表示方法， 其特征在 于， 所述步骤31)的图表 示学习模 型的输入层为节 点的one‑hot编码， 定义文件依赖图为G＝ (V,E)， 某文件vi的one‑hot编码vi为第i位为1， 其余位是0的|V|维向量， 隐藏层为矩阵Z∈Rd ×|V|， 由|V|个d维向量构成， 其输出结果表示为φ(vi)＝Zvi， 输出层是使用层次化softmax算 法计算得到的节点对之间的共现概 率。 7.根据权利要求4所述的基于c和c++软件的依赖结构的文件特征表示方法， 其特征在 于， 所述步骤33)的节点上下文表示为NS(vi,ω)＝{vi‑w,…vi+w}\vi， 其中vi是中心节点， ω 是窗口两侧的宽度。 8.根据权利要求4所述的基于c和c++软件的依赖结构的文件特征表示方法， 其特征在 于， 所述步骤34)的目标函数， 基于节点间的独立 概率分布假设， 定义如下： 其中由于传统softmax算法在计算基数时需要在所有节点上进行运算， 在大型图上的 计算成本昂贵， 该步骤中使用使用层次化softmax算法进行优化， 具体包括： 根据节点在上 下文中出现的频率使用哈夫曼编码转换将节点分配到二叉树中， 使得出现频率更高的节点 具有更短的根路径， 假设到节点vj的路径表示 其中b0为根节点， b「log|V|]为 节点vj， 有 其中二叉树上的每一个节点可以视为一个二分类器， 表示为 其中ψ(bk)∈Rd是节点bk的d维向量表示， 层次化softmax的计算复杂度为O(log|V|)， 传统 softmax的计算复杂度是O(log|V|)， 在计算复杂度上有了明显的优化， 计算出目标函数的 结果后， 使用随机梯度下降与反向传播 算法对模型进行优化， 优化 参数是θ ＝{φ, ψ}。权　利　要　求　书 2/2 页 3 CN 114610321 A 3