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


A técnica 'call-string', técnica clássica para análise interprocedural, não pode ser aplicada a binários que não seguem padrões de uso da pilha utilizados por compiladores de linguagens de alto nível. Exemplos são programas que ofuscam chamadas de procedimento usando uma combinação de instruções 'push' e 'ret', que é uma técnica extremamente utilizada para esconder código malicioso. Neste artigo, uma técnica equivalente à 'call-string' é demonstrada, em que um grafo abstrato da pilha pode ser utilizado para identificar estas ofuscações. Um grafo abstrato da pilha contem nós representando instruções que realizam inserção na pilha. Uma aresta neste grafo representa a próxima instrução que realiza a inserção na pilha abstrata ao longo de um caminho do fluxo de controle. Para um programa que manipula a pilha utilizando somente instruções 'call' e 'ret', seu grafo abstrato da pilha é equivalente ao seu grafo de chamadas. Desde que o grafo abstrato da pilha representa operações na pilha por qualquer instrução, o mesmo torna-se um substituto apropriado para o grafo de chamadas para análise interprocedural de binários ofuscados.


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.
BOCCARDO, Davidson R.; LAKHOTIA, Arun; MANACERO JR, Aleardo; VENABLE, Michael. Adapting Call-string Approach for x86 Obfuscated Binaries. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 9. , 2009, Campinas. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2009 . p. 145-158. DOI: