库函数的快速鉴别和识别技术

文档编号:

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. 目标

2. 难点

3. 要点

4. 实现

5. 结果

 


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条指令组成)都难以识别,而且错误识别的概率非常高。然而不识别它们是不好的,因为它会导致级联的识别失败:如果我们不识别函数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

 

尤其让我们满意的是没有错误识别。然而这并不意味着错误永远不会发生。请注意,该算法只对函数工作。

数据有时位于代码段,而且因此我们需要把某些名字标记为“数据名”,而非“函数名”。在一个现代的大型库文件中检验所有名字并标记所有的数据名字是不容易的。

我们计划在未来某时实现这些数据名字的标记。