背景

代碼反混淆（deobfuscation）和代碼混淆（obfuscation）對(duì)應(yīng)，是其逆過程。維基百科將代碼混淆定義為故意生成人類難以理解的源代碼或機(jī)器碼的過程（"In software development, obfuscation is the deliberate act of creating source or machine code that is difficult for humans to understand."）。代碼反混淆可以理解為將原本人類難以理解的代碼轉(zhuǎn)化為簡單的、可理解的、直觀的代碼的過程。

這篇文章主要介紹一下 "Big Code" 在代碼反混淆領(lǐng)域的應(yīng)用。更具體一點(diǎn)就是介紹一下提出 "JSNice" 和 "Deguard" 的兩篇文章，這兩篇文章雖然已經(jīng)發(fā)表快五年了，但至今沒有文章Follow這兩份工作，因?yàn)槲恼乱呀?jīng)將使用 "Big Code" 做代碼命名反混淆做到了極致。后來的人無法在這個(gè)問題上推陳出新，脫穎而出。

"Big Code"： 代碼托管網(wǎng)站如GitHub上的大量免費(fèi)可用的高質(zhì)量代碼被稱為 "Big Code" ，這些數(shù)據(jù)結(jié)合統(tǒng)計(jì)推理或深度學(xué)習(xí)為新興的開發(fā)工具的出現(xiàn)提供了契機(jī)。

概率圖模型：概率圖模型是用圖來表示變量概率依賴關(guān)系的理論，結(jié)合概率論與圖論的知識(shí)，利用圖來表示與模型有關(guān)的變量的聯(lián)合概率分布。

問題

為了項(xiàng)目的安全，開發(fā)者在打包發(fā)布項(xiàng)目時(shí)會(huì)對(duì)代碼進(jìn)行混淆加密，包括但不限于用無意義的短變量去重命名類、變量、方法，以免代碼被輕易破解泄露。另外由于JS腳本主要用于Web開發(fā)，對(duì)其進(jìn)行混淆還能壓縮腳本的大小，使得瀏覽器下載、加載更加快速，提升用戶的瀏覽體驗(yàn)。

這一類通過對(duì)類、變量、方法重命名的混淆方案確實(shí)能加大其他開發(fā)者對(duì)代碼的理解難度。其他開發(fā)者不干了，為了能方便理解他人混淆后的代碼，學(xué)習(xí)（抄襲）他人的經(jīng)驗(yàn)，針對(duì)這一類混淆方法的反混淆方法也應(yīng)運(yùn)而生。

下面先展示一下安卓APP的代碼混淆技術(shù)：

經(jīng)過混淆的代碼在功能上是沒有變化的，但是去掉了部分名稱中的語義信息。因?yàn)榉N種限制，這類混淆也不可能對(duì)所有的名稱都進(jìn)行替換。上圖中的SQLiteHelper、SQLiteDatabase和Cursor就是一個(gè)證明，這些名稱都是安卓API，如果將這些類名混淆會(huì)影響代碼的功能。

理論上一個(gè)有經(jīng)驗(yàn)的安卓開發(fā)者可以在這些有限的提示下為所有的名稱找到富含語義的表示，所以反混淆只需要一個(gè)有經(jīng)驗(yàn)的開發(fā)者（有經(jīng)驗(yàn)的開發(fā)者：？？？我做錯(cuò)了什么）。退一步，找不到有經(jīng)驗(yàn)的開發(fā)者怎么辦，沒關(guān)系，GitHub有高質(zhì)量的各種項(xiàng)目，現(xiàn)訓(xùn)練一個(gè)有經(jīng)驗(yàn)的開發(fā)者也行。不過為了人道主義，消滅996剝削，程序員表示可以用程序代替人，正好可以用GitHub數(shù)據(jù)訓(xùn)練一個(gè)程序做這個(gè)反混淆嘛！理論存在，實(shí)踐開始。

JSNice^[1]

用程序代替人其實(shí)并不簡單，針對(duì)上圖中的反混淆問題，程序需要具有“聯(lián)想”和“推理”能力，比如從a extends SQLiteHelper這一句中，a應(yīng)該很可能也是Helper類，結(jié)合類中有SQLiteDatabase實(shí)例推理出比較符合a的語義的類名是DBHelper。

