Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: High-level view:

I 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.

Summary:

This 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. 

The 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).

The 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.).

The 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.

Overall, 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.

High-level concerns:

There 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.

On 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.

The 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.

If 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.

Low-level concerns:

The 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.

Another 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.

Also, 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.

Perhaps the grossest overclaim the authors make is in the introduction 

“Our work pushes the performance of neural-based decompiler to a new level and presents a new baseline and stand dataset for future developers.” 

I 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.

This continues throughout the paper …

That said, these are minor nits that the authors, if they so choose, could probably fix with little effort.

I 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.

review_title: Review of N-Bref: a high-fidelity decompiler exploiting programming structures

final_score: rating: 7: Good paper, accept
review_content: 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.

Strengths:
- The authors propose an end-to-end system for neural decompilation
- Interesting use of graph neural networks to increase sensitivity to structure in a transformer.
- Favourable comparison to multiple baselines.
- Evaluation also considers a human-written dataset.

Weaknesses:
- 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.)
When 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.
The 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.

- 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?


Further questions:

Accuracy 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?

As 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]?

[i] https://www.microsoft.com/en-us/research/publication/novel-positional-encodings-to-enable-tree-based-transformers/


Minor:

Page 1: "learns to decompile the source code to assembly". That seems backwards.

Consider using \citep and \citet.

Please review your paper with a focus on grammar as well as whitespace and other formatting issues.
(For example, you should use ``$\mathit{xmm0}$`` instead of ``$xmm0$`` ,`` `control flow'`` instead of ``'control flow'``, etc.)

Page 14: There is wrong indentation or missing curly braces next to the "continue" statement in Figure 3.

review_title: Nice results, somewhat chaotic presentation

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper is interesting and addresses an interesting topic. The results seem promising, though the evaluation is done on relatively small test cases. 

The 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. 

The 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. 

The 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.

Some other comments / questions:
* I lack information about the execution time of the training and inference. 
* 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?
* Fig 1b. Here are a number of strange / confusing things:
  - 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.
  - Why do you show one movss (line 9) and not the other movss (line 7)?
  - You have mixed up lines 7 and 8 in the graph (show it as mulss -36(rbp),xmm0), which is confusing.

review_title: The paper proposes a neural network based decompilation infrastructure for translation of assembly code to high-level source code. The paper seems promising, presents interesting ideas and promising results but is unfortunately hard to follow and fully understand. 

final_score: rating: 4: Ok but not good enough - rejection
review_content: 
Summary:

The paper designs a neural architecture (called N-bref) for code decompiling, i.e., translating binary code to high-level code (e.g., C/C++). 

Experiments show that a high token-level accuracy on some LeetCode dataset, compared with a few baseline methods including Seq2Seq and Transformer.


Major concerns: 

1. The paper does not appear to be novel. 

The 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). 

Technically, 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. 

2. The evaluation metric is problematic (or at least unclear).

The 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)."

If 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. 

Such 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. 

With token accuracy given the correct partial AST, I would not agree with the claim that "N-Bref successfully reverts human-written" programs.   

Minor:

For Ins2AST [Fu et al., 2019], did you use Ins2AST+Attention? That seems to be better than Ins2AST (w/o attention). 

Decompilation tasks is --> Decompilation task is

review_title: architecture design

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