it-swarm-eu.dev

È stato matematicamente dimostrato che l'antivirus non è in grado di rilevare tutti i virus?

Quale analisi faceva riferimento a Bruce Schneier quando scrisse:

I virus non hanno una "cura". È stato matematicamente dimostrato che è sempre possibile scrivere un virus che nessun programma antivirus esistente non può fermare.

Dal libro Secrets & Lies di Bruce Schneier, pagina 154.

148
Cate

Sotto una possibile interpretazione di ciò, è il risultato di teorema di Rice . Un programma è dannoso se esegue un'azione dannosa, che lo rende una proprietà semantica. Alcuni programmi sono dannosi e altri no, il che lo rende una proprietà non banale. Pertanto, secondo il teorema di Rice, nel caso generale è indecifrabile che un programma sia dannoso.

In realtà, il contrario può essere facilmente dimostrato: poiché tutti i virus informatici sono codice eseguibile in un modo o nell'altro, tutto ciò che devi fare è scrivere un programma antivirus che riporti QUALSIASI codice eseguibile come virale. Ne consegue logicamente che un tale programma rileverà TUTTI i possibili virus:

  • Tutto il codice viene rilevato dal tuo antivirus (C → D)
  • Tutti i virus sono in codice (V → C)
  • Tutti i virus vengono rilevati dal tuo antivirus (V → D)

Certo, si potrebbe argomentare su questo software antivirus che elimina troppi "falsi positivi". Ma quali sono i criteri per decidere se un positivo è falso o vero? Ah! Viene fuori la distinzione tra codice benigno e codice maligno, tra una suite onesta di "controllo remoto del PC" e un trojan come Netbus è completamente arbitrario, e quindi l'intera questione è inutile.

191
walen

Secondo Wikipedia:

Nel 1987, Fred Cohen ha pubblicato una dimostrazione che non esiste un algoritmo in grado di rilevare perfettamente tutti i possibili virus.

Fa riferimento anche a questo documento . Questa potrebbe essere l'analisi a cui si riferiva il signor Schneier.

93
Harry Johnston

L'affermazione non può essere provata matematicamente a meno che non sia riformulata come proposizione matematica.

Per lo meno, ciò richiede una definizione matematicamente solida di cosa sia un "virus": che è una sfida; e potresti finire con un'astrazione che non è utile nella pratica, perché include alcuni comportamenti che le persone considerano del tutto benigni e utili e/o esclude alcuni comportamenti che le persone considerano antisociali.

La cosa difficile qui è che un virus è un programma che cambia il suo ambiente in qualche modo, e ogni tentativo di definire rigorosamente l'ambiente sarà troppo limitante per un uso pratico.

Quindi direi di no: la proposta non può essere provata matematicamente, ed è perché non può essere formulata matematicamente.

25
Michael Kay

tl; dr - La risposta dipende esattamente da quali requisiti imponi alla domanda.

  1. Se desideri semplicemente rilevare tutti i virus senza ulteriori vincoli, contrassegna semplicemente qualsiasi cosa come virus e il gioco è fatto.

  2. Se si desidera identificare correttamente tutti i programmi come virus o meno, è impossibile nel caso non associato poiché il problema di classificazione si riduce al problema di arresto.

  3. Se si desidera identificare correttamente tutti i programmi come virus o meno e si sta prendendo in considerazione una macchina finita, è teoricamente possibile, ma generalmente non fattibile nella pratica.

  4. Se si consente al computer di produrre errori casuali, qualsiasi programma può essere un virus.

Caso 1: rilevamento completo dei virus

Ovviamente, contrassegnare tutti i programmi come virus li cattura tutti. ( Pok'e'mon !)

A partire da questo caso per sottolineare che non è difficile rilevare tutti i virus; piuttosto, il problema teorico specifico sta classificando correttamente i programmi iff sono virus.

Caso 2: impossibile classificarlo correttamente in uno scenario generale, illimitato

Considera il programma:

doHaltingProblem();          //  Not a virus operation itself
installEveryVirusEver();     //  Definitely a virus operation, but will it happen?

In questo caso, il programma è un virus solo se problema di arresto si interrompe, consentendo a installEveryVirusEver() di verificarsi. Pertanto, il rilevamento di virus si riduce al problema di arresto nel caso generale e non associato.

Caso 3: possibile con la ricerca della forza bruta in scenari limitati

Se i programmi da classificare come virus o meno devono funzionare su una macchina finita, allora puoi semplicemente simulare la macchina in esecuzione da ogni possibile stato iniziale. Le macchine finite eventualmente ritornano ad uno stato precedente , quindi è necessariamente un'analisi finita (se lunga).

Caso 4: le macchine che possono sbagliare possono far emergere spontaneamente virus

Supponendo che una macchina possa eseguire un programma che sarebbe considerato un virus e che esiste una possibilità diversa da zero di una mutazione casuale che lo sposta in quello stato, quindi alla fine dovrebbe arrivare a uno stato di virus.

Che è una specie di punto noioso, ma solo per completezza.


Discussione sulla citazione nella domanda

I virus non hanno una "cura". È stato matematicamente dimostrato che è sempre possibile scrivere un virus che nessun programma antivirus esistente non può fermare.

" Secrets & Lies" , Bruce Schneier, pagina 154

Come sottolineato nel caso (1) sopra, è possibile contrassegnare tutti i virus semplicemente contrassegnando tutto come virus; questo è facile. Ciò che è impossibile è, in un caso non associato, determinare se ogni possibile programma è un virus o meno.

Inoltre, è difficile stabilire se determinati programmi sono virus in casi rilegati. Ad esempio, considera il programma:

var toExecute = decryptByBruteForce([ciphertext]);  // Decrypt the next part of the program by brute-force
run(toExecute);                                     // Run the now-decrypted part of the program

Come discusso nel caso (3), questo programma può essere classificato come virus o meno quando eseguito su una macchina finita, ma poiché ciò richiederebbe la forzatura bruta di un messaggio crittografato, non è probabilmente fattibile in scenari pratici.

Quindi, nelle applicazioni del mondo reale, si riduce a un problema di euristica : i programmi antivirus fanno ipotesi su cosa sia un virus o no. O se si desidera una sicurezza più affidabile, è possibile che un programma antivirus contrassegni tutto ciò che non può rivelarsi sicuro, eludendo il problema della necessità di classificare ogni programma possibile.

Sfortunatamente, l'uso dell'euristica fornisce agli attacchi informati buchi di sicurezza da colpire. Senza leggere la fonte della citazione, sospetto che questo problema sia quello a cui stavano cercando di fare riferimento.

18
Nat

Dipende dalla tua definizione di "stop".

Se definisci stop come "rileva, in anticipo, quel codice potrebbe fare qualcosa di dannoso e impedirne l'esecuzione", allora come altri hanno già detto, questo è impossibile, secondo il teorema di Rice.

Se definisci stop come "rileva quando un programma in esecuzione sta tentando di fare qualcosa di male, e poi fermalo", il teorema di Rice non si applica. Il tuo antivirus non ha bisogno di decidere se il programma potrebbe fare qualcosa di dannoso, solo se sta facendo qualcosa di dannoso ora.

AFAIK, la seconda versione non è stata dimostrata impossibile matematicamente impossibile. E in effetti, per qualsiasi definizione sufficientemente specifica di "dannoso", è molto fattibile - si tratta essenzialmente di sandbox.

Sembra probabile, tuttavia, che non esista una buona definizione di "malevolo", che coprirebbe tutte le forme di malizia che un virus potrebbe tentare. Che dire di un virus che estrae bitcoin? O che serve film sui pirati? O che spammano bacheche per tuo conto? Tutti questi sono indistinguibili dal codice gestito da utenti che vogliono veramente fare esattamente queste cose. Come tale, sospetto (anche se non conosco alcun tentativo di dimostrare) che la creazione di antivirus è completa AI.

16
James_pic

Sì, fu matematicamente provato dalla Chiesa di Alonzo nel 1935–1936 e in modo indipendente poco dopo da Alan Turing nel 1936.

https://en.wikipedia.org/wiki/Entscheidungsproblem

8

No, non puoi, perché la differenza tra malware e un programma utile è completamente soggettiva. Qualsiasi comportamento "malvagio" può essere inteso come comportamento. Ad esempio, ho i seguenti programmi in esecuzione sul mio computer in questo momento:

  • Un programma che crittografa tutti i miei file. È un cryptolocker ransomware o uno strumento di crittografia del disco completo?
  • Un programma che consente l'accesso remoto per controllare il mio computer. È un trojan o è Team Viewer?
  • Un programma che crea connessioni di rete a tutti i tipi di computer su Internet e scambia dati oscuri con loro. È una botnet o una piattaforma informatica distribuita?
  • Un programma che invia tutti i miei file personali a un server remoto. È uno spyware o è Cloud Backup?
  • Un programma che scarica i file eseguibili da Internet e li esegue. È un dropper di malware o è Steam?

Non puoi dire la differenza, perché da una prospettiva puramente tecnica fanno esattamente le stesse cose. L'unica differenza è nell'intenzione. Un programma inganna l'utente su ciò che fa e agisce contro gli interessi degli utenti, l'altro fa esattamente ciò che l'utente vuole che faccia. Ma ciò che l'utente vuole veramente dal proprio software è qualcosa che una macchina non può decidere ... almeno non nella fase attuale della tecnologia AI. Ecco perché tutti gli scanner di virus sono basati principalmente sulle firme.

