二进制代码内联库函数识别

摘 要：内联库函数识别是二进制代码分析的难点问题之一。主要的挑战来自在编译优化的作用下，内联库函数在目标函数中存在多态性和不连续性。本文构建函数的执行流图，将内联库函数识别问题转化为执行流图子图同构测试问题。实验中，对四个常被编译器内联的字符串操作函数，使用MSVC10和ICC14这两个编译器在5个开源软件中进行内联库函数识别测试。实验结果表明，本文方法可以有效识别二进制代码中的内联库函数。

关键词：二进制代码分析；内联库函数识别；子图同构

中图分类号：TP311 文献标识码：A 文章编号：2095-2163（2015）05-

Inline Library Functions Identification in Binary Code

QIU Jing， SU Xiaohong， MA Peijun

（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001，China）

Abstract： Inline library functions identification is one of the difficult issues in binary code analysis. The main challenge comes from the polymorphism and discontinuity of inlined functions due to compiler optimizations. The paper builds execution flow graphs of functions， converting inline library functions identification to subgraph isomorphism testings. In the evaluation， four string operation functions， which are often inlined by a compiler， are evaluated by using MSVC10 and ICC14 with five open source programs. Experimental results show that the proposed approach is effective in inline library functions identification.

Keywords： Binary Code Analysis； Inline Library Functions Identification； Subgraph Isomorphism

0 引 言

随着计算机软件业的不断发展，计算机软件安全日益引起人们关注。二进制代码分析是计算机软件安全领域的一个重要手段。在分析某些无法获取源代码的软件时，分析其二进制代码几乎是唯一手段。人们很少直接分析二进制代码，因此一般都是先将机器代码反汇编成汇编代码。库函数识别的作用在于可以直接将反汇编代码中的大段代码替换成可理解的符号（函数名），便于分析人员理解整个程序的反汇编代码。在编译优化的作用下，内联库函数在内联到目标代码后，形态可能发生变化。因此，内联库函数识别存在两个难点要解决。首先，为了对齐指令地址，或指令流水优化，编译器可能会调整一个函数的某些指令顺序，造成内联库函数字节不连续。其次，编译器寄存器分配策略也会影响内联后的指令，使其发生变化。针对这两个问题，本文基于执行流图来识别内联库函数。

1 库函数识别

1.1 执行流图

执行流图EFG （Execution Flow Graph） ，V代表指令集合， 代表指令之间执行依赖关系。边（vi， vj）表明vi早于vj的执行。使用R/W 表示指令读/写的变量集合，D 表示指令的地址。

一个EFG中的边有两类。第一类边在基本块（单进单出的指令序列）内。对于基本块内的两个点a， b， 如果满足 ， ， 或者b为控制流转移指令，则存在a到b的边。 另一类在基本块间。边（a， b）满足：（1） a和b分别在不同的基本块B1和B2内；（2） a可以在基本块B1 中最后执行，b可以在基本块B2中第一个执行；（3） 在控制流图中，B2是B1的后继。

EFG的构造分为两步。首先，划分函数的基本块，构造控制流图。然后，在基本块内进行数据依赖分析，得到局部EFG。最后，对于每对在控制流图中直接相连的基本块，连接其所对应局部EFG中的出口点和入口点。对于局部EFG中的任意三点A， B， C，如果存在三条边（A， B）， （B， C）， （A， C），则删除边（A， C），因为这条边是冗余的。

1.2 指令编码

指令编码用来将一个指令转换到一个标准形式。首先，一条指令通过下列步骤规范化来消除指令差别：

（1） 指令规范化。 使用reg1来表示指令操作数中的第一个寄存器，reg2表示第二个寄存器，以此类推。如“mov eax， ecx” “mov reg1， reg2”，“xor eax， eax” “xor reg1， reg1”。

（2） 内存规范化。 使用M表示访存操作数，如“mov eax， [ebx]” “mov reg1， M”。

其次，用二元组SR=（m， r）表示消除差异后的指令，其中m表示指令助记符，r为操作数特征值。r中的数字，从高到低，表示操作数的类型。如r=1表示“op reg1”， r=11表示“op reg1， reg1”， r=21表示“op reg1， reg2”。表1给出了指令的所有可能特征值。

最后，SR=（m， r）通过调用函数ID（SR）=Hash（m） | （r

1.3 识别

在库函数集合F中识别识别目标函数fT的过程如下：（1） 反汇编fT ，（2） 构造fT的CFG，（3） 对于F每个内联库函数fL：

构造fT的EFG；

检测GT中所有与fL的EFG同构的子图；

