static-analysis - 使用静态字节码分析来确定通过给定方法的所有可能路径是否是尝试解决停机问题的变体？

Question

是否可以通过读取给定方法的字节码来确定所有可能的执行路径，还是等同于尝试解决停机问题？如果不能将其简化为停机问题，那么在不跨越尝试解决停机问题的边界的情况下，静态分析能走多远？

相关问题:"Finding all the code in a given binary is equivalent to the Halting problem." Really?

Answer 1

是的，这很容易等同于解决停机问题。考虑以下 if 语句:

if (TuringMachine(x)) then goto fred;

好的，真的可以转到 fred 吗？如果你能分析图灵机，你才能回答这个问题。为此有一组等效的字节码。

现在，如果唯一的问题是确定所有似是而非的路径，并且您不关心是否得到一些误报，那么答案是否定的。考虑以下程序:

if (false) then x else y ;

可能的路径:eval(false);do x 和 eval(false);do y 是一个完整的枚举。

如果您想要一个可计算的答案，您必须特别对待循环，将其视为零、一、二或某个最大有界迭代次数。如果一个循环可以永远重复，你的一些路径将无限长，你不能用算法和有限的时间报告它们:-{