SynchRuler: a rule-based flexible synchronization model with model checking

Flexible synchronization models cannot provide a proper way of managing user interactions that change the course of a presentation. In this paper, we present a flexible synchronization model, termed SynchRuler, which allows such user interactions including backward and skip. The synchronization rules, which are based on event-condition-action (ECA) rules, are maintained to handle relationships among streams in SynchRuler. The synchronization rules are manipulated by the receiver-controller-actor (RCA) scheme, where receivers, controllers, and actors are objects to receive events, to check conditions, and to execute actions, respectively. The verification of a multimedia presentation specification is performed with the synchronization model. The correctness of the model and the presentation is controlled with a technique called model checking. Model checker PROMELA/SPIN tool is used for automatic verification of the correctness of LTL (linear temporal logic) formulas.     

Application of Colored Petri Nets for Verification of Scenario Control Structures in UCM Notation

The article presents a method for the analysis and verification of Use Case Map (UCM) models with scenario control structures—protected components and failure handling constructs. UCM models are analyzed and verified with the help of colored Petri nets (CPN) and the SPIN model checker. Algorithms for translating UCM scenario control structures into CPN and CPN into SPIN input language Promela are described. The number of elements of the resulting CPN model and the number of Promela model states are estimated. The presented algorithm and the verification process are illustrated by the study of a network router firmware update.     

Cluster-Based Partial-Order Reduction

The verification of concurrent systems through an exhaustive traversal of the state space suffers from the infamous state-space-explosion problem, caused by the many interleavings of actions of different processes in the system. Partial-order reduction is a well-known technique to tackle this problem. In this paper, we present an enhancement of the partial-order-reduction scheme of Holzmann and Peled that uses the hierarchical structure of concurrent systems. Our technique tries to contain dependencies between actions within clusters of processes, capitalizing on the independence of actions in different clusters to reduce the state space to be verified while preserving properties of interest. The paper starts with a formalization of the partial-order-reduction technique and continues with a presentation of our enhanced technique, including a correctness argument. The new technique has been implemented in the verification tool SPIN. We present implementation details, some small experiments, and one larger case study using a cache coherency protocol. The experimental results are encouraging. Compared to standard partial-order reduction, improvements in reductions are obtained from 21% up to 98% in the number of states and 34% up to 99% in the number of state transitions.     

The Design of a Multicore Extension of the SPIN Model Checker

We describe an extension of the SPIN model checker for use on multicore shared-memory systems and report on its performance. We show how, with proper load balancing, the time requirements of a verification run can, in some cases, be reduced close to N-fold when N processing cores are used. We also analyze the types of verification problems for which multicore algorithms cannot provide relief. The extensions discussed here require only relatively small changes in the SPIN source code and are compatible with most existing verification modes such as partial order reduction, the verification of temporal logic formulas, bitstate hashing, and hash-compact compression.     

Model checking Trampoline OS: a case study on safety analysis for automotive software

Model checking is an effective technique used to identify subtle problems in software safety using a comprehensive search algorithm. However, this comprehensiveness requires a large number of resources and is often too expensive to be applied in practice. This work strives to find a practical solution to model‐checking automotive operating systems for the purpose of safety analysis, with minimum requirements and a systematic engineering approach for applying the technique in practice. The paper presents methods for converting the Trampoline kernel code into formal models for the model checker SPIN, a series of experiments using an incremental verification approach, and the use of embedded C constructs for performance improvement. The conversion methods include functional modularization and treatment for hardware‐dependent code, such as memory access for context switching. The incremental verification approach aims at increasing the level of confidence in the verification even when comprehensiveness cannot be provided because of the limitations of the hardware resource. We also report on potential safety issues found in the Trampoline operating system during the experiments and present experimental evidence of the performance improvement using the embedded C constructs in SPIN. Copyright © 2012 John Wiley & Sons, Ltd.     

Verification support for ARINC‐653‐based avionics software

