井 靖 蔣烈輝, 劉鐵銘 司彬彬 曾 韻 朱曉清

軟件逆向分析過程中的多維圖譜抽取方法

井 靖1蔣烈輝1,2劉鐵銘2司彬彬1曾 韻1朱曉清2

1(信息工程大學(xué)計算機科學(xué)與技術(shù)學(xué)院 河南 鄭州 450000)

2(數(shù)學(xué)工程與先進計算國家重點實驗室 河南 鄭州 450000)

由于軟件逆向分析過程中產(chǎn)生的結(jié)果通常是形式化的符號，且復(fù)雜難懂，因此基于軟件逆向分析進行代碼閱讀或漏洞挖掘等工作的效率非常低下。針對這種情況，首先設(shè)計多維圖譜抽取框架，基于該框架定義多維圖譜描述約束(schema)，使多維圖譜抽取與具體的逆向分析過程之間相互獨立；給出逆向分析算法庫的構(gòu)造方式及算法庫調(diào)用接口，實現(xiàn)基于多維圖譜描述的抽象圖譜生成；設(shè)計基于圖形描述語言DOT的抽象圖譜轉(zhuǎn)換接口，實現(xiàn)抽象圖譜的快速可視化；最后給出多維圖譜抽取算法。實驗結(jié)果表明，采用該方法能有效提高逆向分析過程中生成結(jié)果的可讀性，大幅提升分析人員代碼閱讀及漏洞挖掘的工作效率。

多維圖譜 抽取 抽象圖 DOT接口 可視化

0 引 言

目前比較流行的軟件逆向分析算法通常采用基于抽象解釋理論的近似逼近技術(shù)[1,2]。即依據(jù)分析或驗證的實際語義，定義具有完備格屬性的抽象域，基于抽象解釋框架，將被分析的反匯編代碼或中間代碼上的數(shù)據(jù)流分析轉(zhuǎn)換為抽象域上的數(shù)學(xué)運算，并利用抽象域的數(shù)學(xué)特性迭代求解，最終到達語義不動點從而得到較精確的分析結(jié)果。然而這些算法的結(jié)果通常是以純數(shù)據(jù)或者抽象符號的形式給出，往往晦澀難懂，即便是專業(yè)的逆向分析人員，要想從分析結(jié)果中發(fā)現(xiàn)可執(zhí)行代碼的框架、意圖以及漏洞，要花很長的時間，效率非常低下。如果能對各種逆向分析算法進行分類，并按照不同的分析粒度以圖譜的形式顯示出來，將會大大提高逆向分析人員的工作效率。

比較流行的軟件逆向分析工具中(比如IDA、Ollydb、TEMU、Pin等)都或多或少地提供了圖表視圖的功能，為用戶分析代碼結(jié)構(gòu)、挖掘漏洞等提供了重要幫助[3-5]。但這些工具通常提供圖的維數(shù)太少，適用性差，無法為用戶自定義的分析算法生成相應(yīng)的圖。因此，如何將軟件逆向分析算法進行分類，并將圖的生成從具體的逆向分析中獨立出來，使其能夠靈活地為各種分析結(jié)果生成相應(yīng)的圖譜并按照用戶的需求打印出來是本文主要研究的內(nèi)容。

本文首先提出多維圖譜抽取框架，給出基于XML[6]的多維圖譜描述約束，并在此基礎(chǔ)上給出抽象圖譜抽取方法。然后設(shè)計基于DOT[7]的抽象圖轉(zhuǎn)換接口。最后給出圖譜抽取示例及相關(guān)工作比較。

1 研究基礎(chǔ)與內(nèi)容

從狹義上講，多維是指由時間軸和空間坐標軸構(gòu)成的多個獨立的時空坐標；從廣義上講，多維是指按照一定的分類規(guī)則所劃分的不同類別或者不同視角。在本文多維則是指由靜態(tài)和動態(tài)兩種分析模式以及不同代碼分析粒度構(gòu)成的多種逆向分析方法(多種逆向分析維度)。而圖譜抽取則是指從多維度的逆向分析中提取分析結(jié)果，并按照分析人員的需求以自定義圖的形式表示出來。

