Title: Analyzing and Disentangling Interleaved Interrupt-driven IoT Programs,
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 behaviours 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.