Can a runtime environment detect an infinite loop?

Question

Would it be possible for a runtime environment to detect infinite loops and subsequently stop the associated process, or would implementing such logic be equivalent to solving the halting problem?

For the purpose of this question, I define an "infinite loop" to mean a series of instructions and associated starting stack/heap data that, when executed, return the process to exactly the same state (including the data) as it was in before initiating the infinite loop. (In other words, a program generating an indefinitely long decimal expansion of pi isn't "stuck" in an "infinite loop," because at every iteration, it has more digits of pi somewhere in its associated memory.)

(Ported from https://stackoverflow.com/q/16250472/1858225)

Answer 1

It might be theoretically possible for a runtime environment to check for such loops using the following procedure:

After ever instruction executed, the runtime environment would make a complete image of the state of a running process (i.e. all memory associated with it, including registers, P.C., stack, heap, and globals), save that image somewhere, and then check to see whether it matches any of its previously saved images for that process. If there is a match, then the process is stuck in an infinite loop. Otherwise, the next instruction is executed and the process is repeated.

In fact, rather than performing this check after every single instruction, the runtime environment could simply pause the process periodically and make a save-state. If the process is stuck in an infinite loop involving n states, then after at most n checks, a duplicate state will be observed.

Note, of course, that this is not a solution to the halting problem; the distinction is discussed here.

But such a feature would be an enormous waste of resources; continually pausing a process to save all memory associated with it would slow it down tremendously and consume an enormous amount of memory very quickly. (Although old images could be deleted after a while, it would be risky to limit the total number of images that could be saved because a large infinite loop--i.e., one with many states--might not get caught if there are too few states kept in memory.) Moreover, this feature wouldn't actually provide that much benefit, since its ability to catch errors would be extremely limited and because it's relatively simple to find infinite loops with other debugging methods (such as simply stepping through the code and recognizing the logic error).

Therefore, I doubt that such a runtime environment exists or that it will ever exist, unless someone programs it just for kicks. (Which I am somewhat tempted to do now.)

Answer 2

Let's assume that the program does not interact with the outside world, so that's it's really possible to encapsulate the entire state of the program. (This means it does not do any input, at least.) Furthermore, let's assume that the program is running in some deterministic environment so that each state has a unique successor, which means that the runtime is either not threaded, or that the threading can be deterministically reduced to a sequence.

Under these highly improbable but theoretically non-limiting assumptions, we can duplicate the program and run it in two separate runtimes; each will do exactly the same computation.

So let's do that. We'll run it once in the Tortoise runtime, and at the same time we'll run it in the Hare runtime. However, we'll arrange for the Hare runtime to operate exactly twice as fast; every time the Tortoise runtime makes one step, the Hare runtime makes two steps.

Now we can (theoretically) compare the states after every step of the Tortoise runtime. If the program reaches an endless loop of $n$ steps after some non-looping prefix of $p$ steps, then the Hare and Tortoise states will be identical at every Tortoise step $kn$ for any integer $k$ where $kn\ge p$.

The total cost of the test is one extra state and one state comparison per step, and it will terminate in no more than three times the number of steps it takes for the program to complete its first loop. (One time in the Tortoise and twice in the Hare, for a total of three times.)

As the terms I used imply, this is just Robert Floyd's famous Tortoise and Hare cycle-detection algorithm.

Answer 3

Just as I was going to suggest Floyd's cycle-detection algorithm, rici's post beat me to it. However, the whole thing can be made more practical by speeding up comparisons of full states.

The bottleneck of the proposed algorithm would be in comparing full state. These comparisons will usually not finish, but stop early --- at the first difference. One optimization is to remember where the past differences occurred, and check those parts of the state first. For example, maintain a list of locations, and go through this list before making a full comparison. When a location from this list exposes a difference, stop the comparison (with failure), and move the location to the front of the list.

A different (and potentially more scalable) approach is to use incremental hashing. Pick a function of the full state such that the hash values are easy to adjust in O(1) when some part of the state changes. For example, take a weighted sum of state words mod some large prime and concatenate with the unweighted sum mod some other large prime (can also throw in a modular weighted sum of squares of words, with different weight and modulus). This way, hash updates will take O(1) time on each execution step, and comparisons will take O(1) time until you get a hit. The probability of a false positive (i.e., the hashes match while the states differ) is very low, and even if this ever happens, it will amortize over a large number of true negatives (false negatives are impossible).

Of course, in practice, it seems more likely to get into situations like generating digits of the number pi --- things keep on changing, but never end. Another frequent possibility is that the infinite loop allocates memory, in which case it quickly exhausts all available memory.

In my course on algorithms and data structures, our autograder has to deal with student submissions that sometimes get into infinite loops. This is taken care of by a 30-second time-out and a certain memory limit. Both are much looser than runtime and memory budgets we impose as part of grading. I am not sure if implementing true infinite-loop detection would make a lot of sense in this context because such programs will run quite a bit slower (this is where hardware support for state hashing could help, but again you'd need additional uses to justify this). When students know that their program timed out, they can usually find the infinite loop.

Answer 4

The AProVE termination tool performs static analysis on rewrite systems (including a subclass of Haskell programs) which can prove non-termination, giving an actual example of non-terminating program. The technique is quite powerful and works using a variant of a technique called narrowing.

As far as I know though, there has not been much work on detecting actual non-termination for general languages.

Answer 5

There is an efficient way of detecting infinite loop, with no practical drawbacks (even if it is impossible in theory):

Let's says you have a cryptographic hash function like sha256, delivering a 256 bit's "imprint" of whatever input you give, with a probability of collision of 2^-128 (due to birthday problem).

Let's use an integer counter of 128 bits. here is the detection method:

let's says we have a pure function new_state=f(state); (aka new_state depends only of state). also we have a function bool stop(state);

one can detect that repeated f will end up as an infinite loop (halting problem) like this (C++ code):

uint128 counter=0;
auto current_hash = sha256(current_state);
auto sample = current_hash;
while(not stop(current_state)) {
  current_state = f(current_state); 
  current_hash = sha256(current_state);
  if (current_hash == sample)
     break; // infinite loop detected and avoided
  if (0 == ++counter)
     break; // failed detection, after 3e+38 =2^128 iterations.. past end of our universe
  if (0 == (counter & (counter+1))) // counter is a power of 2 -1
    sample = current_hash;
}

Note that does not really solve the theoretic halting problem:

• hash is only stochastic
• integer may be too small for loop size
• some never ending programs may not become periodic as they may grow the state with no limit.

But it never occurs for regular programs.

Answer 6

You can use the same algorithm as for cycle detection in linear lists: Use two copies of your machine, one executing two steps per cycle, the other executing one step per cycle. If you enter two identical states, then you are in a loop. If you never enter two identical states, which could happen for an infinite Turing machine, then you don't know whether you are in a cycle. You might be able to add a clever AI that will be able to find a loop through some cleverness in some cases, but it won't work in all cases. And if the program halts, then you know that.

Summary: Very easy mechanical solution that works for some cases. High cleverness that works for other cases. Nothing that works for every possible program.