Binary Code Fingerprinting for Cybersecurity: Application to Malicious Code Fingerprinting

Preface
Acknowledgments
Contents
List of Figures
List of Tables
1 Introduction
	1.1 Motivations
	1.2 Binary Fingerprinting for Cybersecurity
	1.3 Outline
2 Binary Analysis Overview
	2.1 The Importance of Binary Analysis
		2.1.1 Evading Techniques of Malware Detection
		2.1.2 Binary Analysis Challenges
	2.2 Software Fingerprinting Applications
		2.2.1 Authorship Attribution
		2.2.2 Clone Detection
		2.2.3 Library Function Fingerprinting
		2.2.4 Binary Software Evolution
		2.2.5 Vulnerability Analysis
		2.2.6 Program Provenance Analysis
	2.3 Methodology
		2.3.1 Nature of Binary Analysis
			2.3.1.1 Static Analysis
			2.3.1.2 Dynamic Analysis
			2.3.1.3 Hybrid Analysis
		2.3.2 Binary Analysis Strategies
		2.3.3 Binary Analysis Approaches
		2.3.4 Feature Taxonomy
	2.4 Implementation
		2.4.1 Disassembling Tools
			2.4.1.1 Interactive Disassembler (IDA)
			2.4.1.2 Objdump
			2.4.1.3 Portable Executable Explorer
			2.4.1.4 Paradyn
			2.4.1.5 Jakstab
			2.4.1.6 OllyDbg
			2.4.1.7 Angr
			2.4.1.8 ByteWeight
		2.4.2 Feature Ranking
		2.4.3 Machine Learning Techniques
			2.4.3.1 Fingerprint Classification
			2.4.3.2 Fingerprint Clustering
		2.4.4 Distance Between Features
	2.5 Code Transformation
		2.5.1 Obfuscation Techniques
		2.5.2 Refactoring Techniques
		2.5.3 The Impact of Compilers
	2.6 Binary Frameworks for Software Fingerprints
		2.6.1 BitBlaze
		2.6.2 BAP
		2.6.3 BinNavi
		2.6.4 iBinHunt
		2.6.5 BitShred
		2.6.6 BinSlayer
		2.6.7 BinJuice
		2.6.8 BinCoa
		2.6.9 BINSEC
		2.6.10 BinGraph
		2.6.11 MAYHEM
		2.6.12 Exposé
		2.6.13 REWARDS
		2.6.14 Helium
		2.6.15 Hercules
		2.6.16 Malheur
		2.6.17 MARD
		2.6.18 BinGold
		2.6.19 BinGo
		2.6.20 BinConvex
		2.6.21 BinCross
		2.6.22 BARF
		2.6.23 Aligot
		2.6.24 Howard
	2.7 Learned Lessons and Concluding Remarks
3 Compiler Provenance Attribution
	3.1 Introduction
		3.1.1 Objectives
		3.1.2 Motivating Example
		3.1.3 Approach Overview
	3.2 Compiler Provenance
		3.2.1 Tier 1: Compiler Family Identification
			3.2.1.1 Compiler Transformation Profile (CTP)
			3.2.1.2 Compiler Tags (CT)
			3.2.1.3 Detection Method
		3.2.2 Tier 2: Compiler Functions Labeling
			3.2.2.1 Compiler Functions (CF)
			3.2.2.2 Detection Method
		3.2.3 Tier 3: Version and Optimization Recognition
			3.2.3.1 Annotated Control Flow Graph (ACFG)
			3.2.3.2 ACFG Construction
			3.2.3.3 Compiler Constructor and Terminator (CCT)
			3.2.3.4 Detection Method
	3.3 ECP Approach
		3.3.1 ECP Overview
		3.3.2 Dataset Generation
		3.3.3 ECP Evaluation Results
		3.3.4 Discussion
	3.4 BinComp Evaluation
		3.4.1 Dataset Preparation
		3.4.2 Evaluation Results
		3.4.3 Comparison
	3.5 Limitations and Concluding Remarks
4 Library Function Identification
	4.1 Introduction
		4.1.1 Motivating Example
		4.1.2 Threat Model
		4.1.3 Approach Overview
	4.2 Feature Extraction
		4.2.1 Graph Feature Metrics
		4.2.2 Instruction-Level Features
		4.2.3 Statistical Features
		4.2.4 Function-Call Graph
		4.2.5 Feature Selection
			4.2.5.1 Feature Ranking
			4.2.5.2 Best Feature Selection
	4.3 Detection
		4.3.1 Bttree Data Structure
		4.3.2 Filtering
			4.3.2.1 Basic Blocks Filter
			4.3.2.2 Instruction Filter
	4.4 Evaluation
		4.4.1 Experimental Setup
		4.4.2 Dataset Preparation
		4.4.3 Function Identification Accuracy Results
		4.4.4 Impact of Compilers
		4.4.5 Impact of Feature Selection
		4.4.6 Impact of Filtering
		4.4.7 Scalability Study
	4.5 Limitations and Concluding Remarks
