Adapting Call-string Approach for x86 Obfuscated Binaries

• Davidson R. Boccardo UNESP
• Arun Lakhotia UNESP
• Aleardo Manacero Jr UNESP
• Michael Venable University of Louisiana at Lafayette

DOI: https://doi.org/10.5753/sbseg.2009.20629

Abstract

Call-string technique, a classic technique for interprocedural analysis, cannot be applied to binaries that do not follow stack conventions used by high-level language compilers. Examples are programs that make obfuscated procedure calls using push and return instructions, which is a technique largely used to hide malicious code. In this paper it is shown that a technique equivalent to call-string, the abstract stack graph (ASG), may be used to identify such obfuscations. An ASG contains nodes representing statements that push some element on the stack. An edge in the graph represents the next instruction that pushes a value on the abstract stack along some control flow path. For a program that manipulates stack using only call and return instructions, its ASG is equivalent to its call-graph. Since the ASG represents stack operations by any instruction it becomes a suitable substitute for the call-graph for interprocedural analysis of obfuscated binaries.

References

Amme, W., Braun, P., Zehendner, E., and Thomasset, F. (2000). Data dependence analysis of assembly code. In Int. J. Parallel Proc.

Balakrishnan, G. (2007). WYSINWYX: What You See Is Not What You eXecute. PhD thesis, C.S. Dept., Univ. of Wisconsin, Madison, WI.

Balakrishnan, G. and Reps, T. (2004). Analyzing memory accesses in x86 executables. In Proc. Int. Conf. on Compiler Construction, Springer-Verlag, pages 5–23, New York, NY.

Bergeron, J., Debbabi, M., Desharnais, J., Erhioui, M. M., Lavoie, Y., and Tawbi, N. (2001). Static detection of malicious code in executable programs. In Int. J. of Req. Eng.

Boccardo, D. R., Manacero Jr., A., and Falavinha Jr., J. N. (2007). Implications of obfuscated code in the development of av detectors (in portuguese). In XXXIV Seminario Integrado de Software e Hardware, SEMISH, pages 2277–2291, Rio de Janeiro, Brazil.

Christodorescu, M. and Jha, S. (2003). Static analysis of executables to detect malicious patterns. In Proc. of the 12th USENIX Security Symposium.

Cifuentes, C. and Fraboulet, A. (1997). Intraprocedural static slicing of binary executables. In Proc. Int. Conf. on Software Maintenance (ICSM), pages 188–195.

Cifuentes, C., Simon, D., and Fraboulet, A. (1998). Assembly to high-level language translation. In Proc. Int. Conf. on Software Maintenance (ICSM), pages 228–237.

Collberg, C., Thomborson, C., and Low, D. (1997). A taxonomy of obfuscating transformations. Technical Report 148, Department of Computer Science, University of Auckland.

Collberg, C. S. and Thomborson, C. (2002). Watermarking, tamper-proofing, and obfuscation tools for software protection. IEEE Trans. on Soft. Eng., 28(8):735–746.

Cousot, P. and Cousot, R. (2002). Modular static program analysis. In CC’02, pages 159–178.

Dalla Preda, M., Christodorescu, M., Jha, S., and Debray, S. (2007). A semanticsbased approach to malware detection. In Proc. Principles of Programming Languages (POPL), pages 377–388, New York, NY, USA. ACM.

Debray, S. K., Muth, R., and Weippert, M. (1998). Alias analysis of executable code. In Proc. Principles of Programming Languages (POPL), pages 12–24.

Goodwin, D. W. (1997). Interprocedural dataflow analysis in an executable optimizer. In Conf. on Prog. Lang. Design and Implementation (PLDI), pages 122–133, New York, NY, USA. ACM.

Guo, B., Bridges, M. J., Triantafyllis, S., Ottoni, G., Raman, E., and August, D. (2005). Practical and accurate low-level pointer analysis. In 3nd Int. Symp. on Code Gen. and Opt.

Kinder, J., Veith, H., and Zuleger, F. (2009). An abstract interpretation-based framework for control flow reconstruction from binaries. In 10th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI 2009), pages 214– 228.

Lakhotia, A. (1993). Constructing call multigraphs using dependence graphs. In Proc. Principles of Programming Languages (POPL), pages 273–284.

Lakhotia, A., Kumar, E. U., and Venable, M. (2005). A method for detecting obfuscated calls in malicious binaries. IEEE Transactions on Software Engineering, 31(11):955– 968.

Lakhotia, A. and Singh, P. K. (2003). Challenges in getting ’formal’ with viruses. Virus Bulletin, pages 15–19.

Larus, J. R. and Schnarr, E. (1995). Eel: Machine-independent executable editing. In Conf. on Prog. Lang. Design and Implementation (PLDI), pages 291–300.

Linn, C. and Debray, S. (2003). Obfuscation of executable code to improve resistance to static disassembly. In 10th ACM Conf. on Computer and Communications Security (CCS).

Milanova, A., Rountev, A., and Ryder, B. G. (2004). Precise call graphs for c programs with function pointers. In Autom. Softw. Eng., pages 11(1): 7–26.

Muller-Olm, M. and Seidl, H. (2004). Precise interprocedural analysis through linear algebra. In Proc. Principles of Programming Languages (POPL), pages 330–341.

Reps, T. and Balakrishnan, G. (2008). Improved memory-access analysis for x86 executables. In Proc. Int. Conf. on Compiler Construction.

Reps, T., Balakrishnan, G., and Lim, J. (2006). Intermediate-representation recovery from low-level code. In Proc. Workshop on Partial Evaluation and Program Manipulation (PEPM), Charleston, SC.

Sagiv, M., Reps, T., and Horwitz, S. (1996). Precise interprocedural dataflow analysis with applications to constant propagation. In Theor. Comput. Sci., pages 167(1–2): 131–170.

Schwarz, B., Debray, S. K., and Andrews, G. R. (2001). PLTO: A link-time optimizer for the Intel IA-32 architecture. In Proc. Workshop on Binary Translation (WBT).

Sharir, M. and Pnueli, A. (1981). Two approaches to interprocedural data flow analysis. S.S. Muchnick and N.D. Jones, editors, Program Flow Analysis: Theory and Applications, chapter 7, pages 189-234. Prentice-Hall, Englewood Cliffs, NJ.

Srivastava, A. and Wall, D. (1993). A practical system for intermodule code optimization at linktime. Journal of Programming Languages, 1(I):1–18.

Szor, P. and Ferrie, P. (2001). Hunting for metamorphic. In Proc. Virus Bull. Conf.

Thompson, K. (1984). Reflections on trusting trust. Commun. ACM, 27(8):761–763.

Venable, M., Chouchane, M. R., Karim, M. E., and Lakhotia, A. (2005). Analyzing memory accesses in obfuscated x86 executables. In DIMVA’05, pages 1–18.

Venkitaraman, R. and Gupta, G. (2004). Static program analysis of embedded executable assembly code. In CASES ’04: Proc. of the 2004 Int. Conf. on Compilers, architecture, and synthesis for embedded systems, pages 157–166, New York, NY, USA. ACM.

Walenstein, A., Mathur, R., Chouchane, M. R., and Lakhotia, A. (2006). Normalizing metamorphic malware using term-rewriting. In 6th IEEE Int. Workshop on Source Code Analysis and Manipulation (SCAM).

Wroblewski, G. (2002). General method of program code obfuscation. In Proc. Int. Conf. on Software Engineering Research and Practice (SERP).

Zhang, W. and Ryder, B. G. (2007). Automatic construction of accurate application call graph with library call abstraction for java. Journal of Software Maintenance, pages 19(4): 231–252.