Accurate Compiler andOptimization IndependentFunction Identification
Derrick McKee1,2, Nathan Burow2, Mathias Payer3
1. Purdue University

2. MIT Lincoln Laboratory

3. EPFLMotivation● Reverse engineering binaries is required for many purposes○ Malware analysis and family identification○ Library version and patch application○ Copyright violation detection● 105 new daily malware samples demands an automated solution2

Why is reverse engineering binaries difficult?
● No debug symbols or type information● Highly dependent on compilation environment○strlen assembly can change by up to 70%● Similar binary code implies function similarity, but dissimilar code does not
imply differences in function semantics

3

Existing Solutions● Static● Dynamic○ BinDiff - Control-flow Graph○ BLEX - Measured code

Isomorphism○ Asm2Vec - NLP embedding

feature vector○ IMF-SIM - Measured code
feature vector○ IDA - Proprietary function
signatures

All existing solutions measure code properties, which are fragile and highly variable.

4What is IOVec Function Identification?
● Semantic binary function identifier● Requires no source code● Sets of program state changes is the unique function fingerprint● Highly resistant to changes in compilation environment, purposefulobfuscation, and architecture changes

IOVFI uses program state changes to identify functions in stripped binaries.

5Input/Output Vectors (IOVecs)● Stores an initial program state, and an expected program state afterfunction execution● A function “accepts” an IOVec if it executes to completion starting with theinitial state, and the resulting program state matches the expectedprogram state● The set of accepted IOVecs is the function signatureIOVecs store program state transformations largely preserved by all compilers.

6IOVec Function Identification

IOVec

int my_func(int a, int b, int* c) {*c = a / b;
return 0;}

Arg 0: ℤ
Arg 1: ℤ - {0}Arg 2: Any valid address
Memory: Any value
Input Program State

Return: 0
Syscalls: None
Memory: Value at ccontains a / b
Expected Program State7

IOVFI Training Phase● IOVFI utilizes a guided mutational fuzzer to discover IOVec sets for eachfunction in a binary● Each function is given every generated IOVec● A binary tree is generated with functions on leaves, and IOVecs asinternal nodes● Function identification involves traversing the binary tree

IOVFI classifies functions by creating a searchable binary tree of IOVecs.

8

IO
Vecs

IOVFI Binary Tree Example

Known

Unknown
9

IOVFI Experimental Setup●We compile coreutils using Clang and GCC at -O{0,1,2,3}●We generate a binary tree from wc, realpath, and uniq

●We identify functions in du, dir, ls, ptx, sort, true, logname, whoami, uname, and dirname●We report F-Score, the harmonic mean of precision and recall

10Comparison with BinDiff 6
Evaluation
Compilation
Environment

Binary Tree
Compilation
Environment

IOVFI
F-ScoreO0
Clang

Improvement
over BinDiff

GCC

Clang

.856

24%

.836

53%

GCC

.823

48%

.838

22%

Clang

.735

87%

.734

99%

GCC

.695

67%

.690

68%

Clang.696

122%

.686

140%

GCC

.674

100%

.659

133%

Clang.692

132%

.689

140%

GCC

.755

139%

.748

201%

O0O2

Widening Accuracy GapO1O311

Comparison with Asm2Vec

Evaluation
Compilation
Environment

Binary Tree
CompilationEnvironment

Asm2Vec
F-ScoreIOVFIF-Score

O0
Clang

GCC

Clang

.952

.856

.224

.836

GCC.296

.823

.951

.838

Clang.0656

.692

.0370

.689

GCC.0519

.755

.0108

.748

O0O3

12

Large Binary Accuracy

O1
Clang

O3
GCC

Clang

GCC

libz

.717

.850

.765

.772

libpng

.633

.695

.629

.639

libxml2.699

.802

.700

.733

13

Cross Architecture Accuracy

O0
Clang

O3
GCC

Clang

GCC

wc

.835

.805

.795

.860

realpath.820.803

.737

.842

uniq.880

.866

.796

.877

14

Conclusion● IOVFI semantically identifies functions in binaries● Uses program state transformations as function fingerprints● Resilient to broad changes in compilation environments and architecture,a first-in-class feature● Source available at https://github.com/HexHive/IOVFIEmail: derrick@geth.systems
Twitter: @unbound_brewer