Why is there no universal antivirus?

(To Alessandro Rugolo)

Since computer viruses exist, there have also been antivirus programs. This is an obvious reality. But why are antiviruses not effective against all viruses?

Answering this question is intuitively simple: because there are always new viruses that behave differently from the previous ones and antiviruses work only with what they know. If you go to see what is behind the intuitive answer then things get complicated, because if you try to investigate the problem, you go into a field of study that is not easy at all.

To understand what we are talking about it is necessary to introduce some concepts or the meaning of "heuristic" and of "Turing machine".

The term "heuristic", in mathematics refers to a procedure used to predict a result which must however be validated by experience as it is not rigorous.

Instead with "universal Turing machine" we mean one ideal machine that programmed allows you to perform any operation, or to calculate any computable function in a finite number of elementary steps.

Well a number of years ago Leonard Max Adleman, besides being one of the three inventors of the RSA encryption algorithm (Rivest-Shamir, Adleman) and the first to have used the term "virus" in computer science to identify malicious agents, also showed that if there was an algorithm capable of detecting the presence of a virus in a general case, this algorithm would be able to solve the problem known under the name of "halting problem". This problem theoretically addressed by Alan Turing consists in say if, given any program and any input, it is possible to determine whether the program will sooner or later stop or continue to run indefinitely. Alan Turing showed that this problem is "undecidable".

Well, to return to our problem, that is, if there can be a program capable of detecting any virus, Leonard Max Adleman has shown that this problem is equivalent to the better known "halting problem" and therefore it too undecidable.

If we suppose, and I see no reason not to, that both Turing and Adleman are right, then we must conclude that it is not possible to create an antivirus program, at least it is not possible to create a generalist antivirus program.
And this is where the term comes back into play heuristic. If it is indeed true that there is no general antivirus that is suitable for all viruses, nobody prevents from working for approximations of the known reality and trying to predict the future behavior of the viruses, their possible evolution. In this sense, the antivirus manufacturers work, trying to create antivirus that can be used against known viruses and against the most likely evolutions of the same.

Photo: US Air Force