針對(duì)以上兩點(diǎn)，程序需要先有關(guān)系的概念，能從一個(gè)詞“聯(lián)想”到另一個(gè)詞，然后還要有推理的能力，能通過約束從幾個(gè)候選詞中找到最符合的那個(gè)詞。怎么做這個(gè)事呢？雖然有很多的未混淆的JS腳本供程序?qū)W習(xí)，但在反混淆JS腳本時(shí)，程序無法理解復(fù)雜的JS腳本，所以需要將JS腳本表示成一種可以利用已知屬性推理未知屬性的結(jié)構(gòu)，JSNice采用了概率圖模型。

概率圖模型相比其他學(xué)習(xí)算法的優(yōu)勢在于可以利用圖結(jié)構(gòu)將已知信息帶入知識(shí)網(wǎng)絡(luò)，在使用概率圖模型之前，往往要求圖結(jié)構(gòu)是已知的?，F(xiàn)實(shí)中我們沒有這些先驗(yàn)知識(shí)，但是有大量的樣本（未混淆代碼）。通過樣本學(xué)習(xí)出未混淆JS腳本的概率圖就是JSNice的核心。

具體到JSNice，這個(gè)工具想要做的是為JS腳本推測名稱（name）和類型（type）。先通過一張圖看看JSNice的推理過程。

由于JSNice推理名稱和推理類型的過程類似，本文就只闡述推理名稱的過程。

1. 確定已知和未知屬性

JS腳本中包含了各類代碼元素（elements）比如變量，常量，類，方法名，域等。對(duì)推理名稱問題，元素的屬性即帶有語義的名稱，一個(gè)需要推理名稱的元素，稱其屬性未知。不需要推理名稱的元素其屬性已知。首先需要確定JS腳本中的元素屬性是否已知。很容易看出圖2(a)代碼中屬性已知的元素包括：常量0和[]、feild名稱length和方法名稱push，其他的局部變量如e，t，n，r和i的屬性都是未知的。

將問題泛化，如何判斷任意的JS腳本中的任意元素的屬性是否已知是需要解決的第一個(gè)問題。JSNice采用程序分析和人工指定的方式確定元素屬性是否已知，簡單來說，JSNice認(rèn)為JS腳本中的常量(constants)、對(duì)象屬性名(objects properties)、方法名(methods)和全局變量名(global variables)都是屬性已知的元素，而所有的局部變量的屬性都是未知的。值得注意的是JSNice將對(duì)象屬性名稱和API名稱直接看做是常量。這個(gè)劃分是否合理暫不去討論，但是其確實(shí)適用與大部分的JS腳本。有興趣的讀者可以自行研究。

2. 建立依賴網(wǎng)絡(luò)

第一步獲取了JS腳本中的所有元素（屬性已知或未知），接下來需要建立元素之間的關(guān)系，好方便后續(xù)的推理；圖2(c)中簡單的給出了一些關(guān)系，比如"var r = e.length"中可以得到(r, length, L=_.R)的關(guān)系。

JSNice實(shí)際考慮的元素關(guān)系十分復(fù)雜，主要有三類，這里簡單的進(jìn)行描述：

• 句法關(guān)系，這一類關(guān)系主要通過AST得到，例子如下：

這類關(guān)系的形式化定義如下

• 別名關(guān)系，這類關(guān)系通過standard alias analysis得到，將方法調(diào)用時(shí)傳入的arguments和方法聲明時(shí)的parameters進(jìn)行關(guān)聯(lián)，形成ARG_TO_PM關(guān)系。
• 函數(shù)名稱關(guān)系，由于JS的語言特性，很多的局部變量本身是方法定義，MAY_CALL和MAY_ACCESS表示一個(gè)方法的可能調(diào)用方法關(guān)系和可能訪問對(duì)象域關(guān)系，這類關(guān)系可以通過program analysis得到。

類型推理采用的關(guān)系有所不同，但這里也不再詳述，有興趣的讀者直接移步原文。

3. 訓(xùn)練和推理

現(xiàn)在整理一下對(duì)某個(gè)JS腳本x進(jìn)行上述兩步分析能得到什么？得到了一個(gè)依賴網(wǎng)絡(luò)  ，其中  為節(jié)點(diǎn)集，分別表示未知（unknow）屬性元素和已知屬性元素。  為邊集，表示兩個(gè)程序元素之間的關(guān)系以及關(guān)系類型。

