鄒 偉 高 峰 顏運(yùn)強(qiáng)

(中國(guó)工程物理研究院計(jì)算機(jī)應(yīng)用研究所 四川綿陽(yáng) 621999)

近年來(lái)，嵌入式軟件的規(guī)模與復(fù)雜度愈發(fā)增加，如何進(jìn)一步通過(guò)軟件測(cè)試、分析與驗(yàn)證提高其可靠性，一直是學(xué)術(shù)界關(guān)注的焦點(diǎn).其中，軟件插樁是一項(xiàng)十分重要的應(yīng)用于該領(lǐng)域的動(dòng)態(tài)分析技術(shù).通過(guò)軟件插樁技術(shù)[1-2]可有效收集程序執(zhí)行過(guò)程信息，如路徑覆蓋信息、函數(shù)調(diào)用關(guān)系信息，能用于軟件性能分析、程序優(yōu)化、測(cè)試覆蓋分析、測(cè)試用例生成與約簡(jiǎn)、軟件缺陷檢測(cè)與修復(fù).

當(dāng)前，軟件插樁技術(shù)包含源代碼級(jí)[3]和二進(jìn)制級(jí)[4-6]2種插樁方式，其中二進(jìn)制插樁技術(shù)又分為動(dòng)態(tài)方式和靜態(tài)方式.研究表明[7]：源代碼級(jí)插樁技術(shù)對(duì)軟件具有很強(qiáng)的侵入性，無(wú)法應(yīng)用于逆向工程或軟件測(cè)試；在二進(jìn)制插樁技術(shù)方面，靜態(tài)二進(jìn)制插樁技術(shù)，由于其較強(qiáng)的侵入性和代碼數(shù)據(jù)難以區(qū)分等難題，在實(shí)際工程中極少使用；和靜態(tài)二進(jìn)制插樁不同的是，動(dòng)態(tài)二進(jìn)制插樁[1-2,7](dynamic binary instrumentation)技術(shù)通過(guò)接管目標(biāo)程序控制流，為目標(biāo)程序提供虛擬運(yùn)行環(huán)境，進(jìn)而監(jiān)視收集目標(biāo)程序運(yùn)行信息.因而，動(dòng)態(tài)二進(jìn)制插樁技術(shù)既不需要重新編譯生成目標(biāo)碼，又不會(huì)改變目標(biāo)碼的執(zhí)行流程，完全不影響原程序執(zhí)行邏輯，具有很好的實(shí)用性.目前，動(dòng)態(tài)二進(jìn)制插樁工具主要包含Pin[8-9]，Valgrind[10]，DynamoRIO[11]等，這些工具都在動(dòng)態(tài)二進(jìn)制翻譯的過(guò)程中對(duì)軟件插樁，可以完成內(nèi)存使用、調(diào)用流、覆蓋信息等程序運(yùn)行信息分析.然而，這些工具還有十分顯著的缺陷，即它們只能對(duì)用戶級(jí)程序進(jìn)行插樁分析，不能完成對(duì)系統(tǒng)級(jí)程序分析，難以滿足嵌入式系統(tǒng)軟件動(dòng)態(tài)分析需要.

因此，亟需能分析嵌入式全系統(tǒng)軟件二進(jìn)制目標(biāo)碼的工具.于是，本文預(yù)想通過(guò)修改動(dòng)態(tài)二進(jìn)制翻譯技術(shù)的全系統(tǒng)仿真工具使其具有動(dòng)態(tài)二進(jìn)制插樁功能，進(jìn)而解決上述問(wèn)題.現(xiàn)在，基于動(dòng)態(tài)二進(jìn)制翻譯技術(shù)的系統(tǒng)級(jí)仿真工具主要包括QEMU(quick emulator)，Bochs,VirtualBox,VMware，其中僅QEMU支持除X86以外其他體系結(jié)構(gòu)的目標(biāo)機(jī)和宿主機(jī)，適合用于嵌入式系統(tǒng).QEMU[12]利用可重定位的動(dòng)態(tài)二進(jìn)制翻譯技術(shù)，在多種體系結(jié)構(gòu)的宿主機(jī)下高效全系統(tǒng)仿真多種目標(biāo)機(jī)體系結(jié)構(gòu)(X86,ARM,MIPS,PPC)，包括操作系統(tǒng)及其所有應(yīng)用軟件都可以無(wú)修改的通過(guò)QEMU加載仿真運(yùn)行.這是因?yàn)?，QEMU在動(dòng)態(tài)翻譯執(zhí)行目標(biāo)系統(tǒng)程序過(guò)程中，模擬了包括CPU、RAM、中斷控制器以及其他外設(shè)在內(nèi)的目標(biāo)體系結(jié)構(gòu)的全部硬件.翻譯執(zhí)行過(guò)程中，如果在QEMU仿真執(zhí)行序列中插入保存模擬運(yùn)行環(huán)境快照的探針功能，那么將為程序的動(dòng)態(tài)分析提供寶貴的運(yùn)行信息.

本文的主要貢獻(xiàn)有3個(gè)方面:

1) 研究QEMU的動(dòng)態(tài)二進(jìn)制翻譯全系統(tǒng)仿真執(zhí)行過(guò)程，提出完成中間碼層次上的二進(jìn)制基本塊插樁，跟蹤和記錄程序執(zhí)行流;

2) 分析與實(shí)驗(yàn)研究插樁對(duì)仿真性能的影響，發(fā)現(xiàn)日志輸出是影響仿真性能的關(guān)鍵因素，通過(guò)分析計(jì)算，解決了由插樁引起的仿真性能驟降的不良影響;

3) 設(shè)計(jì)插樁日志分析工具，完成了對(duì)嵌入式全系統(tǒng)的執(zhí)行流跟蹤、函數(shù)調(diào)用圖、覆蓋率分析.

