N-Bref : A High-fidelity Decompiler Exploiting Programming Structures 
Authors: Cheng Fu
Kunlin Yang
Xinyun Chen
Yuandong Tian
Jishen Zhao
Venue:  (2021)
Keywords: Programming Language
Reverse engineering
neural machine translation
machine learning for system

Abstract: Binary decompilation is a powerful technique for analyzing and understanding software, when source code is unavailable. It is a critical problem in the computer security domain. With the success of neural machine translation (NMT), recent efforts on neural-based decompiler show promising results compared to traditional approaches. However, several key challenges remain: (i) Prior neural-based decompilers focus on simplified programs without considering sophisticated yet widely-used data types such as pointers; furthermore, many high-level expressions map to the same low-level code (expression collision), which incurs critical decompiling performance degradation; (ii) State-of-the-art NMT models(e.g., transformer and its variants) mainly deal with sequential data; this is inefficient for decompilation, where the input and output data are highly structured. In this paper, we propose N-Bref, a new framework for neural decompilers that addresses the two aforementioned challenges with two key design principles: (i)N-Bref designs a structural transformer with three key design components for better comprehension of structural data – an assembly encoder, an abstract syntax tree encoder, and a tree decoder, extending transformer models in the context of decompilation. (ii) N-Bref introduces a program generation tool that can control the complexity of code generation and removes expression collisions. Extensive experiments demonstrate that N-Bref outperforms previous neural-based decompilers by a margin of 6.1%/8.8% accuracy in datatype recovery and source code generation. In particular, N-Bref decompiled human-written Leetcode programs with complex library calls and data types in high accuracy.

Under review as a conference paper at ICLR 2021
N-BREF: A HIGH-FIDELITY DECOMPILER EXPLOIT- ING PROGRAMMING STRUCTURES
Anonymous authors Paper under double-blind review
ABSTRACT
Binary decompilation is powerful technique for analyzing and understanding software, when source code is unavailable. is a critical problem in the com- puter security domain. With the success of neural machine translation (NM'), recent efforts on neural-based decompiler show promising results compared to traditional approaches. However, several key challenges remain: (i) Prior neural- based decompilers focus on simplified programs without considering sophisti- cated yet widely-used data types such as pointers; furthermore, many high-level expressions map to the same low-level code (expression collision), which incurs critical decompiling performance degradation; (ii) State-of-the-ee NMT models (e.g., transformer and its variants) mainly deal with sequential data; this is inef- ficient for decompilation, where the input and output data are highly structured. In this paper, we propose N- new framework for neural decompilers that addresses the two aforementioned challenges with two key design principles: (i) N-Bref designs a structural transformer with three key design components for bet- ter comprehension of structural data an assembly encoder, an abstract syntax tree encoder, and a tree decoder, extending transformer models in the context of decompilation. (ii) N-Bref introduces a program generation tool that can control the complexity of code generation and removes expression collisions. Extensive experiments demonstrate that N-Bref outperforms previous neural- baared decom- pilers by a margin of 1/1. 88 accuracy in datatype recovery and source code generation. In particular, N-Bref decompiled human-written Leetcode programs with complex library calls and data types in high accuracy.
INTRODUCTION
Decompilation, which is a process of recovering source code from binary, is useful in many situa- tions where it is necessary to analyze understand software for which source code is not available. For example, decompilation is highly valuable in many security and forensics applications (Lin et al.) 2010): [ee et al. (201) lT: Brumley et al. (201T)). Given a binary executable, an ideal decompiler generates the high-lew level program that preserves both the semantics and the functionality of the source code. However. this process is difficult as the data structure and semantics are largely destroyed or obfuscated during the compilation. Inspired by remarkable performance in neural machine transla- tion (NMT) tasks (Liu et al. (2019); Vaswani Dong & Lapata (2016)), recent works (Fu et al. (2019): Katz et al. (2099) leverage NMT model for neura decompilation and achieve promising performance on small code snippets.
al.) (2017); Dai et al. (2019); Devlin al.. (2018);
To make neural-based decompilation useful in practice, many challenges remain: (C1) Current state- of-the-art neural architectures for machine translation transformer (Vaswani al.] (017)) or its variants (Dai et al.] (2019); Devlin et al. (2018): Liu et al. (2019)) focused on sequential data (c.g., language), while neural decompilers deal with data with intrinsic structures (e.g., tree/graph) and long-range dependencies. (C2) The main decompilation task consists of many sub-tasks (e.g., datatype recovery, control/dataflow recovery). Training one neural network cannot solve them all. (C3) Practical data types (e.g., pointers) not modeled and compiling configurations need to be known beforehand (Fu et al. (2019)). (C4) Due to lack of unification in terms of library usage, variable type, and/or control-flow complexity, simple crawling from public repositories does not
N-Bref is the abbreviation for "neural-based binary reverse engincering framework"

---

