Survey on Application of Machine Learning in Disassembly on x86 Binaries

doi:10.3969/j.issn.1671-1122.2022.06.002

Abstract

Abstract:

Binary disassembly technology is the core of vulnerability finding, control flow integrity and code similarity measurement. Traditional disassembly techniques highly rely on predefined heuristics and expert knowledge, and its application effect of identifying function boundaries, variable types and reconstructing control flow graphs and other tasks are not good enough. The development of machine learning in handling sequential and graphical data has enabled machine learning to be applied to binary analysis and make up for the defects of the traditional disassembly techniques, thus promoting the researches of binary reverse analysis. This paper focused on the application of machine learning in disassembly on x86 binaries and analyzed in-depth the research work related to function identification, function signature recovery and data flow reconstruction. Firstly, the traditional methods and challenges of disassembly on x86 binaries were summarized comprehensively. Secondly, the general workflow of machine learning in disassembly on x86 binaries including binary feature extraction, vectorization, and model training was distilled. This paper classified the methodologies of feature extraction and vectorization based on the feature contents and embedded approaches respectively, and subsequently summarized the significant techniques of model training utilized in specific disassembly tasks. Finally, the limitations and challenges of current work were concluded, and the future research directions were elaborated.

Key words: disassembly, machine learning, software security, reverse engineering

CLC Number:

TP309

WANG Juan, WANG Yunru, WENG Bin, GONG Jiaxin. Survey on Application of Machine Learning in Disassembly on x86 Binaries[J]. Netinfo Security, 2022, 22(6): 9-25.

Figures/Tables 8

References 62

[1]	ANDRIESSE D, CHEN Xi, VEEN V V D, et al. An in-Depth Analysis of Disassembly on Full-Scale x86/x64 Binaries[C]// USENIX. 25th USENIX Security Symposium (USENIX Security 16). Berkeley:USENIX, 2016: 583-600.
[2]	PANG Chengbin, YU Ruotong, CHEN Yaohui, et al. Sok: All You Ever Wanted to Know about x86/x64 Binary Disassembly but Were Afraid to Ask[C]// IEEE. 2021 IEEE Symposium on Security and Privacy (SP). New York: IEEE, 2021: 833-851.
[3]	SHIN E C R, SONG D, MOAZZEZI R. Recognizing Functions in Binaries with Neural Networks[C]// USENIX. 24th USENIX Security Symposium (USENIX Security 15). Berkeley:USENIX, 2015: 611-626.
[4]	WARTELL R, ZHOU Yan, HAMLEN K W, et al. Differentiating Code from Data in x86 Binaries[C]// Springer. Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Heidelberg: Springer, 2011: 522-536.
[5]	HARRIS L C, MILLER B P. Practical Analysis of Stripped Binary Code[J]. ACM SIGARCH Computer Architecture News, 2005, 33(5): 63-68.
[6]	KINDER J, VEITH H. Jakstab: A Static Analysis Platform for Binaries[C]// Springer. 20th International Conference on Computer Aided Verification. Heidelberg: Springer, 2008: 423-427.
[7]	KRUEGEL C, ROBERTSON W, VALEUR F, et al. Static Disassembly of Obfuscated Binaries[C]// USENIX. USENIX Security Symposium. Berkeley: USENIX, 2004: 18-33.
[8]	LEE J, AVGERINOS T, BRUMLEY D. TIE: Principled Reverse Engineering of Types in Binary Programs[EB/OL]. (2011-02-06) [2021-10-22]. https://www.researchgate.net/publication/221655364_TIE_Principled_Reverse_Engineering_of_Types_in_Binary_Programs.
[9]	ELWAZEER K, ANAND K, KOTHA A, et al. Scalable Variable and Data Type Detection in a Binary Rewriter[C]// ACM. 34th ACM SIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2013: 51-60.
[10]	WANG Ruoyu, SHOSHITAISHVILI Y, BIANCHI A, et al. Ramblr: Making Reassembly Great Again[EB/OL]. (2017-02-27) [2021-11-03]. https://sefcom.asu.edu/publications/ramblr-making-reassembly-great-again-ndss2017.pdf.
[11]	YE Zhibin, JIANG Xin, SHI Dawei. Combined Method of Constructing Binary-Oriented Control Flow Graphs[J]. Application Research of Computers, 2018, 321(7): 254-257.
	叶志斌, 姜鑫, 史大伟. 一种面向二进制的控制流图混合恢复方法[J]. 计算机应用研究, 2018, 321(7): 254-257.
