A methodology for machine language decompilation

ABSTRACT

Machine language decompilation is the translation of machine (assembly) language instruction sequences into statements in a high-level algebraic language such as PL/1. This process can be viewed as the inverse of compilation. Decompilation can be used as an aid for program conversion and program documentation. A general methodology for decompilation that is independent of a particular source and target language is presented. The basic approach is to map the source machine language to a high-level representation, which is relatively machine and language independent, and then translate to the chosen target language. An experimental decompiler was implemented to translate Knuth's MIXAL assembly language into PL/1.

REFERENCES

• 1: Maurice H Halstead, Machine-independent computer programming, Spartan Books, 1962
• 2: M. H. Halstead, Machine Independence and Third Generation Computers, Proceedings FJCC, 1962, 587-592.
• 3: IBM, 1400 Autocoder to COBOL Conversion Aid Program (360A-SE-19X), White Plains, New York, 1967.
• 4: M.H. Halstead, Using the Computer for Program Conversion, Datamation, May 1970, pp. 125-129.
• 5: William A. Sassaman, A Computer Program to Translate Machine Language into Fortran, Proceedings SJCC, 21966, pp. 235-239.
• 6: Barron Cornelius Housel, III, A study of decompiling machine languages into high-level machine independent languages, 1973
• 7: Edward S. Lowry , C. W. Medlock, Object code optimization, Communications of the ACM, v.12 n.1, p.13-22, Jan. 1969 [doi>10.1145/362835.362838]
• 8: F. E. Allen, Program Optimization, Annual Review in Automatic Programming, Vol. 5, Pergamon, 1969, pp. 239-307.
• 9: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 10: P. Barbe, Techniques for Automatic Program Translation, Software Engineering, Vol. 1, Academic Press Inc., 1970, pp. 151-165.
• 11: Frank Friedman, Private Communications, Purdue University, 1973.
• 12: Frank L Friedman , Victor B Schneider, A programming language for mini-computer systems, ACM SIGPLAN Notices, v.9 n.1, p.8-32, January 1974 [doi>10.1145/953220.953222]
• 13: Frances E. Allen, Control flow analysis, ACM SIGPLAN Notices, v.5 n.7, p.1-19, July 1970
• 14: F. E. Allen, J. Cocke, Graph-theoretic constructs for Program Control Flow Analysis, IBM Report RC3923, Yorktown Heights, July 1972.
• 15: John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
• 16: Dennis J. Frailey, Expression optimization using unary complement operators, ACM SIGPLAN Notices, v.5 n.7, p.67-85, July 1970
• 17: A Jump sequence which terminates an instruction block is subject to a number of constraints as discussed in Reference 6.
• 18: SG{n} may be a single block or a strongly connected region (SCR) subject to certain constraints as described in Reference 6.
• 19: R. Stockton Gaines, On the translation of machine language programs, Communications of the ACM, v.8 n.12, p.736-741, Dec. 1965 [doi>10.1145/365691.365925]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Macro and assembly languages

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation

General Terms:
Design, Languages

Keywords:
Decompiling, Inverse translation, Machine language translation, Optimization, Program documentation.