多維圖譜抽取在軟件逆向分析過程中所處的位置如圖1所示。被分析的代碼首先經(jīng)過多源靜態(tài)反匯編(將基于不同CPU的可執(zhí)行代碼翻譯為對應(yīng)指令集下的匯編代碼)或者多架構(gòu)動態(tài)執(zhí)行引擎(支持不同硬件平臺下可執(zhí)行代碼運行的虛擬機)被翻譯成匯編代碼；然后經(jīng)過代碼語義提升(中間代碼生成)將匯編代碼轉(zhuǎn)換為統(tǒng)一的中間語言代碼；接著基于統(tǒng)一的中間語言代碼；進行多維圖譜抽??；最后基于多維圖譜進行控制結(jié)構(gòu)恢復(fù)、數(shù)據(jù)結(jié)構(gòu)恢復(fù)、代碼架構(gòu)恢復(fù)、惡意行為分析和漏洞挖掘等高級語義分析。

圖1 軟件逆向分析過程

其中多源靜態(tài)反匯編已經(jīng)有很多成熟的工具：比如采用線性掃描算法的BAP[8]、采用遞歸掃描算法的IDA[9]、采用啟發(fā)式掃描算法的各種反匯編工具[10]等；基于QEMU虛擬機[11]的多架構(gòu)動態(tài)執(zhí)行引擎已經(jīng)被成功用于動態(tài)軟件逆向分析工作中；代碼語義提升也有很多實現(xiàn)方法：比如BAP和BitBlaze[12]的中間代碼生成方法、基于語義字典的BRIL中間代碼生成[13]等；多維圖譜抽取是基于中間代碼的分析及結(jié)果提取過程，是實現(xiàn)高級語義快速分析的基礎(chǔ)，也是本文的主要研究內(nèi)容。

2 框架設(shè)計

多維圖譜抽取的框架結(jié)構(gòu)如圖2虛線框部分所示。主要由多維圖譜描述文件、抽象圖譜抽取以及抽象圖轉(zhuǎn)換接口三個模塊組成。多維圖譜描述文件采用基于XML的描述方法，用戶可根據(jù)具體分析要求，自定義抽取圖譜的個數(shù)、樣式以及采用分析算法的名稱等；抽象圖譜抽取按照分析代碼的粒度分別劃分為：語句級、基本塊級、結(jié)構(gòu)級以及過程級等(這里的過程級也可以叫做函數(shù)級，過程指procedure)，負責(zé)調(diào)用具體逆向分析算法、提取抽象結(jié)果以及生成抽象圖譜；抽象圖譜轉(zhuǎn)換接口負責(zé)將生成的抽象圖轉(zhuǎn)換為圖形描述語言DOT的描述形式，并傳遞給下層的DOT解析器，最終由DOT解析器將其轉(zhuǎn)換為實際的圖形打印在屏幕上。

圖2 多維圖譜抽取框架

3 模塊設(shè)計

3.1 基于XML的多維圖譜描述

XML是一種可擴展的元標記語言，被廣泛應(yīng)用于數(shù)據(jù)交換、異構(gòu)系統(tǒng)的整合及系統(tǒng)配置等領(lǐng)域中，獨立于任何軟硬件平臺。為了實現(xiàn)圖譜顯示與分析算法之間的相互獨立性，我們利用基于XML的描述文件對要生成圖譜的維數(shù)、樣式、采用的算法等屬性進行描述，并設(shè)計了多維圖譜描述文件的schema，利用XMLSpy 2011生成的多維圖譜描述文件的schema概要圖如圖3所示。

圖3 多維圖譜描述約束概要圖(schema)

