Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2019, Vol. 53 Issue (5): 829-836    DOI: 10.3785/j.issn.1008-973X.2019.05.002
计算机与控制工程     
基于混合分析的二进制程序控制流图构建方法
朱凯龙(),陆余良*(),黄晖,邓兆琨,邓一杰
国防科技大学 电子对抗学院，安徽 合肥 230000
Construction approach for control flow graph from binaries using hybrid analysis
Kai-long ZHU(),YU-liang LU*(),Hui HUANG,Zhao-kun DENG,Yi-jie DENG
Electronic Countermeasure College, National University of Defense Technology, Hefei 230000, China
 全文: PDF(809 KB)   HTML
摘要：

构建控制流图（CFG）是二进制程序分析的基础工作，针对静态构建方法无法处理间接跳转，动态构建方法效率低、不适用于大规模程序的问题，提出结合静态分析和动态分析的混合分析方法. 使用静态分析获得基础的控制流信息；采用模糊测试生成测试用例以进行动态分析，利用动态插桩获得间接跳转信息；融合静态分析和动态分析结果生成控制流图. 基于该混合分析方法，设计并实现了面向x86平台二进制程序的控制流图构建工具CFGConstructor. 分别在示例程序和CGC数据集上进行实验，评估该工具的有效性和性能. 实验结果表明CFGConstructor相比于静态分析能够构建更加完备的控制流图，相比于动态分析分析效率更高，能够适用于大规模程序.
关键词： 二进制程序分析;  控制流图（CFG）;  混合分析技术;  模糊测试;  动态二进制插桩    
Abstract:

The construction of control flow graph (CFG) was the basis of binary program analysis. A hybrid analysis approach combining static and dynamic analysis techniques was proposed, for the problems that the static construction method cannot handle the indirect jump cases and dynamic construction methods were inefficient and not suitable for large-scale programs. The static analysis technique was used to obtain the basic control flow of the target program. Test cases generated by fuzz testing were used to dynamically analyze the target program, during which a dynamic binary instrumentation technique was used to obtain information of indirect jumps. Finally, the analysis results in the former two steps were integrated to generate CFGs. A CFG construction system CFGConstructor targeting on x86 binaries was designed and implemented based on the proposed hybrid analysis method. Experiments were carried out on the sample programs and CGC dataset to evaluate the effectiveness and efficiency. Results show that the proposed approach can construct more complete CFGs than static analysis do, and is more efficient than dynamic analysis, capable to analyze large programs.
Key words: binary analysis    control flow graph (CFG)    hybrid analysis technology    fuzz testing    dynamic binary instrumentation
收稿日期: 2018-04-19 出版日期: 2019-05-17
CLC:  TP 311  
通讯作者: 陆余良     E-mail: 471801698@qq.com;13329018500@189.cn
作者简介: 朱凯龙（1991—），男，博士生，从事程序分析研究. orcid.org/0000-0001-5241-0157. E-mail： 471801698@qq.com
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
朱凯龙
陆余良
黄晖
邓兆琨
邓一杰

引用本文:

朱凯龙,陆余良,黄晖,邓兆琨,邓一杰. 基于混合分析的二进制程序控制流图构建方法[J]. 浙江大学学报(工学版), 2019, 53(5): 829-836.

Kai-long ZHU,YU-liang LU,Hui HUANG,Zhao-kun DENG,Yi-jie DENG. Construction approach for control flow graph from binaries using hybrid analysis. Journal of ZheJiang University (Engineering Science), 2019, 53(5): 829-836.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2019.05.002    或    http://www.zjujournals.com/eng/CN/Y2019/V53/I5/829

