背景

代码反混淆（deobfuscation）和代码混淆（obfuscation）对应，是其逆过程。维基百科将代码混淆定义为故意生成人类难以理解的源代码或机器码的过程（"In software development, obfuscation is the deliberate act of creating source or machine code that is difficult for humans to understand."）。代码反混淆可以理解为将原本人类难以理解的代码转化为简单的、可理解的、直观的代码的过程。

这篇文章主要介绍一下 "Big Code" 在代码反混淆领域的应用。更具体一点就是介绍一下提出 "JSNice" 和 "Deguard" 的两篇文章，这两篇文章虽然已经发表快五年了，但至今没有文章Follow这两份工作，因为文章已经将使用 "Big Code" 做代码命名反混淆做到了极致。后来的人无法在这个问题上推陈出新，脱颖而出。

"Big Code"： 代码托管网站如GitHub上的大量免费可用的高质量代码被称为 "Big Code" ，这些数据结合统计推理或深度学习为新兴的开发工具的出现提供了契机。

概率图模型：概率图模型是用图来表示变量概率依赖关系的理论，结合概率论与图论的知识，利用图来表示与模型有关的变量的联合概率分布。

问题

为了项目的安全，开发者在打包发布项目时会对代码进行混淆加密，包括但不限于用无意义的短变量去重命名类、变量、方法，以免代码被轻易破解泄露。另外由于JS脚本主要用于Web开发，对其进行混淆还能压缩脚本的大小，使得浏览器下载、加载更加快速，提升用户的浏览体验。

这一类通过对类、变量、方法重命名的混淆方案确实能加大其他开发者对代码的理解难度。其他开发者不干了，为了能方便理解他人混淆后的代码，学习（抄袭）他人的经验，针对这一类混淆方法的反混淆方法也应运而生。

下面先展示一下安卓APP的代码混淆技术：

经过混淆的代码在功能上是没有变化的，但是去掉了部分名称中的语义信息。因为种种限制，这类混淆也不可能对所有的名称都进行替换。上图中的SQLiteHelper、SQLiteDatabase和Cursor就是一个证明，这些名称都是安卓API，如果将这些类名混淆会影响代码的功能。

理论上一个有经验的安卓开发者可以在这些有限的提示下为所有的名称找到富含语义的表示，所以反混淆只需要一个有经验的开发者（有经验的开发者：？？？我做错了什么）。退一步，找不到有经验的开发者怎么办，没关系，GitHub有高质量的各种项目，现训练一个有经验的开发者也行。不过为了人道主义，消灭996剥削，程序员表示可以用程序代替人，正好可以用GitHub数据训练一个程序做这个反混淆嘛！理论存在，实践开始。

JSNice^[1]

用程序代替人其实并不简单，针对上图中的反混淆问题，程序需要具有“联想”和“推理”能力，比如从a extends SQLiteHelper这一句中，a应该很可能也是Helper类，结合类中有SQLiteDatabase实例推理出比较符合a的语义的类名是DBHelper。

针对以上两点，程序需要先有关系的概念，能从一个词“联想”到另一个词，然后还要有推理的能力，能通过约束从几个候选词中找到最符合的那个词。怎么做这个事呢？虽然有很多的未混淆的JS脚本供程序学习，但在反混淆JS脚本时，程序无法理解复杂的JS脚本，所以需要将JS脚本表示成一种可以利用已知属性推理未知属性的结构，JSNice采用了概率图模型。

概率图模型相比其他学习算法的优势在于可以利用图结构将已知信息带入知识网络，在使用概率图模型之前，往往要求图结构是已知的。现实中我们没有这些先验知识，但是有大量的样本（未混淆代码）。通过样本学习出未混淆JS脚本的概率图就是JSNice的核心。

具体到JSNice，这个工具想要做的是为JS脚本推测名称（name）和类型（type）。先通过一张图看看JSNice的推理过程。

由于JSNice推理名称和推理类型的过程类似，本文就只阐述推理名称的过程。