[12]	WANG Jun, PANG Jianmin, FU Liguo, et al. An Efficient Feedback Static Binary Translator for Solving Indirect Branch[J]. Journal of Computer Research and Development, 2019, 56(4): 742-754.
	王军, 庞建民, 傅立国, 等. 一种高效解决间接转移的反馈式静态二进制翻译方法[J]. 计算机研究与发展, 2019, 56(4): 742-754.
[13]	CIFUENTES C, EMMERIK M V. Recovery of Jump Table Case Statements from Binary Code[J]. Science of Computer Programming, 2001, 40(2): 171-188. doi: 10.1016/S0167-6423(01)00014-4 URL
[14]	KÄSTNER D, WILHELM S. Generic Control Flow Reconstruction from Assembly Code[C]// ACM. Joint Conference on Languages, Compilers and Tools for Embedded Systems:Software and Compilers for Embedded Systems. New York: ACM, 2002: 46-55.
[15]	BALAKRISHNAN G, REPS T. WYSINWYX: What You See is Not What You eXecute[J]. ACM Transactions on Programming Languages and Systems (TOPLAS), 2010, 32(6): 1-84.
[16]	BLETSCH T, JIANG Xuxian, FREEH V. Mitigating Code-Reuse Attacks with Control-Flow Locking[C]// ACM. 27th Annual Computer Security Applications Conference. New York: ACM, 2011: 353-362.
[17]	GE Xinyang, TALELE N, PAYER M, et al. Fine-Grained Control-Flow Integrity for Kernel Software[C]// IEEE. 2016 IEEE European Symposium on Security and Privacy (EuroS&P). New York:IEEE, 2016: 179-194.
[18]	SUI Yulei, XUE Jingling. SVF: Interprocedural Static Value-Flow Analysis in LLVM[C]// ACM. 25th International Conference on Compiler Construction. New York: ACM, 2016: 265-266.
[19]	NIU Ben, TAN Gang. Modular Control-Flow Integrity[C]// ACM. 35th ACM SIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2014: 577-587.
[20]	LU Kangjie, HU Hong. Where Does It Go? Refining Indirect-Call Targets with Multi-Layer Type Analysis[C]// ACM. 2019 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2019: 1867-1881.
[21]	TICE C, ROEDER T, COLLINGBOURNE P, et al. Enforcing Forward-Edge Control-Flow Integrity in {GCC}&{LLVM}[C]// USENIX. 23rd USENIX Security Symposium. Berkeley: USENIX, 2014: 941-955.
[22]	KIM S H, SUN Cong, ZENG Dongrui, et al. Refining Indirect Call Targets at the Binary Level[EB/OL]. (2021-02-21) [2021-11-23]. https://www.cse.psu.edu/-gxt29/papers/cfgByDatalog_NDSS21.pdf.
[23]	VEEN V V D, GÖKTAS E, CONTAG M, et al. A Tough Call: Mitigating Advanced Code-Reuse Attacks at the Binary Level[C]// IEEE. 2016 IEEE Symposium on Security and Privacy (SP). New York:IEEE, 2016: 934-953.
[24]	WAHBE R, LUCCO S, ANDERSON T E, et al. Efficient Software-Based Fault Isolation[C]// ACM. 14th ACM Symposium on Operating Systems Principles. New York: ACM, 1993: 203-216.
[25]	ZHANG Chao, WEI Tao, CHEN Zhaofeng, et al. Practical Control Flow Integrity and Randomization for Binary Executables[C]// IEEE. 2013 IEEE Symposium on Security and Privacy. New York: IEEE, 2013: 559-573.
[26]	PEI Kexin, GUAN J, WILLIAMS-KING D, et al. XDA: Accurate, Robust Disassembly with Transfer Learning[EB/OL]. (2020-10-03) [2021-08-11]. https://www.cs.columbia.edu/-junfeng/papers/xda-ndss21.pdf.
[27]	MAIER A, GASCON H, WRESSNEGGER C, et al. TypeMiner: Recovering Types in Binary Programs Using Machine Learning[C]// Springer. International Conference on Detection of Intrusions and Malware, and Vulnerability Assessment. Berlin: Springer, 2019: 288-308.
[28]	PEI Kexin, GUAN J, BROUGHTON M, et al. StateFormer: Fine-Grained Type Recovery from Binaries Using Generative State Modeling[C]// ACM. 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. New York: ACM, 2021: 690-702.
[29]	DUAN Yue, LI Xuezixiang, WANG Jinghan, et al. DEEPBINDIFF: Learning Program-Wide Code Representations for Binary Diffing[EB/OL]. (2020-02-23) [2021-09-11]. https://par.nsf.gov/servlets/purl/10198294.
[30]	YU Zeping, CAO Rui, TANG Qiyi, et al. Order Matters: Semantic-Aware Neural Networks for Binary Code Similarity Detection[C]// AAAI. 2020 AAAI Conference on Artificial Intelligence. California: AAAI, 2020: 1145-1152.
[31]	PEI Kexin, XUAN Zhou, YANG Junfeng, et al. TREX: Learning Execution Semantics from Micro-Traces for Binary Similarity[EB/OL]. (2020-12-16) [2021-09-26]. https://arxiv.org/abs/2012.08680.
[32]	LIU Bingchang, HUO Wei, ZHANG Chao, et al. αDiff: Cross-Version Binary Code Similarity Detection with DNN[C]// ACM. 33rd ACM/IEEE International Conference on Automated Software Engineering. New York: ACM, 2018: 667-678.
[33]	ROSENBLUM N E, ZHU Xiaojin, MILLER B P, et al. Learning to Analyze Binary Computer Code[C]// AAAI. 23rd AAAI Conference on Artificial Intelligence. California: AAAI, 2008: 798-804.
[34]	SU Xiaohui. Cross Platform Binary Code Association Analysis Based on Deep Learning[D]. Harbin: Harbin Institute of Technology, 2019.
	苏晓辉. 基于深度学习的跨平台二进制代码关联分析[D]. 哈尔滨: 哈尔滨工业大学, 2019.