現(xiàn)在不去考慮訓(xùn)練的過程，直接看一下推理過程，JSNice采用貪婪算法，對(duì)未知屬性元素遍歷其所有的屬性可能，尋找到使score最大的屬性作為結(jié)果。

具體的算法如下：

JSNice在具體實(shí)現(xiàn)時(shí)對(duì)算法有所優(yōu)化，但是其基本思想和主要框架都沒變。其實(shí)對(duì)比前文提到人進(jìn)行反混淆時(shí)需要的“聯(lián)想”和“推理”兩種能力，candidates函數(shù)擔(dān)負(fù)了“聯(lián)想”的重任，利用scoreEdges函數(shù)對(duì)不同的候選屬性計(jì)算score并選擇最大score對(duì)應(yīng)屬性的過程就是”推理“。

將圖2的推理部分摘出來看：

r的candidates有l(wèi)en和length，t的candidates有step、j和q，i的candidates只有i。推理得到的(r、i、t)的屬性是(len、i、step)而不是(length、i、step)；是因?yàn)榍罢叩木C合score是0.4+0.8+0.5=1.7，而后者的綜合score只有0.5+0.6+0.5=1.6。

那么怎么得到scoreEdges和candidates函數(shù)呢？

JSNice定義了一個(gè)條件隨機(jī)場：

x為給定某個(gè)JS腳本，y為未知屬性元素（復(fù)數(shù)）的任意分配屬性，score為指示屬性y和腳本x的匹配程度的函數(shù)，其返回值為實(shí)數(shù)，值越大越匹配。

Z是對(duì)應(yīng)JS腳本x的一個(gè)懲罰系數(shù)，用來保證其Pr和為1

將score定義為k個(gè)特征函數(shù)的加權(quán)平均，得到

最終條件隨機(jī)場的表示形式為：

寫到這里，出現(xiàn)了第一個(gè)問題，score為k個(gè)特征函數(shù)的加權(quán)平均，如何確定k呢？

JSNice是在訓(xùn)練階段的預(yù)處理步驟得到k的，實(shí)際上不僅僅這一步不僅獲得了k，還直接定義了k個(gè) pairwise feature functions  。

往前回一步，本文前面一直說GitHub有未混淆的代碼可供概率圖模型學(xué)習(xí)，這里定義訓(xùn)練集  由t個(gè)未混淆的JS腳本組成。對(duì)  中的任意  元組，JSNice定義其特征的集合為

整個(gè)訓(xùn)練集的所有特征集為

JSNice直接定義pairwise feature functions為每個(gè)特征三元組

的指示函數(shù)：

所以訓(xùn)練集有多少特征三元組，k的值就有多大。

但說了這么多，還是沒有提到scoreEdges和candidates。別急，直接定義

如此把前面的公式都串起來了，整個(gè)公式組其實(shí)只有  是未知，條件隨機(jī)場的訓(xùn)練過程其實(shí)就是計(jì)算  的過程。

至于candidates，假設(shè)現(xiàn)在概率圖模型中的  已經(jīng)訓(xùn)練完成，根據(jù)前面的定義，  和  其實(shí)是一一對(duì)應(yīng)的，  本身是特征三元組的指示函數(shù)，也和三元組一一對(duì)應(yīng)，所以可以使用權(quán)重  直接限制節(jié)點(diǎn)  的可能取值。定義  函數(shù)對(duì)輸入的特征三元組集合基于此權(quán)重返回top s的三元組。定義  。定義如下輔助函數(shù)：

最后：

candidates函數(shù)其實(shí)就是先在  中找到和  有  關(guān)系的  ，然后利用  和  在訓(xùn)練集中找到和  最相似的詞作為候選。比較方便的是輔助函數(shù)其實(shí)可以在預(yù)測之前提前計(jì)算并緩存下來。

由于筆者本身沒有不研究概率圖模型，所以訓(xùn)練模型得到  的內(nèi)容就省略了，有興趣的讀者可以閱讀原文^[1]，本文只簡單的描述：

JSNice采用判別式訓(xùn)練，由于最大似然需要計(jì)算  ，JSNice采用max-margin training，使用Structured Support Vector Machine (SSVM)并用scalable subgradient descent algorithm優(yōu)化。

