This post is about halting problem, infinite loops and their detection in FindBugs^TM. The initial inspiration to write it was Tom Stuart’s presentation “Impossible Programs” from QCon London 2014 Conference and further investigation of the mentioned issues. In the beginning there are introduced basic terms and then is the practical part with Java code snippets with the FindBugs analysis outcome.

1. Infinite loops

This is a kind of loop which never finishes. Infinite loops are in most cases bad. They are often unexpected. This may happen for example when a logical condition is incorrect or when a certain resource is missing. In case when they are introduced intentionally, for example in listeners, they should be design with a special care. This article considers them as a bad thing. More information can be found on Wikipedia [1].

2. Halting problem

The problem, generally speaking is about deciding whether an arbitrary program finishes or runs forever. More information regarding this issue is available on Wikipedia [2]. There is also a funny movie on youtube [3], posted below and “Impossible Programs” presentation [4]. The problem addresses case of running program forever. This is just about infinite loops introduced in previous section.

3. FindBugs

There are some tools to static code analysis. One of them which is well known in Java world is FindBugs [5]. This is an advanced tool coming from The University of Maryland. The tool can be run on CIs (Jenkins, Hudson), from command line, GUI, ant, maven and IDEs (Eclipse, Netbeans, IntelliJ). For current purposes it is run in Eclipse.

Because halting problem is undecidable, there is no possibility to design such an algorithm to solve it and in consequence it is not possible to implement it. In other words, program which implements function like halts is an impossible program. To answer necessary questions about an application the only way is to evaluate interested cases. It can be done through manual or automated tests performed on a running system. However, the dynamic evaluation could be preceded by a static code analysis. The purpose of the analysis is to find potential defects in code. This post takes care of infinite loops.

3.1. FindBugs in eclipse

Follow instructions given on [6] to install FindBugs in eclipse.

After installation, the tool can be configured in a project’s context (see Figure 1).

Figure 1: Configuration

To execute the tool on a certain project see Figure 2.

Figure 2: Execution

Executions results are available in the dedicated FindBugs perspective (Figure 3).

Figure 3: Outcome

3.2 Analyzing loops with FindBugs

In this part there are analyzed some loops using FindBugs. There is prepared project com.softexploration.loops with following classes: SimpleLoops, RecursiveLoops and Halting. The *Loops classes contain static methods with a purpose to observe static analysis behaviour. The FindBugs is performed on the whole project. Outcome of each class’s methods is analyzed in separate sections.

The complete source code is available on [7].

3.2.1. SimpleLoops

package com.softexploration.loops;

import java.util.Scanner;

public class SimpleLoops {

	public static void main(String[] args) {

		alwaysLoops();
	}

	public static void alwaysLoops() {
		while (true) {
			// do nothing
		}
	}

	public static void alwaysLoopsVar() {
		boolean always = true;
		while (always) {
			// do nothing
		}
	}

	public static void alwaysLoopsFinalVar() {
		final boolean always = true;
		while (always) {
			// do nothing
		}
	}

	public static void neverLoops() {
		final boolean isNull = "string" == null;
		while (isNull) {
			// do nothing
		}
	}

	/**
	 * Loops when reads on input value compatible with Boolean.TRUE
	 */
	public static void somtimesLoops() {
		final boolean input = Boolean.valueOf(new Scanner(System.in).next());
		while (input) {
			// do nothing
		}
	}

}

Figure 4: SimpleLoops

Bug: There is an apparent infinite loop in com.softexploration.loops.SimpleLoops.alwaysLoopsVar()

This loop doesn't seem to have a way to terminate (other than by perhaps throwing an exception).

Rank: Scary (8), confidence: High
Pattern: IL_INFINITE_LOOP 
Type: IL, Category: CORRECTNESS (Correctness)

Bug: There is an apparent infinite loop in com.softexploration.loops.SimpleLoops.neverLoops()

This loop doesn't seem to have a way to terminate (other than by perhaps throwing an exception).

Rank: Scary (8), confidence: High
Pattern: IL_INFINITE_LOOP 
Type: IL, Category: CORRECTNESS (Correctness)

Bug: There is an apparent infinite loop in com.softexploration.loops.SimpleLoops.somtimesLoops()

This loop doesn't seem to have a way to terminate (other than by perhaps throwing an exception).

Rank: Scary (8), confidence: High
Pattern: IL_INFINITE_LOOP 
Type: IL, Category: CORRECTNESS (Correctness)

3.2.2. RecursiveLoops

package com.softexploration.loops;

public class RecursiveLoops {

	public static void main(String[] args) {
		h(false);
	}

	public static void f() {
		f();
	}

	public static boolean g() {
		if (g()) {
			return true;
		} else {
			return g();
		}
	}

	public static boolean h(final boolean in) {
		if (in) {
			h(!in);
		}
		return false;
	}

	public static int fibonacci(int n) {
		if (n < 2) {
			return n;
		} else {
			return fibonacci(n - 1) + fibonacci(n - 2);
		}
	}
}

Figure 5: RecursiveLoops

Bug: There is an apparent infinite recursive loop in com.softexploration.loops.RecursiveLoops.f()

This method unconditionally invokes itself. This would seem to indicate an infinite recursive loop that will result in a stack overflow.

Rank: Scary (9), confidence: High
Pattern: IL_INFINITE_RECURSIVE_LOOP 
Type: IL, Category: CORRECTNESS (Correctness)

Bug: There is an apparent infinite recursive loop in com.softexploration.loops.RecursiveLoops.g()

This method unconditionally invokes itself. This would seem to indicate an infinite recursive loop that will result in a stack overflow.

Rank: Scary (9), confidence: High
Pattern: IL_INFINITE_RECURSIVE_LOOP 
Type: IL, Category: CORRECTNESS (Correctness)

3.2.3. Halting

package com.softexploration.loops.halting;

public class Halting {

	public static void main(String[] args) {
		Halting halting = new Halting();

		if (halting.halts(args[0])) {
			while (true) {
				// do nothing
			}
		}
	}

	public boolean halts(String program) {
		return Boolean.valueOf(program);
	}
}

Figure 6: Halting

Summary

We can observe that when a variable is specified with the final modifier then FundBugs assumes that we are aware of the assigned value. On the other hand, such a value in many cases can be resolved at compile time (FindBugs operated on byte code). In case when a variable is not final and has/hasn’t  chance to be modified the result is a potential bug. Basing on researched cases, when a loop condition is specified with a boolean non-final variable or expressions with non-final variables then a bug is reported.

Resources

[1] http://en.wikipedia.org/wiki/Infinite_loop

[2] http://en.wikipedia.org/wiki/Halting_problem

[3] Proof That Computers Can’t Do Everything (The Halting Problem)

[4] Tom Stuart’s Presentation: “Impossible Programs”

[5] http://findbugs.sourceforge.net/index.html

[6] http://findbugs.sourceforge.net/manual/eclipse.html

[7] https://github.com/softexploration/com.softexploration.loops