图 1  示例程序virtual_function的源代码和汇编代码
图 2  示例程序function_pointer的源代码和汇编代码
图 3  控制流图构建工具CFGConstructor架构
图 4  控制流图中的间接跳转添加
图 5  IDA、CFGConstructor构建示例程序的控制流图
二进制程序 $\left| {{F_{\rm{i}}}} \right|$ $\left| {{V_{\rm{i}}}} \right|$ $\left| {{E_{\rm{i}}}} \right|$ $\left| {{F_{\rm{c}}}} \right|$ $\left| {{V_{\rm{c}}}} \right|$ $\left| {{E_{\rm{c}}}} \right|$ $I$
virtual_function 5 9 8 8 24 27 2
function_pointer 4 11 12 8 27 33 3
表 1  IDA、CFGConstructor对示例程序的分析结果
二进制程序 S/KB $\left| {{F_{\rm{i}}}} \right|$ $\left| {{V_{\rm{i}}}} \right|$ $\left| {{E_{\rm{i}}}} \right|$ $\left| {{F_{\rm{c}}}} \right|$ $\left| {{V_{\rm{c}}}} \right|$ $\left| {{E_{\rm{c}}}} \right|$ $I$ ${\displaystyle\frac{{\left| {{F_{\rm{c}}} - {F_{\rm{i}}}} \right|}}{{\left| {{F_{\rm{i}}}} \right|}}}\Big/$% ${\displaystyle\frac{{\left| {{V_{\rm{c}}} - {V_{\rm{i}}}} \right|}}{{\left| {{V_{\rm{i}}}} \right|}}}\Big/$% ${\displaystyle\frac{{\left| {{E_{\rm{c}}} - {E_{\rm{i}}}} \right|}}{{\left| {{E_{\rm{i}}}} \right|}}}\Big/$%
pwns 6 17 99 113 19 112 150 8 11.76 13.13 32.74
fsb 8 9 19 20 11 32 38 1 22.22 68.42 90.00
silver_bullet 22 18 102 148 20 115 166 3 11.11 12.75 12.16
ret2shellcode 86 40 72 86 64 102 135 2 35.00 16.67 30.23
pwn250 716 362 14 540 23 038 394 18 742 29 526 370 8.84 28.90 28.16
pwn300 727 453 19 193 28 473 495 20 015 30 461 40 9.27 4.28 6.98
平均值 ? ? ? ? ? ? ? ? 12.62 24.72 33.38
表 2  IDA、CFGConstructor对CGC测试集的分析结果
二进制程序 S/KB T t/s
第1次 第2次 第3次 平均值
pwns 6 104 56.12 56.86 58.72 57.23
fsb 8 2 0.70 0.72 0.71 0.71
silver-bullet 22 93 38.48 38.38 38.61 38.49
ret2she-llcode 86 80 28.58 29.15 29.01 28.91
pwn250 716 45 11.11 11.18 11.27 11.19
pwn300 727 321 83.09 82.22 81.95 82.42
表 3  CFGConstructor动态分析的时间开销
1 HENDERSON A, YAN L, HU X, et al DECAF: a platform-neutral whole-system dynamic binary analysis platform[J]. IEEE Transactions on Software Engineering, 2017, 43 (2): 164- 184
doi: 10.1109/TSE.2016.2589242
2 万志远, 周波 基于静态信息流跟踪的输入验证漏洞检测方法[J]. 浙江大学学报: 工学版, 2015, 49 (4): 683- 691
WAN Zhi-yuan, ZHOU Bo Static information flow tracking based approach to detect input validation vulnerabilities[J]. Journal of Zhejiang University: Engineering Science, 2015, 49 (4): 683- 691
3 NEWSOME J, SONG D. Dynamic taint analysis for automatic detection, analysis, and signature generation of exploits on commodity software　[C]// The 12th Annual Network and Distributed System Security Symposium. San Diego: The Internet Society, 2005: 253–260.
4 ZHANG B, FENG C, WU B, et al. Detecting integer overflow in Windows binary executables based on symbolic execution　[C]// 17th IEEE/ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing. Shanghai: IEEE, 2016: 385–390.
5 FLAKE H. Structural comparison of executable objects [C]// 2004 IEEE Conference on Detection of Intrusions and Malware and Vulnerability Assessment. Vienna: IEEE, 2004: 161–173.
6 BERGERON J, DEBBABI M, DESHARNAIS J, et al Static detection of malicious code in executable programs[J]. Requirements Engineering, 2001, 32 (5): 132- 139
7 JENSEN T, THORN T Model checking security properties of control flow graphs[J]. Journal of Computer Security, 2012, 9 (3): 217- 250
8 YAMPOLSKIY M. Code security analysis with assertions [C]// 20th IEEE/ACM International Conference on Automated Software Engineering. California: IEEE/ACM, 2005: 392–395.
9 PANICHELLA A, KIFETEW F, TONELLA P Automated test case generation as a many-objective optimisationproblem with dynamic selection of the targets[J]. IEEE Transactions on Software Engineering, 2018, 44 (2): 122- 158
doi: 10.1109/TSE.2017.2663435
10 BISWAS P, FEDERICO A, SCOTT A, et al. Venerable variadic vulnerabilities vanquished [C]// Proceedings of the 26th USENIX Security Symposium. Vancouver: USENIX, 2017: 183–198.
11 SIDIROGLOU S, LAHTINEN E, RITTENHOUSE N, et al. Targeted automatic integer overflow discovery using goal-directed conditional branch enforcement [C]// 21th International Conference on Architectural Support for Programming Languages and Operating Systems. Atlanta: ACM, 2016: 473–486.
12 Hex-Rays. IDAPro disassembler [EB/OL]. [2018-02-27]. https://www.hex-rays.com/.
13 BARDINS, HERRMANNP, LEROUX J, et al. The BINCOA framework for binary code analysis [C]// Proceedings of the 23rd International Conference of Computer Aided Verification. Snowbird: CAV, 2011: 165–170.
14 KINDER J, VEITH H. Jakstab: astatic analysis platform for binaries [C]// International Conference on Computer Aided Verification. Berlin: Springer-Verlag, 2008: 423–427.
15 BARDIN S, HERRMANN P, VEDRINE F. Refinement-based CFG reconstruction from unstructured programs [C]// 12th International Conference on Verification, Model Checking, and Abstract Interpretation. Austin: VMCAI, 2011: 54–69.
16 XU L, SUN F, SU Z Constructing precise control flow graphs from binaries[J]. University of California, 2012, 32 (3): 156- 169
17 NGUYEN M H, NGUYEN T B, QUAN T, et al. A hybrid approach for control flow graph construction from binary code [C]// 20th Asia-Pacific Software Engineering Conference. South Korea: APSEC, 2014: 159–164.
18 叶志斌, 姜鑫, 史大伟 一种面向二进制的控制流图混合恢复方法[J]. 计算机应用研究, 2018, 35 (7): 2168- 2171
YE Zhi-bin, JIANG Xin, SHI Da-wei Combined method of constructing binary-oriented control flow graphs[J]. Application Research of Computers, 2018, 35 (7): 2168- 2171
doi: 10.3969/j.issn.1001-3695.2018.07.060
19 Microsoft Research. Z3: an efficient SMT solver [EB/OL]. [2018-04-16]. https://github.com/Z3Prover/z3.
20 王铁磊. 面向二进制程序的漏洞挖掘关键技术研究[D]. 北京: 北京大学, 2011.
WANG Tie-lei. Research on binary-executable-oriented software vulnerability detection [D]. Beijing: Peking University, 2011.
21 YAN S, WANG R, SALLS C, et al. SOK: (state of) the art of war: offensive techniques in binary analysis [C]// 37th IEEE Symposium on Security and Privacy. Fairmont: IEEE, 2016: 138–157.
22 ALFREDV A, MONICA S L, RAVI S, 等. 编译原理: 第2版[M]. 赵建华, 郑滔, 戴新宇, 译. 北京: 机械工业出版社, 2009.
23 ZALEWSKIM. American fuzzy lop [EB/OL]. [2017-11-05]. http://lcamtuf.coredump.cx/afl/.
[1] 戴渭,陆余良,朱凯龙. 基于动态能量调控的导向式灰盒模糊测试技术[J]. 浙江大学学报(工学版), 2020, 54(8): 1534-1542.
[2] 焦龙龙, 罗森林, 刘望桐, 潘丽敏, 张笈. 基于遗传算法的二进制程序模糊测试方法[J]. 浙江大学学报(工学版), 2018, 52(5): 1014-1019.