1 相關(guān)工作

通過(guò)文獻(xiàn)查閱發(fā)現(xiàn)，目前已有一些學(xué)者研究使用和改進(jìn)QEMU來(lái)進(jìn)行軟件動(dòng)態(tài)分析.文獻(xiàn)[13]對(duì)程序執(zhí)行路徑跟蹤，查找程序執(zhí)行熱路徑.該文獻(xiàn)通過(guò)在QEMU的基本塊首部插入熱路徑預(yù)測(cè)和跟蹤指令，并在單獨(dú)的線程中對(duì)熱路徑進(jìn)行分析，完成了熱路徑記錄任務(wù)，但由于對(duì)熱路徑進(jìn)行在線解算，嚴(yán)重影響了仿真性能.文獻(xiàn)[14]改進(jìn)QEMU的動(dòng)態(tài)二進(jìn)制翻譯和GDB(GNU project debugger)調(diào)試樁，來(lái)支持通過(guò)GDB控制Linux進(jìn)程動(dòng)態(tài)插樁，以達(dá)到跟蹤Linux進(jìn)程目的；文獻(xiàn)[15]在QEMU翻譯過(guò)程中標(biāo)記函數(shù)調(diào)用和返回指令，獲取Linux進(jìn)程的函數(shù)調(diào)用關(guān)系圖；文獻(xiàn)[16]對(duì)每一條翻譯后的目標(biāo)機(jī)指令增加dump state指令來(lái)收集進(jìn)程的執(zhí)行信息，并發(fā)送到獨(dú)立進(jìn)程進(jìn)行輸出，顯著提高了統(tǒng)計(jì)運(yùn)行信息速度；文獻(xiàn)[17]對(duì)Call/Ret指令的追蹤，完成軟件運(yùn)行時(shí)的函數(shù)剖面分析，成功應(yīng)對(duì)了函數(shù)執(zhí)行過(guò)程被硬件中斷干擾的情況，保證了函數(shù)時(shí)間剖面分析的準(zhǔn)確性,但該文獻(xiàn)對(duì)程序追蹤粒度太粗，不能用于程序流圖、語(yǔ)句覆蓋信息產(chǎn)生；文獻(xiàn)[18]提出一種故障注入方法來(lái)模擬系統(tǒng)故障、檢驗(yàn)軟件的故障容忍性；文獻(xiàn)[19]在中間碼的層次上提出了一系列鉤子指令，獲取目標(biāo)系統(tǒng)的運(yùn)行信息，然而其需要為每一種宿主機(jī)翻譯鉤子指令，靈活度低.

從上面這些文獻(xiàn)可以看出：1)目前基于QEMU的動(dòng)態(tài)二進(jìn)制軟件分析尚未形成統(tǒng)一的理論和方法，研究者在插樁點(diǎn)選擇和探測(cè)內(nèi)容上各不相同.2)研究者都側(cè)重于使用和改進(jìn)QEMU進(jìn)行用戶級(jí)程序執(zhí)行信息收集.因此，本文旨在通過(guò)對(duì)動(dòng)態(tài)二進(jìn)制插樁技術(shù)的分析，結(jié)合QEMU使用基本翻譯塊的事實(shí)，借鑒Gcov[20]的覆蓋分析方法，在基本塊粒度上插樁，深度修改QEMU，實(shí)現(xiàn)二進(jìn)制插樁功能，并在此基礎(chǔ)上形成對(duì)基本塊執(zhí)行日志分析的工具，解決了嵌入式全系統(tǒng)軟件的動(dòng)態(tài)二進(jìn)制分析問(wèn)題.另外，本文還做了更進(jìn)一步的工作：1)減少Q(mào)EMU仿真運(yùn)行日志記錄內(nèi)容，將日志在線分析變?yōu)槭潞蠓治?，提升仿真性能?)本文通過(guò)解決直接塊鏈不返回問(wèn)題，將記錄日志信息精細(xì)到基本翻譯塊的層次，因而可以同時(shí)完成熱路徑分析、函數(shù)剖面分析、函數(shù)調(diào)用流分析、中斷流分析等，豐富了動(dòng)態(tài)二進(jìn)制插樁在程序動(dòng)態(tài)分析的應(yīng)用范圍.

2 動(dòng)態(tài)二進(jìn)制插樁與QEMU

本節(jié)簡(jiǎn)要介紹動(dòng)態(tài)二進(jìn)制插樁和QEMU的技術(shù)原理，幫助說(shuō)明后文對(duì)QEMU插樁改進(jìn).

2.1 動(dòng)態(tài)二進(jìn)制插樁

動(dòng)態(tài)二進(jìn)制插樁，就是在執(zhí)行客戶機(jī)程序的流程中，通過(guò)添加、修改和刪除機(jī)器碼等操作[5]，支持監(jiān)控客戶機(jī)軟件的一種程序仿真運(yùn)行技術(shù).在二進(jìn)制插樁領(lǐng)域，通常以基本塊(basic block)為單位進(jìn)行插樁，完成基本塊運(yùn)行信息收集，生成程序分支(arc)和程序流圖，分析程序動(dòng)態(tài)運(yùn)行信息.所謂基本塊，就是程序運(yùn)行中最基本的指令序列.在這個(gè)指令序列中，所有指令順序執(zhí)行.停止語(yǔ)句和轉(zhuǎn)向語(yǔ)句只能是基本塊的最后1個(gè)語(yǔ)句.分支(arc)是指基本塊之間的控制流,它連接程序中所有有效基本塊形成程序流圖.分支表示基本塊之間的結(jié)構(gòu)關(guān)系，通過(guò)分支可以知道程序在執(zhí)行完基本塊的所有語(yǔ)句后會(huì)轉(zhuǎn)移到哪一個(gè)基本塊繼續(xù)執(zhí)行.程序流圖是程序結(jié)構(gòu)的圖形表示.基本塊是流圖中的節(jié)點(diǎn)，程序的所有基本塊組成了程序流圖的節(jié)點(diǎn)集，程序第1個(gè)語(yǔ)句所在的基本塊稱為首節(jié)點(diǎn).把基本塊之間的控制流向作為節(jié)點(diǎn)之間的有向邊集合.對(duì)程序流圖來(lái)說(shuō)，節(jié)點(diǎn)就是基本塊，代表了程序的執(zhí)行語(yǔ)句；有向邊就是分支，代表了程序的控制流；首節(jié)點(diǎn)就是程序的起始點(diǎn).