[35]	BAO T, BURKET J, WOO M, et al. BYTEWEIGHT: Learning to Recognize Functions in Binary Code[C]// USENIX. 23rd USENIX Security Symposium. Berkeley: USENIX, 2014: 845-860.
[36]	CHUA Z L, SHEN Shiqi, SAXENA P, et al. Neural Nets Can Learn Function Type Signatures from Binaries[C]// USENIX. 26th USENIX Security Symposium. Berkeley: USENIX, 2017: 99-116.
[37]	GUO Wenbo, MU Dongliang, XING Xinyu, et al. DEEPVSA: Facilitating Value-Set Analysis with Deep Learning for Postmortem Program Analysis[C]// USENIX. 28th USENIX Security Symposium. Berkeley: USENIX, 2019: 1787-1804.
[38]	MU Dongliang, GUO Wenbo, CUEVAS A, et al. RENN: Efficient Reverse Execution with Neural-Network-Assisted Alias Analysis[C]// IEEE. 2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE). New York:IEEE, 2019: 924-935.
[39]	DING S S H, FUNG B C M, CHARLAND P. Asm2Vec: Boosting Static Representation Robustness for Binary Clone Search Against Code Obfuscation and Compiler Optimization[C]// IEEE. 2019 IEEE Symposium on Security and Privacy (SP). New York:IEEE, 2019: 472-489.
[40]	LE Q, MIKOLOV T. Distributed Representations of Sentences and Documents[C]// ACM. International Conference on Machine Learning. New York: ACM, 2014: 1188-1196.
[41]	VASWANI A, SHAZEER N, PARMAR N, et al. Attention is All You Need[EB/OL]. (2017-06-12) [2021-11-23]. https://arxiv.org/abs/1706.03762.
[42]	WANG Shuai, WANG Pei, WU Dinghao. Semantics-Aware Machine Learning for Function Recognition in Binary Code[C]// IEEE. 2017 IEEE International Conference on Software Maintenance and Evolution (ICSME). New York:IEEE, 2017: 388-398.
[43]	ANDRIESSE D, SLOWINSKA A, BOS H. Compiler-Agnostic Function Detection in Binaries[C]// IEEE. 2017 IEEE European Symposium on Security and Privacy (EuroS&P). New York:IEEE, 2017: 177-189.
[44]	FEDERICO A D, PAYER M, AGOSTA G. Rev.ng: A Unified Binary Analysis Framework to Recover CFGs and Function Boundaries[C]// ACM. 26th International Conference on Compiler Construction. New York: ACM, 2017: 131-141.
[45]	HE Jingxuan, IVANOV P, TSANKOV P, et al. DEBIN: Predicting Debug Information in Stripped Binaries[C]// ACM. 2018 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2018: 1667-1680.
[46]	BRUMLEY D, JAGER I, AVGERINOS T, et al. BAP: A Binary Analysis Platform[C]// Springer. 2011 International Conference on Computer Aided Verification. Berlin: Springer, 2011: 463-469.
[47]	SHE Dongdong, CHEN Yizheng, SHAH A, et al. Neutaint: Efficient Dynamic Taint Analysis with Neural Networks[C]// IEEE. 2020 IEEE Symposium on Security and Privacy (SP). New York:IEEE, 2020: 1527-1543.
[48]	ZONG Peiyuan, LYU Tao, WANG Dawei, et al. Fuzzguard: Filtering out Unreachable Inputs in Directed Grey-Box Fuzzing through Deep Learning[C]// USENIX. 29th USENIX Security Symposium. Berkeley: USENIX, 2020: 2255-2269.
[49]	LUNDBERG S M, LEE S I. A Unified Approach to Interpreting Model Predictions[C]// ACM. 31st International Conference on Neural Information Processing Systems. New York: ACM, 2017: 4765-4774.
[50]	RIBEIRO M T, SINGH S, GUESTRIN C. ‘Why Should I Trust You?’ Explaining the Predictions of Any Classifier[C]// ACM. 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2016: 1135-1144.
[51]	RIBEIRO M T, SINGH S, GUESTRIN C. Anchors: High-Precision Model-Agnostic Explanations[C]// AAAI. 2018 AAAI Conference on Artificial Intelligence. California: AAAI, 2018: 1527-1535.
[52]	GUO Wenbo, MU Dongliang. XU Jun, et al. Lemna: Explaining Deep Learning Based Security Applications[C]// ACM. 2018 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2018: 364-379.
[53]	ZHANG Mingwei, SEKAR R. Control Flow Integrity for COTS Binaries[C]// USENIX. 22nd USENIX Security Symposium. Berkeley: USENIX, 2013: 337-352.
[54]	WANG Jianqiang, MA Siqi, ZHANG Yuanyuan, et al. NLP-EYE: Detecting Memory Corruptions via Semantic-Aware Memory Operation Function Identification[C]// USENIX. 22nd International Symposium on Research in Attacks, Intrusions and Defenses (RAID 2019). Berkeley:USENIX, 2019: 309-321.
[55]	ZUO Fei, LI Xiaopeng, YOUNG P, et al. Neural Machine Translation Inspired Binary Code Similarity Comparison beyond Function Pairs[EB/OL]. (2019-02-24) [2021-06-04]. https://arxiv.org/pdf/1808.04706.pdf.
[56]	GRIECO G, GRINBLAT G L, UZAL L, et al. Toward Large-Scale Vulnerability Discovery Using Machine Learning[C]// ACM. Sixth ACM Conference on Data and Application Security and Privacy. New York: ACM, 2016: 85-96.
[57]	LI Zhen, ZOU Deqing, XU Shouhuai, et al. VulDeePecker: A Deep Learning-Based System for Vulnerability Detection[EB/OL]. (2018-02-18) [2021-07-13]. https://zzm7000.github.io/teaching/2021springcse703/papers/1801.01681.pdf.
[58]	XIA Bing, PANG Jianmin, ZHOU Xin, et al. Research Progress on Binary Code Similarity Search[J]. Journal of Computer Applications, 2022, 42(4): 985-998.
	夏冰, 庞建民, 周鑫, 等. 二进制代码相似性搜索研究进展[J]. 计算机应用, 2022, 42(4): 985-998.
