Page 267 - 《软件学报》2024年第4期

王尚文 等: 基于指针神经网络的细粒度缺陷定位 1845

2 背景知识

本文所提出的方法主要建立在基于抽象语法树路径的代码表示技术之上. 该技术将程序代码转化为抽象语法
树, 并在树结构上提取从根节点到叶节点的路径. 在该路径上的任意一对相邻节点都在树结构上具有父节点-子节
点的相对关系, 因此所提取到的抽象语法树路径能够有效地对程序结构特征进行建模 [12,15] .
定义 1. 抽象语法树. 代码的抽象语法树定义为一个六元组: < N,L,T,r,∆,W > . 其中, N 是一组非叶子节点, L
′
′
是一组叶子节点, T 是一组叶子节点对应的代码令牌, r ∈ N 代表根节点, δ ∈ ∆ : n → n , n ∈ N, n ∈ (N ∪T) 是反映
′ ω ∈ W : l → t, l ∈ L, t ∈ T 建立起每个叶子节点 与其
两个抽象语法树节点 n 与 n 之间父节点-子节点关系的函数, l
相对应的代码令牌 t 间的对应关系.
定义 2. 抽象语法树路径. 一条抽象语法树路径是一条从根节点 r 出发到一个叶子节点 为止的路径. 路径上
l
′ ′ ′ ′
的任意两个相邻节点间都满足父节点-子节点的关系, 其被定义为一个四元组: p =< r,l,N ,∆ > , 其中 l ∈ L, N ⊂ N, ∆ ⊂ ∆ .
定义 3. 操作路径. 一条操作路径是在一条抽象语法树路径的基础上加上代码令牌的变换操作, 被定义为一个
op =< t, p,o > , 其中 t 是抽象语法树路径 p 上叶子节点 o ∈ {UPDATE,DELETE,
三元组: l 所对应的代码令牌,
INSERT} 是一种代码变换原子操作, 其含义是修复该缺陷需要对代码令牌 t 进行何种形式的代码变换.
图 3 展示了图 1 中正确补丁的抽象语法树以及其对应的代码变换操作. MethodDeclaration 是这棵抽象语法树
的根节点, 其他具有灰色背景的非叶子节点, 而所有椭圆形透明背景的节点是叶子节点. 每个叶子节点对应的代码
令牌展现在长方形中. 为了便于展示, 其他与缺陷代码元素无关的节点没有在图中完全展示出来. 对于缺陷代码令
牌“<”, 其相应的抽象语法树路径 p 为: “MethodDeclaration→Block→IfStatement→IfStatement→InfixExpression→
InfixExpression→InfixExpression→Operator”, 即图 3 中用红色虚线标出的路径. 修复这个缺陷的补丁将“<”替换成
了“<=”, 因此其操作路径为 op=<“<”, p, UPDATE>.

MethodDeclaration

Modifier ... Name ParameterDeclaration Block

Private log Type Name IfStatement Others

Sting Value IfStatement Block

InfixExpression Block
InfixExpression Operator InfixExpression

InfixExpression Operator InfixExpression

Variable Operator MethodInvocation

Charno
UPDATE
图 3 图 1 中正确补丁的抽象语法树与变换操作

3 基于指针神经网络的细粒度缺陷定位方法

鉴于神经网络强大的特征提取能力, 本文提出一种基于指针神经网络的细粒度缺陷定位方法, 该方法主要由
训练阶段和预测阶段组成.
在训练阶段, 我们先对大量的补丁数据进行预处理. 针对每一个补丁, 我们利用抽象语法树差分技术分析其代