检测每个检测到的子图是否可以外联（参见本文之前的工作[1]）；

④ 报告每个检测到的可以外联的子图为一个库函数。

2 实验

2.1 设置

实验所用开源程序列表如表2所示。相应地，分别使用Microsoft Visual C++ 10 （MSVC）和Intel Compiler XE 14 （ICC）编译，并生成调试信息。

由于源代码和二进制代码间存在巨大差异，二进制代码中的内联函数的真实信息几乎不可能获知。内联函数和其余代码之间没有明显分界。任何代码片段都可以视为某个内联函数的实例。但由于实验对象是开源软件，因此在一个内联函数之后可以插入一些特殊代码，就可以定位到内联函数的真实信息且不会影响内联函数的EFG。

从源代码编译得到的二进制文件称为原始文件集。从修改后的源代码编译得到的可执行文件称为修改的文件集。在修改的源代码中，一些函数的随机位置入宏“LIBV（P）”。P是一个指针或者一个变量的地址。在宏里，输出库函数的结果到屏幕，使得插入代码不会被当成死代码。然后修改宏的定义来生成修改的二进制文件集。strlen（）的定义为“#define LIBV（P） printf（"libvcode＼%d"， strlen（（char*）（P）））”。其他函数类似。printf的特殊格式有助于在汇编代码中识别插入的代码。 比如在识别strlen（）中，代码

在反汇编代码中为

其中，位于loc_40B600和push eax之间的代码是strlen（）的一个实例。

实验中的内联库函数有strlen（）， strcpy（）， strcmp（）， memcmp（）。这些函数经常被MSVC内联。相应的源代码来自“＼Microsoft Visual Studio 10.0＼VC＼crt＼src”。汇编代码来自Visual C++ 10，使用参数/FAcs编译（输出汇编代码，机器代码和源代码）。编译使用这些库函数的样本代码并提取内联的代码。

对于原始文件集，如果识别出的内联函数在源代码中能找到，则认为识别结果是正确的。原型工具在原始二进制文件集中识别所有4个内联函数。函数strlen（）， strcpy（）， strcmp（）在C/C++程序中常见。在C++中标准字符串类的操作包含了这些C字符串函数。在原始二进制文件集的实验中，这些识别结果也会被认为是正确的，即使识别出的函数没有在源代码中显式使用。对于修改的文件集，只统计以“libvcode%d”为格式化字符串的printf结尾的识别结果。内联函数的真实情况由IDA的一个插件来统计，通过扫描以“libvcode%d”为格式化字符串的printf得到。

由表3中可见，除了WinMerge，其余程序的每种内联函数数量都不相同。因为一种内联函数的文件集是通过改变插入宏的定义来生成的，这就使得理论上不同内联函数的数量应该一致。但是，一个内联函数实例的数量在没有检查二进制代码前是不确定的，因为某些入宏的短的目标函数可能会被编译器内联。另一方面，源代码中插入的宏在编译预处理阶段被展开，增加了一个目标函数的大小。因此，一些目标函数在宏定义为一种内联函数时会被内联，而在宏定义为另一种内联库函数时则不会被内联。

2.2 实验结果

表4和表5分别给出了MSVC和ICC在原始文件集上 查准率。表中的'-'表示无法计算值。原始文件集里的内联库函数的真实情况未知。因此在表4和表5中查全率无法给出。表6给出了MSVC编译的修改的文件集的查全率和查准率。WinMerge中的strcmp的查准率是空的，因为strcmp在WinMerge中没有被内联。ICC编译的修改的文件集的实验结果没有列出，因为没有发现任何结果。

2.3 讨论

2.3.1 查准率

表4表明原型工具可以准确地识别内联函数。在原始文件集中仅有少数误报。误报是因为工具无法区分字符串函数的宽字节版本和非宽字节版本。类似wscmp（）被误认为strcmp（）。两者之间代码的差别就在于操作数的大小（宽字节版本16位，非字节版本8位）不同。而在指令编码中，不考虑操作数的大小，因此导致了上述误报。

2.3.2 查全率

如表6所示，在修改的文件集中，除了memcmp（），查准率都很高。这是因为memcmp（）的指令发生了改变。代码如下所示。

而从编译器提取的memcmp（）的代码如下。

通常，有三个原因造成漏报。首先，函数的反汇编代码可能是不完整的。在反汇编中，工具在遇到间接跳转时停止反汇编。在修改的文件集中，有些代码是插入到了一个case语句中。因为switch/case语句常被编译器翻译为间接跳转，因此这些内联函数没有被工具识别。

其次，在编译器优化后，一个内联函数可能有不同的指令序列。大多数的漏报都是由于这个原因。比如，编译器可能将一条指令替换为语义等价的指令。如test eax， eax可以替换为cmp eax， ebx，当ebx值为0时。内联函数的参数可以通过寄存器或内存来传递。传递方式也会影响一个内联函数的指令。memcmp（）参数count保存到了局部变量var_268中，而在库函数中则是一个寄存器中。其他优化，如循环判断外提和循环展开也会影响识别结果。

特别地，一个内联函数可能消失在二进制代码中。一个表达式的结果可能会在编译时被编译器计算出。如strlen（）的参数是一个固定字符串，编译器会直接计算出字符串的长度，而不会生成调用strlen（）的代码。因此，一些内联函数可能在修改后的文件集中没有出现在期望的位置，也就没被工具发现。

最后，一个内联函数在不同的编译器编译后可能有不同的指令序列。在实验中，因为内联函数的代码是从MSVC中提取，这些代码可能会和其他编译器编译的完全不同。在ICC编译的代码里， 由于某些未知原因，strlen（）和strcpy（）不总是内联。memcmp（）和strcmp（）被ICC内联，但是对其编译后的二进制代码却与MSVC编译的有所不同。因此，和MSVC编译的原始文件集的实验结果对比，ICC编译的原始文件集中却只有很少的内联函数获得识别，如表5所示。

3 相关工作

最负盛名的的库函数识别技术是IDA FLIRT[2]。使用字节模式匹配算法来判断一个目标函数是否与IDA 已知的签名匹配。DCC[3]类似于FLIRT。Hancock[4]扩展了FLIRT技术，提出一个库函数引用启发规则，认为一个函数如果在一个库函数中被静态调用，那么该函数也是库函数。这些方法的主要缺陷在于一个函数只有头n个字节作为匹配模式。尽管通过增大n的大小，精度可以很容易获得提高。但是不能保证导入所有库函数。UNSTRIP[5]通过系统调用接口即可识别在二进制代码中的包裹函数（Wrapper Function）。尽管如此，这个方法却只是局限于识别包裹函数，因为一个库函数可能没有call指令。

最近，文献[6]提出了一个二进制代码搜索的技术。为了计算函数间的相似性，即将函数分解为连续，且简短的代码序列。本文方法和该文献中的方法都需要和编译器优化。而且，文献[6]中的方法的最大限制是可能产生差的结果，当匹配拥有低于100基本块的函数。

Saed等人提出了一个通过匹配语义整合图的短路径（轨迹）识别二进制代码中复用函数的新技术[7]。一个语义整合图整合了控制流图，寄存器流图，函数调用图。尽管这一方法和本文方法相同之处都是基于图，但是其中的匹配过程却和本文完全不同。另外，该法在图上定义了不同类型的轨迹，并且是使用图编辑距离来衡量两个图的相似度。

4 结束语

识别不连续字节或有多个变种的库函数是困难的。本文介绍了一个识别内联库函数的新方法。方法的新颖性在于将库函数识别问题转化为EFG子图同构问题。在一些流行软件上设计了一定仿真，从而验证了本文方法的有效性。如何加速子图同构测试将是本文下一步的重点研究工作。

参考文献：

[1] QIU J， SU X， MA P. Library functions identification in binary code by using graph isomorphism testings[C]//Software Analysis， Evolution and Reengineering （SANER）， 2015 IEEE 22nd International Conference on， Montreal， Canada： IEEE， 2015： 261-270.

[2] Hex-Rays. Fast library identification and recognition technology[OL/EB]. （1997） [2015-7-17]. https：///products/ida/tech/flirt/in_depth.shtml.

[3] Van Emmerik M. Signatures for library functions in executable files[M]. Brisbane， Australia： Queensland University of Technology， 1994.

[4] GRIFFIN K， SCHNEIDER S， HU X， et al. Automatic generation of string signatures for malware detection[C]//Recent Advances in Intrusion Detection， Saint-Malo， France： Springer Berlin Heidelberg， 2009： 101-120.

[5] JACOBSON E R， ROSENBLUM N， MILLER B P. Labeling library functions in stripped binaries[C]//Proceedings of the 10th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools， New York， NY， USA： ACM， 2011： 1-8.

[6] DAVID Y， YAHAV E. Tracelet-based code search in executables[C]// Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation， New York， NY， ACM， 2014， 49（6）： 349-360.

[7] ALRABAEE S， SHIRANI P， WANG L， et al. SIGMA： A semantic integrated graph matching approach for identifying reused functions in binary code[J]. Digital Investigation， 2015， 12： S61-S71.