INFINITE LOOP DETECTION

INFINITE LOOP DETECTION

CHALLENGE

Infinite loop bugs are both an issue of software safety and of software security. A program that runs into an infinite loop becomes unresponsive, which violates safety properties. If an infinite loop can be triggered with program input by an attacker, the program is vulnerable to a denial of service attack. Under the common weakness enumeration, infinite loops are known as CWE-835 (‘loop with unreachable exit condition’). The problem of finding infinite loops in programs is as old as computing itself. A perfect bug checker would detect all infinite loops in any program without false negative detections, without false positive detections, and with bounded runtime. Because the Halting Problem is known to be undecidable in general, such a perfect bug checker cannot exist. Any real detection algorithm must therefore drop at least one of the three properties and tolerate either false positive detections, false negative detections, or running into non-termination itself.

INNOVATION

This invention presents a new algorithm for automated detection of infinite loops. It is sufficiently lightweight to be applied continuously at runtime. It does not need constraint solver, program source code or hash values over program states. The algorithm is based on autocorrelation, a computation commonly used in many areas of applied statistics. The algorithm can be implemented in hardware or software. Source code is not needed. The algorithm is based on autocorrelation of a program execution’s branch target address sequence. We describe the implementation of the algorithm in a dynamic binary instrumentation tool (1).

COMMERCIAL OPPORTUNITIES

  • Hardware or software implemented infinity loop detection
  • The invention applies autocorrelation as an efficient way to identify suspicious branch sequences on-the-fly
  • Improves savety and security

DEVELOPMENT STATUS

Functionality of the tool is evaluated with infinite loop bug test cases from the Juliet test suite for program analyzers. Applicability of the algorithm to production software is demonstrated by using the tool to detect previously known infinite loop bugs in cgit, Avahi and PHP.

Figure: Triangular coefficient matrix (left). Correlation detects re-visited branches with constant branchsequence length (right)

REFERENCE

(1) Ibing, A., J. Kirsch, and L. Panny. Autocorrelation-Based Detection of Infinite Loops at Runtime. In IEEE Int. Conf. Dependable, Autonomic and Secure Computing, August 2016

Dr. Tobias Steinel
E-Mail:
Reference Number:
Phone:
tsteinel@baypat.de
B76069
+49 (0) 89 5480177 - 39