String analysis for x86 binaries

ABSTRACT

Information about string values at key points in a program can help program understanding, reverse engineering, and forensics. We present a static-analysis technique for recovering possible string values in an executable program, when no debug information or source code is available. The result of our analysis is a regular language that describes a superset of the string values possible at a given program point. We also impart some of the lessons learned in the process of implementing our analysis as a tool for recovering C-style strings in x86 executables.

REFERENCES

• 1: Rita Z. Altucher , William Landi, An extended form of must alias analysis for dynamic allocation, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.74-84, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199466]
• 2: G. Balakrishnan and T. Reps. Analyzing memory accesses in x86 executables. In Proceedings of the International Conference on Compiler Construction (CC'04), pages 5--23, 2004.
• 3: Aske Simon Christensen , Anders Møller , Michael I. Schwartzbach, Extending Java for high-level Web service construction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.6, p.814-875, November 2003 [doi>10.1145/945885.945890]
• 4: A. S. Christensen, A. Møller, and M. I. Schwartzbach. Precise analysis of string expressions. In Proceedings of the 10th International Static Analysis Symposium (SAS '03), volume 2694 of Lecture Notes in Computer Science, pages 1--18. Springer-Verlag, June 2003.
• 5: C. Cifuentes and A. Fraboulet. Interprocedural dataflow recovery of high-level language code from assembly. Technical report, University of Queensland, 1997.
• 6: 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
• 7: DataRescue sa/nv. IDA Pro - interactive disassembler. Published online at http://www.datarescue.com/idabase/. Last accessed on 3 Feb. 2003.
• 8: 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]
• 9: Nurit Dor , Michael Rodeh , Mooly Sagiv, CSSV: towards a realistic tool for statically detecting all buffer overflows in C, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 10: Vinod Ganapathy , Somesh Jha , David Chandler , David Melski , David Vitek, Buffer overrun detection using linear programming and static analysis, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948155]
• 11: Carl Gould , Zhendong Su , Premkumar Devanbu, JDBC Checker: A Static Analysis Tool for SQL/JDBC Applications, Proceedings of the 26th International Conference on Software Engineering, p.697-698, May 23-28, 2004
• 12: Carl Gould , Zhendong Su , Premkumar Devanbu, Static Checking of Dynamically Generated Queries in Database Applications, Proceedings of the 26th International Conference on Software Engineering, p.645-654, May 23-28, 2004
• 13: Christian Kirkegaard , Anders Mller , Michael I. Schwartzbach, Static Analysis of XML Transformations in Java, IEEE Transactions on Software Engineering, v.30 n.3, p.181-192, March 2004 [doi>10.1109/TSE.2004.1271173]
• 14: Arun Lakhotia , Eric Uday Kumar, Abstracting Stack to Detect Obfuscated Calls in Binaries, Proceedings of the Source Code Analysis and Manipulation, Fourth IEEE International Workshop on (SCAM'04), p.17-26, September 15-16, 2004 [doi>10.1109/SCAM.2004.1]
• 15: D. Larochelle and D. Evans. Statically detecting likely buffer overflow vulnerabilities. In Proceedings of the 2001 USENIX Security Symposium, 2001.
• 16: M. Mohri and M.-J. Nederhof. Regular approximation of context-free grammars through transformation. In J.-C. Junqua and G. van Noord, editors, Robustness in Language and Speech Technology, pages 153--163. Kluwer Academic Publishers, 2001.
• 17: Alan Mycroft, Type-Based Decompilation (or Program Reconstruction via Type Reconstruction), Proceedings of the 8th European Symposium on Programming Languages and Systems, p.208-223, March 22-28, 1999
• 18: 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]
• 19: Radu Rugina , Martin Rinard, Symbolic bounds analysis of pointers, array indices, and accessed memory regions, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.182-195, June 18-21, 2000, Vancouver, British Columbia, Canada
• 20: R. Vall, E. Phong, C. Etienne, G. Laurie, H. Patrick, and L. Vijay. Soot - a Java bytecode optimization framework, 1999.
• 21: D. Wagner, J. S. Foster, E. A. Brewer, and A. Aiken. A first step towards automated detection of buffer overrun vulnerabilities. In Proceedings of the Networking and Distributed System Security Symposium (NDSS'00), San Diego, California, Feb. 2000.
• 22: Yichen Xie , Andy Chou , Dawson Engler, ARCHER: using symbolic, path-sensitive analysis to detect memory access errors, ACM SIGSOFT Software Engineering Notes, v.28 n.5, September 2003

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

General Terms:
Algorithms, Design, Theory