Deguard^[2]

相對(duì)JSNice做的對(duì)JS腳本進(jìn)行反混淆，Deguard對(duì)安卓APK做反混淆的難度要大了很多，放在眼前的一個(gè)問題就是項(xiàng)目規(guī)模，JSNice的應(yīng)用scope其實(shí)是Web上的JS腳本，考慮網(wǎng)站的加載等限制，單個(gè)JS腳本必不會(huì)太大，而安卓APK不同，由于安卓本身事件驅(qū)動(dòng)的編程方式，一個(gè)簡單的安卓APK的復(fù)雜度可能就能比得上十分復(fù)雜的JS腳本。并且安卓APK的大小一般也沒有限制。

還有一些安卓或者說Java需要的約束是建模時(shí)需要考慮的，比如一個(gè)Java類中的feilds名稱必須不一樣，一個(gè)package中的classes名稱必須不一樣。不滿足這些約束，對(duì)APK進(jìn)行反混淆的結(jié)果就失去了其實(shí)用性。

考慮到安卓application的復(fù)雜性，選取合適的粒度建模是首要的問題，關(guān)系過于復(fù)雜不利于概率圖模型的學(xué)習(xí)，關(guān)系過于簡略可能導(dǎo)致無法預(yù)測準(zhǔn)確的屬性，必須有一個(gè)權(quán)衡。

1. 確定程序元素（圖的節(jié)點(diǎn)  ）

要為安卓APK定義一個(gè)依賴圖，首先確定圖上的節(jié)點(diǎn)，Deguard考慮了APK中的如下元素：

• Types，不管是基本類型(int, long, float)，引用類型(Object, ArrayList)，還是數(shù)組類型(int[], Object[])都能做為節(jié)點(diǎn)
• Feilds，APK中的任意類中定義的任意Feild都能做為節(jié)點(diǎn)
• Packages，APK中的任意package能做為節(jié)點(diǎn)，像package a.b就可以做為兩個(gè)節(jié)點(diǎn)，a和a.b。
• Methods，APK中的任意方法都能做為節(jié)點(diǎn)，但是如果有overrides關(guān)系，那么子類和父類的method公用一個(gè)節(jié)點(diǎn)表示。
• Constant values and null
• Access Modifiers，比如static，synchronized
• Operations

這里沒有考慮Java語言中的泛型機(jī)制是因?yàn)樵诰幾g過程中會(huì)消除泛型，APK本身就是編譯過后的文件。另外和JSNice不一樣的是，Deguard沒有考慮局部變量名和參數(shù)名，但考慮了局部變量的類型和參數(shù)的類型，一方面減少規(guī)模，另一方面就是變量名和參數(shù)名本身不在APK中。

2. 確定元素屬性是否已知

這里將元素屬性定義為節(jié)點(diǎn)是否被混淆，屬性已知說明節(jié)點(diǎn)名稱未被混淆，不需要預(yù)測名稱，屬性未知說明節(jié)點(diǎn)名稱已被混淆，需要預(yù)測名稱。

已知屬性元素包括

• 節(jié)點(diǎn)如果代表pakages，classes，methods和feilds且在安卓API中，那么這些節(jié)點(diǎn)是已知的，因?yàn)榛诿Q的混淆工具并不會(huì)混淆這些名稱
• 構(gòu)造函數(shù)名稱都是已知的
• 節(jié)點(diǎn)代表對(duì)安卓API方法重寫的方法也是已知的，因?yàn)榍拔囊呀?jīng)提過，重寫關(guān)系其實(shí)是用一個(gè)節(jié)點(diǎn)表示。

剩下的元素都是未知的，需要預(yù)測名稱

3. 構(gòu)建依賴網(wǎng)絡(luò)

Deguard用一張圖詳細(xì)描述了其用于構(gòu)建依賴網(wǎng)絡(luò)的關(guān)系

相對(duì)JSNice中大部分的關(guān)系來自AST，Deguard選擇的關(guān)系明顯融合進(jìn)了人的經(jīng)驗(yàn)，更加的抽象。實(shí)際上本文的精華也是這一張圖，某種程度上這圖中展現(xiàn)出來了人類對(duì)具體問題具體分析的思考，而不是僅僅簡單的復(fù)用已有工作提出的各種關(guān)系。

