|
庫函數的快速鑒別和識別技術
|
|
文檔編號：
|
S002-0017
|
|
原作者：
|
Ilfak Guilfanov [DataRescue.com]
|
|
譯者：
|
月中人 [PTG]
|
|
審校：
|
|
|
發布時間：
|
2007-01-10
|
|
原文標題：
|
Fast Library Identification and Recognition Technology
|
|
關鍵詞：
|
庫函數,鑒別,識別,簽名,特征文件
|
|
1. 原文版權聲明：
(c) Copyright 1997 by Ilfak Guilfanov & DataRescue
Reproduction strictly forbidden
2. 譯文字典：
Identification鑒別，即確定一個函數是什么；
Recognition識別，即從程序中分離出屬于一個函數的那些代碼；
misidentification錯誤標識
|
1 目標
對于現代高級語言所寫的程序，分離庫函數所費的時間是反匯編的一個主要障礙。我們會因為沒有從中獲得新的知識而覺得時間被浪費了：它只是我們深入分析程序和反映其意圖的算法之前一個必不可少的步驟。遺憾的是，每次反匯編一個新的程序都不得不重復這一步。
有時，了解一個庫函數的類別能相當大地減輕對程序的分析工作。這對于丟棄無用信息可能極有幫助。舉例來說，一個處理流數據的C++函數通常與程序的主要算法無關。
請注意一個有意思的現象，每一高級語言程序都使用很多標準庫函數，有時甚至達到所有被調用函數的95%是標準函數。使用某個眾所周知的編譯器編譯的“Hello, world!”程序中有：
庫函數 - 58個
函數main() - 1個
當然，這是一個人為的例子，但我們的分析確實顯示，真實程序中的函數平均50%是庫函數。這就是為什么反匯編器的使用者不得不花費他一半以上的時間來分離出那些庫函數。對一個未知程序進行分析類似于解答一個巨大的拼字智力游戲：我們確定的字母越多，就越容易猜測下一個字。反匯編過程中，在一個函數里面注解和有意義名字越多，意味著能夠更快地理解它的意圖。象OWL、MFC以及其他一些標準庫的廣泛使用，甚至更增加了在目標程序中標準函數所占的成分。
使用現代技術（如，AppExpert或類似的向導）用C++編的一個中等尺寸的Win32程序，會從1000到2500個庫函數中調用任何函數。
我們試圖創造一個識別標準庫函數的算法來輔助IDA用戶。我們希望它是一個實用而且有用的東西，因此必須接受一些限制：
n 我們只考慮用C/C++編寫的程序
n 我們不企圖達成完美的函數識別：從理論上講這是不可能的。而且，對某些函數的識別可能導致不良后果。例如，對下面這個函數的識別將會誤導以致產生許多錯誤標識。
push bp
mov bp, sp
xor ax, ax
pop bp
ret
這毫無意義，因為在現代的C++庫中你會發現有許多不同名字的函數與它每個字節都完全相同。
n 我們只識別和鑒別位于代碼段的函數，而忽略數據段。
n 當一個函數已經被成功鑒別的時候，我們給它指定一個名字和一個最終的注解。我們不打算提供關于函數參數或函數行為的信息。
我們還要求做到以下幾點
n 我們努力完全地避免假陽性。我們認為假陽性（一個被錯誤地鑒別的函數）比假陰性（一個沒有鑒別出來的函數）更糟。理想的情況應該是根本不產生假陽性。
n 函數的識別需要你提供最低限度的處理器和存儲器資源。
n 由于IDA的多價結構 - 它支持好幾十種非常不同的處理器 - 鑒別算法必須是獨立于平臺的，即它必須適用于為任何處理器編譯的程序。
n 應該鑒別main()函數并適當地加以標注，因為我們對庫的啟動代碼不感興趣。
2 難點
存儲器的使用量
識別和鑒別的主要障礙是函數的純數量及其占用存儲空間的大小。如果我們計算所有編譯器‘廠商’為不同存儲器‘模型’生產的所有庫所有‘版本’，所需儲存空間動輒成百上千億字節之巨。
如果我們試圖考慮OWL、MFC、MFC及類似的庫，情況更糟。所需要的儲存量是極大的。目前，個人電腦用戶不可能負擔得起劃撥成百上千兆字節的磁盤空間給一個簡單的反匯編工具程序。因此，我們必須采用某種算法，如此便可以減少識別標準庫函數時所需信息的尺寸。當然，由于必須被識別的函數個數多，我們需要一個有效率的識別算法：簡單的暴力搜索并非一個可選方案。
可變性
另一個的困難在于程序中的‘變數’字節[_variant_ bytes]。有些字節在載入時被修正（被解決），而另一些字節在鏈接時變成常數，但是大部份變數字節是來自引用的外部名字。在那種情況下，編譯器不知道被調用函數的地址，而且保留這些字節的值為零。這種所謂的“修正信息[fixup information]”通常被寫到輸出文件[output file]的一個表（有時叫做“重定位表”或“重定位信息”）。下例包含有變數字節。
B8 0000s mov ax, seg _OVRGROUP_
9A 00000000se call _farmalloc
26: 3B 1E 0000e cmp bx, word ptr es:__ovrbuffer
鏈接器將會試圖解決外部引用，使用所調用的函數的地址替換那些零，但是有些字節仍保留不變：程序中對動態庫的引用或者包含絕對地址的那些字節。這些引用只能在載入時由系統裝載程序解決。它將會試圖解決所有的外部引用而且用絕對地址替換零。當系統裝載程序不能夠解決某個外部引用時，如同該程序引用一個未知DLL的情況一樣，程序就不運行。
某些鏈接器設置的優化也會讓事情變復雜，因為那些固定的字節有時會被改變。例如：
0000: 9A........ call far ptr xxx
被替換成
0000: 90 nop
0001: 0E push cs
0002: E8.... call near ptr xxx
程序會照常運行，但是鏈接器帶來的替換確實讓我們不可能利用函數模板做逐字節對比。一個程序中變數字節的出現使得不可能利用簡單的檢驗和來識別。如果函數沒有包含變數字節，開頭N字節的CRC[循環冗余校驗碼]就足以鑒別和選擇在一個散列表中的一組函數。使用這種表會大大減少鑒別所需的信息大小：函數的名字、它的長度以及檢驗和就夠了。
我們已經用例子證明了，識別所有的標準庫函數是不可能的，或者甚至是不值得的。還有一個補充證明就是，某些函數是同一的，它們做的事完全相同，只是以不同的方式調用。例如，函數strcmp()和fstrcmp()在大規模存儲器模型中是同一的。
這里我們遇到一個左右為難的問題：有些函數并非無足輕重，而且將它們標注會對用戶有幫助，所以我們不想從識別過程中丟棄這些函數，然而我們無法區別它們。
更具體些：考慮這個
call xxx
ret
或者
jmp xxx
乍一看，這些代碼片斷沒有特別之處。問題是它們在標準庫中出現，有時數量相當多。Borland C++ 1.5版OS/2編譯器使用的那些庫包含20個這種類型的調用，出現在read()、write()等重要的函數中。
對這些函數的無格式比較不會有什么收獲。區別那些函數的唯一機會是發現它們調用其他的什么函數。通常，所有的短函數（只由2-3條指令組成）都難以識別，而且錯誤識別的概率非常高。然而不識別它們是不好的，因為它會導致級聯的識別失?。喝绻覀儾蛔R別函數tolower()，我們可能就無法識別引用tolower()的strlwr()。
版權
最后，有一個明顯的版權問題：就是一個反匯編器的分發可能不帶那些標準庫。
3 要點
為了解決以上提出的問題，我們創建一個數據庫，含有我們想要識別的所有庫的所有函數。于是對于反匯編出來的程序每個字節，IDA Pro都檢查它能否標志著某個標準庫函數的開始。
識別算法所需要的信息保存在一個特征[signature]文件中。每個函數表現為一個模式。模式是一個函數開頭的32個字節，其中所有變數字節用符號標記。例如：
558BEC0EFF7604..........59595DC3558BEC0EFF7604..........59595DC3 _registerbgidriver
558BEC1E078A66048A460E8B5E108B4E0AD1E9D1E980E1C0024E0C8A6E0A8A76 _biosdisk
558BEC1EB41AC55604CD211F5DC3.................................... _setdta
558BEC1EB42FCD210653B41A8B5606CD21B44E8B4E088B5604CD219C5993B41A _findfirst
其中變數字節顯示為“..”，有些函數開始幾字節組成的序列相同。因此樹結構好象很適合用來儲存它們：
558BEC
0EFF7604..........59595DC3558BEC0EFF7604..........59595DC3 _registerbgidriver
1E
078A66048A460E8B5E108B4E0AD1E9D1E980E1C0024E0C8A6E0A8A76 _biosdisk
B4
1AC55604CD211F5DC3 _setdta
2FCD210653B41A8B5606CD21B44E8B4E088B5604CD219C5993B41A _findfirst
字節序列保存在樹的結點中。在這個例子中，樹的根包含序列“558BEC”，三個子樹起源于根，分別地以
字節0E、1E、B4開始。以B4開始的子樹生出兩個子樹。每個子樹以葉子結束。關于函數的信息保存在那里（上述例子中只有名字是可見的）。
[注意此處有誤：根據之前列出的4個模式來看，直接源于根的只有0E和1E兩個子樹，B4應在1E之后]
樹數據結構同時達成兩個目標：
n 存儲器需求減少了，因為我們在樹結點儲存幾個函數共用字節。當然，節省量與具有相同開頭字節的函數數目成比例。
n 它很適合于加快模式速配。將程序中某個特定位置與一個特征文件中所有函數進行匹配所需的比較次數是以函數數目的對數增長。
單獨以函數開頭的32個字節為基礎下結論不是很明智。正如前面所提到的，現代的真實庫包含一些以相同字節開始的函數：
558BEC
56
1E
B8....8ED8
33C050FF7608FF7606..........83C406
8BF083FEFF
0. _chmod (20 5F33)
1. _access (18 9A62)
當兩個函數有相同的開頭32個字節時，它們被儲存在樹的同一個葉子中。為了解決這種情況，我們從位置33起開始計算那些字節的CRC16直到遇到第一個變數字節為止。CRC被儲存在特征文件中。用于計算該CRC的字節數目也需要保存，因為這個數目因不同函數而不同。在上述例子中，計算_chmod函數（字節33到52）的CRC16用了20字節，而_access函數用18字節。
當然，有一種可能性是，第一個變數字節處在33d[十進制數]位置。則用來計算CRC16的字節序列的長度等于零。但實際上，這很少地發生，而且這個算法所引起錯誤識別的次數非常低。
有時函數有相同的起始32字節模式，而且有相同的CRC16，如下面的例子中
05B8FFFFEB278A4606B4008BD8B8....8EC0
0. _tolower (03 41CB) (000C:00)
1. _toupper (03 41CB) (000C:FF)
真抱歉：只有3個字節用來計算CRC16，而且兩個函數的CRC16是相同的。在這種情況下，我們將會嘗試尋找到某個位置，使得同一葉子的所有函數在那里有不同的字節。（在我們的例子中這個位置是32+3+000C）[注意數的進制]
但是既使這個方法也不能識別所有的函數?？戳硗庖粋€例子：
... (這里只顯示樹的一部分)
0D8A049850E8....83C402880446803C0075EE8BC7:
0. _strupr (04 D19F) (REF 0011: _toupper)
1. _strlwr (04 D19F) (REF 0011: _tolower)
這些函數在非變數字節處完全相同，而只有它們調用的函數不同。在這個例子中區別兩函數的唯一方法是檢驗偏移11處的那條指令所引用的名字。
最后這個方法有一缺點：函數_strupr()和_ strlwr()的正確識別依賴于函數_toupper()和_tolower()的識別。這意味著在因為缺少對_toupper()或_tolower()的引用而識別失敗的情況下，我們必須推遲識別并且稍后在找到_tolower()或_toupper()后重做識別。這影響了算法的整體設計：我們需要做第二趟以解決那些被推遲的識別。幸運地，后一趟只應用在程序中少數地方。
最后，你會發現有的函數在非變數字節處完全相同，[而且變數字節]引用相同的名字，但是這些函數被以不同的名字調用。那些函數有相同的實現但有不同的名字。令人驚訝的是，在標準庫中，尤其在C++庫中，這是常見的情形。
我們稱這種情形為‘沖突’，即隸屬于同一葉子的一些函數無法通過上述方法相互區別。下面是一個典型的例子：
558BEC1EB441C55606CD211F720433C0EB0450E8....5DCB................
0. _remove (00 0000)
1. _unlink (00 0000)
或者
8BDC36834702FAE9....8BDC36834702F6E9............................
0. @iostream@$vsn (00 0000)
1. @iostream_withassign@$vsn (00 0000)
人工智能是解決這些沖突的唯一辦法。因為當前目標是效率和速度，所以我們決定把人工智能作為該算法的未來發展方向。
4 實現
在IDA Pro 3.6版中，該算法的實際實現幾乎完全符合以上描述。我們已限制算法只使用于C和C++語言編寫的程序反匯編，但是未來絕對有可能為其他庫編寫預處理器[pre-processors]。
為每個編譯器提供一個單獨的特征文件。這樣隔離降低了跨編譯器的鑒別沖突概率。一個特別的特征文件，名為啟動特征文件[startup signature file]，被應用于所反匯編程序的入口以確定生成它所用的編譯器。一旦得以鑒別，我們就知道應該使用哪個特征文件來反匯編其它部分。我們的算法成功地辨別市場上大多數常用的編譯器的啟動模塊。
既然我們以一個特征文件儲存適合于一個編譯器的所有函數簽名，所以就不必要區別這些編譯器的版本和/或庫的存儲器模型（小的、緊湊的、中等的、大的、極大的）。
對于反匯編文件的每個格式，我們使用專門的啟動特征文件。特征文件exe.sig用于MS DOS下運行的程序，而lx.sig或ne.sig用于OS/2下的，等等。
為了降低短函數的錯誤識別概率，我們必須完全地記錄任何一個對外部名字的引用－－假如存在這樣的引用。這也許會在某種程度上降低函數識別成功的機會，但是我們認為事實證明采用這樣的方式是正確的。錯誤地識別不如不識別。我們創建特征文件時不使用某些短函數（少于4字節），它們不包含對外部名字的引用，而且我們也不企圖去識別這類函數。
來自<ctype.h>的函數很短，但它們引用符號類型數組，所以我們決定把對這個數組的引用作為一個例外：我們計算符號類型數組的CRC16，并將它儲存特征文件中。
沒有人工智能，我們用自然智能解決沖突。特征文件的創作人決定特征文件中函數的取舍。選擇函數是很容易的，而且實際上是編輯一個文本文件。
函數的模式不是以它們的最初形式儲存在一個特征文件中（即，它們看起來不像例子那樣）。我們不使用那些形式的模式，而是儲存一些比特數組，這些位用來確定某些字節的改變，即字節的數值被分離儲存。因此，除了函數的名字以外，特征文件沒有包含來自原始庫文件的字節。特征文件的創建包括兩個階段：庫的預處理和特征文件的創建。在第一個階段使用‘parselib’這個程序。它預處理*.obj和*.lib文件以產生一個模式文件。模式文件包含函數的模式、它們的名字、它們的CRC16以及創建特征文件所需的所有其他信息。在第二個階段，‘sigmake’這個程序從模式文件建立特征文件。
分為兩個階段允許sigmake工具程序與輸入文件的格式無關。因此未來將有可能為非*.obj和*.lib格式的文件編寫另外的預處理器。
我們決定壓縮（使用InfoZip算法）所創建的特征文件以減少儲存它們所需的磁盤空間。
為了方便用戶，我們試圖盡最大可能識別main()函數。鑒別這個函數的算法因編譯器不同而不同、因程序不同而不同。（DOS/OS2/Windows/GUI/Console...）。
該算法作為一個文本字符串被寫入一個特征文件中。遺憾的是，我們還不能自動產生該算法。
5 結果
事實證明那些特征文件壓縮得很好；它們的壓縮系數可能大于2。這個壓縮率的理由是，一個特征文件大約95%是函數名字。（例子：用于MFC 2.x的特征文件在壓縮前是2.5MB，壓縮是700Kb。它包含33634個函數名字；平均每個函數用21字節儲存。通常，一個庫文件尺寸對一個特征文件尺寸的比率從100到500不等。
正確識別函數的百分比非常高。我們的算法識別出那個“Hello World”程序中除一個函數之外的所有函數。未被識別的函數只有一條指令：
jmp off_1234
尤其讓我們滿意的是沒有錯誤識別。然而這并不意味著錯誤永遠不會發生。請注意，該算法只對函數工作。
數據有時位于代碼段，而且因此我們需要把某些名字標記為“數據名”，而非“函數名”。在一個現代的大型庫文件中檢驗所有名字并標記所有的數據名字是不容易的。
我們計劃在未來某時實現這些數據名字的標記。