依據(jù)插樁技術(shù)不同，基本塊插樁可以在編譯時(shí)進(jìn)行，也可以在運(yùn)行時(shí)進(jìn)行.例如GNU(GNU’s not Unix)的覆蓋率統(tǒng)計(jì)工具Gcov就是通過(guò)編譯選項(xiàng)在基本塊上進(jìn)行二進(jìn)制插樁，以實(shí)現(xiàn)對(duì)軟件的覆蓋統(tǒng)計(jì).當(dāng)插樁后的程序運(yùn)行時(shí)，動(dòng)態(tài)填充程序內(nèi)的基本塊、分支和程序流圖.當(dāng)程序運(yùn)行結(jié)束時(shí)，將基本塊、分支和程序流圖輸出到文件中，最終由Gcov完成動(dòng)態(tài)分析.而Pin，Valgrind，DynamoRIO等工具則是通過(guò)動(dòng)態(tài)二進(jìn)制翻譯技術(shù)完全控制目標(biāo)二進(jìn)制程序的執(zhí)行.它們?cè)谶\(yùn)行目標(biāo)二進(jìn)制程序時(shí)進(jìn)行二進(jìn)制翻譯，發(fā)現(xiàn)目標(biāo)程序中的基本塊并進(jìn)行插樁，最后在程序結(jié)束時(shí)給出程序運(yùn)行動(dòng)態(tài)信息.目前這些工具存在較大的局限性，例如它們都只能完成應(yīng)用級(jí)程序的動(dòng)態(tài)分析，還沒(méi)有一種工具可以完成系統(tǒng)級(jí)動(dòng)態(tài)二進(jìn)制插樁，由此可見(jiàn)，系統(tǒng)級(jí)程序的動(dòng)態(tài)二進(jìn)制分析對(duì)二進(jìn)制插樁技術(shù)來(lái)說(shuō)是一個(gè)巨大的挑戰(zhàn).

2.2 QEMU

QEMU可進(jìn)行應(yīng)用級(jí)軟件仿真和系統(tǒng)級(jí)軟件仿真.進(jìn)行系統(tǒng)級(jí)軟件仿真時(shí)，QEMU提供包括處理器、存儲(chǔ)器、總線以及中斷控制器、MMU(memory management unit)、FPU(float point unit)以及其他外設(shè)的全系統(tǒng)仿真，可以不作修改運(yùn)行任何客戶機(jī)系統(tǒng)軟件.QEMU[12-13]主要包含2方面任務(wù)：1)執(zhí)行調(diào)度；2)動(dòng)態(tài)二進(jìn)制翻譯.仿真執(zhí)行時(shí)，QEMU判斷當(dāng)前PC(program counter)對(duì)應(yīng)基本翻譯塊(translate block, TB)是否已經(jīng)在TB Cache中，如果不在TB Cache中，則進(jìn)行動(dòng)態(tài)二進(jìn)制翻譯；否則，執(zhí)行該基本翻譯塊的宿主機(jī)指令.當(dāng)執(zhí)行到未翻譯的客戶機(jī)指令序列時(shí)，則表明當(dāng)前PC對(duì)應(yīng)基本塊的開(kāi)始，QEMU產(chǎn)生基本翻譯塊，開(kāi)始進(jìn)行動(dòng)態(tài)二進(jìn)制翻譯.動(dòng)態(tài)二進(jìn)制翻譯包含翻譯前端和翻譯后端2個(gè)階段，完成客戶機(jī)指令序列到宿主機(jī)指令序列的語(yǔ)義等效轉(zhuǎn)換.第1階段，函數(shù)gen_intermediate_code讀取客戶機(jī)指令序列進(jìn)行反匯編產(chǎn)生中間碼(intermediate code).在一些學(xué)者的研究中，中間碼或稱為中間表示，或稱為虛擬指令集.在這1階段，跳轉(zhuǎn)指令確定了基本翻譯塊的邊界.第2階段，函數(shù)tcg_gen_code遍歷中間碼，將中間碼轉(zhuǎn)換成宿主機(jī)指令，保存翻譯塊并加入TB Cache.

3 QEMU插樁改進(jìn)

QEMU的動(dòng)態(tài)翻譯仿真執(zhí)行流程,與Pin，Valgrind，DynamoRIO等工具的動(dòng)態(tài)插樁過(guò)程十分類(lèi)似.然而，Pin，Valgrind，DynamoRIO等不支持系統(tǒng)級(jí)程序的仿真執(zhí)行[2]，也不支持交叉動(dòng)態(tài)二進(jìn)制翻譯.所謂交叉動(dòng)態(tài)二進(jìn)制翻譯，即原二進(jìn)制程序同翻譯后的二進(jìn)制程序體系結(jié)構(gòu)不同.PinOS是一個(gè)通過(guò)Pin開(kāi)發(fā)的全系統(tǒng)的插樁工具，但其僅能用于Linux架構(gòu)[2]，不支持嵌入式系統(tǒng).而QEMU全系統(tǒng)仿真時(shí)完全掌握系統(tǒng)運(yùn)行流程和仿真環(huán)境狀態(tài).因此，可以對(duì)其進(jìn)行深度修改，使其具有二進(jìn)制插樁功能，解決嵌入式全系統(tǒng)的軟件動(dòng)態(tài)分析的難題.而要使QEMU具有二進(jìn)制插樁功能，必須解決3個(gè)問(wèn)題：

