Intermediate-representation recovery from low-level code

ABSTRACT

The goal of our work is to create tools that an analyst can use to understand the workings of COTS components, plugins, mobile code, and DLLs, as well as memory snapshots of worms and virus-infected code. This paper describes how static analysis provides techniques that can be used to recover intermediate representations that are similar to those that can be created for a program written in a high-level language.

REFERENCES

• 1: PREfast with driver-specific rules, October 2004. WHDC, Microsoft Corp., http://www.microsoft.com/whdc/devtools/tools/PREfastdrv.mspx.
• 2: Wolfram Amme , Peter Braun , François Thomasset , Eberhard Zehendner, Data Dependence Analysis of Assembly Code, International Journal of Parallel Programming, v.28 n.5, p.431-467, Oct. 2000 [doi>10.1023/A:1007588710878]
• 3: W. Backes. Programmanalyse des XRTL Zwischencodes. PhD thesis, Universitaet des Saarlandes, 2004. (In German.).
• 4: G. Balakrishnan and T. Reps. Analyzing memory accesses in x86 executables. In CC, 2004.
• 5: G. Balakrishnan and T. Reps. Recency-abstraction for heap-allocated storage. TR 1548, UW-Madison, December 2005.
• 6: G. Balakrishnan and T. Reps. Recovery of variables and heap structure in x86 executables. TR 1533, UW-Madison, 2005.
• 7: G. Balakrishnan, T. Reps, D. Melski, and T. Teitelbaum. WYSINWYX: What You See Is Not What You eXecute. In VSTTE, 2005.
• 8: Thomas Ball , Sriram K. Rajamani, The SLAM Toolkit, Proceedings of the 13th International Conference on Computer Aided Verification, p.260-264, July 18-22, 2001
• 9: J. Bergeron, M. Debbabi, J. Desharnais, M. M. Erhioui, Y. Lavoie, and N. Tawbi. Static detection of malicious code in executable programs. Int. J. of Req. Eng., 2001.
• 10: J. Bergeron , Mourad Debbabi , M. M. Erhioui , Béchir Ktari, Static Analysis of Binary Code to Isolate Malicious Behaviors, Proceedings of the 8th Workshop on Enabling Technologies on Infrastructure for Collaborative Enterprises, p.184-189, June 16-18, 1999
• 11: Ahmed Bouajjani , Javier Esparza , Tayssir Touili, A generic approach to the static analysis of concurrent programs with procedures, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.62-73, January 15-17, 2003, New Orleans, Louisiana, USA
• 12: William R. Bush , Jonathan D. Pincus , David J. Sielaff, A static analyzer for finding dynamic programming errors, Software—Practice & Experience, v.30 n.7, p.775-802, June 2000 [doi>10.1002/(SICI)1097-024X(200006)30:7<775::AID-SPE309>3.0.CO;2-H]
• 13: H. Chen, D. Dean, and D. Wagner. Model checking one million lines of C code. In NDSS, 2004.
• 14: Hao Chen , David Wagner, MOPS: an infrastructure for examining security properties of software, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586142]
• 15: C. Cifuentes and A. Fraboulet. Interprocedural data flow recovery of high-level language code from assembly. TR 421, U. Queensland, 1997.
• 16: Cristina Cifuentes , Antoine Fraboulet, Intraprocedural Static Slicing of Binary Executables, Proceedings of the International Conference on Software Maintenance, p.188, October 01-03, 1997
• 17: Cristina Cifuentes , Doug Simon , Antoine Fraboulet, Assembly to High-Level Language Translation, Proceedings of the International Conference on Software Maintenance, p.228, March 16-19, 1998
• 18: CodeSurfer, GrammaTech, Inc. "http://www.grammatech.com".
• 19: K. D. Cooper , K. Kennedy, Interprocedural side-effect analysis in linear time, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.57-66, June 20-24, 1988, Atlanta, Georgia, United States
• 20: James C. Corbett , Matthew B. Dwyer , John Hatcliff , Shawn Laubach , Corina S. Păsăreanu , Robby , Hongjun Zheng, Bandera: extracting finite-state models from Java source code, Proceedings of the 22nd international conference on Software engineering, p.439-448, June 04-11, 2000, Limerick, Ireland [doi>10.1145/337180.337234]
• 21: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 22: Manuvir Das , Sorin Lerner , Mark Seigle, ESP: path-sensitive program verification in polynomial time, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 23: Saumya Debray , Robert Muth , Matthew Weippert, Alias analysis of executable code, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-24, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268948]
• 24: Peter Harry Eidorff , Fritz Henglein , Christian Mossin , Henning Niss , Morten Heine Sørensen , Mads Tofte, AnnoDomini: from type theory to Year 2000 conversion tool, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292543]
• 25: D. R. Engler, B. Chelf, A. Chou, and S. Hallem. Checking system rules using system-specific, programmer-written compiler extensions. In OSDI. 2000.
• 26: Bolei Guo , Matthew J. Bridges , Spyridon Triantafyllis , Guilherme Ottoni , Easwaran Raman , David I. August, Practical and Accurate Low-Level Pointer Analysis, Proceedings of the international symposium on Code generation and optimization, p.291-302, March 20-23, 2005 [doi>10.1109/CGO.2005.27]
• 27: K. Havelund and T. Pressburger. Model checking Java programs using Java PathFinder. STTT, 2(4), 2000.
• 28: Thomas A. Henzinger , Ranjit Jhala , Rupak Majumdar , Grégoire Sutre, Lazy abstraction, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.58-70, January 16-18, 2002, Portland, Oregon
• 29: Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
• 30: M. Howard. Some bad news and some good news. October 2002. MSDN, Microsoft Corp.
• 31: IDAPro disassembler, http://www.datarescue.com/idabase/.
• 32: N. Kidd, T. Reps, D. Melski, and A. Lal. WPDS++; A C++ library for weighted pushdown systems, 2004. http://www.cs.wisc.edu/wpis/wpds++/.
• 33: A. Lal, T. Reps, and G. Balakrishnan. Extended weighted pushdown systems. In CAV, 2005.
• 34: James R. Larus , Eric Schnarr, EEL: machine-independent executable editing, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.291-300, June 18-21, 1995, La Jolla, California, United States
• 35: M. Müller-Olm and H. Seidl. Analysis of modular arithmetic. In ESOP, 2005.
• 36: A. Mycroft. Type-based decompilation. In ESOP, 1999.
• 37: G. Ramalingam , John Field , Frank Tip, Aggregate structure identification and its application to program analysis, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.119-132, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292553]
• 38: T. Reps, G. Balakrishnan, J. Lim, and T. Teitelbaum. A next-generation platform for analyzing executables. In APLAS, 2005.
• 39: T. Reps, S. Schwoon, and S. Jha. Weighted pushdown systems and their application to interprocedural dataflow analysis. In SAS, 2003.
• 40: Thomas Reps , Stefan Schwoon , Somesh Jha , David Melski, Weighted pushdown systems and their application to interprocedural dataflow analysis, Science of Computer Programming, v.58 n.1-2, p.206-263, October 2005 [doi>10.1016/j.scico.2005.02.009]
• 41: Xavier Rival, Abstract Interpretation-Based Certification of Assembly Code, Proceedings of the 4th International Conference on Verification, Model Checking, and Abstract Interpretation, p.41-55, January 09-11, 2002
• 42: M. Sharir and A. Pnueli. Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and Applications, chapter 7. Prentice-Hall, Englewood Cliffs, NJ, 1981.
• 43: A. Srivastava, A. Edwards, and H. Vo. Vulcan: Binary transformation in a distributed environment. TR 2001--50, Microsoft Research, 2001.
• 44: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
• 45: D. Wagner, J. Foster, E. Brewer, and A. Aiken. A first step towards automated detection of buffer overrun vulnerabilities. In NDSS, 2000.
• 46: D. W. Wall. Systems for late code modification. In R. Giegerich and S. L. Graham, editors, Code Generation - Concepts. Tools, Techniques, pages 275--293. Springer-Verlag, 1992.
• 47: Henry S. Warren, Hacker's Delight, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 48: Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Partial evaluation

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program synthesis

General Terms:
Design, Verification