[發明專利]一種基于樹優化的程序依賴關系分析方法及系統

有效

• 申請號: 201410055841.2
• 申請日: 2014-02-19
• 公開（公告）號: CN103793653A
• 公開（公告）日: 2014-05-14
• 發明（設計）人: 陳愷;趙險峰;張穎君
• 申請（專利權）人: 中國科學院信息工程研究所
• 主分類號: G06F21/57
• 分類號: G06F21/57
• 代理公司: 北京輕創知識產權代理有限公司 11212
• 代理人: 楊立

技術領域

本發明涉及程序分析技術領域，特別是涉及一種基于樹優化的程序依賴關系分析方法及系統。

背景技術

程序依賴關系分析通常被用來檢測變量是否受輸入數據影響，也可以用來跟蹤輸入數據的傳播過程。這個方法在檢測攻擊和漏洞方面應用非常廣泛，已經成為軟件分析領域的重要方法。

程序依賴關系分析支持靜態和動態分析。靜態分析方法效率較高，但是精確度不足，因為需要估計間接內存地址和間接跳轉/調用的值。動態分析方法在二進制代碼分析中較為流行，通常是通過插裝指令來實現分析，但通過這種方法每個插裝的指令執行都要消耗額外的執行時間，這個時間通常是正常執行的數倍。

分析人員嘗試很多方法來提高程序依賴關系分析的效率，主要是基于硬件的方法和基于編譯器的方法。

一、對于基于硬件的方法，雖然可極大提高分析的運行性能，但是并不是所有的系統都支持這類硬件。而且，在硬件中修改傳播規則也不容易。

二、對于基于編譯器的方法，通常依據一些策略從源程序中選擇部分語句進行程序依賴關系分析。通過減少需要分析語句的數量，來提高傳播速度。但是，這些方法通常會遭遇一個或多個如下的缺陷：a）只有其中一部分與某些預定策略相關的指令會被選擇進行依賴關系分析。一旦這些策略發生改變，這類方法需要重新分析整個程序來找到合適的分析語句，缺乏靈活性。b）這些方法通常需要源代碼，但是軟件提供商，尤其商業的軟件提供商，不會公開源代碼。c）一些方法需要改變目標程序的原始代碼，這是在一些應用程序中是不被允許的。

因此，針對上述問題，本發明提出了一種基于樹優化的程序依賴關系分析方法及系統。

發明內容

本發明所要解決的技術問題是提供一種基于樹優化的程序依賴關系分析方法及系統，用于解決現有程序依賴關系分析方法效率不高、精度度不足等問題。

本發明解決上述技術問題的技術方案如下：一種基于樹優化的程序依賴關系分析方法，包括：

步驟1，以函數為基本單位進行程序依賴關系分析，將函數中的連續指令劃分為多個基本塊，且保證每個基本塊有單一入口和單一出口；

步驟2，針對每個基本塊構建相應的指令依賴樹和指令依賴森林；

步驟3，分析各基本塊的指令依賴樹和指令依賴森林，去除未改變原狀態的指令，去除依賴于特殊寄存器的指令依賴樹；

步驟4，分析各基本塊的指令依賴樹和指令依賴森林，從前一基本塊中去除在其后續各基本塊中有重復定義但未被使用的變量對應的指令依賴樹；

步驟5，根據步驟3和步驟4的處理結果，選取內存索引中不能靜態計算寄存器值的指令所在的位置，將該指令位置之前的位置作為動態插裝位置；

步驟6，在所有動態插裝位置上插裝統一化的影子指令，通過影子指令分析指令依賴樹和指令依賴森林。

在上述技術方案的基礎上，本發明還可以做如下改進。

進一步，所述步驟2中，若指令中定義的一個變量i沒出現在指令依賴樹的節點集合V中，則將該變量i增加到指令依賴樹的節點集合V中，并增加從該節點i到指令所用到的變量相應的邊。

進一步，所述步驟2中，若指令中定義的一個變量i出現在指令依賴樹的節點集合V中，且其是指令依賴森林的根節點，則刪除從節點i到其孩子節點的邊，并增加從i到指令所用到的變量集合相應的邊；若i是指令依賴森林的葉子節點，則i沒有在基本塊中重復定義，增加新的節點i₁，作為塊入口i的初始狀態，并用i₁取代i，增加從i到相應指令中使用變量的邊；否則，增加i的父節點到i的孩子節點的邊，并去掉i的父節點到i的邊及i到其孩子節點的邊。

進一步，所述步驟4具體包括：

步驟41，定義一個記錄在一個基本塊中被定義但未被使用的變量的集合S；

步驟42，分析函數的最后一個基本塊B，如果該基本塊的最后一個指令是一個函數調用指令，則清空S；

步驟43，若最后一個基本塊是一個分支塊，則重新定義S集合為兩個分支的定義集合的交集，若存在一個分支未被分析過，則返回分析該分支；

步驟44，如果基本塊的非葉節點存在于步驟43執行后的S中，則刪除該非葉節點；

步驟45，更新集合S，重復執行步驟41至步驟44，優化基本塊B前面的基本塊。

進一步，所述步驟5中，若在指令依賴森林中沒有間接內存地址，則動態插裝位置為基本塊中的任意位置。