1) 流程嵌入，即如何將插樁過(guò)程附加到QEMU仿真執(zhí)行過(guò)程;

2) 樁點(diǎn)選擇，即在基本塊中如何選擇決策探針插入位置;

3) 探針內(nèi)容，即在探針中如何收集以及收集哪些客戶機(jī)信息來(lái)滿足插樁日志分析工具設(shè)計(jì).

3.1 流程嵌入

當(dāng)前，一些文獻(xiàn)通過(guò)QEMU客戶機(jī)程序執(zhí)行流程分析，將探針插在執(zhí)行調(diào)度循環(huán)中，如圖1所示:

Fig. 1 Instrumentation in the main cycle圖1 主循環(huán)內(nèi)插樁

在執(zhí)行基本塊前后分別插入探針，獲取虛擬CPU運(yùn)行信息，記錄PC和時(shí)間戳.但這種方法會(huì)丟失一些基本塊運(yùn)行信息.這是因?yàn)镼EMU使用了直接塊鏈技術(shù).使用直接塊鏈技術(shù)[12-13]后，執(zhí)行調(diào)度程序一旦進(jìn)入執(zhí)行基本塊流程，控制流不返回執(zhí)行調(diào)度主循環(huán)，而直接選擇下一個(gè)基本塊繼續(xù)執(zhí)行.如圖1所示，開(kāi)始執(zhí)行基本塊后，控制流進(jìn)入包含多個(gè)基本塊的程序流圖，不能立即返回執(zhí)行調(diào)度主循環(huán)，從而導(dǎo)致丟失部分程序運(yùn)行信息.為解決這一問(wèn)題，一些文獻(xiàn)提出取消直接塊鏈功能[13,15]，甚至提出采用單步執(zhí)行的方式[13].這些方法雖可解決上述問(wèn)題，卻嚴(yán)重制約QEMU仿真性能.

針對(duì)這一問(wèn)題，要收集基本塊執(zhí)行信息，只能將探針嵌入基本塊執(zhí)行過(guò)程內(nèi)部，如圖2所示.在基本翻譯塊的前后分別插入探針.這樣，即使采用直接塊鏈技術(shù)，也不會(huì)丟失程序運(yùn)行信息.基本塊運(yùn)行時(shí)，記錄基本塊開(kāi)始PC和時(shí)間戳.基本塊結(jié)束時(shí)，記錄其結(jié)束時(shí)間戳和控制流轉(zhuǎn)移目的地址.

Fig. 2 Instrumentation in basic block圖2 基本塊內(nèi)插樁

Fig. 3 The flow of dynamic instrumentation in basic block圖3 基本塊動(dòng)態(tài)插樁流程嵌入示意圖

然而，基本塊內(nèi)嵌入探針并不是簡(jiǎn)單的工作.例如，探針插入可以在翻譯前端完成也可以在翻譯后端完成.本文選擇在翻譯前端完成，即在函數(shù)gen_intermediate_code中完成.這是因?yàn)椋?)該方法可以適合多種宿主機(jī)，不需要為每種宿主機(jī)體系結(jié)構(gòu)修改代碼;2)在翻譯前端可以更方便通過(guò)代碼操作客戶機(jī)運(yùn)行環(huán)境狀態(tài)信息,而在翻譯后端QEMU所能使用的信息僅僅是中間碼，完全沒(méi)有客戶機(jī)環(huán)境信息.因此，本文的動(dòng)態(tài)插樁過(guò)程如圖3所示.在每一個(gè)基本塊產(chǎn)生中間碼之前，函數(shù)gen_intermediate_code先進(jìn)行塊首插樁，插入探針，將探針中間碼添加在基本塊中間碼首部.遇上跳轉(zhuǎn)指令離開(kāi)基本塊時(shí)，函數(shù)gen_intermediate_code進(jìn)行塊末插樁，插入探針，將探針中間碼添加在基本塊中間碼末端.后端翻譯時(shí)，即函數(shù)tcg_gen_code中，探針中間碼連同基本塊功能中間碼一起翻譯成宿主機(jī)指令序列，從而完成了對(duì)插樁流程的嵌入.

3.2 樁點(diǎn)選擇

Fig. 4 Intermediate code and instrumentation selection圖4 中間碼與樁點(diǎn)選擇示意圖

問(wèn)題轉(zhuǎn)化為研究基本塊前端翻譯過(guò)程，即如何確定基本塊中的插樁點(diǎn).插樁點(diǎn)的選擇既要保證覆蓋基本塊所有執(zhí)行路徑，又不會(huì)產(chǎn)生冗余記錄.根據(jù)研究發(fā)現(xiàn)，基本塊中間碼組織結(jié)構(gòu)如圖4所示，除客戶機(jī)基本塊翻譯來(lái)的中間碼外，中間碼中還包括了用于控制直接塊鏈退出的其他中間碼，如ld,brne,goto_tb,exit_tb等虛擬指令.仿真執(zhí)行時(shí)，控制流有3條路徑離開(kāi)基本翻譯塊.

1) 客戶機(jī)軟件控制流從位置a進(jìn)入基本翻譯塊，將tcg_exit_req加載到變量flag后，控制流判斷flag是否為0，如果不是，跳轉(zhuǎn)到最后1條指令exit_req_lable處，從出口c離開(kāi)，返回執(zhí)行調(diào)度主循環(huán).這表示被仿真系統(tǒng)處理器收到外設(shè)產(chǎn)生中斷或產(chǎn)生了異常等，需退出直接塊鏈執(zhí)行.

