使用静态字节码分析来确定通过给定方法的所有可能路径是尝试解决停止问题的一种变体吗？
是否可以通过读取给定方法的字节码来确定所有可能的执行路径，或者这是否相当于尝试解决暂停问题？如果不能将其简化为停机问题，那么在不跨越尝试解决停机问题的边界的情况下，静态分析能走多远？
Is it possible to determine all the possible execution paths by reading the bytecode of a given method, or will that be equivalent to trying to solve the halting problem? If it can't be reduced to the halting problem, then how far can I go with static analysis without crossing the boundary of trying to solve the halting problem?
Related question: "Finding all the code in a given binary is equivalent to the Halting problem." Really?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
是的，这很容易等同于解决停机问题。考虑以下 if 语句：
if (TuringMachine(x)) then goto fred;
好吧，真的可以去找 Fred 吗？只有能够分析图灵机才能回答这个问题。
为此有一组等效的字节码。
现在，如果唯一的问题是确定所有看似合理的路径，并且您不关心是否会得到一些误报，那么答案是否定的。考虑以下程序：
可能的路径： eval(false );do x 和 eval(false);do y 是一个完整的枚举。
如果您想要一个可计算的答案，则必须将循环特殊对待，如零次、一次、两次或某个最大有界迭代次数。如果循环可以永远重复，那么您的某些路径将无限长，并且您无法使用算法和有限时间来报告它们：-{
Yes, this is easily equivalent to solving the halting problem. Consider the following if statement:
if (TuringMachine(x)) then goto fred;
OK, is it really possible to goto fred? You can only answer this question if you can analyze a Turing machine.
There's an equivalent set of bytecodes for this.
Now, if the only problem is to determine all plausible paths, and you don't care if you get some false positives, the answer is No. Consider the following program:
The possbile paths: eval(false);do x and eval(false);do y is a complete enumeration.
You have to treat loops specially, as zero, one, two, or some maximum bounded number of iterations, it you want a computable answer. If a loop can repeat forever, some of your paths will be infinitely long and you can't report them with a algorithm and finite time :-{