一種高效解決間接轉移的反饋式靜態二進制翻譯方法

王 軍 龐建民 傅立國 岳 峰 張家豪

(數學工程與先進計算國家重點實驗室(戰略支援部隊信息工程大學) 鄭州 450002)

二進制翻譯[1]的核心目標是將源指令集的指令序列通過代碼翻譯操作，翻譯成等價的其他指令集的指令序列.二進制翻譯已廣泛用于軟件安全分析[2-3]、程序行為分析[4]、軟件逆向工程、系統虛擬等領域，并已成為軟件移植[5]的主流技術.如FX!32把x86平臺下的Win32應用程序移植到Alpha平臺[6-7]；昆士蘭大學開發的跨平臺靜態二進制翻譯器UQBT(University of Queensland binary translator)，可以支持不同源平臺應用程序到目的平臺的翻譯；動態二進制翻譯器QEMU (quick emulator) 同時支持進程級和系統級程序翻譯，并已成功實現對國產龍芯平臺的支持[8].

主流的二進制翻譯可以分為動態二進制翻譯、靜態二進制翻譯和動靜結合的二進制翻譯[9].動態二進制翻譯[10]是一種即時翻譯(邊翻譯邊執行)技術，在運行目標代碼時能很好地解決代碼發現和代碼定位問題[11-12]，但是動態二進制翻譯需要在動態翻譯源平臺二進制可執行程序的同時執行翻譯生成的目標平臺二進制程序，翻譯時間和代碼優化時間占據程序執行時間，所以動態二進制翻譯不能采用深度優化的方法.即便目前有很多優化方法，如熱路徑優化[13]、寄存器映射[14]、多線程并行優化[8]等，在一定程度上提高了動態二進制翻譯的效率，但動態二進制翻譯效率低的問題仍然比較突出.靜態二進制翻譯在不運行程序的情況下，靜態分析源平臺可執行文件，提取程序指令進行翻譯，能夠采用較復雜的代碼分析和優化算法，能生成高質量的代碼，程序執行效率較高；而且靜態二進制翻譯方式一次翻譯多次執行的特性也十分適用于高性能計算程序的翻譯，但是靜態二進制翻譯難以處理下段的代碼發現和代碼定位問題[15].

代碼發現問題是指在靜態條件下難以獲取間接轉移(具體可分為間接跳轉和間接調用[16])目標地址的問題，間接轉移指令的目標地址可能是一個寄存器或者存儲器的值；代碼定位問題是指難以在程序執行時確定源平臺轉移目的地址對應的目標平臺代碼地址.

目前現有的解決靜態二進制翻譯中由間接轉移引起的代碼發現和代碼定位問題的方法，無論是解釋器法還是地址映射表法，都存在一個共同的缺陷：生成代碼質量不高且含有較多的冗余代碼.為了更高效地解決靜態二進制翻譯面臨的代碼發現問題，本文對課題組之前實現的基于動態二進制翻譯器QEMU的靜態二進制翻譯器SQEMU[17](static QEMU)進行了優化和改進，提出了以基本塊為單位進行翻譯的反饋式靜態二進制翻譯框架(feedback static QEMU, FD-SQEMU)，并提出了二級地址映射表法，更快速地實現了代碼定位.為了解決基本塊翻譯引入的代碼定位問題，設計了高效的二級地址映射表來快速定位轉移指令目標地址.在翻譯過程中，使用數組結構Address保存源平臺每個基本塊對應的目標平臺的代碼基本塊起始地址，并使用索引數組Index保存源平臺指令地址在Address中對應的索引位置，從而根據Index和Address數組快速得到源平臺指令塊在目的平臺上的對應地址.為了解決靜態二進制翻譯中的代碼定位問題，本文引入了反饋機制，在靜態翻譯目標程序時對間接轉移指令添加監控反饋代碼，之后運行翻譯后的目標程序，依據監控反饋信息[6]確定間接轉移目標地址進行代碼發現.之后，依據反饋的間接轉移目標信息對源程序重新進行基本塊劃分，然后繼續翻譯、執行、反饋，重復此過程直至程序能正常執行結束.

本文的主要貢獻有3個方面:

1) 針對現有靜態二進制翻譯中由間接轉移指令引起的代碼發現和代碼定位問題解決方法效率較低的缺陷，提出了基于基本塊翻譯的反饋式靜態二進制翻譯框架FD-SQEMU，以基本塊方式進行翻譯能更好地進行代碼優化，生成更高質量的目標代碼.

2) 針對SQEMU線性逐行遍歷翻譯方式不能兼顧程序上下文以及引入大量冗余代碼的缺陷，改進了地址映射方式，提出了二級地址映射表法，更快速地解決了靜態二進制翻譯中代碼定位問題.

