VX Heaven

Library Collection Sources Engines Constructors Simulators Utilities Links Forum

Reductions of the general virus detection problem

Ferenc Leitold
In U. E. Gattiker (Ed.), Conference Proceedings EICAR International Conference, pp. 24-30
ISBN 87-987271-2-5
June 2001

PDFDownload PDF (57.24Kb) (You need to be registered on forum)
[Back to index] [Comments]


Theoretically it is impossible to generate a program which can solve the general virus detection problem. This theorem has been proved in different ways in the literature. Since the general virus detection problem is not solvable, we have to reduce the problem: we can deal "only" with a subset of viruses. For example, we can limit the storage space of viruses or we can limit the execution time of viruses. Theoretically in these cases it can be proved that there is an algorithm for the virus detection problem. On the other hand, we can reduce the general virus detection problem if we deal with the known viruses only. In this paper, I would like to examine the virus detection problem, the possible reductions of the virus detection problem and, of course, I would like to highlight the usability of the virus detection algorithms in the practice too.

[Read the article]

By accessing, viewing, downloading or otherwise using this content you agree to be bound by the Terms of Use! aka