Formal modelling and verification of GALS systems using GRL and CADP

A GALS (Globally Asynchronous, Locally Synchronous) system consists of several synchronous components that evolve concurrently and interact with each other asynchronously. The design of GALS systems is tedious and error-prone due to the high degree of synchronous and asynchronous concurrency present in complex architectures. In this paper, we present GRL (GALS Representation Language), a formal language designed to model GALS systems, for the purpose of formal verification of the asynchronous aspects. GRL combines the synchronous reactive model underlying dataflow languages and the asynchronous concurrent model underlying process algebras. We propose a translation from GRL to LNT, a value-passing concurrent language with classical process algebra flavour. This makes possible the analysis of GRL specifications using all the state-of-the-art simulation and verification functionalities provided by the CADP toolbox.     

SystemJ: A GALS language for system level design

In this paper we present the syntax, semantics, and compilation of a new system-level programming language called SystemJ. SystemJ is a multiclock language supporting the Globally Asynchronous Locally Synchronous (GALS) model of computation. The synchronous reactive (SR) model is used for synchronous parts of the modelled system, and those parts, which represent individual clock-domains, are coupled asynchronously each to the other on the top-level of system design. SystemJ is based on Java language, which is used to describe “instantaneous” data transformations. Hence, SystemJ is well suited for both software-based embedded and distributed systems. SystemJ offers effective modelling of (1) data transformations through the power of Java, (2) control and synchronous concurrency through the SR paradigm and (3) asynchronous concurrency through clock domains and rendezvous. The language is based on semantics that is amenable to efficient code generation and partial automatic verification. The SystemJ micro-step semantics provide asynchronous and synchronous extensions over the semantics of other SR languages such as Esterel and provide an ideal platform for efficient software implementation.     

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.     

基于SPIN的系统建模研究

模型检测由于其自动化程度高,是形式化验证领域最受欢迎的验证方式之一。要使用模型检测器,首先要对要验证的系统进行建模。本文阐述模型检测技术的基本原理,并采用SPIN模型检测器对Promela建模进行研究。最后给出一个简单的公交车运行模型,并对实验结果进行分析。     

AltaRica 3.0模型到Promela模型转换与验证方法研究

AltaRica语言用于安全关键系统的建模,其拥有一套完整的建模分析工具,但随着AltaRica3.0的更新,ARC等传统的AltaRica建模分析工具已不再支持,而SPIN作为一个穷尽式模型验证工具被广泛应用。介绍了AltaRica3.0相对于之前版本在表达能力方面的改进,以及其底层模型GTS的基本结构。以AltaRica3.0扁平化为GTS模型的思想为基础,提出了一种AltaRica3.0模型向Promela模型的转换规则。以民用飞机中机轮刹车系统WBS为例,建立了AltaRica3.0模型,并且通过转换规则转为Promela模型。最后根据民用航空标准SAE ARP 4761中对机轮刹车系统的安全性要求,利用SPIN工具对机轮刹车系统的安全属性进行了验证。     

Data decision diagrams for Promela systems analysis

In this paper, we show how to verify computation tree logic (CTL) properties, using symbolic methods, on systems described in Promela. Symbolic representation is based on data decision diagrams (DDDs) which are n-valued Shared Decision Trees designed to represent dynamic systems with integer domain variables. We describe principal components used for the verification of Promela systems (DDD, representation of Promela programs with DDD, the transposition of the execution of Promela instructions into DDD). Then we compare and contrast our method with the model checker SPIN or classical binary decision diagram (BDD) techniques to highlight as to which system classes SPIN or our tool is more relevant.     

基于SPIN的G语言系统模型的验证

对于大型系统,为确保其运行的可靠性、稳定性及高效性,需要从两个方面对系统进行验证:业务模型和系统模型。目前,对业务模型的验证可通过BPMN来完成;对系统模型的验证可通过SPIN(Simple Promela Interpreter)工具执行。G语言是由NI公司创建的一种图形化程序框图语言,还未被加入ANSI标准,因此,文中第一步工作是提取G语言的形式、规则、文法等语言特性。由于SPIN对G语言不提供直接的支持,因此第二步工作是完成G2Promela的映射。在G2Promela的工作中,主要是基于编译器的框架,以Scanner-Parser-Optimizer-Generator(SPOG框架)为主线,根据第一步的预处理工作,按方法函数、指针、关键字、变量等分类创建G2Promela的映射规则,最终实现G2Promela的转换,完成对G语言系统模型的验证。该方法的提出弥补了G语言系统模型验证方面的空白,从而更深入地确保了G语言程序的性能。     

一种基于故障扩展SysML活动图的安全性验证框架研究

