2019

Neural Reverse Engineering of Stripped Binaries using Augmented Control Flow Graphs

David, Yaniv, Alon, Uri, Yahav, Eran

Understand

We address the problem of reverse engineering of stripped executables, which contain no debug information.

This is a challenging problem because of the low amount of syntactic information available in stripped executables, and the diverse assembly code patterns arising from compiler optimizations.
We present a novel approach for predicting procedure names in stripped executables.
Our approach combines static analysis with neural models.

Built on

Dropout: a simple way to prevent neural networks from overfitting
Nitish Srivastava, Geoffrey E Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2014 · 1958
Earlier work this paper cites.
Program Slicing
Mark Weiser. 1984 · 1984
Earlier work this paper cites.
Program slicing in the presence of pointers. In Proceedings of the 1993 Software Engineering Research Forum . Citeseer, 255–260
James R Lyle and David Binkley. 1993 · 1993
Earlier work this paper cites.
Long Short-Term Memory
Sepp Hochreiter and Jürgen Schmidhuber. 1997 · 1997
Earlier work this paper cites.
Refactoring: Improving the Design of Existing Code
Martin Fowler and Kent Beck. 1999 · 1999
Earlier work this paper cites.
A Next-generation Platform for Analyzing Executables. In Proceedings of the Third Asian Conference on Programming Languages and Systems (APLAS’05) . Springer-Verlag, Berlin, Heidelberg, 212–229
T. Reps, G. Balakrishnan, J. Lim, and T. Teitelbaum. 2005 · 2005
Earlier work this paper cites.
PolyUnpack : Automating the Hidden-Code Extraction of
R. Edmonds. 2006 · 2006
Earlier work this paper cites.
Debugging Method Names. In Proceedings of the 23rd European Conference on ECOOP 2009 — Object-Oriented Programming (Genoa) . Springer-Verlag, Berlin, Heidelberg, 294–317
Einar W. Høst and Bjarte M. Østvold. 2009 · 2009
Earlier work this paper cites.
Labeling library functions in stripped binaries. In Proceedings of the 10th SIGPLAN-SIGSOFT workshop on Program analysis for software tools, PASTE’11 . 1–8
Emily R. Jacobson, Nathan E. Rosenblum, and Barton P. Miller. 2011 · 2011
Earlier work this paper cites.
TIE: Principled reverse engineering of types in binary programs
JongHyup Lee, Thanassis Avgerinos, and David Brumley. 2011 · 2011
Earlier work this paper cites.
Neural Machine Translation by Jointly Learning to Align and Translate
Original
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2014 · 2014
Earlier work this paper cites.
BYTEWEIGHT: Learning to recognize functions in binary code
Tiffany Bao, Jonathan Burket, Maverick Woo, Rafael Turner, and David Brumley. 2014 · 2014
Earlier work this paper cites.
Learning phrase representations using RNN encoder-decoder for statistical machine translation
Original
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014 · 2014
Earlier work this paper cites.
Adam: A method for stochastic optimization
Original
Diederik Kingma and Jimmy Ba. 2014 · 2014
Earlier work this paper cites.
Structured generative models of natural source code. In International Conference on Machine Learning . 649–657
Chris Maddison and Daniel Tarlow. 2014 · 2014
Earlier work this paper cites.
Code Completion with Statistical Language Models. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’14) . ACM, New York, NY, USA, 419–428
Veselin Raychev, Martin Vechev, and Eran Yahav. 2014 · 2014
Earlier work this paper cites.
Sequence to sequence learning with neural networks. In Advances in neural information processing systems . 3104–3112
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. 2014 · 2014
Earlier work this paper cites.
Suggesting Accurate Method and Class Names. In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering (ESEC/FSE 2015) . ACM, New York, NY, USA, 38–49
Miltiadis Allamanis, Earl T. Barr, Christian Bird, and Charles Sutton. 2015a · 2015
Earlier work this paper cites.

Similar