Software model checking consists in applying the most powerful results in formal verification research to programming languages such as C. One general technique to implement this approach is producing a reduced model of the software in order to employ existing and efficient tools, such as SPIN . This paper focusses on the application of this approach to the avionics software constructed on top of the Application Executive Software (APEX ) Interface, which is widely employed by manufacturers in the avionics industry. It presents a method to automatically extract PROMELA models from the C source code. In order to close the extracted model during verification, we built a reusable APEX ‐specific environment. This APEX environment models the execution engine (i.e. an APEX compliant real‐time operating system) that implements APEX services. In particular, it explains how to deal with aspects such as real‐time and APEX scheduling. Time is modelled in such a way that the we save time and memory by avoiding the analysis of irrelevant steps. This model of time and the construction of a deterministic scheduler guarantees the scalability of our approach. The paper also presents a tool that can verify realistic applications, and that has been used as a novel testing method to ensure the correctness of our APEX environment. This testing method uses SPIN to execute official APEX test cases. Copyright © 2010 John Wiley & Sons, Ltd.     

Comparison of SPIN and VIS for protocol verification

In this paper, we compare and contrast SPIN and VIS, two widely used formal verification tools. In particular, we devote special attention to the efficiency of these tools for the verification of communications protocols that can be implemented either in software or hardware. As a basis of our comparison, we formally describe and verify the Asynchronous Transfer Mode Ring (ATMR) medium access protocol using SPIN and its hardware model using VIS. We believe that this study is of particular interest as more and more protocols, like ATM protocols, are implemented in hardware to match high-speed requirements. Published online: 1 March 2002     

RFID超轻量级认证协议RCIA形式化分析与改进

无线射频识别（RFID）是物联网中的一种非接触式的自动识别技术,被广泛运用于构建物物互联的RFID系统。RCIA是一种超轻量级RFID双向认证协议,提供高安全性并声称能抵御去同步攻击。形式化方法是安全协议分析的有力手段。运用模型检测工具SPIN对RCIA协议的认证性及一致性进行验证,结果表明RCIA协议存在去同步攻击漏洞。针对此漏洞,提出基于密钥同步机制的修补方案,对RCIA协议进行了改进。对改进后的协议进行形式化分析与验证,结果表明改进后的RCIA协议具有更高的安全性。提出的协议抽象建模方法对此类超轻量级RFID双向认证协议形式化分析具有重要借鉴意义;提出的基于密钥同步机制的漏洞修补方案,被证明能有效抵御去同步漏洞,可适用于此类超轻量级RFID双向认证协议的设计和分析。     

Linux中SystemV进程通信机制安全性形式化验证

基于Linux开发安全操作系统是提高计算机安全的重要途径，而形式化验证则是开发过程的重要和必要的环节，我们从Linux的各个子系统着手进行验证，逐步搭建起整个操作系统的验证模型。考虑到访问控制机制是实现操作系统安全性的关键，本文主要讨论使用SPIN模型检验器对IPC子系统中的SystemV进程通信机制进行形式化验证的过程与方法法。查找安全漏洞并改进现有的机制，为开发工程提供理论上的保证。     

RPKI增量同步Delta协议的形式化检测与实现

现有RPKI体系中,RPKI资料库与RP服务器之间的数据同步使用开源工具Rsync,但由于RPKI体系中证书数据结构的特殊性,使用Rsync进行数据的同步不仅效率低下,而且Rsync会消耗过多的系统资源,从而使整个RPKI体系遭遇潜在的安全风险.因此,IETF针对RPKI资料库数据特征,提出增量同步Delta协议以替代Rsync在RPKI中的作用.本文详细介绍了Delta协议的工作逻辑和机制,从安全性和高效性两方面将之与Rsync进行全面对比,并使用Promela语言构建Delta协议模型,借助形式化验证工具SPIN对该模型进行验证,从而证明该协议具备较高的协议安全性和稳定性.最后,本文给出Delta协议的实现结构.