预期程序崩溃

Question

我正在编写一个程序，它应该能够判断我在计算机上运行的任何程序是否会崩溃。

大概可以在机器代码中读取、建立潜在代码路径的模型、测试每个代码路径在标准和边界条件下的行为、映射导致未处理异常的条件，然后追溯所有这些步骤以生成所需的设置输入和条件，这些条件将触发要采取的异常代码路径。这就像使用模糊调试器，只是更有条不紊。当然，这是一个很大的工作量，但它应该非常迅速地在现代硬件。

一位同事说我想做的事根本不可能。对我来说有点极端。鉴于摩尔定律的技术发展曲线，无法达到的计算能力最终将成为现实--最终。如果说这样的事情永远不可能发生，那似乎有点夸张了。

为什么不能这么做？

Answer 1

以下是一个程序：

accept integer i greater than 2
loop with k from 2 to 2*i
  is k prime?
    is 2*i-k prime?
      exit safely
end loop
do something nasty.

如果您跟踪导致这个程序做一些讨厌的事情的输入，您已经解决了戈德巴赫猜想。你可以在诺贝尔奖的同时领取菲尔兹奖章。

这就是说，有可能验证一些程序不会做任何讨厌的事情。我和其他人正在研究一种框架，您可以在这个框架中使用各种技术来做到这一点。。下面是一些例子：

这个压缩库可能会显示输入大小为20、输出大小为40的内存错误，但现在不会了。

这种二进制搜索可能会失败，但现在不会了。

Answer 2

这是计算和数学的圣杯之一，被称为Entscheidungsproblem问题。你解决不了这个问题。这两个领域里最聪明的人花了很多年在这上面，证明了它是无法解决的。当nbt和Pascal说你会因此获得诺贝尔奖和菲尔兹奖时，他们真的是认真的。

Answer 3

大概可以在机器代码中读取、建立潜在代码路径的模型、测试每个代码路径在标准和边界条件下的行为、映射导致未处理异常的条件，然后追溯所有这些步骤以生成所需的设置输入和条件，这些条件将触发要采取的异常代码路径。

是的，这是有可能的，不管理论上的人怎么说。有许多公司销售的产品与您所描述的完全一样，其中包括Vericode、Coverity、Fortify、Klocwork和Grammatech。

理论上说，假设你想要的是声音和完成，这是不可能的。在实践中，只要你的假阳性率不算太坏，你就可以降低产品的可靠性和完整性，而且你会有顾客排队购买你的产品。

一旦你放弃了可靠性和完全性，不可能定理就不再成立，你就进入了更像工程而不是理论的东西。

编辑，亚历克斯的评论

我将以数学家为捷径，说既然原来的问题是“它有可能”，那么几种可行的商业产品的存在证明答案是“是的”。使用商业软件可能产生的经济依赖超出了最初问题的范围。