[59]	FANG Lei, WU Zehui, WEI Qiang. Summary of Binary Code Similarity Detection Techniques[J]. Computer Science, 2021, 48(5): 1-8.
	方磊, 武泽慧, 魏强. 二进制代码相似性检测技术综述[J]. 计算机科学, 2021, 48(5): 1-8.
[60]	YU Yingchao, CHEN Zuoning, GAN Shuitao, et al. Research on the Technologies of Security Analysis Technologies on the Embedded Device Firmware[J]. Chinese Journal of Computers, 2021, 44(5): 859-881.
	于颖超, 陈左宁, 甘水滔, 等. 嵌入式设备固件安全分析技术研究[J]. 计算机学报, 2021, 44(5): 859-881.
[61]	ZHANG Lei, CUI Yong, LIU Jing, et al. Application of Machine Learning in Cyberspace Security Research[J]. Chinese Journal of Computers, 2018, 41(9): 1943-1975.
	张蕾, 崔勇, 刘静, 等. 机器学习在网络空间安全研究中的应用[J]. 计算机学报, 2018, 41(9): 1943-1975.
[62]	LI Yun, HUANG Chenlin, WANG Zhongfeng, et al. Survey of Software Vulnerability Mining Methods Based on Machine Learning[J]. Journal of Software, 2020, 31(7): 2040-2061.
	李韵, 黄辰林, 王中锋, 等. 基于机器学习的软件漏洞挖掘方法综述[J]. 软件学报, 2020, 31(7): 2040-2061.

