在二進制翻譯中利用本地庫代碼

譚月輝，尹文龍，郭寶鋒，崔佩璋

(1.山西農(nóng)業(yè)大學 信息學院， 山西 晉中 030801; 2 陸軍工程大學石家莊校區(qū) 電子與光學工程系， 石家莊 050003)

二進制翻譯[1]已廣泛應用于軟件安全分析[2]、軟件逆向工程、系統(tǒng)虛擬等領域，并已成為軟件遷移的主流技術。例如，F(xiàn)X!32把x86平臺下的Win32應用程序翻譯到Alpha平臺[3]；昆士蘭大學開發(fā)的跨平臺靜態(tài)二進制翻譯器UQBT，可以支持不同源平臺和目的平臺[4]；跨平臺動態(tài)二進制翻譯器QEMU，支持進程級和系統(tǒng)級虛擬，已支持國產(chǎn)龍芯平臺[5]。

主流二進制翻譯可以分為動態(tài)二進制翻譯、靜態(tài)二進制翻譯和動靜結合的二進制翻譯。動態(tài)二進制翻譯是一種即時翻譯技術，在運行目標程序時動態(tài)生成所需代碼，能夠較好解決代碼發(fā)現(xiàn)和代碼定位問題[6-8]。動態(tài)二進制翻譯需要在執(zhí)行目標程序的同時生成目標代碼，代碼優(yōu)化時間包含于程序執(zhí)行時間，所以不能采用深度的優(yōu)化方法。另外，動態(tài)二進制翻譯須在執(zhí)行所生成目標代碼的同時，完成加載分析、運行環(huán)境設置、實時翻譯、代碼緩存管理、代碼塊切換等工作。一些技術如熱路徑優(yōu)化[9]、寄存器映射[10]、多線程優(yōu)化[5]等提高了動態(tài)二進制翻譯的效率，但未解決動態(tài)二進制翻譯效率低的問題。靜態(tài)二進制翻譯在不運行目標程序的情況下，靜態(tài)分析可執(zhí)行程序，提取指令進行翻譯，能采用復雜的代碼分析和優(yōu)化算法，生成高質量代碼，執(zhí)行效率高[5]。但靜態(tài)二進制翻譯難處理代碼發(fā)現(xiàn)和代碼定位問題，在實際應用中受到限制。

由于程序的局部性特點，即20%的代碼占用了80%的執(zhí)行時間。二進制翻譯生成的代碼質量是影響二進制翻譯效率的最重要的因素。傳統(tǒng)優(yōu)化技術著重于從中間代碼層到目標指令層的基本塊級優(yōu)化，而忽視了不同平臺間具有的共享代碼庫。本文為充分利用當前可執(zhí)行文件使用動態(tài)鏈接庫的特點，針對動態(tài)鏈接庫共享代碼進行替換，從而減少翻譯開銷和提升代碼質量，提升系統(tǒng)效率。

本文首先使用形式化的方法給出代碼優(yōu)化的上界，然后提出使用本地函數(shù)庫的Jecket方法并證明該方法對翻譯的代碼塊達到了理論的優(yōu)化上界，最后，在流行的動態(tài)二進制翻譯器QEMU系統(tǒng)中實現(xiàn)該算法，并使用nbench測試集驗證了Jecket算法能夠顯著提升運行效率。

1 相關研究

Jens提出了動態(tài)二進制翻譯的形式化模型，首先，Jens根據(jù)理論計算機圖靈機模型提出了更接近真實機的形式化表示形式，進而給出了二進制翻譯遵循的原則，最后給出代碼優(yōu)化的上界的表示形式。其中一些重要的理論表示如下：

M(S,I,γ)表示計算機，其中:S表示計算機的狀態(tài)，I表示計算機的指令集，γ表示I×S→S的映射，表示在某個機器狀態(tài)下對某條指令的解釋。

令Ms(S,I,γ)表示源平臺計算機，Mt(S,I,γ)表示模板平臺計算機，基于此，二進制翻譯可表示為：

尋找一個映射φ使得源平臺在當前狀態(tài)下s解釋指令i，總有對應的目標平臺對應的狀態(tài)s′執(zhí)行i′=φ(i)。該映射φ就是二進制翻譯的核心工作之一。

由于映射φ并不是唯一的，為了得到最優(yōu)的形式，各種中間表示優(yōu)化方法都是對映射函數(shù)φ的簡化，對于Jens所實現(xiàn)的系統(tǒng)Yirr-Ma，Jens證明了其最優(yōu)形式代碼優(yōu)化包括機器狀態(tài)映射和指令映射，并舉例說明其代碼優(yōu)化最優(yōu)情況下增加的開銷是290%。