3) 提出了新的代碼發現的思路，利用動態執行、監控、反饋進行代碼發現，更有效地解決了數據段代碼問題.另外，該方法雖然是針對基于QEMU的靜態二進制翻譯框架SQEMU實現的，但具有相當強的通用性，不限于目標平臺和指令形式，對降低二進制翻譯后的代碼膨脹率有重要意義，有很強的可擴展性.

1 相關工作

目前，靜態二進制翻譯在不同的平臺已有不同的實現，本節首先對靜態二進制翻譯中間接轉移處理的相關方法進行介紹，然后重點對二進制翻譯系統HBT(hybrid binary translation)和SQEMU的工作方式及其優缺點進行介紹.

1.1 常見的靜態二進制翻譯中間接轉移處理方法

一種主流的解決靜態二進制翻譯中間接轉移問題的方法是引入解釋器.

目前已有成熟的靜態二進制翻譯系統引入解釋器模塊來處理二進制翻譯中的間接轉移問題，例如跨平臺靜態二進制翻譯器UQBT系統[7].UQBT系統先將源平臺二進制文件Ms抽象為機器無關語言HRTL(higher-level register transfer language)，之后對HRTL中間語言進行優化，生成目的平臺可執行文件.在將HRTL中間語言翻譯為目標機器指令遇到間接轉移指令時，UQBT系統使用解釋器再次使用源二進制文件解釋執行獲得Ms到Mt的地址映射.

使用解釋器法處理間接轉移存在著2個問題：1)處理速度較慢;2)需要重復使用源二進制文件的代碼段.

另一種主流的解決靜態二進制翻譯中間接轉移問題的方法是地址映射表法，地址映射表實質上替代了上述解釋器獲取間接轉移目標的功能.

比較成熟的使用地址映射表法處理間接轉移問題的二進制翻譯系統如Shen等人[18]提出的基于LLVM(low level virtual machine)的動靜結合的二進制翻譯系統HBT和盧帥兵等人[17]提出的基于QEMU的靜態翻譯器SQEMU.

1.2 基于LLVM的動靜結合的二進制翻譯系統HBT

HBT系統將動態翻譯器作為目標代碼的一個動態庫鏈接入二進制文件，在翻譯源程序完畢開始執行時若遇到間接轉移指令，則查找地址映射表確認分支目標地址，如未找到，則啟動動態二進制翻譯器進行處理.可見，地址映射表結構的設計直接關系到系統執行的效率.

另外，HBT采用LLVM switch 指令，生成一系列的if-else指令，這些指令需要比較和跳轉才能定位到目標跳轉地址，該方法的又一個局限性是不可能將所有的目標地址放入LLVM switch列表.實際上，HBT僅將返回地址、函數指針、函數入口點作為地址映射表項，對switch語句產生的間接跳轉指令并沒有統一的解決方法，在實現中僅對ARM平臺二進制文件進行了處理.

1.3 基于QEMU的靜態翻譯器SQEMU

SQEMU是基于QEMU改造的一個靜態翻譯器，其實質是采用地址映射表法處理間接轉移問題，其具體翻譯過程如圖1所示，其中TCG(tiny code generator)為QEMU自帶的中間表示.

Fig. 1 Framework of SQEMU圖1 SQEMU框架設計

SQEMU分離了翻譯時間、代碼優化時間和目標程序執行時間[17]，使得目標程序在翻譯中及翻譯后能夠采用不同層次的優化算法，生成更高質量的執行代碼，這也是靜態二進制翻譯器的優勢.首先，SQEMU線性遍歷、逐行翻譯源程序，并使用地址索引映射表記錄每一條源平臺指令對應的目的平臺指令塊起始地址，成功解決了靜態二進制翻譯中由間接跳轉和間接轉移指令引起的代碼發現和代碼定位問題.另外，SQEMU實現了對本地庫函數的封裝[19]，在目標平臺模擬源平臺參數傳遞和返回規則，實現了目標程序調用本地庫函數的功能，提高了程序執行效率.

但是，為解決靜態二進制翻譯面臨的代碼發現和代碼定位問題，SQEMU采用線性遍歷、逐行翻譯的方法，通過生成每一條x86指令對應的標簽來輔助進行代碼定位。該方法存在2個問題:1)逐行翻譯的方式忽略了程序上下文信息，無法借助基本塊優化算法等對翻譯代碼進行有效優化；2)逐行翻譯引入了較多的冗余代碼，導致代碼膨脹率較高，程序整體執行效率較低.

為解決SQEMU逐行翻譯無法進行塊內優化以及引入較多冗余代碼、目標程序執行效率較低的問題，本文引入了基本塊翻譯方式.但與此同時，基本塊翻譯方式，又帶來了代碼發現和代碼定位的問題.為解決代碼發現問題，本文提出反饋式二進制翻譯框架，將代碼發現放入程序執行過程，在程序執行時進行監控，利用執行反饋情況獲取程序間接轉移目標地址；為與反饋框架相匹配并高效解決代碼定位問題，本文改進了SQEMU地址索引映射表，提出了基于基本塊首地址的二級地址映射表和映射方法.

