Analyzing and Disentangling Interleaved Interrupt-Driven IoT Programs

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

TL;DR

This paper introduces a novel, real-time algorithm to "disentangle" the complex, interleaved execution of interrupt-driven programs in Internet of Things (IoT) devices. By accurately identifying individual Interrupt Procedure Instances (IPIs) with constant time and space overhead, the researchers provide a foundational tool for building more effective debugging, profiling, and testing suites for Wireless Sensor Networks (WSNs).

What Problem Does This Paper Address?

Wireless Sensor Networks (WSNs) are the backbone of the IoT, but programming them is notoriously difficult. Unlike traditional software, WSN programs are heavily interrupt-driven. When an event occurs (like a sensor reading), an interrupt handler runs immediately, often "posting" additional tasks to be executed later by a scheduler.

Because interrupts can preempt one another and tasks are queued for later, the execution of a single logical event—an Interrupt Procedure Instance (IPI)—becomes fragmented and interleaved with others. This creates a "spaghetti" of execution traces that are nearly impossible to predict from source code alone. Existing analysis tools (like Sentomist or T-Morph) struggle because they often assume task-posting is an atomic (uninterruptible) operation, or they require "rolling back" analysis because they can't identify the end of an execution instance in real-time. This leads to high memory overhead and makes long-term monitoring of IoT devices impossible.

Methods

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

  1. IHEntry: The start of an interrupt handler.
  2. IHExit: The end of an interrupt handler.
  3. RunTaskEntry: When the scheduler starts a queued task.
  4. RunTaskExit: When a task finishes.
  5. PostOk: A point indicating a task was successfully added to the system queue.

To handle the complexity of nested interrupts and deferred tasks, the algorithm uses two primary data structures:

  • A Global Stack (pInst_S): To keep track of which IPI was running when a new interrupt preempted it.
  • A Global Queue (okInst_Q): To map successfully posted tasks back to the specific IPI that created them.

Unlike previous methods, this algorithm identifies the start and end points of an IPI immediately as they occur (real-time) and does not assume that task-posting cannot be interrupted.

Datasets

The researchers evaluated their algorithm using five variants of three classic WSN applications running on TinyOS:

  • Oscilloscope: A sensor data collection program.
  • TestBlink: A program implementing multi-hop packet transmissions.
  • TestCTP: An application using the Collection Tree Protocol (CTP) for routing.

The evaluation was performed using the Avrora simulator, a cycle-accurate instruction-level simulator for sensor networks, mimicking a Mica2 platform with an ATmega128 microcontroller.

Key Insights and Ideas

  • Constant Complexity is King: The most significant insight is that IPI identification can be achieved with $O(1)$ time and space complexity per instruction. Because the maximum interrupt nesting depth and the OS task queue size are small constants in practice, the algorithm's overhead does not grow over time.
  • Decoupling Analysis from Identification: By creating a generic identification layer, the authors allow other researchers to build diverse tools (like bug detectors or performance profilers) on top of it without those tools needing to understand the messy details of interrupt interleaving.
  • The "PostOk" Necessity: Previous tools failed to account for the fact that a task-posting operation itself can be interrupted. By specifically tracking the PostOk point, this algorithm remains robust even in highly congested execution environments.

Key Results

  • Efficiency: In comparative experiments, the new algorithm maintained a flat line for both memory usage and time overhead across long execution periods (up to 150 seconds).
  • Superiority over "The Old Tool": The existing state-of-the-art tools showed memory and time overhead that increased significantly as the program ran longer. For example, in some tests, the "old tool" saw time overhead spikes that were nearly non-existent in the new algorithm.
  • Real-time Capability: The algorithm proved it could output an instruction's instance information and position (START, END, or INTERM) immediately, enabling online, live analysis of IoT devices.

Limitations and Future Work

While the algorithm is highly efficient, the current implementation relies on instruction-level probing (via the Avrora simulator). Implementing this on bare-metal hardware without a simulator might require hardware-assisted tracing or minimal instrumentation that could slightly alter timing (the "probe effect").

The authors suggest that the next step is to use this foundation to study IPI-based bug patterns. By understanding how these instances should interleave, they hope to develop automated testing techniques that can catch elusive concurrency bugs in IoT deployments before they go into the field.

Summary updated

Abstract

In the Internet of Things (IoT) community, wireless sensor network (WSN) is a key technique to enable ubiquitous sensing of environments and provide reliable services to applications. WSN programs, typically interrupt-driven, implement the functionalities via the collaboration of interrupt procedure instances (IPIs, namely executions of interrupt processing logic). However, due to the complicated concurrency model of WSN programs, the IPIs are interleaved intricately and the program behaviors are hard to predicate from the source codes. Thus, to improve the software quality of WSN programs, it is significant to disentangle the interleaved executions and develop various IPI-based program analysis techniques, including offline and online ones. As the common foundation of those techniques, a generic efficient and real-time algorithm to identify IPIs is urgently desired. However, the existing instance-identification approach cannot satisfy the desires. In this paper, we first formally define the concept of IPI. Next, we propose a generic IPI-identification algorithm, and prove its correctness, real-time, and efficiency. We also conduct comparison experiments to illustrate that our algorithm is more efficient than the existing one in terms of both time and space. As the theoretical analyses and empirical studies exhibit, our algorithm provides the groundwork for IPI-based analyses of WSN programs in IoT environment.
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