2) 客戶機(jī)軟件控制流從位置a進(jìn)入基本翻譯塊，將tcg_exit_req加載到變量flag后，控制流判斷flag=0時(shí)，控制流執(zhí)行完其他中間指令，遇見(jiàn)指令goto_tb，從出口b離開(kāi)，進(jìn)入直接塊鏈控制流.

3) 客戶機(jī)軟件控制流從位置a進(jìn)入基本翻譯塊，將tcg_exit_req加載到變量flag后，控制流判斷flag=0時(shí)，控制流執(zhí)行完其他中間指令，控制流執(zhí)行完其他中間指令后，未遇見(jiàn)指令goto_tb，從出口c離開(kāi)，返回執(zhí)行調(diào)度主循環(huán).

顯然，為覆蓋全部路徑，應(yīng)選擇圖4中所示3處插樁點(diǎn)(三角形).這是因?yàn)?，在直接塊鏈的控制流中，當(dāng)執(zhí)行一個(gè)基本塊時(shí)，首先會(huì)檢查是否需要退出直接塊鏈執(zhí)行.如果檢查到需要退出執(zhí)行，則控制流直接轉(zhuǎn)到當(dāng)前塊末端，而導(dǎo)致當(dāng)前基本塊的客戶機(jī)指令沒(méi)有執(zhí)行.如果插樁不當(dāng)，會(huì)將此種未運(yùn)行客戶機(jī)指令的情況虛假統(tǒng)計(jì)到日志記錄中.

另外，除以上3條路徑離開(kāi)基本塊以外，QEMU還可以在異常或中斷觸發(fā)下離開(kāi)基本塊.為簡(jiǎn)化插樁操作，本文未對(duì)此種路徑進(jìn)行插樁.這是因?yàn)?，異?；蛑袛喈a(chǎn)生對(duì)嵌入式系統(tǒng)來(lái)說(shuō)是隨機(jī)的，我們可以認(rèn)為這是疊加在所有的基本塊運(yùn)行信息上的白噪聲信號(hào)，不會(huì)影響最終分析工具的結(jié)果.

3.3 探針內(nèi)容

插樁流程和探針點(diǎn)選擇決策后，確定探測(cè)內(nèi)容和分析時(shí)機(jī)成為首要問(wèn)題.理論上，動(dòng)態(tài)二進(jìn)制插樁可以探測(cè)記錄目標(biāo)體系結(jié)構(gòu)全部信息，包括全部寄存器值、存儲(chǔ)器內(nèi)容、程序棧和堆的值、程序執(zhí)行流以及進(jìn)入退出基本塊時(shí)間等.但為了減少系統(tǒng)壓力，盡量不影響系統(tǒng)仿真速度，在實(shí)踐中僅記錄少量體系結(jié)構(gòu)運(yùn)行信息.例如Gcov只記錄了基本塊的執(zhí)行次數(shù)和基本塊的進(jìn)入地址，因而其函數(shù)剖面分析功能結(jié)果存在誤差.本文參照Gcov，將探測(cè)內(nèi)容定義成四元組(type,ts,pc,dest).type表示插樁點(diǎn)的位置，依據(jù)插樁點(diǎn)位置的選擇，type分別可以取1,2,3這3種值；ts表示探針運(yùn)行時(shí)刻客戶機(jī)時(shí)間戳；pc表示插樁點(diǎn)運(yùn)行時(shí)客戶機(jī)的PC值；dest僅在type=2時(shí)有效，表示下一個(gè)基本塊的首地址，記錄程序中的跳轉(zhuǎn)信息.

圖5是本文所述插樁方法產(chǎn)生的動(dòng)態(tài)插樁實(shí)例.目標(biāo)二進(jìn)制基本塊取自EEMBC(Embedded Microprocessor Benchmark Consortium)組織Core Mark1.0中的main函數(shù).該基本塊包含2條指令，分別位于0x159a和0x159c.

從圖5可以看出，此時(shí)處理器工作在Thumb模式.經(jīng)過(guò)前端翻譯后轉(zhuǎn)換成中間碼，共產(chǎn)生12條指令.經(jīng)3處插樁9條指令后，共計(jì)21條指令.這3處插樁分別調(diào)用helper函數(shù)profile_enter_tb，profile_set_pc_tb，profile_exit_tb實(shí)現(xiàn)對(duì)執(zhí)行路徑及時(shí)間戳的記錄.

3.4 性能優(yōu)化

根據(jù)3.3節(jié)分析，每個(gè)插樁點(diǎn)都需要記錄客戶機(jī)時(shí)間戳.記錄時(shí)間戳最簡(jiǎn)單的方法就是通過(guò)系統(tǒng)調(diào)用獲取宿主機(jī)當(dāng)前tick作為四元組中的ts.然而，采用這種方法存在2方面的問(wèn)題:1)每一個(gè)基本塊獲取一次tick，即陷入系統(tǒng)一次，嚴(yán)重影響動(dòng)態(tài)二進(jìn)制翻譯執(zhí)行效率；2)宿主機(jī)系統(tǒng)的時(shí)間流逝包含了執(zhí)行調(diào)度、動(dòng)態(tài)二進(jìn)制翻譯等非客戶機(jī)指令運(yùn)行時(shí)間，造成客戶機(jī)執(zhí)行時(shí)間打點(diǎn)偏移.本文提出的解決方案是，在動(dòng)態(tài)二進(jìn)制翻譯執(zhí)行過(guò)程中，將流逝時(shí)間解釋為指令計(jì)數(shù).因?yàn)閷?duì)于確定的計(jì)算機(jī)系統(tǒng)來(lái)說(shuō)，單條指令的執(zhí)行通常在一定的時(shí)間內(nèi)完成.因此，可以通過(guò)指令計(jì)數(shù)來(lái)反映客戶機(jī)系統(tǒng)時(shí)間.

