Reliable identification of bounded-length viruses is NP-complete

被引：49

作者：

Spinellis, D ^{[1
]}

机构：

[1] Athens Univ Econ & Business, Dept Management Sci & Technol, GR-10434 Athens, Greece

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 2003年 / 49卷 / 01期

关键词：

buffer overflow; complexity; detection; identification; mutation; NP-complete; security; virus;

D O I：

10.1109/TIT.2002.806137

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：280 / 284

页数：5

共 20 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2] FAST STRING SEARCHING ALGORITHM [J].

BOYER, RS ;

MOORE, JS .

COMMUNICATIONS OF THE ACM, 1977, 20 (10) :762-772

[3]

Chess D. M., 2000, VIR B C SEPT

[4]

Cohen F., 1989, Computers & Security, V8, P325, DOI 10.1016/0167-4048(89)90089-8

[5]

Cohen F., 1987, Computers & Security, V6, P22, DOI 10.1016/0167-4048(87)90122-2

[6]

Cook S. A., 1971, P 3 ANN ACM S THEOR, P151, DOI [DOI 10.1145/800157.805047, 10.1145/800157.805047]

[7]

Cowan C., 2000, P DARPA INF SURV C E, VVolume 2, P119

[8]

DENNING PJ, 1988, AM SCI MAY, P236

[9]

Duff T., 1989, Computing Systems, V2, P155

[10]

Eichin M. W., 1989, Proceedings 1989 IEEE Symposium on Security and Privacy (Cat. No.89CH2703-7), P326, DOI 10.1109/SECPRI.1989.36307

← 1 2 →