Under review as a conference paper at ICLR 2021
work well. Source code of different styles can be compiled into identical binary code (i.e., "expres- sion collision" or EC) and yield issues when evaluating decomplied code against original source code. To our best knowledge, code generation toolkit with configurable code complexity exists.
In this paper, we present N- N-Bref. an end-to-end decompile the source code to assembly. For (C1), we design back-bone structural transformer by incorporating inductive Graph Neural Networks (GNNs) (Hamilton et al. (2017)) to represent the low-level code (LLC) as control/dataflow dependency graphs and source code as Abstract Syntax Tree (AST). To better model long-range correlations in the structural representations, we add a graph neural network after each of the self-attention layers in the transformer. The AST decoder expands the AST of the source code in a tree fashion to better capture the dependency of each predicted node. Also, we adopt memory augmentation (Cornia et al. (019)) and new tokenizing methods to improve the scalability of our neural networks with the growing size of programs. The backbone network is learned to iteratively generate AST for source code from structured representation of assembly.
decompiler framework that learns to
For (C2) and (C3), we decouple decompilation into two sub-tasks: data type solver (DT-Solver) and source code generator (SC-Gen), both use the same backbone structural transformer with dif- ferent parameters. The output of the data type solver is used as the decoder input of the source code generation. For (C4), we design dataset generator to generate training data, test and analyze the performance of different design principles across configurable code complexity. Different from conventional dataset generators (Yang et al. (2011) IntelC++compiler (2017) ) used in programming language studies, our generator produces similar code styles as those written by human program- mers, has unified source code representation that avoids EC, has configurable complexity and data types to facilitate factor analysis, and is specifically designed for learning-basee methodologies.
Extensive experiments show that on our new metrics, N-Bref outperforms transformer baseline/pre- vious neural-based decompiler (Fu et al. (2019) by 3.5% and 5.5%/8. 8% in data type re- covery and source code generation tasks, respectively. Furthermore, on 5 jumman-witte Leetcode solutions, N-Bref shows 4.1 4.1%/6.0 and 6.0%/9.799 margins over transformer/previoos neural de- compiler in data type recovery and source code generation, respectively. We also perform a compre- hensive study of the design component in neural-based decompiler across different dataset configu- rations. In summary, this paper makes the following contributions:
We construct an end-to-end decompilation system by integrating LLC Encoder, an AST encoder, an AST decoder, and a set of novel embedding methods in a holistic manner. Our new architectures bridge the gap between low-level code and high-level code by transforming both of them into a graph space.
We perform a comprehensive analysis of the influence of each neural-based decompiler design component to the overall program recovery accuracy across different dataset configurations. We corroborate the design performance on various generated benchmarks and Leetcode tasks.
We boost decompilation performance by decomposing the decompilation process into separate tasks, data type recovery and AST generation. In addition, we present corresponding new metrics to evaluate data type recovery and source code generation.
We develop the first dataset generation tool for neural-based decompiler development and testing. It randomly generates programs with configurable complexity and data types; it also unifies source code representation to prevent "expression collision".
2 PRELIMINARIES OF DECOMPILERS
Decompilation takes an executable file as input and attempts to create high-level source code that are more semantically meaningful and can be compiled back. Figure [ shows low-level code snippet disassembled from a stripped binary and the corresponding high-level program.
A commonly used low-level code (LLC) is assembly (ASM). An assembly program is a sequence of instructions that can be executed on particular processor architecture (e.g. MIPS, x86-64). The first token for each instruction is called an "opcode", which specifies the operation to be performed by the instruction. Many instructions in a program operate on processor registers (a small amount of fast storage in the processor) or instant values perform arithmetic operations, such as shift- ing (c.g.shl, shr), floating-point multiplications (c.g. mulss), etc. Other instructions include (1)
Complete assembly code and graph are shown in Appendix H
2

---

Under review as a conference paper at ICLR 2021
char foo (loet 1n1
char L2[4]:
function
2
short 3=
float 4 :xap11:
4000
aimt Compond
binary
type
[[(surchu (L2, LL2
stmi voriable reference
operator
Jeise
LO=14"L0:
if sime
9 return IZ:
L2[La]=7;
Type Recovery
Generation
declaration
local
variable parametera
(4)
leog -220hhl) nox
-Lyyp,, samo smmno 38j/pp
Siarren Saudo
Desinadion Wode
opoodd
mowl edi, esi
move) cal
me
A.:
Jmp .13
kmm2
atrchrSPPLT
nov noLD
1100pp) can [12
ripp
mp
movi
movb
movi
SkymppaammD
$0
data flow edge
instruction 50 structure
control-llow odiee
An example of (a) source code to AST conversion. Note that the pseudo 'statement" or 'stmt" nodes are added by the compiler during AST conversion. (b) assembly (x86-64) to graph
Figure 1:
memory instructions that load (Figure lb) Line 1) or store (Line 9) data from memory/register to register/memory: (2) branch instructions that conditionally (Line 6) or unconditionally (Line 10) redirect program execution to a different sequence.
Each instruction has certain internal structure, depending on the opcode. For example, in Line 8 of Figure the first operand is floating-poin point value in the memory and multss multiplies the value with the destination register (Imm0) and stores the value back to 2mm0. Besides. connections also exist between instructions: (i) branch instructions (e.g., je, jmp) reveal the "control flow' of the high-level program; (ii) the register which stores the new value of mullas (Line 8) is consumed later source register (Line 9). These data movements reveal the 'data flow' of the program. In this paper, we formulate the low-level instructions as graph using the instruction structure, control-flow and data-flow between each nodes shown in Figure lib..
High-level programming languages can represented its equivalent abstract syntax tree (AST) (Baxter et al. (1998) during code generation (Figure aa). This representation has many advantages over its sequential representations: (i) adjacent nodes are logically closer in AST com- pared with sequential representations, (ii) error propagation in sequential expansion can be alleviated in tree decoder, and (iii) AST grammar helps prevent error predictions.
N-BREF OVERVIEW
In this section, provide an overview of our design components with an illustrative example. Figure D shows an example of the prediction procedures.
The Backbone Structural Transformer. Our structural transformer has three components: (1) LLC encoder, (2) AST encoder, and (3) AST decoder (Detailed in Sec. 4. The LLC encoder takes the low-level instructions converted from binaries using disassembler as input. AST encoder takes the input of previous (partial) AST, and the predictions of AST decoder are AST nodes, which can be equivalently converted to the high-level program. As mentioned earlier, we formulate input low-level code into graphs and high-level code into tree structures.
As the AST of the data declaration is very distinct from the rest of the code (Figure[aa) in high- level program, decompose decompilation into two tasks: data type solver (DT-Solver) and source code generator (SC-Gen). Both have the backbone structural transformer.
Step
t+2
Terminal node
LLC
AST Encoder
Encoder
non-Terminal node
AST Decoder
Prediction
Terminate!
Figure 2: An example of prediction procedures in N-Bref pipeline. AST is expanded in a breadth-fiin manner.
Prediction Procedure. Figure 1 shows an example of the code recovery process of N-Bref. The assembly graph and high-level AST is the input of LLC encoder and AST encoder. The input of the AST decoder is the tree path from the root node to the expansion node. Initially, a single root-node fed into the AST encoder/decoder. Once new node is generated from decoder in each step,
3

---

Under review as a conference paper at ICLR 2021
Table 1: Hyper-parameters in data generation
Description
Block depth (hdepth)
maximal level of nested control dependencies ("loup" or "branches))
Block size (buize)
maximal mumber of children for a component statement (See Figure Tai) for each code block.
Block number (bmmm)
muximal number of times to generate the control blocks with depth of bleyok maximal depth of each line of code
Expression complexity (En)
update the AST and use it the AST encoder input in the next prediction step. We expand the AST in breadth-first (BFS) fashion.
AST contains explicit terminal nodes, which tokens with no child, such as registers, numeries, variable references and variable types. Non-terminal nodes (e.g. binary operator '=") must have children, otherwise there is a syntax error. The branch stop expansion when its leaf nodes are all terminal nodes. Note that during training, we apply 'teacher foreing' by attaching the correct node label into the AST encoder at each step. (See Appendix E for formal algorithm)
Cascading DT-Solver and SC-Gen. As shown in Figure D we divide the AST into two parts: (i) AST of data type and (ii) AST of main code body. Each part generated using DT-Solver and sC-Gen respectively. This method allows the network to focus each task individually and resolves more complicated data types. During testing, DT-Solver first generates the left part of the AST in Figure T then the SC-Gen will continue the expansion from this intermediate results. During training, the initial data type input to the SC-Gen is the program golden.
METHODOLOGY: DATA GENERATOR
In this section, we detail the data generator designed N-Bref. We design data generator so that has no expression collision (EC). For example, 'unary" operators converted to 'binary' operators (i++ and i=i+l) and all the 'while' loops are transferred into 'for' loops. Experimentally, we observe that data generator free of EC and performance improves. EC hurts the performance because (1) the same input assembly can be mapped to multiple equivalent outputs; semantics result in extra token dimensions; (3) the training under EC is both difficult and slow due to label adjustment at runtime.
(2) extra high-level
The generator is configurable with multiple hyper-parameters (Table D which makes it easy for N-Bref to accommodate with different decompiliation tasks. It also allows us to analyze which components in the pipeline improve the scalability and performance (See Sec. 6
For each data point in the dataset, we sample beepth biize and 6yum with a uniform distribution between and user-specific maximal value (Table(]). The number of sampled variables (var of program is related to bi and Edephh following Poisson Distribution (Equations in Appendix D). The generator also takes the libraries libú, that are pre-detined by the user potential generated components. If a function call is sampled, the data generator will filter out the variables that do not match with its input/ output types (line 4 Figure (a)).
In summary, bdepth and Eg control the difficulty of control/data flow, while besze and bnum con- trol the length of the code. For example, the code snippet in Figure T[a) has configuration of [Fe, bdepth, baize, Drum) [2, 1, 1, 1]. Note that in N-Bref, the program is compiled using gec with optimizations. Previous works (Brumley al. (2013): Lee al.] (2011); b [in al. (2010) also disabled optimizations. because many optimizations change variable types and rewrite source code (e.g. loop-invariant optimization) which will result in unfair accuracy evaluations.
100
Self Aftention
Graph MN
Graph NN
MultiHoas
M Minnii
Hite
Assembly
Tree
Self Alff-Attmiion
X
Grappe Morthoo
Hau
H
AST Encoder
LLC Eiscoder
AST Decodar
M.1
AST Tree
X
Figure The backbone neural architecture design for DT-Solver and SC-Gen. N1,N2,N2 indicates the number of times to repeat the block in the architectures.
4

---

Under review as a conference paper at ICLR 2021
5 METHODOLOGY: PIPELINE
Here, we present the details of the backbone structural transformer in N-Bref.
LLC Encoder. As shown in Figure [b). we first formulate the assembly code as graphs by adding
the following edges between nodes: (i) between the 'opeode' node of branch instructions and all their possible next instructions (control flow). (ii) between instructions 'opcode' and its 'operands' (i.e., registers/ / instant values). (iii) between the same register node of different instructions (register read-after-write, which indicates the data-dependency. Different from (Shi et al. (2019), we do not add redundant pseudo nodes indicates node positions, because this method not scalable for long programs due to the exponential size of input using pseudo nodes. Instead, we directly concatenate all one-hot meta-features of node together, namely the register / instruction type (var, / (ins). position in the instruction (Npoe), node id (fzzd) and numerical field (Nnum) during tokenizing process. If the token is number, we represent it in a binary format to help the transformer generalize to unseen numerical values (e.g., 12 is represented as 7zum= [0, O, 0, O, 1, 1, O, O]. 16-by-1 vector). This representation method can greatly reduce the length of the transformer input and make the decompiler more robust for long programs.
The tokenized vector for each node (h = [var:; insr; Rips; ThMock; Yhid; Apum Aazere [", 1',00 Rdx1) are fed into an embedding graph neural network (GNN) GraphSAGE (Hamilton et al. (017)) ) an inductive framework that can generalize representations for unseen graphs. We pad Azeros to the input vector ho to match the GNN output feature size Note that to better represent the data flow in assembly code, we leverage character embedding for registers (var, = c For instance, if the register is Sraz, we would break it into 'r', 'a', 'x'. That is because the naming policy of x86-64 (also MIPS) hardware registers indicates their underlying connections $caz is the first 32-bit of register Srar and Saz/Sah is the first 16-/8-bit of register Seax.
After getting the assembly graph V and each node's representation ho, each node (where E V) aggregates the feature representations of its sampled neighbors:
h'v(w) mar(a marraaWW' h", + +b)) Yuu E (v))
(1)
Here, the hi, represents the hidden state of node's neighbours and N(u) represents the set of neighbours of the node v. W is a trainable matrix (d-by-d) and b' is a bias vector, a represents the sigmoid activation function. We choose to use an element-wise max-pooling (max) as aggregator to collect the states from neighbours. The aggregation vector is concatenated with the current state of the node h4 as the input to a fully-connected layer to get the new state:
h = W (hh,, (x)(
(2)
Here, W E Rdx2d is the trainable embedding matrix and h+t (a d-b-- vector) is the output of the current layer of GNN. [, is the concatenation operation.
AST Encoder. The AST encoder encodes the AST tree from the AST decoder to guide future tree expansions. In this work, we treat the AST tree as graph (V) and embed it using GNN in the same way as LLC encoder following Eq. [T. The input of the GNN includes meta-features of the tokenized AST node feature feat) and boolean indicating whether the node is expanded in this step (Nezpond)) The input vector h, [Reppand: feat]] (u E (h()) is added with the positional encoding result:
V) is fed into a GNN and the output
Ro = hr W Wi + W2hhde
(3)
Here Adepth and hide are the one-hot vector of the node's (v) depth in the tree and node's position among the parent's children. W1 and W2 are trainable matrices for embedding. The output hidden states fed into our designed self-attention module /Sec.5.Il. At the end of the AST encoder, we integrate the AST encoder output (Hast) and LLC encoder output (Hua) using an additional multi- head attention layer with Hise input K and V, and Hast as Q (Figure 3) The result (Hazz) will be used for networks downstream.
AST Decoder. querying node of the AST decoder is represented as a path from the root to itself using the same methods proposed in (Zhu et al. (2019); Chen et al. (2018a)). This method reduces the length of the input into the decoder. The results from the level code encoder Hiic and the AST encoder H'st are integrated into the decoder using two attention layers following Eq. (4) as shown in Figure The output of the AST decoder is mapped into its output space with dimension d,, x 1 using another fully- connected layer. d, is the number of possible tokens of high-level code. After the new prediction is generated, we update the AST tree for the next time step (Figure. 2
The AST decoder takes the encoding result from the previous stage as input. The
5

---

Under review as a conference paper at ICLR 2021
5.1 MEMORY AND GRAPH AUGMENTED SELF-ATTENTION MODULE
Decompilation is hardly word-by-word translation like natural language. Each individual token in low-level code or AST tree must be interpreted in the context of its surrounding semantics. To capture the prior knowledge embedding, we leverage two additional modules (i) memory-augmentation (ii) grapt-augmmenatiion in transformer attention. The formal descriptions are shown below.
programming structures and emphasize the node connections after
Memory augmentation. We propose a memory-augmented attention layer similar to the method in (Cornia et al. (2019)) The imput prior information trained and does not depend on the input data. Traditional transformer's building block is self-attention layer which takes three sets of vectors (queries Q, keys K and values V) as input. The layer first computes the similarity distribution between Q and K and use the resulted probability to do a weighted sum on V. (equations in Vaswani et al. (2017)) In N-Bref, we add two trainable matrices for each head as an extra input to the transformer for memory augmentation. And the computation is adjusted to:
H- MultiH ea K, V) Concat(heade ... head, W
(4)
Q'KT
head,- Attention Q¹, K V") softmarl Vd
)
(5)
where Q = QW V = [VWes vi: Moi), K = [KWAs, Mas]
(6)
Here, is the number of parallel attention heads. (W Wk..W) are trainable matrices with a dimension of d x t. W has the dimension of d x d. Moi, Mai E Rd Xd and dm controls the number of slots of the memory. Note that we remove the positional embedding in the original transformer for LLC encoder as the position information is integrated into GNN embedding.
Graph augmentation. We propose to emphasize the connections of assembly nodes after at- tention layer. The output of the multi-head attention layer 8 can be viewed as a matrix H2 = [h000 he ",...,,.,,,h ....,,..N, convert H, back to graph structure using the edge information of assembly code. The new graph with connected hidden states is the input to an additional GNN layer using Eq. 2 after each self-attention layer.
H RdxN where N is the number of nodes in the assembly graph. We first
6 EVALUATION
6.1 EXPERIMENTAL SETUP
We assess the performance of N-Bref on various benchmarks generated by our dataset generator with various difficulty levels and Leetcode solutions (Problems (2017); details in Appendix B) as shown in Table 2 This binary is disassembled using the GNU binary utilities to obtain the assembly code. To generate the AST for C code, we implement the parser using elang compiler for python. Our dataset generator is built on csmith (Yang et al. (201)), which is a code generation tool for compiler debugging. The original tool the implementation for decompilation tasks. For the neural network setting discussed in Figure 3 we choose [N1, N2, NV3
suitable our cases and thus N-Bref modifies most of
2, 2, 2, (t is the number of heads used in N-Bref), an embedding dimensionality d = 256, and memory slots dm = 128. The training/evaluation is implemented using Pytorch 1.4 and DGL library (Wang et al. (011)). Details about the training parammers and settings are included in Appendix A.
Complexity arguments and benchmarks. This section describes the tasks in our evaluation. We randomly generate 25,000 pairs of high-level programs and the corresponding assembly code in each task for network training (60%), validation (20%) and evaluation (20%). We mainly focus on tuning bäepth and brum (see Table. [ We set E. 3, baize = 3, bias 2 and test lib,. with different complexities: (i)-<ath.hh > and <ttiin..t.. Function recursion is allowed for code generation. Other than function calls, normal expressions ("+,- also possible operators during code generation. (Code examples in Appendix C.)
\. ll. >, &,, == etc.) are
Metrics. We evaluate the performance of N-Bref using token accuracy. For evaluation of SC-Gen, we expand the decompiled AST from the root to match the structure of the golden AST (ASTc). The token accuracy is calculated as:
acc Tuun (AST ASTa)
num num(ASTe) (ASTc)
We also show the evaluation result using graph edit distance (Sanfelu & Fu (1983) without enfore- ing the match between the decompiled AST and AST on the graph generation in Appendix G.

---

Under review as a conference paper at ICLR 2021
The metric is fair to evaluate decompilation tasks as we remove all the EC. 7 able to evaluate sequence output by treating the sequence as a tree.
have two metrics: (i) macro accuracy (AcCmac) and (ii) micro accuracy (Acomic). The Acemae treats unsigned and signed variables as the same. This is because unsigned and signed variables have difference in assembly code except through hints from type-revealing functions (for example, the return value of strlen() () must be an unsigned integer). Note that we do not recover numerical values that are directly assigned to vari- able and we replace them with token 'nam'. These values exist in the stack memory or assembly instructions which can be resolved after the AST correctly recovered using additional analysis methods. One of our future works can leverage the pointer network (See et al.) 2017) to directly copy numerical values to the output.
For DT-Solver,
6.2 RESULTS
Performance impact of each design component. To study the effectiveness of potential design principles, we perform a thorough sensitivity study as shown in Figure
In SC-Gen, we observe that with the growth of code length and complexity, each component in N- Bref preserves more performance compared to the baseline transformer. The transformer with LLC encoder shows the least performance degradation when complexity and length increase (as shown by the slope). This is because the GNN in N-Bref connects instructions that are distant from each other to alleviate the performance drop. By expanding the source code into tree structure (AST encoder+decoder), the result shows that it also prevents the accuracy of degradation.
For DT-Solver, increasing basse improves the performance, because short programs do not have enough semantics to identify variable types. Also, the performance declines when increasing the program complexity (ddepen), and we assume that is because wiring control-flow complicates the analysis of data-flow. Traditional decompiler REWARD shows large performance drop along the axis of bdepth. That is because the dynamic analysis in REWARD is for a single control path. As such, it has limited performance among complex control-flow We also tested many other design options but they cannot achieve better scalability and performance empirically compared to N- N-Bref.
AST Generation
Type Recovery
Trans LLC enc
Trans AST enc dec
Trans
Reward
00
0.9
acc
0.85
0
0
0.8
60g Ddg
0
0.7
0.75
3
2
3
2
1
size
depth
size
depth
Figure 4: Sensitivity analysis of each design component over dataset complexity for <mathhh>> Each sample trained for 10 epochs for simplicity. 'Trans' Refers to the baseline transformer.
Comparison to previous works. N-Bref yields the highest token accuracy across all benchmarks 19.11% on average) as shown in Table in both data type recovery and AST generation. N-Bref en- genders 5.5% and 8.8% margin over hansformer-baseling and Ins2AST, which is a previous neural- based program decompiler (Fu et al. (2019).. The encoder in Ins2AST leverages N-ary Tree LSTM, which cannot collect information for instructions far apart but logically adjacent. Our LLC encoder, on the other hand, leverages GNN embedding and graph augmentation to emphasize node connec- tions. We do not show the results of traditional decompilers (RetDec (2017); Raax (201 7) as they do not preserve any semantics and achieves very low token accuracy using Eq. (Examples of traditional decompilation results are shown in Fu et al. (2019)).
For type recovery, N-Bref also achieves 3.55% / 6.1% / 30.3% average margin over transformer,
Ins2AST, and REWARD respectively. Traditional decompiler REWARD leverages type-revealing instructions and does not consider other low-level representations. Also, REWARD focuses single path in the program executed using dynamic analysis. As such, they cannot handle control flow properly. N-Bref uses static analysis and considers all paths during execution.
7

---

Under review as a conference paper at ICLR 2021
For baseline transformer and N-Bref, also present the Acemie in parentheses of Table 2 The gap between Acemae and Acemie is reduced when the program gets longer (reduced from 28.5% to 20.2% for <math. h> using N-Bref). That is because longer program have more type-revealing in- structions/functions which can help the network to identify data types ('unsigned/signed" correctly. Also, N-Bref shows higher tolerance the complexity and length growth compared other works. For lib,n =<ttrigg h>, the token accuracy drops by 6.1% % from the easiest to the hardest settings compared 9.5% 8.2% accuracy drop for baseline transformer and Ins2AST, respectively. That is because GNN can gather information from adjacent nodes for large assembly graphs. Also, AST decoders can effectively prevent error propagation through tree expansion when the souree code grow larger, unlike sequence generation where early prediction errors affect the later nodes.
We also select 5 Leetcode Problems (2017) solutions in C as an auxiliary test dataset and train a new model with the complexity of (bdepth = bsize 4) using <string. h>> library. The result shows N-Bref able to recover real benchmarks and achieves 6% / 9.7% margin over transformer and previous neural-basee decompiler. This means N-Bref is able to generalize to human-writin code. The complexity of datasets we generate can cover real-world applications.
Table Accuracy (%) comparison between N-Bref and alternative methods in (a) type recovery, and (b) AST generation. Ins2AST is previous neural-bass program decompiler (only code sketch generation stage).
REWARD (Lin et al. (2010) a traditional framework for type recovery. Lang2logic (Dong & Lapata 2016)
sequence-to-tree translator. The baseline is the transformer.
(166, M
(a) Data Type Recovery Accmael Aecrmis)
AST Generation (token accuracy)
REWARD
buseline
lang2logii
Ins2AST+an T+ait
N.Brel
baseline line
Imngle
Ins2AST+ai
N.Brel
(,Tt
85.1
96.6 (70.2)
92.1
94.1
99.6 (71.1)
90.3
84.3
94.5
(math.2,2)
66.2
94.1 (71.4)
88.6
91.3
97.3(72.5)
87.1
81.5
85.6
92.2
(math.3.3)
53.1
91.9 (73.4)
88.3
95.3 (75.1)
84.0
77.8
89.5
[.1
82.4
(71.6)
91.1
92.9
(73.3)
88.6
80.8
85.1
92.9
(str..2)
63.1
93.1 (72.5)
90.8
(74.9)
84.3
(53r,3.3)
$0.9
91.5 (73.6)
84.8
88.6
95.3 (75.4)
79.1
70.3
76.9
86.8
leetcode
73.3
91.9 (73.8)
89.1
(75.9)
73.1
88.3
Table 3: Ablation study of N-Bref on AST generation. '-ensemble" refers to disable the separation of data type recovery and AST generation.
(lib, baizn; bdepttt)
-GNN after attention
node representation
-positional encoding
-memory augmentation
ennsmblee
N-Bref
math.2,2
91.0
90.5
92.0
91.1
90.3
92.2
math.3.3
88.4
87.6
89.0
87.9
87.3
89.5
str,2,2
89.7
88.7
90.0
88.9
88.3
90.6
str,3.3
85.8
85.2
86.0
84.5
83.2
86.8
Ablation Study. Table 3 shows the ablation studies of techniques in N- N-Bref. Graph augmentation
in LLC and AST encoder (1*t column) helps increase the accuracy by 1.1%. Depth and child index positional encoding improve the performance by 0.53%. When replacing our method with Ahmad al. (2020) for positional encoding. accuracy has 0.23% drop. The 'node representation refers to character embedding for assembly registers, concatenation of meta-fcatures (Details in Sec. 55) Removing these techniques leads to a 1.8% accuracy drop on average. Memory augmentation helps to capture the prior knowledge of the code structure and removes it shows a 1.7% performance drop.
Also, splitting the decompilation task into two-part shows 2.5% improvement accuracy.
RELATED WORK
Data Type Recovery and Program Decompilation. There has been long line of research
verse engineering of binary code (Cifuentes (1994); Emmerik & Waddington (2004); Brumley et al.)
(2011) Bao et (2014;; Rosenblum et 2008); Yakdan et al. (2016)). Commercialized decom- pilers Hex- Rays RetDec (2017) do not care about semantics of the code which means their recovered code is very distinct from source code (see examples in Fu et al. (2019)) For type recov- ery, traditional methods (Lee et al. (011)) [in et al. (2010) leveraged the type-revealing operations or functions calls as a hint to inference variable types. These methods incur accuracy drop when there is not enough type-revealing semantics. N-Bref proposes learning method which can collect more finengraieed information and achieve better accuracy in type inference. For control/data- flow recovery, Fu et al. (2019); Katz et al. (2099) propose neural network methods for decompilation. However, both works are based on a sequence-tor pruuence-to-sqquene sequuenc neural network and tested on simple programs. N-Bref leverages structural transformer-basee model that achieves better results.
8

---

Under review as a conference paper at ICLR 2021
Neural Networks for Code Generation. Neural networks have been used for code generation in prior works (Ling et al. (2016): Yin & Neubig (2017); Rabinovich et al. (2017); Yin & Neubig 2018 ) These prior efforts are different from decompilation task the imput is input-output
pairs (Chen et al. (2019) 2017), description of the code usage (Zhu et al. (019)), ), or other domain- specific languages (Nguyen et al. (2013)). The abstract syntax tree (AST) was used in these cent works (Chen et al. (2018b); Yin & Neubig (2018)) Yet, most of the works leverage the Tree LSTM (Tai al. (2015), ; Dong & Lapata (2018)) or Convolutional Neural networks (Chen et al. (0188a) N-Bref demonstrates the effectiveness of transformer in the decompilation framework.
Neural Networks for Binary Analysis. There is significant body of work on binary analysis using neural networks, such predicting execution throughput (Mendis al. (20T8)), guiding the branch predictions (Shi et al. (2019)) program analysis (Ben-Nun et al. (2018) and verification Li ct al. (2015). Most of the works using RNN to encode binary or assembly code (Mendis al. (2018); Ben-Nun et al. (2018). (Shin et al. (205)) proposes to use RNN to identify function entry point in binary. GNNs were used some of these works to encode memory heap information (Li et al. (2015) assembly code (Shi et al. (2019). but the original representation methods are not scalable as they added many pseudo nodes and the node representation not suitable for the transformer. iHe al (2018); Lacomis et al. (2019) use naive NMT model to predict debug information and to assign meaningful names to variables from binaries, yet they did not leverage the structural programming information. Many designs in N-Bref are easy to integrate with various neural- -asddd binary analysis tasks where the input is also low-level code.
8 CONCLUSIONS AND FUTURE WORK
In this paper, we present N-Bref, an end-to-end framework that customizes the design of a neural- based decompiler. N-Bref designs dataset generator that removes expression collision and gener- ates random programs with any complexity configurations. N-Bref disentangles decompilation into two parts- data type recovery and AST generation, and incorporates new architecture to facilitate structural translation tasks by integrating structural encoder/decoder into the transformer. New em- beddinggrepreesntation techniques help to further improve accuracy. Experiments show that N-Bref outperform previous decompilers and the state-of-the-at transformer.
Mcanwhile, we observe that many other challenges remain, for example: (i) reverse engineering binary that has been optimized or obfuscated is still challenging; (ii) directly recovering numerical values from assembly code requires more efforts. We leave these more challenging problem setups as future work.
REFERENCES
Wasi Uddin Ahmad, Saikat Chakraborty, Baishakhi Ray, and Kai-Wei Chang. A transformer-base approach for source code summarization. arXiv preprint arXiv:2005.0060 2020.
Tiffany Bao, Jonathan Burket, Maverick Woo, Rafael Turner, and David Brumley. (BYTEWEIGHT): Learning to recognize functions in binary code. In 23rd {USENIX) Secu- rity Symposium (f (USENIX) Security 14), pp. 845-80888 165-860.222 2014.
I. D. Baxter, A. Yahin, L. Moura, M. Sant' Anna, and L.. Bier. Clone detection using abstract syntax trees. In Proceedings. International Conference on Software Maintenance (Cat. No. 98CB36272), pp. 368-377, 1998.
Tal Ben-Nun, Alice Shoshana Jakobovits, and Torsten Hoefler. Neural code comprehension: A learnable representation of code semanties. In Advances Neural Information Processing Sys- tems, pp. 3585-3597, 2018
David Brumley, Ivan Jager, Thanassis Avgerinos, and Edward J. Schwartz. Bap: A binary analysis platform. In Ganesh Gopalakrishnan and Shaz Qadeer (eds.), Computer Aided Verification, pp- 463-469, Berlin, Heidelberg. 2011. Springer Berlin Heidelberg. ISBN 978-3-642-22 642-221 10-1.
David Brumley, JongHyup Lee, Edward Schwartz, and Maverick Woo. Native x86 decompilation semeatics-preserving structural analysis and iterative control-flow structuring. In Presented
using semantics preserving as part of the 22nd {USENIX) Security Symposium ( (UUSENIX) Security 13), pp. 353-368, 2013.

---

Under review as a conference paper at ICLR 2021
Bo Chen, Le Sun, and Xianpei Han. Sequence-to-action: End-to-end semantic graph gener- ation for semantic parsing. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 766-777, Mclbourne, Australia, July 2018a. Association for Computational Linguistics. doi: 10. 10.18653/1//118-10771 URL.
https: wttp//wwww.. ac web http:/anhhoooyyyyoeeeo
Xinyun Chen, Chang Liu, and Dawn Song. Towards synthesizing complex programs from input- output examples. arXiv preprint arXiv:1706.0/22 2017.
Xinyun Chen, Chang Liu, and Dawn Song. Tree-to-tree neural networks for program translation. In Advances in Neural Information Processing Systems, pp. 2547-2557, 2018b.
Xinyun Chen, Chang Liu, and Dawn Song. Execution- guided neural program synthesis. In Interna- tional Conference on Learning Representations, 2019. URL.
net/
Forum? gf
Cristina Cifuentes, Reverse compilation techniques. 1994.
Marcella Cornia, Matteo Stefanini, Lorenzo Baraldi, and Rita Cucchiara. M2: Meshed-memory transformer for image captioning. arXiv preprint arXiv: 2019.
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoe V Le, and Ruslan Salakhutdi- nov. Transformer-xl: Attentive language models beyond fixed-length context. arXiv preprint arXiv:1901.0286/ 2019.
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805. 2018.
Li Dong and Mirella Lapata. Language to logical form with neural attention. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 23-43, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10.18653/v 1//16/ 1004. URLhttps: www. aclweb. http://ww..r..aaooooooooe/------
Li Dong and Mirella Lapata. Coarse-to-fine decoding for neural semantic parsing. arXiv preprint 1805.04933 2018.
MV Emmerik and Trent Waddington. Using a decompiler for weal-world source recovery. In 11th Working Conference Reverse Engineering, pp. 27-36. IEEE, 2004.
Cheng Fu, Huili Chen, Haolan Liu, Xinyun Chen, Yuandong Tian, Farinaz Koushanfar, and Jishen Zhao. Coda: An end-to-end neural program decompiler. In Advances Neural Information Processing Systems, pp. 3703-37777773 3714, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In I. Guyon, U. V. Luxburg. wanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 1024-1034. Curran Associates, Inc., 2017. URL http:://ppppp///// nips. wwtpppppppppp......eeppppppppppp S703-Inductiveerrreeeetttaaaaa wtt.:ppwwss.tttt..........oerraa
Bengio, H. Wallach, R. Fergus, S. Vish-
Jingxuan He, Pesho Ivanov, Petar Tsankov, Veselin Raychev, and Martin Vechev. Debin: Predicting debug information stripped binaries. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 1667-1680, 2018.
Hex-Rays. httpps///wwhhexxrayys com/
2017.
IntelC++compiler.
wwt.tteell..o.eeeeooooommo.oottt httpc/////.ooooottt////////////e html 2017.
Omer Katz, Yuval Olshaker, Yoav Goldberg, and Eran Yahav. Towards neural decompilation. arXiv preprint wwtxiv:9905.08322 2019.
Jeremy Lacomis, Pengcheng Yin, Edward Schwartz, Miltiadis Allamanis, Claire Le Goues, Graham Neubig, and Bogdan Vasilescu. Dire: A neural approach to decompiled identifier naming. In 2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE), pp- 628-639. IEEF, 2019.
10

---

Under review as a conference paper at ICLR 2021
JongHyup Lee, Thanassis Avgerinos, and David Brumley. Tie: Principled reverse engineering of types in binary programs. 2011.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint 1511::5511.544990 2015.
Zhen Li, Deqing Zou, Shouhuai Xu, Xinyu Ou, Hai Jin, Sujuan Wang, Zhijun Deng. and Yuyi Zhong. Vuldeepecker: A deep learning-based system for vulnerability de- tection. In 25th Anmual Network and Distributed System Security Symposimm, NDSS 2018, San Diego, California. USA, February 18-21, 2018. The Internet Society, 2018. URL http:://w.inteereetsoost www.inneeteteiett........... orrterrreetcceee..oro////ss horg:///dds/ggccottteet///pppl.p conttent//plloccs/stttees 25/ 25/2015 /2////21nds 10.0033-2200 2 paper.
Zhiqiang Lin, Xiangyu Zhang, and Dongyan Xu. Automatic reverse engineering of data structures from binary execution. In Proceedings of the 11th Annual Information Security Symposium, pp- 1-1, 2010.
Wang Ling, Phil Blunsom, Edward Grefenstette, Karl Moritz Hermann, Tomáš Kočiský, Fumin Wang, and Andrew Senior. Latent predictor networks for code generation. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume J: Long Papers), pp. 599-609, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10.18653/ 1/P16 1057. BtLhttp:: www wwwwww.wwa..c...... htt.///ww..ggaantooogggg////////
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint 1rXhv:1907.11000 2019.
Sifei Luan, Di Yang, Celeste Barnaby, Koushik Sen, and Satish Chandra. Aroma: Code recom- mendation via structural code search. Proceedings of the ACM on Programming Languages, 3 (0OPSLA):1-2) 2019.
Charith Mendis, Alex Renda, Saman Amarasinghe, and Michael Carbin. Ithemal: Accurate, portable and fast basic block throughput estimation using deep neural networks. arXiv preprint 1800 07412, 2018
Lili Mou, Ge Li, Lu Zhang, Tao Wang, and Zhi Jin. Convolutional neural networks over tree structures for programming language processing. arXiv preprint arXiv:1409.5718, 2014.
Anh Tuan Nguyen, Tung Thanh Nguyen, and Tien N. Nguyen. Lexical statistical machine translation for language migration. In Proceedings of the 2013 9th Joint Meeting Foundations of Software Engineering. ESEC/FSE 2013, pp. 654, New York, NY, USA, 2013. ACM. ISBN 978- doi: 10.1145/2491411.22 2444444. URL http:://dooo wtt.:/ii..ammmor./....o...
1-4503-2233 -237-9.
24914 4 2494584
Leetcode String Problems.
2017.
Maxim Rabinovich, Mitchell Stem, and Dan Klein. Abstract syntax networks for code generation and semantic parsing. arXiv preprint arXiv: 2017.
RetDec.
com/ 2017.
Nathan E Rosenblum, Xiaojin Zhu, Barton P Miller, and Karen Hunt. Learning to analyze binary computer code. 2008
A. Sanfeliu and K. Fu. A distance measure between attributed relational graphs for pattern recog- nition. IEEE Transactions on Systems, Man, and Cybernetics, SMC-133))353-362 1983. doi: 190.09/TMM..198..3311111
Abigail See, Peter J. Liu, and Christopher D. Manning. Get to the point: Summarization with ceinter-geneattor networks. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1073-1083, Vancouver, Canada, July 2017. Association for Computational Linguistics. doi: 10. 10.18665//1//11--0099 URL https:
7/www. c web. www.ee.orrggntttno wew..oorg//atthhoooo////11111100
11

---

Under review as a conference paper at ICLR 2021
Zhan Shi, Kevin Swersky, Daniel Tarlow, Parthasarathy Ranganathan, and Milad Hashemi. Learning execution through neural code fusion. arXiv preprint 1.K.019906.7181,..2 2019.
Eui Chul Richard Shin, Dawn Song, and Reza Moazzezi. Recognizing functions in binaries with neural networks. In 24th { {USENIX) Security Symposium ({USENIX) Security 15), pp. 611-626, 2015.
Kai Sheng Tai, Richard Socher, and Christopher D Manning. Improved semantic representations from tree-structured long short-term memory networks. arXiv preprint wxiiv/553.00007: 2015.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5198-5998099 6008, 2017.
Minjie Wang, Lingfan Yu, Da Zheng. Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, Ziyue Huang, Qipeng Guo, Hao Zhang, Haibin Lin, Junbo Zhao, Jinyang Li, Alexander Smola, and Zheng Zhang. Deep graph library: Towards efficient and scalable deep learning on graphs. ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019. URL httph:tt: /raxiv wwwpxxv..rrg/aaao abs 0099001155
K. Yakdan, S. Dechand, E. Cerhards-Padillle and M. Smith. Helping johnny to analyze malware: A usability-optmmized decompiler and malware analysis user study. 2016 IEEE Symposium on Security and Privacy (SP), pp. 158-177, May 2016. doi: 10. 10.1109/SP.201..8.
Xuejun Yang, Yang Chen, Eric Fide, and John Regehr. Finding and understanding bugs in com- pilers. In Proceedings of the 32nd ACM SIGPLAN conference on Programming language design and implementation, pp. 283-294, 2011.
Fangke Ye, Shengtian Zhou, Anand Venkat, Ryan Marucs, Nesime Tatbul, Jesmin Jahan Tithi, Paul Petersen, Timothy Mattson, Tim Kraska, Pradeep Dubey, et al. Misim: An end-to-end neural code similarity system. arXiv preprint S2iv:2006.052633 2020.
Pengcheng Yin and Graham Neubig. A syntactic neural model for ation. In Proceedings of the 55th Annual Meeting of the Association for Computational Lin- guistics (Volume I: Long Papers), pp. 440-450, Vancouver, Canada, July 2017. Association for Computational Linguistics. doi: 10.18653/v1/P11--0441 URL //wp:w///wwwwww. aclweb. www.wwrbbrrrr.....ooooo..o...o.r
code gener-
lanthlloyy/I1--11 1041
Pengcheng Yin and Graham Neubig. Tranx: A transition-based neural abstract syntax parser for semantic parsing and code generation. arXiv preprint arXiv: 180.002700, 2018.
Yaqin Zhou, Shangqing Liu, Jingkai Siow, Xiaoning Du, and Yang Liu. Devign: Effective vulnera- bility identification by learning comprehensive program semantics via graph neural networks. In Advances in Neural Information Processing Systems, pp. 10197-10207, 2019.
Qihao Zhu, Yingfei Xiong, Yican Sun, Lili Mou, Lu Zhang, et al. Treegen: A tree-based transformer architecture for code generation, arXiv preprint arXiv:991.00900 2019.
12

---

Under review as a conference paper at ICLR 2021
A TRAINING SETUP AND
We ran our experiments on Amazon EC2 using p3. 16xlarge instance which contains Nvidia Tesla V100 GPUs with 16GB main memory. Hyper-parameters for Lang2logic and Ins2AST are selected using cross-validation with grid search. We present the hyper-parameters used by different neural networks in Table The number of GNN layer N-Bref is set 3. We use an Adam optimizer with 31 = 0.9, 31 0.98 which is the setting in the original Transformer Vaswani et al. (2017). We add label smoothing and a dropout rate 0.3. Weights of attentive layers are initialized from the uniform distribution, while weights of feed-forward layers are initialized using techniques the same as Vaswani al. (2017). Other scheduling methods (e.g. learning rate, warm-up steps) are the same Cornia et al. (2019) for training N-Bref and transformer baseline.
Table 4: plyper-parametten chosen for each neural network model
Baseline Transformer
Lang2logic
Ins2AST
N-Bref
Batch Size
50
50
16
16
Number of encoder layer
2
2
3
N1
Number of decoder layer
2
2
3
N2= N3=2
Number of head (d)
Multi-head Attention
Multi-head
Encoder Type
LSTM
N-ary LSTM
Attention +GNN
Multi-head Attention
Multi-head Attention+GNN
Decoder Type
Tree LSTM
Tree LSTM
Hidden States Size
256
Embedding size
256
Gradient clip threshold
1.0
13

---

Under review as a conference paper at ICLR 2021
B LEETCODE SOLUTIONS EXAMPLES
We present the examples of the tested Leetcode solutions Figure and The tasks that are tested includes "Isomorphic Strings", "Multiply Strings", "Longest Palindromic Substring", "Implement strStr("", "ZigZag Conversion". Many easy problems are too short (e.g. "Length of the last word") to justify the performance of N-Bref and some of them use their own-defined functions which is beyond the scope of N-Bref.
Figure 1: Isomorphic Strings
Figure 2: Multiply Strings
/*
/*
Input: "egg", "add"
Input: numl "2", num2 "3" Output: "6"
Output: true
Input: s "foo", "bar"
Input: numl = "123" num2 "456"
Output:
false
Output: "56088"
*/
Input: "paper", "title"
Output: true
char* multiply (char= numl, char* num2) {
int lenl = 0:
int len2 = 0:
bool istsomorphi (char 8, chare t) {
int sprod[100)
/s same length */
char [ns[100] {0) int i:
int len strlen
/s for ascii code s/
int j:
char hashs[128 = {0):
int k;
char hasht[128] (0);
int c:
int i; int x;
lenl strlen (numl );
int y;
len2 = strlen (num2): );
for (i lenl 1: >= 0; i--) {
for
(i 0: i < len: i++)
k = lenl - - i:
x s[i];
for (j len2 1: >= 0: j-) {
if (hashs [x] = 0)
[rod[k++] += (numl[i) '0)
hashs[x] = [[i]:
(num2[j] '0);
clse {
if [hashs[x] != {i))) return false;
k=k+1; /* the last carry digit */
/s carry all a/
}
for (i 0; i<
1; i=i-1)
}
= prod 10;
prod[i] prod [i] % 10:
y [[i];
prod[i 1] += c:
if (hasht[y] 0) {
hasht[y] = s[i]:
/s remove lead zeros #/ for ( k> prod 1] 0: )
}
clse {
k=k-1;
if (hasht[yl 1= sfi)) return false;
/* reverse */
}
for (i = 0: < k: i++) {
ans prod
+ :0
}
ans [k] 00'
return true;
return ans;
14

---

Under review as a conference paper at ICLR 2021
C EXAMPLES OF N-BREF GENERATED PROGRAMS
We present the dataset examples in Figure S and
We define char, short, int, long as 'int8_t" _t', 'int16_r', 'int32.1' and 'int64_t" simplify tokenizing process (64-bit machine). 'uint' refers to 'unsigned' type.
Figure 3: <math.h> random generated exam- ple with uum +- 1 i depth < basce t- 2.
Figure 4:
<String.h>> depth < baize f- 1.
with by num
6 #include <string h
# #include <math, h>
int32_1 *foo (void)
int32_t fintint #1_0){
int32_t 1.0 = 0x3BL;
int8_t +1.1 &1_0 [11:
int32_t 1.1 13L:
int32_t [.2[5]:
float 1 = 0x2p+9;
uint16 t 1 0x47L;
uint8 1 L3UL;
int32 1 OI.;
int32_t #l.4 = &l.1:
int 1.5;
int32_t 1.5 0x9BL:
intl6_t 1.6 0x15L:
int32_t 1.6 = 0xA9L:
int32.t #1.7 = &1.2 [3];
int32_t 1.7 OL:
int32_t (2]
uint32_t 1.8 = 0x45L;
uint32.t 1.9 0xIIL;
float 1_9 0xlp+l:
intl6_t 1.10 IL;
float 1.10 OxE.3p+15.
int32.t 111 OxDIL;
for (I_0=10;(1) (1_0000(1000=0))) (10:==)) 1_0=1_0 -5)
for (1.5 0: 1.5 4; 1.5++)
for (1.6 17:
1.0[1.5] 13L:
(1.6 (-9)); 16=16 I
for (1.5 = 0; 1.5 5; 1.5++)
if ((I.5 >= (1.3 16))
1.2[1.5] = OxBDL: ir (urrnem((strat((() streat(&1_0[31, &1-0(1)),
1.1 &= OxFBL:
1.7 -= ((1.5)
(0xDIL >> 18)) & I.1);
&1.0121, 1.2(3)) 1.3 1.3 - 6; 17 17:
1.1 (OL &
((1 15) 11);:
elsef
else {
1_8 1.8 + 1;
for (1.5 = 0; 1.5 < 2; 1.5++)
if (1.6 > 0)
1.8[1_5] = &1]2
1.9 frexp (1.2 (1155)
1_8 [_8
continue:
1.4 "= ((+(1.2[3) (21))
(..1. 13L));
if ((1 1 & 717 >>
((1.7 1.6) (_7)))
if ((1.214) (1_2[3) (0x7EL. 1_2(44)))
1.4 = &1.5;
for (1.4 (1.4 3): 1.4 1)
else
1.2 1.9; {
1_3 = 1.3 + 1:
1.2 = floor [pow[ (1 1_9 (.10));
else
return 1.4;
L.1 = (0x67L < (.2
L11 1_]
}
1_2 stremp(&11100 1_011), &1.0
return 1111;
15

---

Under review as a conference paper at ICLR 2021
D EQUATIONS OF POSSION DISTRIBUTIONS FOR VARIABLE NUMBERS
For variable number (varnam or v) generated for program, it follows Poisson distribution (Eq. where À- Unam + b Ddepth + bias as discussed in Section Evaluation.
A P(u)
V
0, 0, 2, .......
(8)
v!
E FORMAL ALGORITHM FOR PREDICTIONS
Algorithm Algorithm for N-Bref prediction.
INPUT: Assembly Graph Gasmi Root Node 7; Terminal Node Types (7); LLC encoder, AST encoder, AST decoder (LLCen; AST on ASTae): N-Bref model (Model)
OUTPUT: Complete AST Jast.
1: Q - [7]
2: (ostuepdate(1)
3: while Q not empty do
4: node Q-pop()
5: child + model(LLC... = Gasm; ASTen Gnsts AST = Tree Tree_path(node) child is not 'eos' then
6:
7:
Gaet che.teedate(hhild) if child then
8:
9:
Qappend(childd)
Return: Gast
F PERFORMANCE IN GRAPH EDIT DISTANCE
We test the performance of N-Bref using graph edit distance (GED) which is calculated as Eq. 9 The distance is calculated the minimum number of operations (i.e., node substitution and node insertion) to change our output AST (AST) into the golden AST (ASTc).
(ED(AST,ASTa)
min Σ Cost(es) Ct....ek
2m
Here, e, denotes the ith operations to change AST to ASTG our testing, we set Cost(e) 1. The maximum possible GED between a AST and AST is the number of nodes in ASTG. Note that when e, substitutes a node from non-terminal to terminal type, the branch the original terminal node is automatically deleted.
The tree expansion algorithm to generate AST is shown above in Appendix E. Table 5 shows the GED of N-Bref and transformer baseline. N-Bref shows 40.4% reduction average in graph edit distance compared to traditional transformer.
Table Comparison between N-Bref and baseline transformer using graph edit distance across datasets.
AST Generation (edit distance)
Average number of tree nodes
(lib, buize, Ddepth)
baseline transformer
N-Bref (-% over baseline)
math, 1,
9.13
4.70 (-88.5%)
78.8
math, 2,
22.22
13.38 (-39.8%)
155.2
math, 3.
46.37
29.64 (-36.1%)
239.6
str, 1,
12.31
6,45 (-47.6%)
82.0
str, 2, 2
30.51
17.43 (-42.9%)
170.4
str, 3, 3
59,62
36.31 (-39.1%)
251.1
Leetcode
44.33
31.46 (-29.0%)
214.9
16

---

Under review as a conference paper at ICLR 2021
Table 6: Performance on code vulnerability detection.
Bi-LSTMMare source code
BI-LSTMHal*" source code
Metries
Transformer on binary
N-Bref (binary)
(25872 data points)
(10302 data points)
Accuracy
61.2
54.5
56.4
59.3
Fl score
65.0
57.1
59.6
63.3
result from implementation of ValDeePecker Li et 2018 and devign dataset.
G PERFORMANCE OF N-BREF IN OTHER BINARY ANALYSIS TASKS
N-Bref's structural transformer architecture / low-level code encoding and representations are easy to integrate with various neural-based binary analysis tasks as their input also low-level code, al- lowing advances in such tasks, i..,, vulnerability detection, crypto algorithm classification, malware detection, etc.
We tried out tasks using N-Bref"s encoder and low-level representation methods to analyze binary code:
(i) Identify binary code vulnerabilities (Table 6). We test the performance of N-Bref vulner- abilities detections using Devign dataset which includes 25872 data points collected from commit difference of FFmpeg and QEMU repository. Using the commit id given from Devign dataset (Zhou et al. (2019)), we clone the old repository, compile it and extract the binary of the function from the compiled project. We successfully generate 10302 binaries (25872 total data given) as many project commits in the dataset are not able to compile.
(ii) Measure binary code similarity (Table 77. We test N-Bref on POJ-104 tasks (Mou al. 2014 by compiling them into binary codes and use the same metrics as MISIM (Ye et al. (2220) to evaluate the performance of N-Bref.
In vulnerability detection task, the performance of N B-Bref is 3.0% margin over transformer baseline on binaries and 4.08% margin over BiL.TMM-aase vulnerability detector (Li et al. (2018) on high- level source code using the same amount of dataset. For code similarity measures, N-Bref achieves 3.85% MAP@F R performance increase compared to transformer baseline and shows 5.0%/20. 16% better MAP@R R than Aroma( Luan et al. (2019)) and NCC (Neural code comprehension Ben-Nun jet al. (2018) that are code searching frameworks that operates on high-level code. Note that binaries more abstract and are difficult to analyze compared to high-level code.
Table 7: Performance of code similarity accuracy.
MISIM-RNN*
NCC# (source code)
Aroma (source code)
Transformer (binary)
N-Bref
Metries
(source code)
(binary)
MAP @ (R(())
74.01
39.95
55.12
56.26
60.11
AP (%)
81.64
50.42
55.40
62.46
67.20
AUPRG (%)
99.84
98.86
99.07
99.13
99.64
# result from MISIM( et al, (2020)
17

---

Under review as a conference paper at ICLR 2021
H COMPLETE ASSEMBLY CODE FOR FIGURE 1
#include <string.hh h> char foo float 1.0, int $1_1
foo:
.L
{
pushq %rbp
char 1.2 [ 4 4
movq
Krsp %rbp
short 1.3 = 2
subq
$48. %rsp
float 1.4 0x9p+1;
movss
Sxmm0, -36(%)bp)
if ( strchr 1_2 11 [0))){
movq
%rdi -88(%bbp)
1.0 1.4 1.0;
movq
%fs :40. %rax
movq
%rax -8(6rbp)
else {
xorl
Reax. %eax
1.2 1.3 =
$2. - 18(%rbb))
}
movss
(co()rip)) %xmm0
return 2:
movss %xmm0, - rbp(%)bp) movq
}
-8((%rbp) ) %rax
movl
(%rax), %edx
leaq
-12(%rbp), %rax
movl
%edx. %esi
movq ārax %rdi
call strchr@
testq %rax. %rax je .1.2 -36(%rbp) %amm0
mulss
-16(%rbp) ) %xmm0
9xmm0, 36(% jmp LL3
.L:
movswl - -18(%rbp), %eax
movb $7 -22(%rbp,
.L:
movl
%eax
movq 8(Krbp) , %rex
xorq %fs:40,
je .L
LS:
leave
I COMPLETE ASSEMBLY CODE GRAPH FOR FIGURE
18

---

Under review as a conference paper at ICLR 2021
Figure 5: complete assembly graph of Figure 1. Note that eax is the lower 32-bit of mur, so has data dependency with res for line 12-13. Also. when there is no destination nodes in the instruction (e.g.. line 9), the destination should be the memory location represented by address register (e.g.. rhp) and offset (e.g..- -3 in line 9).
-8
rbp
ICX
move
BaX
movi
57
Pop
movb
mov
mmp
38
1bp
miguss
Ppp
Krmm
movvss
control- ol-foww edge
FBX
teetq
Strchr
muiis -18(tt)) Jomma
movss 36j(bp)
-15(bb)) cax
structure
movl $0 6ax
moug 48(tbp),
jmp 133
opends
movi
movi
14:13:
move
8
10
12
15
Destinatoo
Node
IOx
esi
moves -30/ (oorbap).mmme Ammm
BIrohIBPLT
data flow edge
nowi
1.2(pp)).
edk, es! move ddi call
rax, rax
Node
rbp
tBX
movl
leaa
19


Reviews:
[{"review_id": "ezglM0J2B77", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nSummary:\n\nThe paper designs a neural architecture (called N-bref) for code decompiling, i.e., translating binary code to high-level code (e.g., C/C++). \n\nExperiments show that a high token-level accuracy on some LeetCode dataset, compared with a few baseline methods including Seq2Seq and Transformer.\n\n\nMajor concerns: \n\n1. The paper does not appear to be novel. \n\nThe paper identifies 4 challenges for decompiling, but some of them are generic, such as long-dependency problems and data augmentation. For the other two challenges (datatype and control/dataflow), the paper proposes to decompose the generation into two subtasks: source code generator (SC-Gen) and data type solver (DT-Solver). \n\nTechnically, both SC-Gen and DT-Solver are modeled by the same neural architecture (but differently parametrized): a memory-augmented structural transformer. This appears to be a ragbag of existing and known models: Transformer [Vaswani et al., 2017], Tree Transformer [Sun et al., 2020], and Memory Augmentation [Cornia et al., 2020]. I do not feel this paper very exciting. \n\n2. The evaluation metric is problematic (or at least unclear).\n\nThe performance of a model is measured by \"token accuracy\" when the authors \"expand the decompiled AST from the root into the same structure as the golden AST (AST_G).\"\n\nIf this is what the authors meant, a real program is never generated. The authors assume a correct program is there, and predict the next AST token/rule assuming previous partial AST is the same as AST. \n\nSuch measure of success could be drastically different from the real performance of generation. The authors should consider string match of the generated program compared with reference, or the functional accuracy of the generated program. \n\nWith token accuracy given the correct partial AST, I would not agree with the claim that \"N-Bref successfully reverts human-written\" programs.   \n\nMinor:\n\nFor Ins2AST [Fu et al., 2019], did you use Ins2AST+Attention? That seems to be better than Ins2AST (w/o attention). \n\nDecompilation tasks is --> Decompilation task is\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "_H6wrgteIwo", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors present a neural-based decompilation framework. They generate synthetic input data in order to make sure source code examples have a consistent code style that can be more easily learned. They predict types of variables and the actual code in two separate steps. For both steps, they employ a custom transformer architecture where evey second layer of the encoder is a graph neural network. There are two separate encoders of this kind, one conditions on a CFG obtained from static analysis of the input assembly, while the other one conditions on the partial output AST that has been generated thus far.\n\nStrengths:\n- The authors propose an end-to-end system for neural decompilation\n- Interesting use of graph neural networks to increase sensitivity to structure in a transformer.\n- Favourable comparison to multiple baselines.\n- Evaluation also considers a human-written dataset.\n\nWeaknesses:\n- It is not so easy to fully understand the approach end-to-end. Perhaps the presentation can be improved. (Though I understand that it can be challenging to fit an explanation of an ambitious approach with multiple novel components into 8 pages.)\nWhen reading the paper, it happened to me a couple times that I tried to go back to some piece of information and I did not find it at the location where I would expect to find it. Some details are discussed in the introduction, but apparently nowhere else, for example how the output of the DT-Solver is used. It would help to reorganize the paper a bit so that the exposition follows the order of operations when running the approach and to discuss which data goes where in the technical sections.\nThe paper says that DT-Solver and SC-Gen are both based on the same architecture, but DT-Solver is not really discussed in detail. As an example, it is not stated if the types of variables are chosen from some fixed set (which one?) or if the DT-Solver generates a type AST, but Figure 1 suggests a fixed set. Figure 3 is helpful, but it seems it does not show the full story for either DT-Solver or SC-Gen. Figure 1 is a bit confusing, as the shown AST does not appear to match the given source code. (E.g., there is no variable of type `int *`), and variable declarations are shown as part of a single AST of the program even though later they are treated separately.\n\n- The evaluation metric is explained rather vaguely, so I am not sure if I fully understand what is meant, but this is crucial to interpret the results. How do you \"expand the decompiled AST from the root into the same structure as the golden AST\"? What happens during expansion if a token does not match? Is the subtree removed? I guess after the expansion step, you compare AST nodes that end up at the same position in the tree?\n\n\nFurther questions:\n\nAccuracy based on syntax comparison to synthetically-generated input examples is not necessarily what an end user cares about. How well do your decompilation results preserve semantics? I.e., if token accuracy is imperfect, what kinds of mismatches do you typically get? It would also be interesting to understand a bit better the distribution of the results, e.g., how do the results change if you count the fraction of results with perfect token accuracy instead of computing averages over token accuracy?\n\nAs far as I understand, the positional encoding for ASTs drops a lot of structure information, which is then recovered by the GNN layers. Have you considered using richer positional encodings along the lines of [i]?\n\n[i] https://www.microsoft.com/en-us/research/publication/novel-positional-encodings-to-enable-tree-based-transformers/\n\n\nMinor:\n\nPage 1: \"learns to decompile the source code to assembly\". That seems backwards.\n\nConsider using \\citep and \\citet.\n\nPlease review your paper with a focus on grammar as well as whitespace and other formatting issues.\n(For example, you should use ``$\\mathit{xmm0}$`` instead of ``$xmm0$`` ,`` `control flow'`` instead of ``'control flow'``, etc.)\n\nPage 14: There is wrong indentation or missing curly braces next to the \"continue\" statement in Figure 3.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "XF8c0MoC-1", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "High-level view:\n\nI don’t think this is necessarily a bad paper, but I think it’s unacceptable for ICLR in its current form. I currently lean heavily toward rejection. After thinking over the concepts in the paper more, I might lean more strongly toward rejection or toward acceptance (if the authors can address the issues I raise below). I provide details below examination of how I’ve come to my evaluation rating below.\n\nSummary:\n\nThis paper principally focuses on the idea of decompilation. Decompilation can mean many things, but the general idea as I understand it, is to take a representation of a software program from one level (e.g., program binary) and then “lift it” to a level that is higher in abstraction (e.g., from binary to assembly, from assembly to C, from C to a lambda calculus, etc.). As I understand it, it’s called decompilation because it tends to do the opposite of what a compiler does. Compilers tend to lower a representation of a software program into something that is closer to the hardware and therefore potentially more efficient. \n\nThe benefits of decompilation are numerous. One major benefit is in the ability to perform programming language – to – programming language transformation. Another, which is the focus of this paper, is for reverse engineering purposes of a binary. There are many others. As such, in my opinion this is unquestionably an important subtopic for the field of machine programming and the authors approach also seems satisfactory to me for ICLR (described below).\n\nThe authors present a new approach called: neural-based binary reverse engineering framework (N-Bref). N-Bref has a number of components that it relies on to perform its decompilation. They consist mostly of components from the programming languages community (e.g., assembly code, abstract syntax trees for encoding and decoding, etc.) and the machine learning community (e.g., deep neural networks for learning structural transformations, etc.).\n\nThe authors empirically evaluate their N-Bref’s accuracy on a number of problems from the open source LeetCode problem set and generate 25,000 pairs of high-level source and low-level source which are broken into training (60%), validation (20%), and testing (20%). LeetCode problems tend to be fairly simple, self-contained, and, to my knowledge, are coding problems that are meant to help train new programmers or prepare software developers for coding interviews, amongst other things. An emerging use of LeetCode is to use it as a baseline for machine programming (MP) in a variety of different ways. In this case, the authors are using LeetCode coded solutions in MP to compiled the source code into a lower level form (assembly I believe) and then see if N-Bref can return the assembly back to the original form or some semantically equivalent form. Their empirical approach seems sound to me.\n\nOverall, the authors show better accuracy for their tested problem set against REWARD, a baseline system (a transformer), lang2logic, and Ins2AST across two dimensions: data type recovery and abstract syntax tree (AST) generation.\n\nHigh-level concerns:\n\nThere are several reasons I’m not positive about this paper. Perhaps the biggest reason is I can’t seem to understand what is novel about the system. That is, unless I’ve just missed something, it seems that all of the core components of N-Bref are lifted from prior work with perhaps some minor augmentation. This feels largely incremental to me.\n\nOn the other hand, one could argue that N-Bref is novel because it combines a number of existing components in a unique way to achieve better performance that prior work. I can see this perspective. However, if we considered this view, it seems like the problem they are solving should be more impactful than type recovery and AST generation. I’m not saying these problems aren’t important – especially type recovery (I think this problem is deeply important) – but that it should go further to demonstrate more dimensions of decompilation.\n\nThe second major concern I have with this paper is the small dataset they are using. Consider, for a moment, that they are using only 25,000 input/output pairs for their training/validation/testing. Now consider a prior accepted ICLR 2020 paper, Hoppity (Dinella et al.), which trained on nearly 300k code change commits in GitHub. This looks like an order of magnitude difference in dataset empirical evaluation to me. On top of that, the only data is coming from LeetCode. We have no empirical demonstration that this approach will work on other datasets outside of LeetCode.\n\nIf the authors can address these two primary concerns by the time of decisions, I will likely slant toward the positive. If they do not (or will not), I will likely champion this paper’s rejection, as I do not believe in its current form it’s up to ICLR standards.\n\nLow-level concerns:\n\nThe language in the paper seems to use many strong and ambiguous claims: “N-Bref outperforms previous neural-based decompilers by a large margin.” First of all, what is a “large margin”? There’s not quantitative measurement in the word “large”. Large could mean 1%, 10%, 100,000%. This kind of language is not what I expect from tier-1 publications.\n\nAnother example is: “However, key challenges remain:” where they then summarize two problems. I agree that the two problems they highlight are important. But I absolutely do not agree that those are the *only* two problems that stand in the way of decompilation.\n\nAlso, there seems to be some lack of understanding of the field of machine programming, from my perspective. For example in the abstract the authors claim “decompilation aims to reverse engineer binary executables.” I 100% disagree with this definition. As I stated above, I believe, the more general space of decompilation is actually the idea of lifting a software program representation from one format to a higher-level format that increases the level of abstraction from the hardware. Moreover, I know of many decompilation systems (e.g., verified lifting is one), that has an entirely different goal than reverse engineering. Verified lifting is principally focused, as I understand it, is focused on language to language translation.\n\nPerhaps the grossest overclaim the authors make is in the introduction \n\n“Our work pushes the performance of neural-based decompiler to a new level and presents a new baseline and stand dataset for future developers.” \n\nI find that sentence simply unacceptable. I could never give an accept rating to a paper that makes such an outlandish claim with such a small body of evidence. Moreover, other people have used LeetCode as a baseline, so it’s not the first time people have done this. So it seems wrong to me on many levels.\n\nThis continues throughout the paper …\n\nThat said, these are minor nits that the authors, if they so choose, could probably fix with little effort.\n\nI would hope that in a later version of the paper the authors would tone the language down, move away from the number of strong claims they make in the paper, and provide measurable data points when making claims about performance: “Our system is more accurate than <list the systems you’re comparing against> from X% to Y%.” Right now the only way to figure that out seems to be to deeply study the experimental evaluation, which is a bit inappropriate in my opinion. I believe it could (and should) be listed directly in the abstract and in the introduction. By hiding these details, it creates a perception of overclaiming – at least it did for me.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "1x4ihnzcUWY", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper is interesting and addresses an interesting topic. The results seem promising, though the evaluation is done on relatively small test cases. \n\nThe proposal to divide the problem into two sub-tasks, i.e., data type solver and source code generation, is promising and can probably have impact on future decompiler proposals. \n\nThe main problem with the paper is that it is hard to read and understand. I'm aware of the page limitations, but the authors have crammed so much inte these pages that is hard to follow. Further, there are also a number of inconsistencies and unclear stuff (see below). For example, the authors claim that one thing their proposed method extends beyond earlier methods is to handle pointer references. However, I can't find in the paper how that is done. \n\nThe usefulness may be limited of this work, since they only work on unoptimized code (see e.g., page 4, 2nd paragraph). However, in reality, most code have went though substantial optimization during the compile phase.\n\nSome other comments / questions:\n* I lack information about the execution time of the training and inference. \n* Page 2, 2nd paragraph. You claim that your code generator produces similar code styles as human programmers. What do you mean by that, and how du you support that claim?\n* Fig 1b. Here are a number of strange / confusing things:\n  - Why are not all asm instructions shown in the data flow graph? For example movl (line 2), call (line 4), testq (line 5), etc. are missing.\n  - Why do you show one movss (line 9) and not the other movss (line 7)?\n  - You have mixed up lines 7 and 8 in the graph (show it as mulss -36(rbp),xmm0), which is confusing.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper describes N-Bref, a new tool for decompilation of stripped binaries. Compared to previous tools for neural-based decompilation, this tool is based on two new ideas: a) to separate the generation of data declarations from the generation of the code itself, and b) the use of more sophisticated network architectures. These network architectures, however, all come from prior work, so the contribution in that regard is only their application to this particular problem. 

The authors addressed many of complaints raised by reviewers, particularly with regards to presentation and explanations, but I think the most substantial concerns remain. 

The most substantial concern is novelty. The technique is built on a combination of existing models, and its only original idea seems to be to treat the generation of data declarations and the code itself as separate tasks to be handled by independently trained networks. 

In terms of results, the paper shows some quantitative improvements over prior work, although it is not so clear that those improvements matter. The quality improvement is measured in terms of AST differences, but it is not clear how often those AST differences translate into semantic differences. More importantly, the tool is restricted to un-optimized binaries, which significantly limits its applicability for any real-world application. Prior work by Katz et al. is evaluated against optimized binaries, as are other types of lifting such as the Helium project by Mendis et al [1]. Given the prevasiveness of optimization in deployed code, a tool that cannot handle it has virtually no applicability.

I think some significant technical novelty could make up for the lack of evaluation against optimized binaries. Alternatively, strong results on optimized binaries would justify publication even if the technique is built from existing building blocks, but as it stands, I think the paper is too incremental to merit acceptance. 

[1]  Charith Mendis, Jeffrey Bosboom, Kevin Wu, Shoaib Kamil, Jonathan Ragan-Kelley, Sylvain Paris, Qin Zhao, Saman P. Amarasinghe:
Helium: lifting high-performance stencil kernels from stripped x86 binaries to halide DSL code. PLDI 2015: 391-402

Decision: Reject