基於塊對目標代碼掃描並替換敏感指令的方法

2023-04-29 08:48:26 2

專利名稱：基於塊對目標代碼掃描並替換敏感指令的方法
技術領域：
本發明涉及面向X86體系結構作業系統虛擬化的二進位翻譯(Binary Translation, BT)方法，尤其是對目標代碼進行掃描並對掃描中發現的敏感指令進行替換的方法。
背景技術：
近年來，隨著硬體技術的迅猛發展尤其是多核乃至眾核處理器的出現，提高計算機 系統高速增長計算能力的使用率日益成為迫切的市場需求。作業系統虛擬化技術通過在 同一臺物理機器上同時運行多個作業系統並對外提供服務，能夠有效提高伺服器的利用 率，因而受到各研究機構和商業機構的高度重視，並在伺服器整合、計算機安全、虛擬 數據中心等領域得到廣泛應用。
作業系統虛擬化依賴於一種稱為虛擬監控器(Virtual Machine Monitor, VMM)的 系統軟體，被虛擬化的作業系統則稱為客戶作業系統(Guest 0S， G0S)。目前，V顧軟 件主要基於三種方法實現作業系統虛擬化，即硬體輔助虛擬化、半虛擬化和BT虛擬化。 三種方法的基本原理及特點簡述如下
1) 硬體輔助虛擬化要求處理器提供硬體支持，如Intel的VT技術和AMD的SVM技術。 VMM通過捕獲在特殊處理器狀態下運行的客戶作業系統執行敏感指令時觸發的硬體 異常實現作業系統虛擬化，如XenSource公司的虛擬機監視器產品Xen和開源軟體 KVM等。該方法的優點為實現簡單，缺點是需要在處理器普通狀態與虛擬化狀態之 間頻繁切換，並且切換的系統開銷遠大於普通系統調用。
2) 半虛擬化要求客戶作業系統降特權級(如Ringl)運行，並對其原始碼相應部分進 行修改以配合V薩實現虛擬化。該方法的局限性在於必須獲得GOS原始碼，並且需 要對任何希望虛擬化的作業系統進行修改，移植和維護工作量巨大。Xen是採用半 虛擬化技術的代表(同一 VMM可對不同GOS採用不同的虛擬化方法)。
3) BT虛擬化則通過對GOS內核二進位代碼進行掃描，發現其中的敏感指令，並將其轉 換為相應的虛擬化代碼來實現GOS虛擬化。採用BT虛擬化方法的VMM有VMWare公 司的濯are Workstation禾口 Sun公司的VirtualBox。
與前兩種方法相比，BT虛擬化對軟硬體等外部條件的依賴最小——既不需要硬體支持，也不需要獲得客戶作業系統原始碼，其關鍵就在於通過掃描發現內核二進位代碼 中的敏感指令，並將其轉換為包含相應虛擬化功能代碼且保持G0S原有執行語義不變的 一段指令序列。所謂"敏感指令"泛指所有一旦在真實處理器上執行即可能改變處理器 的實際狀態，從而導致VMM或其它客戶作業系統無法正常運行的指令或基於安全隔離目 的需要V腿介入的指令。敏感指令轉換方法有指令緩存和本地替換兩種指令緩存方法不修改內存中的G0S代碼，而是在指令緩衝區內複製、轉換即將執行的目標代碼塊，並在該緩衝區內執行轉換後的目標代碼塊，如VMWare和開源軟體Qemu。本地替換方法則直接在敏感指令所在 內存位置將其替換為一條控制轉移指令，通常為JMP指令，使目標代碼改變流程去執行 一段與敏感指令原有語義等價的虛擬化功能代碼或安全檢查代碼，以達到虛擬化或安全 隔離目的。與指令緩存方法相比，本地替換方法具有簡單直觀、內存佔用量小等優點， 但是採用該方法時，將不可避免地遇到部分敏感指令長度小於替換指令即短敏感指令的 情形。例如在X86體系結構中，為了能夠直接跳轉到任意虛地址空間，通常使用5字 節或更長的JMP跳轉指令作為替換指令，而某些敏感指令，如P0PF指令，只有l字節 長度，無法直接替換成JMP指令。針對這一情形，目前已知的基於本地替換方法的V麗軟體均採用可觸發硬體異常的 軟中斷指令(INTO或INT3指令)進行替換，如Sun公司的VirtualBox採用1位元組長 度的INT3指令(0xCC)替換所有長度小於JMP指令的敏感指令。但是，釆用INT0/INT3 指令替換的主要缺點在於每次執行該指令時都會觸發硬體異常，尤其是當被替換指令 被頻繁調用時，硬體狀態的反覆切換將導致大量的系統開銷。因此，當敏感指令長度小 於JMP指令長度時，如何尋找包含該敏感指令且長度不小於JMP指令的最小目標代碼塊， 並將該最小目標代碼塊替換為JMP指令，以減少使用INT3指令替換的概率，同時保持 目標代碼原有執行語義不變，是本領域技術人員關注的重要問題。發明內容本發明要解決的技術問題為提供一種基於塊對目標代碼掃描並替換敏感指令的方法，當敏感指令長度小於JMP跳轉指令時，尋找包含該敏感指令且長度不小於JMP指令 的最小目標代碼塊，並用JMP指令替換該最小目標代碼塊，同時保持最小目標代碼塊原 有執行語義不變。包含指定敏感指令且長度不小於JMP指令的最小目標代碼塊稱為該敏 感指令的替換代碼塊，簡稱替換塊。為了準確描述本發明，首先給出如下說明及定義-
在X86體系結構中，所有控制轉移指令包括JCC、 JMP、 CALL、 RET和IRET指令。 這些控制轉移指令可劃分為兩類有條件轉移指令和無條件轉移指令。除全部JCC指令 以外，JMP/CALL/RET/IRET指令都是無條件轉移指令。所有控制轉移指令又可劃分為目標 地址明確控制轉移指令和目標地址不明確控制轉移指令。目標地址明確控制轉移指令包 括全部JCC指令、直接CALL指令和直接JMP指令，簡稱為直接控制轉移指令；目標地 址不明確控制轉移指令則包括間接CALL指令、間接JMP指令、LCALL指令、LJMP指令、 RET指令和IRET指令，簡稱為間接控制轉移指令。正是由於控制轉移指令固有的、改變 程序執行流程的特性，才使得目標代碼具有代碼塊的概念，即從一個代碼塊轉移到另外 一個代碼塊繼續執行。
定義l:基本塊(Basic Block， BB)是指以G0S起始執行地址、G0S中斷處理函數首 地址或控制轉移指令目標地址為起始邊界，以無條件控制轉移指令或已掃描地址為結束 邊界的連續目標指令序列。
定義2:替換塊(R印lacedBlock， RB)是指滿足以下條件的最短連續目標指令序列
1) 位於基本塊內部(包括基本塊自身)；
2) 包含指定敏感指令且長度不小於JMP指令長度；
3) 不含所屬基本塊範圍之內、本替換塊範圍之外任何控制轉移指令的目標地址(本 替換塊首地址除外)。
定義3:轉換塊(Translated Block, TB)是指替換塊被替換之後，經由替換指令(通 常為JMP指令或INT3指令)執行、包含虛擬化代碼或安全檢査代碼且與原替換塊具有等 價執行語義的一組指令序列。
定義4:待轉換敏感指令隊列是指以線性鍊表形式實現的、保存基本塊掃描時發現的 敏感指令地址及其相關信息的數據結構。待轉換敏感指令隊列節點以敏感指令地址為索 引值，按地址大小按序排列。
定義5:待掃描入口地址隊列是指以線性鍊表形式實現的、保存動態掃描時發現的控 制轉移指令目標地址及其調用地址的數據結構。待掃描入口地址隊列節點以目標地址為 索引值，按地址大小按序排列。
定義6調用者地址隊列是指以線性鍊表形式實現的、保存具有相同目標地址的控制轉 移指令地址的數據結構。調用者地址隊列節點以控制轉移指令地址為索引值，包含在待 掃描入口地址隊列的每個節點之中。
9是指以平衡二叉樹AVL(balanced binary tree, 以發明者G.M. Adelson-Velskii和E.M.Landis名字命名)形式實現的、保存被替換RB相 關信息的數據結構。樹中節點以被替換RB首地址為索引值，其它信息包括被替換RB的 長度及其與對應TB中每條指令地址的對應關係等。
定義7:掃描信息位圖是指以位圖(一段連續虛擬內存單元)形式實現的、用於保存 G0S內核虛地址掃描狀態及相關信息的數據結構。在掃描信息位圖中，每條GOS虛地址的 掃描信息由與該地址一一對應的掃描信息位元(簡稱位元)描述，每個掃描信息位元由 二個比特位組成OO表示該位元對應的虛地址未掃描或非指令首地址；Ol表示該位元對 應的虛地址已掃描；10表示該位元對應的虛地址未掃描或非指令首地址且為基本塊邊界 或控制轉移指令目標地址；11表示該位元對應的虛地址已掃描且為基本塊邊界地址或控
制轉移指令目標地址。從以上描述可看出當位元的高位為1時，表示對應的虛地址為
基本塊邊界或控制轉移指令的目標地址；當位元的低位為1時，表示對應的虛地址已掃 描。由於每個虛地址對應二個比特位，因此每個4KB G0S內核代碼頁需要1KB大小的連 續虛擬內存作為其掃描信息位圖。反之，每個4KB數據頁可作為4個連續G0S內核代碼 頁的掃描信息位圖，將這種用途的數據頁稱為掃描信息位圖頁。
掃描信息位圖索引結構由掃描信息位圖頁目錄頁(以下簡稱頁目錄頁)、掃描信息 位圖頁表頁(以下簡稱頁表頁)和掃描信息位圖頁(以下簡稱位圖頁)組成。相應的， G0S內核虛地址劃分為頁目錄索引、頁表索引和頁內偏移三個位段最高X位為頁目錄索
引，對應2》個頁目錄項，存放頁表頁的首地址；中間Y位為頁表索引，對應2y個頁表項，
存放位圖頁的首地址；最低Z位為頁內偏移，存放內核虛地址對應的掃描信息位元在位 圖頁中的偏移量(以二個比特為單位計算)。
在上述定義的基礎之上，本發明具體技術方案如下
步驟l.創建並初始化全局數據結構
1.1創建並初始化掃描信息位圖頁目錄頁分配一個數據頁作為掃描信息位圖索引 結構中的頁目錄頁，並將頁目錄頁中的頁目錄項全部初始化為0 (表示全部G0S內核虛地 址空間尚未掃描)；
1.2初始化待掃描入口地址隊列及已替換RB有效信息平衡二叉樹將待掃描入口地 址隊列及已替換RB有效信息平衡二叉樹的頭指針設為NULL。 1.3令全局變量M = JMP替換指令長度。步驟2.從G0S內核加載程序(如Grub)輸入參數中獲取G0S內核起始執行地址， 記為首個掃描入口地址，然後對首個掃描入口地址進行動態掃描
2.1. 採用掃描狀態査詢方法檢查首個掃描入口地址的掃描狀態若已掃描，轉步驟 3;若未掃描，將首個掃描入口地址記為基本塊起始邊界，轉2.2。掃描狀態查詢方法為 首先將被查詢地址劃分為頁目錄索引、頁表索引和頁內偏移三個位段；然後檢査頁目錄 索引指向的頁目錄項，若頁目錄項為0，則返回-1表示該地址未掃描且該地址對應位元 不存在。若頁目錄項不為0，則繼續檢查頁表索引指向的頁表項，若頁表項為0，則返回 -1表示該地址未掃描且該地址對應位元不存在，若頁表項不為0，則根據頁表項中的掃 描信息位圖頁首地址和頁內偏移計算得到被查詢地址對應位元的實際位置並返回位元的 實際值。最後根據位元的實際值確定被掃描指令的首地址的掃描狀態位元的實際值低 位為l表示已掃描，為0表示未掃描。
2.2. 對基本塊起始邊界進行基本塊掃描，方法是-
2.2.1初始化待轉換敏感指令隊列將待轉換敏感指令隊列頭指針設為NULL; 2.2.2將基本塊起始地址設為待掃描地址；
2.2.3對待掃描地址處指令進行解碼，根據解碼結果執行以下操作 2.2.3.1若為敏感指令或間接控制轉移指令，則將該指令添加到待轉換敏感指令隊 列，轉2.2.4;
2.2.3.2若為直接控制轉移指令，則首先採用目標地址有效性檢查方法檢査該目標 地址是否指向已替換RB內部若指向已替換RB內部，則將直接控制轉移指令添加到待 轉換敏感指令隊列以便替換時對其目標地址進行修正，然後轉2.2.4;若不指向已替換 RB內部，則採用2. 1中掃描狀態查詢方法檢査目標地址的掃描狀態，若目標地址已掃描 則轉2.2.4，否則將目標地址添加到待掃描入口地址隊列，轉2.2.4。目標地址有效性檢 査方法為採用通用的平衡二叉樹遍歷方法遍歷已替換RB有效信息平衡二叉樹，找到索 引值小於指定目標地址且與指定目標地址最接近的節點，若指定目標地址小於或等於該 節點索引值(即已替換RB的首地址)加上節點中記錄的已替換RB長度，則表明指定目 標地址指向己替換RB內部，否則不指向已替換RB內部。
2.2.3.3若為普通指令，則轉2.2.4;
2.2.4根據解碼結果記錄被掃描指令的掃描狀態，方法為首先採用掃描信息位元索 引方法得到被掃描指令首地址對應位元的實際位置，將該位元的低位設為1;然後採用掃 描信息位元索引方法依次得到被掃描指令所有剩餘字節對應位元的實際位置，將這些位元設為00;最後若被掃描指令為直接控制轉移指令，則採用掃描信息位元索引方法得到 該控制轉移指令目標地址對應的位元的實際位置，並將該位元的高位設為l。其中，掃描 信息位元索引方法為首先將被索引地址劃分為頁目錄索引、頁表索引和頁內偏移三個 位段；然後檢査頁目錄索引指向的頁目錄項是否為O，是則立即分配一個數據頁作為掃描 信息位圖頁表頁並將該頁表頁的首地址寫入頁目錄頁中對應的頁目錄項中；接著檢查頁 表索引指向的頁表項是否為O，是則立即分配一個數據頁作為掃描信息位圖頁並將該位圖
頁的首地址寫入頁表頁中對應的頁表項中；最後根據掃描信息位圖頁首地址和頁內偏移
得到被索弓I地址對應位元的實際位置。
2.2.5將被掃描指令地址加上該指令長度，得到下一條指令的首地址。 2.2.6若被掃描指令為無條件控制轉移指令或採用2.1中掃描狀態查詢方法發現下 一條指令首地址已掃描，則將下一條指令首地址設為基本塊的結束邊界，並將其掃描信 息位元的高位設為l，表示該地址為基本塊邊界地址或控制轉移指令目標地址，然後結束 本次基本塊掃描並轉2. 3;否則轉2.2.7。
2.2.7將下一條指令首地址設為待掃描地址，轉2.2.3，繼續進行基本塊掃描。 2. 3對待轉換敏感指令隊列中的敏感指令進行基於替換塊的敏感指令本地替換 2.3.1若待轉換敏感指令隊列為空，則停止替換，轉步驟3;若待轉換敏感指令隊列 不為空，從待轉換敏感指令隊列中取出最小的敏感指令地址，在基本塊內(從基本塊起 始邊界到基本塊結束邊界之間的連續虛地址空間)尋找包含該敏感指令的替換塊，尋找
方法如下
2.3.1.1將該敏感指令自身設為當前RB;
2.3.1.2若當前RB長度不小於M字節，則將當前RB設為待轉換RB，轉2.3.3;若 當前RB長度小於M字節，嘗試向低地址空間擴展相鄰指令到當前RB，擴展方法如下
Al.若當前RB首地址為基本塊起始邊界，轉2. 3. 1. 3;否則向低地址空間擴展一條指 令到當前RB，方法是採用2. 2. 4中的掃描信息位元索引方法從當前RB首地址開始向低 地址空間搜索掃描信息位圖，依次得到每條連續地址對應位元的實際位置並檢査每個位 元的實際值，找到第一個低位為1的位元，將該低位為1的位元對應的虛地址(即被擴 展指令的首地址)設為當前RB起始邊界，轉B1。
Bl.若被擴展指令首地址對應位元的高位為1，表示該位元對應的地址為控制轉移指 令的目標地址，執行C1;否則轉2.3. 1.2。
Cl.檢査待掃描入口地址隊列，若發現以被擴展指令首地址為索引值的節點，則採用遍歷擴展方法檢查該節點的調用者隊列，將所有位於基本塊範圍之內的調用者地址與當 前RB之間的所有指令擴展到當前RB，轉2. 3. 1.2。若未發現以被擴展指令首地址為索引 值的節點，直接轉2.3.1.2。遍歷擴展方法為採用2.2.3.2中的目標地址有效性檢查方 法依次檢查每個調用者地址是否位於基本塊範圍之內且位於當前RB範圍之外，是則將調 用者地址設為當前RB的邊界若調用者地址小於當前RB首地址，則將該地址設為當前 RB首地址；若調用者地址大於當前RB的結束邊界，則將調用者地址的下一條指令首地址 (即調用者地址加上該地址處的控制轉移指令長度)設為當前RB的結束邊界。否則檢査 下一個調用者地址。
2.3.1.3嘗試向高地址空間擴展相鄰指令到當前RB，擴展方法如下 A2.若當前RB結束邊界為基本塊的結束邊界，轉2. 3. 2，否則向高地址空間擴展一條 指令到當前RB，方法是採用2. 2. 4中的掃描信息位元索引方法從當前RB結束邊界開始 向高地址空間搜索掃描信息位圖，依次得到每條連續地址對應位元的實際位置並檢查每 個位元的實際值，找到第二個低位為1的位元(對應當前RB之後第一條已掃描指令的下 一條指令首地址)或第一個被設置為IO的位元(對應基本塊的結束邊界)，將該位元對 應的虛地址設為當前RB結束邊界，而找到的第一個低位為1的位元對應的虛地址即被擴 展指令首地址。
B2.若被擴展指令首地址對應的位元為10，轉2.3.2;否則檢査被擴展指令首地址對 應位元的高位，若高位為l，轉C2，若高位為0，轉2. 3. 1.2。
C2.檢査待掃描入口地址隊列，若發現以被擴展指令首地址為索引值的節點，則採用 Cl中的遍歷擴展方法檢査該節點的調用者隊列，將所有位於基本塊範圍之內的調用者地 址與當前RB之間的所有指令擴展到當前RB，轉2. 3. 1. 2。若未發現以被擴展指令首地址 為索引值的節點，直接轉2.3.1.2。
2.3.2若當前RB長度小於M字節(表明基本塊長度小於JMP替換指令)，則將敏感 指令設為待轉換RB;否則將當前RB設為待轉換RB。
2. 3. 3採用二進位翻譯中的常規方法生成與待轉換RB具有等價執行語義的轉換代碼 塊，記為TB。
2. 3. 4若待轉換RB的長度不小於M字節，則將該RB前M字節替換為JMP指令，目 標地址為2. 2. 3中生成的TB首地址，剩餘字節用NOP指令填充，得到已替換RB;若待轉 換RB的長度小於M字節，則將該RB的首字節替換為INT3指令，剩餘字節用NOP指令填 充，得到已替換RB。
132. 3. 5在已替換RB有效信息平衡二叉樹中創建已替換RB的節點，該節點包括已替 換RB的首地址、長度及其與TB指令之間的地址對應關係這些有效信息。對於被替換為 INT3指令的RB (實際為敏感指令)，將在該INT3指令執行時由V麗INT3異常處理函數 根據已替換RB有效信息平衡二叉樹中記錄的信息找到並執行其轉換代碼；對於被替換為 JMP指令的RB，則通過JMP指令直接執行已替換RB的轉換代碼。
2.3.6遍歷待掃描敏感指令隊列，刪除所有以已替換RB中的敏感指令地址為索引值 的節點，轉2.3.1。
2.4遍歷待掃描入口地址隊列，刪除所有以已掃描入口地址為索引值的節點。
2.5若待掃描入口地址隊列為空，則結束本次動態掃描，轉步驟3;否則從待掃描入
口地址隊列中取出最大未掃描入口地址，記為基本塊起始邊界，轉2.2執行下一次基本
塊掃描。
步驟3.從首個掃描入口地址開始執行GOS內核代碼，直至產生硬體中斷或異常，或 執行間接控制轉移指令的轉換代碼。
步驟4.將G0S中斷或異常處理函數的入口地址或間接控制轉移指令的目標地址設為 首個掃描入口地址，轉2.1。
根據以上過程可知在對GOS執行完第一次動態掃描之後，GOS便處於原有代碼與轉 換代碼反覆、交替運行狀態，並且隨著GOS的運行，在不動態加載新的GOS內核模塊的 前提下，未經掃描的GOS內核代碼將會越來越少，從而動態掃描所引入的系統開銷也會 越來越小。
採用本發明可以達到以下技術效果
1. 採用基於替換塊的敏感指令本地替換方法，以替換塊為單位進行替換，能夠最大限 度地避免使用INT0/INT3指令進行替換(只在基本塊長度小於JMP替換指令時使用 INT3指令替換)，從而有效提高BT虛擬化性能。
2. 可對任意定義的X86敏感指令進行替換，可擴展性好、適用性廣。
3. 以GOS內核虛地址為索引動態創建掃描信息位圖，不僅能夠減少內存開銷，而且能 夠有效防止錯位攻擊和基於緩衝區溢出的虛地址變化攻擊。
因此，本發明既可以滿足採用BT技術實現作業系統虛擬化的軟體支持需求，也能夠 應用於要求對目標代碼進行安全檢查或隔離的應用場景。


