再论“计算机病毒的不可判定性”

nkspark

本首席在这篇帖子http://bbs.kafan.cn/thread-867712-29-1.html里提到要专题讲一下病毒的识别，当时的想法是找时间讲讲SVM。现在还没备好课，只是简单的提一下我的观点：如果用垃圾邮件识别来类比的话，单个用户自用的SVM基本上是OK的（严格说，也不见得OK），所有用户共用SVM是不靠谱的。SVM用在病毒识别，作为对人工判别的辅助工具是可行的，单独作为引擎是扯淡的。当然本首席说的这些，99.9%的卡饭同学是理解不了的，等本首席备好课，再来细讲病毒的识别。


本次论题本首席要开讲的是当时随手搜到的链接，关于“计算机病毒的不可判定性”的.

先把链接内容直接转贴过来，大家学习过，本首席再开讲：
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
http://hi.baidu.com/jilule/blog/item/eb9ee8b43d26c7c237d3cae5.html
计算机病毒不可判定定理
2010年05月22日 星期六 下午 10:21

传统病毒定义是Fred Cohen博士1984年提出的，“计算机病毒是一种程序，它可以感染其它程序，感染的方式为在被感染程序中加入计算机病毒的一个副本，这个副本可能是在原病毒基础上演变过来的”。Cohen提出计算机病毒的模型，证明只要延用现行的计算机体系，计算机病毒就存在“不可判定性”。F·Cohen博士给出了如下简结的证明：假设能研究出一个检测程序D，对任何一个程序X。 D(X)=TRUE，X是病毒 D(X)=FALSE，X不是病毒 那么D无法判断以下程序V是不是病毒： PROCEDURE V： BEGIN： 1.IF NOT D(R) THEN GOTO 3； 2.GOTO 5； 3.传染一个可执行文件 4.若触发条件成立则执行破坏功能 5.正常功能； . . . END 这样，当D判断V是病毒时，V却不传染即V不是病毒，若D判断V是正常程序，V却执行病毒的功能，这与D的假设矛盾，即D是不可能编写出来的。 由于理论上的限制，不可能有一种完美无缺的，无条件病毒防治方法。Cohen的《计算机病毒的理论与实践》发表以后，从理论上计算机病毒是不可判定的这一结论已经被大家所接受。 国内外计算机安全理论界对计算机病毒的理论研究目前已经基本停止。受病毒在理论上就是不可判定的这一根本前提的制约，事实上，无论是启发式，亦或是虚拟机，都只能是一种工程学的努力，其成功的概率永远不可达到100％。

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


看到这些文字，恍惚之间本首席有一种感觉，这些文字仿佛出自本首席当年的手笔。

休谟八十多岁的时候，看到自己年青时写的文章，常常击节赞叹，却完全忘记了出自自己的手笔。本首席也常有这样的感觉，刚刚过去几天，看到论坛里的《云安全》系列讲座，不免击节赞叹，竟有如此妙文，不知出自哪位高人之手。可见遗忘乃是人生之常态。

不过关于Fred Cohen，本首席却还记得。国人有凡事抢第一的陋习，本首席也不能免俗。最早在国内提到Fred Cohen大名的，非本首席莫属。本首席可以和卡饭的同学打个赌，如果哪位同学能找到10年前国内有人提过Fred Cohen，证明不是本首席国内第一个提Fred Cohen，本首席直接把面前的显示器吃了。

当我们试图再论“计算机病毒的不可判定性”的时候, 首先要做的第一件事是要搞清楚Fred Cohen给出的结论所对应的前提。这可不是一件容易的事情。

很多时候，当我们断章取义的拿出一句话，常常会有这句话说得很荒谬的感觉。但还原这句话的全部场景，又常常发现，彼时彼刻，这句话说得恰当深刻，决不似当前感受的此时此刻。

当我们回到Fred Cohen的时代，发现的第一个现象是所有的问题都归结于图灵机模型。而Fred Cohen得出的计算机病毒的不可判定性的结论是图灵机是否停机的不可判定性的自然推导。

第二个需要注意的方面是，Fred Cohen讨论的是狭义的病毒。狭义的病毒具有两条基本特征，一是依赖宿主程序，二是传染性。

另外，也许Fred Cohen一开始就过分注意了“程序”和“用户”的不可区分性，潜意识里的“图灵测试”已经开始下了结论。

首先，我们已经看到，随着时代的发展，病毒这个概念已经大大扩展了，用来指代任何可能给用户造成危害和困扰的程序。有的研究者用“恶意代码”来指代这种泛概念下的病毒，但一般用户还是喜欢用病毒来指代。不论是啥，一律称之为病毒。