8
Philipp

Per dimostrare matematicamente che è sempre possibile scrivere un virus in grado di bypassare tutti i programmi antivirus esistenti, dovresti prima definire matematicamente cos'è un virus e buona fortuna.

Forse un "programma che esegue azioni indesiderate"? Bene, è semplicemente impossibile, immagina un programma che apre una connessione al tuo PC e abilita il controllo remoto. L'antivirus può vedere che il programma fa questo, ma come può sapere se è desiderato o no?

Potrebbe essere un programma di controllo remoto legittimo come TeamViewer o potrebbe essere un mascarading di virus come un semplice programma di visualizzazione di immagini, in ogni caso, il tuo antivirus vedrà un programma in grado di leggere e visualizzare immagini dal tuo PC e aprire connessioni remote, e non avrà modo di sapere se è un comportamento "desiderato" o meno, dal momento che non può sapere perché si sta installando quel programma.

5
kajacx

Come sottolineato da @walen, in realtà è possibile rilevare tutti i virus se sono consentiti falsi positivi: basta riportare tutto come un virus.

Supponiamo che sia anche possibile rilevare tutti i virus se non sono ammessi falsi positivi. Avremo una funzione IsVirus che può essere eseguita su qualsiasi programma e restituire se quel programma è o meno un virus. Ora, considera questo programma che chiameremo P:

if IsVirus(P):
    exit
else:
    DoVirusThings

Qual è il valore di IsVirus(P)? Se è true, allora P esce semplicemente senza fare nulla e quindi abbiamo un falso positivo. Ma se è false, allora P fa cose da virus e abbiamo un virus non rilevato.

Ciò dimostra che non è possibile rilevare tutti i virus se non sono ammessi falsi positivi.

4
Matthew

La domanda originale era "È stato matematicamente dimostrato che l'antivirus non è in grado di rilevare tutti i virus?"

È probabilmente esatto dire che non possiamo mai provare che abbiamo un codice scritto che rileverà tutti i virus.

Un computer per uso generico collegato a Internet con la possibilità di scaricare ed eseguire il codice è probabilmente equivalente a una macchina di Turing universale. Questa equivalenza include le dimensioni infinite del nastro di Turing: se la larghezza di banda dell'interfaccia di rete della macchina è inferiore al tasso di crescita totale dei dati accessibili da Internet, la macchina non potrà mai raggiungere la "fine del nastro". (Ne ho parlato un po 'alla conclusione di questo documento molto tempo fa. Sebbene sia dimostrabile in senso pratico, elaborare una prova matematica richiederebbe probabilmente aggiungere alcuni vincoli.)

Se quanto sopra è vero, e se "fermare" significa "produrre un rapporto che elenchi tutti i virus sul sistema, non più o meno", allora non possiamo provare in anticipo che il programma si fermerà con una risposta corretta; dobbiamo eseguirlo per scoprirlo.

Se entrambi i paragrafi precedenti sono veri, non possiamo mai verificare la correttezza del rapporto risultante, perché non possiamo mai compilare un elenco completo di tutti i possibili virus con cui confrontarlo: quei virus sono tutti là fuori da qualche parte sul nastro, è infinito di dimensioni e non possiamo mai leggere tutto.

Se tutti e tre i paragrafi sono veri, non potremo mai provare di aver scritto un rilevatore di virus corretto al 100%.

2
stevegt

È stato matematicamente dimostrato che l'antivirus non è in grado di rilevare tutti i virus?

Quale analisi faceva riferimento a Bruce Schneier quando scrisse:

I virus non hanno una "cura". È stato matematicamente dimostrato che è sempre possibile scrivere un virus che nessun programma antivirus esistente non può fermare. "[0]

[0] Segreti e bugie. Bruce Schneier. Pagina 154

Questa risposta non affronta direttamente a quale analisi si riferisse Bruce Schneier. Una persona interessata al significato di una fonte primaria quando ha fatto una dichiarazione dovrebbe fare lo sforzo di contattare la fonte primaria stessa per porre le proprie domande specifiche , per evitare speculazioni, congetture o confusione.

Teorema di incompletezza di Kurt Gödel pubblicato nel 1931 in Über formal unentscheidbare Sätze der "Principia Mathematica" und verwandter Systeme (chiamato in inglese " Su proposizioni formalmente indecidibili di "Principia Mathematica" e sistemi correlati ") se attentamente considerato è molto istruttivo rilevante per l'analisi di any sistema formale, dai virus informatici alla politica

1. Se un sistema (logico o assiomatico formale) è coerente, non può essere completo.
2. La coerenza degli assiomi non può essere dimostrata all'interno del proprio sistema.

