ACM通信

研究突出了

从“大代码”预测程序属性

作者:Veselin Raychev, Martin Vechev, Andreas Krause
ACM通讯，2019年3月，第62卷第3期，99-107页
10.1145 / 3306204
评论

我们提出了一种从大型代码库(又称“大代码”)中预测程序属性的新方法。我们的方法从“大代码”中学到了一个概率模型，并使用这个模型来预测新的、看不见的程序的属性。

我们工作的关键思想是将程序转换为一种表示形式，使我们能够形成推断程序属性的问题，就像机器学习中的结构化预测一样。这使我们能够利用强大的概率模型，如条件随机场(CRFs)和执行联合程序属性的预测。

作为该方法的一个示例，我们构建了一个名为JSNICE的可伸缩预测引擎，用于在JavaScript上下文中解决两种任务:预测标识符(语法)名称和预测变量(语义)类型注释。通过实验，JSNICE预测了63%的名称标识符的正确名称，其类型注释预测在81%的情况下是正确的。自发布以来http://jsnice.org， JSNice已经成为一个流行的系统，有数十万的使用。

通过将推断程序属性的问题表述为结构化的预测，我们的工作为一系列新的“大代码”应用提供了可能，如去混淆器、反编译器、不变生成器等。

回到顶部

1.简介

近年来，由于类型系统、约束求解、程序分析和综合技术的进步，编程语言领域取得了重大进展。基本上，这些方法对每个程序进行推理隔离虽然强大，但基于这些技术的编程工具的有效性正在接近其固有的限制。因此，如果要进行重大改进，就需要进行更具破坏性的更改。

与此同时，从大型数据集(也称为“大数据”)创建概率模型已经改变了许多领域，如自然语言处理、计算机视觉、推荐系统等。然而，尽管“大数据”在各种应用领域取得了压倒性的成功，但从大型程序数据集中学习之前并没有对编程工具产生切实的影响。然而，随着GitHub等存储库中公开的源代码的巨大增长⁴和BitBucket都²(DARPA最近的一项倡议将其称为“大代码”¹¹)带来了创造基于此类数据的概率模型的新型编程工具的机会。它的愿景是，通过利用已经花费在开发数百万个程序上的巨大努力，这些工具将有能力解决传统技术无法解决的任务。然而，有效地从项目中学习是一个挑战。一个原因是程序就是数据变形金刚具有复杂的语义，应该在学习的概率模型中捕获和保存。

1.1.程序的结构化预测

我们工作的核心技术洞察力是将输入程序转换为一种表示，使我们能够用条件随机场(CRFs)的结构化预测来表述预测程序属性的问题。¹⁵事实上，crf是一个强大的概率模型，成功地应用于包括计算机视觉和自然语言处理在内的各种应用中。^12，15，16我们将展示如何实例化这种方法来预测语义信息(例如，类型注释)以及语法事实(例如，标识符名称)。据我们所知，这是第一个展示了crf如何在程序的上下文中被学习和使用的作品。通过连接程序到crf，广泛的学习和推理算法¹⁴可用于领域的程序。

图1说明了结构化预测方法。在预测阶段(图的上部)，我们得到了一个输入程序，我们可以据此推断出感兴趣的属性。下一步，我们将程序转换为一种称为依赖网络的表示形式。依赖网络捕获程序元素之间的关系，这些程序元素的属性是可以预测的，而它们的属性是已知的。一旦获得网络，我们执行结构化预测，特别是称为最大后验推理(MAP)的查询。¹⁴此查询产生一个联合通过优化基于学习到的CRF模型的评分函数，对所有元素进行预测。考虑到结构和相关性的联合预测尤其重要，因为不同元素的性质往往是相关的。一个有用的类比是在图像处理中进行联合预测的能力，其中像素标签的预测受到相邻像素的预测的影响。

图1。程序的结构化预测。

图2。的屏幕截图http://jsnice.org/:缩小的代码(左)，去混淆版本(右)。

1.2.JSNICE: JavaScript的名称和类型推断

