# SemDiff: Binary Similarity Detection by Diffing Key-Semantics Graphs

Zian Liu<EMAIL_ADDRESS>Swinburne University of Technology &
Data 61 ,  Zhi Zhang<EMAIL_ADDRESS>University of Western Australia ,
Siqi Ma<EMAIL_ADDRESS>University of New South Wales ,  Dongxi Liu
<EMAIL_ADDRESS>Data 61, CSIRO ,  Jun Zhang<EMAIL_ADDRESS>Swinburne University of Technology ,  Chao Chen<EMAIL_ADDRESS>Royal
Melbourne Institution of Technology ,  Shigang Liu<EMAIL_ADDRESS>Swinburne University of Technology ,  Muhammad Ejaz Ahmed
<EMAIL_ADDRESS>Data 61, CSIRO and  Yang Xiang<EMAIL_ADDRESS>Swinburne University of Technology

###### Abstract.

Binary similarity detection is a critical technique that has been applied in
many real-world scenarios where source code is not available, e.g., bug
search, malware analysis, and code plagiarism detection. Existing works are
_ineffective_ in detecting similar binaries in cases where different compiling
optimizations, compilers, source code versions, or obfuscation are deployed.

We observe that all the cases do not change a binary’s key code behaviors
although they significantly modify its syntax and structure. With this key
observation, we extract a set of _key_ instructions from a binary to capture
its key code behaviors. By detecting the similarity between two binaries’ key
instructions, we can address well the ineffectiveness limitation of existing
works. Specifically, we translate each extracted key instruction into a self-
defined key expression, generating a key-semantics graph based on the binary’s
control flow. Each node in the key-semantics graph denotes a key instruction,
and the node attribute is the key expression. To quantify the similarity
between two given key-semantics graphs, we first serialize each graph into a
sequence of key expressions by topological sort. Then, we tokenize and
concatenate key expressions to generate token lists. We calculate the
locality-sensitive hash value for all token lists and quantify their
similarity. Our evaluation results show that overall, SemDiff outperforms
state-of-the-art tools when detecting the similarity of binaries generated
from different optimization levels, compilers, and obfuscations. SemDiff is
also effective for library version search and finding similar vulnerabilities
in firmware.

##  1\. Introduction

Binary code similarity detection (also known as binary diffing) is important
for bug search, patch generation and analysis, malware detection, and
plagiarism detection (Haq and Caballero, 2021). Existing works can be
categorized into machine-learning-based approaches or program-analysis-based
approaches.

Machine learning based approaches either capture syntactic, structural, and
semantic features from binary code to train a similarity detection model (Xu
et al., 2017b; Liu et al., 2018; Gao et al., 2018) or leverage natural
language processing (NLP) (Ding et al., 2019; Duan et al., 2020) to learn
semantic information. Although such machine-learning-based approaches are
theoretically effective, the performance highly relies on how well the
training data is created. Real-world binaries are diverse, that is, the same
piece of source code could be compiled into different pieces of binaries
because of using different compilers (optimization levels) (Duan et al.,
2020). It is thus difficult to build a representative dataset for training. If
the training data are not well established, the corresponding approaches will
be affected significantly. Unsupervised learning automatically learns each
instruction embeddings from its context instructions. However, optimizations
or different compilers can make changes to a non-trivial part of the function,
rendering this method less accurate.

Program analysis approaches generally execute static/dynamic analysis to
extract information (e.g., data/control dependencies) from the binaries and
then quantify similarity based on certain defined rules (Ming et al., 2017;
Wang and Wu, 2017; Luo et al., 2014). However, static function-level
processing approaches match a sequence of blocks or instructions, which
defines each basic block or each instruction within a function as the smallest
unit of similarity quantification. Considering the case of using different
compiling optimization to proceed with the same source code, the basic block
of each function will become totally different through block splitting,
instructions can be different due to instruction substitution. Therefore,
block or instruction comparison is not the ideal approach to handle binary
similarity comparison(Ren et al., 2021).

To resolve the above limitations, we propose and implement a novel semantic-
aware approach, SemDiff, to compare arbitrary binary codes without considering
which compilers and optimization levels the developers utilized. Specifically,
SemDiff consists of two modules, _Graph Generation_ and _Graph Diffing_. In
graph generation, SemDiff takes as input of a pair of binary functions and
then constructs a key-semantics graph for each function by 1) identifying the
key instructions that reflect major function behaviors (e.g., invoking
functions, assigning value); 2) applying symbolic execution to extract
symbolic expressions of each instruction and instruction dependencies; 3)
translating symbolic expressions into self-defined key expressions and using
directed edges to connect all the correlated instructions. After having a pair
of key-semantic graphs of the two binary functions, graph diffing takes the
graphs as input and leverages topological sort to serialize both graphs into
two sequences. It then tokenizes each sequence and executes locality-sensitive
hash (LSH)-based comparison to calculate an LSH value for each key-semantics
graph. Two graphs (i.e., binary functions) are regarded as similar if their
LSH values are similar

We evaluated the binary similarity performance of SemDiff by using 9
libraries, i.e., openssl, libtomcrypt, coreutils, ImageMagick, libgmp, curl,
sqlite3, zlib and Puttygen, and compare it with five state-of-the-art tools,
i.e., Bindiff (Flake, 2004), funtionsimsearch (Dullien, 2018), Asm2Vec (Ding
et al., 2019), Gemini (Xu et al., 2017b), and Palmtree (Li et al., 2021). The
results demonstrated that SemDiff on average outperforms baseline tools no
matter whether the source code is compiled by the same compiler (with
different optimization levels) or the same optimization levels (with different
compilers). The out-performance of SemDiff is because of the semantic-
preserving key expressions and effective LSH-based graph diffing. In addition,
we applied SemDiff to conduct vulnerability detection and library version
check and found that SemDiff could significantly improve the performance of
such similarity-dependent detection.

Summary of Contributions: We summarize our major contributions as follows:

  * •

We proposed a novel semantic-aware approach for binary similarity detection.
We abstract binary code by selecting the key instructions only and then
executing symbolic execution to extract the instruction correlations for
further analysis. The approach efficiently simplifies binary code by
preserving the most essential instructions and their corresponding semantic
information.

  * •

We proposed an approach to translate the instruction summary into a graph. To
achieve an accurate comparison, we propose an LSH-based approach to convert a
graph into a sequence for the final similarity calculation. Such an approach
could be applied to various scenarios (e.g., vulnerability searching, and
malware detection).

  * •

We assessed the performance of SemDiff by using 9 popular libraries and also
compared the detection results with the state-of-the-art tools. The results
demonstrated that SemDiff not only outperformed in binary similarity detection
but also can be utilized to assist the other tools that require binary
comparison.

  * •

We currently published our tool, SemDiff, and the experimental data to our
repository
https://anonymous.4open.science/r/SemDiff4BinaryDetection-F12C/README.md for
reviewers to check and test. After this paper is accepted, the tool and
dataset will be published.

Note that binary code in this paper represents the assembly code compiled by
compilers.

Figure 1. Due to compiling optimization, a binary snippet on the left is
obviously different in syntax and code structure from the one on the right,
although they are from the same source code (on the top).

##  2\. Background

###  2.1. Motivation

We demonstrate a code compilation example in Figure 1 to represent the binary
diversity and how a compiling optimization changes a control-flow-graph (CFG).
Specifically, a non-optimized binary snippet (on the left) has a conditional
branch (jle .L2) with two destinations, i.e., mov ecx, 1 and mov ecx, 0. An
optimized snippet (on the right) substitutes the three instructions with sbb.
Although both snippets are from the same source code, they have different
syntax and structures. The performance of supervised learning heavily depends
on the training data. Therefore, supervised learning approaches (Ding et al.,
2016; Xu et al., 2017b; Feng et al., 2016; Gao et al., 2018) will be
ineffective for binaries compiled with unseen optimizations or compilers.
Unsupervised learning automatically learns instruction embeddings from
contexts. Therefore, if a non-trivial part of the context is different due to
optimizations or different compilers, this approach (Duan et al., 2020; Ding
et al., 2019) will be less accurate. Some program-analysis-based methods
compare similarity at the granularity of basic blocks. However, as in the
example, the blocks are merged after optimization. Thus methods based on
basic-block level (Luo et al., 2014; Chandramohan et al., 2016; Flake, 2004)
comparison can be ineffective for optimizations. Some program-analysis-based
methods utilize Longest Common Sequence (LCS) to align two sequences of
instructions or blocks from the two functions. However, optimization as shown
in the example can change the instruction or basic block or their ordering,
thus posing challenges to sequence aligning-based approaches (Ming et al.,
2017; Wang and Wu, 2017; Luo et al., 2014).

###  2.2. Preliminary

In this section, we first present our goal and then give our assumptions of
SemDiff.

Our goal:  Detecting binary similarity can be conducted at different
granularity, i.e., basic block, function, or inter-procedure CFG. A basic-
block level quantifies the similarity between two given basic blocks. A
function level quantifies the similarity between two given functions. An
inter-procedure CFG quantifies two graphs of basic blocks connected across
multiple functions following the control flow of a binary. Given that it is
critical to find vulnerabilities in similar functions in the real world (Gao
et al., 2018; Chandramohan et al., 2016; Feng et al., 2016), our goal is to
effectively detect binary similarity at a function level, the same as (Ding et
al., 2019; Flake, 2004; Dullien, 2018; Ding et al., 2016; Luo et al., 2014).
As mentioned in Section 1, binary similarity detection includes machine-
learning and program-analysis approaches. In this paper, we use the program-
analysis approach to compare binary similarity.

Our Assumptions:

Similar to previous works (Ding et al., 2019; Duan et al., 2020; Zuo et al.,
2022; Ming et al., 2017), we make three assumptions that are practical in the
real world. First, binaries are stripped without debugging information, as a
stripped binary is released as a software product in the real world to protect
its intellectual property. Second, binaries can be obfuscated, which is often
used to make real binary code difficult to understand. Third, binaries are
assumed to be unpacked, as binary unpacking is an orthogonal problem and can
be solved by prior works (Cheng et al., 2018; Roundy and Miller, 2013).

###  2.3. Challenge

To compute the similarity of the two binaries precisely, the following
challenges need to be resolved.

Challenge I: Extract Core Semantics. The syntax of the binary code varies when
compiling the same source code with different compilers or optimizations.
Extracting equivalent semantics from those two syntactically different
programs is challenging. Existing solutions typically compare symbolic
expressions after translating the binary into higher-level Intermediate
Representations (IR) (Chandramohan et al., 2016; Luo et al., 2014). However,
these IRs do not simplify the binary code. On the contrary, their grammar
makes IR even more complex than binary code because they tend to translate one
binary instruction to multiple IR instructions. Moreover, even translating to
IR, IR still contains unmatched variables due to different compilers or
optimizations. Therefore, comparing symbolic expressions of IR still cannot
accurately identify semantic equivalence. Also, each binary instruction
corresponds to at least one IR instruction. Therefore, a representation of the
binary code that can both preserve semantics and simplify binary code is
required.

