【VC++开源代码栏目提醒】:文章导读:在新的一年中,各位网友都进入紧张的学习或是工作阶段。
网学会员整理了VC++开源代码-基于二进制可执行代码的控制流分析研究 精灵论文 - 综合课件的相关内容供大家参考,祝大家在新的一年里工作和学习顺利!
基于二进制可执行
代码的控制流分析研究 阳俊文崔宝江 北京邮电大学计算机学院北京 100876 摘要软件安全领域有很多关键问题需要对二进制可执行性
代码进行安全特性的分析。
控制 流分析是进行这些安全特性分析的一个关键步骤。
介绍了基于二进制文件的控制流分析过 程引进支配结点支配树等相关概念分析了条件语句、多路分支语句和循环语句在编译 成二进制文件后在流图和支配树上所表现的特征并描述了条件结构和循环结构的恢复方 法。
关键词 二进制可执行
代码支配树控制流分析 中图分类号TP393 Control Flow Analysis based on binary executable YANG Junwen CUI Baojiang Beijing University of Posts and Telecommunications Beijing 100876 Abstract: In this security areaThere are lots of problems needed to be analyzed base on binary executable. One important step of these security analyze is Control Flow Analysis. The process of Control Flow Analyze based on binary executable is simply introduced in this paper. The concept of domain tree was brought in and then the features of 2-way switch and loop conditionals of binary in the flow graph and domain tree were introduced. Finally we present the domain-tree-base methods of condition switch and loop recovery. Key
words: binary executable Domain Tree Control Flow Analysis 0 引言 日益严重的
网络攻击的发生大多数都是由软件的安全缺陷所引起。
很多情况下这些
软件 的源
代码不可获得或者在源
代码中缺陷不可见因此研究基于可执行二进制文件的缺陷和 漏洞检测具有重大的理论价值和现实意义已成为国内外信息安全的一个研究热点出现了 1 2 3 CodeSurfer BitBlaze 和 IntScope 等二进制分析平台。
基于二进制可执行
代码的分析的相关 研究手段包括静态分析456动态分析78和软件逆向工程等。
控制流分析是对可执行二进制文件进行缺陷检测的一个关键步骤它涉及到汇编
代码中 的顺序、二路分支、多路分支、循环等基本控制结构的恢复问题一个良好的控制流分析 可以得到清晰的程序执行流以用来支持对程序不同执行路径的安全分析。
本文将先介绍基于二进制可执行
代码的控制流分析的整个流程接着引进支配树等相关 概念描述基本控制结构在控制流图和支配树中的特征并给出相对应的恢复方法。
1 基于二进制文件的控制流分析 基于二进制可执行文件的控制流分析的基本流程如图 1 所示其中高级结构恢复包括 了简单的条件语句结构、多路分支语句结构和循环结构的恢复。
基金项目国家“863”项目2007AA01Z466 作者简介阳俊文1985-男硕士软件安全. E-mail: junwenyang15gmail.com 1.1 反汇编算法 图 1 基于二进制可执行
代码的控制流分析流程 Fig 1 The process of Control Flow Analysis base on binary executable 反汇编的目的在于把二进制文件的机器码转化成易于看懂的汇编语言反汇编算法的选 择直接影响着后续的控制流分析。
传统的反汇编算法有线性遍历算法和递归遍历算法两种前者能够最大程度地对二进制 机器码进行识别但由于缺少了对
代码入口和控制流的分析导致数据和
代码不能区分。
后 者从
代码的入口点开始依据跳转指令来进行反汇编能够很好地解决线性遍历算法所产生 的问题但是在对指令进行递归遍历的时候遇到间接跳转指令的时候将会缺失
代码的控 制信息从而会导致部分本该是
代码的指令被跳过反汇编。
国内外的学者针对反汇编过程所碰到的问题做了大量的研究对反汇编算法进行了改 进。
出现了扩展的线性遍历算法、推测反汇编算法、混合反汇编算法等。
1.2 函数识别 正确的函数识别将能使二进制可执行文件的结构更加清晰更具可读性并且可以从这 些调用获得整个二进制可执行文件的准确的类型信息以用在后续的数据流分析中。
函数识别包括了系统库识别和用户库识别。
目前对
系统库的识别是国内外学者的一个研 究热点进行系统库识别的基本思想是建立库文件的特征signatures。
这些特征指的是一 些简单的字节序列他们代表库中每个函数的前几个字节通过运用散列等技术手段在可执 行程序中扫描这些特征来进行库函数识别。
至于用户自定义库识别方面由于用户库的相关 信息缺少、不同编译器生成用户库
代码不尽相同等原因目前研究成果不大现在主要的识 别技术手段有模板库生成、模式识别等9。
1.3 基本块划分和控制流图生成 基本块是指满足下列两个条件的连续指令序列1控制流只能从基本块的第一个指令进 入该块。
也就是说没有跳转到基本块中间的转移指令。
2除了基本块的最后一个指令控 制流在离开基本块之前不会停机或者跳转。
控制流图的结点由基本块构成同时控制流图的边指明了哪些基本块可能紧随着一个基 本块执行。
当将指令序列划分为基本块之后也就得到了控制流图的结点而要得到控制流图还 需要得到流图的边。
在流图中从基本块 B 到基本块 C 之间有一条有向边当且仅当基本块 C 的第一条指令有可能紧跟在基本块 B 的最后一个指令之后执行存在这样一条边的原因 有两种1基本块 B 的末尾指令为跳转指令且跳转指令属于基本块 C。
2按照输入的 指令序列的线性顺序基本块 C 紧跟在基本块 B 后面且基本块 B 的末尾指令不是直接跳 转指令。
在这里基本块 B 是基本块 C 的前驱基本块 C 是基本块 B 的后继。
1.4 支配树的概念 在恢复高级结构的过程中都涉及到了支配树10这一概念下面将对其中涉及到的概 念和原理做一简单介绍。
1 支配节点 如果每一条从流图的入口结点 s 到结点 n 的路径都经过结点 d则结点 d 为结点 n 的支 配结点称 d 支配 n记为 d dom n 。
2 直接支配结点 在从入口结点 s 到结点 n 的任何路径上n 的最后一个支配结点 m 称为结点 n 的直接支 配结点。
结点 n 的直接支配结点 m 具有下列性质如果 d ≠ n 且 d d o m n 那么 d dom m 。
3 回边 若流图中的一条边 a → 4 支配树 b 其中 b 支配 a称边 a → b 为回边。
支配树是具有以下两个特性的树1 树的根节点为控制流图的入口结点。
2 树的任 一结点 n 具有孩子结点 m 当且仅当结点 n 为结点 m 的直接支配结点。
5 基本原理 如果 p 1 p 2 ... p k 是 n 的所有前驱并且 d ≠ n 那么 d d o m n 当且仅当对于每个 id dom p i 。
根据上面所描述的概念和基本原理有以下两个推论 1 控制流图的入口结点的直接支配结点是其自身。
2 一个结点的支配结点集合包括两部分一是该结点它本身另一部分是它的所有前驱的 支配结点集合的交集。
计算流图中各个结点的所有支配结点这个
问题可以写成一个前向数据流分析问题10 以图 2 的示例流图说明。
图 2 控制流图 图 3 支配树 Fig 2 CFG Fig3 Domain-Tree 假定以 Dn 表示结点 n 的支配结点集合。
根据推论 1结点 1 的支配结点为其自身即 D1 1 。
结点 2 只有一个前驱因此 D2 2 ∪ 1 1 2 。
对于结点 3其在流图中有 3 个前驱结点分别为结点 1、结点 2 和 结点 7结点 1 和结点 2 的支配结点集合已计算而对于结点 7由于其支配结点尚未计算 则其为初始化值12 34 5 6 7 8 因此有 D3 3 ∪ D1 ∩ D7 3 ∪ 1 2 ∩ 1 2 3 4 5 6 7 8 1 2 3 类似地得到各个结点的支配结点集合最终得到流图所对应的支配树见图 3 表 1 示例流图中各个结点的支配结点 Tab.1 domain nodes of each node in the CFG 结点 n 结点 n 的支配结点 1 1 2 12 3 13 4 134 5 1345 6 1346 7 1347 8 13478 1.5 简单的条件语句识别 表 2 所示的条件语句源
代码经
VC6.0 编译后得到的二进制可执行文件这两种类型的 条件语句部分的控制流图如图 4 和图 5 所示 表 2 常见的简单条件语句类型 Tab.2 normal conditional statements 简单条件语句类型 1 简单条件语句类型 2 ifE S1 S2 ifE S1 else S2 S3 图 4 条件类型 1 的流图 图 5 条件类型 2 的流图 Fig.4 CFG of conditional statement 1 Fig.5 CFG of conditional statement 2 从流图中可以看到碰到条件语句块的时候会在入口块处产生两条分支并且最终这 两条分支都交汇在出口块处。
条件结构块中图 4 中的结点 3 和图 5 中的结点 4 作为条件结 构子图的终结点称为后随结点条件结构的后随结点定义为条件结构结束后第一个到达的结 点。
图 6 条件类型 1 的支配树 图 7 条件类型 2 的支配树 Fig.4 Domain Tree of conditional statement 1 Fig.4 Domain Tree of conditional statement 1 对于这两种类型的简单条件语句结构设条件结构的起始基本块为 S_BB结束基本块 为 E_BB观察流图和支配树可以得到以下两个特征 1 在支配树上E_BB 为 S_BB 的孩子结点 2 在流图中E_BB 作为后随结点其具有两个或两个以上的前驱。
很明显地在流图中条件结构体内部从 S_BB 开始出现两条分支因此 S_BB 必定为 E_BB 的直接支配结点从而有特征 1。
同时在条件结构体内部从 S_BB 到 E_BB 存在着 两条或两条以上的路径并且这些路径的交汇点必定在 E_BB 处从而有特征 2。
综上可以看到要对控制流图进行条件结构识别最重要的是要寻找到条件结构的后随 结点。
而对于类型 1 和类型 2 的条件结构后随结点处于条件结构的起始跳转块在支配树上 的孩子结点当中。
下面介绍嵌套的条件语句结构在流图和支配树的特征。
图 8 嵌套条件语句的控制流图 图 9 嵌套条件语句的支配树 Fig.8 CFG of nested conditional statement Fig.9 CFG of nested conditional statement 在图 8 所示的流图中存在着两个条件结构条件结构 A 以结点 2 作为起始的跳转块 结点 5 作为后随结点条件结构 B 则是以结点 1 作为起始的跳转块结点 5 作为后随结点。
可以发现对于条件结构 B其后随结点处于该条件结构起始跳转块 1 在支配树中的孩子结点 当中如图 9 所示。
但对于条件结构 A其起始的跳转块是结点 2在支配树上的孩子结点 为 3 和 4这两个结点在控制流图上均是只有一个前驱因此结点 3 和结点 4 都不是条件结 构 A 的后随结点但是如果在支配树上再往上遍历一层得到结点 1可以发现条件结构 B 的后随结点就在结点 1 的孩子结点当中。
综合上面所述得到二进制可执行文件中的条件结构的识别步骤如下 1 初始化 JList 链表和 unchecked 数组。
链表和数组均为空。
2 层序遍历支配树寻找不属于循环结构和多路分支结构的跳转块并将寻找到的跳转块 按层次从高到低地添加到链表 JList 中。
3 若链表空转步骤 5若链表非空从链表中取一个结点记为 J_BB其作为某个条 件结构记为 A的起始跳转块 4 查看 J_BB 在支配树上是否存在一个孩子结点满足下述条件在控制流图中的前驱个数 为 2 个或 2 个以上。
若存在则该满足条件的孩子结点为 J_BB 和 unchecked 数组中所 有跳转块的公共的后随结点此时找到一个unchecked 数组空时或多个条件结构 继续寻找转步骤 3若不存在则说明存在一个嵌套的条件结构可将 J_BB 保存 在 unchecked 数组中转步骤 4 5 在支配树上检查 J_BB 的祖先结点寻找离 J_BB 最近的属于跳转块类型的结点并将其 赋值给 J_BB转步骤 3。
6 结束。
1.6 多路分支语句识别 Switch 块常
常用于同一个操作数取得不同值时的时候需要不同的操作的情况。
Switch 块实质上是创建所有可能的取值以及相应的响应
代码的表。
编译器在遇到 switch 语句见表 3的时候一般将会完成下列的动作 1 计算表达式 E 的值。
2 在 case 列表中寻找与表达式值相同的V j 值。
当在 case
列表中找不到和表达式匹配的 值时就用默认值和表达式匹配。
3 执行和匹配值关联的语句 S j 。
switchE case V1: S1break case V2: S2break ...... case Vn-1: Sn-1break default: Sn 表 3 switch 语句 Tab.3 statement of n-way branches 编译器有几种处理 switch 块的方法具体使用哪一种取决于 switch 块的大小以及表达 式 E 取值的范围在这里介绍最常见的两种二叉查找树实现和跳转表实现。
1 树实现 编译器将 Vj 值表示成一个二叉查找树编译器所生成
代码在检测 switch 块表达式 E 的 时候通过检测 E 的值在二叉树的位置来确定其值从而执行相对应的
代码块 Sj。
2 跳转表实现 编译器跳转表实现的思路是将 switch 块的各个分支语句各个编译并将各个分支的地 址指针存放在一个指针表中在 switch 块执行的时候将表达式 E 的值作为指针表的索引 获得对应分支的地址从而跳转到相对应的分支执行操作。
要注意的是这个过程并不是函 数调用而是一个经过指针表的无条件跳转。
跳转表往往保存在.text 段的
代码空隙里编译器通过将表达式 E 的值作为索引就能 得到其相对应分支
代码的地址从而执行相关操作。
在了解了编译器是如何处理 Switch 语句之后可以根据树实现和表实现的特征进行 switch 语句的识别这里不再详述。
1.7 循环识别 C 语言中常见的几种循环语句经
VC6.0RELEASE 编译后其生成流图和支配关系如 下所示 图 10 while 语句do…while 语句和 for 语句的流图和支配关系 Fig.10 CFG and domain relation of normal loop statements 图 11 whilewhile语句的流图和支配关系 图 12 whileifbreak语句的流图和支配关系 Fig.11 CFG and domain relation of special statement 1 Fig.12 CFG and domain relation of special statement 2 通过对循环条件语句编译后在汇编
代码上特征的分析可以发现循环结构绝大部分都满 足自然循环10的两个条件1有唯一的入口结点。
2存在一条进入循环头的回边。
根据回边的定义通过支配树的辅助可以很容易地找到流图的回边。
得到了回边也 就确定了一个循环结构并且得到了循环结构的起始结点和结束结点。
紧接着我们所需要做 的就是确定循环结构的其他结点。
循环结构的出口可能是不唯一的但根据循环结构具有唯一入口这一性质可以将循环 的起始结点标志为 visited以循环结构的结束结点作为开始在流图上做反向深度遍历这 个遍历过程中遍历到的结点也即是循环结构的其他结点。
综上所述得到汇编
代码里循环结构的步骤如下 1 控制流图生成 2 支配树生成 3 寻找控制流图中的所有回边并加入到回边集合中 4 在步骤3中所寻找到的回边集合中取出一条记为 E_BB-S_BB。
将 S_BB 标志为 visited以 E_BB 为起点在流图中作反向的深度遍历。
5 步骤 4 中遍历到的结点和 S_BB、E_BB 公共组成了一个循环结构。
6 回边集合中还有未处理的回边则继续步骤4否则结束该过程。
如图 2 的示例流图根据支配树可以发现存在两条回边分别为 7-3 和 8-1。
对于回 边 7-3将结点 3 标志为 visited从结点 7 开始做流图的反向深度遍历依次遍历到的结点 将是 4675 或 4576再加上结点 3从而得到了构成一个循环结构的所有结点34675。
对于回边 8-1相类似地也能得到一个循环结构。
2 结语 本文描述了基于二进制可执行文件的控制流分析过程中所涉及到的相关问题完成了流 图的生成和高级结构的恢复等工作得到了清晰的程序执行流为后续的安全缺陷检测提供 了良好的基础。
在基于汇编
代码做控制流静态分析时由于间接跳转和间接调用指令的存在生成的控 制流图和函数调用图将是不完整的从而导致
程序相关信息的缺失。
这也是目前针对二进制 可执行文件进行静态分析的一个尚未完善解决的问题成为了国内外学者的研究热点所在。
对于这个问题目前有两种主流的解决
方案一是利用动静态分析相结合的方法旨在能在 保留静态手段的良好的分析效率前提下利用动态分析的手段来得到程序运行时的相关信 息。
二是引进良好的中间语言表示针对所检测安全特性的特点来
设计中间表示在中间表 示的生成过程中获取程序的相关信息在中间表示的基础上再进行安全缺陷的相关分析。
而 这也正是我们下一步的研究方向和重点。
参考文献References 1 Balakrishnan G Gruian R Reps T et al. CodeSurfer/x86-A Platform for Analyzing x86 Executables. Computer Science 2005 Volume 3443/2005 139. 2 Song D Brumley DHeng Yin et al. BitBlaze:A New Approach to Computer Security via Binary Analysis.Computer Science2008Volume 5352/20081-25. 3 Tielei Wang Tao Wei Zhiqiang LinWei Zou. IntScope: Automatically Detecting Integer Overflow Vulnerability in X86 Binary Using Symbolic Execution. the 16th Network and Distributed System Security Symposium NDSS09San Diego CA February 2009. 4 Cova M Felmetsger V Banks G.Static Detection of Vulnerabilities in X86 Executable. Computer Security Applications Conference 2006. ACSAC 06. 22nd Annual.269-278. 5 Melski.D Teitelbaum.TReps.T. Static Analysis of Software Executables. Conference For Homeland Security 2009. CATCH 09. Cybersecurity Applications Technology. 6 田硕梁洪亮.二进制程序安全缺陷静态分析方法的研究综述.
计算机科学2009367.8-13. 7 忽朝俭李舟军张甲.基于可执行
代码的漏洞检测技术研究.第二届信息安全漏洞分析与风险评估大 会2009. 8 崔宝江国鹏飞王建新.基于符号执行与实际执行的二进制
代码执行路径分析. 第二届信息安全漏洞分 析与风险评估大会2009. 9 陈凯明. 逆编译几项关键技术研究.合肥:合肥工业大学.2003. 10 Alfred V.AhoMonica S.LamRavi Sethietal. Compilers:PrinciplesTechniquesand Tools. Addison Wesley.