Jen*_*ens 7 c c++ pointers static-analysis halting-problem
我并没有深入根植于静态代码分析的正式方面,因此这个问题.
几年前,我读到使用静态代码分析区分代码和数据等同于暂停问题.(引用需要,但我不再拥有它了.Stackoverflow在这里或这里有线程.)至少对于基于冯诺依曼架构的常见计算机架构,其中代码和数据共享相同的内存,这似乎是有意义的.
现在我正在研究C/C++代码和指针分析的静态分析; 该程序不执行.不知怎的,我有一种感觉,静态跟踪指针值的所有创建和使用类似于停止问题,因为我无法确定内存中的给定值是否是指针值,即我无法通过指针值跟踪指针值的值记忆. 别名分析可能会缩小问题范围,但面对多线程代码似乎变得不那么有用了.
(人们甚至可以考虑跟踪任意值,而不仅仅是指针:为任何给定的"有趣"值构建一个完整的值流似乎等同于停止问题.)
由于这只是一种预感,我的问题是:我可以参考更正式的发现吗？我错了吗？
它几乎肯定是等价的，以 C 不是图灵等效语言这一事实为模（由于类型的表示，给定的 C 实现是一个巨大的有限状态机而不是图灵机）。在有效类型为指针类型的对象中，指针不需要保留其原始表示形式；您可以检查表示形式并对其执行任意操作，例如，加密指针并稍后解密。确定任意计算是否可逆，或者两个计算是否彼此相反，（即兴）可能相当于确定停止。