Challenge II: Symbolic Formula Too Long. Instead of processing simple text-
based analysis, many approaches (Ding et al., 2019; Gao et al., 2018; Zuo et
al., 2022; Xu et al., 2017b) study the code similarities through semantic
graph comparison. They extract graphs (e.g., control flow graphs, call graphs)
and convert the graphs into vectors. Through machine learning algorithms, the
binary code snippets with similar vectors will be identified. However, these
approaches are not applicable. Specifically, those approaches regard each
binary instruction as a vector of a fixed size, as different binary
instruction generally are short (e.g., one operator with one or two operands)
and has similar lengths. In reality, such a fixed size requirement is not
applicable to our case, as our designed key expression might contain the
semantics of multiple lines of instructions, thus can have extremely long
expression, and the expression length can vary enormously. Instead, we adopt a
locality-Sensitive hash (LSH) based approach to compute a hash value for all
the nodes in the graph and further compare the hash values to calculate the
similarity. LSH algorithm is able to represent high-dimensional data with low-
dimensional data while preserving the relative distance among data.

Challenge III: Inefficient and Inaccurate Sequence Comparison To compare the
function similarity, many works adopt a divide-and-conquer algorithm: longest
common sequence (LCS) (Ming et al., 2017; Wang and Wu, 2017; Luo et al.,
2014). In LCS, each function is treated as a sequence of instructions or
blocks. At the lowest level, it compares one instruction with another
instruction or one block with another block. However, the comparison strategy
at the lowest level is to be defined by us (i.e., how to compare the
similarity between two instructions or two blocks). Therefore, human experts
need to inspect the binary code and conclude rules for comparison. The
accuracy heavily depends on the quality of the set comparison rules. Also, it
is time-consuming for human to propose rules, making this approach unscalable.
Moreover, LCS is NP-hard, the running time cost is significant. Nonetheless,
these approaches cannot process the graph of binary codes efficiently.

###  2.4. Solution

Regarding the challenges to binary comparison, we propose the following
approaches.

Respond to challenge 1, we propose a symbolic-based binary translation
approach to abstract key instructions from each binary and generate semantic-
aware representatives for further comparison. After observing the binary codes
generated from the same high-level source code, we found that instructions can
be classified into _key instructions_ and _non-key instructions_. In
particular, key instructions represent the major function executions and
parameter value transmission and non-key instructions are the instructions for
preprocessing purposes such as address computation.

Through our manual inspection, we classified the key instructions into four
types, _calling behavior_ , _comparing manner_ , _indirect branch_ , and
_memory store_.

  * •

Calling behavior. It represents a calling instruction that takes operands
operated by previous instructions as function arguments.

  * •

Comparing manner. It is an instruction with operands of comparing objectives.
The instruction with the operator such as cmp, test will affect which
subsequent branches to execute at a joint point.

  * •

Indirect branch. It represents an instruction with an operand of a target
address (e.g., jmp eax).

  * •

Memory store. It is an instruction with the operand that stores values or
memory addresses (e.g., mov [edx], ebx).

Key Instruction | Key Expression
---|---
calling behavior | $RET\\_FuncAddr(exp_{1},...,exp_{n})$
comparing manner | $exp_{1}\;cmp\;exp_{2}$
indirect branch | $branch\;exp$
memory store | $[exp_{1}]\;=\;exp_{2}$
Table 1. Key instructions and their corresponding key expressions.

Therefore, we further define four types of _key expressions_ corresponding to
the types of key instructions, shown in Table 1. For the key expression of a
calling behavior, $RET$ denotes a call instruction. $FuncAddr$ is the starting
address of a function, and $exp_{i}$ ($i\in\\{1,...,n\\}$) is the symbolic
expression of the function arguments. For the key expression of a comparing
manner, $cmp$ denotes a comparing instruction. $exp_{1}$ and $exp_{2}$ are two
operands used for comparison. For the key expression of an indirect branch,
$branch$ denotes a branching instruction and $exp$ refers to the symbolic
expression of the branch destination. For the key expression of a memory
store, $exp_{2}$ is written into the memory address denoted by $exp_{1}$.
According to the defined key expressions, we first symbolically execute the
binary to derive each instruction’s each operand’s symbolic expression and
then translate each marked key instruction into specific key expressions (see
Section 3.2 for details).

To address challenges 2 to 3, we utilize the LSH algorithm. Specifically,
given the abstracted binary with key expressions, we raise an LSH-hash-based
comparison to compute the similarity of the two abstracted assemblies.
Specifically, we first build a _key-semantics graph_ , which summary the major
behavior of each function. Referring to node correlations demonstrated in the
graph, we topologically sort all nodes and use LSH hashing to hash each graph
into an LSH value. By comparing the LSH values of the two graphs, we can
finally speculate the similarity between the two graphs.

##  3\. SemDiff

Figure 2. SemDiff Overview. SemDiff consists of two modules, i.e., graph
generation and graph diffing. (LSH is short for Locality-Sensitive Hash.)

###  3.1. Overview

For two binary candidates, e.g., BinA and BinB, each has a set of functions,
that is, $\\{FuncA_{1},...,FuncA_{n}\\}$ and $\\{FuncB_{1},...,FuncB_{m}\\}$.
To detect binary similarity at function level, we select a pair of $FuncA_{i}$
($i\in\\{1,...,n\\}$) and $FuncB_{j}$ ($j\in\\{1,...,m\\}$) from BinA and
BinB, and feed them into SemDiff for similarity quantification. SemDiff
consists of two modules, i.e., graph generation and graph diffing, which work
as follows:

  * •

Graph Generation. It contains three major steps. First, we leverage customized
symbolic execution to extract symbolic expressions of key instructions from a
given function. Second, we translate the extracted symbolic expressions into
key expressions. Last, we generate a graph preserving the key semantics of a
function by connecting the translated key expression to the function’s control
flow.

  * •

Graph Diffing. It has four major steps. First, we serialize a key-semantics
graph into a sequence of key expressions by topological sort. Second, we
tokenize each key expression to produce a list of token sequences. Third, we
concatenate all the token sequences for all the key expressions and use the
locality-sensitive hash (LSH) to hash the concatenated tokens and generate an
LSH hash value for one function. Last, we diff two given functions by
quantifying the Jaccard similarity between two generated LSH hash values.

By doing so, a similarity score will be computed for the selected pair of
functions. For each function in BinA, we do a 1-to-n compare with all the
functions in BinB and pick a pair of functions that has the highest score as
the most similar one. If the picked pair has the same function name, it means
that we detect the correct pair.

###  3.2. Graph Generation

####  3.2.1. Key-Instruction Symbolic Expression Extraction

To efficiently extract all symbolic expressions of key instructions from a
given function, we customize symbolic execution by proposing two techniques.
First, we symbolically execute a function to traverse all its instructions.
Second, we symbolically execute a loop in a lightweight way rather than
repeatedly executing the loop till the loop condition is not satisfied.

Traversing All Instructions in A Function:  For a given function in a binary,
we perform a complete instruction traversal as shown in algorithm 1. The input
for the algorithm is a function’s first instruction. The function is regarded
as a control-flow graph where a node denotes an instruction and children of
the node are subsequent instructions conforming to the function’s control
flow. At the beginning of the algorithm, we also need to provide symbolic
values to the function’s input arguments. Particularly, we assign symbolic
values $VAR_{i}$ ($i\in N$) to relevant registers. The order for assigning
values for the registers is based on the x86-64 calling conventions. For
example, on x64 Linux, register rdi,rsi, rdx, rcx represents arguments 1 to 4
of the function.

The algorithm 1 implements a depth-first searching function, i.e.,
execute_next_node. which achieves a complete instruction coverage rather than
a complete code path to avoid the serious path-explosion problem.
Specifically, we first check whether a node has been executed before (Line 2).
If no, we symbolically execute the node (Line 3). As an instruction in a node
can have one or more operands, each of its operands will produce a symbolic
expression after the symbolic execution. Thus, we maintain a record of
symbolic expressions for each operand in each instruction. If the data to be
referenced is resolvable (e.g., mov esi, address where address points to a
string of ‘‘Rtmin’’), we use its resolved value (‘‘Rtmin’’) to continue the
symbolic execution. If data is unresolvable (e.g., mov edi, cs:bio_err where
cs:bio_err is unknown), we assign unused $VAR_{i}$ ($i\in N$) to represent
unknown values.

If the node has been executed before, we check whether the node is the start
of a loop (Line 8). If yes, we process the loop in a lightweight way, i.e.,
$lightweight\\_loop\\_processing()$ shown in Line 10 and discussed in
Lightweight Loop Processing later. If the node has been executed before but
does not form a loop, we simply return (Line 11) to avoid repeated node
execution.

1 Function  _execute_next_node(_$Node$_)_:

2

3 if  _Node has not been executed before_ then

4 $symbolic\\_execution(Node)$

// symbolically execute the instruction and update relevant records of
symbolic expressions.

5 foreach  _$j\in Node.children$_ do

6 $execute\\_next\\_node(j)$

7 end foreach

8

9 end if

10 else if  _$Node$ forms a loop_ then

11

12 $loop=extract\\_loop(Node)$

13 $lightweight\\_loop\\_processing(loop)$

14 end if

15

16

17

Algorithm 1 Complete Instruction Traversal

Lightweight Loop Processing:  In the symbolic execution above, it is
inefficient to execute a loop as the loop can be repeated many times or even
infinite. Instead, we propose a lightweight approach. Considering that a loop
updates one or more variables each time (e.g., adding or subtracting a counter
value), we call such a variable a _loop counter_. When we encounter a loop, we
execute the loop only two times. If there are branches within the loop, we
randomly select one branch at the first time of loop execution. In the second
time loop execution, we follow the same path. For example, in Figure 3, there
is more than one branch in the loop. In the first time of execution, we
randomly select a path ${.L1-.L3-.L4}$. We execute ${.L1-.L3-.L4}$ and their
symbolic expressions are denoted in Figure 3 after each 1st: symbol. If there
is more than one operand, the symbolic expressions of the operands are
separated by a comma. For example, 1st: 3,3 at line 5 in $L3$ means that,
after the symbolic execution, the first operand’s symbolic expression is 3,
and the second operand’s symbolic expression is also 3. In the second time
execution, we follow the same path. Their symbolic expressions are denoted
after each 2nd: symbol. We then compare each operand’s symbolic expression
after the first and second execution to detect operands with changed symbolic
expressions. We add a symbol ITER as the prefix to it, meaning it is a loop
counter. For example, in Figure 3, we identify eax in lines 7 and 8 as loop
counter because the first time the symbolic expression of eax is VAR0 and the
second time the symbolic expression of eax is VAR0+1. This means this variable
increase by 1 in each iteration. Therefore, we change eax’s symbolic
expression to ITER(VAR0).

Figure 3. An example of a loop.

####  3.2.2. Key Expressions Translation

As symbolic Expressions of Key Instructions have been extracted, they can be
complicated and still have many syntactic differences due to compiling
techniques such as data encoding (Nagra and Collberg, 2009) and Mixed-Boolean-
Arithmetic (Zhou et al., 2007). As such, we further translate them into key
expressions in two steps. First, we use expression-synthesizing techniques
(David et al., 2020; Saıdi et al., 2010; Kan et al., 2019) to synthesize a
symbolic expression into a simplified one, e.g., $x\lor y-x\land y\Rightarrow
x\bigoplus y$. This technique can effectively transform long and complex
symbolic expressions into simpler and shorter expressions. Second, we
translate each key instruction to key expression according to the rules as
shown in Table 1.