指令計(jì)數(shù)可以在仿真運(yùn)行中統(tǒng)計(jì)，但這不是最佳方法.在插樁日志處理工具的設(shè)計(jì)中，本文將日志記錄轉(zhuǎn)化為基本塊序列.在執(zhí)行基本塊中，控制流順序執(zhí)行，因此可以通過(guò)執(zhí)行基本塊的開(kāi)始地址和結(jié)束地址計(jì)算指令計(jì)數(shù)，從而反映基本塊執(zhí)行時(shí)間.這樣插樁內(nèi)容可定義為三元組(type,pc,dest)，不包含時(shí)間戳，而采用事后分析基本塊指令計(jì)數(shù)來(lái)得到基本塊執(zhí)行時(shí)間.這樣就減少系統(tǒng)調(diào)用陷入，也減少了日志輸出量，從而限制插樁程序?qū)Ψ抡嫘阅艿挠绊?見(jiàn)5.1節(jié)).

本文通過(guò)性能測(cè)試顯示，日志輸出I/O嚴(yán)重影響了仿真性能(見(jiàn)5.1節(jié)).為了減少日志輸出，本文在第4節(jié)分析工具設(shè)計(jì)過(guò)程中進(jìn)一步研究發(fā)現(xiàn)，可以將每次基本塊運(yùn)行日志記錄優(yōu)化為一條，這樣就可以把日志輸出減少到一半.這是因?yàn)椋?dāng)把計(jì)時(shí)方式改為指令計(jì)數(shù)時(shí)，探針不再需要記錄基本塊運(yùn)行開(kāi)始時(shí)間.因此，只需在離開(kāi)基本塊控制流插入探針，就能計(jì)算出該基本塊對(duì)應(yīng)的函數(shù)和語(yǔ)句執(zhí)行時(shí)間.如果控制流跳轉(zhuǎn)到其他基本塊，離開(kāi)基本塊時(shí)還應(yīng)該記錄目標(biāo)基本塊地址，用于函數(shù)調(diào)用關(guān)系計(jì)算.通過(guò)這樣的方式，本文減少了插樁對(duì)仿真性能的不良影響.為減少在線分析對(duì)仿真性能的影響，同Gcov一樣，本文采用事后分析日志的策略.

4 分析工具

為分析插樁代碼運(yùn)行日志記錄，本文設(shè)計(jì)開(kāi)發(fā)插樁日志分析工具(instrumentation analysis tool, IAT)，其工作原理如圖6所示.步驟1，讀取運(yùn)行日志記錄，完成基本塊還原；步驟2，讀取目標(biāo)二進(jìn)制可執(zhí)行文件調(diào)試信息，還原地址與源代碼的映射關(guān)系；步驟3，計(jì)算基本塊命中源代碼情況，從而解算出函數(shù)調(diào)用關(guān)系、覆蓋信息等.

Fig. 6 IAT schematic diagram圖6 IAT原理圖

4.1 基本塊還原

當(dāng)插樁完成后，QEMU仿真運(yùn)行客戶機(jī)二進(jìn)制代碼產(chǎn)生記錄日志文件.日志文件中每行包含前文所述的三元組(type,pc,dest)探測(cè)內(nèi)容.如圖6右側(cè)①所示，IAT對(duì)記錄日志逐行掃描，獲取每一個(gè)基本塊的地址范圍、目標(biāo)基本塊等信息.然而，這些信息僅含程序運(yùn)行覆蓋的基本塊、分支和程序流.如果要進(jìn)一步統(tǒng)計(jì)軟件函數(shù)調(diào)用流圖、基本塊覆蓋情況、語(yǔ)句覆蓋情況、函數(shù)覆蓋情況甚至分支覆蓋情況，必須獲取目標(biāo)機(jī)軟件的全部基本塊、語(yǔ)句、函數(shù)與二進(jìn)制目標(biāo)碼的映射關(guān)系.

4.2 源碼信息還原

在僅有二進(jìn)制的情況下，可以使用調(diào)試信息來(lái)獲取這種映射關(guān)系.現(xiàn)代編譯器在將高級(jí)語(yǔ)言轉(zhuǎn)換成機(jī)器碼，同時(shí)在目標(biāo)二進(jìn)制文件中裝入調(diào)試信息，方便程序調(diào)試和和軟件優(yōu)化.通常，調(diào)試信息按DWARF[21]格式保存在目標(biāo)二進(jìn)制文件的調(diào)試信息段.根據(jù)DWARF信息，調(diào)試器能獲取地址和符號(hào)的對(duì)應(yīng)關(guān)系、地址和編譯單元的對(duì)應(yīng)關(guān)系、能獲取變量類(lèi)型、變量存儲(chǔ)位置等信息.然而，為了適應(yīng)多種編譯器和目標(biāo)體系結(jié)構(gòu)，DWARF格式十分復(fù)雜.本文借助軟件包elftools來(lái)分析DWARF格式.通過(guò)elftools提供的API，IAT讀取目標(biāo)二進(jìn)制可執(zhí)行文件，獲取其中全部函數(shù)及其地址范圍、全部編譯基本塊及其地址范圍等.如圖6左側(cè)②所示，IAT通過(guò)調(diào)試信息項(xiàng)sub_program獲取所有函數(shù)的地址范圍，形成以(function,address)為關(guān)鍵字的函數(shù)集合.IAT通過(guò)調(diào)試信息項(xiàng)line_program獲取編譯單元，并通過(guò)所有函數(shù)過(guò)濾出可執(zhí)行編譯單元，形成以(file,line,column)為關(guān)鍵字的運(yùn)行單元集合.這樣，就可以通過(guò)分析函數(shù)集合和運(yùn)行單元集合的命中性和執(zhí)行時(shí)間來(lái)完成軟件分析.

