Boosting Neural Networks to Decompile Optimized Binaries
Decompilation aims to transform a low-level program language (LPL) (eg.,
binary file) into its functionally-equivalent high-level program language (HPL)
(e.g., C/C++). It is a core technology in software security, especially in
vulnerability discovery and malware analysis. In recent years, with the
successful application of neural machine translation (NMT) models in natural
language processing (NLP), researchers have tried to build neural decompilers
by borrowing the idea of NMT. They formulate the decompilation process as a
translation problem between LPL and HPL, aiming to reduce the human cost
required to develop decompilation tools and improve their generalizability.
However, state-of-the-art learning-based decompilers do not cope well with
compiler-optimized binaries. Since real-world binaries are mostly
compiler-optimized, decompilers that do not consider optimized binaries have
limited practical significance. In this paper, we propose a novel
learning-based approach named NeurDP, that targets compiler-optimized binaries.
NeurDP uses a graph neural network (GNN) model to convert LPL to an
intermediate representation (IR), which bridges the gap between source code and
optimized binary. We also design an Optimized Translation Unit (OTU) to split
functions into smaller code fragments for better translation performance.
Evaluation results on datasets containing various types of statements show that
NeurDP can decompile optimized binaries with 45.21% higher accuracy than
state-of-the-art neural decompilation frameworks.
Ying Cao, Ruigang Liang, Kai Chen, Peiwei Hu
# Boosting Neural Networks to Decompile Optimized Binaries

###### Abstract.

Decompilation aims to transform a low-level program language (LPL) (e.g., binary file) into its functionally-equivalent high-level program language (HPL) (e.g., C/C++). It is a core technology in software security, especially in vulnerability discovery and malware analysis. In recent years, with the successful application of neural machine translation (NMT) models in natural language processing (NLP), researchers have tried to build neural decompilers by borrowing the idea of NMT. They formulate the decompilation process as a translation problem between LPL and HPL, aiming to reduce the human cost required to develop decompilation tools and improve their generalizability. However, state-of-the-art learning-based decompilers do not cope well with compiler-optimized binaries. Since real-world binaries are mostly compiler-optimized, decompilers that do not consider optimized binaries have limited practical significance. In this paper, we propose a novel learning-based approach named _NeurDP_, that targets compiler-optimized binaries. _NeurDP_ uses a graph neural network (GNN) model to convert LPL to an intermediate representation (IR), which bridges the gap between source code and optimized binary. We also design an Optimized Translation Unit (OTU) to split functions into smaller code fragments for better translation performance. Evaluation results on datasets containing various types of statements show that _NeurDP_ can decompile optimized binaries with 45.21% higher accuracy than state-of-the-art neural decompilation frameworks.

