Skip to content
Open access

Verifying Interrupt-driven Programs Efficiently via Heuristic and Reduced Partial-order Constraints

Sep 2026 · ACM Transactions on Embedded Computing Systems · 0 citations · 36 references

TL;DR

A model checking approach for detecting assertion violations in interrupt-driven programs by considering the unique enable-before mechanism specific to interrupt-driven programs, infeasible partial-order constraints are identified and eliminated, resulting in a simplified formula for more efficient reasoning.

Abstract

Interrupt-driven programs are extensively utilized in embedded systems for safety-critical domains. However, uncertain interleaving executions of enabled tasks with different priorities often lead to concurrency defects. In this context, assertion violation detection is a fundamental method to ensure program correctness. Worryingly, it remains a challenge for state-of-the-art tools to achieve both precision and efficiency. To address this issue, we introduce a model checking approach for detecting assertion violations in interrupt-driven programs. First, precise partial-order constraints are established to represent potential task interleavings with different priorities. Subsequently, heuristic constraints are formulated to capture the concurrency-control relations inherent in interrupt-driven systems, thereby providing effective guidance for the back-end solver in exploring the solution space. Furthermore, by considering the unique enable-before mechanism specific to interrupt-driven programs, infeasible partial-order constraints are identified and eliminated, resulting in a simplified formula for more efficient reasoning. This formula is finally fed into a modern SAT or SMT solver, along with a constraint specifying the set of error states. Our approach has been implemented in a model checker namely IDPchecker for real-world C programs. Comprehensive experiments demonstrate that the proposed strategies can contribute to the solving time reduction while maintaining enough accuracy, making IDPchecker much more precise and efficient than the relative tools.

Read PDF

Similar papers

Book Open access Oct 2026

Iekkë: A Bounded-Round Partial-Order Encoding Verification Tool for Concurrent C Programs

We present Iekkë, a BMC tool for verifying multi-threaded C programs. It implements a new bounded-round partial-order encoding for the sequential consistency shared-memory model. The encoding combines the compactness of lazy sequentialization with the structural precision of the partial-order approach. Its concurrency...

P. Di Biase, Bernd Fischer, Salvatore La Torre et al. · 0 citations
Book Open access Oct 2026

Precise and Efficient Static Data Race Detection

This paper presents a precise modeling of data races based on event-level ordering constraints, which avoids any instrumentation while capturing the exact semantics and covering all potential race occurrences within the given bounded scope and integrates it into a concurrent program verification framework and proves it...

Pei-Feng Wang, Zhi-Hang Sun, Fei He · 0 citations
Open access Oct 2026

Efficient Predictive Monitoring of Message Passing Interface Programs

The Message Passing Interface (MPI) is the standard programming model for high-performance computing, yet nondeterministic scheduling in concurrent executions makes reliability assurance highly challenging. Beyond deadlocks, property-related bugs such as modifying a send buffer before a nonblocking send completes or ac...

Jia-Qiang Yao, Hao-Cheng Geng, Zhen-Bang Chen · 0 citations
Preprint Oct 2026

Structural Analysis of Hybrid-Trace Nets: An Optimization Approach

Fault and error detection is crucial for ensuring the correctness of safety-critical systems. Safety verification often addresses reachability of bad system states, where exhaustive state inspection may be intractable due to the large state spaces of complex systems. We propose a reachability relaxation for hybrid trac...

L. Nguyen, C. Bonial, John G. Rogers et al. · 0 citations
Preprint Sep 2026

Specification-Guided Path Shortcutting for Efficient Probabilistic Model Checking

Given the safety-critical nature of many embedded systems, their safety assurance is essential. Because such systems are typically stochastic, probabilistic model checking is a particularly important technique. However, there is a well-known scalability issue due to state-space explosion, especially when verifying comp...

T. Matsumoto, Kazuki Watanabe, Masaki Waga · 0 citations
Open access Sep 2026

Modelling Shared-Space Coordination in mCRL2: a Bach-to-mCRL2 Translation Framework

Although significant research has focused on the theory and implementation of data-based coordination languages, the critical aspect of their automated verification using model-checking techniques remains underexplored, which is essential for ensuring reliability and correctness in distributed systems. Existing tools,...

Corentin Reuther, Jean-Marie Jacquet · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.