任务		算法	难点	准确度
指令识别		线性扫描	填充字符、代码段数据、指令共享字节	≥95%
指令识别		递归下降	间接分支、无返回函数	≥95%
函数识别	main函数	基于调用约定规则	—	≥95%
	函数边界	算法+模式匹配	间接调用、尾调用、多入口函数、编译器、函数共用代码、非连续函数、无返回函数	60%~90%
	函数指纹	难以解决		—
交叉引用识别		大量使用启发式	对齐、数据单元大小、函数入口	≥95%
控制流图生成	基本块	代码扫描+启发式	—	≥95%
	直接跳转、直接调用、尾调用	启发式	—	≥95%
	间接跳转	启发式、值集分析	编译器设定、运行效率	≥95%
	间接调用	难以解决		—
	无返回函数	启发式+ 迭代	函数边界	≥95%

相关工作		人工选择属性	序列化特征	控制流特征	数据流特征
指令边界识别	文献[4]所提方法	—	代码、数据序列	—	—
指令边界识别	XDA	序列位置	原始字节序列	—	—
函数边界识别	ByteWeight	—	原始字节序列、反汇编指令序列	—	—
	文献[3]所提方法	—	原始字节序列	—	—
	文献[33]所提方法	函数序言、尾声模板;自定义结构属性	—	—	—
	FID	—	—	—	寄存器、内存单元数据流依赖
函数指纹、变量类型复原	Eklavya	—	反汇编指令序列	—	—
	TypeMiner	—	—	控制流图	数据单元间依赖关系
	StateFormer	序列位置、操作码位置、架构标识序列	原始字节序列	—	操作数动态值序列
