No Access

Reachability Analysis of Self Modifying Code

Tayssir Touili

https://orcid.org/0000-0002-1134-2220

LIPN, CNRS and University Paris 13, Villetaneuse, 93430, France

E-mail Address: touili@lipn.fr

Corresponding author.

Search for more papers by this author

and

Xin Ye

East China Normal University and LIPN, Villetaneuse, 93430, France

E-mail Address: xin@lipn.fr

Search for more papers by this author

https://doi.org/10.1142/S0129054122500290Cited by:0 (Source: Crossref)

Abstract

A Self modifying code is code that modifies its own instructions during execution time. It is nowadays widely used, especially in malware to make the code hard to analyse and to detect by anti-viruses. Thus, the analysis of such self modifying programs is a big challenge. Pushdown systems (PDSs) is a natural model that is extensively used for the analysis of sequential programs because they allow to accurately model procedure calls and mimic the program’s stack. In this work, we propose to extend the PushDown System model with self-modifying rules. We call the new model Self-Modifying PushDown System (SM-PDS). A SM-PDS is a PDS that can modify its own set of transitions during execution. We show how SM-PDSs can be used to naturally represent self-modifying programs and provide efficient algorithms to compute the backward and forward reachable configurations of SM-PDSs. We implemented our techniques in a tool and obtained encouraging results. In particular, we successfully applied our tool for the detection of self-modifying malware.

Communicated by Oscar Ibarra

Keywords:

References

1. A. Bertrand, M. Matias and D. Koen , A model for self-modifying code, In International Workshop on Information Hiding (2006). Google Scholar
2. A. Bouajjani, J. Esparza and O. Maler , Reachability analysis of pushdown automata: Application to model checking, In International Conference on Concurrency Theory (1997). Crossref, Google Scholar
3. F. Song and T. Touili , Efficient malware detection using model-checking, In International Symposium on Formal Methods (2012). Crossref, Google Scholar
4. F. Song and T. Touili , Ltl model-checking for malware detection, In International Conference on Tools and Algorithms for the Construction and Analysis of Systems (2013). Crossref, Google Scholar
5. G. Balakrishnan, T. W. Reps, N. Kidd, A. Lal, J. Lim et al., Model checking x86 executables with codesurfer/x86 and WPDS++, In International Conference on Computer Aided Verification (2005). Crossref, Google Scholar
6. G. Bonfante, J. Marion and D. Reynaud-Plantey , A computability perspective on selfmodifying programs, In 2009 Seventh IEEE International Conference on Software Engineering and Formal Methods (2009). Crossref, Google Scholar
7. H. Cai, Z. Shao and A. Vaynberg , Certified self-modifying code, ACM SIGPLAN Notices 42(6) (2007). Crossref, Google Scholar
8. J. Bergeron, M. Debbabi et al., Static detection of malicious code in executable programs, Int. J. of Req. Eng. 2001(184–189) (2001). Google Scholar
9. J. Esparza, D. Hansel, P. Rossmanith and S. Schwoon , Efficient algorithms for model checking pushdown systems, In International Conference on Computer Aided Verification (2000). Crossref, Google Scholar
10. J. Kinder, S. Katzenbeisser, C. Schallhart and H. Veith , Detecting malicious code by model checking, In International Conference on Detection of Intrusions and Malware, and Vulnerability Assessment (2005). Crossref, Google Scholar
11. H. Veith and J. Kinder , Jakstab: A static analysis platform for binaries, In International Conference on Computer Aided Verification (2008). Google Scholar
12. K. Coogan, S. Debray, T. Kaochar and G. Townsend , Automatic static unpacking of malware binaries, In 16th Working Conference on Reverse Engineering (2009). Crossref, Google Scholar
13. K. Gyung et al., Renovo: A hidden code extractor for packed executables, In Proceedings of the 2007 ACM workshop on Recurring Malcode (2007). Google Scholar
14. K. Roundy and B. Miller , Hybrid analysis and control of malware, In International Workshop on Recent Advances in Intrusion Detectio (2010). Crossref, Google Scholar
15. M. Christodorescu, S. Jha, S. Seshia, D. Song and R. Bryant , Semantics-aware malware detection, In 2005 IEEE Symposium Security and Privacy. Google Scholar
16. P. Royal, M. Halpin et al., Polyunpack: Automating the hidden-code extraction of unpack-executing malware, In 22nd Annual Computer Security Applications Conference (ACSAC’06) (2006). Crossref, Google Scholar
17. P. Singh and A. Lakhotia , Static verification of worm and virus behavior in binary executables using model checking, In IEEE Systems, Man and Cybernetics Society Information Assurance Workshop (2003). Crossref, Google Scholar
18. S. Blazy, V. Laporte and D. Pichardie , Verified abstract interpretation techniques for disassembling low-level self-modifying code, Journal of Automated Reasoning 56(3) (2016). Crossref, Web of Science, Google Scholar
19. S. Debray, K. Coogan and G. Townsend, On the semantics of self-unpacking malware code, Tech. rep. University of Arizona, Computer Science (2008). Google Scholar
20. S. Schwoon, Model-checking pushdown systems, PhD thesis, Technische Universität München, Universitätsbibliothek (2002). Google Scholar
21. EnSilo Research Team, Self-modifying code unpacking tool using dynamorio, https://github.com/BreakingMalware/Selfie. Google Scholar
22. Unpacker Tool, Automated unpacking: A behaviour based approach, https://github.com/malwaremusings/unpacker. Google Scholar
23. T. Touili and X. Ye , Reachability analysis of self modifying code, In 22nd International Conference on Engineering of Complex Computer Systems (ICECCS) (2017). Crossref, Google Scholar