其中g(shù)raph為描述文件的根元素；static和dynamic為graph的子元素，分別用來描述靜態(tài)圖譜和動態(tài)圖譜的屬性；instruction、baseblock、structure和procedure子元素分別用來描述指令級、基本塊級、結(jié)構(gòu)級以及過程級圖譜的相關(guān)屬性；algoname、algoaddr、style子元素則用來描述圖譜所選用的算法名稱、算法地址、顯示圖譜的樣式等；node和edge是style的子元素，color和shape分別用來描述結(jié)點和邊的顏色以及形狀屬性。

說明1：圖中dynamic元素的結(jié)構(gòu)與static元素的類似，但是比static元素多了一個trace屬性，用于指定動態(tài)執(zhí)行的指令序列；

說明2：baseblock、structure和procedure元素的結(jié)構(gòu)與instruction元素的類似，元素右側(cè)的加號表示未展開；

說明3：虛線框的元素或?qū)傩员硎臼强蛇x的，在描述文件中不是必須被定義的。

3.2 基于圖譜描述的抽象圖譜抽取

按照被分析對象的來源，抽象圖譜抽取可劃分為靜態(tài)和動態(tài)兩大類。靜態(tài)抽象圖譜抽取基于靜態(tài)反匯編或代碼語義提升得到的中間代碼，利用傳統(tǒng)的前向、后向數(shù)據(jù)流分析，或者面向某個抽象域的抽象解釋框架，對被分析代碼進行不同粒度的迭代求解[14,15]。動態(tài)抽象圖譜抽取基于動態(tài)執(zhí)行引擎(比如pin for x86、Qemu、TEMU for x86、DroidScope for arm[16]等)記錄的虛擬執(zhí)行序列，即指令流或經(jīng)過代碼語義提升的中間代碼序列，采用不同粒度的逆向分析算法進行數(shù)據(jù)流分析。

抽象圖譜抽取模塊主要由算法庫和算法庫調(diào)用接口兩部分構(gòu)成。算法庫由目前已經(jīng)比較成熟的逆向分析算法構(gòu)成，按照分析的粒度進行劃分，主要包括語句級算法庫、基本塊算法庫、結(jié)構(gòu)級算法庫和過程級算法庫。算法庫調(diào)用接口根據(jù)圖譜描述文件中static元素以及dynamic元素所描述的屬性，比如子元素的個數(shù)以及每個子元素下algoname以及algoaddr元素描述的算法名稱和算法地址等，依次調(diào)用對應(yīng)的算法進行靜態(tài)分析，完成抽象圖譜的抽取；并將各自style元素定義的屬性傳遞給下層的DOT轉(zhuǎn)換接口。常用的調(diào)用接口定義如表1所示，表1中的接口參數(shù)algoname和algoname_list均由圖譜描述文件中定義過的algoname屬性值來確定。

表1 常用算法庫調(diào)用接口

由于算法庫中包括的算法多樣，分析的粒度越小，圖的復(fù)雜程度通常越高。此外動態(tài)抽象圖譜只針對代碼的一條執(zhí)行路徑，對于不同執(zhí)行路徑生成的動態(tài)抽象圖譜反映了不同路徑下的分析結(jié)果。所以為了方便分析人員的觀察和閱讀，描述文件中的mix屬性和layer屬性分別對生成圖的模式進行了限定，并根據(jù)這些屬性調(diào)用不同的接口函數(shù)。當mix=1時，表示可以混合顯示，即將不同維度(粒度)的圖合并為一幅大圖，調(diào)用mix_*_abs_graph()函數(shù)；mix=0表示不同維度的圖將分別獨立顯示，調(diào)用single_*_abs_graph()函數(shù)。此外，當layer=-1時，hight=-1，表示顯示完整的圖；layer=n(n∈N)時，hight=N，表示顯示到圖的高度最多至第n層。

3.3 基于DOT 的抽象圖譜轉(zhuǎn)換接口

DOT是一種圖形描述語言，它提供了一種簡單的圖形描述方法，很容易被人和計算機程序理解，具體的語法規(guī)范可以參考文獻[7]。DOT語言也可以看做是一種腳本語言，由專門的DOT解釋程序來解釋執(zhí)行，比如GraphViz就是一組用于處理dot文件的開源工具包[7]。它既可以作為獨立的軟件來使用，也可以作為庫被其他應(yīng)用程序調(diào)用。下面是一個簡單的dot描述示例：

digraph sample{

A [shape=box];

A->B->D;

A->C->F;

B->E [style=dotted];

D->A [style=dotted];

}

圖4是針對上述dot描述文件使用GraphViz工具解釋執(zhí)行后顯示的圖形。

圖4 GraphViz解釋后生成的圖

經(jīng)過靜態(tài)、動態(tài)圖譜抽取模塊得到的抽象圖通常只含有節(jié)點以及邊的關(guān)系，即結(jié)點集合N和邊結(jié)合E，不利于用戶的查看和分析。設(shè)計DOT接口可以將這些抽象圖(結(jié)點集合、邊集合)自動轉(zhuǎn)化為DOT描述文件，從而調(diào)用DOT解釋器實現(xiàn)多維圖譜的可視化。DOT接口API定義如表2所示。

表2 DOT轉(zhuǎn)換接口列表

4 多維圖譜抽取算法

基于多維圖譜抽取框架以及各個模塊定義的接口函數(shù)，設(shè)計多維圖譜抽取算法。該算法以多維圖譜描述文件Spec_Xml以及被分析代碼來源Code_Source為輸入?yún)?shù)，以多維圖譜GRAPHS為輸出結(jié)果，具體的算法偽代碼如下所示：

算法1 多維圖譜抽取算法

輸入 Spec_Xml，Code_Source

輸出 Graphs

Proc Di_Graphs_Extract (Spec_Xml, Code_Source)

If (Code_Source is static)

mixed=Get_ Attribut _Value(static, mix);

If (Spec_Xml->static->instruction is not null)

Graph[0]=instruction;

End If

If (Spec_Xml->static->baseblock is not null)

Graph[1]= baseblock;

End If

If (Spec_Xml->static->structure is not null)

Graph[2]= structure;

End If

If (Spec_Xml->static->procedure is not null)

Graph[3]= procedure;

End If

For (i=0; i<4; i++) do

layer= Get_Attribut_Value(Graph[i], layer);

algoname=Get_Child_Value(Graph[i], algoname);

algoaddr= Get_Child_Value(Graph[i], algoaddr);

style->node.color=

Get_ Attribut _Value(Graph[i]->style->node, color);

style->node.shape=

Get_ Attribut _Value(Graph[i]->style->node, shape);

Style->edge.color=

Get_ Attribut _Value(Graph[i]->style->edge, color);

Style->edge.shape=

Get_ Attribut _Value(Graph[i]->style->edge, shape);

(N, E)= Static_Abs_Graph (algoname, algoaddr);

dot_node_attr=node_attr(style.node);

dot_edge_attr=edge_attr(style.edge);

dot_edges=edge_to_edge( E );

dot_file=create_cot_file(dot_node_attr, dot_edge_attr, dot_edges, mixed);

GraphViz(dot_file);

//調(diào)用dot文檔解析器

End For

End If

If (Code_Source is dynamic trace)

Similar to static;

//與靜態(tài)代碼的處理方法類似

End If

End Proc

設(shè)被分析代碼是靜態(tài)的中間語句，且語句級、基本塊級、結(jié)構(gòu)級以及過程級抽象圖生成算法的最大復(fù)雜度為K，抽象圖的邊的最大數(shù)目為e，轉(zhuǎn)換為dot文檔后的語句最大條數(shù)為d，則通過分析算法可以得靜態(tài)多維圖譜抽取算法的最大復(fù)雜度為C≈O(K+e+d)。

證明：