作为这种方法的一个例子，我们构建了一个系统，它解决了JavaScript中的两个重要挑战:预测(语法)标识符名称和(语义)变量类型注释。这样的预测在软件工程(例如，重构以提高代码可读性)、程序分析(例如，类型推断)和安全(例如，去混淆)中都有应用。我们关注JavaScript有三个原因。首先，在类型推断方面，近年来出现了添加类型注释的JavaScript扩展，比如谷歌闭包编译器⁵和打印稿。⁷然而，这些扩展依赖于传统的类型推断，无法扩展到使用动态计算和复杂库(如jQuery)的实际程序。¹³我们的工作预测了实际程序中可能的类型注释，这些注释可以提供给程序员或标准的类型检查器。其次，Web上的许多JavaScript代码都是模糊的，使人们很难理解程序在做什么。我们的方法恢复了可能的标识符名称，从而使Web上的许多代码再次可读。这是通过在开源库(如GitHub)中提供的大型且注释良好的JavaScript程序语料库实现的。

自从发布以来，JSNICE已经成为一个广泛使用的系统，用户范围从JavaScript开发人员到安全专家。在一年的时间里，我们的用户清除了超过9gb(8770万行代码)的唯一(非重复)JavaScript程序。图3显示了这些程序大小的直方图，表明用户经常使用较大的代码片段查询它。JavaScript程序的平均大小为91.7 KB。

图3。直方图的查询大小为http://jsnice.org/用户在2015年5月10日- 2016年5月10日期间发送的。

1.3.Nice2Predict:结构化预测框架