控制流与数据流生成	Deep-VSA	—	反汇编指令序列	—	—
控制流与数据流生成	RENN	—	反汇编指令序列	—	—
其他二进制分析工作	文献[34]所提方法	块级属性、块间属性	—	—	—
	Asm2vec	—	反汇编指令序列	—	—
	DeepBinDiff	—	反汇编指令序列	控制流图	—
	Order Matters	块相邻;图所属;平台、编译器、优化级别	反汇编指令序列	控制流图	—
	Trex	指令位置、操作码位置、架构标识序列	原始字节序列	—	操作数动态值序列
	αDiff	导入的库函数	原始字节序列	调用函数的个数、被调用的次数	—

相关工作		独热编码	有监督的学习嵌入	自监督的语言模型
指令边界识别	XDA	—	—	MLM
函数边界识别	文献[3]所提方法	256维独热向量	—	—
函数指纹、变量类型复原	Eklavya	—	—	skipgram
函数指纹、变量类型复原	StateFormer	—	—	MLM
控制流与数据流生成	Deep-VSA	257维独热向量	—	—
控制流与数据流生成	RENN	257维独热向量	—	—
其他二进制分析工作	文献[34]所提方法	7维独热向量	孪生图嵌入神经网络	—
	DeepBinDiff	—	—	CBoW
	Order Matters	—	ANP、BIG、GC	MLM
	Trex	—	—	MLM

相关工作		算法		数据集	效果（平均）
相关工作		传统机器学习	人工神经网络	数据集	效果（平均）
指令边界识别	文献[4]所提方法	PPM	—	11*[PE(x86)]	Acc.99.98%
指令边界识别	XDA	—	语言模型MLM （RoBERTa）微调dense	3121* [SPEC2017/SPEC2006/BAP(linux/windows;x86/x64)]	Acc.指令99.7%,函数边99%
函数边界识别	文献[33]所提方法	CRF	—	1171*[x86(linux/windows;gcc/icc/msvs)]	AUC 95.61%
	ByteWeight	Weighted Prefix Tree	—	2200*[BAP(linux/windows;x86/x64)]	Pre.92.84%,Rec.92.96%
	文献[3]所提方法	—	Bi-LSTM	2200*[BAP(linux/windows; x86/x64)]	Pre.97.19%,Rec.94.46%
	FID	Linear SVC; AdaBoost; GradientBoosting	—	4240[BAP子集(gcc/icc/llvm;7混淆机制)]	Pre.91.6%,Rec.95.9%
函数指纹、变量类型复原	Eklavya	—	嵌入模型 word2vec; 分类模型 RNN+GRU	5168*[BAP+5扩展包(x86/x64)]	Acc.参数个数 81.72%,参数类型80.69%
	Debin	Extremely randomized Trees;CRF	—	9000*[ELF(x86/x64/arm)]	变量类型 Pre.68.2%,Rec.68.37%
	TypeMiner	Random Forest; LinearSVC	—	14*软件	指针/数值类型Pre.93%,Rec.93%;整型长度Pre.77%,Rec.64%
	StateFormer	—	语言模型GSM（新）微调dense	33*[软件(arm/mips/x86/x64;3混淆机制)]	变量类型Pre.79.41%,Rec.75.19%
控制流与数据流生成	Deep-VSA	—	基于Bi-LSTM的链式网络	78*[软件包(Linux)]	Pre.97.46%,Rec.95.18%
控制流与数据流生成	RENN	—	Conditional GRU（新）	78*[软件包(Linux)]	Pre.99.91%,Rec.99.88%

反汇编结构应用	指令	函数	交叉引用	控制流图
漏洞检测	√	√	√	√
控制流完整性	√	√	—	√
代码布局随机化	√	√	√	√
代码相似度匹配	√	√	—	√
历史代码补丁	√	√	√	√
软件去浮	√	√	—	√
软件故障隔离	√	√	—	√