靜態(tài)語句級Get_Abs_Graph()的復(fù)雜度c11與algoname算法的復(fù)雜度相關(guān)；edge_to_edge()的復(fù)雜度c12與抽象圖邊的條數(shù)相關(guān)；Create_Dot_Document()的復(fù)雜度c13也與抽象圖邊的條數(shù)相關(guān)；GraphViz()的復(fù)雜度c14與dot文件中的語句條數(shù)相關(guān)。

設(shè)語句級抽象算法復(fù)雜度為k1，抽象圖(N, E)邊的條數(shù)為e1，dot文件中的語句條數(shù)為d1，則語句級靜態(tài)圖譜抽取的復(fù)雜度為：

C1=c11+c12+c13+c14=k1+e1+e1+d1=k1+2e1+d1

同理，基本塊級、結(jié)構(gòu)級和過程級的靜態(tài)圖譜抽取復(fù)雜度分別為：

C2= c21+c22+c23+c24=k2+e2+e2+d2=k2+2e2+d2

C3= c31+c32+c33+c34=k3+e3+e3+d3=k3+2e3+d3

C4= c41+c42+c43+c44=k4+e4+e4+d4=k4+2e4+d4

因為K=max(k1, k2, k3, k4)，e=max(e1, e2, e3, e4)，d=max(d1, d2, d3, d4)。

則靜態(tài)圖譜抽取的最大復(fù)雜度為：

C=C1+C2+C3+C4≈4K+8e+4d≈O(K+e+d)

說明：上述結(jié)論是以靜態(tài)圖譜抽取部分的復(fù)雜度為例，動態(tài)圖譜抽取的算法與靜態(tài)類似。只是抽象圖生成算法的復(fù)雜度以及抽象圖邊的條數(shù)，dot文檔的語句條數(shù)與靜態(tài)圖譜的不同，可以得到相類似的結(jié)論。

5 實驗方法與測試

為了驗證多維圖譜抽取算法的有效性，和時間復(fù)雜度，課題組搭建嵌入式二進制分析平臺EBAP[15]作為多維靜態(tài)圖譜抽取的前端?；赒EMU搭建動態(tài)信息提取系統(tǒng)作為動態(tài)圖譜提取的前端，以基于BRIL[13]中間語言的中間代碼和中間代碼序列作為靜態(tài)圖譜抽取和動態(tài)圖譜抽取的對象。

實驗機型為聯(lián)想ThinkCentre M8400s，處理器為Intel酷睿i5 2400，8 GB內(nèi)存，主機操作系統(tǒng)為Windows 7，將源程序test1.cpp～test5.cpp經(jīng)過gcc4.4.3編譯得到測試程序test for x86系列test1.exe～test5.exe，將源程序test1.cpp/test2.cpp/test3.cpp經(jīng)過arm-linux-gcc-4.4.3交叉編譯得到test for arm系列test1/test2/test5。選用基于抽象解釋的數(shù)據(jù)依賴分析算法(語句級)、精度可調(diào)的控制流圖恢復(fù)算法(基本塊級)[15]、基于結(jié)構(gòu)語義樹的高級控制結(jié)構(gòu)恢復(fù)算法(結(jié)構(gòu)級)[13]等各粒度的算法構(gòu)建算法庫，編寫圖譜描述文件，并調(diào)用算法1進行測試。

測試的部分結(jié)果如圖5-圖7所示。其中test1.exe語句級靜態(tài)圖譜抽取結(jié)果如圖5所示，test2.exe基本塊級與結(jié)構(gòu)級以普通混合模式顯示的靜態(tài)圖譜結(jié)果如圖6所示，test3.exe過程級最大高度hight=6的靜態(tài)圖譜結(jié)果如圖7所示。

圖5 語句級靜態(tài)分析圖

圖6 基本塊和結(jié)構(gòu)級靜態(tài)分析圖

圖7 過程級靜態(tài)分析圖

由圖可以看到，經(jīng)過多維圖譜抽取算法得到的結(jié)果使語句級的依賴關(guān)系、基本塊間的控制流轉(zhuǎn)關(guān)系、高級控制結(jié)構(gòu)的構(gòu)成方式以及函數(shù)間的調(diào)用關(guān)系一目了然。大大提高了分析人員閱讀代碼的工作效率，為下一步進行關(guān)鍵區(qū)域的漏洞挖掘等安全性分析工作提供了方向性的指導(dǎo)。

多維圖譜抽取的時間性能測試如表3和表4所示。

表3 靜態(tài)圖譜抽取時間性能測試結(jié)果

表4 動態(tài)圖譜抽取時間性能測試結(jié)果

由測試結(jié)果可以發(fā)現(xiàn)，動態(tài)抽取的中間代碼語句條數(shù)比靜態(tài)分析下得到的要多，而靜態(tài)圖譜抽取的時間卻比動態(tài)圖譜提取的時間要長，原因如下：

1) 動態(tài)圖譜提取測試針對中間代碼序列的一次運行過程，在運行時會將循環(huán)結(jié)構(gòu)的代碼按照實際的循環(huán)次數(shù)進行展開，故其語句條數(shù)通常會比靜態(tài)分析得到的要多；

2) 動態(tài)圖譜因為其語句級依賴關(guān)系、基本塊之間的控制關(guān)系、結(jié)構(gòu)關(guān)系以及函數(shù)間的調(diào)用關(guān)系是確定的，比較簡單，這使得抽象圖譜生成算法可以迅速到達不動點，因此整個圖譜的抽取也就會比靜態(tài)圖譜抽取的速度要快。

另外測試結(jié)果中的時間性能還與采用的算法庫中的抽象圖譜生成算法的復(fù)雜度密切相關(guān)，選用的算法復(fù)雜度越高，圖譜抽取所需的時間就越長。

6 結(jié) 語

目前常用的其他逆向分析工具，比如IDA、Ollydb等，都僅提供基于某種特定靜態(tài)匯編代碼的語句級、基本塊級、過程級的結(jié)構(gòu)圖。當用戶基于匯編代碼采用其他逆向分析算法進行分析的時候，無法幫用戶更新這些結(jié)構(gòu)圖，不方便分析人員的分析和比較。多維圖譜抽取技術(shù)實現(xiàn)了圖譜生成與逆向分析算法的獨立，即當采用的逆向分析算法發(fā)生變化的時候，只需要修改圖譜描述文件中對應(yīng)維度下算法元素的名稱和地址屬性，就可以自動生成對應(yīng)算法的實際圖形。分析人員不需要關(guān)心具體圖形是如何顯示的。

下一步需要完成的工作主要有：完成圖譜復(fù)雜混合模式的顯示功能，增強不同粒度之間圖譜的對比性和關(guān)聯(lián)性，尤其是基本塊級、結(jié)構(gòu)級與過程級之間的關(guān)聯(lián)性；實現(xiàn)復(fù)雜圖譜的部分以及連續(xù)顯示，更加方便用戶的閱讀和分析；完成基于不同抽象圖譜提取算法的時間性能測試及比較，為用戶算法選擇提供參考；另外基于多維圖譜的惡意行為檢測技術(shù)和漏洞挖掘技術(shù)等也是我們進一步重點研究的內(nèi)容。

[1] JeanLouis Boulanger.Static analysis of software:The abstract interpretation[M].Hoboken:Wiley Press,2013.

[2] Patrick Cousot,Radhia Cousot.Abstract interpretation:a unified lattice model for static analysis of programs by construction or approximation of fixpoints[C]//Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on principles of programming languages,Los Angeles,California,1977:238-252.

[3] 李永偉.基于Hex-Rays的緩沖區(qū)溢出漏洞挖掘技術(shù)研究[D].鄭州:解放軍信息工程大學(xué),2013.

[4] 焦永生,舒輝.基于TEMU的進程間通信過程逆向[J].計算機應(yīng)用研究,2013,30(7):2091-2095.

[5] Heng Yin,Dawn Song.TEMU:Binary Code Analysis via Whole-System Layered Annotative Execution[EB/OL].(2012-10-11).[2014-09-11].http://www.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-3.html.