剩下的內(nèi)容比如模型的訓(xùn)練和推理其實(shí)和JSNice差不多，這里不會(huì)重復(fù)一遍，后續(xù)會(huì)講不一樣的地方，也就是Deguard如何處理Java程序帶來的關(guān)于各種名稱的約束。

Java中的名稱約束還是比較復(fù)雜的，這里拿一個(gè)例子講一下：

1. A.a(A)沒有任何約束，因?yàn)锳作為參數(shù)的方法只有它一個(gè)
2. A.b(Object)不能被重命名為equals，因?yàn)檫@樣會(huì)override java.lang.Object.equals(Object)
3. B.g()和B.h()方法重命名名稱必須不一樣，因?yàn)檫@兩方法的特征一樣
4. B.g()和A.c()方法重命名名稱必須不一樣，如果一樣就是隱式的繼承
5. B.h()和A.c()方法重命名名稱必須不一樣，也是由于method overriding的原因
6. C.x()和B.h()卻沒有沖突，因?yàn)锽.h()是private的

相等約束（繼承重寫機(jī)制）可通過共用節(jié)點(diǎn)表示，不等約束也需要明確表示，所以Deguard提出了一個(gè)檢測方法名稱不等約束的算法

其他元素，比如類名，F(xiàn)eilds名稱的不等約束比較簡單，直接處理就行。

所有不等約束以集合  表示，  ，  中任意兩個(gè)節(jié)點(diǎn)的名稱必須不一樣。

注意這個(gè)約束只用與預(yù)測階段，因?yàn)橛?xùn)練數(shù)據(jù)（未混淆）本身滿足這些約束。很容易可以把這些約束結(jié)合到JSNice的算法1中。

Deguard的概率圖優(yōu)化算法和JSNice也不一樣，采用的是pseudo likelihood estimation。具體闡述推薦閱讀文章^[3]。

值得注意的是，為什么JSNice就沒有Deguard中提到的相等約束和不等約束，筆者個(gè)人認(rèn)為還是由問題和語言特性共同決定，JSNice的名稱預(yù)測其實(shí)只預(yù)測了局部變量，而JS的語言特性導(dǎo)致其本身不需要檢測局部變量的名稱沖突，只有執(zhí)行結(jié)果報(bào)錯(cuò)才會(huì)說明程序出錯(cuò)。也就是說其實(shí)JS本身語言特性就沒有這類約束，自然不需要建模。

總結(jié)

提出JSNice和Deguard的兩篇文章算是基于 "Big Code" 的較早的研究了，這兩個(gè)工具現(xiàn)在還在維護(hù)并可用（JSNice^[4]、Deguard^[5]）也證明了基于 "Big Code" 的研究和工具確實(shí)是可行可信有前途的。

從文章的研究思路來看，基于 "Big Code" 的研究首先需要判斷："Big Code"能夠做到什么和做出來的東西能不能make sense兩個(gè)問題。分享的兩篇文章能夠發(fā)表就在于大家相信基于已有開源項(xiàng)目做反混淆這件事是合理的。

另外一個(gè)就是找到問題本身和建模并解決問題同等重要甚至更加重要。這兩篇文章其實(shí)都是做的一件事，就是做代碼命名推薦。而作者能夠在命名推薦這個(gè)大的領(lǐng)域內(nèi)（領(lǐng)域太大），找到完整程序的代碼命名推薦（難以入手，沒有已知）問題，再進(jìn)一步縮小Scope到基于部分已知命名的完整程序的代碼命名推薦（可以做，"Big Code"可以支持）這件事，這個(gè)范圍內(nèi)還正好有兩個(gè)應(yīng)用（JS腳本和安卓APK的反混淆）可以支撐研究，真正是十分厲害也比較走運(yùn)。

結(jié)合現(xiàn)在深度學(xué)習(xí)的風(fēng)口，其實(shí)從應(yīng)用的角度來看，模型的復(fù)雜度和創(chuàng)新度并不重要，還是模型和問題本身的契合度更加重要。

參考

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. ^項(xiàng)目地址 http://www.jsnice.org/
5. ^項(xiàng)目地址 http://apk-deguard.com/