VX Heavens

Bibliothek Sammlung Quellcodes Engines Konstruktoren Simulatoren Zusatzprogramme Links Forum
Minimize
Lesezeichen

Reliable Identification of Bounded-length Viruses is NP-complete

Diomidis Spinellis
IEEE Transactions on Information Theory, 49(1), pp. 280-284, January 2003.
ISSN 0018-9448
January 2003

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

Abstract

A virus is a program that replicates itself by copying its code into other files. A common virus protection mechanism involves scanning files to detect code patterns of known viruses. We prove that the problem of reliably identifying a bounded-length mutating virus is NP-complete by showing that a virus detector for a certain virus strain can be used to solve the satisfiability problem. The implication of this result is that virus identification methods will be facing increasing strain as virus mutation and hosting strategies mature, and that different protection methods should be developed and employed.

[Read the article]

deenesitfrplruua