INCREMENTAL DECOMPILATION OF LOOP-FREE BINARY CODE: ERLANG
DOI:
https://doi.org/10.24193/subbi.2018.2.05Keywords:
incremental decompilation, Erlang, dominator tree, post-dominator tree, code duplication.Abstract
Decompiling byte code to a human readable format is an important research field. A proper decompiler can be used to recover lost source code, helps in different reverse engineering tasks and also enhances static analyzer tools by refining the calculated static semantic information. In an era with a lot of advancement in areas such as incremental algorithms and boolean satisfiability (SAT) solvers, the question of how to properly structure a decompilation tool to function in a completely incremental manner has remained an interesting problem.
This paper presents a concise algorithm and structuring design pattern for byte code which has a loop-free representation, as is seen in the Erlang language. The algorithms presented in this paper were implemented and verified during the decompilation of the Erlang/OTP library.
References
Joe Armstrong. Programming Erlang. The Pragmatic Bookshelf, 2nd edition, October 2013. ISBN 978-1-93778-553-6.
Ericsson AB. Erlang Programming Language. http://www.erlang.org, 2018. [Accessed: 2018.03.14].
D´aniel Luk´acs and Melinda T´oth. Structuring Erlang BEAM Control Flow. In Proc. of the 16th ACM SIGPLAN International Workshop on Erlang, Erlang 2017, pages 31–42, New York, NY, USA, 2017. ACM. ISBN 978-1-4503-5179-9.
Cristina Cifuentes. Structuring decompiled graphs, pages 91–105. Springer Berlin Heidelberg, Berlin, Heidelberg, 1996. ISBN 978-3-540-49939-8.
G. Ramalingam and Thomas Reps. An incremental algorithm for maintaining the dominator tree of a reducible flowgraph. In Proc. of the 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’94, pages 287–296, New York, NY, USA, 1994. ACM. ISBN 0-89791-636-0.
Vugranam C. Sreedhar and Guang R. Gao. A linear time algorithm for placing φ-nodes. In Proceedings of the 22Nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’95, pages 62–73, New York, NY, USA,1995. ACM. ISBN 0-89791-692-1.
Vugranam C. Sreedhar, Guang R. Gao, and Yong-Fong Lee. Incremental computation of dominator trees. ACM Trans. Program. Lang. Syst., 19(2):239–252, March 1997. ISSN 0164-0925.
Paul F. Dietz. Maintaining order in a linked list. In Proc. of the Fourteenth Annual ACM Symposium on Theory of Computing, STOC ’82, pages 122–127, New York, NY, USA, 1982. ACM. ISBN 0-89791-070-2.
Paolo G. Franciosa, Giorgio Gambosi, and Umberto Nanni. The incremental maintenance of a depth-first-search tree in directed acyclic graphs. Information Processing Letters, 61(2):113 – 120, 1997. ISSN 0020-0190.
Mihalis Pitidis and Konstantinos Sagonas. Purity in Erlang. In Jurriaan Hage and Marco T. Morazán, editors, Implementation and Application of Functional Languages, pages 137–152, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. ISBN 978-3-642-24276-2.
Istv´an Boz´o, D´aniel Horp´acsi, Zolt´an Horv´ath, R´obert Kitlei, Judit K˝oszegi, M´at´e Tejfel, and Melinda T´oth. RefactorErl - Source Code Analysis and Refactoring in Erlang. In Proc. of the 12th Symposium on Programming Languages and Software Tools, ISBN 978-9949-23-178-2, pages 138–148, Tallin, Estonia, October 2011.
Ericsson AB. Erlang/OTP (source code). https://github.com/erlang/otp, 2018. [Accessed: 2018.03.14].
Gregory Morse. Towards a General Theory of Incremental Decompilation. TDK Thesis, Budapest, Hungary, May 2018.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2018 Studia Universitatis Babeș-Bolyai Informatica
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