Jens致力于優(yōu)化機器狀態(tài)的映射和指令塊的翻譯，而忽略了從語義層的模擬，導致其優(yōu)化無法從更高的語義層面上的語義塊的映射。本文從程序等價變換的角度給出了二進制翻譯可度量的優(yōu)化上界，從而在理論和實踐上指導工程應用。

2 二進制翻譯的等價性和優(yōu)化上界

程序等價變換是指在保持程序功能不變的前提下，對程序的結構、執(zhí)行模式、存儲模式、編程模式等做出的變換。目的是提高變換后程序的執(zhí)行效率、安全性、可移植性等，包括低級語言到低級語言的變換，如二進制翻譯、數(shù)學庫的性能調優(yōu)；高級語言到低級語言的變換，典型的高級語言編譯器；串行程序到并行程序的變換，如高性能平臺軟件并行化移植。程序變換的等價性，目前只能在給定的系統(tǒng)上判定程序變換前后功能性語義的等價性，尚沒有統(tǒng)一的等價性定義。二進制翻譯是一種指令層次的程序等價變換，其有關理論也適用于二進制翻譯。

2.1 二進制翻譯等價性定義

根據(jù)Jens的二進制翻譯模型，結合程序變換的相關理論，把二進制翻譯的等價性在指令層面和語義層面給出等價性定義。

定義1指令級等價 源平臺Ms，目標平臺Mt，當滿足γ(s,i)=γ′(φ(s),φ(i))=γ′(s′,φ(i))時，二進制翻譯指令映射和狀態(tài)映射是等價的。

該定義說明了在指令級別模擬的強等價情況，是程序等價的強等價模式。在一些二進制翻譯器中，對源平臺指令進行逐條指令解釋執(zhí)行就滿足指令級等價要求。但是這種強等價定義限制了優(yōu)化函數(shù)的層次，只能對每個指令進行優(yōu)化，而不能根據(jù)指令所在基本塊或者函數(shù)語義進行優(yōu)化。

定義2語義級等價源平臺Ms，目標平臺Mt，對于任意指令序列t={i1,i2,i3,…}當滿足γ(s,t)=r′(φ(s),φ(t))=γ′(s′,t′)時，二進制翻譯指令映射和狀態(tài)映射是等價的。

語義級等價要求Mt在初始狀態(tài)執(zhí)行了翻譯的目標平臺指令序列φ(t)后，得到的最終狀態(tài)與源平臺執(zhí)行t得到的狀態(tài)對應。并不要求對每條指令的執(zhí)行都有一個與之對應的中間狀態(tài)，使得基于基本塊、超級塊和函數(shù)級的優(yōu)化能夠進行。

等價性定義類似于數(shù)學同構概念，能夠反映出源平臺和目標平臺在可計算性上的一致性。根據(jù)該等價性定義，我們給出二進制翻譯的優(yōu)化上界。

2.2 二進制翻譯優(yōu)化上界

證明：

令δs,δt表示平臺Ms和Mt的編譯過程，有

Es=δs(B)

Et=δt(B)

那么，經(jīng)過二進制翻譯生成的可執(zhí)行文件Est可表示為

可見，二進制翻譯過程是程序從源文件B到Mt平臺可執(zhí)行文件的一種變換過程，同樣的δt也是B到Et的一種變換，而且有

該定理是顯而易見的，通常由于二進制翻譯系統(tǒng)的復雜性和不同平臺的特殊性，二進制翻譯的效率是本地碼的1/5，甚至更低。所以，充分利用本地碼能夠極大的提高二進制翻譯效率。

3 Jecket算法

使用Jecket算法(Jecket的涵義是算法封裝)對本地庫函數(shù)進行封裝，在目標平臺模擬源平臺參數(shù)傳遞和返回規(guī)則，實現(xiàn)目標二進制文件運行時調用本地庫函數(shù)的功能。主要包括以下3個階段，庫函數(shù)識別、調用庫函數(shù)的指令翻譯、執(zhí)行時本地庫函數(shù)調用。

3.1 調用庫函數(shù)的指令翻譯

根據(jù)可執(zhí)行文件.sym表和.plt表，可以分析出指令的調用地址和庫函數(shù)名的對應關系。符號表.sym包括符號名稱、符號類型和綁定屬性、相關段索引、符號的值、符號的大小，其中根據(jù)符號類型如STT_FUNC函數(shù)類型、符號大小和符號名稱來判斷該符號是否是庫函數(shù)。圖 1展示了通過可執(zhí)行文件符號表獲取函數(shù)信息的算法過程。

一般情況下，在翻譯階段，如果函數(shù)調用指令調用動態(tài)鏈接庫函數(shù)，首先根據(jù)該庫函數(shù)的參數(shù)列表按照源平臺參數(shù)傳遞規(guī)則提取出所有參數(shù)，然后使用所提取的參數(shù)調用目的平臺對應的庫函數(shù)。在函數(shù)返回后，獲取函數(shù)返回值，并將該返回值按照源平臺規(guī)則返回到相應的寄存器或者變量。