1. 确定已知和未知属性

JS脚本中包含了各类代码元素（elements）比如变量，常量，类，方法名，域等。对推理名称问题，元素的属性即带有语义的名称，一个需要推理名称的元素，称其属性未知。不需要推理名称的元素其属性已知。首先需要确定JS脚本中的元素属性是否已知。很容易看出图2(a)代码中属性已知的元素包括：常量0和[]、feild名称length和方法名称push，其他的局部变量如e，t，n，r和i的属性都是未知的。

将问题泛化，如何判断任意的JS脚本中的任意元素的属性是否已知是需要解决的第一个问题。JSNice采用程序分析和人工指定的方式确定元素属性是否已知，简单来说，JSNice认为JS脚本中的常量(constants)、对象属性名(objects properties)、方法名(methods)和全局变量名(global variables)都是属性已知的元素，而所有的局部变量的属性都是未知的。值得注意的是JSNice将对象属性名称和API名称直接看做是常量。这个划分是否合理暂不去讨论，但是其确实适用与大部分的JS脚本。有兴趣的读者可以自行研究。

2. 建立依赖网络

第一步获取了JS脚本中的所有元素（属性已知或未知），接下来需要建立元素之间的关系，好方便后续的推理；图2(c)中简单的给出了一些关系，比如"var r = e.length"中可以得到(r, length, L=_.R)的关系。

JSNice实际考虑的元素关系十分复杂，主要有三类，这里简单的进行描述：

• 句法关系，这一类关系主要通过AST得到，例子如下：

这类关系的形式化定义如下

• 别名关系，这类关系通过standard alias analysis得到，将方法调用时传入的arguments和方法声明时的parameters进行关联，形成ARG_TO_PM关系。
• 函数名称关系，由于JS的语言特性，很多的局部变量本身是方法定义，MAY_CALL和MAY_ACCESS表示一个方法的可能调用方法关系和可能访问对象域关系，这类关系可以通过program analysis得到。

类型推理采用的关系有所不同，但这里也不再详述，有兴趣的读者直接移步原文。

3. 训练和推理

现在整理一下对某个JS脚本x进行上述两步分析能得到什么？得到了一个依赖网络  ，其中  为节点集，分别表示未知（unknow）属性元素和已知属性元素。  为边集，表示两个程序元素之间的关系以及关系类型。

现在不去考虑训练的过程，直接看一下推理过程，JSNice采用贪婪算法，对未知属性元素遍历其所有的属性可能，寻找到使score最大的属性作为结果。

具体的算法如下：

JSNice在具体实现时对算法有所优化，但是其基本思想和主要框架都没变。其实对比前文提到人进行反混淆时需要的“联想”和“推理”两种能力，candidates函数担负了“联想”的重任，利用scoreEdges函数对不同的候选属性计算score并选择最大score对应属性的过程就是”推理“。

将图2的推理部分摘出来看：

r的candidates有len和length，t的candidates有step、j和q，i的candidates只有i。推理得到的(r、i、t)的属性是(len、i、step)而不是(length、i、step)；是因为前者的综合score是0.4+0.8+0.5=1.7，而后者的综合score只有0.5+0.6+0.5=1.6。

那么怎么得到scoreEdges和candidates函数呢？

JSNice定义了一个条件随机场：

x为给定某个JS脚本，y为未知属性元素（复数）的任意分配属性，score为指示属性y和脚本x的匹配程度的函数，其返回值为实数，值越大越匹配。

Z是对应JS脚本x的一个惩罚系数，用来保证其Pr和为1

将score定义为k个特征函数的加权平均，得到

最终条件随机场的表示形式为：

写到这里，出现了第一个问题，score为k个特征函数的加权平均，如何确定k呢？

JSNice是在训练阶段的预处理步骤得到k的，实际上不仅仅这一步不仅获得了k，还直接定义了k个 pairwise feature functions  。

