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.
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.· Companion Proceedings of the...· 0 citations
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· Proceedings of the 41st IEEE...· 0 citations
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· Proceedings of the ACM on So...· 0 citations
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
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
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· Electronic Proceedings in Th...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.