为了加快创建新应用程序的速度(JSNICE就是一个例子)，我们构建了一个可重用的框架Nice2Predict(在http://nice2predict.org)，包括本工作的所有组成部分(例如，训练和推理)，除了特征函数的定义(这是特定于应用程序)。然后，要使用我们的方法，只需根据CRF模型对应用程序进行划分，这是通过定义合适的特征函数(我们将在本文稍后的部分中为JSNICE展示此类函数)来完成的，然后调用Nice2Predict训练和推断机制。最近的一个实例是DeGuard⁹（http://apk-deguard.com)，该系统通过预测ProGuard擦除的方法、类和字段名来执行Android布局去混淆。⁶

回到顶部

2.概述

现在，我们在一个运行的示例中提供了对我们的概率方法的非正式描述。中的JavaScript程序图4 (a)．这是一个具有短的、非描述性标识符名称的程序。这样的名称可以由没有经验的程序员新手产生，也可以由称为最小化(一种布局混淆的形式)的自动化过程产生，它将标识符名称替换为更短的名称。在客户端JavaScript的情况下，最小化是Web上的一个常见过程，用于减少通过网络传输的代码的大小和/或防止用户理解程序实际在做什么。除了晦涩的名称，这个程序中的变量也缺乏注释的类型信息。这个模糊化的程序碰巧将输入字符串划分为给定大小的块，并将这些块存储到数组的连续条目中，这可能很难理解。

图4。概率推断程序属性的一个例子。

给定程序图4 (a)， JSNICE自动生成程序图4 (e)．输出程序具有新的标识符名称，并使用参数、局部变量和返回语句的预测类型进行注释。总的来说，与原来的程序相比，这个程序更容易理解它的功能。我们现在概述执行这种转换的预测方法。我们专注于预测名称(逆转缩小)，但是预测类型的过程是相同的。

2.1.第一步:确定已知和未知属性

给定程序图4 (a)，我们使用简单的静态(范围)分析来确定我们想要推断其属性的程序元素集。这些元素的属性是未知的在输入(即受缩小影响)。当预测名称时，这个集合由输入程序的所有局部变量和函数参数组成:E t n r,我。我们还确定其属性为已知的(不受缩小影响)。这包括字段和方法名(例如，带有name的字段元素长度)．中显示了这两种元素图4 (b)．我们的目标是预测未知的属性基于:(i)获得的已知的属性和(ii)元素之间的关系(此处讨论)。

2.2.步骤2:建立依赖网络

接下来，使用我们稍后定义的特性，我们构建一个依赖网络来捕获程序元素之间的关系。在进行预测时，依赖网络是捕获结构的关键，并直观地决定了要预测的属性如何相互影响。例如，已知和未知属性之间的联系允许我们利用许多程序使用公共锚点(例如JQuery API)这一事实，这意味着我们旨在预测的未知量会受到已知元素使用方式的影响。依赖关系是以下形式的三组(n, m, rel),n,米是程序元素吗rel是两个元素之间的特殊关系。在我们的工作中，所有的依赖关系都是三元组的，但这些可以扩展到涉及两个以上元素的关系。

在图4 (c)，我们展示了程序元素之间的三个依赖关系示例。例如，声明我+ = t生成一个依赖(我t L + = R),因为我而且t位于+=表达式的左右两侧。同样,该声明Var r = e.length生成多个依赖项，包括(r、长度L = _.R)哪个指定了关系的左边部分，由l，出现在表示的右侧的去引用之前R(我们将在第4节详细阐述不同类型的关系)图4 (c)我们只包括一些关系。

2.3.步骤3:MAP推断

在获得依赖网络之后，我们接下来通过MAP推断查询推断出节点最有可能的值。¹⁴非正式地说，在这种类型的查询中，预测利用了网络结构(即节点之间的连接)，而不是每次单独预测每个节点。见图4 (d)，为网络之用图4 (c)，我们的系统会推断出新的名称一步而且len．它还预测了之前的名字我是最有可能的。让我们考虑一下我们是如何预测这些名字的一步而且len．网络在图4 (d)和in是同一种吗图4 (c)但是随着学习阶段的输出产生了额外的表(即，学习决定了具体的特征函数和与它们相关的权重)。每个表都是一个函数，当由相应的边连接时，它对属性的赋值进行评分(直观地说，是特定对的可能性有多大)。考虑最上面的桌子图4 (d)．第一行表示赋值我而且一步得分为0.5。MAP推断搜索向节点分配属性，以便总和表格中显示的分数是最大化的。对于两个节点我而且t，推断最终会从表中选择最高分(即值)我而且一步)．同样的节点我而且r．然而,对于节点r而且长度,推理不选择最上面的行，但要选择第二行的值。原因是，如果它选择了最上面的行，那么唯一可行的选择(为了匹配值长度的第二行我右表(值0.6)。然而，赋值0.6导致较低结合整体分数。也就是说，MAP推断必须考虑全局结构并且不能简单地选择每个函数的最大值。

为了获得良好的MAP推断性能，我们开发了一种针对程序领域的新的算法变体(现有的推断算法无法有效地处理不受限制的网络结构和每个元素大量可能的预测的组合)。

2.4.输出程序

最后，在推断出新名称之后，我们的系统将原始程序转换为使用这些名称。在程序中捕获整个推断过程的输出图4 (e)．注意，在这个输出程序中，名称往往准确地捕捉程序的功能。

2.5.预测类型注解

尽管我们演示了变量名的推断过程，但预测类型注释的总体流程是相同的。有趣的是，在预测类型之后，可以调用标准类型检查器来检查预测的类型对程序是否有效。我们的例子图4 (e)，预测的类型注释(显示在注释中)确实有效。通常，在预测语义属性(如类型)时，可靠性发挥了作用，我们的方法可以作为猜测-检查循环的一部分。

2.6.独立的缩小

我们注意到，我们的名称推断过程与缩小的名称是什么无关。特别地，该进程将返回相同的名称，无论使用哪个迷你符来混淆原始程序(只要这些迷你符总是重命名同一组的变量)。

回到顶部

3.结构预测

我们现在介绍结构化预测方法。我们稍后将在第4节中实例化这种方法。

3.1.符号:程序，标签，预测

让xX是一个程序。与标准程序分析一样，我们将推断关于程序语句或表达式的属性(称为程序元素)。为一个程序x，每个元素(例如变量)都用一个索引(一个自然数)来标识。我们通常将元素分成两类:(i)我们感兴趣的推断属性的元素和(ii)我们知道其属性的元素(例如，通过标准程序分析或手工注释获得)。我们使用两个辅助函数n,米：X为给定程序返回适当数量的程序元素x：n（x)返回类型为(i)和的元素个数米（x类型元素的数量(ii)。当x我们写的上下文清楚吗n而不是n（x),米而不是米（x)．