圖2給出了一般情況下的調用庫函數(shù)的指令的翻譯算法。在進行庫函數(shù)本地化時，庫函數(shù)信息如庫函數(shù)名、參數(shù)類型、參數(shù)列表、返回值類型等需預先獲取。由于庫函數(shù)是開放并且文檔十分豐富，獲得此類函數(shù)信息十分方便。該算法針對源指令為函數(shù)調用指令的情況，當調用的目標函數(shù)在func_array中時，根據(jù)func_array的函數(shù)參數(shù)和返回值信息生成對于參數(shù)傳遞指令和調用指令，最后生成函數(shù)返回處理指令。

特殊的庫函數(shù)調用需要復雜的處理機制，當調用的庫函數(shù)參數(shù)為結構體指針時，源平臺與目的平臺結構體的實現(xiàn)不完全一致，例如某字段位數(shù)不同，字段的數(shù)據(jù)類型不同。在調用目標庫函數(shù)前，需要臨時申請目的平臺結構體空間，函數(shù)返回后把臨時結構體的各項值存儲到源平臺結構體的對應位置。

當調用的庫函數(shù)參數(shù)個數(shù)和類型不確定，如printf、sprintf、fprintf時，需要在調用接口實現(xiàn)對格式化字符串的分析，獲取實時的參數(shù)，然后調用目的平臺庫函數(shù)。

3.2 執(zhí)行時本地庫函數(shù)調用

執(zhí)行本地庫函數(shù)調用時可以直接執(zhí)行生成的二進指令，為了實現(xiàn)方便并利于調試，可采用執(zhí)行時調用本地庫函數(shù)可使用類似于QEMU中的helper函數(shù)機制，執(zhí)行環(huán)境包括參數(shù)信息，源平臺CPUState環(huán)境指針等傳遞到helpery函數(shù),helper函數(shù)根提取出參數(shù)并計算，得到結果寫入源平臺CPUState對應位置。圖 3展示了調用正弦函數(shù)sin的helper代碼示例。

由于庫函數(shù)的復雜性和多樣性，在進行庫函數(shù)封裝時需要處理參數(shù)獲取、返回值獲取、格式化字符串分析、結構體中各項值獲取等問題，庫函數(shù)封裝是一項具有挑戰(zhàn)性的工作。在源可執(zhí)行程序多次調用庫函數(shù)的情況下，庫函數(shù)本地化調用能夠顯著提升運行效率。

4 實驗

下面給出Jecket的性能測試，并與QEMU進行對比，使用nbench測試集測試了qemu-1.7.2版本實現(xiàn)Jecket算法前后的CPU，F(xiàn)PU和內存系統(tǒng)的性能。

令TQEMU和TSQEMU分別為QEMU和SQEMU執(zhí)行可執(zhí)行程序時的時間,Sspeedup為SQEMU相對QEMU的加速比，

實驗的目的在于驗證SQEMU的正確性和效率，nbench含有正確性驗證模塊，測試用例如表1所示，實驗環(huán)境如表2所示。

表1 Nbench-2.2.3測試用例

表2 二進制翻譯環(huán)境

經(jīng)統(tǒng)計，對nbench測試項目的生成代碼指令數(shù)減少了27.73%。從圖4可以看出：使用本地包裝算法Jecket后，nbench測試項目最高達到了60.70倍的加速。NEURAL NET測試項目頻繁使用庫函數(shù)exp，經(jīng)過Jecket封裝，直接調用本地庫函數(shù)，減少了大量的翻譯時間和生成代碼，極大的提升了執(zhí)行效率。對于沒有使用本地庫函數(shù)的測試項目如NUMERIC SORT，BITFIELD，F(xiàn)P EMULATIOIN等，函數(shù)本地化并不影響其執(zhí)行效率。該測試集結果顯示，對于含有庫函數(shù)調用的應用，Jecket算法有極大的加速比。

5 結論

1) 給出了二進制翻譯作為程序變化的形式化表示方法，然后給出優(yōu)化過程的一個優(yōu)化上界，探討了逼近此優(yōu)化上界的方案并給出利用本地庫函數(shù)替換翻譯過程和執(zhí)行代碼的Jecket方法，并證明了通過Jecket的庫函數(shù)部分代碼可以達到優(yōu)化上界的執(zhí)行效率。

2) 通過在二進制翻譯器qemu系統(tǒng)中實現(xiàn)Jecket算法并使用nbench測試集測試了Jecket算法的加速效率。對于核心區(qū)域含有庫函數(shù)調用的應用顯著提高了系統(tǒng)效率。