那么如何判断一个程序是不是病毒呢？本首席以前论述过，这其实不是技术决定的，而是市场决定的。当一个市场里的用户，对恶意性很敏感，那么这个市场里的反病毒厂商就倾向于扩大病毒的判定范围，以迎合用户的喜好，例如外-挂、keygen都可能判为病毒。同理，如果一个市场的用户，对恶意性不敏感，那么这个市场里的反病毒厂商就倾向于缩小病毒的判定范围，例如对keygen放行。如果有同学有闲心可以去调查一下，中外用户的喜好差异就很明显。这也是反病毒厂商在不同地域的查杀率不一样的根本原因，因为不同地域对应着不同的市场。

不管对一个程序是不是病毒由技术决定，还是由市场决定，当它被判定为病毒的时候，总是有一个标准存在那里的。这就明显和Fred Cohen提出的“病毒不可判定性”相矛盾。

回到Fred Cohen的“病毒的不可判定性”，完整地表述包含了攻防双方：
* 根据病毒的反馈来判定病毒，是不可判定的；
* 根据病毒的行为来判定病毒，是不可判定的；
* 病毒的变种是什么样的，是不可判定的；
* 根据杀软的反馈来判定杀软，是不可判定的；
* 根据杀软的行为来判定杀软，是不可判定的；
* 杀软的变种是什么样的，是不可判定的；

仔细考虑这些结论，可以看到，真正被判了死刑的，其实是某些仅仅依赖于病毒行为进行判断的“启发”和“主防”；

Fred Cohen对于“计算机病毒的不可判定性”的结论在他随后的研究工作中一直没有改变过。当然他原文中的表述也基本上是无懈可击的。大家慢慢都接受了Fred Cohen的结论，更深入的研究是对这个结论进行扩展和理论完善。质疑的声音几乎看不到，总之本首席刚刚又花了一分钟时间去确认，没找到反对这个结论的文章。毕竟图灵机描述起来是很复杂的，NP完全问题是迈不过去的，估计很多人想质疑也没有哪个勇气。

但是，且慢，大家在引用Fred Cohen关于“计算机病毒的不可判定性”的结论的时候：
1、是不是都忽略了这个结论的前提： “根据病毒的反馈（appearance）来判定病毒”？
2、是不是都默认了“杀软D(X)可被嵌入病毒”这个条件一定成立？

Fred Cohen认为，当我们去观察一个病毒的执行结果时，因为病毒有可能采用“观察者判断病毒”相同的逻辑，从而使得病毒的执行结果存在不确定性。

让我们来考察一下，反病毒业界是否是“根据病毒的反馈（appearance）来判定病毒”的呢？如果是这样的话，Fred Cohen的结论自然成立无虞，但真实情况是这样吗？(appearance这个词的大意是对病毒执行结果的观察)。

即使我们退一万步讲，Fred Cohen证明的也只是利用程序（杀软）来自动识别病毒时（在某些条件下）存在不可判定的问题，他没有说过“人识别病毒时存在不可判定性”。

Fred Cohen也曾试图证明“对人来说计算机病毒也是不可判定的”，但这时他没有办法把这种情况抽象成数学描述。于是只能用本首席最常用的例证法，Fred Cohen说人对病毒考察的所有工具都是不可信的，因为所有工具都肯能被病毒感染，从而输出不确定的结果。并给出了Ken Thompson的一个传奇故事作为例证。

本首席多年前也听说过Ken Thompson的类似传奇故事，说的是老Ken到上海访问，一个高级别的国家重点实验室，里面都是UNIX服务器，老Ken走到一台服务器前，用自己的名字登陆。所有陪同的人都等着看笑话，因为中国的服务器上不可能有老Ken的账号。奇迹出现了，老Ken顺利登入服务器，而且是超级用户权限。所有人傻眼。

但所有程序(不是说一台计算机,而是所有计算机)都被病毒感染的可能性是不存在的. 当我们假设计算机病毒存在智能,具有生物特性的时候, 那么计算机病毒的进化就自然而然要受到生物进化法则的制约. 而且计算机病毒的进化与真正的生物进化有本质的区别, 就是计算机病毒的进化在现阶段人工智能水平下, 无法脱离人的帮助而自动进行.