####  3.2.3. Generating A Key-Semantics Graph

Key-Instruction Type | Key Expression | A List of Token Sequences
---|---|---
calling behavior | $RET\\_FuncAddr(exp\\_1,...,exp\\_n)$ | $RET\\_(exp\\_1\\_token\\_1),...,RET\\_(exp\\_1\\_token\\_n),...;$
$RET\\_(exp\\_n\\_token\\_1),...,RET\\_(exp\\_n\\_token\\_n)$
comparing manner | $exp\\_1\;cmp\;exp\\_2$ |  $cmp\;exp\\_1\\_token\\_1,...,cmp\;exp\\_1\\_token\\_n,...$;
$cmp\;exp\\_2\\_token1,...,cmp\;exp\\_2\\_token\\_n$
indirect branch | $branch\;exp$ | $branch\;exp\\_token\\_1,...,branch\;exp\\_token\\_n$
memory store | $[exp\\_1]\;=\;exp\\_2$ | $[exp\\_1\\_token\\_1]=,...[exp\\_1\\_token\\_n]=;$
$=exp\\_2\\_token\\_1,...,=exp\\_2\\_token\\_n$
Table 2. Key expression tokenization.

Key instructions in a function have been turned into key expressions. However,
until now, the key instructions are still an unsorted list, as highlighted in
red rectangles in Figure 4. Now we connect the key expressions based on a
function’s control flow to produce a key-semantics graph. Each node in the
key-semantic graph represents a key instruction, represented as a vertex
$V=\\{V_{1},...,V_{n}\\}$ in the key-semantics graph. The vertex attribute
$Attr_{i}$ ($i\in\\{1,...,n\\}$) is its key expression. The edges
$E=\\{(i,j)\mid i,j\in V^{2}\\}$ in the graph represent the control-flow among
key instructions.

For example, Figure 4 shows how graph generation processes a pair of binary
functions compiled from the same source code with and without optimization.
Specifically, it first extracts symbolic expressions of key instructions from
a given binary function and then translates the extracted expressions into key
expressions. Last, it connects the key expressions based on the function’s
control flow to generate a key-semantics graph.

Figure 4. An example of (key-semantics) graph generation and graph diffing.
FuncA and FuncB are compiled from the same source code without and with
optimizations.

###  3.3. Graph Diffing

To quantify the similarity between the two given graphs, existing approaches
vectorize the attribute of each node. Thus, this requires the attributes must
be short symbols. However, the attributes of our key-semantic graph can be
long expressions, making existing approaches inapplicable.

Inspired by (Yamaguchi et al., 2012; Lin et al., 2019) where source codes are
transformed into a sequence of instructions to traverse an Abstract Syntax
Tree in a linear order, we address the problem in three steps. 1) We serialize
a key-semantics graph into a sequence of nodes by _topological sort_. 2) We
tokenize the key expressions (i.e., each node attribute in the serialized
graph). 3) We concatenate the tokenized key expressions and apply _locality-
sensitive hash_ (LSH) to produce an LSH value for similarity quantification.

####  3.3.1. Key-Expression Sequences serialization

The technique of topological sort can sort all the nodes
$V=\\{V_{1},...,V_{n}\\}$ of a directed graph $G=(V,E)$ in a linear order and
thus $G$ satisfies the following property: every directed edge
$\\{(V_{u},V_{v})\mid V_{u},V_{v}\in V^{2}\\}$ is forward, i.e., $V_{u}$ comes
before $V_{v}$. More specifically, topological sort can keep the structural
and geometrical relations among the nodes. Similar graphs can result in
similar topological sequences.

However, it is possible that a loop in the function contains multiple key
instructions. Therefore, graph generation step can produce loops in key-
semantics graph. And topological sort works only for a directed graph that has
no loop, which cannot be directly applied to a key-semantics graph that can
contain loops. To address this issue, we first make a key-semantics graph
loop-free by removing the last edge in the flow of a loop and then adding a
symbol of $WHILE$ into the starting node of the loop, meaning it is the
beginning of the loop. As shown in Figure 3, $.L4$ to $.L1$ is the last edge
of the flow and is removed. The nodes in the loop body are retained.

####  3.3.2. Key-Expressions Tokenization

For each node attribute in the serialized graph, we split its key expression
into operands and operators, constituting a sequence of tokens, e.g.,
${X+3-Y+7*Z}$ is spit and tokenized into a sequence of ${X,3,-,7,*,Z}$. If a
key expression has brackets or parentheses, we retain the brackets or
parentheses for each token when splitting it, e.g., parts of two key
expressions are $[X+[Y+Z-3]*2]$ and $(X+(Y*6+(Z-3+K)))$. They are tokenized
as: $[X],[[Y]],[[Z]],[[-]],[[3]],[*],[2]$ and
$(X),((Y)),((*)),((6)),(((Z))),(((-))),(((3)))(((K)))$. We note that the plus
symbol (${+}$) in a key expression is omitted when it is split, as we observe
that a tokenized plus symbol dominates a token sequence, which makes two
different token sequences have a high similarity score. To associate a token
with its corresponding key-expression type, we prefix a token with a symbol as
shown in Table 2.

  * •

For a calling behavior, each token is prefixed with $RET\\_()$, denoting that
it comes from a calling instruction, e.g., a key expression is
$RET\\_(3,VAR0+4)$ becomes $RET\\_(3),RET\\_(VAR0),RET(4)$.

  * •

For a comparing manner, each token is prefixed with $cmp$, e.g., a key
expression $4\;cmp\;[VAR1+18]$ turn into $cmp\;4$, $cmp\;[VAR1]$, $cmp\;[18]$.

  * •

For an indirect branch, each token is prefixed with $branch$, e.g.,
$branch\;[[VAR2+10]+16]$ turns into $branch\;[[VAR2]]$, $branch\;[[10]]$,
$branch\;[16]$.

  * •

For a memory store, tokens on the left of equal sign ends with ${=}$, tokens
on the right of the equal sign prefixed with ${=}$, e.g.,
$[VAR2+18]=(VAR1+10)*3$ becomes $[VAR2]=,[18]=,=(VAR1),=(10),=*,=3$.

####  3.3.3. LSH Values Hashing and Quantifying Similarity

The LSH approach is effective for nearest neighbor search in high-dimensional
spaces as LSH can represent high-dimensional data in a low-dimension format
while preserving the relative distance between data. Particularly, this
approach hashes data objects into buckets so that similar objects will be
hashed into the same bucket with a high probability. As such, we utilize LSH
to generate an LSH value for a serialized and tokenized key-semantics graph.
Specifically, we first concatenate all the token sequences from all the key
expressions in a serialized key-semantics graph. We then generate an LSH value
for the concatenated token sequence to represent one function. With two LSH
values from two given functions, we use the _Jaccard similarity_ to quantify
the similarity between the two functions, as the Jaccard similarity shown
below is commonly used to measure similarity or distance for two given
datasets.

$J(A,B)=\dfrac{\left|A\cap B\right|}{\left|A\cup B\right|},$

where $A$ and $B$ are two datasets, and the number of the common elements in
them is divided by their total number.

Figure 4 shows an example of how graph diffing operates. It first serializes
two given key-semantics graphs and then tokenizes the key expressions, which
are concatenated to generate a token list. Last, it computes LSH values for
token lists from each binary function and quantifies their similarity.

Source Lines of Code:  Our implementation for the first module contains 12,527
C++ SLOC and it serves as a plugin to IDA Pro. The second module has 2,913
python SLOC. We use APIs provided by
msynth111https://github.com/mrphrazer/msynth as a python package to synthesize
symbolic expressions of key instructions.

##  4\. Evaluation

We evaluated the effectiveness of SemDiff answering the following research
questions (RQs):

  * •

RQ1. What is the accuracy of the generated key expressions?

  * •

RQ2. Can SemDiff detect similarity across different compiling optimizations,
compilers, and obfuscations?

  * •

RQ3. Can SemDiff be applied to real-world applications?

###  4.1. Experiment Setup

Dataset We conducted experiments on nine popular open-source projects, i.e.,
openssl-3.3.0, libtomcrypt-1.18.2, coreutils-8.32, ImageMagick-7.1.010,
libgmp-6.2.1, curl-7.80, sqlite3-3.37.0, zlib-1.2.11 and Puttygen-0.74. From
these libraries, we selected 13 programs (listed in Table 4) that are widely
used by vendors and the other researchers (Ding et al., 2019; Wang and Wu,
2017; Mengin and Rossi, 2021).

Environment We set up a machine with an Intel NUC8i5BEH (Intel processor
i5-8259U with 16 GB memory). Since the experiment might involve deep learning,
we also use an accelerator cluster of HPC systems with 456 NVidia Tesla P100,
114 Dual Xeon 14-core E5-2690 v4 compute nodes and 256 GB memory.

Experiment We compare SemDiff with five state-of-the-art tools of binary
similarity detection (i.e., BinDiff (Flake, 2004), functionsimsearch (Dullien,
2018), Asm2Vec (Ding et al., 2019), Gemini (Xu et al., 2017b), and Palmtree
(Li et al., 2021)). We run Gemini and Palmtree on the HPC and other tools on
an Intel NUC. For BinDiff, we utilize the function level features to achieve
similarity comparison. functionsimsearch, Gemini, and Palmtree are machine
learning based approaches. Hence, we leverage a total of 12 binaries from four
programs (i.e., busybox, coreutils, libgmp, and libMagickCore) compiled with
different optimization levels for model training. Aligned with existing works
(Ding et al., 2019; Eschweiler et al., 2016; Feng et al., 2016), we consider
functions with at least five basic blocks as functions with less than 5 blocks
are less likely to contain bugs, and thus are of less interest for similarity
detection.

Similarity Measurement Given a pair of binary codes (i.e., BinA and BinB)
compiled by different optimization levels, we compute the similarity score as
below. First, we select a function from BinA and execute a binary similarity
detection tool to acquire a similarity score between the selected function and
each function in BinB. The pair of functions with the largest score is
regarded as the most similar function. Then we enable the debugging
information of the function based on the function name to check whether
functions in BinB and BinA are the same. To quantify the similarity, we use
the same metrics as the previous works (Ding et al., 2019; Ren et al., 2021).
That is precision at position 1 (precision@1), which captures the ratio of
binary functions from BinA that correctly find the function with the same name
in BinB at position 1. Precision@1 is equal to Recall at Position 1 (Recall@1)
in this case.

Please note that in the following sections, we use the aforementioned program
versions for evaluation. For Section 4.4.1, we use the aforementioned program
version as the baseline and compared them with other versions in terms of
their binary similarity, e.g., curl-3.3.0 is against curl-7.43, curl-7.65 and
curl-7.72.

###  4.2. RQ1: Correctness of Key Expressions