我们使用集合标签_U表示预测属性可以接受的所有可能值。例如，在类型预测中，标签_U包含所有可能的基本类型(例如，数字，字符串等)。然后，对于一个程序x，我们用这个符号y= (y₁、……y_n（x）)来表示预测的程序属性向量。在这里,yY在哪里Y= (标签_U）^＊．也就是每一项y_我在向量y范围在标签_U表示程序元素我有财产y_我．

为一个程序x，我们定义这个向量获取已知属性。在这里,每一个可以从属性集中取值吗标签_K哪些可能与属性集不同标签_U我们用来预测。例如，如果已知属性是整数常量，标签_K将包含所有有效整数。为了避免杂乱x从上下文是清晰的，我们用z而不是Z^x．我们使用标签＝标签_U标签_K表示所有属性的集合。

注意，要应用这种方法，预测的总数必须预先固定(即:n（x))。这不同于其他的设置，比如语法，¹⁰预测的数量是无限的。

3.2.问题定义

让表示训练数据:的集合t每个程序都用相应的属性进行了注释。我们的目标是学习一个能捕捉条件概率的模型公关（y|x)．一旦学习了这个模型，我们就可以通过提出以下MAP查询来预测新程序的属性:

给定一个新程序x,找y= arg马克斯_{y 'x}公关（y '|x）

也就是说，我们的目标是找到最有可能的程序属性赋值y根据概率模型。在这里,_xY描述一组可能的属性赋值y '对以下元素编程x．一组_x允许限制可能的属性集，对于编码特定于问题的约束很有用。例如，在类型注释推断中，集合_x可以将注释限制为使结果程序进行类型检查的类型。

3.3.条件随机场(CRFs)

我们现在简要地描述CRFs，这是Lafferty等人定义的一个特殊模型。¹⁵以前用于一系列任务，如自然语言处理、图像分类等。crf表示条件概率公关（y|x)．我们考虑因素为正的情况，在这种情况下，不损失一般性，任何条件概率的性质y给定一个程序x可以编码如下:

在那里,分数函数是否返回一个实数，表示属性赋值的分数y为一个程序x．得分较高的作业比得分较低的作业更容易发生。Z（x),被称为配分函数，确保上述表达式实际上编码了条件分布。它只根据程序返回一个实数x,即:

W.l.o.g,分数可以表示为和的组成k特征函数f_我与重量有关w_我：

在这里,f是函数的向量吗f_我而且w是权重向量吗w_我．特征函数f_我：YxXR;用于给程序属性赋值打分。这种分数函数的表示非常适合学习(如权重w可以从数据中学习)。

3.4.特性的约束

特征函数是控制似然预测的关键。例如，可以定义一个特征函数来禁止或降低不受欢迎的预测的分数:比如iff_我（y^B，x) = -H在哪里H是一个很大的正数吗f_我(重量w_我> 0)实际上禁用赋值y^B作为公关（y^B|x)将趋近0。

3.5.一般预测方法

让我们首先定义在进行预测时使用的程序元素之间的关系类型。让一组可能的关系rel。在我们的运行示例中考虑的一个示例关系是L + = r．相关变量我而且t在图4 (c)由表达式而生I + = t在代码中。其他关系的例子见第4节。

3.6.两两指标特性功能

让是一组成对的特征函数，其中每个_我：标签x标签xrelR分数一对与来自的关系相关联的属性rel．例如:

一般来说，可以使用任何特征函数，但我们的工作表明，这些成对函数足以高质量地预测名称和类型。接下来，我们将更正式地介绍预测过程的步骤。

3.7.步骤1:建立依赖网络

我们从建立网络开始G^x＝V^x，E^x为一个程序x，捕获预测之间的依赖关系。在这里,由我们想要预测其属性的元素(例如，变量)组成以及我们已经知道其性质的元素边的集合E^xV^xxV^xxrel表示两个程序元素之间存在关系的事实，并描述这种关系是什么。这种网络的定义也称为网络multi-graph因为没有限制在一对节点之间只有一条边，所以我们的定义允许具有不同的多个依赖关系rel。

我们定义特征函数f（y，x)在图表上G^x如下。让(y，z^x)是未知属性的串联y已知的性质z^x在x．然后,f_我定义为其相应的应用的总和_我在所有网络边的集合上G^x：

