Problem Definition
在許多研究中,檢測惡意軟體的問題已被展示為 NP-Cpmplete。[^A_comprehensive_review_on_malware_detection_approaches]
A. Difficulty of Problem in Theory
早期的惡意軟體的檢測使用病毒的檢測方式。根據早期的研究,這種檢測方式是不可能且 NP-complete。會造成這樣的原因,是因為檢測病毒的程式有矛盾。假設有一個檢測者 $D$ 會去判斷程式 $P$ 是否為病毒。若 $P$ 是病毒,$D$ 會把它標記起來,讓他無法去與其他程式互動,就像非病毒的一般程式一樣。但若 $D$ 沒有將 $P$ 標記起來(由於 $P$ 表現得像非病毒),$P$ 就會去感染其他程式。[^Computer_viruses:_theory_and_experiments]
According to M. Chess and R. White, there is no program that detects all viruses without false positives (FPs) because viruses are polymorphic and can be exist in different forms[^An_undetectable_computer_virus].
According to M. Adleman detecting a virus is quite intractable and almost impossible.[^An_abstract_theory_of_computer_viruses] This is because according to Gödel numberings of the partial recursive functions, it is not possible to create detecting mechanism.
Zuo et al. claim that there exist computer viruses whose detecting procedures have sufficiently large time complexity, and there are undecidable viruses which have no minimal detecting procedure.[^On_the_time_complexity_of_computer_viruses]