二进制代码多形态库函数快速识别研究

Library function identification is important for binary code analysis, which helps to improve the degree of automation of analysis and reduce the workload of analysts. The proposed project will address four problems in existing approaches by using the approach that is based on the subgraph isomorphism testings of a new execution flow graph. First, current approaches based on execution flow graphs cannot distinguish constant values of instructions and cannot distinguish the library functions with identical bytes. We propose a new execution graph, classifying the operands of instructions into two classes: the one can be ignored and the one cannot be ignored. The type information of dependence is also added to the edges for increasing the precision of identification. Second, current approaches have not taken the morphism into consideration and means of code transformation can be implemented in combination. Thus, the semantic equivalent instruction sequence of an instruction sequence is regarded as a library function and identified by library function identification and rewriting. Third, current approaches cannot identify a library function that is optimized by common subexpression eliminations. We propose a novel method for common subexpression anti-eliminations. We abstract the execution flow graph by removing irrelevant instructions. Then, if an instance of the library function exists, the target function is rewritten by copying the common subexpression for identifying the library function. Finally, subgraph isomorphism testings have a high time complexity. We develop filters and use parallel techniques to accelerate the identification.

库函数识别是二进制代码分析中重要环节，有助于提高分析的自动化程度，减轻分析人员的工作量。本项目提出一种基于新的执行流图子图同构测试的库函数识别方法，解决现有识别方法存在的4个问题。首先，针对现有基于执行流图的方法无法区分指令常量和字节完全一致的库函数的问题，提出新的执行流图，将指令操作数区分为可忽略的和不可忽略的，并对执行流图的边增加依赖类型信息，提高识别精度。其次，针对现有方法尚未对多态库函数处理，且代码变形手段可以组合实施的问题，将指令序列的等价序列视为库函数，并通过库函数的反复识别和改写来识别多态库函数。再次，针对现有方法无法识别经过公共子表达式消除后的库函数的问题，提出公共子表达式反消除方法，通过忽略不相关指令来简化执行流图，进而检测是否存在库函数，并进一步通过复制公共子表达式来识别库函数。最后，针对子图同构测试时间复杂度较高的问题，设计过滤器并使用并行处理技术来加快识别速度。

二进制代码分析常用于源代码缺失的场景中，如恶意代码分析，第三方软件漏洞挖掘。库函数识别是将二进制代码中成块的代码识别成简单易理解的符号，帮助分析人员或其他工具理解二进制代码。当前研究存在的挑战在于函数边界的不确定性、多形态。本课题针对无交叉引用、无明显头特征函数传统方法无法识别的问题，研究了应用深度学习方法识别函数返回函数，基于此识别函数。针对海量二进制代码搜索无法快速检索的问题，研究了基于传统全文检索技术的搜索引擎，能够指出搜索代码和命中代码具体的映射，能够验证执行依赖。最后，作为二进制代码库函数识别的一个应用，针对当前在线考试系统无法有效检测直接输出作弊的问题，提出了基于抽象语法树、控制流图搜索、深度学习文本分类三种方法检测直接输出作弊。本课题执行期间取得了良好的进展，产出了一系列研究成果并发表于国际期刊。