Project | Functions (#) | Project | Functions (#)
---|---|---|---
Coreutils-O0 | 25 | Curl-O1 | 30
Coreutils-O3 | 20 | libgmp-Os | 31
Coreutils-Os | 27 | libmagickcore-o1 | 24
libtomcrypt-O1 | 23 | libmagickcore-o2 | 20

Table 3. Statistics of the analyzed functions.We randomly selected 200
functions in total from various projects with different optimization levels.

To justify the correctness of the translated key expressions, we randomly
selected 200 functions from the dataset described in Section 4.1 and asked
three experienced programmers to label them manually. The 200 functions are
shown in Table 3. It demonstrated that SemDiff can correctly translate 85% of
instructions. By manually inspecting the incorrect cases, we observed that
SemDiff cannot recognize (currently not supported) some x64 mnemonics’
variants (e.g., movzx) that are less frequently used in binary codes. As
SemDiff is built on top of IDA pro to resolve string variable names into
contents of the string, IDA pro might mistakenly resolve the strings. For
example, IDA pro may consider constant value as a memory address and resolve
the content in that memory address.

Program | BinDiff | funcsimsrch | Asm2Vec | Gemini | Palmtree | SemDiff
---|---|---|---|---|---|---
O1-O0 O3-O0 Os-O0 | O1-O0 O3-O0 Os-O0 | O1-O0 O3-O0 Os-O0 | O1-O0 O3-O0 Os-O0 | O1-O0 O3-O0 Os-O0 | O1-O0 O3-O0 Os-O0
openssl | (0.459, 0.321, 0.319) | (0.091, 0.073, 0.063) | (0.798, 0.724, 0.733) | (0.320, 0.272, 0.246) | (0.368, 0.319, 0.328) |  (0.818, 0.779, 0.759)
libtomcrypt | (0.226, 0.127, 0.069) | (0.097, 0.039, 0.061) | (0.673, 0.604, 0.700) | (0.075, 0.034, 0.059) | (0.124, 0.063, 0.117) |  (0.800, 0.766, 0.716)
coreutils | (0.315, 0.042, 0.229) | (0.081, 0.038, 0.063) |  (0.570, 0.416, 0.525) | (0.169, 0.144, 0.171) | (0.285, 0.179, 0.254) |  (0.553, 0.479, 0.625)
libMagickCore | (0.217, 0.090, 0.122) | (0.045, 0.023, 0.040) |  (0.648, 0.729, 0.721) | (0.166, 0.126, 0.127) | (0.249, 0.197, 0.189) |  (0.740, 0.715, 0.664)
libMagickWand | (0.272, 0.074, 0.054) | (0.053, 0.040, 0.039) | (0.459, 0.734, 0.804) | (0.076, 0.075, 0.056) | (0.160, 0.121, 0.151) |  (0.930, 0.875, 0.812)
libgmp | (0.419, 0.759, 0.340) | (0.244, 0.484, 0.194) |  (0.705, 0.823, 0.733) | (0.485, 0.505, 0.409) | (0.660, 0.738, 0.587) |  (0.783, 0.808, 0.746)
curl | (0.598, 0.409, 0.495) | (0.031, 0.075, 0.110) | (0.753, 0.699, 0.703) | (0.362, 0.372, 0.333) | (0.529, 0.394, 0.505) |  (0.825, 0.731, 0.791)
sqlite3 | (0.487, 0.022, 0.265) | (0.145, 0.070, 0.130) | (0.687, 0.433, 0.640) | (0.132, 0.061, 0.128) | (0.229, 0.111, 0.206) |  (0.738, 0.522, 0.695)
libz | (0.700, 0.181, 0.452) | (0.367, 0.278, 0.260) |  (0.767, 0.750, 0.836) | (0.297, 0.224, 0.206) | (0.525, 0.259, 0.402) |  (0.778, 0.681, 0.849)
plink | (0.553, 0.127, 0.290) | (0.108, 0.052, 0.109) | (0.690, 0.473, 0.673) | (0.263, 0.229, 0.213) | (0.372, 0.250, 0.323) |  (0.748, 0.562, 0.800)
pscp | (0.542, 0.115, 0.361) | (0.076, 0.047, 0.070) | (0.679, 0.406, 0.634) | (0.244, 0.206, 0.244) | (0.379, 0.241, 0.302) |  (0.754, 0.551, 0.811)
psftp | (0.563, 0.111, 0.331) | (0.088, 0.045, 0.080) | (0.690, 0.439, 0.640) | (0.248, 0.210, 0.240) | (0.361, 0.253, 0.334) |  (0.767, 0.559, 0.787)
puttygen | (0.505, 0.082, 0.470) | (0.063, 0.018, 0.059) | (0.648, 0.371, 0.624) | (0.261, 0.184, 0.263) | (0.379, 0.247, 0.374) |  (0.673, 0.513, 0.770)
Avg. | (0.450, 0.189, 0.292) | (0.115, 0.099, 0.098) | (0.674, 0.585, 0.690) | (0.238, 0.203, 0.207) | (0.355, 0.259, 0.313) |  (0.762, 0.657, 0.756)
Table 4. Libraries compiled by GCC5.4.0 with different optimization levels. funcsimsrch is short for functionsimsearch. Program | BinDiff | funcsimsrch | Asm2Vec | Gemini | Palmtree | SemDiff
---|---|---|---|---|---|---
O0-O0 O3-O3 | O0-O0 O3-O3 | O0-O0 O3-O3 | O0-O0 O3-O3 | O0-O0 O3-O3 | O0-O0 O3-O3
openssl | (0.704, 0.300) | (0.085, 0.055) |  (0.841, 0.852) | (0.358, 0.232) | (0.181, 0.265) |  (0.770, 0.877)
libtomcrypt | (0.395, 0.126) | (0.082, 0.032) |  (0.625, 0.844) | (0.125, 0.124) | (0.127, 0.090) |  (0.758, 0.770)
coreutils | (0.720, 0.190) | (0.068, 0.056) | (0.695, 0.797) | (0.222, 0.181) | (0.216, 0.280) |  (0.752, 0.828)
libMagickCore | (0.563, 0.168) | (0.065, 0.043) |  (0.607, 0.862) | (0.216, 0.175) | (0.204, 0.210) |  (0.757, 0.812)
libMagickWand | (0.519, 0.101) | (0.026, 0.024) | (0.324, 0.795) | (0.08, 0.133) | (0.054, 0.070) |  (0.872, 0.912)
libgmp | (0.270, 0.291) | (0.108, 0.195) | (0.376, 0.639) | (0.135, 0.249) | (0.150, 0.277) |  (0.487, 0.661)
curl | (0.853, 0.363) | (0.101, 0.250) | (0.845, 0.725) | (0.404, 0.356) | (0.284, 0.322) |  (0.938, 0.900)
sqlite3 | (0.828, 0.086) | (0.181, 0.081) | (0.795, 0.617) | (0.191, 0.109) | (0.119, 0.156) |  (0.890, 0.697)
libz | (0.882, 0.259) | (0.422, 0.309) | (0.863, 0.728) | (0.555, 0.267) | (0.336, 0.395) |  (0.961, 0.827)
plink | (0.826, 0.400) | (0.103, 0.106) | (0.764, 0.748) | (0.234, 0.230) | (0.165, 0.297) |  (0.870, 0.820)
pscp | (0.822, 0.396) | (0.095, 0.099) | (0.752, 0.743) | (0.242, 0.199) | (0.155, 0.241) |  (0.879, 0.819)
psftp | (0.828, 0.400) | (0.096, 0.106) | (0.644, 0.755) | (0.261, 0.207) | (0.174, 0.262) |  (0.878, 0.820)
puttygen | (0.809, 0.423) | (0.083, 0.090) | (0.762, 0.636) | (0.292, 0.182) | (0.242, 0.246) |  (0.870, 0.767)
Avg. | (0.700, 0.269) | (0.114, 0.111) | (0.694, 0.749) | (0.255, 0.203) | (0.185, 0.239) |  (0.823, 0.808)
Table 5. Binary comparison result when using different compilers. funcsimsrch
is short for functionsimsearch.

###  4.3. RQ 2: Similarity Detection Performance

####  4.3.1. Cross-GCC-Compiling-Optimization-Level

GCC is one of the most widely used compilers in the real world and thus we
choose it for cross-compiling-optimization-level evaluation. We conduct the
experiment by setting five optimization levels, $O0$, $O1$, $O2$, $O3$, and
$Os$, and apply SemDiff and the other five state-of-the-art tools to detect
the similarity of the binary codes generated from the same source function,
but compiled by using different optimization levels. In addition, we leverage
the metrics of Normalized Compression Distance (NCD) score (Ren et al., 2021;
Alshahwan et al., 2020; Raff and Nicholas, 2017a; Borbely, 2015; Raff and
Nicholas, 2017b) to quantify the syntactic similarity of the binary code pair.
A higher NVD score represents the binary code pair looks more dissimilar.

The similarity detection results are listed in Table 4. Due to the page
limitation, we only list the detection results of the most dissimilar pair
(i.e., $O3$ vs $O0$) and the two other dissimilar pairs (i.e., $O1$ vs $O0$
and $Os$ vs $O0$). The other results and the corresponding discussions are all
listed on our website. The similarity detection results illustrate that
SemDiff averagely achieves a detection precision at 73%, but the other
detection tools can only achieve a detection prediction at 65% on average.
Although Asm2Vec slightly performs better than SemDiff in some cases, SemDiff
could maintain a high detection performance even though the pair of binary
codes look the most dissimilar.

####  4.3.2.  Cross-Compiler

Similarly, we conduct the experiment by using two different compilers (i.e.,
GCC 5.4.0 and CLANG 3.8.0), but the same optimization level to assess the
similarity detection performance of SemDiff. By checking the NVD score of the
binary code pairs, we found that GCC $O0$ vs CLANG $O0$ and GCC $O1$ vs Clang
$O1$ are the two most dissimilar binary code pairs. Therefore, we listed the
similarity detection results in the paper (shown in Table 5). The rest results
are listed on our website as well.

On average, SemDiff could achieve a detection precision at 81% when using the
same optimization level, but different compilers. Also in some cases, Asm2Vec
performs slightly better than SemDiff.

For binaries compiled from the same source code using different optimization
levels in Section 4.3.1 or different compilers in Section 4.3.2, their
function numbers vary mainly due to the inline optimization, which inserts
functions being called into the callee function. Also, they are likely to
differ in almost all the binary functions as some instructions inside a
function have syntactic differences but the same semantics. These differences
will result in different function attributes such as the statistics of basic
blocks, instructions, and mnemonics. Thus methods that rely on syntactic
information (all except SemDiff) are less accurate. However, most key
semantics of a function is still preserved in this case, making SemDiff more
effective than other tools.

Program | Version |  BinDiff |  funcsimsrch |  Asm2Vec |  Gemini |  Palmtree |  SemDiff
---|---|---|---|---|---|---|---
openssl | 1.0.2o vs. 3.0.0 |  0.272 |  0.063 |  0.428 |  0.284 |  0.382 |  0.534
1.1.1i vs. 3.0.0 |  0.733 |  0.337 |  0.839 |  0.576 |  0.649 |  0.918
1.1.1 vs. 3.0.0 |  0.738 |  0.376 |  0.813 |  0.568 |  0.648 |  0.923
coreutils | 8.27 vs. 8.32 |  0.847 |  0.263 |  0.895 |  0.551 |  0.626 |  0.877
8.29 vs. 8.32 |  0.886 |  0.291 |  0.899 |  0.576 |  0.671 |  0.878
8.31 vs. 8.32 |  0.982 |  0.331 |  0.916 |  0.591 |  0.673 |  0.900
curl | 7.43 vs. 7.80 |  0.723 |  0.567 |  0.800 |  0.438 |  0.603 |  0.908
7.65 vs. 7.80 |  0.929 |  0.822 |  0.795 |  0.509 |  0.741 |  0.955
7.72 vs. 7.80 |  0.946 |  0.736 |  0.822 |  0.588 |  0.743 |  0.946
libz | 1.2.3.4 vs.1.2.11 |  0.567 |  0.667 |  0.700 |  0.520 |  0.560 |  0.800
1.2.3.9 vs. 1.2.11 |  0.655 |  0.660 |  0.786 |  0.599 |  0.598 |  0.833
1.2.8 vs. 1.2.11 |  0.796 |  0.804 |  0.839 |  0.747 |  0.768 |  0.903
Avg. |  |  0.764 |  0.495 |  0.779 |  0.548 |  0.658 |  0.870
Table 6. The similarity scores are computed by 6 tools for open-source
programs of different versions compiled by GCC 5.4.0. (funcsimsrch is short
for functionsimsearch.)

####  4.3.3. Different Obfuscation Options

We also quantify the similarity detection performance by using different
obfuscation options, that is two programs that are compiled by CLANG 3.8.0
with $O0$ and OLLVM (Junod et al., 2015) with three different obfuscation
options (i.e., SUB, BCF, and FLA). OLLVM with SUB substitutes specific
instructions within a basic block and does not change a function’s control-
flow graph significantly. With BCF, it adds additional basic blocks into a
function in a fixed pattern. With FLA, it flattens the control flow by simply
splitting original basic blocks into smaller ones or adding extra basic blocks
into an original function.

For each program, we generate three pairs and each pair consists of a CLANG-
compiled binary and an OLLVM-compiled binary with one obfuscation option. We
then fed each pair into SemDiff and two representative machine-learning-based
tools (i.e., Gemini and Palmtree) for similarity quantification. The results
are shown in Table 7. Clearly, SemDiff outperforms the other two tools for all
obfuscation options by large margin.

Program | OLLVM-SUB | OLLVM-BCF | OLLVM-FLA
---|---|---|---
Gemini |  Palmtree |  SemDiff |  Gemini |  Palmtree |  SemDiff |  Gemini |  Palmtree |  SemDiff
openssl |  0.627 |  0.713 |  0.973 |  0.034 |  0.056 |  0.840 |  0.004 |  0.004 |  0.444
libtomcrypt |  0.309 |  0.520 |  0.973 |  0.021 |  0.026 |  0.849 |  0.003 |  0.004 |  0.721
coreutils |  0.410 |  0.589 |  0.835 |  0.033 |  0.037 |  0.839 |  0.001 |  0.001 |  0.582
libMagickCore |  0.403 |  0.481 |  0.934 |  0.011 |  0.018 |  0.885 |  0.001 |  0.001 |  0.623
libMagickWand |  0.192 |  0.129 |  0.997 |  0.027 |  0.032 |  0.962 |  0.001 |  0.006 |  0.733
libgmp |  0.310 |  0.649 |  0.769 |  0.073 |  0.085 |  0.715 |  0.061 |  0.066 |  0.604
curl |  0.348 |  0.248 |  0.967 |  0.055 |  0.021 |  0.922 |  0.014 |  0.021 |  0.75
sqlite3 |  0.113 |  0.113 |  0.814 |  0.011 |  0.007 |  0.941 |  0.001 |  0.001 |  0.639
libz |  0.400 |  0.355 |  0.941 |  0.073 |  0.073 |  0.963 |  0.027 |  0.027 |  0.817
plink |  0.178 |  0.161 |  0.940 |  0.019 |  0.014 |  0.644 |  0.001 |  0.002 |  0.694
pscp |  0.188 |  0.170 |  0.945 |  0.018 |  0.019 |  0.653 |  0.001 |  0.003 |  0.689
psftp |  0.186 |  0.145 |  0.936 |  0.019 |  0.014 |  0.656 |  0.001 |  0.003 |  0.688
puttygen |  0.226 |  0.195 |  0.930 |  0.026 |  0.032 |  0.671 |  0.006 |  0.011 |  0.718
Avg. |  0.234 |  0.198 |  0.925 |  0.032 |  0.026 |  0.779 |  0.007 |  0.010 |  0.714
Table 7. The similarity scores of Gemini, Palmtree and SemDiff for programs
compiled by CLANG 3.8.0 with $O0$ and OLLVM with different obfuscation
options.

To understand the root cause of the failure cases of SemDiff, we manually
analyzed the results and found that in experiments of Section 4.3.1 and
Section 4.3.2, when SemDiff failed to rank the ground truth similar function
at the first place, in approximately 50% of the cases, SemDiff still rank the
similar function before 10th place. We consider this still can assist humans
to find similar functions efficiently. In the other 50% cases, SemDiff failed
to rank similar functions at front positions mainly due to three reasons: 1)
Lack of support for some less frequent mnemonics such as cvtss2sd. This can
negatively impact semantic information extraction thus decreasing precision.
2) Some calls are optimized into other instructions. For example, call strlen
is replaced with repne scasb, which has the same impact and behavior as call
strlen. Even using symbolic execution, their symbolic values still differ
enormously. 3) Sometimes, the unfolded loop and the folded loop can be
difficult to match. Because their symbolic expressions can differ. And the
loop number does not match (i.e., only one unfolded loop but multiple unfolded
loops).