往前回一步，本文前面一直说GitHub有未混淆的代码可供概率图模型学习，这里定义训练集  由t个未混淆的JS脚本组成。对  中的任意  元组，JSNice定义其特征的集合为

整个训练集的所有特征集为

JSNice直接定义pairwise feature functions为每个特征三元组

的指示函数：

所以训练集有多少特征三元组，k的值就有多大。

但说了这么多，还是没有提到scoreEdges和candidates。别急，直接定义

如此把前面的公式都串起来了，整个公式组其实只有  是未知，条件随机场的训练过程其实就是计算  的过程。

至于candidates，假设现在概率图模型中的  已经训练完成，根据前面的定义，  和  其实是一一对应的，  本身是特征三元组的指示函数，也和三元组一一对应，所以可以使用权重  直接限制节点  的可能取值。定义  函数对输入的特征三元组集合基于此权重返回top s的三元组。定义  。定义如下辅助函数：

最后：

candidates函数其实就是先在  中找到和  有  关系的  ，然后利用  和  在训练集中找到和  最相似的词作为候选。比较方便的是辅助函数其实可以在预测之前提前计算并缓存下来。

由于笔者本身没有不研究概率图模型，所以训练模型得到  的内容就省略了，有兴趣的读者可以阅读原文^[1]，本文只简单的描述：

JSNice采用判别式训练，由于最大似然需要计算  ，JSNice采用max-margin training，使用Structured Support Vector Machine (SSVM)并用scalable subgradient descent algorithm优化。

Deguard^[2]

相对JSNice做的对JS脚本进行反混淆，Deguard对安卓APK做反混淆的难度要大了很多，放在眼前的一个问题就是项目规模，JSNice的应用scope其实是Web上的JS脚本，考虑网站的加载等限制，单个JS脚本必不会太大，而安卓APK不同，由于安卓本身事件驱动的编程方式，一个简单的安卓APK的复杂度可能就能比得上十分复杂的JS脚本。并且安卓APK的大小一般也没有限制。

还有一些安卓或者说Java需要的约束是建模时需要考虑的，比如一个Java类中的feilds名称必须不一样，一个package中的classes名称必须不一样。不满足这些约束，对APK进行反混淆的结果就失去了其实用性。

考虑到安卓application的复杂性，选取合适的粒度建模是首要的问题，关系过于复杂不利于概率图模型的学习，关系过于简略可能导致无法预测准确的属性，必须有一个权衡。

1. 确定程序元素（图的节点  ）

要为安卓APK定义一个依赖图，首先确定图上的节点，Deguard考虑了APK中的如下元素：

• Types，不管是基本类型(int, long, float)，引用类型(Object, ArrayList)，还是数组类型(int[], Object[])都能做为节点
• Feilds，APK中的任意类中定义的任意Feild都能做为节点
• Packages，APK中的任意package能做为节点，像package a.b就可以做为两个节点，a和a.b。
• Methods，APK中的任意方法都能做为节点，但是如果有overrides关系，那么子类和父类的method公用一个节点表示。
• Constant values and null
• Access Modifiers，比如static，synchronized
• Operations

这里没有考虑Java语言中的泛型机制是因为在编译过程中会消除泛型，APK本身就是编译过后的文件。另外和JSNice不一样的是，Deguard没有考虑局部变量名和参数名，但考虑了局部变量的类型和参数的类型，一方面减少规模，另一方面就是变量名和参数名本身不在APK中。

2. 确定元素属性是否已知

这里将元素属性定义为节点是否被混淆，属性已知说明节点名称未被混淆，不需要预测名称，属性未知说明节点名称已被混淆，需要预测名称。

已知属性元素包括

• 节点如果代表pakages，classes，methods和feilds且在安卓API中，那么这些节点是已知的，因为基于名称的混淆工具并不会混淆这些名称
• 构造函数名称都是已知的
• 节点代表对安卓API方法重写的方法也是已知的，因为前文已经提过，重写关系其实是用一个节点表示。

剩下的元素都是未知的，需要预测名称

