在数学上是否已经证明防病毒不能检测到所有病毒？

#1 楼

在一种可能的解释下，这是赖斯定理的结果。如果程序执行某些恶意操作，则该程序是恶意的，这使其成为语义属性。有些程序是恶意的，而有些则不是，这使其成为不平凡的财产。因此，根据赖斯定理，一般情况下无法确定程序是否为恶意程序。

#2 楼

实际上，相反的事实很容易得到证明：由于所有计算机病毒都以某种方式是可执行代码，因此您所要做的就是编写一个防病毒程序，该程序会将任何可执行代码报告为病毒。从逻辑上讲，这样的程序将检测所有可能的病毒：


防病毒程序检测到所有代码（C→D）
所有病毒均为代码（V→C）
您的防病毒软件（V→D）可以检测到所有病毒。

当然，可以对这种防病毒软件拒绝过多的“误报”提出质疑。但是，确定阳性是假还是假的标准是什么？啊!事实证明，良性代码与恶意代码之间的区别，诚实的“远程PC控制”套件和类似Netbus的木马之间的区别是完全任意的，因此整个问题毫无意义。

#3 楼

据维基百科：


1987年，弗雷德·科恩（Fred Cohen）发表了一篇论证，其中没有一种算法可以完美地检测所有可能的病毒。也参考了本文。那可能就是施耐尔先生所指的分析。

#4 楼

除非将其重新表述为数学命题，否则该声明无法在数学上得到证明。并且您可能会得到一个在实践中没有用的抽象，因为它包含了一些人们认为完全良性和有用的行为，并且/或者排除了一些人们认为是反社会的行为。

这里的难点在于，病毒是一种以某种方式改变其环境的程序，任何严格定义环境的尝试都将在实际使用中受到很大限制。该命题无法在数学上得到证明，这是因为它不能用数学公式表述。

#5 楼

tl; dr-答案取决于您对该问题施加的要求是什么。 ，就可以了。


如果您想正确地将所有程序识别为病毒，那么在无限制的情况下是不可能的，因为分类问题可以简化为停顿问题。 。


如果您想将所有程序正确地识别为病毒还是非病毒，并且您正在考虑使用一台有限的机器，那么从理论上讲这是可行的，但实际上通常不可行。 />

如果允许计算机产生随机错误，则任何程序都可以是病毒。


情况1：完整的病毒检测
显然，将所有程序标记为病毒可以将它们全部捕获。 （Pok'e'mon！）
从这种情况开始，指出要检测所有病毒并不困难；相反，特定的理论问题是当程序是病毒时才正确分类。
情况2：在一般的无限制情况下不可能正确地分类
考虑程序：

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

在这种情况下，仅当停止问题停止运行时，该程序才是病毒，从而使installEveryVirusEver()发生。因此，在没有约束力的一般情况下，病毒检测可以减少停顿问题。
情况3：在受限情况下可以通过强力搜索进行搜索
在有限的机器上运行，那么您可以简单地模拟从每种可能的启动状态开始运行的机器。有限的计算机最终将循环回到先前的状态，因此它必须是有限的（如果是冗长的）分析。
案例4：可能出错的计算机可以自发出现病毒
假设一台机器可以运行被视为病毒的程序，并且随机突变将其转移到该状态的可能性不为零，那么它最终应该会进入病毒状态。

讨论问题中的报价

病毒没有“治愈方法”。数学上已经证明，编写任何现有的防病毒程序都无法停止的病毒总是可能的。在上述情况（1）中，可以通过仅将所有内容标记为病毒来标记所有病毒；这很容易。在无约束的情况下，不可能确定每个可能的程序是否都是病毒。
此外，很难确定特定程序在受约束的情况下是否为病毒。例如，考虑以下程序：如案例（3）所述，在有限的计算机上运行时，该程序可以归类为病毒或非病毒，但是这样做可能需要蛮力。 -强制使用加密的消息，在实际情况下不太可能。或者，如果您想要更可靠的安全性，则可以让防病毒程序标记任何它证明不安全的内容，从而避免了需要对每个可能程序进行分类的问题。知识渊博的攻击者将安全漏洞作为目标。在没有阅读报价来源的情况下，我怀疑这是他们试图引用的问题。