4.3 覆蓋標(biāo)記與調(diào)用計(jì)算

在基本塊和源碼信息還原后，IAT逐一遍歷基本塊完成軟件分析.在本文中，軟件分析指對(duì)軟件call graph,function profile,coverage,control flow等信息分析.對(duì)于每一個(gè)基本塊，如果該基本塊地址范圍(start_PC，end_PC)命中函數(shù)集中某(function，address)的地址范圍，則增加該函數(shù)運(yùn)行時(shí)間，并標(biāo)記函數(shù)已覆蓋；如果該基本塊地址范圍(start_PC，end_PC)命中運(yùn)行單元集合中的某(file，line，column)運(yùn)行單元，則標(biāo)記該(file，line，column)運(yùn)行單元已覆蓋.如果該基本塊包含dest_PC，那么標(biāo)記該控制流轉(zhuǎn)移過(guò)程和函數(shù)調(diào)用關(guān)系.

對(duì)全系統(tǒng)仿真來(lái)說(shuō)，在進(jìn)行控制流和函數(shù)調(diào)用關(guān)系解算時(shí)還需要考慮系統(tǒng)中斷的影響.這是因?yàn)橐恍r(shí)候主控制流會(huì)被中斷控制流打斷，中斷控制流會(huì)被計(jì)入主控制流或者中斷函數(shù)被計(jì)為被打斷函數(shù)的子函數(shù).這樣，一方面IAT必須將中斷控制流從主控制流中剪去；另一方面，IAT必須記錄被中斷打斷的主控制流，以便中斷控制流退出后將控制流接續(xù)到被打斷的主控制流.被中斷所打斷的中斷控制流可以采用相同的方法解決.

5 插樁實(shí)驗(yàn)與程序運(yùn)行結(jié)果

本文采用EEMBC組織提供的嵌入式性能評(píng)估套件CoreMark1.0[22]完成插樁性能測(cè)試和插樁結(jié)果分析. CoreMark程序測(cè)試集包含鏈表、矩陣、狀態(tài)機(jī)等相關(guān)操作的性能測(cè)試用例.

5.1 性能測(cè)試與優(yōu)化

插樁后，當(dāng)程序執(zhí)行探針時(shí)，QEMU將目標(biāo)機(jī)程序運(yùn)行時(shí)信息輸出到指定文件.本文在2個(gè)數(shù)量級(jí)上運(yùn)行CoreMark，即分別插樁運(yùn)行CoreMark 10～150次和執(zhí)行CoreMark 10 000～150 000次，計(jì)算插樁代價(jià).這是因?yàn)椋罩据敵鯥/O嚴(yán)重影響了仿真性能.如圖7～8所示.在圖7中，淺色(藍(lán)色)(T)數(shù)據(jù)系列表示原QEMU運(yùn)行CoreMark的結(jié)果為1 690 iter/s；深色(橙色)(NIOST)數(shù)據(jù)系列表示插樁但不進(jìn)行日志輸出的修改，其運(yùn)行CoreMark的結(jié)果為1 324 iter/s，性能下降21%.然而，插樁并進(jìn)行I/O的修改最快僅為0.21 iter/s，性能下降99.987%，如圖8所示.這表明插樁本身對(duì)仿真性能的影響遠(yuǎn)小于I/O對(duì)仿真性能的影響，為本文第3節(jié)的性能優(yōu)化提供了依據(jù).因此，本文做了大量的工作來(lái)減少插樁過(guò)程中I/O對(duì)仿真性能的影響，如3.4節(jié)所述.通過(guò)優(yōu)化，仿真性能得到顯著提高，如圖8所示.圖8中，最淺色(藍(lán)色)(GT)數(shù)據(jù)系列表示包含獲取時(shí)間的QEMU修改，其仿真運(yùn)行CoreMark的結(jié)果為0.08 iter/s；最深色(橙色)(NT)數(shù)據(jù)系列表示不包含獲取時(shí)間的QEMU修改，其仿真運(yùn)行CoreMark的結(jié)果為0.13 iter/s，與GT相比性能提高1.70倍；較深色(綠色)(NST)數(shù)據(jù)系列表示不獲取時(shí)間，每個(gè)基本塊僅有一個(gè)插樁點(diǎn)的QEMU修改，其仿真運(yùn)行CoreMark的結(jié)果為0.21 iter/s，與NST相比性能提高1.57倍，性能累計(jì)提高2.68倍.

Fig. 7 Instrumentation without I/O圖7 插樁不進(jìn)行I/O

Fig. 8 Instrumentation with I/O圖8 插樁進(jìn)行I/O

然而，這仍然遠(yuǎn)不能滿足實(shí)際需要，還需提高仿真性能.為進(jìn)一步減少插樁對(duì)仿真性能的不良影響，本文通過(guò)實(shí)驗(yàn)研究分析，發(fā)現(xiàn)對(duì)日志進(jìn)行分批集中輸出，而不是產(chǎn)生1條就輸出1條，即不是在每一個(gè)樁點(diǎn)都進(jìn)行輸出，僅在日志達(dá)到指定的緩沖區(qū)大小后進(jìn)行日志集中輸出寫(xiě)入文件，可以有效地提高插樁后程序的仿真執(zhí)行效率，如圖9所示.圖9中淺色(藍(lán)色)(B1K)數(shù)據(jù)系列表示將跟蹤日志輸出緩沖設(shè)置為1 KB時(shí)，其仿真運(yùn)行CoreMark的結(jié)果為64.41 iter/s；深色(橙色)(BKK)數(shù)據(jù)系列表示將跟蹤日志輸出緩沖設(shè)置為1 MB時(shí)，其仿真運(yùn)行CoreMark的結(jié)果為64.61 iter/s，與B1K相比速度提高0.003倍.由此可見(jiàn)，緩沖大小對(duì)仿真速度并沒(méi)有顯著提高，然而采用集中輸出日志的方法比在每個(gè)樁點(diǎn)中都進(jìn)行日志輸出，仿真性能提高26.24倍，同不進(jìn)行優(yōu)化相比，仿真性能提高303.43倍.因此，本文最終選擇采用優(yōu)化后的集中輸出方案，仿真運(yùn)行CoreMark的結(jié)果為64.41 iter/s.

