Analyzing and Disentangling Interleaved Interrupt-driven IoT Programs

Yuxia Sun, Song Guo, Shing-Chi Cheung, Yong Tang

Introduction

Wireless Sensor Networks (WSNs) form the backbone of the Internet of Things (IoT), but their programming model presents unique challenges. Unlike traditional software, WSN applications are heavily interrupt-driven. When an event occurs, such as a sensor reading, an interrupt handler runs immediately and often "posts" additional tasks to be executed later by a scheduler.

This execution model causes a single logical event—referred to as an Interrupt Procedure Instance (IPI)—to become fragmented and interleaved with other instances. As illustrated in Figure 1, this creates a complex "spaghetti" of execution traces that are nearly impossible to predict or analyze using standard methods from source code alone.

Interleaved execution traces of Interrupt Procedure Instances (IPIs).

The Challenge of Real-time Identification

Existing analysis tools often struggle with these interleaved traces. Many assume that task-posting is an atomic operation or require "rolling back" analysis because they cannot identify the end of an execution instance in real-time. This leads to high memory overhead and makes long-term monitoring of IoT devices impractical. The fragmentation of IPIs across multiple preemptions and deferred tasks necessitates a more robust identification mechanism.

Methodology: Real-time IPI Identification

The researchers propose a novel, generic IPI-identification algorithm designed to run at the instruction level. The core innovation lies in tracking five key execution points:

  1. IHEntry/IHExit: The start and end of an interrupt handler.
  2. RunTaskEntry/RunTaskExit: The start and end of a scheduled task.
  3. PostOk: A critical point indicating a task was successfully added to the system queue, even if the posting operation itself was interrupted.

To manage the complexity of nested interrupts and deferred tasks, the algorithm uses a global stack to track preempted IPIs and a global queue to map tasks back to their originating IPI. Unlike previous methods, this approach identifies the boundaries of an IPI immediately as they occur.

Evaluation and Results

The algorithm was evaluated using classic WSN applications (Oscilloscope, TestBlink, and TestCTP) on the TinyOS platform via the Avrora cycle-accurate simulator.

A key finding is that IPI identification can be achieved with $O(1)$ time and space complexity per instruction. Because interrupt nesting depth and task queue sizes are small constants in typical IoT systems, the algorithm's overhead remains flat over time. In contrast, existing state-of-the-art tools show memory and time overhead that increases significantly as the program execution continues.

Comparison of memory usage (space overhead) between the proposed algorithm and existing methods over time.

Conclusion

By providing a real-time, constant-overhead identification layer, this work enables the development of more effective debugging, profiling, and testing suites for WSNs. Decoupling the identification of execution instances from the analysis itself allows researchers to build diverse tools—such as bug detectors or performance profilers—without needing to manage the intricacies of interrupt interleaving. Future work will focus on using this foundation to identify specific IPI-based bug patterns in IoT deployments before they reach the field.

Summary updated

BibTeX
@article{sun2019analyzing,
  author = {Yuxia Sun and Song Guo and Shing-Chi Cheung and Yong Tang},
  title = {{Analyzing and Disentangling Interleaved Interrupt-driven IoT Programs}},
  journal = {IEEE Internet of Things Journal},
  year = {2019},
  doi = {10.1109/jiot.2019.2900769},
}
Figure