3.8.步骤2:MAP推断

回想一下，我们执行的键查询是MAP推断。也就是说，给定一个程序x，找到一个预测y这样:

因为参数max是独立于Z（x)，我们得到一个等价的简化查询:

理论上，可以使用任何可用的推理算法来解决上述查询(精确推理通常是一个NP-hard MaxSAT问题)。在本工作中，我们设计了一种适合我们程序设置的快速近似贪婪MAP推理算法:成对特征函数、不受限制的性质G^x还有很多可能的作业。我们的算法逐个或成对地更改每个节点的标签，直到赋值分数无法进一步提高为止。

3.9.学习

训练阶段的目标(下半部分)图1)就是学习重量w中使用的分数函数来自一个大型训练集的程序。这些权重不能通过在训练数据中计数的方式得到。¹⁴(部分20.3.1)。相反，我们使用来自在线支持向量机的学习技术:给定一个训练数据集的t样本，目标是找到w比如给定的作业y^（j）在尽可能多的训练样本中，得分最高的作业受到额外的边际学习约束。Ratliff等人描述了学习过程。¹⁷

回到顶部

4.预测名称和类型

在本节中，我们将介绍JSNICE系统，用于预测:(i)局部变量的名称和(ii)函数参数的类型注释。我们在JavaScript上下文中研究上述挑战，JavaScript是一种流行的语言，解决上述两个问题非常重要。但是我们注意到，本节中讨论的很多机制都适用于其他编程语言。

4.1.JavaScript标识符名称预测

名称预测任务的目标是预测给定程序中局部变量的(最可能的)名称x．我们按如下方式进行。首先,我们定义的所有常量、对象属性、方法和全局变量x．中的每个元素可以从集合中赋值吗标签_K＝JSConstsJSNames,在那里JSNames是所有有效标识符名称的集合JSConsts是可能常数的集合。我们注意到对象属性名称和应用程序编程接口(Application Programming Interface, API)名称被建模为常量，因为点(.)操作符接受左侧的对象和右侧的字符串常量。我们定义集合的所有局部变量x．在这里，属于两个不同作用域的变量名将导致两个程序元素．最后,标签_U范围在JSNames。

为了确保新预测的名称保持程序语义，我们确保以下附加约束保持:所有对重命名的局部变量的引用必须重命名为相同的名称。这取决于我们如何定义(每个元素对应一个局部变量，而不是每个变量出现一个元素)，(ii)预测的标识符名称不能是保留关键字。这是通过确保标签_U不包含关键字，并且(iii)预测不能在同一范围内为两个不同的变量建议相同的名称。这是通过禁止分配名称冲突的标签来实现的。

4.2.JavaScript类型注释预测

我们的第二个应用程序涉及函数参数的概率类型注释推断。通过标准的程序分析技术派生这些注释特别具有挑战性，因为这样的派生将需要找到函数的所有可能的调用者。相反，我们利用现有的手动(类型)注释JavaScript程序。在JSNICE中，我们使用JSDoc¹用于训练数据的注释代码。

我们用来预测类型注释的简化语言定义如下:

在这里,n常量的范围(nJSConsts)，var是一个元变量，范围覆盖程序变量、*范围覆盖二元操作符(+、-、*、/、.、<、==、==等)以及所有可能的变量类型。也就是= {?｝l在哪里l是一组类型(我们讨论如何实例化l下面),?表示未知类型。为了明确起见，我们使用集合JSTypes在哪里JSTypes=。我们使用函数[]_x：前女友JSTypes获取程序中表达式的类型x．这个地图可以手动提供，也可以通过程序分析构建。当程序x从我们使用的上下文来看是很清楚的[e作为[]的快捷方式_x（e)．

4.3.定义已知和未知的程序元素

我们定义未知程序元素的集合如下:

也就是说,包含未知类型的变量。原则上，我们可以区分类型和未知类型?为了更好地控制我们想要预测的类型。然而，由于标准类型推断不能预测函数参数的类型，所以我们用type?来注释所有未注释的参数。

接下来，我们定义已知元素的集合．请注意,可以包含任何表达式，而不仅仅是变量：

也就是说,包含两者，类型已知的表达式和常量。我们不限制可能的赋值集合_x,也就是说,_x= (JSTypes）ⁿ(回想一下,n是一个函数，它返回要预测其属性的元素的数量)。这意味着我们完全依赖于学习去发现能够创造出不矛盾类型的规则。我们应用的唯一限制(在这里讨论)是约束JSTypes当执行预测。

为JSTypes= {?｝l一组l类型可以以各种方式实例化。在这项工作中，我们定义l＝P（T),T，是类型的完整格T定义在图5．在图中，我们使用“…”来表示用户定义的对象类型的数量可能是无限的。请注意,l允许变量可以是联合类型{字符串,数字}为方便起见，也可以写成字符串V数字。

图5。预测发生的类型格。

4.4.相关程序元素

我们引入的程序元素之间的关系定义了如何构建边缘集E^x程序的x．由于这两项预测任务的元素是相似的，所以它们之间的关系也是相似的。如果关系是特定于某个特定任务的，那么我们会在描述中明确说明。

相关的表达式。我们讨论的第一个关系本质上是语法关系:它基于程序的抽象语法树(AST)将两个程序元素联系起来。让我们考虑一下这个表达式我+ j < k。首先，我们构建表达式的AST，如图6 (a)．假设我们对执行变量的名称预测感兴趣我，j,k，分别用指标1、2、3表示，即:然后，我们构建如下所示的依赖网络图6 (b)为了表明对三个元素的预测是相互依赖的(特殊的关系显示在边缘上)。例如，边缘之间1而且2表示这些节点在表达式中参与的关系L + R在哪里l的节点。1而且R的节点。2．

图6。(a)表达的ASTI + j < k以及由AST关系构建的两个依赖网络:(b)用于名称，(c)用于类型预测。

使用以下语法定义关系:

所有关系rel_ast的一部分rel,也就是说,rel_astrel．如前所述，二进制运算符上的范围。使用上述语法派生的所有关系只出现一次l而且R．对于一个关系rrel_ast,让r［x/l，y/R，e/_]表示其中的表达式x被替换为l，y被替换为R和表达e用_代替。然后，给定两个程序元素一个而且b和的关系rrel_ast，则认为匹配存在，如果r［一个/l，b/R, (expr) / _)经验值（x) /。在这里,expr表示程序设计语言中所有可能的表达式经验值（x)是程序的所有表达式x。优势(a、b r）E^x两个程序元素之间一个而且b之间存在匹配，则表示存在a、b,r．

注意，对于给定的一对元素一个而且b可能有不止一个关系匹配，也就是两者都匹配r₁，r₂rel_ast比赛在哪里r₁r₂(因此，两者之间可能有多条边一个而且b与不同的关系)。

上面描述的关系对于名称和类型推断都很有用。对于名称，相关的表达式是变量，而对于类型，它们不需要局限于变量。例如,在图6 (c)类型之间是有关系的k而且我+ j通过L < R．注意，我们的规则不直接捕获之间的关系[我]而且(i + j)，但它们是传递相关的。尽管如此，仍然存在许多重要的类型推断关系。例如，在经典的类型推断中，关系L = R隐含了一个约束规则[L] [R]在哪里超类型关系(在图5)．有趣的是，我们的推断模型可以学习这样的规则而不是手动提供它们。

其他关系。我们引入了另外三种类型的语义关系:(i)捕捉表达式之间的别名的关系，(ii)函数调用关系捕捉一个函数(由变量表示)是否可以调用另一个函数(也由变量表示)，以及(iii)对象访问关系指定一个对象字段(由字符串常量表示)是否可以由函数访问。最后两种关系仅用于名称预测，并且在预测函数名称时特别有效。

回到顶部

5.实施和评价

我们在一个名为JSNICE的交互式系统中实现了我们的方法，该系统的目标是JavaScript的名称和类型预测。JSNICE修改谷歌闭包编译器。⁵在标准操作中，这个编译器接受人类可读的JavaScript和可选的类型注释，对其进行类型检查，并返回一个经过优化的、精简的、人类不可读的JavaScript和剥离的注释。

在我们的系统中，我们向编译器添加了一种新模式，它与标准操作相反:给定一个优化的最小化JavaScript代码，JSNICE生成的JavaScript代码具有良好的注释(使用类型)，并且尽可能让人读懂(使用有用的标识符名称)。我们的名称和类型的两个应用程序被实现为两个可以单独调用的概率模型。

5.1.我们的数据集

为了评估我们的方法，我们收集了两组不相交的JavaScript程序，以形成我们的训练和评估数据。为了进行培训，我们从GitHub上下载了10517个JavaScript项目。⁴为了进行评估，我们选取了BitBucket中提交次数最多的50个JavaScript项目。²通过从不同的存储库中选取项目，我们减少了训练和评估数据重叠的可能性。

我们还在GitHub中搜索，检查评估数据中的项目是否包含在训练数据中。最后，我们实现了一个简单的检查器，从训练和评估数据中检测和过滤出缩小和模糊的文件。在对精简文件进行过滤后，我们最终得到了324501个文件的训练数据和2710个文件的评估数据。

5.2.精度

为了评估JSNICE的精度，我们首先使用UglifyJS缩小了训练数据中的所有2710个文件⁸(对于使用JSNICE的目的，其他声音缩小器应该产生等效的输入)。如前所述，我们关注一种特别流行的混淆形式，称为布局混淆。它的工作原理是将局部变量重命名为无意义的短名称，并删除空白和类型注释(其他类型的混淆，如加密，在本工作中不考虑)。每个缩小的程序在语义上是等价的(使用与或eval)到原文。然后，我们在小型程序上使用JSNICE来评估它在重构名称和类型信息方面的能力。我们比较了以下配置的精度:

• 最强大的系统与所有的训练数据工作，并执行结构化预测，如目前所述。
• 两个系统使用一小部分的训练数据一个对10%的文件，一个对1%的文件。
• 为了评估结构在进行预测时的影响，我们取消了未知属性之间的关系，并对该网络进行了预测(训练阶段仍然使用结构)。
• naïve基线不做预测:它保持名称相同，并将所有类型设置为最常见的类型字符串。

名字的预测。为了评估名称预测的准确性，我们使用每个小型程序并使用JSNICE中的名称推断来重命名其本地变量。然后，我们将每个测试程序的新名称与原始名称(在混淆之前)进行比较。的第二列汇总了名称重构的结果表1．总的来说，我们最好的系统准确地恢复了63.4%的标识符名称。训练数据较少的系统精度明显较低，这说明训练数据大小的重要性。

表1。在我们的测试集中评估了小型JavaScript程序名称和类型重构的精度和查全率。

不使用结构化预测也会显著降低精度，其效果与少一个数量级的数据差不多。最后，不改变任何标识符名称产生25.3%的准确性，这是因为缩小代码可能不会重命名一些变量(例如，全局变量)，以保证语义保持转换，偶尔一个字母的局部变量名称保持不变(例如，循环的归纳变量)。

注释类型预测。在2710个测试程序中，有396个在JSDoc中为函数提供类型注释。对于这些396，我们采用了没有类型注释的简化版本，并试图在函数签名中重新发现所有类型。我们首先运行Closure编译器类型推断，它没有为函数参数生成类型。然后，我们运行JSNICE并对其进行计算，以推断这些函数参数类型。

JSNICE并不总是为每个函数参数生成一种类型。例如，如果函数体为空，或者没有使用参数，我们通常无法将参数与任何已知的程序属性联系起来，结果是无法进行预测，返回未知的类型(?)为了考虑到这一影响，我们报告了召回和精度。召回率是JSNICE在评估中作出预测的函数参数的百分比，而不是?精度指的是JSNICE做出的预测中，与测试程序手工提供的JSDoc注释完全相等的案例的百分比。我们注意到，手动注释并不总是精确的，因此100%的精度不一定是理想的结果。

的最后两列给出了类型的评估结果表1．由于我们评估的产品JavaScript应用程序通常具有简短的方法和复杂的关系，因此在我们最好的系统中，预测程序类型的回调率只有66.9%。然而，我们注意到，我们推断的所有类型都不是通过最先进的前向类型分析推断出来的(例如Facebook Flow^3.)．

由于常用类型的总数不如名称的数量多，训练数据量对系统精度和召回率的影响较小。为了进一步提高类型预测的精度和召回率，我们假设在程序元素之间添加更多的(语义)关系比添加更多的训练数据更重要。drop结构略微提高了预测类型的精度，但代价是显著降低了查全率。原因在于，一些类型仅通过非结构化方法无法捕获的其他预测类型关系与已知属性进行传递性关联。另一种是预测系统，它为每个变量建议JavaScript程序中最可能的类型字符串．该系统召回率为100%，但精度仅为37.8%。

5.3.预测类型的有用性

为了看看预测的类型是否有用，我们将它们与原始类型进行了比较。首先，我们注意到，在396个程序中，我们的求值数据有3,505个函数参数类型注释。在删除这些注释并使用JSNICE重新构造它们之后，没有被删除的注释的数量是多少?增加到4,114个相同的项目。JSNICE生成的类型比原来更多(尽管有66.3%的回调)的原因是，并不是原来程序中的所有函数都手动提供了类型。

有趣的是，尽管注释的函数比原始代码多，JSNICE的输出类型错误却更少。我们总结了这些发现图7．对于这396个程序中的每一个，我们都运行了谷歌闭包编译器的类型检查以发现类型错误。其中，该pass检查不兼容的类型、调用非函数、冲突的、缺失的类型和对象上不存在的属性。对于我们的求值，我们保留了所有的检查，除了不存在的属性检查，它在几乎所有(甚至有效)程序上都失败了，因为它依赖于注释JavaScript类的所有属性——几乎没有任何程序在训练或求值数据中拥有的注释。

图7。使用手动提供的类型和预测类型的类型检查程序数量的评估结果。

当我们在输入程序上运行类型检查时，我们发现大多数程序(289个)有类型检查错误。令人惊讶的是，这可以解释为JavaScript开发人员通常不会对注释进行类型检查。其中，我们发现原始代码中有拼写错误的类型名称。大多数类型检查错误都是由于缺少或冲突的类型造成的。在许多情况下，提供的类型对于文档来说很有趣，但在语义上是错误的，例如，参数是字符串表示函数的名字，但是手动注释将其类型指定为函数．相比之下，JSNICE重构的类型使大多数(227个)程序进行类型检查。在141个最初不进行类型检查的程序中，JSNICE能够推断出正确的类型。另一方面，JSNICE在21个程序中引入了类型错误。我们调查了其中的一些错误，发现并非所有的错误都是由于错误的类型造成的——在某些情况下，由于类型系统无法精确地表达所需的程序属性，而又不能手动提供类型转换注释，所以预测的类型被拒绝了。

5.4.模型尺寸

我们的模型包含7,627,484个用于名称的特性和7,052个用于类型的特性。每个特性及其权重被存储为一个三重值。因此，每个特性只需要20个字节，因此名称模型需要145.5 MB，类型模型需要1.3 MB。存储所有名称和类型的字典需要16.8 MB。由于我们不压缩模型，查询处理的内存需求与模型大小成比例。

回到顶部

6.结论

我们提出了一种新的概率方法，通过学习大型代码库(称为“大代码”)来预测程序的属性。其核心技术思想是用crf将属性推断问题表述为结构化预测，实现程序属性的联合预测。作为我们方法的一个实例，我们展示了一个名为JSNICE的系统，它可以通过预测JavaScript的名称和类型注释来逆转布局去混淆的过程。自从公开发布以来，JSNICE已经成为JavaScript布局去混淆的流行工具。

未来工作中有趣的项目包括反转其他类型的混淆(除了布局)，扩展方法来预测程序的语义不变量，以及更丰富的与标准程序分析器的集成，其中机器学习模型的下一个预测是由分析器产生的一个潜在的反例来指导之前的预测。

我们还注意到，在过去几年中，向“大代码”学习的领域已经成为一个活跃的研究领域。最近在Raychev可以找到关于这一领域各种发展的调查¹⁸以及Vechev & Yahav。¹⁹

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2019 ACM股份有限公司

---

没有发现记录