Fig. 9 Instrumentation with buffered I/O圖9 插樁進(jìn)行緩沖I/O

5.2 實(shí)驗(yàn)結(jié)果

根據(jù)設(shè)計(jì)，IAT工具可以分析call graph,function profile,coverage,control flow等.為減少I(mǎi)AT工具分析數(shù)據(jù)量，本文將CoreMark的迭代次數(shù)設(shè)置為3次后通過(guò)IAT工具分析日志記錄，產(chǎn)生的結(jié)果為：

1) 函數(shù)調(diào)用關(guān)系

通過(guò)IAT工具，實(shí)驗(yàn)分析得出CoreMark的main函數(shù)調(diào)用關(guān)系，如圖10～12所示.圖11和圖12為圖10中的子函數(shù)，其中圖11展示了本文對(duì)CoreMark的移植方法.

Fig. 10 Function main call graph圖10 函數(shù)main調(diào)用圖

Fig. 11 Function portable_init call graph圖11 函數(shù)portable_init調(diào)用圖

Fig. 12 Function core_list_mergesort call graph圖12 函數(shù)core_list_mergesort調(diào)用圖

和使用程序源碼分析調(diào)用關(guān)系不同的是，動(dòng)態(tài)分析得出的調(diào)用關(guān)系僅僅包含軟件運(yùn)行時(shí)覆蓋到的調(diào)用.但是，實(shí)驗(yàn)表明，動(dòng)態(tài)分析函數(shù)調(diào)用關(guān)系具有自己的特點(diǎn)，那就是它可解算出使用函數(shù)指針調(diào)用的子函數(shù).如圖12所示，函數(shù)core_list_mergsort通過(guò)指針調(diào)用了2個(gè)鏈表項(xiàng)比較函數(shù)cmp_idx和cmp_complex.

2) 函數(shù)剖面分析

通過(guò)IAT工具，實(shí)驗(yàn)分析得出CoreMark和移植函數(shù)中，消耗CPU時(shí)間最多前5名依次是core_state_transition,crcu8,core_list_find,core_bench_state,core_list_mergesort,分別消耗的指令計(jì)數(shù)是427 966,135 551,79 578,33 960,33 787，分別占總運(yùn)行時(shí)間55%,17%,10%,4%,4%.如圖13所示.分析完成后，軟件設(shè)計(jì)者可根據(jù)上述信息進(jìn)行軟件優(yōu)化.

Fig. 13 Function profile圖13 函數(shù)剖面分析示意圖

3) 覆蓋分析

通過(guò)IAT工具，實(shí)驗(yàn)分析得出CoreMark函數(shù)和移植函數(shù)共計(jì)79個(gè)，在執(zhí)行中共覆蓋其中52個(gè)函數(shù)，覆蓋率為65.82%.如圖14所示，圖14中縱坐標(biāo)為CoreMark中的函數(shù)，橫坐標(biāo)值為1的函數(shù)表示該函數(shù)為執(zhí)行路徑所覆蓋，反之值為0的函數(shù)表示該函數(shù)未被執(zhí)行路徑所覆蓋.

通過(guò)IAT工具，實(shí)驗(yàn)分析得出CoreMark共計(jì)包含1192個(gè)可執(zhí)行編譯單元，其中444個(gè)單元為執(zhí)行所覆蓋，覆蓋率為37.24%.如圖15所示，圖15中縱坐標(biāo)為(file,line,column)三元組，橫坐標(biāo)通過(guò)1和0分別表示該三元組標(biāo)識(shí)的語(yǔ)句塊執(zhí)行與否.通過(guò)這些信息，可以解算軟件語(yǔ)句覆蓋率.如果將這些信息同源碼信息、執(zhí)行控制流信息結(jié)合起來(lái)，則可以解算軟件分支覆蓋率、MC/DC覆蓋率等.由于篇幅有限，本文不再贅述.

Fig. 14 Function coverage圖14 函數(shù)覆蓋情況示意圖

Fig. 15 Branch coverage圖15 分支覆蓋情況示意圖

6 總 結(jié)

本文在QEMU的動(dòng)態(tài)二進(jìn)制翻譯技術(shù)的基礎(chǔ)上，突破基本塊中間碼動(dòng)態(tài)插樁、基本塊運(yùn)行時(shí)間統(tǒng)計(jì)、中斷對(duì)控制流影響消除等關(guān)鍵技術(shù)，對(duì)QEMU進(jìn)行動(dòng)態(tài)二進(jìn)制插樁改造，成功完成軟件運(yùn)行信息動(dòng)態(tài)收集.并在此基礎(chǔ)上，設(shè)計(jì)了插樁日志分析工具IAT，完成了對(duì)軟件的函數(shù)調(diào)用、函數(shù)剖面分析、函數(shù)和分支覆蓋率統(tǒng)計(jì)等功能.實(shí)驗(yàn)結(jié)果表明：通過(guò)本文的工作，可以有效解決嵌入式全系統(tǒng)軟件的二進(jìn)制插樁問(wèn)題.