另外, Fred Cohen在论述“计算机病毒的不可判定性”时，还存在一个隐含的假设，那就是计算机病毒处在运行态。嗯，计算机病毒是活的。所以我们才面对一个对抗的局面。但实际上，计算机病毒在计算机、网络中，大部分时间是以数据的形式存在，形象地说，是死的，休眠态。也就是说，在感染、传播的过程中，也正是病毒最脆弱的时候。

所以，现在我们已经可以很确定的说，Fred Cohen给出的“计算机病毒是不可判定的”的结论，适用范围是非常有限的。不能作为反病毒业界在应对用户质疑要求改进反病毒技术时的推托借口。

到此本首席的《再论“计算机病毒的不可判定性”》已经接近尾声，本首席最初是打算全盘否定Fred Cohen的这个结论的，但深入分析后，也同意在特定条件下，这一结论是成立的。但通过上面的论述，可以看到，这个结论不是普适的，要求的假设和前提条件与实际情况重合度有限。

下面我们总结一下本文：
1、 Fred Cohen的“计算机病毒的不可判定性”是针对处在运行态的计算机病毒，指出仅仅凭借对计算机病毒的运行结果和行为来判断其是否是计算机病毒，是不可判定的；
2、对于以数据形态存在的计算机病毒，是否是可判定的，Fred Cohen没有给出结论，本首席也没看到任何人给出过结论。
3、本首席认为，以数据形态存在的计算机病毒是可判定的，本文没有给出证明，就以猜想的形式存在吧。

在大家关注Fred Cohen的“计算机病毒的不可判定性”的时候，往往都忽略了Fred Cohen同时说的另一段话，那就是“对于现实世界而言，没有哪个现存的病毒是不能被识别的，也没有哪个杀毒软件是不能被绕过的。杀软和病毒之间的对抗会一直存在下去。”

这段话其实本身也是对“计算机病毒的不可判定性”在某种意义上的一个否定吧。只是防病毒厂商在为自己不能实现100%查杀率进行辩护时，刻意忽略了“没有哪个现存的病毒是不能被识别的”这句话，仅仅强调“计算机病毒的不可判定性”。

本首席的《再论“计算机病毒的不可判定性”》对现实反病毒技术的指导意义：
1、在发展新技术时要尽量绕开Fred Cohen的“计算机病毒的不可判定性”成立的前提。也就是说，当你的技术是在计算机病毒活着（运行态）的前提下来判断一个程序是不是计算机病毒的时候，你已经败了。即使是让病毒部分运行、在可控环境下运行（VM、沙箱、主防等等），你也无法保证判断的准确性。
2、如果一定要采用让程序运行再判断的技术方式，那么对杀软的自身防护就成为查杀的关键。Fred Cohen的“计算机病毒的不可判定性”成立的条件之一是病毒对杀软（D(X)）判断逻辑的调用。如果杀软的自身防护做的足够好，那么可以在某种程度上破坏这个成立条件。
3、静态分析因为不涉及到Fred Cohen的“计算机病毒的不可判定性”成立的前提，所以应该是防病毒厂商依赖的主要病毒识别技术，尽管此路也是困难重重。

(全文完)

seehere

等文章写好了再改成  原创 标签吧。否则被扣分了。

nkspark

seehere 发表于 2011-4-4 11:03
等文章写好了再改成  原创 标签吧。否则被扣分了。

谢谢建议。

本首席在边写边改，如果不及时保存，卡饭的帖子编辑框有Bug，一个自动刷新，本首席的文字就没了。

小紫英

首先，我们应该看到：
1、不考虑误报时，100%查杀率是很容易实现的；

首席你何必来回自抽，伤不起啊

nkspark

休谟八十多岁的时候，看到自己年青时写的文章，常常击节赞叹，却完全忘记了出自自己的手笔。本首席也常有这样的感觉，刚刚过去几天，看到论坛里的《云安全》系列讲座，不免击节赞叹，竟有如此妙文，不知出自哪位高人之手。可见遗忘乃是人生之常态。

不过关于Fred Cohen，本首席却还记得。国人有凡事抢第一的陋习，本首席也不能免俗。最早在国内提到Fred Cohen大名的，非本首席莫属。本首席可以和卡饭的同学打个赌，如果哪位同学能找到10年前国内有人提过Fred Cohen，证明不是本首席国内第一个提Fred Cohen，依照惯例，本首席直接把面前的显示器吃了。

你想怎样

惯例 ?   

惯例是啥意思啊 ?

以前吃过吗 ?

byxxdrls

作为小白，认同病毒不可能百分百被识别（从总体来讲），局部可以达到百分百。

evolution1240

您是虾扑瘟能吗

122693882

手洗  威武啊  

fishack

不懂。。。