Questi teoremi hanno concluso mezzo secolo di tentativi, a partire dal lavoro di Frege e culminando nel Principia Mathematica e nel formalismo di Hilbert, per trovare una serie di assiomi sufficienti per tutta la matematica.

Con il senno di poi, l'idea di base alla base del teorema di incompletezza è piuttosto semplice. Gödel essenzialmente ha costruito una formula che afferma che non è dimostrabile in un dato sistema formale. Se fosse provabile, sarebbe falso. Quindi ci sarà sempre almeno un'affermazione vera ma non dimostrabile. Cioè, per qualsiasi insieme di assiomi computabilmente enumerabile per l'aritmetica (ovvero un insieme che può in linea di principio essere stampato da un computer idealizzato con risorse illimitate), esiste una formula vera per l'aritmetica, ma che non è dimostrabile in quel sistema. Per rendere questo preciso, tuttavia, Gödel aveva bisogno di produrre un metodo per codificare (come numeri naturali) affermazioni, prove e il concetto di provabilità; lo ha fatto usando un processo noto come numerazione di Gödel.

1
guest271314

Bene, la definizione di virus è piuttosto vaga. Sì, è un'entità malevola, ma il malware è altrettanto vago. A seconda del sistema e delle relative politiche, le possibilità per un'entità dannosa cambieranno. Definire un'entità in continua evoluzione è qualcosa che è emerso in vari campi, teoria dei numeri, macchine a stati, ecc. Ed è stato dimostrato in diversi modi che non è possibile, almeno sulla base di ciò che sappiamo.

Un modo sarebbe, invece di definire ciò che è dannoso, che possiamo definire ciò che è permesso, un sistema molto rigoroso e indipendente, che consente di eseguire solo determinate sequenze di operazioni. In questo modo può essere tenuto al sicuro.

Questo problema IMO è difficile quanto la definizione casuale.

1
Adithya Sama

Un virus è solo un codice - è gentile se dice "Il mio programma di rasaerba AI può dire la differenza tra piante infestanti e piante" - in tal caso, attira i rischi?

Se scarichi un programma che invia e-mail a tutti nell'elenco dei contatti, è un virus o sei uno spammer? Dipende dal motivo per cui hai scaricato il programma, non da specifici byte nel programma.

Quindi non devi nemmeno andare alla prova matematica - puoi semplicemente ragionare sul fatto che non può essere fatto.

D'altra parte, si potrebbe dire che è facile identificare i virus se si definisce il virus in base al comportamento. I programmi vengono aggiornati nell'ambito di un processo di aggiornamento, se qualcosa tenta di modificare il codice sul computer al di fuori di questo processo, è possibile definirlo un virus. Con queste definizioni è possibile rilevare facilmente le modifiche che si verificano al di fuori di specifiche procedure di installazione. Potrebbe essere necessario un hardware in grado di separare il codice dai dati e bloccare lo spazio del codice quando non si tiene premuto un pulsante, ma è possibile (se fastidioso).

Questo presuppone anche che il codice che hai installato deliberatamente durante il processo di aggiornamento non sia un virus stesso, ma poiché stiamo definendo un virus in base al comportamento per questo esempio, quindi per definizione suppongo che non lo sia.

1
Bill K

Non è una prova matematica, ma AFAIK ci sono due modi per rilevare malware:

firme

Poiché è possibile sviluppare un nuovo malware, incluso offuscare o modificare quelli esistenti, la firma del nuovo malware non sarà nel database antivirus, quindi non verrà rilevata

euristica

Questo metodo utilizza l'analisi dinamica e/o statica automatica per comprendere il comportamento del software e in base a ciò che fa l'antivirus decide se è dannoso o meno.

E qui arriva la parte difficile, non tutto ciò che oggi è considerato innocuo potrebbe essere in futuro.

Ad esempio, 20 anni fa un software che utilizzava le librerie di crittografia potrebbe non essere stato visto come qualcosa di dannoso, ora sappiamo che potrebbe essere una sorta di ransomware che crittografa i tuoi dati. Allo stesso tempo, puoi (e dovresti) utilizzare un gestore di password che utilizza anche librerie di crittografia per archiviare in modo sicuro i tuoi dati. Quindi, come possiamo decidere se si tratta di malware o non solo in base al fatto che crittografa i dati? Allo stesso modo una TCP può essere usata per perdere informazioni o per navigare su siti web

L'unica differenza è semantica, che è difficile da analizzare in modo automatico poiché le tecnologie sono in costante evoluzione e il malware si adatta a tale evoluzione. Dopo tutto il malware non è diverso da qualsiasi altro software, tranne per le cattive intenzioni del proprietario

0
Mr. E