2022-03-14发表2022-08-08更新论文阅读12 分钟读完 (大约1837个字)

论文阅读 - DeepFix Fixing Common C Language Errors by Deep Learning

program repair ≈ grammar correction in nlp 作者提出了一个端到端的，带 attention 的多层 seq2seq neural network，包括 RNN 编码器，和带 attention 的 RNN 解码器。该网络可以预测程序出错的位置并附上正确的修复。对比其他修复特定编程任务的工作，DeepFix 可以用在任何未预见的任务上。不易解决的错误需要考虑到程序文本中的长期依赖。DeepFix 通过带注意力机制的 seq2seq 模型来捕捉长期依赖。它的优势在于：(1) 利用端对端的基于深度学习网络解决普遍的编程问题；(2) 可以迭代地解决一个程序中的多个错误；(3) 在上千 C 程序评估中得到很好的结果。

Program Representation

程序文本由不同类型的标记组成，如类型、关键字、特殊字符(如分号)、函数、文字和变量。其中，类型、关键字、特殊字符和库函数构成了跨不同程序的共享词汇表。作者在表示程序时保留它们，对其他类型的 token 进行如下建模。首先定义一个固定大小的名称池，然后为每个程序构造一个单独的编码映射 encoding map ，方法是将程序中每个不同的标识符(变量名或函数名)随机映射到池中唯一的名称，并选择一个足够大的池来为数据集中的任何程序创建上述映射。这种转换不会改变程序的语义，且是可逆的。字面量的确切值对学习任务无关紧要，因此，根据字面值的类型将其映射为特殊的 token ，例如，将所有整数字面值映射为 NUM ，将所有字符串字面值映射为 STR 。用 < eos > 表示标记序列的结束。

由于一个程序用 seq 的 tokens 表示时，要产生类似长度的准确修复后的 seq 非常困难，且一个程序通常包含上百个 token。所以作者把代码行号也进行标记，将一个 K 行的程序 P 表示为 $(l_1 , s_1 ),…,( l_k ,s_k)< eos >$，l 和 s 分别是对行号和语句的标记。一个 fix 包括 $l_i , s_i$ ，这比用全部的 token 作为输出简单得多。

Neural Network Architecture

基于 Neural Machine Translation by Jointly Learning to Align and Translate ，NLP 中 encoder-decoder 中第一个使用 attention 机制的工作，将 attention 机制用到了神经网络机器翻译(NMT)。https://arxiv.org/pdf/1409.0473.pdf

这里编码器和解码器 rnn 都由 N 个堆叠的门控循环单元(GRUs)组成。编码器将输入序列中的每个 token 映射到一个称为 annotation 的实向量。对于输入序列$x_1，…，x_{T_x}$, t 时刻的隐藏单元激活计算如下:

$h_t^{(1)} = GRU(h_{t-1}^{(1)},x_t)$

$h_t^{(n)} = GRU(h_{t-1}^{(n)},h_t^{(n-1)}),\forall n \in { 2,…,N }$

解码器网络的隐藏状态被初始化为用编码器网络的最终状态，然后更新：

$d_t^{(n)} = GRU(d_{t-1}^{(n)},d_t^{(n-1)}),\forall n \in { 2,…,N }$

$d_t^{(1)} = GRU(d_{t-1}^{(1)},z_t)$

其中 $z_t$ 是输出 $\hat{y}_{t-1}$在 $t-1$ 和上下文向量 $c_t$ 的连接，定义如下:

$c_t = \sum_{j=1}^{T_x} a_{tj}h_j^{(N)}$

$a_{tj} = \frac{exp(e_{tj})}{\sum_{k=1}^{T_x}exp(e_{tk})}$

$e_{tk} = \Phi(d_{t-1},h_k^{(N)})$

c 就是全部隐状态的一个加权和，用到归一化权重 a 。a 就是一个对齐模型，用来评估当前预测词，与输入词每一个词的相关度。将上一个输出序列隐状态 $d_{t-1}$ 和输入序列隐状态 $h$ 输入网络，然后做 softmax 归一化，计算出权重。

Iterative Repair

DeepFix 使用简单而有效的迭代策略来修复程序中的多个错误。oracle 的工作是通过检查更新后的程序是否比输入的程序好来决定是否接受修复。如果更新后的程序不会比输入程序产生更多的错误消息，则使用编译器并接受修复。我们还使用一些启发式方法来防止对输入程序的任意更改。例如，如果 oracle 不保留原始语句 $s_i$ 中的标识符和关键字，则它拒绝 fix $s_i$。一旦修复程序被接受，DeepFix 将再次向网络显示更新后的程序。

这种迭代策略停止的条件：(1) oracle 确定更新程序没有任何错误；或 (2) 网络视输入程序是正确的，发出一种特殊 token “fix”；或 (3) oracle拒绝修复,或 (4)达到预定的迭代的数量上限。

除了决定是否替换语句，网络还会决定新的一行是否要插入在行前或行后，用 $l_i^-,l_i^+$ 代替 $l_i$，如果要删除行，则将 $l_i$ 带上空字符 $\epsilon$。oracle 使用程序特殊的编码映射，将修复好的 token sequence 重构回原来的标识符。它使用修复中的行号，并用输入程序中相应行中的字面值替换诸如 NUM 和 STR 等特殊标记。如果 oracle 不能重建程序文本，那么它拒绝修复。

作者提出的修复策略有几个优点：(1) 程序完整地呈现在网络上。识别和修复编程错误通常需要能够推断长期依赖关系的全局分析。网络架构能够有选择地参与程序的任何部分，可以推理结构和语法约束，以预测错误的位置和需要的修复。(2) 在输入和输出中都包含行号，降低了粒度，从而降低了预测任务的复杂性。(3) DeepFix可以迭代地修复程序中的多个错误。(4) oracle用于跟踪进度，防止无用的或任意的更改。(5) DeepFix的修复策略比较泛化。例如，如果我们试图修复逻辑错误，我们可以使用测试引擎和测试套件作为oracle。如果修复程序通过了更多的测试，那么它将被接受。