On the Impossibility of Virus Detection

David Evans
12 February 2017


The question of how to detect malicious programs seems like a practical one, but at its core depends on the fundamental nature of general purpose computers and deep theoretical questions about what computers can and cannot do. This essay starts by formalizing the question of what it means to detect a virus. Then, we discuss theoretical results that show solving this (and most other important computer security problems) is impossible for general purpose computers. But impossible doesn't mean hopeless --- it just means we have to redefine our problems and approaches, and aim for solutions that work well in practice, even if nothing can work in theory.


[PDF], 6 pages


This paper was instigated by Melih Abdulhayoglu, based on my posted lecture slides from my Introduction to Computing course. Some of the ideas here are covered in Chapter 12 of my introductory computing textbook.