圖l是本發明'總體流程圖2是本發明第2. 2步中基本塊掃描流程圖3是本發明第2. 3步中敏感指令本地替換流程圖
圖4是本發明定義7中掃描信息位圖索引結構及索引方法示意圖
具體實施方法
圖1為本發明整體流程圖
1. 創建並初始化全局數據結構。
2. 從G0S內核加載程序輸入參數中獲取GOS內核起始執行地址，記為首個掃描入口 地址，然後對首個掃描入口地址進行動態掃描
2.1.採用掃描狀態査詢方法檢査首個掃描入口地址的掃描狀態若已掃描，轉3; 若未掃描，將首個掃描入口地址記為基本塊起始邊界，轉2.2。 2. 2.對基本塊起始邊界進行基本塊掃描。
2. 3對待轉換敏感指令隊列中的敏感指令進行基於替換塊的敏感指令本地替換。
2.4遍歷待掃描入口地址隊列，刪除所有以巳掃描入口地址為索引值的節點。
2.5若待掃描入口地址隊列為空，則結束本次動態掃描，轉3;否則從待掃描入口地
址隊列中取出最大未掃描入口地址，記為基本塊起始邊界並轉2.2。
3從首個掃描入口地址開始執行G0S內核代碼，直至產生硬體中斷或異常或執行間
接控制轉移指令的轉換代碼。
4.將G0S中斷或異常處理函數的入口地址或間接控制轉移指令的目標地址設為首個
掃描入口地址，轉2. 1。
圖2是本發明2. 2步中基本塊掃描流程圖
2.2.1初始化待轉換敏感指令隊列將待轉換敏感指令隊列頭指針設為NULL。 2.2.2將基本塊起始地址設為待掃描地址。
2.2.3對待掃描地址處指令進行解碼，根據解碼結果執行以下操作 2.2.3.1若為敏感指令或間接控制轉移指令，則將該指令添加到待轉換敏感指令隊 列，轉2.2.4。
2.2.3.2若為直接控制轉移指令，則採用目標地址有效性檢査方法檢査該目標地址 是否指向已替換RB內部若指向已替換RB內部，則將直接控制轉移指令添加到待轉換 敏感指令隊列，然後轉2.2.4;若不指向已替換RB內部，則檢查目標地址的掃描狀態，若目標地址已掃描則轉2.2.4，否則將目標地址添加到待掃描入口地址隊列，轉2.2.4。 2. 2. 3. 3若為普通指令，轉2.2.4。
2. 2. 4根據解碼結果記錄被掃描指令的掃描狀態首先採用掃描信息位元索引方法得 到被掃描指令首地址對應位元的實際位置，將該位元的低位設為1;然後採用掃描信息位 元索引方法依次得到被掃描指令所有剩餘字節對應位元的實際位置，將這些位元設為00;
最後若被掃描指令為直接控制轉移指令，則採用掃描信息位元索引方法得到該控制轉移
指令目標地址對應的位元的實際位置，並將該位元的高位設為1。
2.2.5將被掃描指令地址加上該指令長度，得到下一條指令的首地址。
2.2.6若被掃描指令為無條件控制轉移指令或下一條指令首地址已掃描，則將下一
條指令的首地址設為基本塊的結束邊界，並將其掃描信息位元的高位設為1，然後轉2. 3;
否則轉2. 2.7。
2.2.7將下一條指令的首地址設為待掃描地址，轉2.2.3。 圖3是本發明2. 3步中基於替換塊的敏感指令本地替換流程圖 2.3.1若待轉換敏感指令隊列為空，則停止替換，轉步驟3;若待轉換敏感指令隊列 不為空，從待轉換敏感指令隊列中取出最小的敏感指令地址，在基本塊內(從基本塊起 始邊界到基本塊結束邊界之間的連續虛地址空間)尋找包含該敏感指令的替換塊，尋找 方法如下
2.3.1.1將該敏感指令自身設為當前RB;
2.3. 1.2若當前RB長度不小於M字節，則將當前RB設為待轉換RB，轉2. 3. 3;若 當前RB長度小於M字節，嘗試向低地址空間擴展相鄰指令到當前RB，擴展方法如下
Al.若當前RB首地址為基本塊起始邊界，轉2. 3. 1. 3;否則向低地址空間擴展一條指 令到當前RB，方法是採用2. 2. 4中的掃描信息位元索引方法從當前RB首地址開始向低 地址空間搜索掃描信息位圖，依次得到每條連續地址對應位元的實際位置並檢査每個位 元的實際值，找到第一個低位為1的位元，將該低位為1的位元對應的虛地址(即被擴 展指令的首地址)設為當前RB起始邊界，轉B1。
Bl.若被擴展指令首地址對應位元的高位為1，表示該位元對應的地址為控制轉移指 令的目標地址，轉C1;否則轉2.3. 1.2。
Cl.檢查待掃描入口地址隊列，若發現以被擴展指令首地址為索引值的節點，則採用 遍歷擴展方法檢查該節點的調用者隊列，將所有位於基本塊範圍之內的調用者地址與當 前RB之間的所有指令擴展到當前RB，轉2. 3. 1.2。若未發現以被擴展指令首地址為索引值的節點，直接轉2.3.1.2。
2.3.1.3嘗試向高地址空間擴展相鄰指令到當前RB，擴展方法如下 A2.若當前RB結束邊界為基本塊的結束邊界，轉2. 3.2,否則向高地址空間擴展一條 指令到當前RB，方法是採用2. 2. 4中的掃描信息位元索引方法從當前RB結束邊界開始 向高地址空間搜索掃描信息位圖，依次得到每條連續地址對應位元的實際位置並檢查每 個位元的實際值，找到第二個低位為1的位元(對應當前RB之後第一條已掃描指令的下 一條指令首地址)或第一個被設置為IO的位元(對應基本塊的結束邊界)，將該位元對 應的虛地址設為當前RB結束邊界，而找到的第一個低位為1的位元對應的虛地址即被擴 展指令首地址。
B2.若被擴展指令首地址對應的位元為10，轉2.3.2;否則檢査被擴展指令首地址對 應位元的高位，若高位為l，轉C2，若高位為0，轉2. 3. 1.2。
C2.檢查待掃描入口地址隊列，若發現以被擴展指令首地址為索引值的節點，則釆用 遍歷擴展方法檢査該節點的調用者隊列，將所有位於基本塊範圍之內的調用者地址與當 前RB之間的所有指令擴展到當前RB，轉2.3. 1.2。若未發現以被擴展指令首地址為索引 值的節點，直接轉2.3.1.2。
2.3.2若當前RB長度小於M字節(表明基本塊長度小於JMP替換指令)，則將敏感 指令設為待轉換RB;否則將當前RB設為待轉換RB。
2. 3. 3採用二進位翻譯中的常規方法生成與待轉換RB具有等價執行語義的轉換代碼 塊，記為TB。
2. 3. 4若待轉換RB的長度不小於M字節，則將該RB前M字節替換為JMP指令，目 標地址為2.2.3中生成的TB首地址，剩餘字節用NOP指令填充，得到已替換RB;若待轉 換RB的長度小於M字節，則將該RB的首字節替換為INT3指令，剩餘字節用NOP指令填 充，得到已替換RB。
2.3.5在已替換RB有效信息平衡二叉樹中創建已替換RB的節點，該節點包括己替 換RB的首地址、長度及其與TB指令之間的地址對應關係這些有效信息。對於被替換為 INT3指令的RB (實際為敏感指令)，將在該INT3指令執行時由VMMINT3異常處理函數 根據已替換RB有效信息平衡二叉樹中記錄的信息找到並執行其轉換代碼；對於被替換為 JMP指令的RB，則通過JMP指令直接執行已替換RB的轉換代碼。
2.3.6遍歷待掃描敏感指令隊列，刪除所有以已替換RB中的敏感指令地址為索引值 的節點，轉2.3. 1。圖4是本發明定義7中掃描信息位圖及其索引方法示意圖
以X86-32位體系結構為例32位內核虛地址共劃分為頁目錄索引、頁表索引和頁內 偏移三個位段。其中最高8位為頁目錄索引，對應256個表項；中間IO位為頁表索引， 對應1024個表項；最低14位則為內核虛地址對應位元在掃描信息位圖頁中的偏移量(以 二個比特位為單位計算)。指定G0S內核虛地址va對應的掃描信息位元索引與獲取方法 如下
1) 取va的高8位(即頁目錄索引)，左移2位後加上頁目錄頁首地址，得到va對應的 頁目錄項的首地址，從頁目錄項中取出頁表頁的首地址；
2) 取va的中間10位(即頁表索引)，左移2位後加上頁表頁的首地址，得到va對應 的頁表項的首地址，從頁表項中取出位圖頁的首地址；
3) 取va的低14位，右移2位後加上位圖頁的首地址，得到va對應的掃描信息位元所 在的內存單元地址(位於掃描信息位圖頁中)，記為pScanByte;
4) 將va的低14位與0x3進行位與運算，得到va對應的掃描信息位元在pScanByted 中的偏移量，記為offset;
5) 按下列公式計算得到va對應的掃描信息位元的實際值，記為ScanBit:
ScanBit = (pScanByte & ( 0x3 〈〈 (offset << l)))》(offset 〈〈 1) 公式中的"〈〈"為左移運算符，"》"為右移運算符，表示將16進位無符號整數左 移或右移指定的位數；"&"為位與運算符。
18
權利要求
1.一種基於塊對目標代碼掃描並替換敏感指令的方法，其特徵在於包括以下步驟步驟1.創建並初始化全局數據結構1.1創建並初始化掃描信息位圖頁目錄頁分配一個數據頁作為掃描信息位圖索引結構中的頁目錄頁，並將頁目錄頁中的頁目錄項全部初始化為0；掃描信息位圖是指以位圖形式實現的、用於保存GOS內核虛地址掃描狀態及相關信息的數據結構；在掃描信息位圖中，每條GOS虛地址的掃描信息由與該地址一一對應的掃描信息位元-簡稱位元描述，每個掃描信息位元由二個比特位組成00表示該位元對應的虛地址未掃描或非指令首地址；01表示該位元對應的虛地址已掃描；10表示該位元對應的虛地址未掃描或非指令首地址且為基本塊邊界或控制轉移指令目標地址；11表示該位元對應的虛地址已掃描且為基本塊邊界地址或控制轉移指令目標地址；基本塊是指以GOS起始執行地址、GOS中斷處理函數首地址或控制轉移指令目標地址為起始邊界，以無條件控制轉移指令或已掃描地址為結束邊界的連續目標指令序列；掃描信息位圖索引結構由掃描信息位圖頁目錄頁--簡稱頁目錄頁、掃描信息位圖頁表頁--簡稱頁表頁和掃描信息位圖頁--簡稱位圖頁組成，GOS內核虛地址劃分為頁目錄索引、頁表索引和頁內偏移三個位段，頁目錄索引存放頁表頁的首地址，頁表索引存放位圖頁的首地址，頁內偏移存放內核虛地址對應的掃描信息位元在位圖頁中的偏移量；1.2初始化待掃描入口地址隊列及已替換RB有效信息平衡二叉樹將待掃描入口地址隊列及已替換RB有效信息平衡二叉樹的頭指針設為NULL；待掃描入口地址隊列是指以線性鍊表形式實現的、保存動態掃描時發現的控制轉移指令目標地址及其調用地址的數據結構，待掃描入口地址隊列節點以目標地址為索引值，按地址大小按序排列；已替換RB有效信息平衡二叉樹是指以平衡二叉樹AVL形式實現的、保存被替換RB相關信息的數據結構，樹中節點以被替換RB首地址為索引值，其它信息包括被替換RB的長度及其與對應TB中每條指令地址的對應關係；RB是替換塊，指滿足以下條件的最短連續目標指令序列位於基本塊內部，包括基本塊自身；包含指定敏感指令且長度不小於JMP指令長度；不含所屬基本塊範圍之內、本替換塊範圍之外任何控制轉移指令的目標地址，本替換塊首地址除外；TB是轉換塊，指替換塊被替換之後，經由替換指令執行、包含虛擬化代碼或安全檢查代碼且與原替換塊具有等價執行語義的一組指令序列；1.3令全局變量M＝JMP替換指令長度；步驟2.從GOS內核加載程序輸入參數中獲取GOS內核起始執行地址，記為首個掃描入口地址，然後對首個掃描入口地址進行動態掃描2.1.採用掃描狀態查詢方法檢查首個掃描入口地址的掃描狀態若已掃描，轉步驟3；若未掃描，將首個掃描入口地址記為基本塊起始邊界，轉2.2；2.2.對基本塊起始邊界進行基本塊掃描，方法是2.2.1初始化待轉換敏感指令隊列將待轉換敏感指令隊列頭指針設為NULL；待轉換敏感指令隊列是指以線性鍊表形式實現的、保存基本塊掃描時發現的敏感指令地址及其相關信息的數據結構，待轉換敏感指令隊列節點以敏感指令地址為索引值，按地址大小按序排列；2.2.2將基本塊起始地址設為待掃描地址；2.2.3對待掃描地址處指令進行解碼，根據解碼結果執行以下操作2.2.3.1若為敏感指令或間接控制轉移指令，則將該指令添加到待轉換敏感指令隊列，轉2.2.4；2.2.3.2若為直接控制轉移指令，則首先採用目標地址有效性檢查方法檢查該目標地址是否指向已替換RB內部若指向已替換RB內部，則將直接控制轉移指令添加到待轉換敏感指令隊列，然後轉2.2.4；若不指向已替換RB內部，則採用掃描狀態查詢方法檢查目標地址的掃描狀態，若目標地址已掃描則轉2.2.4，否則將目標地址添加到待掃描入口地址隊列，轉2.2.4；2.2.3.3若為普通指令，則轉2.2.4；2.2.4根據解碼結果記錄被掃描指令的掃描狀態，方法為首先採用掃描信息位元索引方法得到被掃描指令首地址對應位元的實際位置，將該位元的低位設為1；然後採用掃描信息位元索引方法依次得到被掃描指令所有剩餘字節對應位元的實際位置，將這些位元設為00；最後若被掃描指令為直接控制轉移指令，則採用掃描信息位元索引方法得到該控制轉移指令目標地址對應的位元的實際位置，並將該位元的高位設為1；2.2.5將被掃描指令地址加上該指令長度，得到下一條指令的首地址；2.2.6若被掃描指令為無條件控制轉移指令或下一條指令首地址已掃描，則將下一條指令首地址設為基本塊的結束邊界，並將其掃描信息位元的高位設為1，表示該地址為基本塊邊界地址或控制轉移指令目標地址，然後結束本次基本塊掃描並轉2.3；否則轉2.2.7；2.2.7將下一條指令首地址設為待掃描地址，轉2.2.3，繼續進行基本塊掃描；2.3對待轉換敏感指令隊列中的敏感指令進行基於替換塊的敏感指令本地替換2.3.1若待轉換敏感指令隊列為空，則停止替換，轉步驟3；若待轉換敏感指令隊列不為空，從待轉換敏感指令隊列中取出最小的敏感指令地址，在基本塊內尋找包含該敏感指令的替換塊，尋找方法如下2.3.1.1將該敏感指令自身設為當前RB；2.3.1.2若當前RB長度不小於M字節，則將當前RB設為待轉換RB，轉2.3.3；若當前RB長度小於M字節，嘗試向低地址空間擴展相鄰指令到當前RB，擴展方法如下A1.若當前RB首地址為基本塊起始邊界，轉2.3.1.3；否則向低地址空間擴展一條指令到當前RB，轉B1；B1.若該低位為1的位元的高位為1，執行C1，否則轉2.3.1.2；C1.檢查待掃描入口地址隊列，若發現以低位為1位元對應的虛地址為索引值的節點，則採用遍歷擴展方法檢查該節點的調用者隊列，將所有位於基本塊範圍之內的調用者地址與當前RB之間的所有指令擴展到當前RB，轉2.3.1.2；若未發現以低位為1位元對應的虛地址為索引值的節點，則轉2.3.1.2；調用者隊列是指以線性鍊表形式實現的、保存具有相同目標地址的控制轉移指令地址的數據結構，調用者地址隊列節點以控制轉移指令地址為索引值，包含在待掃描入口地址隊列的每個節點之中；2.3.1.3嘗試向高地址空間擴展相鄰指令到當前RB，擴展方法如下A2.若當前RB結束邊界為基本塊的結束邊界，轉2.3.2，否則向高地址空間擴展一條基本塊指令到當前RB；B2.若被擴展指令首地址對應的位元為10，轉2.3.2；否則檢查被擴展指令首地址對應位元的高位，若高位為1，轉C2，若高位為0，轉2.3.1.2；C2.檢查待掃描入口地址隊列，若發現以被擴展指令首地址為索引值的節點，則採用遍歷擴展方法檢查該節點的調用者隊列，將所有位於基本塊範圍之內的調用者地址與當前RB之間的所有指令擴展到當前RB，轉2.3.1.2，若未發現以被擴展指令首地址為索引值的節點，直接轉2.3.1.2；2.3.2若當前RB長度小於M字節，則將敏感指令設為待轉換RB；否則將當前RB設為待轉換RB；2.3.3採用二進位翻譯中的常規方法生成與待轉換RB具有等價執行語義的轉換代碼塊，記為TB；2.3.4若待轉換RB的長度不小於M字節，則將該RB前M字節替換為JMP指令，目標地址為TB首地址，剩餘字節用NOP指令填充，得到已替換RB；若待轉換RB的長度小於M字節，則將該RB的首字節替換為INT3指令，剩餘字節用NOP指令填充，得到已替換RB；2.3.5在已替換RB有效信息平衡二叉樹中創建已替換RB的節點，該節點包括已替換RB的首地址、長度及其與TB指令之間的地址對應關係這些有效信息；2.3.6遍歷待掃描敏感指令隊列，刪除所有以已替換RB中的敏感指令地址為索引值的節點，轉2.3.1；2.4遍歷待掃描入口地址隊列，刪除所有以已掃描入口地址為索引值的節點；2.5若待掃描入口地址隊列為空，則結束本次動態掃描，轉步驟3；否則從待掃描入口地址隊列中取出最大未掃描入口地址，記為基本塊起始邊界，轉2.2執行下一次基本塊掃描；步驟3從首個掃描入口地址開始執行GOS內核代碼，直至產生硬體中斷或異常或執行間接控制轉移指令的轉換代碼；步驟4.將GOS中斷或異常處理函數的入口地址或間接控制轉移指令的目標地址設為首個掃描入口地址，轉2.1。
2. 如權利要求l所述的基於塊對目標代碼掃描並替換敏感指令的方法，其特徵在於 所述掃描狀態查詢方法是首先將被查詢地址劃分為頁目錄索引、頁表索引和頁內偏移 三個位段；然後檢查頁目錄索引指向的頁目錄項，若頁目錄項為0，則返回-1表示該地 址未掃描且該地址對應位元不存在；若頁目錄項不為0，則繼續檢査頁表索引指向的頁表 項，若頁表項為0，則返回-1表示該地址未掃描且該地址對應位元不存在，若頁表項不 為O，則根據頁表項中的掃描信息位圖頁首地址和頁內偏移計算得到被查詢地址對應位元 的實際位置並返回位元的實際值；最後根據位元的實際值確定被掃描指令的首地址的掃 描狀態位元的實際值低位為l表示已掃描，為0表示未掃描。
3. 如權利要求l所述的基於塊對目標代碼掃描並替換敏感指令的方法，其特徵在於 所述目標地址有效性檢査方法為採用平衡二叉樹遍歷方法遍歷己替換RB有效信息平衡 二叉樹，找到索引值小於指定目標地址且與指定目標地址最接近的節點，若指定目標地 址小於或等於已替換RB的首地址加上節點中記錄的已替換RB長度，則表明指定目標地 址指向已替換RB內部，否則不指向已替換RB內部。
4. 如權利要求l所述的基於塊對目標代碼掃描並替換敏感指令的方法，其特徵在於 所述掃描信息位元索引方法為首先將被索引地址劃分為頁目錄索引、頁表索引和頁內偏移三個位段；然後檢查頁目錄索引指向的頁目錄項是否為O，是則立即分配一個數據頁 作為掃描信息位圖頁表頁並將該頁表頁的首地址寫入頁目錄頁中對應的頁目錄項中；接著檢査頁表索引指向的頁表項是否為O，是則立即分配一個數據頁作為掃描信息位圖頁並 將該位圖頁的首地址寫入頁表頁中對應的頁表項中；最後根據掃描信息位圖頁首地址和 頁內偏移得到被索引地址對應位元的實際位置。
5. 如權利要求l所述的基於塊對目標代碼掃描並替換敏感指令的方法，其特徵在於 所述向低地址空間擴展一條基本塊指令到當前RB的方法是採用掃描信息位元索引方法 從當前RB首地址開始向低地址空間搜索掃描信息位圖，依次得到每條連續地址對應位元的實際位置並檢查每個位元的實際值，找到第一個低位為1的位元，將該低位為1的位元對應的虛地址即被擴展指令的首地址設為當前RB起始邊界。
6. 如權利要求l所述的基於塊對目標代碼掃描並替換敏感指令的方法，其特徵在於所述遍歷擴展方法為採用目標地址有效性檢查方法依次檢査每個調用者地址是否位於基本塊範圍之內且位於當前RB範圍之外，是則將調用者地址設為當前RB的邊界，即若 調用者地址小於當前RB首地址，則將該地址設為當前RB首地址；若調用者地址大於當 前RB的結束邊界，則將該地址設為當前RB的結束邊界，否則檢查下一個調用者地址。
7. 如權利要求l所述的基於塊對目標代碼掃描並替換敏感指令的方法，其特徵在於 所述向高地址空間擴展一條基本塊指令到當前RB的方法是採用掃描信息位元索引方法 從當前RB結束邊界開始向高地址空間搜索掃描信息位圖，依次得到每條連續地址對應位 元的實際位置並檢査每個位元的實際值，找到第二個低位為1的位元或第一個被設置為 10的位元，將該位元對應的虛地址設為當前RB結束邊界，而找到的第一個低位為1的位 元對應的虛地址即被擴展指令首地址。
全文摘要
本發明公開了一種基於塊對目標代碼掃描並替換敏感指令的方法，目的是提供一種當敏感指令長度小於JMP時，尋找包含該敏感指令且長度不小於JMP的最小目標代碼塊，並用JMP替換該最小目標代碼塊的方法。技術方案是對首個掃描入口地址進行動態掃描，主要包括對基本塊起始邊界進行基本塊掃描，對待轉換敏感指令隊列中的敏感指令進行基於替換塊的敏感指令本地替換；然後從首個掃描入口地址開始執行GOS內核代碼，直至產生硬體中斷或異常或執行間接控制轉移指令的轉換代碼；將GOS中斷或異常處理函數的入口地址或間接控制轉移指令的目標地址設為首個掃描入口地址，然後循環執行動態掃描。採用本發明能夠最大限度地避免使用INT0/INT3指令進行替換，有效提高BT虛擬化性能。
文檔編號G06F9/455GK101630269SQ20091004383
公開日2010年1月20日 申請日期2009年7月3日 優先權日2009年7月3日
發明者劉曉建, 吳慶波, 孔金珠, 張衛華, 戴華東, 易曉東, 譚鬱松 申請人:中國人民解放軍國防科學技術大學