随着嵌入式系统在能源、交通等安全关键领域的广泛应用,针对嵌入式软件的安全性分析与验证方法一直是学术界和工业界的研究热点之一。使用扩展了故障树语义信息的SysML活动图来统一系统的功能模型与安全需求分析模型,并在保留故障树和SysML活动图两种模型语义描述的基础上,提出了一种基于故障扩展SysML活动图的安全性验证框架,包括:首先利用故障树最小割集提取故障信息并给出故障树逻辑门的转换规则;然后给出故障扩展SysML活动图的构建步骤;最后使用Promela对故障扩展SysML活动图进行建模,并使用模型检测工具SPIN对其进行分析验证。通过一个燃气灶控制系统验证了此方法的有效性。     

基于小系统理论的简化SET协议

基于Lu & Smolka的SET协议支付过程简化模型,在小系统理论的基础上,运用Promela语言对协议进行形式化建模,采用线性时态逻辑LTL公式对协议的认证性进行形式化描述。在网络环境被入侵者控制的假设下,运用SPIN发现攻击;采用atomic和Bit-state hashing等优化策略,降低模型检测的复杂性,提高验证效率;最后针对协议存在的漏洞提出协议改进方案。     

Formal Verification of Object-Oriented Graph Grammars Specifications

Concurrent object-oriented systems are ubiquitous due to the importance of networks and the current demands for modular, reusable, and easy to develop software. However, checking the correctness of such systems is a hard task, mainly due to concurrency and inheritance aspects. In this paper we present an approach to the verification of concurrent object-oriented systems. We use graph grammars equipped with object oriented features (including inheritance and polymorphism) as the specification formalism, and define a translation from such specifications to Promela, the input language of the SPIN model checker.     

Compiling and verifying SC-SystemJ programs for safety-critical reactive systems

Most of today's embedded systems are very complex. These systems, controlled by computer programs, continuously interact with their physical environments through network of sensory input and output devices. Consequently, the operations of such embedded systems are highly reactive and concurrent. Since embedded systems are deployed in many safety-critical applications, where failures can lead to catastrophic events, an approach that combines mathematical logic and formal verification is employed in order to ensure correct behavior of the control algorithm. This paper presents What You Prove Is What You Execute (WYPIWYE) compilation strategy for a Globally Asynchronous Locally Synchronous (GALS) programming language called Safey-Critical SystemJ. SC-SystemJ is a safety-critical subset of the SystemJ language. A formal big-step transition semantics of SC-SystemJ is developed for compiling SC-SystemJ programs into propositional Linear Temporal Logic formulas. These LTL formulas are then converted into a network of Mealy automata using a novel and efficient compilation algorithm. The resultant Mealy automata have a straightforward syntactic translation into Promela code. The resultant Promela models can be used for verifying correctness properties via the SPIN model-checker. Finally there is a single translation procedure to compile both: Promela and C/Java code for execution, which satisfies the De-Bruijn index, i.e. this final translation step is simple enough that is can be manually verified.     

基于SPIN的地下建筑设备监控系统软件验证

在地下建筑智能化系统中,设备监控系统是基本的组成部分,其软件设计的正确性十分重要。提出了一种基于SPIN的地下建筑设备监控系统软件正确性验证方法。构建了基于iFIX组态软件的设备控制系统软件Promela模型,利用SPIN模型检验方法对其安全性进行了验证。还利用简化模型进行反例追踪,找出了安全性规约中存在的错误。检验结果表明提出的验证方法是有效性。     

Moving from Weakly Endochronous Systems to Delay-Insensitive Circuits

We consider the problem of synthesizing the asynchronous wrappers and glue logic needed for the correct GALS implementation of a modular synchronous system. Our approach is based on the weakly endochronous synchronous model, which defines high-level, implementation-independent conditions guaranteeing correct desynchronization at the level of the abstract synchronous model. We can therefore factor the synthesis problem into (1) a high-level, implementation-independent phase insuring the weak endochrony of each synchronous module and (2) the actual wrapper synthesis phase, highly simplified by the high-level assumptions, yet flexible enough to produce various, efficient implementations.We focus here on the synthesis of delay-insensitive asynchronous wrappers from weakly endochronous synchronous modules, and show how this can be done for a simple DLX processor model.     

A UML-based static verification framework for security

