Question:
At-il été prouvé mathématiquement que l'antivirus ne peut pas détecter tous les virus?
Cate
2019-01-23 07:51:10 UTC
view on stackexchange narkive permalink

Quelle analyse Bruce Schneier faisait-il référence lorsqu'il a écrit:

Les virus n'ont pas de «remède». Il a été prouvé mathématiquement qu'il est toujours possible d'écrire un virus qu'aucun programme antivirus existant ne peut arrêter.

Extrait du livre Secrets & Lies de Bruce Schneier , page 154.

Je pense qu'il est déjà impossible de faire une définition complète et formelle de ce qu'est un virus informatique en premier lieu, c'est-à-dire de décrire ce qu'est exactement la «malveillance».Mais une telle définition est nécessaire pour même argumenter sur le problème décidable ou indécidable.Mais même si vous trouvez une sorte de définition utile mais pas parfaite, elle sera probablement indécidable à cause du [problème d'arrêt] (https://en.wikipedia.org/wiki/Halting_problem).
Le message est verrouillé car il génère une tonne de spéculations et d'opinions.La question se pose sur la source d'un article référencé dans un autre article.
Les commentaires ne sont pas destinés à une discussion approfondie;cette conversation a été [déplacée vers le chat] (https://chat.stackexchange.com/rooms/88818/discussion-on-question-by-cate-has-it-been-mathematically-proven-that-antivirus).
Cette question me rappelle un dialogue de Douglas R. Hoffstadter expliquant les théorèmes d'incomplétude de Gödel: https://genius.com/Douglas-hofstadter-contracrostipunctus-annotated
Un exemple de ne pas pouvoir détecter un «virus» ou ce qu'une fonction en JavaScript renvoie ** à moins que la fonction ne soit appelée ** [Comment vérifier si une fonction JavaScript renvoie une promesse?] (Https://stackoverflow.com/ q / 43416214 /);[Peut-on créer une expression régulière qui détermine le type de retour d'une fonction?] (Https://stackoverflow.com/q/43417236/);https://astexplorer.net/#/gist/7b371f354537e9d3415bc8ed9fad9c94/9cb99f18e70987ff09d1195b7c3189be87d67105
Le problème de l'arrêt dit oui?Si vous ne pouvez pas dire si un programme s'arrête, il semblerait que vous ne puissiez pas non plus dire si un programme fait quelque chose de malveillant / est un virus.
Votre titre pose une question différente de celle revendiquée dans le devis.Le devis affirme que tous les virus ne peuvent pas être arrêtés.Ceci est évidemment différent de demander s'ils peuvent tous être détectés comme dans votre titre.(C'est vrai car il est possible d'arrêter un virus sans le détecter)
Considérez-vous l'application de surveillance comme un antivirus?Il est toujours possible de créer un moniteur qui détecte les tentatives d'écriture, de suppression et même de lecture du répertoire attribué (disons / usr / local / virus) ou de développer ce répertoire au-delà de certaines limites.Dans la plupart des cas pratiques, cela éliminerait de vastes classes de virus.
Contre-exemple facile: un programme qui affiche des vidéos de chats et s'envoie à tous vos amis.Certains peuvent le voir comme un virus, d'autres le verront comme une excellente application avec des fonctionnalités intéressantes.Donc, cette seule instance est déjà indécidable.
Dix-neuf réponses:
Joseph Sible-Reinstate Monica
2019-01-23 09:10:11 UTC
view on stackexchange narkive permalink

Selon une interprétation possible de cela, c'est le résultat du théorème de Rice. Un programme est malveillant s'il effectue une action malveillante, ce qui en fait une propriété sémantique. Certains programmes sont malveillants et d'autres non, ce qui en fait une propriété non triviale. Ainsi, d'après le théorème de Rice, il est indécidable dans le cas général si un programme est malveillant.

Les commentaires ne sont pas destinés à une discussion approfondie;cette conversation a été [déplacée vers le chat] (https://chat.stackexchange.com/rooms/88726/discussion-on-answer-by-joseph-sible-has-it-been-mathematically-proven-that-anti).
Sans oublier, «malveillant» est un terme presque entièrement subjectif.J'ai vu des programmes de désassemblage être signalés comme des logiciels malveillants parce que l'auteur de l'AV considérait apparemment l'ingénierie inverse comme une chose "malveillante" (même si je ne peux pas penser à une situation où quelqu'un qui ne voulait pas que le désassembleur se termine sur son ordinateuravec elle là-bas).
@DoktorJ: Le fait est que même si vous trouvez une définition non syntaxique rigide pour «malveillant» _ (indépendamment du fait que cette définition manque certains virus, ou inclut certains non-virus) _, il est toujours impossible de signaler tout / seulement malveillantprogrammes.
Le PO a posé des questions sur les «virus» et non sur les logiciels malveillants.les virus ne sont pas nécessairement malveillants.La seule propriété déterminante est qu'il s'auto-réplique.(Maintenant, c'est probablement le malware OP _meant_ (virus ou non)).
@Stéphane Chazelas L'auto-réplication est également une propriété sémantique non triviale, donc indécidable.
@BlueRaja-DannyPflughoeft: il est important que cela ne soit vrai que dans la mesure où il est impossible de le dire à l'avance, avec une garantie de résiliation.Étant donné une définition rigoureuse des actions que le programme n'est pas autorisé à exécuter, il est parfaitement possible de le faire pendant que le programme est en cours d'exécution - c'est le principe du sandboxing.La plupart des utilisateurs se contenteraient d'un programme qui arrête les logiciels malveillants avant qu'il ne fasse quelque chose de mal, qu'il ait également la possibilité de montrer d'abord des singes dansants.Le problème est que ces «définitions rigoureuses» s'avéreront inévitablement incomplètes.
Je pense que le théorème de Rice ne s'applique que si vous devez décider * à l'avance * si un programme est malveillant, et si vous n'autorisez pas les faux positifs.Si le scanner de virus peut par ex.intercepter les appels d'API, modifier le programme (par exemple pour insérer des vérifications d'exécution) et rejeter occasionnellement un programme «sûr», il devrait être possible de prouver la sécurité.C'est fondamentalement comment, par ex.une machine virtuelle Java peut offrir des garanties de sécurité, n'est-ce pas?
@JeroenMostert: Non, cela n'a rien à voir avec l'analyse statique vs runtime.La différence est de savoir si la définition est sémantique ou syntaxique."Une liste des actions que le programme est autorisé à effectuer" est une définition syntaxique.C'est pourquoi écrire un bac à sable est tellement plus facile que d'écrire un antivirus.
@JeroenMostert: Sandboxing ne résout ** pas ** le problème.Comment savoir si la dernière version de votre navigateur que vous avez installée contient un malware caché qui capture votre saisie au clavier sur les sites Web des banques?Allez-vous utiliser un bac à sable différent pour chaque site Web sensible?Comment savez-vous que votre dernier logiciel de sandboxing n'est pas lui-même un malware?Comment savez-vous que votre système d'exploitation ...
@Joseph: Je suis d'accord avec votre réponse, mais un problème possible est que les vrais ordinateurs ne sont pas Turing-complets, et il est donc théoriquement possible (bien que pratiquement impossible) de déterminer si un programme quelconque ferait entrer votre ordinateur spécifique dans un état indésirable.Naturellement, vous ne pourrez pas le faire dans votre ordinateur lui-même, mais en théorie, vous pouvez utiliser un autre ordinateur disposant de plus de mémoire pour effectuer l'analyse.Bien entendu, le temps nécessaire est proportionnel au nombre d'états possibles dans lesquels votre ordinateur peut se trouver ...
@user21820: Je n'ai jamais dit que le sandboxing était ou pourrait être une solution parfaite (il devrait être assez évident que * no * solution peut être une protection absolue contre les logiciels malveillants, d'un simple point de vue pratique, et encore moins de la théorie).La question est de savoir si le théorème de Rice est la bonne chose à invoquer ici comme preuve mathématique qu'un tel malware ne peut pas être détecté.(Ou, en remontant un niveau de plus, si Schneider faisait référence à cela du tout, ce qui ne semble pas être le cas - bien que non noté, [cette réponse] (https://security.stackexchange.com/a/202003/ 147318) semble être la bonne.)
@user21820 qui n'est même pas complet, car deux programmes pourraient être différents uniquement là où vos données sont réellement envoyées.Une application bancaire et un renifleur de mot de passe liront tous les deux votre mot de passe et l'enverront à un serveur - votre machine fera exactement la même chose, mais le destinataire est différent - donc une analyse locale ne peut jamais décider si le destinataire est quelqu'un que vous avez réellement l'intentionenvoyé vos données à, donc tout Internet avec toutes les machines accessibles ensemble devrait au minimum être votre machine à états pour vérifier tous les états - bonne chance ...
@Falco: Oui bien sûr.Il existe de nombreux détails de ce type, mais la zone de commentaire était trop peu profonde pour les contenir.
walen
2019-01-23 20:21:11 UTC
view on stackexchange narkive permalink

En fait, l'inverse peut être facilement prouvé : comme tous les virus informatiques sont du code exécutable d'une manière ou d'une autre, il suffit de écrire un programme antivirus qui signalera TOUT exécutable coder comme viral. Il s'ensuit logiquement qu'un tel programme détectera TOUS les virus possibles :

  • Tout le code est détecté par votre antivirus (C → D)
  • Tous les virus sont du code (V → C)
  • Tous les virus sont détectés par votre antivirus (V → D)

Bien sûr, un argument pourrait être fait à propos de ce logiciel antivirus qui en évite trop "faux positifs". Mais quels sont les critères pour décider si un positif est faux ou vrai? Ah! Il s'avère que la distinction entre un code bénin et un code malveillant, entre une honnête suite de "contrôle PC à distance" et un cheval de Troie comme Netbus est complètement arbitraire, et donc toute la question est inutile.

Mignonne.Je veux dire, totalement hors de propos, mais aussi mignon et intelligent.
On peut un peu plus utilement exiger que les programmes soient composés de certaines actions qui ne peuvent pas être composées de manière à produire un comportement de "virus", puis rejeter tous les programmes qui ne sont pas composés uniquement de telles actions.Cette approche est pratique à de nombreuses fins;le plus gros problème est que la gamme des tâches qui peuvent être effectuées en utilisant uniquement des actions qui ne peuvent pas produire un comportement de virus est quelque peu en deçà de la gamme de tâches que les gens veulent que les ordinateurs effectuent.
@supercat, le problème avec votre version est que vous devez proposer une définition du «comportement du virus» qui peut être appliquée par programme.Par exemple, un mineur Javascript Bitcoin peut ressembler à un virus lors de la visite du site Web du New York Times, mais comportement souhaité lors de la visite du logiciel Joe's Discount Pirate.Le cryptage du contenu de votre disque dur peut être un bon comportement lorsque c'est votre logiciel FDE qui le fait, et un virus lorsque cela est effectué par un ransomware.
Ce programme antivirus se détecte * lui-même * comme un virus et s'arrête, le rendant incapable de détecter quoi que ce soit d'autre.
@Mark: Je définirais un virus comme un programme qui s'installe pour s'exécuter automatiquement sans le consentement du propriétaire ou de l'opérateur de l'ordinateur.Si l'ensemble des actions autorisées n'inclut aucun moyen d'installer le programme à exécuter automatiquement, il ne sera pas possible de créer un virus à partir des actions de cet ensemble.
@supercat De nombreux virus sont installés avec le consentement de l'opérateur, mais font des choses auxquelles l'opérateur n'a pas consenti.Cependant, si vous empêchez l'exécution automatique, un redémarrage le tuerait, mais pas les effets secondaires.
@Poik: Tous les programmes malveillants qui se propagent ne sont pas des virus.Pour qu'un morceau de code soit un virus, il doit entre autres pouvoir, sans le consentement d'un opérateur, se faire exécuter à un moment ultérieur où aucune partie de celui-ci n'est en cours d'exécution.Empêcher les applications de modifier d'autres programmes ou la séquence de démarrage empêchera à 100% les virus, bien que d'autres formes de logiciels malveillants tels que les vers soient toujours possibles.
sauf, comment détecter si quelque chose est du code exécutable?par exemple, le virus JPG qui exploitait un bogue dans le rendu JPG de Microsoft (provoquant l'exécution de code lorsque Microsoft Internet Explorer visitait une page Web).Donc, le seul moyen serait d'étendre votre pseudo-code pour dire que tous les bits le sont, car tous les bits pourraient être du code exécutable.Si nous voulons devenir aussi ridicules, je pourrais dire que "bytes" (signalé par "dir") est en fait une traduction de "virus found", donc "dir" est en fait un logiciel anti-virus qui fait cela.Absolument ridicule.(Pour ne pas dire que je n'apprécie pas le ridicule. Bravo.)
L'antivirus qui détecte tout le code exécutable comme malveillant détecte également le système d'exploitation sur lequel il s'exécute comme malveillant.Si ce programme audiovisuel faisait réellement quelque chose à ce sujet, il planterait le système d'exploitation assez rapidement, à chaque fois.Ne ferait pas un excellent programme audiovisuel, mais créerait un virus méchant
Sonne comme un argument pour les programmes recherchés * sur liste blanche * uniquement, comme dans un référentiel de seuls logiciels testés à installer (peut-être même FOSS, pas contrairement à la plupart des référentiels Linux), pour au moins éviter d'installer des éléments malveillants exprès
Lorsque vous posez une question sur quelque chose de pratique, même à distance, vous pouvez supposer que la solution triviale est exclue par défaut.
Je conteste la première prémisse: * Tout le code est détecté par votre antivirus. * Comme étant la partie de ceci qui est pratiquement impossible.
@Xen2050 "Sonne comme un argument pour les programmes recherchés sur liste blanche uniquement ..." Oui, c'est le cas.Malheureusement, il existe des millions d'applications pour les smartphones par exemple.Je ne veux pas être celui qui doit tous les tester.
Peut-on considérer un script comme un "code"?Si c'est le cas, je pense que la première prémisse devient un peu moins triviale
Que signifie Virical?Je ne trouve pas de définition pour cela.
@TemporalWolf Non, c'est anormalement trivial: la première instruction du code machine est stop.Si, à un moment quelconque, vous constatez que votre machine est arrêtée, cela signifie qu'elle a détecté du code.
-1 parce que cette réponse n'est d'aucune façon utile.
@TOOGAM: exactement.Si nous parlons de x86, la plupart des séquences d'octets sont décodées comme des instructions x86 valides.Habituellement, le texte ASCII donne une séquence d'instructions qui n'a aucun sens, ou inclut des instructions privilégiées comme «6c ins» et «6e outs», mais il n'est pas rare qu'une séquence ne contienne aucune instruction illégale.(Surtout en mode 32 bits.) J'ai mis le texte de cette réponse dans `.ascii" ... "` dans foo.s (en remplaçant les nouvelles lignes par `\ n` et en échappant les guillemets), et l'ai assemblé avec` gcc-m32 -c foo.s`.Beaucoup de brèves instructions de branchement conditionnel, mais pas d'instructions illégales!
Oh, je peux le mettre sur Godbolt d'une manière qui montrera le démontage * avec * hexdump: https://godbolt.org/z/IIXBUc (contrairement à cette première tentative lang = asm qui ne le fait pas: https: // godbolt.org / z / -2ATIj).Certaines des instructions plus amusantes incluent `imul esi, DWORD PTR [edx + esi * 2 + 0x61], 0x202c7972`.
@Fax qui suppose que vous êtes en mesure de scanner le programme pour commencer.Peut-être est-il exécuté via un périphérique connecté, fonctionne comme un chargeur de démarrage, déchiffré à la demande ou mime l'interaction de l'utilisateur en se faisant passer pour un clavier.Tous les quatre nécessitent des approches différentes et non triviales de l'application et sont toutes des choses qui sont actuellement connues pour être exploitées dans la nature.Votre système nécessite également la restriction absolue et non triviale selon laquelle aucun fichier non exécutable ne contient la représentation binaire d'une instruction d'arrêt de la machine ... voici plusieurs caractères unicode qui contiennent 0xF4, le code x86: ôǴ˴ϴӴ ״
@TemporalWolf Non, cela ne suppose pas.Du point de vue d'un programme, «tout code est présent» est une tautologie logique.Personne n'a dit que votre ordinateur ne pouvait pas être un excellent presse-papiers.
@JackAidley Il n'y a rien d '«intelligent» là-dedans.C'est comme conclure que si nous nous tuons, nous n'aurons plus de problèmes dans la vie.
Cette réponse fonctionnerait parfaitement dans une configuration où l'AV est appelé pour juger un peu de code et doit donner une réponse.Malheureusement, cela laisse une lacune dans votre preuve car vous auriez besoin de prouver que l'AV sera invité à juger chaque bit de code.(Et le plus petit écart dont il a besoin pour pouvoir répondre).
J'ai un remède pour chaque maladie connue de l'homme!
J'ai l'impression que c'est une utilisation incorrecte de "détecter".Cela revient à dire que si un jury déclare un homme coupable pour les mauvaises raisons, même s'il était vraiment coupable, ils * savaient * qu'il était coupable.* Savoir * signifie quelque chose de plus qu'être correct, et «détecter» ici est utilisé de manière très similaire;cela signifie plus que simplement décider.Cela devrait signifier qu'une analyse a été effectuée et qu'une certaine justification de la décision existe.
@Steve On dirait une tentative incorrecte de transformer «virus» en adjectif.Si tel est le cas, il devrait être «viral».
@jpmc26 Plus comme une erreur non native.Je sais que c'est "viral" en anglais, mais en espagnol c'est "vírico, vírica" et je les ai mélangés par inadvertance.
Harry Johnston
2019-01-23 12:20:05 UTC
view on stackexchange narkive permalink

Selon Wikipédia:

En 1987, Fred Cohen a publié une démonstration qu'il n'y a pas d'algorithme capable de détecter parfaitement tous les virus possibles.

Il fait également référence à cet article. C'est peut-être l'analyse à laquelle M. Schneier faisait référence.

Schneier déclare ici que c'est le résultat auquel il faisait référence lorsqu'il a fait une déclaration très similaire quelque temps plus tard dans un autre contexte: https://www.schneier.com/blog/archives/2009/07/making_an_opera.html
@Stephan: Pour chaque binaire possible, il existe une plateforme hypothétique pour laquelle il est virulent et une plateforme hypothétique pour laquelle il n'est pas virulent.Ce théorème est plus fort que le théorème de Rice car il s'applique également aux hypercalculateurs.
il a donc été prouvé qu'en 1987, l'antivirus parfait n'existait pas?soigné.mais a-t-il aussi prouvé que l'antivirus parfait ne pouvait être créé, ou simplement qu'il n'existait pas à partir de 1987?
@user1067003, Je ne suis pas un informaticien, mais je suis sûr que l'expression "il n'y a pas d'algorithme" signifie qu'il n'y a pas d'algorithme possible, pas seulement qu'il n'y a pas d'algorithme * connu *.Sinon, ce ne serait pas un résultat très intéressant.(La preuve telle qu'elle est écrite ne s'applique probablement qu'aux ordinateurs classiques, cependant, elle devra peut-être être refaite pour couvrir les ordinateurs quantiques ou toute autre architecture plus abstruse.)
Cette réponse s'appuie fortement sur un lien externe pour répondre à la question.Pouvez-vous résumer les arguments de cet article?
Les ordinateurs Quantum @HarryJohnston: sont équivalents aux machines de Turing en termes de calculabilité, donc non, il n'a pas besoin d'être refait.En fait, presque tous les informaticiens pensent que chaque ordinateur physiquement réalisable est, au mieux, [équivalent à une machine de Turing] (https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis)
@BlueRaja-DannyPflughoeft, la thèse de l'église affirme que l'esprit humain équivaut à une machine à turing.Cela n'a aucune base sur la possibilité ou non de construire un hypercalculateur.Tout ce que cela signifie, c'est que nous ne pourrions pas faire les calculs à la main.Nous devrons nous fier à l'exactitude de la machine.Comment cet article confirme-t-il cette affirmation?
Michael Kay
2019-01-24 00:24:46 UTC
view on stackexchange narkive permalink

L'instruction ne peut être prouvée mathématiquement que si elle est reformulée sous forme de proposition mathématique.

À tout le moins, cela nécessite une définition mathématiquement solide de ce qu'est un «virus»: ce qui est difficile; et vous pourriez vous retrouver avec une abstraction qui n'est pas utile dans la pratique, car elle inclut certains comportements que les gens considèrent comme totalement bénins et utiles, et / ou exclut certains comportements que les gens considèrent comme antisociaux.

Les plus difficiles la chose ici est qu'un virus est un programme qui modifie son environnement d'une manière ou d'une autre, et toute tentative de définir rigoureusement l'environnement va être trop limitative pour une utilisation pratique.

Donc je dirais non: la proposition ne peut pas être prouvé mathématiquement, et c'est parce qu'il ne peut pas être formulé mathématiquement.

Un contre-exemple: je spécialiserai la question originale (perdant sa généralité), en définissant * un virus * comme n'importe quel `script bash` qui invoque` rm -rf / * `lorsqu'il est exécuté sans arguments;et je définirai * un antivirus * comme une version de l'interpréteur bash qui refuse l'exécution de la commande `rm -rf / *`.J'espère que vous conviendrez que nous pouvons aller jusqu'au bout en définissant rigoureusement ce que signifie mathématiquement un "interpréteur bash", "exécuter", etc.Est-ce que je viens de formuler une version plus faible de la question initiale?Cela réfute-t-il votre affirmation selon laquelle * il ne peut pas être formulé mathématiquement *?Oui et oui.
@ulidtko Non. Vous ne pouvez pas définir arbitrairement un virus comme ce que vous voulez.Sinon, je pourrais définir un virus comme "un logiciel qui a 'anti-virus' dans son nom", ce qui n'aiderait en rien la discussion, car c'est une discussion de philosophie, pas de sécurité ou de mathématiques.En fait, votre définition du virus est comme si vous disiez "Je définis l'ensemble des nombres pairs comme étant {2}".Allez-y et créez un tel système si vous le souhaitez, mais vous n'avez rien réfuté en le faisant.Comme Michael l'a suggéré, le "virus" ne peut être défini mathématiquement d'aucune manière utile à cette conversation.
Re: «À tout le moins, cela nécessite une définition mathématiquement solide de ce qu'est un« virus »»: Pas nécessairement.S'il y a des caractéristiques qui s'appliqueraient à * n'importe quelle * définition de «virus», alors vous pourrez peut-être formaliser mathématiquement certaines de ces caractéristiques sans avoir besoin de produire une définition complète spécifique.Cette caractérisation partielle pourrait suffire à vous permettre d'appliquer [le théorème de Rice] (https://en.wikipedia.org/wiki/Rice%27s_theorem).
@ulidtko Sur la même base, je pourrais définir un virus comme n'importe quel programme qui envoie un e-mail.Je suis sûr que je pourrais raisonner sur cette classe de programmes, mais cela ne me dirait rien sur la classe de programmes que les gens ordinaires classent comme virus dans le monde réel.
Le théorème d'@ruakh Rice ne s'applique que si vous limitez votre programme antivirus à fonctionner par analyse statique du code (source ou objet).La question est de "détecter les virus", sans se limiter à les détecter par analyse statique.Que se passe-t-il si vous les détectez en observant leur comportement d'auto-réplication?
@MichaelKay: Je suis au courant;J'ai seulement mentionné le théorème de Rice comme exemple de la raison pour laquelle votre déclaration était incorrecte.Désolé si ce n'était pas clair.
Sur un système 64 bits avec un espace mémoire complet de 64 bits et sans mémoire extensible, la taille de la mémoire sera de 2 $ ^ {64} $ octets.Si nous considérons ensuite toutes les permutations possibles de cet espace mémoire, alors il y a $ 8 ^ {2 ^ {64}} $ programmes dans cet espace mémoire.Moins si l'on considère que le binaire compilé coexistera avec la mémoire.Le nombre de programmes étant limité, ils peuvent être divisés en un ensemble de programmes malveillants et de programmes non malveillants.Ce serait la définition des programmes 64 bits malveillants.Vous prétendez que nous n'avons pas de définition qui s'étendrait à 128 bits, etc.
Votre affirmation pourrait également être qu'une combinaison particulière de bits pourrait être malveillante pour un utilisateur et non malveillante pour un autre utilisateur.Dans cette situation, le problème peut être résolu en permettant à un utilisateur de mettre sur liste blanche quelque chose qui a été signalé comme malveillant.Ce n'est pas l'idéal, mais tout cela signifie vraiment que les gens auront différentes définitions de malveillant ou dans un sens plus réaliste - que certains utilisateurs * veulent * exécuter du code malveillant sur leur propre machine.
Nat
2019-01-25 11:00:19 UTC
view on stackexchange narkive permalink

tl; dr - La réponse dépend exactement des exigences que vous imposez à la question.

  1. Si vous voulez détecter tous les virus sans autre contrainte, alors marquez simplement n'importe quoi et tout comme un virus, et vous avez terminé.

  2. Si vous voulez identifier correctement tous les programmes comme un virus ou non, alors c'est impossible dans le cas non lié puisque le problème de classification se réduit au problème d'arrêt.

  3. Si vous voulez identifier correctement tous les programmes comme virus ou non, et vous considérez une machine finie, alors c'est théoriquement possible mais pas généralement faisable en pratique.

  4. Si vous admettez que l'ordinateur peut produire des erreurs aléatoires, alors n'importe quel programme peut être un virus.

Cas 1: Détection complète des virus

De toute évidence, signaler tous les programmes comme virus les attrape tous. ( Pok'e'mon! )

En commençant par ce cas pour faire remarquer qu'il n'est pas difficile de détecter tous les virus; plutôt, le problème théorique spécifique est de classer correctement les programmes iff comme des virus.

Cas 2: Impossible de classer correctement dans un scénario général et illimité

Considérez le programme: 

  doHaltingProblem (); // Pas une opération de virus itselfinstallEveryVirusEver (); // Certainement une opération de virus, mais cela se produira-t-il?

Dans ce cas, le programme n'est un virus que si le problème d'arrêt s'arrête, permettant installEveryVirusEver () pour se produire. Ainsi, la détection de virus se réduit au problème d’arrêt dans le cas général, non lié.

Cas 3: Possible par recherche par force brute dans des scénarios limités

Si les programmes doivent être classés comme virus -ou non doivent fonctionner sur une machine finie, alors vous pouvez simplement simuler la machine fonctionnant à partir de tous les états de démarrage possibles. Les machines finies finiront par revenir à un état antérieur, donc c'est nécessairement une analyse finie (si longue).

Cas 4: les machines qui peuvent faire des erreurs peuvent faire émerger spontanément des virus

En supposant qu’une machine peut exécuter un programme qui serait considéré comme un virus, et qu’il n’y a pas de chance nulle de changement de mutation aléatoire dans cet état, puis il devrait finalement arriver à un état de virus.

Ce qui est un peu ennuyeux, mais juste pour être complet.

Discussion sur le quote dans la question

Les virus n'ont pas de «remède». Il a été prouvé mathématiquement qu'il est toujours possible d'écrire un virus qu'aucun programme antivirus existant ne peut arrêter.

- " Secrets & Lies " , Bruce Schneier, page 154

Comme indiqué dans le cas (1) ci-dessus, il est possible de signaler tous les virus en signalant simplement tout comme un virus; c'est facile. Ce qui est impossible, dans un cas non lié, est de déterminer si chaque programme possible est un virus ou non.

De plus, il est difficile d'établir si des programmes particuliers sont des virus dans des cas liés. Par exemple, considérons le programme: 

  var toExecute = decryptByBruteForce ([ciphertext]); // Décrypter la partie suivante du programme par brute-forcerun (toExecute); // Exécutez la partie maintenant décryptée du programme

Comme indiqué dans le cas (3), ce programme peut être classé comme un virus ou pas lorsqu'il est exécuté sur une machine finie, mais comme cela nécessiterait de forcer brutalement un message chiffré, ce n'est probablement pas faisable dans des scénarios pratiques.

Ainsi, dans les applications du monde réel, cela se réduit à un problème d ' heuristique: les programmes antivirus tentent de deviner ce qu'est un virus ou non. Ou si vous voulez une sécurité plus fiable, vous pouvez demander à un programme antivirus de signaler tout ce qu'il ne peut pas prouver sûr, évitant ainsi la nécessité de classer tous les programmes possibles.

Malheureusement, l'utilisation de l'heuristique donne aux attaquants bien informés des failles de sécurité à cibler. Sans lire la source de la citation, je soupçonne que ce problème est ce à quoi ils essayaient de se référer.

Le cas (4) n'est pas seulement ennuyeux, mais indique un scénario plus probable et un scénario problématique.Considérez un code qui contient des appels if (cannotHappen) installEveryVirusEver ();où cannotHappen ne peut pas se produire si la machine fonctionne correctement, mais est susceptible de se produire si la machine est overclockée.Comment classer correctement cela?
@HansOlsson Oui, il faudrait généraliser l'ontologie pour capturer les problèmes qui ne rentrent pas bien dans le modèle déterministe;nous devrions vraisemblablement considérer l'ensemble des résultats possibles, puis les classer en fonction de leur degré de sécurité, ou bien admettre simplement que les programmes en général peuvent agir de manière malveillante même s'ils ne sont pas conçus pour.J'espérais faire un clin d'œil à des problèmes comme [row hammer] (https://en.wikipedia.org/wiki/Row_hammer), où la présomption de fonctionnement sans erreur peut vraiment gâcher l'analyse.
"brute forçant un message chiffré" Pourquoi ne pas exécuter le programme dans un bac à sable et comprendre comment il déchiffre le message lui-même?IIRC c'est ainsi que certains antivirus fonctionnent déjà.
@micsthepick L'exécution d'un programme dans un bac à sable est une solution de meilleure mise à l'échelle qui est susceptible d'être généralement supérieure dans des cas non triviaux, vous avez donc raison de dire que cela aurait tendance à être préféré dans la pratique.Simplement, la question porte sur l'antivirus au sens de l'analyse préventive;le bac à sable est un sujet différent.
Il convient de noter que l'exemple de problème d'arrêt peut être contourné en signalant simplement tout programme qui a le potentiel d'installer un virus comme virus (c'est-à-dire que le code d'octet dédié à faire cela existe, donc probablement le logiciel peut le faire).
James_pic
2019-01-23 23:03:48 UTC
view on stackexchange narkive permalink

Cela dépend de votre définition de "stop".

Si vous définissez stop comme étant "détecter, à l'avance, ce code pourrait faire quelque chose de malveillant et empêcher son exécution", alors comme d'autres l'ont fait mentionné, cela est impossible, par le théorème de Rice.

Si vous définissez stop comme "détecter quand un programme en cours d'exécution tente de faire quelque chose de mal, puis l'arrêter", alors le théorème de Rice ne s'applique pas. Votre antivirus n'a pas besoin de décider si le programme pourrait faire quelque chose de malveillant, seulement s'il fait quelque chose de malveillant maintenant.

AFAIK, la deuxième version n'a pas été prouvée mathématiquement impossible. Et en effet, pour toute définition suffisamment précise de «malveillant», c'est très faisable - c'est essentiellement du sandboxing.

Il semble cependant probable qu'il n'y ait pas de bonne définition de «malveillant», qui couvrirait tout les formes de malveillance qu'un virus pourrait tenter. Qu'en est-il d'un virus qui mine le bitcoin? Ou qui sert des films de pirates? Ou qui envoie des messages indésirables en votre nom? Tous ces éléments sont indiscernables du code exécuté par des utilisateurs qui veulent vraiment faire exactement ces choses. En tant que tel, je soupçonne (bien que je ne sache aucune tentative de prouver) que la création d'un antivirus est une IA complète.

Le problème de la définition de malicieux n’est guère un obstacle.Différentes personnes auront des intérêts différents qui entrent dans l'élaboration d'une définition qui leur convient, mais ce n'est pas grave.
Ainsi, quelqu'un produit un lien sur un site Web qui installe un logiciel sur votre machine pour surveiller les films que vous regardez et transmet les données à MegaCorp.Est-ce un virus?Votre réponse varie-t-elle selon que le «quelqu'un» est Microsoft, par rapport à un adolescent hacker?Votre évaluation mathématique du logiciel prend-elle en compte la fiabilité du créateur?En bref, cela peut-il être formulé comme un problème mathématique?
@MichaelKay: Oui.Non, juste si l'action enfreint votre politique.Oui.
J'ai entendu parler de NP complet, mais qu'est-ce que l'IA complète?
@Michael AI concurrence est l'idée (je crois un peu plus laineuse) que "vous ne pouvez pas résoudre ce problème sans créer également une intelligence artificielle générale".Je ne pense pas que ce soit aussi clairement défini que NP, donc cela ne se prête probablement pas à une preuve mathématique.
@R La sophistication croissante des logiciels malveillants et la merdique croissante des éditeurs de logiciels commerciaux rendent cette zone grise très vaste.La définition la plus sensée pour moi d'un logiciel malveillant serait un logiciel qui ferait quelque chose que l'utilisateur ne voulait pas et dont il n'était pas conscient - ce qui dépend non seulement des désirs de l'utilisateur, mais de sa capacité à comprendre ce qui se passe.Cela inclut-il la barre d'outils de navigateur merdique qu'Oracle inclut avec les mises à jour Java?Ou le proxy MITM Lenovo inclus avec certains de leurs ordinateurs portables?Presque tout sauf GNU HURD est dans la zone grise.
Merci, cela a du sens.J'en avais entendu une version moins rigoureuse, du genre: voici cinq (ou 10) problèmes qu'il serait très utile de résoudre, mais il s'avère que résoudre un seul d'entre eux (créer une AGI / ASI) serait en faitfournir les moyens de résoudre les autres également (en supposant que cela ne nous efface pas / ne fasse pas de nous ses animaux de compagnie / etc.)
Cela me rappelle la vieille question "qu'est-ce qu'une mauvaise herbe?"avec la réponse "tout ce que vous ne voulez pas pousser dans votre jardin", re: votre commentaire à @R
Michał Kuliński
2019-01-23 17:35:02 UTC
view on stackexchange narkive permalink

Oui, cela a été prouvé mathématiquement par l'église Alonzo en 1935–36 et indépendamment peu de temps après par Alan Turing en 1936.

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

Si l'instruction * était * d'une manière ou d'une autre réductible au problème d'arrêt, le plus intéressant serait de montrer que c'est le cas, pas seulement de le laisser tomber.Ou, pour le dire plus directement: non, ce n'est certainement pas ce que Church et Turing ont prouvé (ce n'est même pas proche de ce qu'ils voulaient prouver).
Oui @JeroenMostert vous avez raison.J'avais tort.Church et Turing ont prouvé qu'il n'existe pas de mécanisme qui décide si un tel programme qui détecte tous les virus peut même être écrit.J'ai confondu les concepts.Oncle Bob a blogué à ce sujet: https: //blog.cleancoder.com/uncle-bob/2018/06/21/IntegersAndEstimates.html
Alors, cette réponse doit-elle être supprimée ou complètement réécrite?
Le blog de Martin, bien qu'amusant, commet certaines des erreurs les plus courantes lorsqu'il s'agit d'expliquer le problème de l'arrêt.Par exemple, "la spécification d'un programme est une grande équation diophantienne dans un bazillion d'inconnues" est erronée, pure et simple.Certes, c'est * une * façon de spécifier un programme (si vous plissez les yeux), mais vous devez être * beaucoup * plus prudent que cela pour faire des déclarations significatives sur ce que les preuves disent est et n'est pas possible.Des explications comme celles-ci ont tendance à obscurcir plutôt qu'à clarifier - les mathématiques réelles sont subtiles, mais pour la bonne raison que ces choses * sont * subtiles.
Je ne suis pas sûr que cette réponse soit fausse: si "arrêter" signifie "produire un rapport répertoriant tous les virus du système, ni plus ni moins", alors nous ne pouvons pas prouver à l'avance que le programme s'arrêtera avec unbonne réponse à moins que nous l'exécutions pour le savoir.Notez que l'article référencé fait également référence au problème d'arrêt: https://web.archive.org/web/20140525233117/http://grnlight.net/index.php/computer-articles/109-an-undetectable-computer-virus
@schroeder supprimé.
@stevegt le problème d'arrêt n'est pas de savoir s'il donnera une réponse correcte.Il s'agit de savoir s'il peut même s'arrêter en premier lieu, ce qui est une période sans réponse.Vous ne saurez jamais s'il s'arrêtera, mais ce n'est pas utile ici car aucune connexion n'a été établie entre une machine qui détecte si une machine s'arrête et la machine qui détecte si une machine fait quelque chose de malveillant.
Philipp
2019-01-25 14:58:42 UTC
view on stackexchange narkive permalink

Non, vous ne pouvez pas, car la différence entre un logiciel malveillant et un programme utile est complètement subjective. Tout comportement «mauvais» peut être un comportement intentionnel. Par exemple, j'ai les programmes suivants en cours d'exécution sur mon ordinateur en ce moment:

  • Un programme qui crypte tous mes fichiers. S'agit-il d'un ransomware cryptolocker ou d'un outil de chiffrement complet du disque?
  • Un programme qui permet un accès à distance pour contrôler mon ordinateur. Est-ce un cheval de Troie ou est-ce Team Viewer?
  • Un programme qui crée des connexions réseau à toutes sortes d'ordinateurs partout sur Internet et échange des données obscures avec eux. S'agit-il d'un botnet ou d'une plateforme informatique distribuée?
  • Un programme qui envoie tous mes fichiers personnels vers un serveur distant. S'agit-il d'un logiciel espion ou de Cloud Backup?
  • Un programme qui télécharge des fichiers exécutables sur Internet et les exécute. Est-ce un dropper de malware ou est-ce Steam?

Vous ne pouvez pas faire la différence, car d'un point de vue purement technique, ils font exactement les mêmes choses. La seule différence réside dans l'intention. Un programme trompe l'utilisateur sur ce qu'il fait et agit contre les intérêts des utilisateurs, l'autre fait exactement ce que l'utilisateur veut qu'il fasse. Mais ce que l'utilisateur attend vraiment de son logiciel, c'est quelque chose qu'une machine ne peut pas décider ... du moins pas au stade actuel de la technologie de l'IA. C'est pourquoi tous les antivirus sont principalement basés sur les signatures.

kajacx
2019-01-24 18:43:56 UTC
view on stackexchange narkive permalink

Pour prouver mathématiquement qu'il est toujours possible d'écrire un virus capable de contourner tous les programmes antivirus existants, vous devez d'abord définir mathématiquement ce qu'est un virus, et bonne chance avec cela.

Peut-être un "programme qui effectue des actions indésirables"? Eh bien c'est tout simplement impossible, imaginez un programme qui ouvre une connexion à votre PC et permet le contrôle à distance. L'antivirus peut voir que le programme fait cela, mais comment savoir si c'est souhaité ou non?

Il peut s'agir d'un programme de contrôle à distance légitime comme TeamViewer, ou d'un virus mascaradant simplement programme de visualisation d'images, plus précisément, votre antivirus verra un programme capable de lire et d'afficher des images de votre PC et d'ouvrir des connexions à distance, et il n'aura aucun moyen de dire si c'est un comportement "souhaité" ou non, car il ne peut pas sachez pourquoi vous installez ce programme.

Matthew
2019-01-25 17:45:32 UTC
view on stackexchange narkive permalink

Comme l'a souligné @walen, il est en fait possible de détecter tous les virus si les faux positifs sont autorisés: il suffit de signaler tout comme un virus.

Supposons qu'il est également possible de détecter tous les virus si les faux positifs ne sont pas autorisés. Nous aurons une fonction IsVirus qui peut être exécutée sur n'importe quel programme et retourner si ce programme est ou non un virus. Maintenant, considérons ce programme que nous appellerons P:

  if IsVirus (P): exitelse: DoVirusThings

Quoi est la valeur de IsVirus (P) ? Si c'est true , alors P sort juste sans rien faire et nous avons donc un faux positif. Mais si c'est false , alors P fait des choses virales et nous avons un virus non détecté.

Cela prouve qu'il n'est pas possible de détecter tous les virus si les faux positifs ne sont pas autorisés.

Downvoter, veuillez expliquer pourquoi.Autant que je sache, cette preuve est valable.
Je n'ai pas voté contre, même si cela semble un peu décevant, car il ne semble pas y avoir de contradiction.C'est, si «IsVirus (P)» est vrai, alors votre script n'est pas viral;cependant, «IsVirus (P)» a affirmé que «P» était viral, pas votre script.
En réalité, personne ne se soucierait si «IsVirus» rapportait que «P» était en effet un virus, même s'il ne serait pas en fait un avec cette définition de «P».En effet, il n'est pas du tout déraisonnable d'appeler * `P` un virus, car il est conçu pour faire de mauvaises choses et devenir intelligent avec nous si nous essayons de l'identifier.En d'autres termes, le simple fait d'invoquer «IsVirus» pourrait être utilisé comme identificateur de virus pour tout programme qui n'est pas notre propre programme antivirus.(Il existe des moyens de «corriger» ce raisonnement, mais ils impliquent d'être beaucoup plus précis avec nos définitions.)
AiliacmsbfCMT `P` est le script
@Matthew Hah, opps, a raté cette partie!Cela semble être une contradiction alors, bien que cela semble être un problème d'auto-référentiel, comme "_Cette déclaration est fausse._", plutôt que la classification de virus.
Un programme antivirus pourrait identifier tout ce qui contient `DoVirusThings` comme un virus, car il n'a aucune utilité dans les programmes non-virus et peut être appelé d'une autre manière.
Je pense que vous supposez que «le code étant un virus» est entièrement corrélé au «code faisant des choses virales lorsqu'il est exécuté».Ce n'est pas une hypothèse folle, mais c'est néanmoins une hypothèse (et avec cette hypothèse, je pense que votre preuve fonctionne).
Hm, vous ne pouvez pas facilement introduire `P` dans une fonction si` P` est censé être le programme entier.Au lieu de cela, faites en sorte que la "fonction" IsVirus soit un exécutable qui vérifie les virus et insérez l'exécutable actuel en tant que nom de fichier.Maintenant, il est beaucoup plus facile pour le programme de «se nourrir de l'antivirus» et de créer la contradiction. cependant, alors le programme `P` * fera * des choses virus-y quand un exécutable arbitraire` IsVirus` retourne faux sur lui, donc le signaler comme virus est en fait correct.
stevegt
2019-01-24 05:21:03 UTC
view on stackexchange narkive permalink

La question initiale était "At-il été prouvé mathématiquement qu'un antivirus ne peut pas détecter tous les virus?"

Il est probablement exact de dire que nous ne pouvons jamais prouver que nous avons écrit un code qui détecte tous les virus.

Un ordinateur à usage général connecté à Internet avec la capacité de télécharger et d'exécuter du code est probablement équivalent à une machine de Turing universelle. Cette équivalence inclut la taille de bande infinie de Turing: si la bande passante de l'interface réseau de la machine est inférieure au taux de croissance total des données accessibles sur Internet, la machine ne peut jamais atteindre la «fin de la bande». (J'ai couvert cela un peu dans la conclusion de cet article il y a longtemps. Bien que cela puisse être démontré dans un sens pratique, trouver une preuve mathématique nécessiterait probablement l'ajout de certaines contraintes.)

Si ce qui précède est vrai, et si "arrêter" signifie "produire un rapport listant tous les virus sur le système, ni plus ni moins", alors nous ne pouvons pas prouver à l'avance que le programme s'arrêtera avec un répondre; nous devons l'exécuter pour le découvrir.

Si les deux paragraphes ci-dessus sont vrais, nous ne pourrons jamais vérifier l'exactitude du rapport résultant, car nous ne pourrons jamais compiler une liste complète de tous les virus possibles avec lesquels la comparer: ces virus sont tous là-bas quelque part sur la bande, sa taille est infinie et nous ne pouvons jamais tout lire.

Si les trois paragraphes sont vrais, nous ne pourrons jamais prouver que nous avons écrit un détecteur de virus 100% correct.

Adithya Sama
2019-01-24 16:13:56 UTC
view on stackexchange narkive permalink

Eh bien, la définition d'un virus est assez vague. Oui, c'est une entité malveillante, mais malveillante est tout aussi vague. En fonction du système et de ses politiques, les possibilités d'une entité malveillante changeront. Définir une entité en constante évolution est quelque chose qui est apparu dans divers domaines, la théorie des nombres, les machines à états, etc. et il a été prouvé de différentes manières que ce n'est pas possible, du moins sur la base de ce que nous savons.

Une façon serait, au lieu de définir ce qui est malveillant, nous pouvons définir ce qui est autorisé, un système très strict et indépendant, qui ne permet que certaines séquences d'opérations à effectuer. De cette façon, il PEUT être gardé en sécurité.

Ce problème IMO est tout aussi difficile que de définir l'aléatoire.

Bill K
2019-01-25 05:52:11 UTC
view on stackexchange narkive permalink

Un virus n'est que du code - c'est gentil de dire "Mon programme de tondeuse à gazon AI peut-il faire la différence entre les mauvaises herbes et les plantes" - si oui, est-ce qu'il tire des daises?

Si vous téléchargez un programme qui envoie des e-mails à tout le monde dans votre liste de contacts, est-ce un virus ou êtes-vous un spammeur? Cela dépend de la raison pour laquelle vous avez téléchargé le programme, pas des octets spécifiques du programme.

Donc, vous n'avez même pas besoin d'aller à la preuve mathématique - vous pouvez simplement raisonner que cela ne peut pas être fait.

D'un autre côté, vous pourriez dire qu'il est facile d'identifier les virus si vous définissez le virus par son comportement. Les programmes sont mis à jour dans le cadre d'un processus de mise à jour.Si quelque chose tente de modifier le code de votre ordinateur en dehors de ce processus, vous pouvez le définir comme un virus. Avec ces définitions, vous pouvez facilement détecter les changements qui se produisent en dehors des procédures d'installation spécifiques. Cela peut prendre du matériel capable de séparer le code des données et de verrouiller l'espace de code lorsque vous ne maintenez pas un bouton, mais c'est possible (si ennuyeux).

Cela suppose également que le code que vous avez délibérément installé pendant le processus de mise à jour n'est pas un virus en lui-même, mais puisque nous définissons un virus par comportement pour cet exemple, je suppose que ce n'est pas le cas par définition.

guest271314
2019-01-28 02:13:56 UTC
view on stackexchange narkive permalink

At-il été prouvé mathématiquement que l'antivirus ne peut pas détecter tous les virus?

À quelle analyse Bruce Schneier faisait-il référence lorsqu'il a écrit:

Les virus n'ont pas "guérir." Il a été prouvé mathématiquement qu'il est toujours possible d'écrire un virus qu'aucun programme antivirus existant ne peut arrêter. "[0]

[0] Secrets & Lies. Bruce Schneier. Page 154

Cette réponse ne traite pas directement de l'analyse que Bruce Schneier faisait référence. Une personne intéressée par la signification d'une source principale lorsqu'elle a fait une déclaration doit faire l'effort de contacter le source principale eux-mêmes pour poser leurs questions spécifiques , afin d'éviter toute spéculation, conjecture ou confusion.

Le Théorème d'incomplétude de Kurt Gödel publié en 1931 dans Über formal unentscheidbare Sätze der "Principia Mathematica" und verwandter Systeme (appelé en anglais "On Formally Undecidable Propositions of" Principia Mathematica "and Related Systems" ), lorsqu'il est soigneusement considéré, est très instructif pour l'analyse de tout système formel, des virus informatiques à la politique

1. Si un système (formel logique ou axiomatique) est cohérent, il ne peut pas être complet.
2. La cohérence des axiomes ne peut pas être prouvée dans leur propre système.

Ces théorèmes ont mis fin à un demi-siècle de tentatives, commençant par les travaux de Frege et aboutissant à Principia Mathematica et Hilbert formalisme, pour trouver un ensemble d'axiomes suffisant pour toutes les mathématiques.

Avec le recul, l'idée de base au cœur du théorème d'incomplétude est assez simple. Gödel a essentiellement construit une formule qui prétend qu'elle n'est pas démontrable dans un système formel donné. Si c'était prouvable, ce serait faux. Ainsi, il y aura toujours au moins un déclaration vraie mais non démontrable. Autrement dit, pour tout ensemble d'axiomes calculables pour l'arithmétique (c'est-à-dire un ensemble qui peut en principe être imprimé par un ordinateur idéalisé avec des ressources illimitées), il existe une formule qui est vraie pour l'arithmétique, mais qui n'est ce système. Pour rendre cela précis, cependant, Gödel avait besoin de produire une méthode pour coder (sous forme de nombres naturels) les déclarations, les preuves et le concept de prouvabilité; il l'a fait en utilisant un processus connu sous le nom de numérotation Gödel.

Mr. E
2019-01-24 01:17:27 UTC
view on stackexchange narkive permalink

Ce n'est pas une preuve mathématique, mais AFAIK, il existe deux façons de détecter les logiciels malveillants:

Signatures

Au fur et à mesure que de nouveaux logiciels malveillants peuvent être développés - y compris l'obscurcissement ou modifier les existants - la signature du nouveau malware ne sera pas dans la base de données antivirus, donc il ne sera pas détecté

Heuristique

Cette méthode utilise une analyse dynamique et / ou statique automatique pour comprendre le comportement du logiciel et en fonction de ce qu'il fait, l'antivirus décide s'il est malveillant ou non.

Et voici la partie délicate, tout ce qui est aujourd'hui considéré comme inoffensif ne le sera peut-être pas dans le futur.

Par exemple, il y a 20 ans, un logiciel utilisant des bibliothèques de chiffrement ne l'a peut-être pas été considéré comme quelque chose de malveillant, nous savons maintenant qu'il peut s'agir d'une sorte de ransomware cryptant vos données. Dans le même temps, vous pouvez (et vous devriez) utiliser un gestionnaire de mots de passe qui utilise également des bibliothèques de cryptage pour stocker vos données en toute sécurité. Alors, comment pouvons-nous décider s'il s'agit d'un malware ou pas uniquement en fonction du fait qu'il crypte les données? De même, une connexion TCP peut être utilisée pour fuir des informations ou pour parcourir des sites Web

La seule différence est la sémantique, qui est difficile à analyser de manière automatique car les technologies évoluent constamment et les logiciels malveillants s'adaptent à cette évolution. Après tout, les logiciels malveillants ne sont pas différents de tout autre logiciel, à l'exception des mauvaises intentions de son propriétaire

Vous répondez à la question comme un programmeur (ce que je suis).C'est inutile.Leur question ne vit pas dans le domaine de la réalité mais plutôt dans la théorie.C'est comme quand j'essaye de convaincre les gens qu'aucune "IA" (Intelligence Artificielle) ne peut être mauvaise ou avoir une âme.Ils signalent des recherches ou un article de niveau Elon Musk / Alex Jones et je souligne le mot «Artificiel».Ils n'écoutent toujours pas.Être un expert ne vous aide pas lorsque vous vous disputez avec la plupart des gens.
"Être un expert ne vous aide pas lorsque vous vous disputez avec la plupart des gens."Bien que cela soit vrai, ils demandent des sites Web dont le seul but est de demander à des «experts» en la matière.Pourquoi demander à quelqu'un s'il n'est pas disposé à accepter sa réponse?
Tout le monde est un expert.
R.. GitHub STOP HELPING ICE
2019-01-23 22:24:54 UTC
view on stackexchange narkive permalink

Non, cela n'a pas été prouvé et ne peut pas être prouvé parce que ce n'est pas vrai. Un programme antivirus qui fonctionne réellement est simplement un modèle de contrôle des autorisations / accès approprié appliqué par l'environnement d'exécution. Le théorème de Rice n'est pas pertinent car vous n'avez pas à déterminer à l'avance si un programme est sûr. Vous l'exécutez simplement sous les contrôles d'accès et l'abandonnez (ou refusez simplement l'accès) s'il tente de faire quelque chose de contraire à votre politique.

Mathématiquement, cela signifie que vous avez un test calculable qui vous donne un résultat positif résultat si un programme est malveillant , mais peut ne pas s'arrêter si le programme n'est pas malveillant. C'est très bien, car le test exécute le programme, et vous pouvez continuer à fonctionner tant que ce n'est pas malveillant.

Bien sûr, les programmes antivirus du monde réel ne font pas la chose simple évidemment juste (qui serait intégré au système d'exploitation, à la machine virtuelle d'exécution ou à un composant similaire, et non à un produit audiovisuel séparé). Au lieu de cela, ils utilisent de fausses signatures et heuristiques pour classer les programmes. Il est prouvable (voir d'autres réponses) qu'une telle approche ne peut pas fonctionner.

"Non quoi?Non cela n'a pas été prouvé?Mais lisez les autres réponses qui montrent que cela a été prouvé?Un début de réponse très déroutant.Pouvez-vous clarifier?
Le non est une réponse directe à la ligne d'objet de la question.Je vais élaborer.
Dois-je éliminer le virus qui utilise Rowhammer pour écraser les contrôles de sécurité du noyau?
@Joshua: L'environnement d'exécution peut complètement détecter ou empêcher cela.Par exemple en exécutant le programme sous un interpréteur.Voir «modèle de contrôle d'accès approprié».Dans ce cas, le matériel est bogué et autoriser tout accès direct de bas niveau à cette partie du système (faire des requêtes sur le bus mémoire) est un contrôle d'accès insuffisant.
Contrairement à spectre (jusqu'à présent), rowhammer peut être exploité via un interprète.
Pouvez-vous * prouver * l'existence présumée de cet * environnement d'exécution approprié *?
Supposons que vous ayez deux programmes: un programme légitime qui nettoie les anciens fichiers temporaires qui correspondent à certains critères, et un programme malveillant qui supprime les fichiers importants qui correspondent à certains critères.Comment les contrôles d'accès à l'exécution distinguent-ils de manière fiable ces cas?
@ulidtko: Oui.Méthodes formelles Les gens font des choses comme ça tout le temps avec la vérification des conceptions logiques.Mais cela dépend d'une formalisation de vos règles pour ce qui est autorisé et ce qui ne l'est pas.Beaucoup de gens n'ont même pas en tête un modèle pour ce qui est et ce qui n'est pas malveillant, et s'attendent à ce qu'une machine (ou une autre personne) lise leur esprit et applique les normes sociales de l'intérieur pour prendre la décision.Bien sûr, cela semble peu probable.
@Ray: Le contrôle d'accès permet d'écrire / supprimer sur un ensemble de fichiers et pas sur un autre.C'est ainsi que fonctionnent les autorisations normales du système de fichiers.
@Joshua: Cela dépend de la nature de l'interprète.Il ne peut certainement pas être exploité sur un interpréteur qui permute les adresses physiques et virtuelles via un chiffrement cryptographique fort (sans également casser le chiffrement), ou juste un qui limite l'accès à la mémoire d'une manière appropriée.* Si * votre machine physique est sujette à de tels bogues, * alors * votre contrôle d'accès doit inclure des mesures pour empêcher l'accès aux mécanismes de déclenchement de ces bogues.Ce n'est pas sorcier, les gens.
Bien que bon, cela n'empêchera pas tous les virus.@Ray vous a permis de contourner le problème avec cet exemple spécifique, mais ce ne sera pas toujours le cas.Qu'en est-il de l'endroit où _le même logiciel_ peut être considéré dans un cas d'utilisation comme utile mais dans un autre cas d'utilisation comme malveillant?Pensez à un logiciel qui permet le contrôle à distance de votre ordinateur, écrit et utilisé initialement pour de bon.Puis d'autres en abusent.Le joueur appelle cela un logiciel génial lorsque son copain lui obtient de l'XP pendant qu'il dort, et son voisin le considère comme un logiciel malveillant lorsque son ennemi fait un bruit blanc désagréable.Les déchets d'une personne sont le trésor d'une autre.
@Aaron: ** Pour la nième fois **, il s'agit de choisir le modèle de contrôle d'accès approprié / de définir le malware.
BTW mis à part le ton, ma réponse ici est fondamentalement la même que [réponse de James_pic] (https://security.stackexchange.com/a/202047/2836) qui est apparue plus tard et n'est pas si ridiculement critiquée par des personnes qui ne l'ont pas faitlisez les commentaires.
Cette réponse explique comment empêcher l'exécution de _ programmes non autorisés_, pas de virus en particulier.La question concerne spécifiquement les logiciels malveillants.
@forest: Malware est juste un programme qui fait quelque chose que vous ne voulez pas qu'il fasse.
@R .. a écrit "choisir le contrôle d'accès approprié ..." Si c'est aussi simple que cela, alors vous devriez écrire un article dessus.Parce que, avec l'exemple spécifique que j'ai fourni, si vous pouvez réellement écrire un tel contrôle d'accès ou une telle définition pour faire la différence entre «l'action A est ok» et «(exactement la même chose) l'action A est malveillante», alors vous deviendriez millionnaire.Non, mieux encore, parce que vous auriez complètement défié la logique elle-même et découvert un type de logique entièrement nouveau pour rendre cela possible, vous pourriez bien devenir milliardaire, ou être capable de défier la physique avec la nouvelle logique et devenir un surhomme.
... mon point est, exactement la même chose, la même chose, la même action peut être à la fois malveillante ** et ** non malveillante.Pas au même endroit au même moment, bien sûr.Mais à un endroit différent, ou à une heure différente.Peut-être même sur le même ordinateur, avec les mêmes contrôles d'accès définis, faisant la même action (même fichier, même modification, etc.), mais Susy considère que c'est une bonne chose, puis une demi-heure plus tard quand son frère utilise le PC qu'il considèrec'est malveillant.Ou Susy le considère comme malveillant au temps X mais pas au Y ("play-me-a-tune-app" est cool pendant le temps libre, mais peut facilement être utilisé comme malware)
@R .. Je tiens à répéter, vous êtes sur la bonne voie.Mes commentaires ne sont pas signifiés autrement.De meilleurs contrôles d'accès amélioreraient le blocage des logiciels malveillants.Ce que vous proposez est une énorme amélioration par rapport aux antivirus modernes.Les points qui lui sont opposés sont simplement que, dans cette Q&R spécifique, le demandeur de questions a posé des questions très spécifiques sur les preuves mathématiques de la détection de chaque malware.Nous devons supposer que cela signifie avec un minimum de faux positifs, sinon la réponse est "tout bloquer".Ainsi, lorsque "p! = Q" et "p = q" sont tous les deux vrais, nos commentaires suggèrent que ce n'est pas le cas.
L'idée centrale de cette réponse semble correcte, bien que le cadrage soit incorrect - en particulier, il semble que cette réponse concerne une question légèrement différente, mais mal cadrée pour correspondre à cette question.Le problème est que cette question porte sur la manière d'analyser un programme pour déterminer s'il s'agit d'un virus en fonction de sa spécification, par ex.un binaire de celui-ci, que cette réponse n'essaie même pas de traiter.Cependant, je suppose que cette réponse est une sorte de défi de cadre dans la mesure où la raison pour laquelle elle ne tente pas de répondre à la question est qu'elle propose une meilleure solution que l'antivirus: la gestion de l'exécution.
marshal craft
2019-01-24 13:47:47 UTC
view on stackexchange narkive permalink

Je suis moi-même d'accord avec Najib. Les théorèmes de modèles ne peuvent être appliqués qu'à un sous-ensemble logique très formel d'une logique formelle. Je ne sais pas que quoi que ce soit puisse être formulé sur l'incomplétude de la réalité, sur la base d'une grammaire logique formelle. Cela semble être une question de philosophie plus grande à un moment donné. Cela dit, en supposant que vous puissiez décrire concrètement ce que signifie être virus ou malveillant, c'est-à-dire que cela peut être formulé comme une question mathématique, alors assurez-vous que cela peut être montré.

Les ordinateurs présentent des ressources limitées. Ainsi, par la force brute, chaque état peut être considéré et s'il est malveillant.

Cela échoue si des combinaisons d'états à travers le temps sont envisagées, peut-être? Je ne peux pas me dire.

kubanczyk
2019-01-23 17:10:37 UTC
view on stackexchange narkive permalink

Pouvons-nous avoir un antivirus qui détecte tous les virus?

Aucun calcul nécessaire. Temps d'expérimentation. Organisons un pool de virus, un pool de systèmes qui essaient de se défendre et des mécanismes qui changent / améliorent constamment les deux parties.

Donnez-leur une planète. Attendez des milliards d'années.

Avons-nous encore des virus?

Pour moi, le grand nombre de possibilités déjà testées est bien au-delà de la satisfaction.

À propos de «prouver»

Ici, je voudrais expliquer pourquoi j'ai radicalement recadré votre question.

La réponse directe à votre question "A-t-il été prouvé mathématiquement qu'une déclaration d'< sur le monde réel>" est: Non, les mathématiciens n'ont jamais prouvé votre déclaration sur le monde réel (ou toute autre déclaration du genre). Par monde réel, j'entends celui que vous voyez lorsque vous regardez par la fenêtre.

Vous ne pouvez prouver quoi que ce soit dans les systèmes axiomatiques ("mondes" régis par un ensemble de axiomes - où les axiomes eux-mêmes sont définis comme non démontrables). Je ne connais pas les axiomes qui régissent les vrais virus informatiques, donc je ne peux rien prouver à ce sujet.

J'essaierai de prédire la réalité et j'aurai souvent raison, bien sûr. Mais j'utiliserai pour cela des théories falsifiables, pas des preuves.

Votre argument va un peu trop dans l'autre sens - il y a des lacunes évidentes dans ce que l'évolution biologique peut pratiquement accomplir (aucune vache n'a sauté par-dessus la lune), et l'absence de «solutions» à certains «problèmes» est difficile à acceptercomme preuve absolue que quelque chose ne peut être fait que si vous démontrez pourquoi nous ne pourrions pas faire mieux.En particulier, les mécanismes par lesquels les virus et les logiciels antivirus sont «évolués» et «sélectionnés» sont très différents.Même le mot «virus» est devenu un abus de langage lorsqu'il s'agit de logiciels malveillants actuels (qui se copient rarement).
@JeroenMostert Je viens de rapporter un fait.Alors que vous sous-entendez que jouer avec des pensées dans nos têtes donnerait des résultats plus satisfaisants, dans ce cas, le nombre de répétitions et les immenses pools de spécimens impliqués me suffisent.Autrement dit, je suppose qu'il est beaucoup plus probable qu'un cerveau humain oublie quelque chose ici, que pour toute la biosphère qui le vérifie pendant tant de générations.(Mais - oui! - dans d'autres cas, notre réflexion peut être supérieure, bien sûr. Tant mieux pour nous!)
Les voitures sont impossibles.Preuve: des milliards d'années d'évolution n'ont pas donné de roues.Q.E.D.Cela échoue, bien sûr, car les parallèles entre la biologie et l'ingénierie ne vont que très loin - vous n'avez même pas besoin de présupposer des inventeurs intelligents pour cela.De même l'informatique.Nous avons repéré de jolis parallèles entre les programmes de réplication et les virus biologiques il y a longtemps, mais c'est aussi loin que cela va, et les programmes de réplication réels ne sont devenus que des curiosités théoriques, tandis que les programmes malveillants sont morts mais en train de battre.Le parallèle biologique est-il toujours valable et perspicace?Je ne suppose pas.
@JeroenMostert Oui, je pense que je l'ai mentionné aussi.
La question n'est pas de savoir si des preuves sont possibles ou non.Vous avez fait un pas en répondant à la question.Il y a eu une référence et le cadrage est fait dans ce contexte.Ceci est une non-réponse.
@schroeder Ah, c'est une préoccupation valable - je me suis modifié moi-même pour corriger mon omission.
Outre les lacunes relevées dans les commentaires précédents, cette réponse (probablement accidentellement) repose implicitement sur des hypothèses erronées quant à l'équivalence entre virus biologiques et virus informatiques.Ce n'est pas parce que les deux sont appelés «virus» qu'ils ont des propriétés pertinentes identiques.Le nom est une métaphore, pas une définition précise.
** Les processus évolutifs ne sont pas optimisés **;ils sont [satisfaisants] (https://en.wikipedia.org/wiki/Satisficing).Vous ne pouvez pas prétendre que l'échec d'un système évolutif à développer une stratégie optimale contre un agent contradictoire prouve son impossibilité.De plus, je suis presque sûr qu'OP ne se soucie pas du système axiomatique utilisé dans la preuve.Personne ne vous condamnerait pour avoir utilisé les [axiomes de Zermelo – Fraenkel] (https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory#Axioms), et souligner ses problèmes est un hareng rouge.
Marshall Whittaker
2019-01-24 00:04:43 UTC
view on stackexchange narkive permalink

Plus ou moins, oui. Les mathématiques derrière cela en termes simples, cela se résume à un paradoxe d'amorçage, un type de paradoxe temporel qui remet en question l'origine de l'information. Cela est lié à ce problème en ce que si vous avez un antivirus qui détecte tous les virus connus, mais que le lendemain, quelqu'un crée un nouveau virus, il n'y aurait pas de signature dans l'ancienne analyse antivirus pour détecter le nouveau virus fort>. Si vous pouviez prendre tous les virus informatiques de la fin des temps, puis les renvoyer vers l'avant maintenant et créer des signatures de virus à partir d'eux tous, d'où proviennent les informations ? L'avenir ou le passé? Comme le consensus général est que le voyage dans le temps est impossible pour un certain nombre de raisons mathématiques / physiques, vous ne pouvez pas avoir une couverture de tous les virus , seulement de tous les virus connus .

Cela repose sur l'hypothèse non déclarée que "les antivirus ne peuvent pas détecter les virus qui n'existaient pas, ou n'étaient pas connus, lors de la création / de la dernière mise à jour de l'antivirus".C'est la clé de la question, donc le simple fait de supposer que c'est vrai signifie que votre réponse n'a pas de substance réelle.De plus, pour ** certains ** virus, cette hypothèse est clairement fausse, car les heuristiques fonctionnent sur certains virus.Tout le discours sur le voyage dans le temps n'est que duvet.


ⓘ
Ce Q&R a été automatiquement traduit de la langue anglaise.Le contenu original est disponible sur stackexchange, que nous remercions pour la licence cc by-sa 4.0 sous laquelle il est distribué.
Loading...