预测程序崩溃

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 Cuoq 说你会因为这样做而赢得诺贝尔奖和菲尔兹奖时，他们是认真的。

Answer 3

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

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

理论上说这是不可能的，假设你想要的东西既是声音又是完整。在实践中，你可以同时放弃健全性和完整性，只要你的误报率不太糟糕，并且会有客户排队购买你的产品。

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

编辑亚历克斯的评论
我会走数学家的捷径，并说既然最初的问题是“是否可能”，那么几种可行的商业产品的存在证明答案是“是”。使用商业软件可能产生的经济依赖性超出了最初问题的范围。