7

我并不太深植于静态代码分析的非常正式的一面，因此这个问题。

几年前，我读到使用静态代码分析将代码与数据区分开来等同于停机问题。（需要引用，但我没有了。Stackoverflow 在此处或此处有线程。）至少对于基于Von Neumann 架构的常见计算机架构，其中代码和数据共享相同的内存，这似乎是有道理的。

现在看C/C++代码的静态分析和指针分析；程序不执行。不知何故，我有一种感觉，静态跟踪指针值的所有创建和使用类似于停止问题，因为我无法确定内存中的给定值是否是指针值，即我无法通过以下方式跟踪指针值的值流记忆。 别名分析可能会缩小问题的范围，但在面对多线程代码时它似乎变得不那么有用了。

（甚至可以考虑跟踪任意值，而不仅仅是指针：为任何给定的“有趣”值构造一个完整的值流似乎等同于停止问题。）

由于这只是一种预感，我的问题是：我可以参考更正式的发现吗？我弄错了吗？

4

4 回答 4

3

您可以随时编写代码：

extern bool some_program_halts();
extern int* invalid_pointer();

#include <iostream>
int main()
{
    using namespace std;
    if( some_program_halts() ) { cout << *invalid_pointer() << endl; }
}

检查这个程序是否取消引用无效指针相当于找出调用some_program_halts()，呃，是否停止。

于 2013-12-30T23:11:37.090 回答
1

它几乎肯定是等效的，以 C 不是图灵等效语言的事实为模（由于类型的表示，给定的 C 实现是一个巨大的有限状态机而不是图灵机）。在有效类型为指针类型的对象中，指针不需要保持其原始表示；您可以检查表示并对其执行任意操作，例如，加密指针并稍后解密它们。确定任意计算是否可逆，或者两个计算是否彼此相反，可能（临时）等同于确定暂停。

于 2013-12-30T23:01:38.573 回答
0

如果我理解正确：是的，检查 C 或 C++ 程序是否访问无效指针等同于停止问题（在任何情况下都是 C 或 C++ 程序的）。

假设您有一个工具可以告诉您程序是否访问了无效指针，以及您想要检查是否停止的程序。通过向每个指针添加额外信息，您可以（在运行时）检查指针是否有效；添加此类检查，失败时无限循环。您现在有一个没有无效指针访问的程序。通过替换程序可以以无效指针访问终止的所有位置，当且仅当原始程序终止时，您将获得一个具有无效指针访问的程序。

于 2013-12-30T23:05:07.673 回答
0

静态分析几乎总是一种近似值，通常可以通过使用Alf 回答中的程序减少停止问题来证明。但是，近似值可能会在误报或误报方面出错。

  • “保守”的静态检查只会有假阴性。它永远不会接受一个“坏”的程序，但它不可避免地会拒绝一些“足够复杂”的好程序。
  • “自由”的静态检查会有误报。有时它会错误地接受一个坏程序，但（通常）它也会接受所有好的程序。

一些例子：

  • Java 的类型系统是保守的：具有类型的变量无论如何T都会在运行时包含类型的实例T（或子类型或 null）。T
  • GCC 警告未初始化变量的选项是自由的：它没有找到未初始化变量的所有潜在用途。这是一个误报程序的示例。
  • 相反，Java 对局部变量进行保守的未初始化变量检查。如果它看到任何使用潜在未初始化变量的潜在执行路径，它将拒绝编译程序。

编译器和外部静态分析工具经常使用自由检查来发出警告。诸如类型系统和编译器优化之类的事情往往依赖于保守的检查是正确的。

许多任务有几种不同精度的合理保守和自由算法。别名分析当然就是其中之一。

有关更多信息，请参阅任何好的编译器教科书，例如dragon book。

于 2013-12-31T22:47:05.410 回答