2 反饋式靜態二進制翻譯框架FD-SQEMU

靜態翻譯是將源平臺的二進制可執行文件完全翻譯到目標機器上，通常一次翻譯后就可以多次在目標平臺上運行，并且因為其翻譯過程耗費的時間不計入執行時間，所以靜態翻譯可以花費大量的時間用于生成代碼的優化，而且靜態翻譯可以利用程序以往執行的記錄進行優化，以獲得更高的效率.

但是，靜態二進制翻譯在翻譯帶有間接轉移指令的程序時，由于無法獲得運行時信息，可能無法獲得間接跳轉和間接調用的目標地址，無法準確定位到目標平臺上該轉移地址，進而無法正確實現源二進制程序的功能，不能保證程序翻譯的等價性.逐行翻譯方式，雖然能夠很好地進行代碼定位，因為每一行源代碼均對應一個目的平臺代碼塊，直接或者間接跳轉的任意地址均可以被準確定位，但是該方法無法進行塊內優化且程序效率較低.而基本塊翻譯方式只記錄了基本塊的首地址，對于轉移目的地址在基本塊中間的間接跳轉或者間接調用指令則無法處理.

為了確定間接跳轉和間接調用的目的地址，本文設計并實現了反饋式靜態二進制翻譯框架.其基本思想是，先翻譯源二進制程序，進而執行、監控，在遇到無法確定目標地址的間接跳轉或者間接調用時，終止執行并反饋回跳轉的目標地址；然后將該跳轉目標地址作為一個新的基本塊起始地址，重新對源平臺二進制文件進行基本塊劃分，重新翻譯，直至能完整實現源二進制文件的功能，實現程序等價性翻譯[20].

本文設計的反饋式靜態二進制翻譯框架如圖2所示，主要包括8個模塊：預處理模塊、源文件解析器、前端解碼器、TCG分析優化器、后端編碼器、目標文件生成器、動態執行模塊和反饋地址處理模塊.

Fig. 2 Framework of FD-SQEMU圖2 FD-SQEMU框架設計

1) 預處理模塊.分析源平臺可執行文件，獲取源程序的代碼段，對程序的代碼段進行基本塊劃分，生成基本塊信息表Tb，基本塊劃分方式與《編譯與反編譯技術》這本書中介紹的相同.

2) 源文件解析器.分析源平臺可執行文件，獲取程序入口地址，提取代碼段、數據段、只讀數據段、初始化段、動態鏈接表、全局符號表等.代碼段，用于結合基本塊信息表進行靜態翻譯；數據段和只讀數據段用于翻譯后程序的執行；動態鏈接表和全局符號表用于對系統函數和用戶函數的定位以及使用.

3) 前端解碼器.以基本塊為單位對源平臺指令解碼.FD-SQEMU采用了QEMU前端，保留了QEMU能對多源平臺如x86，ARM，MIPS等平臺的指令解碼功能，并根據譯碼器分析出的指令生成相對應的TCG指令，在遇到間接轉移指令時，在該間接轉移指令前加上異常處理指令.

4) TCG分析優化器.對中間表示無關語言TCG進行平臺無關化優化，如活性分析、塊內寄存器分配、塊內代碼優化等.

5) 后端編碼器.依據TCG中間表示生成目標平臺機器指令.在目標代碼層次，根據目標平臺特點采取可行的優化措施，如用戶函數調用與返回時冗余操作的消除、調用庫函數時寄存器快速傳遞參數等.

6) 目標文件生成器.重新組合從源文件分析器獲得的可執行文件的數據段、只讀數據段和全局符號表信息，從TCG生成器獲得的代碼段、初始化段對應的TCG中間表示序列，生成TCG對應的目標平臺可執行elf文件，需要處理庫函數接口、間接跳轉和間接調用指令.

7) 動態執行模塊.提供執行環境，保障由目標文件生成器生成的目標機器代碼執行.若程序完整地正確執行，則說明程序翻譯完成；若執行遇到間接轉移地址找不到的情況，則返回該轉移目標地址，此處返回的地址是源平臺可執行文件中的跳轉目標地址.

8) 反饋地址處理模塊.該模塊依據動態執行模塊返回的跳轉目標地址，對源平臺可執行文件重新劃分基本塊，并更新基本塊信息表Tb，以供系統重新翻譯.

實質上，該翻譯框架依舊是基于QEMU[21]設計的，繼續沿用了QEMU的前端文件分析和TCG中間表示，并繼承了QEMU的跨平臺特性[22].另外，在FD-SQEMU中，對庫函數的處理繼續采用了SQEMU中庫函數封裝方法以及庫函數本地化調用方法，以提升程序的運行效率.

