Il problema di Cohen

Certo. Nel famoso risultato di Cohen, afferma che un rilevatore di virus perfetto dovrebbe emettere un allarme se e solo se il programma di input può mai agire come un virus (cioè infettare la macchina e causare danni).

Considera il seguente programma:

f();
infect_and_do_damage();

dove f() è una funzione innocua, e infect_and_do_damage() è un carico utile virale che infetta la tua macchina e provoca ogni tipo di danno (cancella il tuo disco rigido, ruba tutto il tuo denaro, qualunque cosa).

Consideriamo ciò che un rivelatore di virus perfetto dovrebbe dire su questo programma:

• Se f() può tornare, questo è un virus e il rilevatore di virus dovrebbe emettere un allarme.

• D'altra parte, se f() entra sempre in un ciclo infinito e non ritorna mai, la seconda riga è codice morto, infect_and_do_damage() non sarà mai invocato, questo programma non agirà mai come un virus, e il rilevatore di virus non dovrebbe disattivare alcun allarme.

Quindi, il problema di determinare se questo codice è un virus è equivalente al problema di determinare se la funzione f() può mai fermarsi. Questo è il famoso problema di arresto, che è noto per essere indecidibile.

In altre parole, rilevare se un programma è un virus è altrettanto difficile come rilevare se un programma si fermerà. Pertanto, entrambi i problemi sono indecidibili.

Si noti che questo è un risultato puramente teorico. L'indecidibilità è un costrutto puramente teorico. Il fatto che un problema sia indecidibile non è la fine della conversazione; è solo l'inizio della conversazione.

In pratica, ci sono vari modi per tentare di affrontare l'indecidibilità: ad esempio, prova a scrivere una soluzione che sia probabilisticamente corretta, anche se non è sempre corretta su tutti i programmi; prova a trovare una soluzione che funzioni per l'insieme di programmi che potresti trovare in pratica, anche se non funziona su tutti i programmi; consentire alla soluzione di rispondere occasionalmente "Non so" o di sbagliare dal dichiarare un programma un virus (o errare dalla parte dei falsi negativi); e così via.

Quindi non dovresti considerare questo come una dichiarazione definitiva che il rilevamento dei virus è impossibile - solo perché il problema è indecidibile non significa che sia necessariamente impossibile trovare una soluzione abbastanza buona nella pratica. Ma identifica alcune barriere fondamentali alla costruzione di un rilevatore di virus perfetto.

Per integrare la risposta di @ DW: anche se il problema potrebbe essere risolto, esiste anche un problema di definizione inerente: che è un virus, comunque?

Ad esempio, come dice la battuta, Microsoft Word è un virus:

• È molto diffuso.
• Si "replica": quando alcune persone iniziano a utilizzare i file .doc come base per la documentazione e gli scambi di lavoro, in qualche modo costringono altre persone a installare Word.
• La parola rende la vita di molte persone (me compreso) un inferno vivente (non continuamente, ma abbastanza spesso da essere notato).

In che modo Word non può essere un virus?

Naturalmente, molte persone (inclusi gli avvocati di Microsoft) sostengono che Word non è un virus e che è una asserzione ridicola. Tuttavia, questo dimostra che la proprietà not-a-virus è macroscopica : non è una distinzione netta proveniente dal solo codice (per "macroscopico" intendo che è una proprietà emergente del intero, non di uno degli opcode di assieme nell'eseguibile).

Facciamo un esempio meno esagerato: l'installer per un sistema operativo Linux. È un codice? Sì. Si copia da solo? Si Certamente. Modifica il settore di avvio? Assolutamente. Altera il sistema operativo già presente sulla macchina? Oh si. L'unica proprietà che lo rende un non -virus è che ogni volta che l'installatore fa tutto quanto sopra, l'utente umano lo vuole in questo modo .

Ne consegue che un antivirus perfetto deve in qualche modo indovinare ciò che l'utente desidera. E non può esserci una risposta assoluta a questo. In pratica, la maggior parte dei software antivirus tenta di fare "ipotesi plausibili" e, quando si tratta di decidere, decidere cosa l'utente dovrebbe desiderare (è così che stamattina ho passato un'ora frustrante cercando di inviare un file eseguibile a un cliente: alcuni antivirus ho deciso che non posso desiderare di mandare un file eseguibile via e-mail.