Effective Approaches to Attention-based Neural Machine Translation. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, EMNLP 2015, Lisbon, Portugal, September 17-21, 2015 . 1412–1421
Thang Luong, Hieu Pham, and Christopher D. Manning. 2015 · 2015
Cited alongside, same era.
Cross-Architecture Bug Search in Binary Executables. In Proceedings of the 2015 IEEE Symposium on Security and Privacy (SP ’15) . IEEE Computer Society, Washington, DC, USA, 709–724
Jannik Pewny, Behrad Garmany, Robert Gawlik, Christian Rossow, and Thorsten Holz. 2015 · 2015
Cited alongside, same era.
Predicting Program Properties from "Big Code". In Proceedings of the 42Nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’15) . ACM, New York, NY, USA, 111–124
Veselin Raychev, Martin Vechev, and Andreas Krause. 2015 · 2015
Cited alongside, same era.
Recognizing Functions in Binaries with Neural Networks.. In USENIX Security Symposium . 611–626
Eui Chul Richard Shin, Dawn Song, and Reza Moazzezi. 2015 · 2015
Cited alongside, same era.
PHOG: Probabilistic Model for Code. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016 . 2933–2942
Pavol Bielik, Veselin Raychev, and Martin T. Vechev. 2016 · 2016
Cited alongside, same era.
Probabilistic Model for Code with Decision Trees. In Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2016) . ACM, New York, NY, USA, 731–747
Veselin Raychev, Pavol Bielik, and Martin Vechev. 2016a · 2016
Cited alongside, same era.
Similarity of Binaries Through Re-optimization. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2017) . ACM, New York, NY, USA, 79–94
Yaniv David, Nimrod Partush, and Eran Yahav. 2017 · 2017
Cited alongside, same era.
Semi-Supervised Classification with Graph Convolutional Networks. In ICLR
Thomas Kipf and Max Welling. 2017 · 2017
Cited alongside, same era.
DéjàVu: a map of code duplicates on GitHub
Cristina V Lopes, Petr Maj, Pedro Martins, Vaibhav Saini, Di Yang, Jakub Zitny, Hitesh Sajnani, and Jan Vitek. 2017 · 2017
Cited alongside, same era.
Data-Driven Program Completion
Original
Yanxin Lu, Swarat Chaudhuri, Chris Jermaine, and David Melski. 2017 · 2017
Cited alongside, same era.
Bayesian Sketch Learning for Program Synthesis
Original
Vijayaraghavan Murali, Swarat Chaudhuri, and Chris Jermaine. 2017 · 2017
Cited alongside, same era.
Detecting argument selection defects
Andrew Rice, Edward Aftandilian, Ciera Jaspan, Emily Johnston, Michael Pradel, and Yulissa Arroyo-Paredes. 2017 · 2017
Cited alongside, same era.

Then

State-of-the-art speech recognition with sequence-to-sequence models. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) . IEEE, 4774–4778
Chung-Cheng Chiu, Tara N Sainath, Yonghui Wu, Rohit Prabhavalkar, Patrick Nguyen, Zhifeng Chen, Anjuli Kannan, Ron J Weiss, Kanishka Rao, Ekaterina Gonina, et al · 2018
Later among the works it cites.
Path-based Function Embedding and Its Application to Error-handling Specification Mining. In Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE 2018) . ACM, New York, NY, USA, 423–433
Daniel DeFreez, Aditya V. Thakur, and Cindy Rubio-González. 2018 · 2018
Later among the works it cites.
Debin: Predicting Debug Information in Stripped Binaries. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (CCS ’18) . ACM, New York, NY, USA, 1667–1680
Jingxuan He, Pesho Ivanov, Petar Tsankov, Veselin Raychev, and Martin Vechev. 2018 · 2018
Later among the works it cites.
Mapping Language to Code in Programmatic Context. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing . 1643–1652
Srinivasan Iyer, Ioannis Konstas, Alvin Cheung, and Luke Zettlemoyer. 2018 · 2018
Later among the works it cites.
Statistical Reconstruction of Class Hierarchies in Binaries. In Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS ’18) . ACM, New York, NY, USA, 363–376
Omer Katz, Noam Rinetzky, and Eran Yahav. 2018 · 2018
Later among the works it cites.
DeepBugs: A Learning Approach to Name-based Bug Detection
Michael Pradel and Koushik Sen. 2018 · 2018
Later among the works it cites.
Language models are unsupervised multitask learners
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2018 · 2018
Later among the works it cites.
Retrieval on source code: a neural code search. In Proceedings of the 2nd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages, MAPL@PLDI 2018, Philadelphia, PA, USA, June 18-22, 2018 . 31–41
Saksham Sachdev, Hongyu Li, Sifei Luan, Seohyun Kim, Koushik Sen, and Satish Chandra. 2018 · 2018
Later among the works it cites.
Structural Language Models for Any-Code Generation
Original
Uri Alon, Roy Sadaka, Omer Levy, and Eran Yahav. 2019b · 2019
Closest in time.
Code2Vec: Learning Distributed Representations of Code
Uri Alon, Meital Zilberstein, Omer Levy, and Eran Yahav. 2019c · 2019
Closest in time.
Generative Code Modeling with Graphs. In International Conference on Learning Representations
Marc Brockschmidt, Miltiadis Allamanis, Alexander L. Gaunt, and Oleksandr Polozov. 2019 · 2019
Closest in time.
BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers) . 4171–4186
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019 · 2019
Closest in time.
Asm2Vec : Boosting Static Representation Robustness for Binary Clone Search against Code Obfuscation and Compiler Optimization
Steven H H Ding, Benjamin C M Fung, and Philippe Charland. 2019 · 2019
Closest in time.
Structured Neural Summarization. In International Conference on Learning Representations
Patrick Fernandes, Miltiadis Allamanis, and Marc Brockschmidt. 2019 · 2019
Closest in time.
DIRE: A Neural Approach to Decompiled Identifier Naming
Original
Jeremy Lacomis, Pengcheng Yin, Edward J Schwartz, Miltiadis Allamanis, Claire Le Goues, Graham Neubig, and Bogdan Vasilescu. 2019 · 2019
Closest in time.
An Observational Investigation of Reverse Engineers’ Processes. In 29th USENIX Security Symposium (USENIX Security 20) . 1875–1892
Daniel Votipka, Seth Rabin, Kristopher Micinski, Jeffrey S Foster, and Michelle L Mazurek. 2020 · 2020
Closest in time.
A Convolutional Attention Network for Extreme Summarization of Source Code. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016 . 2091–2100
Miltiadis Allamanis, Hao Peng, and Charles A. Sutton. 2016 · 2091
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…