3 間接轉移指令的處理

間接轉移指令在靜態分析時無法確定該指令跳轉的目標地址，針對不同運行環境或者運行對象，其轉移目標可能不同，本文通過動態執行反饋機制獲取間接轉移目標地址，進而結合二級地址映射表來確定目的平臺上轉移目標地址.下面對二級地址映射表的構造和查找過程以及間接轉移目標地址的獲取進行詳述.

3.1 相關定義與符號約定

本文定義下述符號表示翻譯過程中涉及的概念.

Ms：源平臺;

Mt：目的平臺;

Is:源機器平臺指令；

Asi:源平臺間接轉移目標地址；

Bs：源平臺二進制文件；

Bt：使用FD-SQEMU翻譯源平臺二進制文件Bs到Mt所得的二進制文件；

B0,B1,…,Bn,…：源平臺劃分的各基本塊，B0表示從程序入口開始的第1個基本塊；

A0，A1,…,An,…：源平臺劃分的各基本塊的起始地址(指令塊第1條指令的地址)；

LB0,LB1,…,LBn,…：源平臺指令基本塊對應的目標平臺指令塊；

LA0，LA1,…,LAn,…：源平臺劃分的各基本塊的起始地址對應的目標平臺指令塊起始地址.

3.2 間接轉移處理過程

對于間接轉移來說，通過靜態分析確定間接轉移的目標地址是非常難的問題，而且該間接轉移指令可能跳轉到程序的任何一個位置，本文采用反饋方式，借助動態執行profile信息獲取間接轉移目標地址，具體獲取過程算法流程如圖3所示：

Fig. 3 Solving process of indirect branch圖3 間接轉移處理過程

1) 預處理模塊對源平臺二進制文件Bs進行基本塊劃分，獲取各基本塊起始和結束地址信息，存入基本塊信息表Tb，初始基本塊劃分算法如算法1所示.

2) 根據源平臺二進制文件Bs以及基本塊信息表Tb，結合靜態二進制翻譯器生成目標平臺二進制文件Bt，并在生成Bt的過程中在間接轉移指令前添加異常處理反饋指令進行監控反饋，詳細算法見3.4節的算法4.

3) 將生成的目標平臺二進制文件Bt，在動態執行模塊執行，如果程序正常結束，則說明程序已翻譯完成，可存儲供后續使用；如程序找不到轉移目標地址Asi(說明該地址不是已劃分基本塊首地址)，異常結束，則返回該轉移目標地址供反饋模塊處理.

4) 反饋處理模塊依據程序異常結束拋出的轉移目標地址Asi，對源平臺二進制文件Bs重新進行基本塊劃分，并更新基本塊信息表Tb；之后，依據更新后的基本塊信息表Tb，重新對源平臺二進制文件進行翻譯，待再次翻譯完成后重新執行；重復此過程，直至程序能正常執行、正常結束，完成該源程序的翻譯.

算法1. 初始基本塊劃分算法.

功能：對x86源代碼進行初始基本塊劃分；

輸入：x86匯編代碼；

輸出：基本塊信息表Tb.

① 獲取每個基本塊的入口語句：程序的第1條語句，能由跳轉語句或者函數調用語句轉移到的語句，緊跟在條件轉移或者函數調用語句后的語句.

② 確定每條入口語句所屬的基本塊：由該入口語句到下一條入口語句、轉移語句或者停語句之間的語句序列.

③ 刪除掉未被納入到基本塊中間的語句，并根據基本塊起止地址信息生成基本塊信息表Tb.

在對源程序重新進行基本塊劃分時，重點便是更新基本塊信息表Tb，主要是更新該表中基本塊的起始地址和結束地址.在反饋模塊更新基本塊信息表Tb時，如發現某一轉移目標地址Asi在某一基本塊Bx的中間(該地址大于基本塊起始地址，小于該基本塊結束地址)，則將該基本塊Bx劃分為2個基本塊，并以轉移目標地址Asi為下一基本塊的起始地址，該轉移目標地址上一條指令的地址為上一基本塊的結束地址，以圖4 QUICKSORT程序的核心代碼片段為例進行說明.

如圖4所示，如在原先劃分的起始地址Ax為0x4007f5、結束地址是0x400899的基本塊Bx中有一間接轉移目標地址Asin為0x40080d，則將原來的基本塊拆分為2個基本塊，這2個基本塊的起止地址分別是0x4007f5～0x400809，0x40080d～0x400899，并據此更新基本塊信息表Tb，為源平臺二進制程序后續的靜態翻譯提供基本塊劃分信息.

針對間接轉移目標地址的確定，本系統將其作為基本塊首地址進行處理，并存入二級地址映射表,以方便轉移地址的快速查找及定位.