5 Identifying Reused Functions in Binary Code
	5.1 Existing Representations of Binary Code
		5.1.1 Control Flow Graph
		5.1.2 Register Flow Graph
		5.1.3 Function-Call Graph
	5.2 Reused Function Identification
		5.2.1 Overview
		5.2.2 Building SIG Blocks
			5.2.2.1 Information Control Flow Graph
			5.2.2.2 Merged Register Flow Graph
			5.2.2.3 Color Function-Call Graph
		5.2.3 SIG: Semantic Integrated Graph
		5.2.4 Graph Edit Distance
	5.3 Evaluation
		5.3.1 Dataset
		5.3.2 Accuracy Results of Sorting and Encryption Algorithms
		5.3.3 Impact of Compilers and Compilation Settings
		5.3.4 Impact of Obfuscation and Refactoring Techniques
	5.4 Limitations and Concluding Remarks
6 Function Fingerprinting
	6.1 Introduction
		6.1.1 Overview
		6.1.2 Threat Model
	6.2 Function Fingerprinting
		6.2.1 Feature Extraction
			6.2.1.1 Characterization of Function Prototype
			6.2.1.2 Composition of CFG Instructions
			6.2.1.3 Types of Function Calls
		6.2.2 Fingerprint Generation
			6.2.2.1 Disassembling and CFG Extraction
			6.2.2.2 Tracelet Generation
			6.2.2.3 Feature Extraction
			6.2.2.4 Signature Hashing
			6.2.2.5 Fingerprint Components
		6.2.3 Fingerprint Matching
			6.2.3.1 Fingerprint Candidate Selection
			6.2.3.2 Fingerprint Similarity Computation
	6.3 Evaluation
		6.3.1 Dataset Preparation
		6.3.2 Comparison with Existing Tools
		6.3.3 Function Reuse Detection
			6.3.3.1 Function Reuse Between Zlib Versions
			6.3.3.2 Function Reuse Between Libraries
		6.3.4 Scalability Evaluation
			6.3.4.1 Fingerprint Methodology Scalability
			6.3.4.2 Implementation Scalability
		6.3.5 Resilience to Different Compiler Optimization Levels
		6.3.6 Library Function Detection
		6.3.7 Malware Similarity Analysis
		6.3.8 Resilience to Obfuscation
	6.4 Limitations and Concluding Remarks
7 Free Open-Source Software Fingerprinting
	7.1 Introduction
		7.1.1 Approach Overview
		7.1.2 Threat Model
	7.2 Identifying FOSS Functions
		7.2.1 Normalization
		7.2.2 Feature Extraction
		7.2.3 Feature Analysis
		7.2.4 Feature Selection
		7.2.5 Detection Method
			7.2.5.1 Hidden Markov Model
			7.2.5.2 Neighborhood Hash Graph Kernel
			7.2.5.3 Z-score Calculation
			7.2.5.4 Bayesian Network Model
	7.3 Evaluation
		7.3.1 Experiment Setup
		7.3.2 Dataset Preparation
		7.3.3 Evaluation Metrics
		7.3.4 FOSSIL Accuracy
		7.3.5 Comparison
			7.3.5.1 Accuracy
			7.3.5.2 Performance
		7.3.6 Scalability Study
		7.3.7 The Confidence Estimation of a Bayesian Network
		7.3.8 The Impact of Evading Techniques
		7.3.9 The Impact of Compilers
		7.3.10 Applying FOSSIL to Real Malware Binaries
			7.3.10.1 Malware Dataset Analyzed by Technical Reports
			7.3.10.2 General Malware Dataset
	7.4 Limitations and Concluding Remarks
8 Clone Detection
	8.1 Introduction
		8.1.1 Motivating Example
		8.1.2 Overview
	8.2 Function Clone Detection
		8.2.1 Normalization
		8.2.2 Basic Block Comparison
		8.2.3 Fuzzy Matching Detection Engine
			8.2.3.1 Path Exploration
			8.2.3.2 Neighborhood Exploration
		8.2.4 Fingerprint-Based Detection Engine
	8.3 Evaluation
		8.3.1 Clone Detection
			8.3.1.1 Open-source Projects
			8.3.1.2 Dynamic Link Library Files
			8.3.1.3 Clone Detection Between Different Binaries
		8.3.2 Compiler Optimization
		8.3.3 Code Obfuscation
		8.3.4 Recovering Patch Information
		8.3.5 Searching Malware and Vulnerability Functions
		8.3.6 Comparison with Other Tools
	8.4 Limitations and Concluding Remarks
9 Authorship Attribution
	9.1 Approach Overview
	9.2 Authorship Attribution
		9.2.1 Filtering
		9.2.2 Canonicalization
		9.2.3 Choice Categorization
			9.2.3.1 General Choices
			9.2.3.2 Feature Vector of General Choices
			9.2.3.3 Qualitative Choices
				Example of Qualitative Choices:
			9.2.3.4 Feature Vector of Qualitative Choices
			9.2.3.5 Embedded Choices
			9.2.3.6 Feature Vector of Embedded Choices
			9.2.3.7 Structural Choices
			9.2.3.8 Feature Vector of Structural Choices
		9.2.4 Classification
	9.3 Evaluation
		9.3.1 Experimental Setup
		9.3.2 Dataset
		9.3.3 Evaluation Metrics
		9.3.4 Accuracy
		9.3.5 Scalability
		9.3.6 Impact of Code Transformation Techniques
		9.3.7 Impact of Obfuscation
		9.3.8 Impact of Compilers and Compilation Settings
		9.3.9 Applying BINAUTHOR to Real Malware Binaries
	9.4 Limitations and Concluding Remarks
10 Conclusion
References