2022-

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote † †: Footnote †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote † †: thanks: [

+
Footnote † †: Footnote † †: thanks: [

+
Footnote †: Footnote †: thanks: [

+
Footnote †: Footnote † †: thanks: [

+
Footnote †: Footnote † †: thanks: [

+
Footnote † †: Footnote † †: thanks: [

+
Footnote † †: Footnote † †: thanks: [

+
Footnote † †: Footnote † †: thanks: [

+
Footnote † †: Footnote † †: thanks: [

+
Footnote † †: Footnote † †: thanks: [

+
Footnote † †: Footnote † † †: thanks: [

+
Footnote † † †: Footnote † † † †: thanks: [

+
Footnote
they still suffer a severe drawback: _none of these works can appropriately handle the decompilation of optimized code._ As compiler optimization is ubiquitously used, the ability to decompile optimized code is essential for the practical application of neural-based approaches.

Through extensive analysis and experimentation, we found that it is not easy to train an end-to-end decompilation model that can handle optimized LPL. Since deep learning models are data-driven, a high-quality training set is critical to the model's performance. Most models used in the source code or reverse engineering domains rely on large, high-quality supervised or unsupervised datasets. In contrast, there are very few mature datasets in the field of decompilation, and datasets used in previous neural-based decompilation studies are not built for the decompilation of optimized LPL. Without a well-labeled dataset, it is difficult for the model to learn the mapping rules between HPL and LPL. Although many open-source projects exist in the real world, the source code and binary code cannot be completely matched at the statement level due to code optimization (e.g., dead code elimination), making it inaccurate to directly use source code as the labels for the optimized binaries. We summarize the challenges as follows.

**Challenges. C1:** It is well known that statements of HPL are often significantly refactored during compiler optimization, which makes it challenging to make an exact match between the semantics of LPL and HPL. For example, dead code elimination causes certain statements in HPL not to appear in LPL. Loop unwinding can cause some code to appear multiple times in the binary and only once in the source code. These optimization strategies all lead to the code structure and semantic information in the text level of LPL being quite different from HPL. In some cases, textually similar HPL codes (only some variable names differ) can correspond to completely different LPL codes, and vice versa. Therefore, it is not feasible to directly train end-to-end models using HPL as the label of LPL, which makes it challenging to capture the decompilation rules.

**C2:** Splitting LPL and HPL into code fragments with correct correspondence is a nontrivial task. Previous work typically utilizes functions or basic blocks (BBs) as input units for training neural models. However, the number of instructions in a function or a BB can be infinite (up to 1,000 instructions), which is hard to handle appropriately by neural network models. Therefore, it is essential to split the BB into finer-grained units, which can effectively reduce the model's difficulty in learning the decompiled rules. One straightforward method is to split the LPL or HPL based on debug information. However, the LPL and HPL mapped by the debug information are inaccurate, especially for optimized binaries. For example, the dead code in the HPL will also be mapped onto the LPL along with the live code. Another straightforward way is to set a maximum fragment length and split the basic block into fragments. However, several statements in a fragment may have over one independent feature. For example, there are three independent features (data flows) in the code segment "\(a=0;b=c+d;call(c)\),". Thus it is difficult for the model to properly encode it into a single vector representing its function or semantics. Splitting data dependency graphs (DDG) may solve this problem, but it is also a difficult task. Worse still, the DDGs of LPL and HPL are quite different because of compiler optimization.

**Our approach.** In this paper, we propose an NN-based decompilation framework called NeurDP1. _NeurDP_ uses a neural network model to translate LPL into an optimized IR (IR decompiler) to address C1 instead of directly translating LPL into HPL. As we know, the compiler first generates the intermediate representation (IR) code during the compilation process and performs most of the optimization strategies on the IR. Therefore, the structural differences between the optimized IR and LPL are much more minor than those between HPL and LPL. Compared to previous end-to-end neural decompilers, _NeurDP_ can cope with the decompilation problem of compiler-optimized LPL. Finally, _NeurDP_ converts IR statement to HPL statement directly.

Footnote 1: NeurDP (Neural Decompilation)

Specifically, to train a well-performing IR decompiler model, we design a splitting technique called Optimal Translation Unit (OTU) to address C2. _OTU_ splits BBs into smaller pairs of LPL and _HIR_ fragments. The statements in each fragment have data dependencies and can be synthesized into one feature. _OTU_ helps build a high-quality training set for our NN model.

To evaluate the accuracy of _NeurDP_, we use several programs randomly generated using our tool which is developed by cfile (Zhu et al., 2017) and regular expressions, including 500 lines of code. Since our goal is to boost the neural network's ability for decompilation, we compare _NeurDP_ with related studies using neural networks (e.g., Coda (Coda, 2018) and Neutron (Beng et al., 2019)). Experimental results show that _NeurDP_ is 5.8%-27.8% more accurate than Coda on unoptimized code. Moreover, _NeurDP_ can handle compiler-optimized code well, while Coda is incapable of action. _NeurDP_ can decompile optimized binaries with 45.21% higher accuracy than another neural decompilation Neutron (Beng et al., 2019). According to our evaluation, the introduction of _OTU_ and IR mechanisms in our model improves the accuracy by 4.1%-71.23% compared to using the model directly in the optimized code.

**Contributions.** Our main contributions are outlined below:

\(\bullet\) We design a novel neural machine decompilation technique. It is the first neural-based decompiler that can handle compiler-optimized code.

\(\bullet\) We design an optimal translation unit (OTU) scheme, which can help other researchers form a sound dataset for training the IR decompilation model or other applications.

\(\bullet\) We implement our techniques and conduct extensive evaluations. The results show that _NeurDP_ is much better than the state-of-the-art neural-based decompilers, especially for optimized code. We release our dataset and the NN parameters on GitHub2.

Footnote 2: [https://github.com/zjiangcogito/neur-dp-data.git](https://github.com/zjiangcogito/neur-dp-data.git)

## 2. Background

### Compilation and Optimization

Compilation translates HPL (e.g., C/C++) into LPL (e.g., machine code) that can be run on the target CPU (e.g., X86, ARM). Due to the differences between the two PLs, unnecessary information (e.g., symbols) for the CPU is usually removed. Also, in this process, optimization technologies are designed to minimize or maximize some attributes of the executable program, e.g., to reduce the program's
memory usage. Note that the execution results of the optimized target program should be the same as the original program without optimization. Optimization usually has several levels (e.g., from 00 to 03 for the compiler gcc3). The higher the optimization level, the greater the difference between the compiled binary code and the source code. Optimization makes it more difficult to generate decompiled code using deep learning models. For example, the optimization could look for redundant operations among lines of code and combine them, or calculate some operations in the compiling time rather than the running time. This would change the structure of HPL. The optimization process is usually irreversible. Also, the optimization strategies are very diverse, even for the same type of operation. For example, in Figure 1, the target program languages after optimization for the division operations can have different forms when they have different types of operands. Specifically, if the operand is variable, the translated code is sdiv. Moreover, when the operand is changed to immediate, the target code is mov, movk, small, lsr, asr, add, which does not even contain the division operation.

Footnote 3: [https://gcc.gnu.org/](https://gcc.gnu.org/)

### Decompilation

Decompilation is a technique that transforms a compiled executable program or ASM (LPL) into a functionally equivalent HPL (Sakamoto et al., 2016). As mentioned previously, to decompile code, analysts would make many heuristic rules to help lift binary code to source code (Katz et al., 2017; Katz et al., 2017; Katz et al., 2017). However, generalizing the rules is challenging since complex instruction set architectures (ISA), code structure, and optimization strategies. Experts need to summarize the code changes brought by many optimization strategies and handcraft the corresponding decompilation rules. For example, in Figure 1, using different optimization levels, the operation var1=var1/-123; could be compiled into different types of instructions, e.g., mov, movk, small, lsr, asr, add. In this case, the developer needs to handcraft the rules to analyze the data dependencies of these instructions, and determine whether these instructions represent a division statement. The situation worsens when new operations are added, or new optimization strategies are developed, introducing new rules and impacting the old ones. What is more, this may mislead a neural-based decompiler to translate the similar code small, lsr, asr, add, which does not mean division operation to sdiv. Obtaining a good model requires training on a large-scale dataset with high-quality labels. However, directly using the source code as the label for optimized binary decompilation is inaccurate due to the gap between the source code and the optimized code.

Existing decompilation tools typically design an intermediate representation (IR) as a bridge between the LPL and the HPL. While converting IR to HPL is a relatively easy task (Beng et al., 2017), the rules for translating LPL to IR rely on expert analysis and definitions. Moreover, as each tool proposes its own IR and has different definitions of micro-operations, rule-based decompilers suffer from poor generalizability and scalability. To solve these issues, researchers proposed neural-based decompilation (Katz et al., 2017; Katz et al., 2017; Katz et al., 2017). Katz et al. (Katz et al., 2017) adopted methods from NMT and formulated decompilation as a language translation task, aiming to overcome the bottleneck of rule-based approaches. Coda (Coda, 2018) and Neutron (Katz et al., 2017) are designed to learn the mapping rules automatically. The neural-based approaches bring a new idea to program decompilation. However, previous neural-based methods all learn a direct mapping from LPL to HPL or the abstract syntax trees (ASTs) of HPL. In addition, none of the current neural-based approaches can handle optimized code, mainly due to the unavailability of a high-quality dataset of optimized code.

## 3. Approach

We propose a novel neural decompilation approach _NeurDP_ that can handle compiler-optimized code. _NeurDP_ first translates LPL to _HIR_ using GNN based IR decompiler model, and then recovers _HIR_ code to HPL. Below we elaborate on the design of _NeurDP_.

Figure 1. An example showing different compiler optimization levels
### Overview

The overview of _NeurDP_ is shown in Figure 2, which aims to decompile the LPL into functionality-equal C-like HPL. And the detail of _NeurDP_ is shown in Figure 6. Considering the large gap between the LPL and HPL, we introduce an IR named _HIR_ as a bridge. IR is optimized by the compiler front end. Using the optimized IR as the model's target can reduce the difficulty of model learning since the model no longer needs to learn to reverse the optimization strategies in the compiler's front end.

In the data construction phase, we first disassemble the binary file, identify the code sections from the binary and retrieve the assembly code of all functions. Then, _NeurDP_ gets the control flow graph (CFG) for each function and the assembly code of each basic block following previous work (Kip
lie in that (i) the instructions in HPL and LPL have poor correspondence (e.g., redundant or missing operations), and (ii) each function has many instructions, making it difficult for the neural network models to learn. In order to solve the problems and facilitate effective learning, we introduce an intermediate representation (_HIR_) that has better instruction correspondence with the LPL and use _OTU_ to split the basic blocks into smaller units.

**Intermediate Representation.**_LIR_ is lifted from LPL by removing machine-related features from LPL, such as registers, designed as the model's input. To get _LIR_, we first change LPL to SSA form, then use optimization strategies similar to constant (register) propagation to eliminate as many registers as possible. _LIR_ maintains almost the same syntax as LPL (\(<\)_opcode_\(>\)\(<\)_opdes_\(>\), \(<\)_opsrc1_\(>\)...). Table 2 shows some of the syntax templates of _LIR_. For _HIR_, we extract the operands and opcodes from LLVM IR and rewrite them automatically according to the syntax (\(<\)_opdes_\(>\)=_opcode_\(>\)\(<\)_op_\(src1>\),...), which is a simplified scheme of LLVM IR. It is feasible to directly use LLVM IR instead of HPL as the model's output. However, a model that converts _LIR_ to LLVM IR instead of _HIR_ needs to learn too much additional information (like data types), which could complicate the model structure and make training such a model extremely difficult. Therefore, we choose to construct the model that converts _LIR_ to _HIR_, which is relatively simple (though training this model is still not straightforward). Table 3 lists parts of the instruction templates we use for _HIR_ and corresponding LLVM IR. Figure 3 (c) shows the _HIR_ generated by _NeurDP_.

**Optimal Translation Unit.**_NeurDP_ splits the basic block into smaller units that could let the model learn the mapping rules between _LIR_ and _HIR_ instructions easily. An unit in _LIR_ should be functionally equivalent to the corresponding unit in _HIR_. One may use a fixed-length translation unit (TU) to spill a function into units. However, the units generated in this way may not be functionally equivalent. For example, in Figure 3, the madd instruction in (b) corresponds to the computation of $mul and $add in (c). Nevertheless, the two instructions are located far away and hard to include in a fixed-length TU. Also, a large size of the TU would include unrelated instructions that cannot be paired.

We assume that a basic block is a black box, as shown in Figure 4. We find that most optimization strategies do not change the output of a basic block. We observe that the output of a basic block usually contains multiple variables whose data dependency graphs within the basic block often overlap. In Figure 4, regions with different colors corresponding to the variables a, b, and n represent their data dependency graphs. To ensure that the optimization to the data dependencies of one variable does not affect the result of other variables, the compiler usually considers optimizing the overlapped and independent parts of the DDG, respectively. Therefore, we consider that the corresponding parts in DDG of _HIR_ and _LIR_ has the same semantic. Based on this observation, we design an Optimal Translation Unit (OTU) to divide the overlapping and independent parts of each dependency path of the basic block, which consists of two steps.

Step 1: _OTU_ divides a basic block into multiple non-overlapping units. Starting from the input variables of the basic block, _OTU_ traverses the entire DDG of the basic block and marks all instructions with two or more out edges as unit boundaries. The _OTU_ obtains

\begin{table}
\begin{tabular}{c|l|l} \hline
**LIVM IR** & **NeurDP FIR** \\ \hline \hline \(<\)result -= mid- city- cop1\({}_{-}\), cop2\({}_{-}\) & \(<\)result -= mid - cop1\({}_{-}\), cop2\({}_{-}\) \\ \hline \(<\)result- = add naw naw n\({}_{-}\) cop1\({}_{-}\), cop2\({}_{-}\) & \(<\)result -= add - cop1\({}_{-}\), cop2\({}_{-}\) \\ \hline \(<\)result- = fub [fast-math flags] - city-\({}_{-}\) cop1\({}_{-}\), cop2\({}_{-}\) & \(<\)result -= fub - cop1\({}_{-}\), cop2\({}_{-}\) \\ \hline \(<\)result- = temp \(<\)comd- city- cop1\({}_{-}\), cop2\({}_{-}\) & \(<\)result -= temp \(<\)comd- cop1\({}_{-}\), cop2\({}_{-}\) \\ \hline switch -<-intty- \(<\)value-, label \(<\)default-\(\{\) [- entity- \(<\)val-, label \(<\)dest+\({}_{-}\) ] & switch -<value-, \(<\)default- [- \(\mid\)val-, \(<\)dest- \({}_{-}\) ] \\ \hline \end{tabular}
\end{table}
Table 3. HIR Syntax Templates

Figure 4. Black box of basic block

\begin{table}
\begin{tabular}{c|l|l} \hline
**Return** & **ret** & **ret x0** \\ \hline
**Unconditional Branch** & **bl** label & **bl x0, labe1[, SRC [, SRC...]]** \\ \hline
**Conditional Branch** & **cop SRC**, SRC & **b** COND, labe11, labe2, SRC, SRC \\  & **b** COND & **labe11** \\ \hline
**Store Register** & **str** SRC, **OST** & **str** DST, **SRC** \\ \hline
**Arithmetic (shifted register)** & **add** DST, SRC, SRC, [**ls1**] **JMM** & **add** DST, **SRC, SRC \\  & **labe11** & **labe1** & **labe1** \\ \hline
**Move(wide immediate)** & **add** DST, SRC, SRC & **mov** DST, **IMM2, [**ls1**] **labe1**
independent non-overlapping units based on the boundaries. After that, a DDG between units (UDG) can be constructed according to the data dependencies between statements. As shown in Figure 5 (a), the \(\mathit{OTU}\) first divides the DDG of \(\mathit{LIR}\) into five non-overlapping units. Each unit is regarded as a node of UDG, and the dotted lines are dependency edges. In the same way, Figure 5 (c) generates a UDG of \(\mathit{HIR}\).

Step 2: \(\mathit{OTU}\) partially merges the units divided in Step 1, because there are units whose out edges all point to one unit. For example, there are 2 out edges between TU1a and TU1b in Figure 5 (a). This is due to compiler optimizations, such as the division optimization in Figure 5 that causes operations on a variable to be divided into 3 units TU1a, TU1b, and TU1c. We iteratively combine such units until no unit in UDG has all the out edges pointing to the same unit. For example, in Figure 5, (b) is the result of the merging of (a).

**Training Dataset.** Since the neural model requires labeled data in the training phase, we use \(\mathit{OTU}\) to partition both the basic blocks of \(\mathit{LIR}\) and \(\mathit{HIR}\) when obtaining the training set. Due to the optimization strategies of the compiler, the CFG of \(\mathit{HIR}\) often does not match precisely with the CFG of LPL or \(\mathit{LIR}\). Inaccurate matching between the basic blocks will lead to inaccurate labeling of the training set. To avoid this problem, we choose functions that contain only one basic block and then segment them to form the training set of \(\mathit{NeurDP}\) (see Section 4). Based on our observation, optimization across basic blocks only changes the segmentation and their orders, which does not introduce new types of instructions and mappings. Therefore, the model trained on our dataset can accurately translate the \(\mathit{LIR}\) instructions in each basic block of a complex function to the corresponding \(\mathit{HIR}\) instructions. Existing rule-based decompilers (Han et al., 2017; Wang et al., 2018; Wang et al., 2018) are also implemented based on this principle.

After applying \(\mathit{OTU}\) in both \(\mathit{LIR}\) and \(\mathit{HIR}\), we try to map units of them to label dataset. We observe that their UDGs are usually isomorphic, although the DDGs of \(\mathit{LIR}\) and \(\mathit{HIR}\) may be different. Therefore, we match UDGs of \(\mathit{LIR}\) and \(\mathit{HIR}\) to pair their units and get labeled. If two nodes in UDG cannot be distinguished, we first examine their internal instructions and distinguish them by some special features, including their constants, const strings, and the address of a procedure call. For nodes that are still indistinguishable according to these features, we throw them away. We use this labeling method to ensure the accuracy of labels.

### Neural Translation

In the field of neural translation, sequence-to-sequence (seq2seq) neural networks (Krizhevsky et al., 2014; Sutskever et al., 2015; Krizhevsky et al., 2014) have achieved excellent results and have been applied in commercial products such as Google Translate (Krizhevsky et al., 2014). Therefore, previously studies (e.g., TraFix (Krizhevsky et al., 2014), Coda (Coda, 2015), and Neutron (Corba et al., 2016)) utilize such models for translation. However, these existing neural machine decompilers do not work well, especially for the optimized LPL, indicating that the seq2seq models cannot effectively cope with the decompilation tasks of LPL. The low accuracy is mainly because seq2seq neural networks do not consider the data dependencies between instructions, which is vital for the compiler to generate LPL. For example, in Figure 6 (c), the seq2seq neural networks view the \(\mathit{LIR}\) as the sequence \(<\)smu1, lsr, add3, asr, add5, lsl>, but ignore the data dependencies (e.g., \(<\)smu1\(\rightarrow\)lsr\(>\) and lsr\(\rightarrow\)add3>). So the model wrongly decompiles the result as shifting and arithmetic operations. However, the correct result is the division operation \(\mathtt{div}\).

Based on the above observation, the neural network model should capture the instructions and the data dependencies between instructions. So we choose to use Graph Neural Networks (GNN). It can capture the features of nodes (i.e., instructions) and edges (i.e., data dependencies) in DDG. Thus, the model's decompilation problem can be defined as follows: Given the \(\mathit{LIR}\)'s DDG subgraph \(G\) as input, the model outputs the corresponding \(\mathit{HIR}\) sequence, expressed as \(P(Y)=P(Y|G)\).

We adopt the graph-based neural network gated graph sequence neural network (GGS-NN) (Krizhevsky et al., 2014). We do not show the details of the model here. Figure 7 shows the model's architecture (i.e., an encoder-decoder architecture). The encoder uses the gated graph neural network (GG-NN) (Krizhevsky et al., 2014). The node initialization module aims to define the initial state of the node and perform initialization operations on the DDG. The decoder uses a long short-term memory (LSTM) network with the bridge mechanism. Considering the inputs are \(\mathit{LIR}\)\(\mathit{HIR}\) units which are not complicated, we use a 2-layer LSTM network. The global attention (Krizhevsky et al., 2014) is introduced to improve the model's performance. The token embedding (Krizhevsky et al., 2014) module is used to generate the word vector of the output sequence, and we use the

Figure 5. An example of pair matching of OTU
learnable multi-dimensional embedding vector. Regarding the loss function, we use the Kullback-Leibler divergence (Kullback and Leibler, 1944) as follows.

\[D_{KL}(p||q)=\sum_{i=1}^{n}p(x)log\frac{p(x)}{q(x)} \tag{1}\]

Based on our evaluation, our model is much more accurate (29.58% higher on average) than seq2seq neural networks. We further look into the code and find that GNN correctly captures the features of data dependencies. For the example in Figure 6, our model can correctly decompile the _LIR_ to div, which means our model is effective even for optimized code.

### Operands Recovery

Recall that the output of our model does not contain real operands. To accurately recover the _HIR_ operands, we further split the _LIR_ unit, pair _LIR/HIR_ instructions, and recover operands in each unit. In this step, we use operands in LIR to fill into the HIR. We first pair the instructions with the same semantic meanings, which can be obtained by analyzing the instructions manually. For example, in Figure 6, the _LIR_ instruction b1 has the same semantic meaning as the _HIR_ instruction cal1. So we pair them together. Note that identifying the semantic meaning of instructions is only a one-time effort. Then, for the unpaired instructions, we pair them in the order of their addresses. For example, in Figure 6, the _LIR_ instructions between Line 1 and Line 6 are paired to the _HIR_ instruction div.

After obtaining the instruction pairs, we design a data-flow-based approach to recover the _HIR_ operands. For each pair, we identify the destination operand in _LIR_ (from the node that has no output link in DDG) and use it as the destination operand in the _HIR_ instruction. Then we identify the source operands in _LIR_ (from the node that has no parents in DDG) and put them as the source operands in the corresponding _HIR_ instruction. For some special instructions in _HIR_ and _LIR_ (e.g., div and madd), we make rules to find the source operands and the destination operands. For example, in Figure 6, we map instructions 1-6 (18 operands) in the _LIR_ to instruction 1 (3 operands) in the _HIR_. By analyzing the DDG of _LIR_, we get the output variable \(x23\_2\), input variable \(x0\_5\), and \(4\) immediate \(\#0x84210843\), \(32\), \(8\), and \(31\), which are not defined inside the DDG. Operands \(x23\_2\) and \(x0\_5\) can be assigned to _HIR_ to the corresponding position. Besides, we manually make the division optimization rules to get another operand \(\#496\).

Figure 6. Neural translation process

Figure 7. Model architecture
## 4. Evaluation

In this section, we describe our experiments to evaluate _NeurDP_'s performance. Firstly, we evaluate the accuracy of decompilation tools at different optimization levels, which can reflect the ability of each decompiler to respond to the optimization strategies related to the expression and data flow in the compiler optimization. We compare _NeurDP_ with two state-of-the-art neural-based decompilers (Beng et al., 2017; Chen et al., 2018). To evaluate the efficiency of our model and _OTU_, we compare _NeurDP_ with other baseline models and other methods of splitting basic blocks. We also analyze the decompiling results of one famous open-source decompilation tool RetDec (Rendle et al., 2017).

### Experiment Setup

**Dataset.** To build the dataset, we randomly generated 20,000 functions, consisting of arithmetic and calling statements, compiled them using _clang10.0_ with optimization levels 00 to 03. By capturing the intermediate results and reversing the binaries, we got 80,000 _LIR/HIR_ pairs. Then, we use _OTU_ to split the function into smaller units for training. After removing the duplicated units and batches that were not full, we got 242,000 pairs. We randomly selected 220,000 pairs for training, and the rest 22,000 pairs were used for validation. We evaluate _NeurDP_ from the following aspects: accuracy and generalizability.

**Platform.** All our experiments are conducted on a 64-bit server running Ubuntu 18.04 with 16 cores (Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz), 128GB memory, 2TB hard drive and 2 GTX Titan-V GPU.

### Accuracy

**Metrics.** As mentioned above, the compiler's optimization changes the statements in the source code. So the decompiled code may not be the same as the original source code at the statements level, even if both codes have the same functionality. We propose a method to evaluate the compiler's accuracy in solving this problem. We consider the decompiled basic block correct if the semantics of this HPL's basic block is the same as the semantics of the corresponding LPL's basic block. Below, we will introduce our comparison method for the semantics of two basic blocks.

Basic block can be abstracted to a function \(F\), mapping the input set \(IN(B)\) to the output set \(OUT(B)\). We define them as follows: \(IN(B)=\{in_{0},in_{1},...,in_{n}\}\), where \(in_{i}\) is the \(i\)-th input of a basic block. \(OUT(B)=\{out_{0},out_{1},...,out_{n}\}\), where \(out_{i}\) is the \(i\)-th output of a basic block. \(F=\{f_{0},f_{1},...,f_{n}\}\), where \(f_{i}\) is the \(i\)-th function of a basic block, \(out_{i}=f_{i}(IN(B))\), \(OUT(B)=F(IN(B))\). We define the accuracy of a basic block as \(Acc_{B}=Count_{correct}(f_{i}^{HPL})/Count(F^{LPL})\), where \(f_{i}^{HPL}\) is the \(i\)-th function of HPL. To find the correct \(f_{i}\), we first locate the corresponding \(out_{i}^{HPL}\) in the decompiled HPL for each \(out_{i}^{LPL}\) in LPL (e.g., pointer to the same variable). For _NeurDP_, it is easy to determine whether the two outputs correspond or not since we map the variables in _LIR_ directly to _HR_ when recovering the variables in Section 3. For other decompilers, we pair outputs by manual analysis. Then we can get corresponding \(<out_{i}^{HPL},out_{i}^{LPL}>\) pairs. Given \(IN(B)\), we consider the \(f_{i}^{HPL}\) obtained by decompiling to be correct if the results of the function \(f_{i}^{HPL}\) and \(f_{i}^{LPL}\) are equal for each paired \(out_{i}^{HPL}\) and \(out_{i}^{LPL}\). At last, we define the _program accuracy_ as \(Acc=\sum_{k=1}^{N}Acc_{B}(B_{i})/N\), where \(N\) is the number of basic blocks in the program, \(B_{i}\) is the \(i\)-th basic block in the program. In the evaluation, _NeurDP_ automatically generates functions from the basic blocks, and we manually check if \(f_{i}^{HPL}\) is correct by comparing the functions from HPL and LPL. For example, in Figure 1, HPL and LPL codes of func1 all contain one basic block. We can get the accuracy of func1 \(Acc=Acc_{B}(B)/1\). The output set and input set of \(B\) in HPL are \(\{ret_{LPL}\}\) and \(\{p0\}\). The output set and input set of \(B\) in LPL are \(\{ret_{PL}\}\) and \(\{w19\}\). Then, we can get output pairs in HPL and LPL \(\{ rectif_{PL},ret_{LPL}\}\). The corresponding function of \(ret_{PL}\) is \(f=\{f_{\_}scamf_{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{ \_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{ \_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{ \_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{ \_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{ \_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{ \_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{ \_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{ \_}{\_}{\_}{\_}{\_}{\}}\). The corresponding function of \(ret_{PL}\) is \(f=(f_{\_}scamf_{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{ \_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{\_}{ \_}{\_}{\_}{\ }{\_}{
Neutron [6]). From the results, we see that _NeurDP_ outperforms both of them. We do not have access to the source code and dataset of Coda [9]. We also find that the details needed to reproduce Coda are not described in their paper. So we could neither test Coda on our dataset nor test our _NeurDP_ on their dataset. Considering that the benchmark \((Math+NE)\)[9] in Coda is generated similarly to our dataset, we directly compare the effect with that described in their paper. Coda splits the long and short sentences in the dataset into two groups for testing \((Math+NE)_{S}\) and \((Math+NE)_{L}\). Therefore, the range of Coda's accuracy on these two datasets is listed in Table 5. In addition, since Coda cannot handle the compiler-optimized LPL, this part of the data is replaced with blanks. For Neutron, we get the code and test it on our dataset. The result in Table 5 shows that Neutron does not perform as well as _NeurDP_ on our dataset, especially for compiler-optimized code. We further analyze the experimental results, where _NeurDP_ adopts _HIR_ as the model's target to cope with compiler optimization and uses the _OTU_ mechanism to divide the basic blocks into finer-grained partitions. In contrast, the previous neural-based work utilizes HPL or AST as the model's target. Source code and AST are not optimized by the compiler front-end and cannot correspond well with the optimized LPL, increasing the difficulty of model learning. Therefore, Coda and Neutron cannot cope with the optimized code very well.

**Compare with Different Neural Networks.** To understand the effect of the GGS-NN model, we compare _NeurDP_ with other models. We select three wildly used seq2seq models (Transformer [164], LSTM [55], and GRU [7]) to make a comparison with our _NeurDP_. Note that, instead of using a tree decoder, we serialize (traverse) the AST of the source code as the output of the transformer for model Transformer (AST) in Table 6. We use the same data set as _NeurDP_ to train these models separately. Note that we use Clang to extract <assembly, source code/AST/IR> as ground truth for these models. In this experiment, we use the accuracy of tokens to evaluate these models. This is because outputs of other models often have so many syntax errors that it is hard to evaluate their functionality. The experimental result proves that the GGS-NN can make decompilation results more accurate (see Section 3.3).

We further evaluate the effectiveness of the NMT model using _HIR_ as a translation target. We choose the Transformer model as the baseline and use source code, AST, and _HIR_ as the model's translation targets for evaluation on DS1. From the first three lines of Table 6, we can find that when the NMT model uses source code (SRC) or AST as the translation target (output), its effect on O1-O3 is far worse than that at O0. In contrast, the model that uses _HIR_ as the output has no significant difference in translation effects at the O0-O3, and the complete accuracy is better than the other two models. The experimental results show that using _HIR_ as the translation target of the model is highly generalizable for optimized code, which are not affected by compiler optimizations. What's more, using our _HIR_ and _LIR_ pairs splitting by _OTU_ performs better than other models.

**Impact under Different Translation Unit.** We evaluate the token accuracy of using different methods of splitting basic blocks, including code sequence-oriented _TU_ (STU) and DDG-oriented _TU_ (DTU). We select _DS1_ to evaluate the performance of different forms of TU. To verify the effect of _TU_, we choose the statement size of the _STU_ as 5, 10, and 15 on the assembly sequence. To further verify the performance between fixed-length and variable-length _DTU_, we select a fixed-length _DTU_ with a size of 5 and our _OTU_. Figure 8 shows the performance of _NeurDP_ under different forms of _TU_. The result indicates that _NeurDP_ becomes less effective in code sequences as the _STU_ increases, mainly because the longer the code the model needs to handle, the more difficult it is to translate accurately. If we do not split the basic block, the results will worsen. In addition, we find that the fixed length of _TU_, either sequence-oriented or DDG-oriented, makes the correspondence between _LIR_ and _HIR_ in the training set more ambiguous, which leads to the model's failure to learn the mapping rules. Compared with the above methods, our _OTU_ can maximize the automation of obtaining _LIR_ and _HIR_ pairs with the correct correspondence for training, thus enabling the model to learn the mapping relationship between them quickly and accurately. What is more worth mentioning is that our approach can deal with compiler optimization problems well.

**Analysis of Rule-based Decompilers.** We also evaluate the performance of one famous open-source rule-based decompiler RetDec [16], which contains over 100,000 lines of code and is a representative decompilation work. In the evaluation, RetDec does not perform as well as those three neural-based decompilers (only achieving 29%) on unoptimized binaries. When evaluated on 01, RetDec achieves 29% accuracy without debug information and 17% accuracy without any symbolic information. When evaluated on 02 and 03, RetDec achieves only 4% accuracy because mostly binaries are failed to decompile. We manually analyzed these samples of

\begin{table}
\begin{tabular}{c|c|c|c|c} \hline \hline  & \multicolumn{4}{c}{**Compiler optimization level**} \\ \cline{2-5}  & **00** & **01** & **02** & **03** \\ \hline \hline
**Transformer-SRC** & 52.93\% & 38.22\% & 39.84\% & 33.37\% \\ \hline
**Transformer-AST** & 75.79\% & 45.62\% & 44.60\% & 32.98\% \\ \hline
**Transformer-IR** & 77.18\% & 75.66\% & 74.49\% & 73.94\% \\ \hline
**LSTM-IR** & 85.40\% & 86.61\% & 85.63\% & 85.95\% \\ \hline
**GRU-IR** & 26.56\% & 21.93\% & 25.85\% & 24.19\% \\ \hline
**NeurDP** & **89.50\%** & **93.16\%** & **93.40\%** & **90.08\%** \\ \hline \hline \end{tabular}
\end{table}
Table 6. Token accuracy of different neural networks

Figure 8. Token accuracy under different forms of TU
decompilation failures and found that many errors occurred in the disassembly step due to the lack of symbolic information. The code sections could not be accurately located. In some cases, although the function entry point was found, the decompilation is broken due to some small disassembly errors. Moreover, we studied the mechanism of rule-based decompilers (Beng et al., 2017; Chen et al., 2018; Chen et al., 2019). Rule-based decompilation tools have more rules and constraints and are more sensitive to disassembly errors. A memory or stack error in the assembly will often cause the following code or the entire function to fail to decompile. In contrast, _NeurDP_ has no constraints (e.g., stack balance), so it has a certain degree of fault tolerance for some disassembly errors, such as _sp stack unbalanced_ caused by inline assembly code. It will not cause the entire decompilation process to fail. Even if the disassembly error leads to the wrong decompilation result, _NeurDP_ can still finish decompiling without triggering an error and stopping like other tools.

## 5. Discussion

**Limitations.** In this work, we propose and implement a novel neural decompilation approach, named _NeurDP_, to demonstrate that the neural-based approach copes with the decompilation problem of compiler-optimized LPL. However, _NeurDP_ still has some limitations. Firstly, the HPL statements generated by _NeurDP_ are mapped directly from _HIR_ and are mostly monadic or binary statements. For example, for an expression a = b + c * d, _NeurDP_'s outputs are two statements tmp = c * d, a = b + tmp. Such problems could be solved through data dependency analysis. Besides, the quality of HPL decompiled by _NeurDP_ is closely related to the accuracy of the LPL (assemble code). We find that for stripped binaries, the disassembly tools (e.g., RetDec) may cause errors in assembly code due to incorrect function boundary identification, especially for decompiled code, which affects the quality of our _NeurDP_'s performance. Secondly, _NeurDP_ is not completely end-to-end from LPL to HPL. The lifting from IR to HPL depends on the rules, so it is not easy to support multi-machine and multi-language. Thirdly, _NeurDP_ is a prototype system, and the dataset contains only the statements consisting of arithmetic and calling operations to integer variables. We plan to include more types of statements in future work. Finally, _NeurDP_ directly uses the existing techniques, including disassembly, reconstruction of control structures, etc. _NeurDP_ does not consider the errors introduced by these modules so these components will affect the final accuracy.

**Future Work.** We will continue to explore techniques for improving the decompilation quality of _NeurDP_ and resolve the above limitations. For example, we will eliminate some binary statements by merging expressions and reducing the redundant variables for HPL generated by _NeurDP_. The elimination of sentences will be achieved through data-flow analysis. At the same time, we will use neural-based methods to learn some patterns of statements that match developers' habits through historical experience and guide the process of merging to generate HPL that is more in line with programming habits. Furthermore, we will combine the collective capability of the-state-of-art commercial and open-source disassembly tools (Zhu et al., 2019; Chen et al., 2019), to generate high-quality assembly code. The goal is to ensure the _NeurDP_'s input is correct, which is a sufficient condition to ensure the performance of the decompiled code.

## 6. Related Work

**Rule-based Decompilation.** Rule-based decompilation techniques rely on PL experts to customize and design specific heuristic rules lifting low-level PL to high-level PL and achieving software decompilation. The current popular rule-based decompilation tools are Hex-Rays (Han et al., 2017), RetDec (Chen et al., 2018) and Ghidra (Ghira et al., 2018). Hex-Rays is a decompiler engine integrated into the commercial reverse tool IDA Pro, which is the de-facto industry standard in the software security industry. However, Hex-Rays is not open-source, and the inside technology is hard to understand. RetDec is an LLVM-based redirectable open-source decompiler developed by Avast in 2017, aiming to be the first "universal" decompiler that can support multiple architectures and languages. RetDec can be used alone or as a plug-in to assist IDA Pro. Ghidra is an SRE framework developed by the National Security Agency (NSA) for cybersecurity missions. Ghidra supports running on Windows, macOS, and Linux, supporting multiple processor instruction sets and executable formats. Although these studies have made significant improvements, they are far from perfect. Rule-based approaches are needed to manually detect known control flow structures based on written rules and patterns. These rules are difficult to develop, error-prone, usually only capture part of the known CFG, and require long development cycles. Worse still, these methods do not work well when decompiling optimized code. However, optimization is now the default option when commercial software is compiled. Unlike rule-based decompilers, the goal of _NeurDP_ is based on deep neural networks to learn and extract rules from code data automatically. Trying to break through the problem of compiler-optimized code is challenging to decompile accurately.

**Learning-based Decompilation.** Most of the existing learn-based decompilation methods (Chen et al., 2018; Chen et al., 2018; Chen et al., 2019) draw on the idea of NMT to transform the decompilation into the problem of mutual translation of two different PL. Katz et al. (2019) first proposed an RNN-based method for decompiling binary code snippets, demonstrating the feasibility of using NMT for decompilation tasks. Katz et al. (2019) proposed a decompilation architecture based on LSTM called TraFix, and they realized that the primary task of building a decompilation tool based on NMT is to make up for the information asymmetry between high-level PL and low-level PL. TraFix takes the preprocessed assembly language as input and the subsequent traversed form of C as output, which reduces the structural asymmetry between the two PLs. Fu et al. (2019) proposed an end-to-end neural decompilation framework, named Coda, based on several neural networks and different models used for different statement types. Coda (Chen et al., 2018) can accurately decompile some simple operations, such as binary operations, which is far from actual application. Unlike the above existing studies, our neural decompilation framework _NeurDP_ can decompile the real-world low-level PL code, especially the compiler-optimized PL code, into a C-like high-level PL code with corresponding functionality.

## 7. Conclusions

In this paper, we propose and implement a neural decompilation framework named _NeurDP_, which accurately decompiles LPL code to a C-like HPL with similar functionality. We also design an optimal translation unit (OTU) suitable to form a dataset for learning
algorithms better capturing the relationship between HPL and LPL. The evaluation results show that _NeurDP_ achieves better accuracy for optimized code, even compared with the state-of-the-art.

###### Acknowledgements.

 This work was supported by NSFC U1836211, Beijing Natural Science Foundation (No.M22004), Youth Innovation Promotion Association CAS, Beijing Academy of Artificial Intelligence (BAAI).