3.3 地映射表的構造

在確定源平臺間接轉移目標地址后，其就成為一基本塊的起始地址，為了保證程序的邏輯關系以及正確翻譯，在翻譯時必須保證各基本塊首地址映射的正確性.

為了解決Ms指令塊地址到Mt指令塊地址的映射問題，需要保存所有Ms基本塊對應的Mt基本塊的地址，并采用合適的方式來保證映射過程的高效性，以提高程序的效率及質量.

地址映射表的構造是在翻譯階段完成的.首先使用源文件解析器，分析源可執行文件的各個段數據，提取出包含指令的代碼段、初始化段、附加段信息，然后使用前端解碼器按照地址從小到大(即A0，A1,…,An，…)的順序逐塊翻譯Ms指令到TCG中間表示，再借助后端編碼器翻譯為Mt指令.在生成目標代碼的過程中，如在翻譯以An為起始地址的一個指令塊Bn時，在生成目標代碼首部加上標簽LAn，并且使用數組Address保存此標簽值，此標簽值即目標地址信息.另外，使用An相對A0的偏移量作為索引，能夠快速定位目的地址.

圖5給出了在翻譯中二級地址映射表的構造過程及源平臺和目標平臺指令塊地址映射信息.

圖5詳細給出了存儲源平臺代碼塊首地址到目的平臺代碼塊首地址信息的二級地址映射表的構造過程，其中二級地址映射表的具體生成算法如算法2所示.在算法2中，使用數組Address存儲源平臺Ms指令塊翻譯為Mt平臺指令塊的首地址，使用數組Index存儲與Ms指令塊對應的Mt指令塊在數組Address中的索引位置.

Fig. 5 Construction of two-level address mapping table圖5 二級地址映射表的構造過程

算法2. 地址映射表的構造算法.

功能：構造源程序地址到目標平臺程序地址的映射表；

輸入：包含基本塊Bn起始地址An和結束地址En的基本塊信息表Tb；

輸出：地址數組Address和索引數組Index.

① FOR每一個{A0,A1,…,An,…} 中的Ax

② 分析起始地址為Ax的基本塊Bx中的操作碼和操作數，并將分析結果翻譯成TCG中間代碼；

③ 將TCG中間代碼翻譯至目標機器代碼，并使用LAx記錄目標機器代碼塊的起始地址，令Address[x]=LAx,Index[Ax-A0]=x;

④ END FOR

在構造二級地址映射表后，本文設計了間接轉移分支指令目的地址的查找算法，如算法3所示.

算法3. 間接轉移分支指令目的地址查找算法.

功能：獲得間接轉移分支指令的目的地址；

輸入：Ms源平臺程序起始地址和Mt目標平臺上間接轉移指令的目的地址；

輸出：目標平臺Mt上間接轉移目標地址.

① 獲取Ms源平臺程序起始地址Ax和源程序間接轉移目標地址A0；

② 計算Ax相對于A0的偏移地址：Ax-A0；

③ 返回Mt目標平臺上間接轉移目標地址：

Address[Index[Ax-A0]].

如算法3所示，結合二級地址映射，采用算法3，利用源平臺程序基本塊起始地址信息，僅需3條指令即可定位到間接轉移目標地址.

下面舉例說明該二級地址映射表構造及查找算法的執行效果.當Ms為x86平臺、Mt為某國產平臺時，基本塊B0的起始地址A0=0x400530，前3個指令塊的第1條指令分別為xor，pop，mov，對應的TCG中間表示代碼塊和生成的申威國產平臺指令塊如圖6所示.

Fig. 6 Example of translating x86 ISA to national ISA圖6 x86指令塊翻譯為某類國產平臺的指令舉例

在目標平臺二進制文件運行遇到間接轉移指令如call *%rax時，以間接轉移指令目標地址rax為0x4005ce為例,使用間接轉移分支指令目的地址查找算法僅使用3條指令即可獲得標簽L_0x4005ce的值，然后轉移到該標簽的位置.具體定位間接跳轉過程為：首先依據源平臺間接轉移地址0x4005ce，訪問Index[0x4005ce-0x400530]即Index[158]，獲得以0x4005ce為起始地址的代碼塊對應的目的平臺代碼塊起始地址L_0x4005ce在數組Address中的位置1；繼而訪問Address[1]獲得L_0x4005ce的值，即定位到間接轉移分支目的地址.

從算法2可以看出，Address保存了所有Ms指令塊對應的目標代碼塊地址，Index保存了該所有Ms指令塊在Address中的索引位置.如此設計，一是思路簡單明了、利于實現，二是查找目標平臺間接轉移目標地址效率較高，以地址索引映射表查找方法、以最小的查詢代價，解決了間接跳轉和間接調用的代碼發現問題.

3.4 間接轉移目標地址的反饋

實際上，在對源平臺二進制文件進行基本塊劃分后，經過翻譯對于大部分間接調用地址基本都能夠在二級地址映射表中查詢得到，這是因為間接調用一般都是調用的子函數，而子函數的入口地址已經被處理為某一基本塊的起始地址，并且該地址已經存儲在二級地址映射表中，在動態執行時可以查詢得到；而對于部分間接跳轉指令，因為跳轉指令地址的不確定性，其可能跳轉到程序的任何位置，比如原先劃分的基本塊中間某地址，此時該目標地址的確定是重中之重，這也是反饋機制存在的必要性.本文通過借助QEMU的Helper機制在翻譯源平臺可執行程序時添加異常處理反饋代碼，采用監控程序執行的方式獲取間接轉移目標地址，該間接轉移地址反饋算法如算法4所示：

算法4. 間接轉移地址反饋算法.

輸入：Ms源平臺上指令Is,如callq *%rax和jmpq *0x200c04(%rip)指令；

輸出：Ms源平臺上不是塊首地址的間接轉移目標地址.

① 分析Ms源平臺上間接轉移指令Is，獲取操作碼opcodes和操作數oprands.

② IFIs是間接轉移指令

③ IFIndex[oprands-A0]≤0

④ 將該操作碼oprands寫入間接轉移地址存儲文件IndirectAdd；

⑤ 程序終止；

⑥ END IF

⑦ ELSE

⑧ 將源平臺指令Is翻譯成TCG中間表示；

⑨ 將TCG中間表示翻譯成Mt目標平臺本地代碼；

⑩ END IF

下面舉例說明算法4的工作原理，依舊以圖4中的間接調用指令callq *%rax為例，在對這條指令進行翻譯時，根據如算法4所示的間接轉移地址反饋過程，在實際將該指令翻譯成目標平臺指令前，首先檢查該間接轉移的源平臺目標地址(rax寄存器中的值0x4005ce)是否已經在二級地址映射表中，根據二級地址映射的構造方法，此時Index[0x4005ce-A0]>0，則Address[Index[0x4005ce-A0]]=L_0x4005ce即為callq *%rax間接調用目標平臺的跳轉地址，此時使用翻譯器正常對該指令翻譯即可.

以間接跳轉指令jmpq *0x200c04(%rip)為例，若Address[Index[0x200c04(%rip)-A0]]==0，則說明該跳轉目標地址未存儲在數組Address中，此時即跳轉目標地址未定，需在jmpq *0x200c04(%rip)指令執行前將0x200c04(%rip)中的值通過文件進行反饋，并終止程序的執行，否則可能會造成不可預知的異常終止情況；待將該間接跳轉的源目標平臺轉移地址確定后，即可更新基本塊信息表Tb，并在翻譯時將該間接轉移的源平臺目標地址和目標平臺地址存入數組Address，如此即可在程序執行時準確定位該間接轉移的目標地址.

4 實驗和結果

下面對FD-SQEMU進行測試，測試的結果分別與QEMU和SQEMU進行比較.測試內容主要包括3個方面:1)正確性測試;2)性能測試;3)反饋次數測試.考慮到程序執行的局部性原理，性能測試中又分為熱代碼測試和整體性能測試2個方面.

熱代碼測試主要針對循環體和遞歸函數，對循環熱代碼的測試主要依托NBENCH測試集進行，對遞歸熱代碼的測試主要通過FIBONACCI,N-QUEEN,QUICKSORT,MERGESORT進行測試；整體性能測試主要通過選取SPEC2006測試集中的部分程序進行測試；與此同時，在各個對象的測試中，記錄每個測試程序含有的所有及需要反饋處理的間接調用和間接跳轉個數.

令TFD-SQEMU,TQEMU,TSQEMU分別表示FD -SQEMU,QEMU,SQEMU執行翻譯后可執行程序的執行時間，定義速度比：

4.1 實驗環境

Ms為x86體系架構的機器，Mt為國產某處理器，主頻1.4 GHz，內存4 GB，操作系統為Fedora，內核版本3.8.0,編譯器為gcc，版本4.5.3.

QEMU與FD-SQEMU運行在Mt機器上.測試用例是NBENCH版本2.2.3，手動實現的主流遞歸算法和SPEC2006測試集[23].

4.2 正確性測試

針對FD-SQEMU的正確性測試主要分為2個部分:1)指令翻譯測試;2)實際程序翻譯測試.

指令翻譯測試借助QEMU自帶的test-i386測試集，重點對x86架構用戶態的指令進行了測試.依據x86指令分類情況，具體的測試結果如表1所示:

Table 1 Correctness Test of Instruction Translation 表1 指令翻譯的正確性測試

在保證了單條指令翻譯的正確性后，對實際程序翻譯進行了正確性測試.具體測試過程如下：首先，在x86平臺上編譯SPEC CPU2006和NBENCH測試集等測試程序并運行記錄結果；然后，在目標平臺上運行翻譯后的可執行程序，并與x86上運行結果相比對.部分程序的測試結果如表2所示：

Table 2 Correctness Test of Program表2 實際程序的正確性測試

Notes: “√” mean that the test cases have passed the correctness verification.

表2的實驗結果表明，翻譯后的目標程序執行結果與源x86平臺上程序執行結果相同，驗證了本文提出的翻譯框架和算法能夠進行正確翻譯，做到了程序翻譯的功能等價.

4.3 循環熱代碼性能測試

NBENCH測試集的主要功能是通過計算一定時間內(一般是5 s)單項測試代碼塊的循環迭代次數來評價系統性能，其中每一個測試塊都是典型的熱代碼，具體的NBENCH測試集各部分功能如表3所示:

Table 3 NBENCH Tasks 表3 NBENCH測試任務

為了展示FD-SQEMU處理熱代碼的能力，我們分別用FD-SQEMU,SQEEMU和QEMU翻譯系統對NBENCH測試集進行測試，并將測試結果進行對比.針對NBENCH測試集，FS-QEMU和SQEMU相對于QEMU的性能提升情況如圖7所示:

Fig. 7 Speedup ratio on NBENCH圖7 FD-SQEMU，SQEMU在NBENCH測試集上的加速比

如圖7所示，對于不同的測試項目，SQEMU和QEMU展示了各自的性能優勢；而FD-QEMU保持了SQEMU和QEMU兩個的性能優勢，并有一定程度上的性能提升.對于STRING_SORT功能測試，因為字符串操作頻繁使用strcmp,strncmp等字符串相關庫函數，FD-SQEMU和SQEMU分別獲得42.57倍和39.25倍的加速比；類似地，因為FOURIER,IDEA,FP EMULATION功能測試使用了pow,sin,cos,memmove等庫函數，FD-SQEMU和SQMEU獲得相應的加速比，并且針對這些功能的測試，FD-SQEMU相對于SQEMU有12%左右的加速比，這是因為FD-SQEMU在繼續沿用SQEMU庫函數本地化的基礎上，采用了基本塊的翻譯方式，在翻譯時進行了更多的優化，提高了生成代碼的質量；對于NUEURAL NET和LU DECOMPOSITION功能測試，SQEMU運行反而比QEMU要慢，但此時FD-SQEMU相比于SQEMU有較高的加速，最高加速可達到36%，因為SQEMU在單條翻譯NEURAL NET和LU DECOMPOSITION時缺少上下文關系，并引入了較多的冗余指令，而FD-SQEMU采用基本塊翻譯，一定程度上保留了源可執行文件的上下文關系，并在翻譯中使用了少量的塊內優化方法，所以對于NUEURAL NET和LU DECOMPOSITION功能測試，FD-SQEMU相比于QEMU有少量的加速，相對于SQEMU的性能提升較為明顯.對于NBENCH測試集，FD-SQEMU相對于QEMU的平均加速比為6.913，相對于SQEMU的平均加速比為1.16.

從NBENCH的測試結果看，FD-SQEMU繼承了SQEMU的優點，并有效去除了SQEMU逐行翻譯引入的部分冗余指令，FD-SQEMU相比于SQEMU的平均性能提升了16.14%.

4.4 遞歸熱代碼性能測試

遞歸算法是會反復執行的熱代碼，遞歸中對單一或某些函數的反復調用會產生大量的函數調用和返回指令，能否高效地處理函數調用，直接影響目標程序執行的效率，本文對典型的遞歸算法進行了測試，并給出了FD-SQEMU和SQEMU相比于QEMU的加速比，具體情況如圖8所示:

Fig. 8 Speedup ratio on recursive algorithms圖8 FD-SQEMU,SQEMU對QEMU在遞歸算法的加速比

如圖8所示，FD-SQEMU繼承了SQEMU對遞歸熱代碼的處理能力，并在性能上有一定的提升，平均性能提升了17.25%.這是因為FD-SQEMU繼承了SQEMU的本地棧作為影子棧[24]實現用戶自定義函數本地化調用的思想，有效減少了函數調用和返回時代碼切換的消耗，保證了相對QEMU的性能提升；在此基礎上FD-SQEMU使用基本塊方式翻譯，一是有效去除了SQEMU逐行翻譯中的冗余代碼并對代碼進行了一定程度的塊內優化，在翻譯代碼膨脹率上FD-SQEMU整體比SQEMU降低了約20%.

4.5 整體性能測試

在對FD-SQEMU整體性能進行測試時，使用的是SPEC2006測試集.SPEC2006測試集中的程序基本都是實際應用中常用到的程序，該測試集的執行結果能夠反映出一個翻譯系統的整體性能.圖9展示了對SPEC2006中部分應用進行測試時FD-SQEMU和SQEMU相對QEMU的性能提升情況.