3. 构建依赖网络

Deguard用一张图详细描述了其用于构建依赖网络的关系

相对JSNice中大部分的关系来自AST，Deguard选择的关系明显融合进了人的经验，更加的抽象。实际上本文的精华也是这一张图，某种程度上这图中展现出来了人类对具体问题具体分析的思考，而不是仅仅简单的复用已有工作提出的各种关系。

剩下的内容比如模型的训练和推理其实和JSNice差不多，这里不会重复一遍，后续会讲不一样的地方，也就是Deguard如何处理Java程序带来的关于各种名称的约束。

Java中的名称约束还是比较复杂的，这里拿一个例子讲一下：

1. A.a(A)没有任何约束，因为A作为参数的方法只有它一个
2. A.b(Object)不能被重命名为equals，因为这样会override java.lang.Object.equals(Object)
3. B.g()和B.h()方法重命名名称必须不一样，因为这两方法的特征一样
4. B.g()和A.c()方法重命名名称必须不一样，如果一样就是隐式的继承
5. B.h()和A.c()方法重命名名称必须不一样，也是由于method overriding的原因
6. C.x()和B.h()却没有冲突，因为B.h()是private的

相等约束（继承重写机制）可通过共用节点表示，不等约束也需要明确表示，所以Deguard提出了一个检测方法名称不等约束的算法

其他元素，比如类名，Feilds名称的不等约束比较简单，直接处理就行。

所有不等约束以集合  表示，  ，  中任意两个节点的名称必须不一样。

注意这个约束只用与预测阶段，因为训练数据（未混淆）本身满足这些约束。很容易可以把这些约束结合到JSNice的算法1中。

Deguard的概率图优化算法和JSNice也不一样，采用的是pseudo likelihood estimation。具体阐述推荐阅读文章^[3]。

值得注意的是，为什么JSNice就没有Deguard中提到的相等约束和不等约束，笔者个人认为还是由问题和语言特性共同决定，JSNice的名称预测其实只预测了局部变量，而JS的语言特性导致其本身不需要检测局部变量的名称冲突，只有执行结果报错才会说明程序出错。也就是说其实JS本身语言特性就没有这类约束，自然不需要建模。

总结

提出JSNice和Deguard的两篇文章算是基于 "Big Code" 的较早的研究了，这两个工具现在还在维护并可用（JSNice^[4]、Deguard^[5]）也证明了基于 "Big Code" 的研究和工具确实是可行可信有前途的。

从文章的研究思路来看，基于 "Big Code" 的研究首先需要判断："Big Code"能够做到什么和做出来的东西能不能make sense两个问题。分享的两篇文章能够发表就在于大家相信基于已有开源项目做反混淆这件事是合理的。

另外一个就是找到问题本身和建模并解决问题同等重要甚至更加重要。这两篇文章其实都是做的一件事，就是做代码命名推荐。而作者能够在命名推荐这个大的领域内（领域太大），找到完整程序的代码命名推荐（难以入手，没有已知）问题，再进一步缩小Scope到基于部分已知命名的完整程序的代码命名推荐（可以做，"Big Code"可以支持）这件事，这个范围内还正好有两个应用（JS脚本和安卓APK的反混淆）可以支撑研究，真正是十分厉害也比较走运。

结合现在深度学习的风口，其实从应用的角度来看，模型的复杂度和创新度并不重要，还是模型和问题本身的契合度更加重要。

参考

1. ^^abPredicting Program Properties from "Big Code". https://files.sri.inf.ethz.ch/website/papers/jsnice15.pdf
2. ^Statistical Deobfuscation of Android Applications. https://files.sri.inf.ethz.ch/website/papers/deguard.pdf
3. ^ C. Sutton and A. McCallum. An introduction to conditional random fields. Found. Trends Mach. Learn., 4(4):267–373, Apr. 2012.
4. ^项目地址 http://www.jsnice.org/
5. ^项目地址 http://apk-deguard.com/