[6] XML可擴展標記語言[EB/OL].(2014-08-20).[2014-09-11].http://zh.wikipedia.org/zh-cn/XML.

[7] Dot language[EB/OL].(2014-09-11).[2014-09-11].http://www.graphviz.org/content/dot-language.

[8] David Brumley,Ivan Jager,Thanassis Avgerinos,et al.BAP:A Binary Analysis Platform[C]//Proceedings of the conference on computer aided verification,2011:1-7.

[9] IDA:About[EB/OL].(2014-01-25).[2014-09-11].https://www.hex-rays.com/products/ida/index.shtml.

[10] 吳偉民,司斯,阮奕邦,等.基于函數(shù)劃分塊及置信度的反匯編優(yōu)化研究[J].計算機應(yīng)用與軟件,2014,31(1):85-88,164.

[11] QEMU Internals[EB/OL].(2014-08-01).[2014-09-11].http://qemu.weilnetz.de/qemu-tech.html.

[12] Dawn Song,David Brumley,Heng Yin,et al.BitBlaze:A New Approach to Computer Security via Binary Analysis[C]//Proceedings of the 4th international conference on information systems security,Hyderabad,India,2008:1-25.

[13] 劉絮穎.反編譯中控制流重構(gòu)與控制結(jié)構(gòu)恢復(fù)技術(shù)研究[D].鄭州:信息工程大學(xué),2010.

[14] 邢雨辰.用于程序驗證的數(shù)據(jù)流分析技術(shù)的整合[D].南京:南京大學(xué),2013.

[15] Jing Jing,Jiang Liehui,Liu Tieming,et al.A Precision tunable CFG Reconstruction Algorithm[C]//Proceedings of international conference on Mechatronic sciences,Electric engineering and Computer,Shenyang,China 2013:2095-2099.

[16] Lok Kwang Yan,Heng Yin.DroidScope:Seamlessly Reconstructing the OS and Dalvik Semantic Views for Dynamic Android Malware Analysis[C]//Proceedings of the 21st USENIX Security Symposium,2012:1-16.

MULTIDIMENSIONAL GRAPHS EXTRACTION METHOD IN SOFTWARE REVERSE ANALYSIS PROCESS

Jing Jing1Jiang Liehui1,2Liu Tieming2Si Binbin1Zeng Yun1Zhu Xiaoqing2

1(SchoolofComputerScienceandTechnology,InformationandEngineeringUniversity,Zhengzhou450000,Henan,China)2(TheStateKeyLaboratoryofMathematicalEngineeringandAdvancedComputing,Zhengzhou450000,Henan,China)

The results of software reverse analysis process are usually the formal symbols, which are complicated and unintelligibility, therefore the efficiency of the works of code behaviour understanding or code vulnerabilities mining based on software reverse analysis is very slow. In view of this, we design the multidimensional graphs extraction framework firstly, and based on this framework we define the multidimensional graphs description constraints (schema), which makes the multidimensional graphs extraction and specific reverse analysis process be independent from each other. And we present the construction approach of reverse analysis algorithm library and design the call interfaces of the algorithm library, realise the multidimensional graphs description-based abstract graphs generation. What’s more, we design the abstract graphs convert interface which is based on DOT (a graph description language), and achieves the fast visualisation of abstract graphs. At last we present an algorithm of multidimensional graphs extraction. Experimental results show that to use this algorithm can effectively improve the readability of the generated results in reverse analysis process, and greatly increase the work efficiency of analysers in code behaviour understanding and code vulnerabilities mining.

Multidimensional graphs Extract

2014-09-12。國家自然科學(xué)基金項目(61272489)。井靖，講師，主研領(lǐng)域：軟件逆向分析。蔣烈輝，教授。劉鐵銘，講師。司彬彬，講師。曾韻，講師。朱曉清，講師。

TP311

A

10.3969/j.issn.1000-386x.2016.04.001

graph DOT interface Visualisation