#6 楼

这取决于您对“ stop”的定义。

如果将stop定义为“提前检测到该代码可能会执行恶意操作并阻止其运行”，那么正如其他人所提到的，根据Rice定理，这是不可能的。

如果将stop定义为“检测正在运行的程序试图做某件事然后停止它”，则Rice定理不适用。您的防病毒软件不需要决定程序是否可以进行恶意操作，而只需确定它是否现在就可以进行恶意操作。实际上，对于“恶意”的任何足够具体的定义，这都是非常可行的-这本质上是沙箱操作。病毒可能尝试的所有恶意形式。开采比特币的病毒呢？还是提供海盗电影？还是代表您发送垃圾留言板？所有这些与真正希望完全执行这些操作的用户所运行的代码没有区别。因此，我怀疑（尽管我不知道有什么尝试证明）创建防病毒软件是AI完整的。

#7 楼

是的，它在1935–36年间由Alonzo Church在数学上进行了证明，此后不久又在1936年由Alan Turing独立地进行了证明。

#8 楼

不，您不能，因为恶意软件和有用程序之间的差异完全是主观的。任何“邪恶”行为都可以是预期的行为。例如，我现在在计算机上运行以下程序：


用于加密我所有文件的程序。是密码锁勒索软件还是全盘加密工具？
允许远程访问控制我的计算机的程序。它是特洛伊木马程序还是Team Viewer？是僵尸网络还是分布式计算平台？
一个程序，可以将我的所有个人文件发送到远程服务器。它是间谍软件还是Cloud Backup？
一个程序，可以从Internet下载可执行文件并运行它们。是恶意软件删除程序还是Steam？

您无法分辨出两者之间的区别，因为从纯粹的技术角度来看，它们执行的操作完全相同。唯一的区别在于意图。一个程序欺骗用户有关其行为并损害用户利益的行为，而另一个程序则恰好执行用户希望它做的事情。但是用户真正希望从其软件中获得的东西是机器无法决定的……至少在目前的AI技术阶段还无法确定。

#9 楼

要以数学方式证明始终可以编写一种可以绕过所有现有防病毒程序的病毒，则必须首先以数学方式定义什么是病毒，并祝您好运。

也许“执行不良动作的程序”？好吧，这简直是不可能的，想象一下一个程序，该程序可以打开与PC的连接并启用远程控制。防病毒软件可以看到该程序可以执行此操作，但是它怎么知道是否需要它呢？简单的图像查看程序，采用简单的方式，您的防病毒软件将看到一个可以从您的PC读取和查看图像并打开远程连接的程序，并且它无法告诉您是否存在“所需”行为，因为它可以不知道为什么要安装该程序。

#10 楼

正如@walen指出的那样，如果允许假阳性，实际上就可以检测到所有病毒：只需将所有内容都报告为病毒即可。 -阳性。我们将提供一个IsVirus函数，该函数可以在任何程序上运行，并返回该程序是否为病毒。现在，考虑一下我们称为P的程序：

if IsVirus(P):
    exit
else:
    DoVirusThings

IsVirus(P)的值是什么？如果它是true，那么P只是不做任何事情就退出，因此我们有一个假阳性。但是如果它是false，那么P确实会病毒，并且我们有未检测到的病毒。

#11 楼

最初的问题是“是否已经在数学上证明了防病毒不能检测到所有病毒？”

