Abstract.

This paper investigates the possibility of malware detection. We first used countability to show that the malware detectors cannot count malware sets. Then, we proved that the malware detection problem is in the NP-complete class by reducing the detection problem into well-known NP-complete problems including Satisfiability, Clique, and Vertex Cover. After that, we tested malware detectors’ performances based on signature-, heuristic- and behaviorbased detection approaches in practice. The experiment test results confirmed that it is not possible to detect all malware strains in theory as well as practice with current technology.

Keywords:

theory of malware, malware detection, possibility of detection, NP-complete, decision problem, undecidable problem.