Secure software engineering is a new research area that has been proposed to address security issues during the development of software systems. This new area of research advocates that security characteristics should be considered from the early stages of the software development life cycle and should not be added as another layer in the system on an ad-hoc basis after the system is built. In this paper, we describe a UML-based Static Verification Framework (USVF) to support the design and verification of secure software systems in early stages of the software development life-cycle taking into consideration security and general requirements of the software system. USVF performs static verification on UML models consisting of UML class and state machine diagrams extended by an action language. We present an operational semantics of UML models, define a property specification language designed to reason about temporal and general properties of UML state machines using the semantic domains of the former, and implement the model checking process by translating models and properties into Promela, the input language of the SPIN model checker. We show that the methodology can be applied to the verification of security properties by representing the main aspects of security, namely availability, integrity and confidentiality, in the USVF property specification language.     

Using SPIN to Analyse the Tree Identification Phase of the IEEE 1394 High-Performance Serial Bus (FireWire) Protocol

We describe how the tree identification phase of the IEEE 1394 high-performance serial bus (FireWire) protocol is modelled in Promela and verified using SPIN. The verification of arbitrary system configurations is discussed. Received July 2001/Accepted in revised form November 2002 Correspondence and offprint requests to: Alice Miller, Department of Computing Science, University of Glasgow, 17 Lilybank Gardens, Glasgow G12 8QQ, UK. Email: alice@dcs.gla.ac.uk     

Guest Editors' Introduction: GALS Design and Validation

Globally asynchronous, locally synchronous (GALS) design has grown in popularity in both academia and industry. Breaking the synchrony assumption in digital design is often unsettling for designers, and to alleviate the difficulty, researchers in EDA have been proposing various GALS-based solutions. However, the tools, verification techniques, and testing methodologies for asynchronous designs are not as widespread as for synchronous digital design, leading to the hitherto limited usage of GALS design approaches. This special issue introduces some of the basic issues of GALS design and validation in the hardware domain. The hope is that this special issue will generate more interest by researchers and industry practitioners in creating design tools, techniques, and validation methodologies for GALS design.     

A Survey and Taxonomy of GALS Design Styles

Single-clocked digital systems are largely a thing of the past. Although most digital circuits remain synchronous, many designs feature multiple clock domains, often running at different frequencies. Using an asynchronous interconnect decouples the timing issues for the separate blocks. Systems employing such schemes are called globally asynchronous, locally synchronous (GALS). To minimize time to market, large SoC designs must integrate many functional blocks with minimal design effort. These blocks are usually designed using standard synchronous methods and often have different clocking requirements. A GALS approach can facilitate fast block reuse by providing wrapper circuits to handle interblock communication across clock domain boundaries. SoCs may also achieve power savings by clocking different blocks at their minimum speeds. For example, Scott et al. describe the advantages of GALS design for an embedded-processor peripheral bus.     

ESpin*：基于SPIN的Eclipse模型检测环境

信息化社会中人们对软件可信性的要求越来越高,传统的测试技术已经不能充分保证系统的安全性,基于模型的形式化验证技术成为解决此类问题的重要途径。SPIN作为典型的模型检测工具,在学术界和工业界都得到了广泛应用。在Eclipse平台上设计并实现了一个基于SPIN的易扩展的模型检测环境ESpin,通过一个优化了的代码分区算法和可迅速支持SPIN升级的文法分析器,构造了一个高效、易扩充的Promela编辑器。编辑器除了支持Promela的全部语法规则外,还提供了包括实时语法反馈、关键字高亮、大纲视图、代码折叠、代码提示、代码补全在内的多种功能,提高了复杂模型的建模效率。ESpin还为用户提供了多种运行模式和特有的向导、配置界面,简化了SPIN的操作过程。     

Design Challenges for a Differential-Power-Analysis Aware GALS-based AES Crypto ASIC

In recent years several successful GALS realizations have been presented. The core of a GALS system is a locally synchronous island that is designed using industry standard synchronous design methodologies. In principle, any functional synchronous block can be encapsulated as a locally synchronous island to form a GALS module. There are, however, several important trade-offs and design decisions involved in doing so. Partitioning a design into several GALS compatible modules is still the most difficult task facing GALS system designers. The controlling state machine of a synchronous functional block may need to be enhanced significantly to accommodate varying latencies involved in data transfers between GALS modules.Such design challenges can not be easily generalized, and in this paper, are presented based on the experiences of designing a GALS system that implements a cryptographic algorithm. The example design uses the GALS methodology to improve resistance against cryptographic power attacks. The problem of side channel attacks against hardware implementations of cryptographic algorithms are briefly presented first, and the GALS architecture featuring several countermeasures against such attacks is introduced. The main part of the paper concentrates on the design decisions involved in the development of this architecture.     

炼焦过程控制计算机故障的分析与模型检测

用模型检测技术分析了工业生产中计算机通讯的一个死锁故障。根据技术人员的分析,建立了该通讯过程的Promela语言模型,并使用SPIN进行检测,找出了发生死锁的原因,其检测结果与技术人员的分析一致。