INFINITE LOOP DETECTION
Inﬁnite loop bugs are both an issue of software safety and of software security. A program that runs into an inﬁnite loop becomes unresponsive, which violates safety properties. If an inﬁnite 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, inﬁnite loops are known as CWE-835 (‘loop with unreachable exit condition’). The problem of ﬁnding inﬁnite loops in programs is as old as computing itself. A perfect bug checker would detect all inﬁnite 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.
This invention presents a new algorithm for automated detection of inﬁnite loops. It is sufﬁciently 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).
- Hardware or software implemented inﬁnity loop detection
- The invention applies autocorrelation as an efﬁcient way to identify suspicious branch sequences on-the-fly
- Improves savety and security
Functionality of the tool is evaluated with inﬁnite 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 inﬁnite loop bugs in cgit, Avahi and PHP.
(1) Ibing, A., J. Kirsch, and L. Panny. Autocorrelation-Based Detection of Inﬁnite Loops at Runtime. In IEEE Int. Conf. Dependable, Autonomic and Secure Computing, August 2016