For the experiment in Section 4.3.3, we speculate that although the
obfuscation options obfuscate a binary in terms of its syntactic structures,
they retain its key semantics, which can be retrieved by SemDiff. For the
three evaluated tools, their generated scores under the SUB option achieve the
highest compared to the other options. This is probably because the SUB option
does not change the control flow. Of the three options, scores in the FLA
option are the lowest, as it introduces more syntactical and control-flow
changes by flattening the control flow. The failure cases are caused by newly
added key instructions by obfuscation, despite the three reasons mentioned in
the last paragraph.

###  4.4. Applications of SemDiff

####  4.4.1. Similarity Quantification in Cross-Program-Version

In real-world applications, binary code similarity can be utilized to find
similar versions of library binaries or executables because vulnerabilities
tend to inherit across a range of versions. Therefore, in this section, for
two given binaries from the same program with different versions, we quantify
their similarities. For each program, four versions spanning from months to
years are compiled using GCC 5.4.0. For each program, one version is selected
as the baseline version (we note that this version is used in previous
experiments of Section 4.3.1 and Section 4.3.2.) and its similarity with each
of the other three versions is computed using precision@1, generating 39 pairs
of binaries in total. Part of the results is displayed in Table 6 due to the
page limit. Please refer to our GitHub repository for complete results.

Overall, SemDiff outperforms all the other tools. Particularly, SemDiff
achieves the best detection performance in 10 programs and ranks second in the
remaining 3 programs, i.e., coreutils, libgmp, and sqlite3. For both coreutils
and sqlite3, SemDiff’s averaged score is only 0.01 lower than that of Bindiff.
For libgmp, SemDiff’s score is only 0.03 lower than that of Asm2vec. A
possible reason why SemDiff performs less well in the 3 programs is: as the
version difference in the 3 programs is smaller than that of the 10 programs,
it indicates that the versions in these programs have more similarities in
syntactic structures, which are easier to be captured by tools that rely on
syntactic and structural features. When the version difference becomes larger
in other programs, SemDiff performs the best. The reasons for the failure
cases in this experiment are also mainly due to lack of support for rare
mnemonics, replacing calls to equivalent instructions, and difficulty in
precisely matching loops.

####  4.4.2. Vulnerability Search

An important application of binary code similarity detection is to find
similar vulnerable functions. We randomly selected 18 Common Vulnerabilities
and Exposures (CVEs) functions and detect their similar vulnerable functions.
For each vulnerable function, we randomly select a vulnerable version of it as
the base function. We also prepared another randomly selected vulnerable
function version, compiled with random compiling settings (i.e., either O0,
O1, O2, O3, Os). They are the target functions that the tools should detect as
similar to the base function. We mix the target functions with all other
functions from the binary and check the probability of the tool successfully
ranking the target vulnerable function at the first place among all functions
(i.e., top-1 score). The result is shown in Table 8. Asm2vec’s top-1 score is
9 out of 18 (50%) while SemDiff is 10 out of 18 (55.6%).

We manually analyzed the CVEs where SemDiff fails to identify (rank at the
first place). We found that out of 8 failure cases, in 6 cases (75%) SemDiff
ranked the vulnerable function before 10th place. This still indicates the
effectiveness of using SemDiff to find vulnerabilities. For the other 2
failure cases, one is due to IDA pro failing to identify the indirect jump
addresses thus making SemDiff unable to produce a complete key-semantics
graph. Another case was due to lack of support for less frequent mnemonics,
which negatively impact the semantic information extraction and thus decreased
the precision.

CVE |  Asm2vec |  SemDiff | CVE |  Asm2vec |  SemDiff
---|---|---|---|---|---
CVE-2016-8617 |  ✓ |  ✗ | CVE-2017-7407 |  ✓ |  ✓
CVE-2016-86151 |  ✗ |  ✓ | CVE-2017-2629 |  ✗ |  ✓
CVE-2016-86152 |  ✗ |  ✓ | CVE-2016-8618 |  ✗ |  ✗
CVE-2016-8616 |  ✓ |  ✗ | CVE-2017-8817 |  ✗ |  ✗
CVE-2017-9502 |  ✓ |  ✓ | CVE-2020-8169 |  ✗ |  ✗
CVE-2017-1000100 |  ✓ |  ✓ | CVE-2021-22876 |  ✗ |  ✗
CVE-2017-1000101 |  ✓ |  ✗ | CVE-2020-8286 |  ✓ |  ✗
CVE-2017-1000254 |  ✗ |  ✓ | CVE-2017-1000257 |  ✓ |  ✓
CVE-2019-5436 |  ✗ |  ✓ | CVE-2020-8285 |  ✓ |  ✓
Table 8. Vulnerability function search results. ✓represents the tool ranked
vulnerable target function at the first place in all functions. ✗is vice
versa. 1 and 2 are two functions from the same CVE ranked alphabetically.

##  5\. Discussion

Key Expression Accuracy:  As analyzed in Section 4, lack of support for less
frequent mnemonics can decrease precision. Therefore, more accuracy can
increase with more complete mnemonics supports. Due to the time limit and the
complexity of all the mnemonics, our current version only supports the most
frequently used mnemonics. Apart from complete mnemonics support, adding hard-
coded optimization knowledge into SemDiff can also increase the accuracy. As
we analyzed before, call strlen and repne scasb has different symbolic
expressions. Identifying them as the same can only be achieved through adding
that optimization knowledge into SemDiff. Since GCC and Clang are open-
sourced, a promising direction is to parse those source code to learn those
knowledge automatically.

Graph Diffing:  In our current method, we use LSH algorithm to translate each
graph into a hash value. Therefore, we equally consider the importance of each
token in the key expression. Also, for each kind of key instruction, we also
consider them to have equal importance. However, some tokens and key
instructions should have more importance than others. For example, the
matching of long instant values should indicate more similarity than matching
some frequent operational symbols such as $*$. Matching two calling type key
instructions with four arguments should weigh more than one argument. The
weight of each token and key instruction type can be learned by machine
learning if one prepares adequate training data.

