Infinite loop detection

The tremendous rise in real-world implementations of cyber-physical systems, for example in the context of the industrial internet of things (IIOT) and advanced driver-assistance systems (ADAS), is accompanied by an explosion in the number of sensors continuously monitoring the physical environment. These sensors are often implemented as embedded systems with some initial processing taking place at the sensor, leading to the name intelligent sensors. The constant availability of these sensors is of the utmost importance. Thus, infinite loop bugs are both an issue of safety and of security, as a program that runs into an infinite loop becomes unresponsive, a phenomenon exploited in a denial of service attack.

While the problem of finding infinite loops in programs is as old as computing itself, the potential consequences of not being able to perform in-line detection of infinite loops become increasingly dire, as the proliferation of cyber-physical systems increases. Furthermore, these embedded systems are often strongly constraint in their computational complexity in order to limit fabrication cost and power consumption.

This invention presents a new algorithm for automated detection of infinite loops. It has sufficiently low computational complexity 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 an autocorrelation measure, commonly used in many areas of applied statistics, here calculated on a program execution’s branch target address sequence¹. The algorithm can be implemented in hardware or software. Modification of existing source code is not required.

The invented method can find application in all types of embedded systems, especially when heightened security and safety concerns are combined with constraints on the locally available computational resources. Some use cases include:

• IIOT, i.e. industry 4.0
• Autonomous vehicles

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.