很准确地说，我们永远不能证明我们已经编写了可以检测所有病毒的代码。 br />
连接到Internet的具有下载和执行代码功能的通用计算机可能等同于通用Turing机。这种等效性包括Turing的无限磁带大小：如果计算机网络接口的带宽小于Internet可访问数据的总增长率，则计算机将永远无法到达“磁带末端”。 （很久以前，我在本文的结论中对此进行了一些介绍。尽管在实践意义上可以证明这一点，但提出数学证明可能需要添加一些约束。）是的，如果“停止”的意思是“产生一份列出系统中所有病毒的报告，或多或少”，那么我们无法事先证明该程序将以正确的答案停止；我们必须运行它才能找到答案。

如果以上两个段落都正确，那么我们将永远无法验证结果报告的正确性，因为我们永远无法汇编所有可能的病毒的完整列表来与之进行比较：这些病毒全部被排除在外。在磁带上的某个地方，它的大小是无限的，我们永远无法阅读全部内容。

如果所有三个段落都正确，那么我们将永远无法证明我们已经编写了100％正确的病毒检测器。

#12 楼

嗯，病毒的定义非常模糊。是的，它是一个恶意实体，但恶意同样模糊。根据系统及其策略，恶意实体的可能性将改变。定义一个不断变化的实体是在各个领域，数论，状态机等领域提出的，并且至少以我们所知，已经以不同的方式证明了这是不可能的。

一种方法是，可以定义允许的内容，而不是定义恶意的内容，而是一个非常严格且独立的系统，该系统仅允许执行某些特定的操作序列。这样可以保持安全。

这个问题IMO与定义随机变量一样困难。

#13 楼

病毒只是代码-如果说“我的AI割草机程序可以告诉我杂草和植物之间的区别”是一种代码-如果是这样，它是否会引起干扰？向您的联系人列表中的所有人发送电子邮件，是病毒还是垃圾邮件发送者？取决于您下载程序的原因，而不取决于程序中的任何字节。

因此，您甚至不必进行数学证明-您可以说它无法完成。

另一方面，如果您按行为定义病毒，则可以说很容易识别病毒。程序将作为更新过程的一部分进行更新，如果在此过程之外尝试更改计算机上的代码，则可以将其定义为病毒。使用此定义，您可以轻松检测出特定安装过程之外发生的更改。当您不按住按钮时，可能需要能够将代码与数据分离并锁定代码空间的硬件，但是这是可能的（如果很烦人）。在更新过程中安装的病毒本身并不是病毒，但是由于我们是根据此示例的行为来定义病毒，因此根据定义，我猜不是。

#14 楼

在数学上是否已经证明防病毒不能检测到所有病毒？ />病毒无法“治愈”。数学上已经证明，编写任何现有的防病毒程序都无法停止的病毒始终是可能的。“ [0]

[0]秘密与谎言。布鲁斯·施耐尔。 154



此答案不能直接解决Bruce Schneier所指的分析问题，对陈述时主要来源有何意义感兴趣的个人应作出努力可以联系主要资料来源自己提出具体问题，以避免猜测，猜想或混乱。的英文版“关于“数学原理”和相关系统的形式不确定的命题”）时，仔细考虑该方法对于分析任何形式的系统（从计算机病毒到政治系统）都非常有启发性。 /> 1.如果是（逻辑或公理形式）系统是一致的，不能完整2。公理的一致性无法在其自身的系统中得到证明。


这些定理结束了半个世纪的尝试，始于弗雷格的著作，并以《数学原理》和希尔伯特的形式主义，找到一套足以满足所有数学要求的公理。

事后看来，不完全性定理的核心基本思想很简单。哥德尔实质上构造了一个公式，该公式声称该公式在给定的形式系统中不可证明。如果
可证明，那将是错误的。因此，将始终至少有一个
真实但无法证明的陈述。也就是说，对于任何可计算的
一组算术公理（即原则上可以由资源无限的理想计算机打印出来的一组），其中的一个公式对算术是正确的，但无法证明在该系统中。但是，为了精确起见，Gödel需要产生一种
方法来编码（作为自然数）陈述，证明和可证明性概念。他使用称为Gödel
编号的过程来做到这一点。

#15 楼

