使用静态字节码分析来确定通过给定方法的所有可能路径是否是尝试解决停止问题的一种方法？ [英] Is using static bytecode analysis to determine all the possible paths through a given method a variant of trying to solve the Halting Problem?

问题描述

是否可以通过读取给定方法的字节码来确定所有可能的执行路径，或者这等同于尝试解决暂停问题？如果不能将其简化为停工问题，那么我可以走静态分析多远而又不试图解决停工问题？

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?

相关问题： ；在给定的二进制文件中查找所有代码等同于停止问题。真的吗？

推荐答案

是的，这很容易解决停止问题。考虑以下if语句：

Yes, this is easily equivalent to solving the halting problem. Consider the following if statement:

如果（TuringMachine（x））then goto fred;

if (TuringMachine(x)) then goto fred;

OK，是真的有可能去弗雷德吗？如果您可以分析图灵机，则只能回答此问题。
有一个等效的字节码集。

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:

if (false) then x else y ;

可能的路径：eval（false）; x和eval（false）; y是一个完整的枚举。

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 :-{

这篇关于使用静态字节码分析来确定通过给定方法的所有可能路径是否是尝试解决停止问题的一种方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！