Fig. 9 Speedup ratio on part of SPEC2006圖9 FD-SQEMU,SQEMU在SPEC2006測試集上的加速比

如圖9所示，對于BZIP2，MILC程序，FD-SQEMU和SQEMU相比于QEMU獲得了1倍多的加速，這是因為這些實際應用中大量代碼迭代次數少，函數重復調用較少，FD-SQEMU和SQEMU在目標代碼執行階段不需要再翻譯和代碼維護，消除了QEMU的代碼塊切換的時間，提高了目標平臺代碼的執行效率；在SPEC 2006測試集中SPECRAND和MCF程序獲得了較高的加速比，對于SPECRAND程序，FD-SQEMU相比于QEMU的加速比高達6.91，這是因為SPECRAND程序反復使用到了產生隨機數的庫函數，對于MCF程序同樣也是如此.

與SQEMU相比，對于SPEC2006中調用庫函數較少的程序進行測試，FD-SQEMU比SQEMU整體性能提升了19.1%；對于反復調用庫函數的SPEC2006程序進行測試，FD-SQEMU對SQEMU性能僅提升了約15%，這是因為FD-SQEMU相比于SQEMU在對庫函數處理上并沒有較大的改進.總體上，對部分SPEC2006程序的測試，FD-SQEMU相比于SQEMU整體性能平均提升了16.75%.

4.6 反饋情況測試

作為反饋式靜態二進制翻譯器FD-SQEMU，在翻譯程序時所需反饋次數也是其性能的重要衡量標準.

在測試時，針對可能存在的因參數不同執行路徑不同的情況，本文做了多種參數的測試，并將各測試實例代碼段中所有間接跳轉和間接調用以及需要通過反饋處理的間接跳轉和間接調用情況進行統計，如表4所示.

如表4中所示，FD-SQEMU對各測試項的反饋運行次數情況并不相同，MCF,FIBONACCI,QUICKSORT,MERGESORT,N-QUEEN,SPECRAND中反饋次數為0，這是因為在這些應用程序中的間接跳轉和間接調用目標地址都為某一函數或者基本塊的首地址，不存在跳轉到某一基本塊中間的情況，此時在數組Address中可以查詢得到該跳轉目標地址在目標平臺上的指令地址，不需要反饋執行；而對于NBENCH測試集的BZIP2和MILC，因為這些程序中部分間接跳轉和間接調用目標地址在原先劃分的基本塊中間，所以需要通過反饋來獲得該地址并對原先基本塊重新劃分，以方便將該地址存入二級地址映射表中進行間接轉移目標定位.實際上在NBENCH,BZIP2,MILC中雖然有較多的間接跳轉和間接調用指令，但是需要進行反饋處理的并不多，其中大部分間接轉移目標地址為某一子程序的起始地址或者某一基本塊的起始地址.實際完成源程序翻譯所需的反饋次數與該程序中間接轉移目標地址在之前劃分的基本塊中間的轉移指令數成線性關系.最初的基本塊信息表Tb的生成，直接影響著程序需要執行、反饋、重翻譯的次數.

Table 4 Translation Feedback Situation of FD-SQEMU表4 FD-SQEMU翻譯反饋情況

5 總 結

本文在分析現有靜態二進制翻譯中解決間接轉移問題方法的基礎上，針對現有間接轉移問題處理方法中線性遍歷翻譯方式代碼優化較少、冗余代碼較多的缺陷，對基于動態QEMU的靜態二進制翻譯器SQEMU進行了改進，提出了基于基本塊翻譯的反饋式靜態二進制翻譯框架FD-SQEMU，并結合二級地址映射表實現了間接轉移目標地址的快速映射.首先，FD-SQEMU在繼承SQEMU庫函數本地化的基礎上，引入基本塊翻譯方式，解決了SQEMU逐行翻譯無法兼顧程序上下文進行塊內優化以及引入大量冗余代碼的缺陷；接著，采用反饋機制，并結合新的二級地址映射表及查找算法，以較高效率解決了靜態二進制翻譯中間接跳轉和間接調用中的代碼發現及定位的問題;最后，通過與SQEMU和QEMU的性能對比實驗，驗證了反饋式靜態二進制翻譯器FD-SQEMU的正確性和有效性.

但在反饋式靜態二進制翻譯中，針對源二進制程序的最初基本塊信息表Tb的建立直接關系到反饋次數，如何根據源二進制程序特性建立更合適的起始基本塊信息表以減少反饋次數還需要進一步分析；另外，在該翻譯過程中，采用的代碼優化較少，還可利用現有的代碼優化方法進一步對翻譯代碼進行優化，以生成更高質量的目標代碼，提高目標代碼的執行效率.