不是数学上的证明，但是AFAIK有两种检测恶意软件的方法：

签名

随着新恶意软件的开发，包括混淆或修改现有恶意软件，新的恶意软件不会出现在防病毒数据库中，因此也不会被检测到。

启发式

此方法使用自动动态和/或静态分析来了解恶意软件的行为软件，并根据其功能决定防病毒软件是否为恶意软件。

这是棘手的部分，并不是今天认为无害的一切都可能在未来。

例如20年前，使用加密库的软件可能尚未被视为恶意软件，现在我们知道这可能是某种勒索软件来加密您的数据。同时，您可以（而且应该使用）密码管理器，该管理器也使用加密库来安全地存储数据。那么，如何仅根据它加密数据这一事实来确定它是否是恶意软件呢？同样，TCP连接可用于泄漏信息或浏览网站

，唯一的区别是语义，这很难自动进行分析，因为技术不断发展，而恶意软件也适应了这种发展。毕竟，除了恶意软件所有者的恶意行为之外，其他恶意软件与其他软件没有什么不同

#16 楼

不，它尚未被证明，也不能被证明，因为它不是真的。实际上有效的防病毒程序只是运行时环境强制执行的合适的权限/访问控制模型。赖斯定理无关紧要，因为您不必提前确定程序是否安全。您只需在访问控制下运行它，然后在它试图做违反策略的操作时中止它（或拒绝访问）。如果progam是恶意的，则为肯定结果，但如果该程序不是恶意的，则可能不会停止。很好，因为测试正在运行该程序，并且只要它没有恶意，您就可以继续运行。它将与OS，运行时VM或类似组件集成在一起，而不是与单独的AV产品集成在一起）。相反，他们使用伪造的签名和启发式方法对程序进行分类。可以证明（参见其他答案）这种方法行不通。

#17 楼

我们可以拥有可以检测所有病毒的防病毒软件吗？

不需要数学。实验时间。让我们安排病毒库，尝试防御的系统库以及不断更改/改善双方的机制。

给他们一个星球。等待数十亿年。

我们还存在病毒吗？

对我来说，已经测试的各种可能性远远不能令人满意。

关于“证明”

在这里，我想解释为什么我彻底地重新定义了您的问题。

您问题的直接答案“在数学上证明了<陈述关于现实世界>”是：不，数学家从未证明过您关于现实世界的陈述（或任何其他此类陈述）。所谓真实世界，是指当您看着窗外时看到的那个世界。定义为无法证明）。我不知道统治真正计算机病毒的公理，所以我无法证明这些。

我会尝试预测现实，并且我会经常正确，确定。但是我将使用可证伪的理论，而不是证明。

#18 楼

我本人也同意纳吉。模型定理只能应用于形式逻辑的非常形式化的逻辑子集。我不知道可以基于某种形式的逻辑语法对现实的不完整性做出任何规定。在某些时候，这似乎是一个更大的哲学问题。也就是说，假设您可以具体描述病毒或恶意软件的含义，也就是可以将其表达为数学问题，然后确定可以将其显示出来。

计算机具有有限的资源。因此，通过蛮力可以考虑每个州，如果它是恶意的。

如果考虑到时间的状态组合，这可能会失败？我不能说自己。

#19 楼

或多或少，是的。用外行的话说，它背后的数学可以归结为Bootstrapping悖论，Bootstrapping悖论是一种时态悖论，它质疑信息的来源。与此相关的问题是，如果您拥有可以检测所有已知病毒的防病毒软件，但是第二天有人创建了新病毒，则旧病毒扫描中将没有签名来检测新病毒。如果可以想象到您可以将所有计算机病毒从某个时间段中清除掉，然后将其传播到现在之前，并从所有这些病毒中创建病毒签名，那么这些信息是从哪里来的？未来还是过去？由于普遍的共识是，出于多种数学/物理原因，不可能进行时间​​旅行，因此您无法覆盖所有病毒，而不能覆盖所有已知病毒。