Inherited Limitations:  In Section 5, there were cases when the static binary
code analysis platform IDA pro that we rely on failed to analyze indirect jump
targets. Unfolded and folded loops matching is also not well resolved. One
possible solution is to unfold the loop for a fixed time. Another solution is
to conclude the unfolded loops into one loop and compare them with the folded
loop. As to key expression simplification, SemDiff utilized msynth (Blazytko
and Schloegel, 2021), which potentially has time efficiency and accuracy
issues.

##  6\. Related Work

###  6.1. Program-analysis Based Methods

SMIT (Hu et al., 2009), BINCLONE (Farhadi et al., 2014), and SPAIN (Xu et al.,
2017a) use hashing techniques to output various instructions sequences into a
fixed length of the hash value and compare their similarity. IDEA (Santos et
al., 2010), MBC (Kang et al., 2012), Expose (Ng and Prakash, 2013) generate an
embedding from sequences. Exediff (Baker et al., 1999), Tracy (David and
Yahav, 2014), and Binsequence (Huang et al., 2017) align two sequences and
decide their similarity. SMIT (Hu et al., 2009), Binslayer (Bourquin et al.,
2013), Cesare et al. (Cesare et al., 2014) transform the problem into finding
the mapping between two CFGs with minimum cost. Beagle (Lindorfer et al.,
2012), Cesare et al. (Cesare et al., 2014), rendezous (Khoo et al., 2013), and
FOSSILE (Alrabaee et al., 2018) divide the graph into $k$ subgraphs and match
subgraphs similarity. CoP (Luo et al., 2014), SIGMA(Alrabaee et al., 2015),
Binsequence (Huang et al., 2017) determine similarity based on paths. Beagle
(Lindorfer et al., 2012), FOSSIL (Alrabaee et al., 2018), and SIGMA (Alrabaee
et al., 2015) classified instruction based on their arithmetic, logic, or data
transfer operations. Binhash (Jin et al., 2012), MULTI-HM (Pewny et al.,
2015), Bingo (Chandramohan et al., 2016), SPAIN (Xu et al., 2017a), Kargén
(Kargén and Shahmehri, 2017), IMF-SIM (Wang and Wu, 2017) check whether output
are the same to the input. Binhunt (Gao et al., 2008), Binhash (Jin et al.,
2012), Expose (Ng and Prakash, 2013), CoP(Luo et al., 2014), MULTI-MH (Pewny
et al., 2015), ESH(David et al., 2016) symbolically execute the binaries and
compare similarity by constraint solver. XMATCH (Feng et al., 2017), TEDEM
(Pewny et al., 2014) determine the edit distance of the tree/graph of the
symbolic formula. However, this genre of work is problematic in basic-level
comparison or sequence aligning due to the difference caused by compilers and
optimizations.

###  6.2. Machine-learning Based Methods

Genius (Feng et al., 2016), Vulseeker(Gao et al., 2018), Gemini (Xu et al.,
2017b), Yu et al. (Yu et al., 2020), Cochard et al. (Cochard et al., 2022),
TIKNIB(Kim et al., 2022) extract features from graphs into feature vectors and
determine the vector similarity. QBinDiff (Mengin and Rossi, 2021)extracts
binary code features and uses graph edit distance and network alignment
methods to measure similarity. $\alpha$Diff (Liu et al., 2018), InnerEye (Zuo
et al., 2022), Asm2Vec (Ding et al., 2019), Kam1n0 (Ding et al., 2016), and
Safe (Massarelli et al., 2019) automatically learn the embedding for each
instruction and use them to produce the basic-level or function-level
embedding. However, this genre of work can be affected heavily by the training
data and optimization levels.

##  7\. Conclusion

This paper proposed SemDiff, which is a novel semantic method for binary
similarity detection. SemDiff has two modules: graph generation and graph
diffing. In graph generation, we proposed complete instructions traversal of a
given function and a lightweight loop processing to generate key instruction
symbolic expressions. We further translate symbolic expressions to key
expressions and form a key-semantics graph. We utilized LSH to diff two key-
semantics graphs.

In our evaluation, We compared SemDiff with 5 state-of-the-art baseline tools
in binary similarity detection, results of which showed that SemDiff
outperformed all the baseline tools on average. While our current version of
SemDiff works for x86-based binaries SemDiff can be extended to support
similarity detection cross architectures (e.g., x86 and ARM) in our future
work. Particularly, we will extend the graph-generation module to extract and
transform key instructions from a target architecture into key expressions.

