一种重构二进制代码中类型抽象的方法

一种重构二进制代码中类型抽象的方法 ? / /计算机研究与发展 : ? , 一 种重构二进制代码中类型抽象的方法 马金鑫 李舟军 忽朝俭 张俊贤 郭 北京航空航天大学计算机学院 北京中国信息安全测评中心 北京. , ,,, ,。。 , , . , . , . ,,. ... . .; ;;; 摘 要 重构二进制代码中的类型信息对逆向工程、漏洞分析及恶意代码检测等方面具有重大的意义, 由于类型信息在编译过程中被移除,且二进制代码中的低级抽象难以理解,因此类型重构一直被认为是 恢复高级抽象遇到的困难问题之一,现有的大多工具对类型重构的准确度不够高.提出一种保守的类型 重构方法,针对类型重构引入一种简单的中间语言,基于这种中间语言构造寄存器抽象语法树,并使用 寄存器抽象语法树部分解决了基址指针别名问题,可有效收集基本类型和结构体类型的类型约束信息. 提出一种判断二进制代码中的循环结构及识别循环变量的方法,可有效收集数组类型的约束信息,并据 此生成类型约束,然后通过处理类型约束来重构最终的类型.使用 中的 个 程序作为测试用 收稿日期: ? ? ;修回日期:? ? 基金项目:国家自然科学基金项目, ,;教育部高等学校博士学科点专项科 研基金项目 ;软 件开发环境国家重点实验室自主研究课题 一通信作者:李舟军 . .计算机 研究与发展 , 形式的简单中间语言,其中,变 , 量只被定义一次 把庞大复杂的汇编指令归约 这种子类型关系 构成偏序,即满足自反性、反对称 为简单的等式形式,该语言可高效地进行达式替 性和传递性,如: 换,图 给出了其部分语法范畴的定义: , ’ ,?。 这种子类型关系还可扩展到聚合体类型: ? , ??? 一 ‘ 本文使用这种子类型关系作为类型约束,提出 一 种保守的类型恢复方法,通过收集汇编代码中变 量存储单元的分配形式及其语法和语义等信息来生 成类型约束,通过计算类型约束所导出的子类型关 系,可尽可能地确定变量的类型,如 .,则说明 为长整数类型.如果仅有类型 约束 .,则 可能是无符号短整数类型或其 图 中间语言中部分语法范畴的定义 子类型,无法进一步确定其准确类型. 收集的类型约束越多类型推理的结果也越精 针对类型重构,只需考虑赋值、一元操作和二元 确,在汇编代码中,基始类型初始可确定的类型 的 操作这 种指令,这几种操作的语义规则如下所示. 来源主要有常数与库函数.常数自身可说明其类型,赋值操作: 一 般认为是若干字节的整型.而库函数中的参数和 一 ; 返回值也是已知的,通过对库函数中参数和返回值 ’ , 的传播,可恢复出大量的变量类型. 中的大一元操作: 多数复合类型都是从库函数中传播而来,只需引用 旦竺 一 ;。库函数的参数和返回值,不需要分析库函数的内部 过程,所以只需维护一张库函数列表,其中每个表项二元操作: 包括库函数的名称、参数个数、参数类型、返回值类 ? 可 ; , ’ , 型.调用库函数时查找库函数表,如果找到则把对应 其中,一 表示表达式 由一个寄存器项构 的实参、形参及返回值类型都添加到类型集合中 . 成,而 是指该寄存器的被定义次数.在 汇 函数间的参数传递及返回值的恢复需考虑调用约 定,如调用约定,前两个参数存放于 和 编代码中,通用寄存器一般被反复的 引用和定义.因这两个寄存器中. 此,在该中间语言中,等式左值的符号名表示为寄存 相对于库函数,普通函数的类型传播过程更为 器名连接上其被定义次数: ,这保证了 复杂,首先需区分普通函数与库函数 ,然后生成普 它的定义唯一性.汇编代码中的通用寄存器分 通函数间的调用图.使用反向的深度优先算法,从调 为 , , 种. 用图的叶子节点开始遍历 这样可确保在处理某节 需要指出的是:当定义一个或 寄存器 点时,它的所有子节点已被处理,遇到子函数调用 的子寄存器时,则认为是对该寄存器的重新定义.如 时,参数及返回值的类型已确定.当处理完整个调 对 重定义时, 的被定义次数也随之递增.此 用图时,程序的类型约束信息收集过程完成,综合处 外,在指令中还存在一种特殊的赋值情况,理这些类型约束信息即可最终生 成最后的类型. 操作表示把当前栈顶的元素弹出到操作数中,这种 情况需对栈建模,本文中暂不讨论这种情况. 中间语言 . 基于中间语言的寄存器抽象语法树 基于上述中间语言,本文提出一种寄存器抽象 . 中间语言的语法和语义 本文为类型重构提出一种具有静态单赋值 语法树 , 和一马金鑫等:一种重构二进制代码中类型抽象的方法 种流敏感的寄存器算术表达式生成算法. 建 表 说明了建立图 中 的语义规则. 立在中间语言上,是编译过程中的抽象语法树的一, ,表示为相应的操作创建子节 种变型.综合利用控制流分析和数据流分析的结果, 点.对于二元操作指令,则生成两个子节点,分别表 通过 可有效地生成寄存器算术表达式,从而 示其操作数.对于一元操作或赋值操作,则只需生成 进一步生成类型约束信息,甚至可直接根据算术表 个子节点., 建立一个叶子节点.节 达式推理出在当前程序点表达式的类型. 为 点的 属性表示在该节点中寄存器的算术表达 一一一一一~妇一~一一 一一一唧一一一一删一~一一量胡一一一~一~量一一一一量幻一一一一一删一一一一一萋一一一 式,它可能为多个表达式的并集,由当前程序点寄存 树结构,包含若干分支节点 与叶子节点 . 分支节点 表示在该程序点的寄存器表达式关 器的引用一定义链中的元素确定.属性表示节点 于寄存器的计算表达式 ,具有若干个子节点,分别 的实际值,为常数或未知数 当寄存器的值在过程内 是该寄存器表达式中寄存器项的引用一定义链中的 无法确定时 .同一寄存器的不同下标表示该寄存器 元素.叶子节点 表示当前节点为常数 无寄存器 项 或其寄存器项的引用一定义链为空. 表为建立 的属性文法 图 为一段汇编代码样例,图 为对这段代码 生成对第 行寄存器的 ,在图 中顶点 .? “ ”,.,. 即汇编代码中第 行中的源操作数,它的 个 . “ ”,.,. 子节点分别为它引用一定义链中的元素 参考第 .‘‘ ”, .~四一~毗~~四~一一一~一~~一~.一~~ 行和 行 .顶点 . 以两条虚线指向两个节点,表. “一” . 示它的值与其前一状态的值相关 二元操作中既是 .? 一 一 呲 .一 源操作数又是目的操作数 ,另两条实线指向的两个 .? ‘‘一”, . .? 节点 与 节点中的“ ”操作符代表汇编代码 . “ ”,.,. 中的操作符. . “ ”,., . “一”, .. ‘‘ ”, .. “ ”.., .? “ ”.., . . ? ‘‘ ”, . . ? ‘‘一”, . . ? ‘‘一”, .. . . 图 寄存器抽象语法树 图 一段汇编代码样例计算机研究与发展 ,被重定义后其符号名的更新,以便与其以前的状态 加以区分. 类型信息收集 表 的语义规则说明了构造 的过程,根 据语义规则,可给出构造 的如下算法: . 基本类型的识别规则 算法 .构造 的算法. 在汇编代码中,基本类型主要通过存取变量的 输入:根节点; 大小和操作符的特征来进行判断,单字节的变量只 引用单字节的寄存器 , 等 ,短整型的变量引用 输出:以根节点生成寄存器抽象语法树.两个字节寄存器, 等 ,长整型则引用 的寄 ? 当前节点处为赋值指令且源操作数为常 存器, 等 .操作符本身也能表明变量的大 数或内存中变量 包括全局、局部和动态分 小,如由 可知所指向的内存中的 配的变量 ,变量为短整型.此外,通过操作符可直接推断类型的 ? 创建一个子节点,设置其值为该常数; 情况有以下两种: , 等浮点操作符表明操 ?; 作数为浮点类型;操作符表明操作符为指针 ? 类型 . ? 获取当前节点处源操作数的引用 定义链; 判断一个变量是否为有符号类型,可使用以下 ?引用一定义链中的每个元素的指令位置 几个规则: 扩展特征,多出现于整数间的扩展转 ? 当前指令是结果恒定的指令 如 换,有零扩展和有符号扩展两种形式,对应汇编代码 , , 为 和 ; 操作符特征,汇编语法中某 ?; 些操作符对有符号类型进行特殊处理,如, ? 等操作符; 跳转特征,条件跳转指令对有符号类型 ? 创建一个子节点.根据反汇编结果填充子 的处理方式也不同,如无符号的大于跳转操作符为 ,而有符号的大于跳转操作符为 . 节点的数据结构 如果是二元操作指令, 创建两个子节点,分别表示源操作数和目 汇编代码的基本类型只表现为整型和浮点型, 的操作数 ; 其他类型都可强制转化为这两种类型,如字符型可 ? 以看成是单字节的无符号整型,几乎不可能从汇编 ?根节点中的每个子节点 代码中准确地区分字符类型与单字节整型,所以在 ? 递归调用算法 ; 本文中,把字符型都重构为单字节的整型,字符型只 ? 能通过库函数明确的类型定义来确定,如在 函数中,若指定格式串为“ ”时,则对应的参数为 构造出 后,即可生成每个节点的算术表 字符型. 达式.对于图 的例子,最顶端的节点 的表达式 . 复合类型信息收集 可通过遍历 中的每条路径来计算,可生成如 . . 结构体的识别规则 下 个表达式: 结构体是不同类型元素的集合,汇编代码中结 ?: 构体量化为占有相同大小的内存.编译器可能在结. ??卜: 构体内根据 体系的需要插入空字节 如对齐 ? : 需要 .结构体成员的符号名在编译过程中被删除, ? . 并被替换成偏移表示.不同的结构体的成员可能含 由于该算法是控制流敏感的,所以算术表达式 有相同的偏移,因此需要确定基址的别名. 为从多条路径计算后的结果.第 条算术表达式为 结构体的成员可通过收集访问内存的偏移信 两个常整数相加,且结果数值为 ,即可推理息来重构.确认两个结构体的成员是否引用同一内 的类型为 的整型,从图 的第 行可得出在栈 存位置 即是否等价 ,可根据下文提出的基址指针 空间上第 个局部变量一 为的整型. 别名分析法来解决.该算法是保守的,有些内存访问 除可用于传播类型信息外,还可以确定基址 等价对是不可证明的,因为一种结构体类型可能被 指针的别名问题。 重构为几种结构体类型,它们可能分别覆盖不同的马金鑫等:一种重构二进制代码中类型抽象的方法 成员 . 针作为参数传递给被调用函数或者作为返回值返回 在 汇编代码中,结构体的访问模式通常为 给调用函数.,但需区分访问栈元素的情况,一般 . . 基址指针别名分析 情况下,栈元素的访问通过栈桢寄存器,而结构体成 结构体成员的访问通常使用基址加上偏移来表 员的访问使用其他寄存器来作为基址寄存器. 示,当使用不同的寄存器表示基址时,难以确定这些 对于结构体类型,需收集以下的类型信息: 在 寄存器是否指向相同的内存位置.在图 中,第 , 过程内寻找基址等价的 模式的地址 , , , 行中的指令均以寄存器为基址来访问同 一 表达式 不含栈元素访问 ; 过程间通过参数或者 结构体中的成员变量,但分别使用了不同的基址 返回值传递的结构体信息,即把结构体或结构体指 寄存器,这使得分析变得复杂而困难... 图 基址寄存器算术表达式替换过程 等人提出了一种保守的可能别名 ?模式地址访问中引用了相同的基址. 分析方法 ,从汇编代码中提取 谓词, 在实际情况中,需考虑控制流,且表达式也更复杂. . . 数组的识别规则 再把谓词转化为 谓词,然后使用数组是具有相同类型的元素的集合,数组元素 进行分析.这种方法对任意两个地址表达式进行别 使用索引表达式来访问,如访问整数数组 名分析,其代价过高. 中第 个元素,其对应的地址表达式为 × 在访问某结构体成员时,该结构体的基址指针 ,其中的乘法可以作为数组类型的特征, 是数组 可能是当前过程中的形参 栈桢指针的正偏移 、局 元素的大小.多维数组的地址表达式更为复杂,但数 部变量 栈桢指针的负偏移 、堆分配变量/ 组元素的大小总是地址表达式中最小的常量. 等堆分配函数的返回值,为 或者全 程序中的索引表达式更为复杂,考虑× 局变量 绝对地址的访问 .无论是哪种形式,最终都 , 常量 转化对应的低级别地址表达式为会被替换成上述的基址寄存器算术表 达式. × ,因此只通过一个地址表达式并不能正确地确 因此,本文提出一种只针对模式 定数组元素的大小,还需要别的地址表达式来进一 地址的别名分析算法,该算法的核心在于判断两个 步精化,只能推测元素的大小是这些地址表达式中模式的基址是否等价易于 确 乘法常量的公约数 . 定 ,而这种表达式的等价性是易于确定的.下面用 数组访问操作使用常量索引表达式时,如 , 图 中的例子来进行说明. 编译成为使用相对基址偏移的基址表达式,这样的 首先,把反汇编代码转化为中间语言 如图 所 地址表达式不包含乘法部分,不能与结构体相区别. 示 ,然后基于中间语言构造 .从 中提 确定数组元素的个数较困难,几乎所有的 编译器 取基址寄存器的算术表达式. 不提供数组边界检查,因此并不显式地提供数组的 从图 中的基址指针分析过程可以看出,通过 大小.数组的上限有时是已知的,可能是堆栈边界或 计算表达式可把基址寄存器都替换成 即 形参形式的基址 ,图 中第 , , , , 行中的 者紧接另一个变量的边界, 通过确定数组内存区域计算机研究与发展 , , , 行可以看出数组元素的大小 为 ,开始地址 的上下边界可以确定它的大小,另外通过识别循环 结构也可获得数组边界的信息. 为 一, 的上界是 ,每次循环 递增,从 而可推出数组的元素个数为.而在复杂情况下, 对于数组类型,需收集的类型信息包括: 在过 程内寻找 × 模式的地址 跳转条件只与 间接相关,这时也需借助来生成 它的算术表达式,进一步确定真正的 ,目 表达式; 过程间通过参数或者返回值传递的数组 信息,即把数组指针作为参数传递给被调用函数或 前本文中的方案只能处理 的四则算术运算,还 者把数组指针作为返回值返回给调用函数; 使用 无法处理位操作运算. 循环结构访问数组元素的信息. : ; 一 . . 循环结构语义提取: , , 汇编代码中的循环有两种形式: 以 为前 一 ;; ,缀的指令; 与高级语言中类似,表现为控制流的循 ; ,环结构.前者可通过 前缀特征识别,而后者的判 一 断需借助控制流图. , 算法 .判断控制流图 中指定节点是否为循, 环节点.一 :一 输入:控制流图 、指定节点 、当前节点; 输出: 是否为循环节点.. .图 一段简单的循环代码 ? 且节点 在已遍历节点集合中, . 类型约束集的处理 ? 设置节点 循环标志为; 当所有类型约束信息收集完成后,通过类型约 ?; 束生成器生成类型约束集合,通过对该集合的处理, ?可提取出最终的类型 ?.本文考虑 种形式的变 ? 当前节点 在已遍历节点集合中,量: 堆分配存储; 栈分配存储 ? ;; 全局存储,即 ? 一 . ? 把当前节点添加到已遍历节点集合; 类型约束处理包括如下几个过程. ?: ,, ?当前节点 的所有后继节点 即把内存区域划分为变量位置的过程.对于堆分配 ? 递归调用算法 ; 内存,需查找对/ 等动态分配函数的调 ?用,结果储存在 中.对于栈分配内存,在函数序 ? 言中通过对栈指针的偏移来达到对栈内存的分配, 全局内存则是通过绝对地址的访问. 基于控制流图的循环识别算法如上所示:首先:子类型关系的计算与传播过 程. 生成精确的控制流图 见前期工作 ,然后根据循 ? 对每个变量位置,先求出其 的算 环在控制流图中的特征来识别.对于一个指定节点 术表达式 . ,递归遍历其后继节点,若能再次回到该节点,则说 ? 对得到的所有 ,确定其中的子 明 处于一个循环路径中,即 为循环节点. 类型关系. 识别循环中的循环变量,对于 例如,若 为 ,而 识别数组非常重要.在汇编代码中,以 为前 为 ,则显然可知为的子类型. 缀的循环指令的循环变量为 .而对于复杂的循 ? 结合库函数中的类型信息与上一步得到的 环结构, 并不是显式的,一般与跳转条件相关. 子类型关系,可确定每个变量位置 与变量类型 很多情况下,跳转条件直接包括循环变量,例如在图 中,图左侧是一段对整数数组初始化的循环结构, 如 , ,等 的子类型关系. 从右侧的第 行即可看出 一就是 ,从第 , 本文中只处理赋值、一元操作及二元操作这马金鑫等:一种重构二进制代码中类型抽象的方法 种情况的类型约束.对于赋值操作 一 ,显然有 .,内存 . , 版本号为 . .使用 .一元操作不传播类型,只更 中 工具集中的 个程序作为测试 新自身的类型,如指令可以更新自身的类型为 用例,它们均由 编译器编译而成,其二进制代码 有符号型.对于二元操作,其情况则复杂很多.对于 具有良好的结构.使用对其进行类型重构得 到的数据如表 所示: 加减运算,如果一个操作数为整型,而另一个操作数 为指针类型,则结果为指针类型.对乘除运算,如果一 个操作数为有符号整型,那结果也为有符号整型. 表 重构的 工具集类型数据 在代码实现中,为每个变量类型生成一个 ,可通过 来得到 对应 的变量类型,如果是复合类型,还包括该类型的成员 类型、成员数量和该类型所占字节数. : ,通过处理类 型约束集合来重构变量位置的类型的过程. 利用上述得到的变量位置与变量类型间的子类 型关系,使用如下规则来重构类型. 规则 .丁 一 . 一一 ~ 一州一 一 一 誊 规则 . 一 . 规则 . 一 上述规则 和规则 表明,本文采取的类型重 构方法是保守的.规则 表示:若为 的子类型,则将的类型重构为 .规则 表示: 若 不为任何类型的子类型,即没有其他 信息可使其精化时,则将 的类型重构为 ,表示任意类型. 表 结构体类型重构对比 实验结果分析/ ? ? 蝎”卯 ? 根据以上所述的方法,本文基于 的插 件框架,使用约 行代码实现了一个重构 类型的原型系统 ,其输入是二进制代码. 使用类型信息库 文件中的数据 类型定义来识别各种数据类型.对于不同编译器生 成的二进制文件, 在分析过程中加载不同 的 文件.如对. 的编译器生成 的二进制文件,则加载. 类型信息库文 件. 的插件作为 的反 编译模块,也使用 文件中的数据类型定义识别 各种数据类型,它对基本类型具有较高的准确识别 率.而对高级类型 特别是结构体 识别能力较差,而 本文提出的方法恰好可弥补这一不足. . 实验结果 实验环境为英特酷睿 代 ,主频计算机研究与发展 ,执行文件,执行二进制文件,并监视、收集 在表 中, 代表单字节型变量的个数,代表字符型变量的个数,代表无符号短整型 和分析动态信息,最终提取数据结构的语法和语义. 变量的个数, 代表短整型变量的个数, 代表 文献 描述了一种在线和离线的类型传播方案, 整型变量的个数,代表无符号整型变量的个 但并未详细地给出恢复复合类型的方法.等人 提出了一种基于推理的数据 数, 代表 类型变量的个数, 代表指 针类型变量的个数, 代表数组类型变量的个数. 抽象恢复方案,并实现了 一种新的基于类型重构理 论的类型推理系统 ,可处理控制流,可应用于动 重构以上几种类型的能力与? 相差不 多,故不在此作比较,而对结构体的识别能力则大大 态与静态的环境中. 使用朝转化二进制代 超过 ? ,实验对比结果如表 所示,码到二进制分析语言 ,使用 算法分析内 “ 表示由 重构类型的结构体变量的个 存的访问模式来确认变量类型,然后把 恢复 数, 是由重构类型的结构体变量的个 的变量传递到类型重构算法,最终生成变量类型. 数,表示文件的大小,表示重构类型所耗实现了一种比较严格的类型重构方法,其中 时间成本. 需要对任意表达式的值集进行计算,成本过 . 讨 论 高且并不一定有实效.等人口 提出了一种自动重构高级别 从表 可以看出,本文方法不仅效率较高,处理 性能可达到约. ,而且重构结构体类型的 的合成类型的方法,为不同的内存访问操作建立对 能力大大地超过了 ,恢复的结构体数量约 象模型,提取尽可能多的关于合成类型的信息,建立 是 的 倍.经过人工验证分析,就这些例子 对应于高级类型的标号集,维护一个不相交集合 每 而言并未发生误报结构体类型的情况.例如,从 个标号放置于自己的不相交集合中 来快速查找标 的验证参考地址: , , , 号等价类,最后通过聚合这些等价类来重构合成类 , ,即可说明成功地重构 型.其方案存在如下缺陷:未处理指针类型,不能恢 出 个结构体变量的类型,而 无法重构出 复数组的大小. 它们的类型.等人 提出了一种值集分析 由于类型信息的缺失,所有二进制代码类型重 ?, 与聚合结构体识别 ? 构的方法都根据汇编语言的语法和操作行为特征来 ,相结合的算法, 推理类型.而在汇编代码中,有些复合类型的操作行 比 识别的 更为严格. 为特征并不明显,因此有可能无法进行准确的类型 是基于程序访问内存模式来确定结构,需要假 重构,例如以下几种情况. 设数据访问模式在程序中是比较清晰的,但这在复合类型被当作整体处理.此时不会对复合 下并不成立.该算法以恢复的信息作为类型的单个元素进行访问,因而无法被识别. 的输人,通过结合 与 可恢复除显式的地经过优化后的二进制代码可能直接把复合 址和偏移以外的间接引用内存的?,可识别结 类型的元素作为独立的变量.这种情况下缺少更多 构体、数组以及数组与结构体的嵌套.但 方法 的信息把这些变量合并成复合类型. 成本过高,且 作为一个启发式只能适用于特定复合类型间发生混淆.如果一个结构体中的 的环境,缺少通用性. 成员都具有同样的类型在函数中这种情况很 常见 ,有时无法将其与数组进行区分.结束语 相关工作 本文提出了一种从二进制代码中重构基本类型 和复合类型的方法:针对类型重构引入了一种简单 近年来重构类型方面的研究并不多见,除的中间语言,并基于该中间语言提出一种构造寄存的和 等反编译软件外,还 器抽象语法树的方法;使用寄存器抽象语法树较好 有一些以类型重构为主要研究目标的相关研究成果. 地解决了基址指针别名问题;提出了一种在二进制 等人? 实现了一种基于动态分析自动提取 代码中判断循环结构及提取循环次数变量的方法; 程序数据结构的工具 :给定一个二进制可 基于这些方法生成类型约束信息,然后通过处理类马金鑫等:一种重构二进制代码中类型抽象的方法 , . 型约束来重构最终的类型.从实验结果数据可看出, / 本文方法可较准确地恢复基本类型,并在结构体类. : 型的重构方面比现有工具具有明显的优势,可用于 , :? 大型二进制程序的类型恢复.本文所提出的方 , .法对于重构二进制代码中的结构体变量结果较好, /’ . 但对于数组类型,特别是多维数组的重构能力还有:’, : ?待进一步改进,这作为本文的下一步需要进行深入 , , . . 研究的工作. : , ,: ?参 考 文 献 马金鑫,忽朝俭,李舟军.基于控制流精化的反汇编方法 .清华大学学报:自然科学版, ,: ?,. . . ? ?, , : ?.刘宗田,李力. 逆编译数据类型恢复技术 .计算, , :?机研究与发展,, : ?, , .: 周晓聪.类型系统的等式理论及其语义的合理性 .计算 / 机研究与发展,, : ? . , .: , // , ,, .. :, : . , , . , , : 忽朝俭,李舟军,郭涛,等.写污点值到污点地址漏洞模式// 检测 .计算机研究与发展, , :.: , ,. , , ,.:. / ,, :? . : , :?吴伟峰,赵荣彩.反编译中用户函数与库函数同名的区分 , . ? 技术研究 .计算机学 报, , :? , , ./ .?// : , :? ,.: . : ,//, . ,, , . : , : ?// ,. ? . :, :?/ . ? . : , : / , . . . :, : ? ,. . / . : , : ?