国产欧美精品专区一区二区_91www永久在线精品果冻传媒_日韩成人亚洲综合专区无码av_欧美激情一区二区三区高清视频_免费福利在线视频亚洲_日韩精品无码人妻自慰喷水_把腿张开老子cao哭你动态图_51a性爱高清免费视频_国产无码资源在线观看資源免費看_再深点灬舒服灬太大了网站

背景

代碼反混淆（deobfuscation）和代碼混淆（obfuscation）對應(yīng)，是其逆過程。維基百科將代碼混淆定義為故意生成人類難以理解的源代碼或機器碼的過程（"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)用。更具體一點就是介紹一下提出 "JSNice" 和 "Deguard" 的兩篇文章，這兩篇文章雖然已經(jīng)發(fā)表快五年了，但至今沒有文章Follow這兩份工作，因為文章已經(jīng)將使用 "Big Code" 做代碼命名反混淆做到了極致。后來的人無法在這個問題上推陳出新，脫穎而出。

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

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

問題

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

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

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

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

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

JSNice^[1]

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

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

概率圖模型相比其他學(xué)習(xí)算法的優(yōu)勢在于可以利用圖結(jié)構(gòu)將已知信息帶入知識網(wǎng)絡(luò)，在使用概率圖模型之前，往往要求圖結(jié)構(gòu)是已知的。現(xiàn)實中我們沒有這些先驗知識，但是有大量的樣本（未混淆代碼）。通過樣本學(xué)習(xí)出未混淆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認(rèn)為JS腳本中的常量(constants)、對象屬性名(objects properties)、方法名(methods)和全局變量名(global variables)都是屬性已知的元素，而所有的局部變量的屬性都是未知的。值得注意的是JSNice將對象屬性名稱和API名稱直接看做是常量。這個劃分是否合理暫不去討論，但是其確實適用與大部分的JS腳本。有興趣的讀者可以自行研究。

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

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

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

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

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

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

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

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

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

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

具體的算法如下：

JSNice在具體實現(xiàn)時對算法有所優(yōu)化，但是其基本思想和主要框架都沒變。其實對比前文提到人進行反混淆時需要的“聯(lián)想”和“推理”兩種能力，candidates函數(shù)擔(dān)負(fù)了“聯(lián)想”的重任，利用scoreEdges函數(shù)對不同的候選屬性計算score并選擇最大score對應(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)；是因為前者的綜合score是0.4+0.8+0.5=1.7，而后者的綜合score只有0.5+0.6+0.5=1.6。

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

JSNice定義了一個條件隨機場：

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

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

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

最終條件隨機場的表示形式為：

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

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

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

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

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

的指示函數(shù)：

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

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

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

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

最后：

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

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

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

Deguard^[2]

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

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

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

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

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

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

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

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

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

已知屬性元素包括

• 節(jié)點如果代表pakages，classes，methods和feilds且在安卓API中，那么這些節(jié)點是已知的，因為基于名稱的混淆工具并不會混淆這些名稱
• 構(gòu)造函數(shù)名稱都是已知的
• 節(jié)點代表對安卓API方法重寫的方法也是已知的，因為前文已經(jīng)提過，重寫關(guān)系其實是用一個節(jié)點表示。

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

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

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

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

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

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

1. A.a(A)沒有任何約束，因為A作為參數(shù)的方法只有它一個
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的

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

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

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

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

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

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

總結(jié)

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

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

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

結(jié)合現(xiàn)在深度學(xué)習(xí)的風(fēng)口，其實從應(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. ^項目地址 http://www.jsnice.org/
5. ^項目地址 http://apk-deguard.com/