A computability perspective on self-modifying programs

Abstract-In order to increase their stealth, malware commonly use the self-modification property of programs. By doing so, programs can hide their real code so that it is difficult to define a signature for it. But then, what is the meaning of those programs: the obfuscated form, or the hidden one? Furthermore, from a computability perspective, it becomes hard to speak about the program since, its own code varies over time. To cope with these issues, we provide an operational semantics for self-modifying programs and we show that they can be constructively rewritten to a non-modifying program