## References

  * (1)
  * Alrabaee et al. (2015) S. Alrabaee, Paria Shirani, Lingyu Wang, and M. Debbabi. 2015\.  SIGMA: A Semantic Integrated Graph Matching Approach for identifying reused functions in binary code.  _Digital Investigation_ (2015), S61–S71.
  * Alrabaee et al. (2018) Saed Alrabaee, Paria Shirani, Lingyu Wang, and Mourad Debbabi. 2018.  FOSSIL: A Resilient and Efficient System for Identifying FOSS Functions in Malware Binaries.  _ACM Transactions on Privacy and Security_ (2018).
  * Alshahwan et al. (2020) Nadia Alshahwan, Earl T. Barr, David Clark, George Danezis, and Héctor D. Menéndez. 2020.  Detecting Malware with Information Complexity.  _Entropy_ 22, 5 (2020), 575.
  * Baker et al. (1999) Brenda S Baker, Udi Manber, and Robert Muth. 1999\.  Compressing differences of executable code. In _ACMSIGPLAN Workshop on Compiler Support for System Software_. 1–10.
  * Blazytko and Schloegel (2021) Tim Blazytko and Moritz Schloegel. 2021.  msynth.  {https://github.com/mrphrazer/msynth}
  * Borbely (2015) Reba Schuller Borbely. 2015\.  On Normalized Compression Distance and Large Malware Towards a Useful Definition of Normalized Compression Distance for the Classification of Large Files.  _Journal of Computer Virology and Hacking Techniques_ (2015).
  * Bourquin et al. (2013) Martial Bourquin, Andy King, and Edward Robbins. 2013\.  BinSlayer: Accurate Comparison of Binary Executables. In _ACM SIGPLAN Program Protection and Reverse Engineering Workshop_.
  * Cesare et al. (2014) Silvio Cesare, Yang Xiang, and Wanlei Zhou. 2014\.  Control Flow-Based Malware Variant Detection.  _IEEE Transactions on Dependable and Secure Computing_ 11 (2014), 307–317.
  * Chandramohan et al. (2016) Mahinthan Chandramohan, Yinxing Xue, Zhengzi Xu, Y. Liu, Chia Yuan Cho, and Hee Beng Kuan Tan. 2016.  BinGo: cross-architecture cross-OS binary search. In _ACM SIGSOFT International Symposium on Foundations of Software Engineering_.
  * Cheng et al. (2018) Binlin Cheng, Jiang Ming, Jianmin Fu, Guojun Peng, Ting Chen, Xiaosong Zhang, and Jean-Yves Marion. 2018.  Towards paving the way for large-scale windows malware analysis: Generic binary unpacking with orders-of-magnitude performance boost. In _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security_. 395–411.
  * Cochard et al. (2022) Victor Cochard, Damian Pfammatter, Chi Thang Duong, and Mathias Humbert. 2022.  Investigating Graph Embedding Methods for Cross-Platform Binary Code Similarity Detection. In _2022 IEEE 7th European Symposium on Security and Privacy (EuroS &P)_. IEEE, 60–73.
  * David et al. (2020) Robin David, Luigi Coniglio, and Mariano Ceccato. 2020\.  QSynth-A Program Synthesis based Approach for Binary Code Deobfuscation. In _BAR 2020 Workshop_.
  * David et al. (2016) Yaniv David, Nimrod Partush, and Eran Yahav. 2016\.  Statistical Similarity of Binaries. 266–280.
  * David and Yahav (2014) Yaniv David and Eran Yahav. 2014.  Tracelet-Based Code Search in Executables. 349–360.
  * Ding et al. (2016) Steven H. H. Ding, B. Fung, and P. Charland. 2016.  Kam1n0: MapReduce-based Assembly Clone Search for Reverse Engineering. In _ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_.
  * Ding et al. (2019) Steven H. H. Ding, B. Fung, and P. Charland. 2019.  Asm2Vec: Boosting Static Representation Robustness for Binary Clone Search against Code Obfuscation and Compiler Optimization. In _OAKLAND_. 472–489.
  * Duan et al. (2020) Yue Duan, Xuezixiang Li, Jinghan Wang, and Heng Yin. 2020\.  Deepbindiff: Learning program-wide code representations for binary diffing.
  * Dullien (2018) Thomas Dullien. 2018\.  Functionsimsearch.
  * Eschweiler et al. (2016) Sebastian Eschweiler, Khaled Yakdan, and Elmar Gerhards-Padilla. 2016.  discovRE: Efficient Cross-Architecture Identification of Bugs in Binary Code. 58–79.
  * Farhadi et al. (2014) Mohammad Reza Farhadi, Benjamin C.M. Fung, Philippe Charland, and Mourad Debbabi. 2014.  BinClone: Detecting Code Clones in Malware. 78–87.
  * Feng et al. (2017) Qian Feng, Minghua Wang, Mu Zhang, Rundong Zhou, Andrew Henderson, and Heng Yin. 2017\.  Extracting Conditional Formulas for Cross-Platform Bug Search. 346–359.
  * Feng et al. (2016) Qian Feng, Rundong Zhou, Chengcheng Xu, Yao Cheng, Brian Testa, and Heng Yin. 2016\.  Scalable Graph-Based Bug Search for Firmware Images. 480–491.
  * Flake (2004) Halvar Flake. 2004\.  Structural comparison of executable objects. In _Detection of intrusions and malware & vulnerability assessment, GI SIG SIDAR workshop, DIMVA 2004_.
  * Gao et al. (2008) Debin Gao, Michael K Reiter, and Dawn Song. 2008.  Binhunt: Automatically finding semantic differences in binary programs. In _International Conference on Information and Communications Security_. 238–255.
  * Gao et al. (2018) Jian Gao, Xin Yang, Ying Fu, Yu Jiang, and Jiaguang Sun. 2018.  VulSeeker: A Semantic Learning Based Vulnerability Seeker for Cross-Platform Binary. 896–899.
  * Haq and Caballero (2021) Irfan Ul Haq and Juan Caballero. 2021.  A Survey of Binary Code Similarity.  _ACM Computing Survey_ 54, 3 (2021), 38 pages.
  * Hu et al. (2009) Xin Hu, Tzi-cker Chiueh, and Kang G. Shin. 2009.  Large-Scale Malware Indexing Using Function-Call Graphs. 611–620.
  * Huang et al. (2017) He Huang, Amr M. Youssef, and Mourad Debbabi. 2017.  BinSequence: fast, accurate and scalable binary code reuse detection. 155–166.
  * Jin et al. (2012) Wesley Jin, Sagar Chaki, Cory Cohen, Arie Gurfinkel, Jeffrey Havrilla, Charles Hines, and Priya Narasimhan. 2012.  Binary Function Clustering Using Semantic Hashes. In _International Conference on Machine Learning and Applications_. 386–391.
  * Junod et al. (2015) Pascal Junod, Julien Rinaldini, Johan Wehrli, and Julie Michielin. 2015.  Obfuscator-LLVM – Software Protection for the Masses. In _IEEE/ACM International Workshop on Software Protection_. 3–9.
  * Kan et al. (2019) Zeliang Kan, Haoyu Wang, Lei Wu, Yao Guo, and Daniel Xiapu Luo. 2019.  Automated deobfuscation of Android native binary code.  _arXiv preprint arXiv:1907.06828_ (2019).
  * Kang et al. (2012) Boojoong Kang, Taekeun Kim, Heejun Kwon, Yangseo Choi, and Eul Gyu Im. 2012.  Malware Classification Method via Binary Content Comparison. 316–321.
  * Kargén and Shahmehri (2017) U. Kargén and N. Shahmehri. 2017.  Towards robust instruction-level trace alignment of binary code. 342–352.
  * Khoo et al. (2013) Wei Ming Khoo, Alan Mycroft, and Ross Anderson. 2013\.  Rendezvous: A search engine for binary code. In _Working Conference on Mining Software Repositories_. 329–338.
  * Kim et al. (2022) Dongkwan Kim, Eunsoo Kim, Sang Kil Cha, Sooel Son, and Yongdae Kim. 2022.  Revisiting binary code similarity analysis using interpretable feature engineering and lessons learned.  _IEEE Transactions on Software Engineering_ (2022).
  * Li et al. (2021) Xuezixiang Li, Yu Qu, and Heng Yin. 2021.  Palmtree: learning an assembly language model for instruction embedding. 3236–3251.
  * Lin et al. (2019) Guanjun Lin, Jun Zhang, Wei Luo, Lei Pan, Olivier De Vel, Paul Montague, and Yang Xiang. 2019.  Software vulnerability discovery via learning multi-domain knowledge bases.  _IEEE Transactions on Dependable and Secure Computing_ (2019).
  * Lindorfer et al. (2012) Martina Lindorfer, Alessandro Di Federico, Federico Maggi, Paolo Milani Comparetti, and Stefano Zanero. 2012.  Lines of Malicious Code: Insights into the Malicious Software Industry. In _ACM Annual Computer Security Applications Conference_. 349–358.
  * Liu et al. (2018) Bingchang Liu, Wei Huo, Chao Zhang, Wenchao Li, Feng Li, Aihua Piao, and Wei Zou. 2018.  $\alpha$diff: Cross-Version Binary Code Similarity Detection with DNN. 667–678.
  * Luo et al. (2014) Lannan Luo, Jiang Ming, Dinghao Wu, Peng Liu, and Sencun Zhu. 2014.  Semantics-Based Obfuscation-Resilient Binary Code Similarity Comparison with Applications to Software Plagiarism Detection. 389–400.
  * Massarelli et al. (2019) Luca Massarelli, Giuseppe Antonio Di Luna, Fabio Petroni, Leonardo Querzoni, and R. Baldoni. 2019\.  SAFE: Self-Attentive Function Embeddings for Binary Similarity.  _ArXiv_ abs/1811.05296 (2019).
  * Mengin and Rossi (2021) Elie Mengin and Fabrice Rossi. 2021.  Binary Diffing as a Network Alignment Problem via Belief Propagation. In _IEEE/ACM International Conference on Automated Software Engineering_. 967–978.
  * Ming et al. (2017) Jiang Ming, Dongpeng Xu, Yufei Jiang, and Dinghao Wu. 2017\.  Binsim: Trace-based semantic binary diffing via system call sliced segment equivalence checking. 253–270.
  * Nagra and Collberg (2009) Jasvir Nagra and Christian Collberg. 2009.  _Surreptitious Software: Obfuscation, Watermarking, and Tamperproofing for Software Protection: Obfuscation, Watermarking, and Tamperproofing for Software Protection_.
  * Ng and Prakash (2013) Beng Heng Ng and Atul Prakash. 2013.  Expose: Discovering Potential Binary Code Re-use. In _IEEE Annual Computer Software and Applications Conference_. 492–501.
  * Pewny et al. (2015) Jannik Pewny, Behrad Garmany, Robert Gawlik, Christian Rossow, and Thorsten Holz. 2015\.  Cross-architecture bug search in binary executables. 709–724.
  * Pewny et al. (2014) Jannik Pewny, Felix Schuster, Lukas Bernhard, Thorsten Holz, and Christian Rossow. 2014.  Leveraging Semantic Signatures for Bug Search in Binary Programs. In _Annual Computer Security Applications Conference_. 406–415.
  * Raff and Nicholas (2017a) Edward Raff and Charles Nicholas. 2017a.  An Alternative to NCD for Large Sequences, Lempel-Ziv Jaccard Distance. In _ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. 1007–1015.
  * Raff and Nicholas (2017b) Edward Raff and Charles Nicholas. 2017b.  Malware classification and class imbalance via stochastic hashed lzjd. In _ACM Workshop on Artificial Intelligence and Security_. 111–120.
  * Ren et al. (2021) Xiaolei Ren, Michael Ho, Jiang Ming, Yu Lei, and Li Li. 2021.  Unleashing the Hidden Power of Compiler Optimization on Binary Code Difference: An Empirical Study. 142–157.
  * Roundy and Miller (2013) Kevin A Roundy and Barton P Miller. 2013.  Binary-code obfuscations in prevalent packer tools.  _Comput. Surveys_ 46 (2013), 1–32.
  * Saıdi et al. (2010) Hassen Saıdi, Phillip Porras, and Vinod Yegneswaran. 2010\.  Experiences in malware binary deobfuscation.  _Virus Bulletin_ (2010).
  * Santos et al. (2010) Igor Santos, Felix Brezo, Javier Nieves, Yoseba K Penya, Borja Sanz, Carlos Laorden, and Pablo G Bringas. 2010.  Idea: Opcode-sequence-based malware detection. In _International Symposium on Engineering Secure Software and Systems_. 35–43.
  * Wang and Wu (2017) Shuai Wang and Dinghao Wu. 2017.  In-Memory Fuzzing for Binary Code Similarity Analysis. 319–330.
  * Xu et al. (2017b) Xiaojun Xu, Chang Liu, Qian Feng, Heng Yin, Le Song, and Dawn Song. 2017b.  Neural network-based graph embedding for cross-platform binary code similarity detection. 363–376.
  * Xu et al. (2017a) Zhengzi Xu, Bihuan Chen, Mahinthan Chandramohan, Yang Liu, and Fu Song. 2017a.  SPAIN: Security Patch Analysis for Binaries towards Understanding the Pain and Pills. 462–472.
  * Yamaguchi et al. (2012) Fabian Yamaguchi, Markus Lottmann, and Konrad Rieck. 2012\.  Generalized Vulnerability Extrapolation Using Abstract Syntax Trees. In _Annual Computer Security Applications Conference_. 359–368.
  * Yu et al. (2020) Zeping Yu, Rui Cao, Qiyi Tang, Sen Nie, Junzhou Huang, and Shi Wu. 2020\.  Order matters: semantic-aware neural networks for binary code similarity detection. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 34. 1145–1152.
  * Zhou et al. (2007) Yongxin Zhou, Alec Main, Yuan X Gu, and Harold Johnson. 2007\.  Information hiding in software with mixed boolean-arithmetic transforms. In _International Workshop on Information Security Applications_. 61–75.
  * Zuo et al. (2022) Fei Zuo, Xiaopeng Li, Zhexin Zhang, Patrick Young, Lannan Luo, and Qiang Zeng. 2022\.  Neural Machine Translation Inspired Binary Code Similarity Comparison beyond Function Pairs.


# Structures and magnetic properties of ZnO nanoislands

Yu Yang1,2, Ping Zhang1111Corresponding author. E-mail address: zhang
<EMAIL_ADDRESS>1LCP, Institute of Applied Physics and Computational
Mathematics, P.O. Box 8009, Beijing 100088, People’s Republic of China
2Center for Advanced Study and Department of Physics, Tsinghua University,
Beijing 100084, People’s Republic of China

###### Abstract

Using first-principles calculations, we systematically study the atomic
structures and electronic properties for two dimensional triangular ZnO
nanoislands that are graphite-like with monolayer and bilayer thickness. We
find that the monolayer ZnO nanoisland with O terminated zigzag edges is
magnetic at its ground state, with the magnetism coming from the O edge
states. The other monolayer and bilayer ZnO nanoislands with different edge
structures are all nonmagnetic at their ground states. It is further revealed
that for different ZnO nanoislands, their magnetic properties are quite
dependent on their sizes, with larger nanoislands having larger magnetic
moments.

As a semiconducting metal oxide with a direct band gap, zinc oxide (ZnO) has
vast applications on optoelectronics, transducers and spintronics Bagnall1997
; Bai2003 ; Wang2004 . Recently, ZnO nanostructures of different morphologies
have been fabricated and studied Kong2003 ; Gao2005 . Especially, graphite-
like hexagonal ZnO nanofilms have been successfully fabricated Tusche2007  and
extensively studied for possible usages in electronic devices Freeman2006 ;
Goniakowski2007 ; Pala2007 . Moreover, similar to the situations in graphene
nanostuctures, ZnO nanotubes and nanoribbons have then also been investigated
for possible potential applications Wang2007 ; Shen2007 ; Mendez2007 ;
Mendez2007NL . It is noted that the monolayer ZnO nanoribbons with zigzag
edges exhibit magnetic behavior Mendez2007NL . Besides carbon nanotubes and
graphene nanoribbons, two dimensional (2D) graphene nanoislands have also been
paid vast attentions because of their unique flexibility in tuning magnetic
properties Rossier2007 ; Wang2008 . Thus when turn to ZnO nanostructures, one
may wonder whether 2D ZnO nanoislands show tunable magnetic properties or not.
Especially when ZnO nanoisland samples is experimentally attainable by
depositing hexagonal ZnO nanofilms on the Ag(111) surface Tusche2007 .
Motivated by this question, in this paper we present systematical
investigations on the atomic structures and electronic properties of 2D
triangular ZnO nanoislands.

Moreover, the so-called $d^{0}$-magnetism have recently attracted extensive
interests, which represents for magnetic behaviors in semiconducting materials
(including ZnO) with the absence of transition metal doping. It was firstly
observed in HfO2 thin films where defects or oxygen vacancies cause magnetic
behaviors Venkatesan2004 . Later, it has also been theoretically predicted
that carbon doping in ZnO Pan07  and cation-vacancy in GaN and BN Dev08  both
will lead to magnetic behaviors. In addition to these previous researches,
here through first-principles calculations, we further reveal that the
monolayer ZnO nanoisland with O terminated zigzag edge also shows magnetism in
its ground state, even without any vacancies or defects.

In the present work, the first-principles calculations are carried out using
the DMOL3 package. Density functional semicore pseudopotentials (DSPP) DSPP
are adopted to replace the effects of core electrons of Zn and O with a simple
potential including some degree of relativistic correction. The spin-polarized
PW91 PW91  functional based on generalized gradient approximation (GGA) is
employed to take into account the exchange and correlation effects of
electrons. For valence electrons, the double-numerical basis with polarized
functions is adopted for expansion of the single-particle wave functions in
Kohn-Sham equations. For better accuracy, the octupole expansion scheme is
adopted for resolving the charge density and Coulombic potential, and a fine
grid is chosen for numerical integration. The charge density is converged to
1$\times$10-6 a.u. in the selfconsistent calculation. In the optimization
process, the energy, energy gradient, and atomic displacement are converged to
1$\times$10-5, 1$\times$10-4 and 1$\times$10-3 a.u., respectively. The atomic
charge and magnetic moment are obtained by the Mulliken population analysis.

In the experiment by Tusche et al., the observed triangular 2D ZnO nanoislands
all have the size of about 20 Å Tusche2007 . So we here start by investigating
several kinds of ZnO nanoislands at this size, including the monolayer and
bilayer ZnO nanoislands with both armchair and zigzag edges. It should be
noted that there are two different kinds of zigzag edges (respectively the Zn-
and O-terminated) for monolayer ZnO nanoislands. In total, five different ZnO
nanoislands are studied here: the monolayer armchair-edge ZnO nanoisland
(AZnONI), and zigzag-edge ZnO nanoisland with Zn- (Zn-ZZnONI) and O-terminated
edges (O-ZZnONI), the bilayer armchair-edge (BAZnONI) and zigzag-edge ZnO
nanoisland (BZZnONI). The optimized atomic structures for these ZnO
nanoislands are all shown in Fig. 1.

During geometry optimizations, different kinds of ZnO nanoislands show
different structural reconstructions. As shown in Figs. 1(a)-(c), after
geometry optimizations for the monolayer ZnO nanoislands, all the atoms are
still inside a same plane. For the AZnONI, the atoms at the edges and corners
are distorted from their equilibrium places, and nine new Zn-Zn bonds form at
the three edges as shown in Fig. 1(a). For the monolayer zigzag-edge ZnO
nanoislands, the structural reconstructions only occur at the three corner
areas. One can see from Fig. 1(b) that in the Zn-ZZnONI structure, the two Zn
atoms at each corner come close with each other and form a new Zn-Zn bond,
with the three O atoms at the corners pushed out from their original sites. In
the O-ZZnONI structure shown in Fig. 1(c), the two O atoms at each corner move
away from each other a little making the three Zn atoms at the corners pulled
in from their original sites. The reconstructions for the BAZnONI and BZZnONI
structures are more complex. Figures. 1(e) and (g) are respectively the side
view for the atomic structures in the blue and red squares in Figs. 1(d) and
(f), from which one can see that the atoms at corners and edges are no longer
in the same plane with the middle atoms. The bond angles at these distorted
areas are decreased to be smaller than 120∘, indicating that these atoms
incline to transit to the wurtzite configuration.

The electronic properties for the 2D ZnO nanoislands are then studied, and
found to depend critically on their edge structures. Figure 2 shows the
calculated energy levels for the five geometrically optimized ZnO nanoislands
with different edge structures. From Figs. 2(a), (d), and (e), we can clearly
see that there exist large energy gaps for the AZnONI, BAZnONI and BZZnONI
structures. This is in accordance with the saturation that the ratio between
Zn and O atom numbers is 1:1 in them. The Zn-ZZnONI and O-ZZnONI structure
respectively contains more Zn and O atoms, and thus are unsaturated. However,
spin-splitting effect can only be observed for the O-ZZnONI structure as shown
in Fig. 2(c). And the calculated total spin ($S_{\rm tot}$) is 2. From the
calculated energy levels shown in Fig. 2(c), we see that the energy difference
between the highest occupied molecular orbital (HOMO) of spin-up and spin-down
electrons ($E_{d}$ (HOMO)) is only 0.13 eV, which is very small and indicates
that the spin-splitting effect is very weak. The smaller energy gap in
individual gaps of spin-up and -down electronic states is defined as
$E_{g}^{*}$, which is 0.18 eV and zero for the Zn- and O-ZZnONI structure
respectively. The zero energy gap indicates that the O-ZZnONI structure is
metallic at its ground state. And the small energy gap of 0.18 eV indicates
that the Zn-ZZnONI structure is chemically not very stable. However, the Zn-
and O-ZZnONI structures still might be fabricated using some special methods,
since unpolarized hexagonal ZnO monolayers have been successfully produced
already Tusche2007 .

The deformation electron density and spin density are then further analyzed to
study the origin of the magnetism in the O-ZZnONI structure. From the
deformation electron density shown in Fig. 3(a), we can see that all the O
atoms get some electrons from Zn atoms in the nanoisland. Mulliken charge
density analysis further shows that the O atoms at the corners and edges get
about 0.1 $e$ more electrons than the O atoms in the middle of the nanoisland.
These extra electrons might supply the excessive electrons in one spin state.
Detailed wavefunction analysis proves that the electronic states around the
Fermi energy are mainly contributed by the oxygen-dominated edge states.
Figure 3(b) shows the spin density distribution in the O-ZZnONI structure. In
this case, it is clear that the magnetic behavior is due to the oxygen edge
states.

The fact that the O-ZZnONI structure without any magnetic impurities is
magnetic might help us better understand the profound origin of magnetism in
ZnO-based nanostructures. Besides, the magnetism in the O-ZZnONI structure
also hints that it might has direct applications in nanoscale spintronics. So
we further investigate the size effects on the magnetism in different O-ZZnONI
structures, which can be differentiated by the number of O atoms at each edge
($i$), and we will use O$i$-ZZnONI to represent the O-ZZnONI structure of
different sizes. Based on this definition, the previously discussed O-ZZnONI
structure is actually the O$6$-ZZnONI structure.

Table I shows the calculated magnetic and electronic properties for some
O$i$-ZZnONI structures. We find that the value of all $E_{d}$ (HOMO) ranges
between 0 and 0.2 eV, which is very small and indicates that the spin-
splitting effect is weak for all the O$i$-ZZnONI structures. From the
calculated $S_{\rm tot}$ listed in Table I, we can see obvious quantum size
effects. Except for O$3$-ZZnONI, the O$i$-ZZnONI structure with a larger size
always has a larger total spin. From careful wavefunction analysis, we find
that in the O$3$-ZZnONI structure, electrons of the middle oxygen atoms also
contribute to its magnetic states. Considering that the magnetic states in
other O$i$-ZZnONI structures are all contributed by their O edge states, this
explains why the O$3$-ZZnONI structure has a larger $S_{\rm tot}$ than the
O$4$-ZZnONI and O$5$-ZZnONI structures. However, the abnormal large total spin
of the O$3$-ZZnONI structure is because of its too small size. For most
O$i$-ZZnONI structures, larger ones will have larger total spin.

In summary, we have systematically investigated the structures and magnetic
properties for 2D ZnO nanoislands. It is found that the structural
reconstructions are mainly around the three corners and three edges for
triangular ZnO nanoislands. Among the five ZnO nanoislands with different edge
structures, only the O-ZZnONI structure is magnetic at its ground state. And
its spin density mainly distributes at the edge oxygen atoms. For the O-ZZnONI
structure with different sizes, we reveal that the magnetic and electronic
properties are quite dependent on their sizes. The O$i$-ZZnONI structure with
a larger size always has a larger magnetic moment, implying their potential
usages in spintronics.

This work was supported by the NSFC under grants No. 10604010 and No.
60776063.

## References

  * (1) D. M. Bagnall, Y. F. Chen, Z. Zhu, T. Yao, S. Koyama, M. Y. Shen and T. Goto, Appl. Phys. Lett. 70, 2230 (1997).
  * (2) X. D. Bai, P. X. Gao and Z. L. Wang, Appl. Phys. Lett. 82, 4806 (2003).
  * (3) Z. L. Wang, X. Y. Kong, Y. Ding, P. Gao, W. L. Hughes, R. Yang and Y. Zhang, Adv. Funct. Mater. 14, 944 (2004).
  * (4) X. Y. Kong and Z. L. Wang, Nano Lett. 3, 1625 (2003).
  * (5) P. X. Gao, Y. Ding, W. J. Mai, W. L. Hughes, C. S. Lao and Z. L. Wang, Science 309, 1700 (2005).
  * (6) C. Tusche, H. L. Meyerheim and J. Kirschner, Phys. Rev. Lett. 99, 026102 (2007).
  * (7) C. L. Freeman, F. Claeyssens, N. L. Allan, and J. H. Harding, Phys. Rev. Lett. 96, 066102 (2006).
  * (8) J. Goniakowski, C. Noguera, and L. Giordano, Phys. Rev. Lett. 98, 205701 (2007).
  * (9) R. G. S. Pala and H. Metiu, J. Phys. Chem. C 111, 12715 (2007).
  * (10) B. L. Wang, S. Nagase, J. J. Zhao, and G. H. Wang, Nanotechnology 18, 345706 (2007).
  * (11) X. Shen, P. B. Allen, J. T. Muckerman, J. W. Davenport and J. C. Zheng, Nano Lett. 7, 2267 (2007).
  * (12) A. R. B. Médez, M. T. M. Martínez, F. L. Urías, M. Terrones and H. Terrones, Chem. Phys. Lett. 448, 258 (2007).
  * (13) A. R. B. Méndez, F. L. Urías, M. Terrones and H. Terrones, Nano Lett. 8, 1562 (2007).
  * (14) J. F. Rossier and J. J. Palacios, Phys. Rev. Lett. 99, 177204 (2007).
  * (15) W. L. Wang, S. Meng and E. Kaxiras, Nano Lett. 8, 241 (2008).
  * (16) M. Venkatesan, C. B. Fitzgerald, and J. M. D. Coey, Nature 430, 630 (2004).
  * (17) H. Pan, J. B. Yi, L. Shen, R. Q. Wu, J. H. Yang, J. Y. Lin, Y. P. Feng, J. Ding, L. H. Van, and J. H. Yin, Phys. Rev. Lett. 99, 127201 (2007).
  * (18) P. Dev, Y. Xue, and P. H. Zhang, Phys. Rev. Lett. 100, 117204 (2008).
  * (19) B. Delley, Phys. Rev. B 66, 155125 (2002).
  * (20) J. P. Perdew and Y. Wang, Phys. Rev. B 45, 13244 (1992).

Table 1: The energy difference of HOMO ($E_{d}$ (HOMO)), the smaller energy gap in individual gaps of spin-up and spin-down states ($E_{g}^{*}$), and the total spin ($S_{\rm tot}$) for the O$i$-ZZnONI structure with different sizes. $i$ |  $E_{d}$ (HOMO) (eV) |  $E_{g}^{*}$ (eV) | $S_{\rm tot}$
---|---|---|---
3 | 0.01 | 0.19 | 2
4 | 0.08 | 0.06 | 1
5 | 0.17 | 0.06 | 1
6 | 0.13 | 0.00 | 2
7 | 0.04 | 0.02 | 3

List of captions

Fig.1 (Color online). Atomic structures from top view for the AZnONI (a), Zn-
ZZnONI (b), O-ZZnONI (c), BAZnONI (d) and BZZnONI (f). (e) and (g) Atomic
structures from side view for the selected atoms in (d) and (f). In all the
structures, red and grey balls represent O and Zn atoms respectively.

Fig.2 (Color online). Energy levels of AZnONI (a), Zn-ZZnONI (b), O-ZZnONI
(c), BAZnONI (d) and BZZnONI (e). The left and right columns in each figure
correspond to spin-up and spin-down electronic states, respectively.

Fig.3 (Color online). Contour plot of the deformation electron density (a) and
isosurface plot of the spin density (b) for the O-ZZnONI. Red and grey balls
respectively represent O and Zn atoms. The isosurface with the value of 0.01
$e$/Å3 is shown in blue.

Figure 1:

Figure 2:

Figure 3: