  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.
