Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2019, Vol. 53 Issue (5): 829-836    DOI: 10.3785/j.issn.1008-973X.2019.05.002
    
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
Download: HTML     PDF(809KB) HTML
Export: BibTeX | EndNote (RIS)      

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     
Received: 19 April 2018      Published: 17 May 2019
CLC:  TP 311  
Corresponding Authors: YU-liang LU     E-mail: 471801698@qq.com;13329018500@189.cn
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Kai-long ZHU
YU-liang LU
Hui HUANG
Zhao-kun DENG
Yi-jie DENG
Cite this article:

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.

URL:

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


基于混合分析的二进制程序控制流图构建方法

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


关键词： 二进制程序分析,  控制流图（CFG）,  混合分析技术,  模糊测试,  动态二进制插桩 
Fig.1 Source code and assembly code of sample program virtual_function
Fig.2 Source code and assembly code of sample program function_pointer
Fig.3 Architecture of CFG construction tool CFGConstructor
Fig.4 Addition of indirect jumps to CFG
Fig.5 CFGs of sample programs constructing by IDA and 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
Tab.1 Analyzing results on sample programs by IDA and 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
Tab.2 Analyzing results on CGC dataset by IDA and CFGConstructor
二进制程序 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
Tab.3 Timecost of CFGConstructor dynamic analysis
[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] JIAO Long-long, LUO Sen-lin, LIU Wang-tong, PAN Li-min, ZHANG Ji. Fuzz testing for binary program based on genetic algorithm[J]. Journal of ZheJiang University (Engineering Science), 2018, 52(5): 1014-1019.