Effective Enumeration of Infinitely Many Programs that Evade Formal Malware Analysis



Liagkou, Vasiliki, Nastou, Panagiotis E, Spirakis, Paul ORCID: 0000-0001-5396-3749 and Stamatiou, Yannis C
(2021) Effective Enumeration of Infinitely Many Programs that Evade Formal Malware Analysis. In: 5th International Symposium on Cyber Security Cryptology and Machine Learning (CSCML2021), 2021-7-8 - 2021-7-9, Beer-Sheva Israel.

[img] Text
cscml21.pdf - Author Accepted Manuscript

Download (588kB) | Preview

Abstract

The formal study of computer malware was initiated in the seminal work of Fred Cohen in the mid 80s who applied elements of the Theory of Computation in the investigation of the theoretical limits of using the Turing Machine formal model of computation in detecting viruses. Cohen gave a simple but realistic, formal, definition of the characteristic actions of a computer virus as a Turing Machine that replicates itself and then proved that constructing a Turing Machine that recognizes viruses (i.e. Turing Machines that act like viruses) is impossible, by reducing the Halting Problem, which is undecidable, to the problem of recognizing a computer virus. In this paper we complement Cohen’s approach along similar lines, based on Recursion Function Theory and the Theory of Computation. More specifically, after providing a simple generalization of Cohen’s definition of a computer virus, we show that the malware/non-malware classification problem is undecidable under this new definition. Moreover, we show that to any formal system, there correspond infinitely many, effectively constructible, programs for which no proof can be produced by the formal system that they are either malware or non-malware programs. In other words, given any formal system, one can provide a procedure that generates, systematically, an infinite number of impossible to classify, within the formal system, programs.

Item Type: Conference or Workshop Item (Unspecified)
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 12 Apr 2021 08:43
Last Modified: 18 Mar 2024 01:35
DOI: 10.1007/978-3-030-78086-9_18
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3118830