Specification,proof, and model checking of the Mondex electronic purse using RAISE

This paper describes how the communication protocol of Mondex electronic purses can be specified and verified against desired security properties. The specification is developed by stepwise refinement using the RAISE formal specification language, RSL, and the proofs are made by translation to PVS and SAL. The work is part of a year-long project contributing to the international grand challenge in verified software engineering. J. C. P. Woodcock     

A verification approach to applied system security

We present a method for the security analysis of realistic models over off-the-shelf systems and their configuration by formal, machine-checked proofs. The presentation follows a large case study based on a formal security analysis of a CVS-Server architecture.The analysis is based on an abstract architecture (enforcing a role-based access control), which is refined to an implementation architecture (based on the usual discretionary access control provided by the POSIX environment). Both architectures serve as a skeleton to formulate access control and confidentiality properties.Both the abstract and the implementation architecture are specified in the language Z. Based on a logical embedding of Z into Isabelle/HOL, we provide formal, machine-checked proofs for consistency properties of the specification, for the correctness of the refinement, and for security properties.     

The certification of the Mondex electronic purse to ITSEC Level E6

Ten years ago the Mondex electronic purse was certified to ITSEC Level E6, the highest level of assurance for secure systems. This involved building formal models in the Z notation, linking them with refinement, and proving that they correctly implement the required security properties. The work has been revived recently as a pilot project for the international Grand Challenge in Verified Software. This paper records the history of the original project and gives an overview of the formal models and proofs used. C. B. Jones     

Verifying Communication Protocols Using Live Sequence Chart Specifications

The need for a formal verification process in System on Chip (SoC) design and Intellectual Property (IP) integration has been recognized and investigated significantly in the past. A major drawback is the lack of a suitable specification language against which definitive and efficient verification of inter-core communication can be performed to prove compliance of an IP block against the protocol specification. Previous research has yielded positive results of verifying systems against the graphical language of Live Sequence Charts (LSCs) but has identified key limitations of the process that arise from the lack of support for important constructs of LSCs such as Kleene stars, subcharts, and hierarchical charts. In this paper we further investigate the use of LSCs as a specification language and show how it can be formally translated to automata suitable for input to a model checker for automatic verification of the system under test. We present the translation for subcharts, Kleene stars, and hierarchical charts that are essential for protocol specification and have not been translated to automata before. Further, we successfully translate the BVCI protocol (point to point communication protocol) specification from LSC to an automaton and present a case study of verifying models using the resulting automaton.     

Integrating formal methods into the development process

It is shown that integrating formal specification and verification with development is faster and more cost-effective than doing the steps separately or in parallel. This case study demonstrates their application in a security context and documents their use in several phases of development, starting from the requirements of a terminal serving a security officer, on through formal requirements and design expressed as state transitions, to detailed design specifications and proofs that these agree with higher-level specifications, stopping just before code-level verification (due to complications typical of such projects). The effects of verification on this particular project are addressed     

Refinement-based Modeling and Formal Verification for Multiple Secure Partitions of TrustZone

As a trusted execution environment technology on ARM processors, TrustZone provides an isolated and independent execution environment for security-sensitive programs and data on the device. However, running the trusted OS and all the trusted applications in the same environment may cause problems---The exploitation of vulnerabilities on any component may affect the others in the system. Although ARM proposed the S-EL2 virtualization technology, which supports multiple isolated partitions in the secure world to alleviate this problem, there may still be security threats such as information leakage between partitions in the real-world partition manager. Current secure partition manager designs and implementations lack rigorous mathematical proofs to guarantee the security of isolated partitions. This study analyzes the multiple secure partitions architecture of ARM TrustZone in detail, proposes a refinement-based modeling and security analysis method for multiple secure partitions of TrustZone, and completes the modeling and formal verification of the secure partition manager in the theorem prover Isabelle/HOL. First, we build a multiple secure partitions model named RMTEE based on refinement: an abstract state machine is used to describe the system running process and security policy requirements, forming the abstract model. Then the abstract model is instantiated into the concrete model, in which the event specification is implemented following the FF-A specification. Second, to address the problem that the existing partition manager design cannot meet the goal of information flow security verification, we design a DAC-based inter-partition communication access control and apply it to the modeling and verification of RMTEE. Lastly, we prove the refinement between the concrete model and the abstract model, and the correctness and security of the event specification in the concrete model. The formalization and verification consist of 137 definitions and 201 lemmas (more than 11,000 lines of Isabelle/HOL code). The results show that the model satisfies confidentiality and integrity, and can effectively defend against malicious attacks on partitions.     

基于精化的TrustZone多安全分区建模与形式化验证

TrustZone作为ARM处理器上的可信执行环境技术,为设备上安全敏感的程序和数据提供一个隔离的独立执行环境.然而,可信操作系统与所有可信应用运行在同一个可信环境中,任意组件上的漏洞被利用都会波及系统中的其他组件.虽然ARM提出了S-EL2虚拟化技术,支持在安全世界建立多个隔离分区来缓解这个问题,但实际分区管理器中仍可能存在分区间信息泄漏等安全威胁.当前的分区管理器设计及实现缺乏严格的数学证明来保证隔离分区的安全性.详细研究了ARM TrustZone多隔离分区架构,提出一种基于精化的TrustZone多安全分区建模与安全性分析方法,并基于定理证明器Isabelle/HOL完成了分区管理器的建模和形式化验证.首先,基于逐层精化的方法构建了多安全分区模型RMTEE,使用抽象状态机描述系统运行过程和安全策略要求,建立多安全分区的抽象模型并实例化实现分区管理器的具体模型,遵循FF-A规范在具体模型中实现了事件规约;其次,针对现有分区管理器设计无法满足信息流安全性验证的不足,设计了基于DAC的分区间通信访问控制,并将其应用到TrustZone安全分区管理器的建模与验证中;再次,证明了具体模型...     

Hybrid Verification of Protocol Bridges

It's usually necessary to apply formal verification on very small modules or else be content with bounded proofs on realistically large modules. But there is no denying that despite its capacity problems, formal verification has its strengths and utility and is a complementary technique to simulation. Used judiciously, simulation and formal techniques can complement each other's strengths, thereby balancing their respective weaknesses. There are different ways to combine these two techniques. In this article, we present two case studies of the application of one such technique: the hybrid verification of a serial protocol. We chose this example because of serial protocols' added complexity compared to parallel protocols. Both case studies involve the same serial protocol (I²C) but demonstrate different aspects of its verification. Selection of the same protocol in both case studies also demonstrates the tremendous value of reuse in formal verification.     

一种描述安全协议的形式化规范语言

安全协议的设计和分析是复杂而且容易出错的。使用形式化的语言有利于安全协议的正确性和完整性。现有的安全协议的描述方法大多很复杂而且容易导致二义，从而导致协议隐含着种种的安全隐患。引入了基于构造类别代数的形式化规范语言来规范安全协议，通过规则集合和公理集合对安全协议进行精确地描述，有利于协议设计地规范化和协议漏洞地发现，同时对Needham-Sehroeder协议进行了形式化规范以进一步说明该形式化语言地使用。     

A refinement calculus for specifications in Hennessy-Milner logic with recursion

This paper is about specification and verification of processes, modelled as CCS-agents. We show, by means of examples that Hennessy-Milner Logic (HML) with recursion is a suitable language for expressing implicit or partial specifications. By extending this specification language withrefinement operators, i.e. operators that describe the internal structure of a system, we obtain a calculus for stepwise refinement of agents from a specification in HML to a realisation in CCS. The method is demonstrated by proving the alternating-bit protocol under weak assumptions about the unreliable media.This paper has also be presented at the BCS-FACS workshop on Specification and Verification of Concurrent Systems, University of Stirling, July 1988, under the title: Hennessy-Milner logic with recursion as a specification language, and a refinement calculus based on it.     

Verifying an infinite systolic algorithm using third-order equational methods

We consider using third-order equational methods to formally verify that an infinite systolic algorithm correctly implements a family of convolution functions. The detailed case study we present illustrates the use of third-order algebra as a formal framework for developing families of computing systems. It also provides an interesting insight into the use of infinite algorithms as a means of verifying a family of finite algorithms. We consider using purely equational reasoning in our verification proofs and in particular, using the rule of free variable induction. We conclude by considering how our verification proofs can be automated using rewriting techniques.     

Atomic actions, and their refinements to isolated protocols

Inspired by the properties of the refinement development of the Mondex Electronic Purse, we view an isolated atomic action as a family of transitions with a common before-state, and different after-states corresponding to different possible outcomes when the action is attempted. We view a protocol for an atomic action as a computation DAG, each path of which achieves in several steps one of the outcomes of the atomic action. We show that in this picture, the protocol can be viewed as a relational refinement of the atomic action in a number of ways. Firstly, it yields a ‘big diagram’ simulation à la ASM. Secondly, it yields a ‘small diagram’ simulation, in which the atomic action is synchronised with an individual step along each path through the protocol, and all the other steps of the path simulate skip. We show that provided each path through the protocol contains one step synchronised with the atomic action, the choice of synchronisation point can be made freely. We describe the relationship between such synchronisations and forward and backward simulations. We relate this theory to serialisations of system runs containing multiple interleaved transactions, showing how the clean picture of the refinement of an isolated atomic action to an isolated protocol becomes obscured by the details of the interleaving. In effect, the fact that protocols are typically executed by a number of co-operating agents, not all of which embark on executing the protocol at the same moment, results in ‘ragged starts’ and ‘ragged ends’ to protocol instantiations, leading to potential overlaps between unrelated protocol instances that the theory must handle. We show how existing Mondex refinements embody the ideas developed, and describe a mechanical verification of the results presented.     

基于协议形式化描述的网络增值服务开发方法与技术

增值服务是在原有网络的软硬件基础之上进行的功能开发，它在不影响原系统功能的前提下实现功能附加，使网络功能得到增值．本文引入形式化描述技术，提出了基于协议形式化描述的网络增值服务开发方法，并通过对文件传输协议的描述讨论了该方法的具体应用．最后总结了该方法在实际网络增值开发中的应用技术．     

Safety-critical Java programs from Circus models

Safety-Critical Java (SCJ) is a novel version of Java that addresses issues related to real-time programming and certification of safety-critical applications. In this paper, we propose a technique that reveals the issues involved in the formal verification of an SCJ program, and provides guidelines for tackling them in a refinement-based approach. It is based on Circus, a combination of well established notations: Z, CSP, Timed CSP, and object orientation. We cater for the specification of timing requirements and their decomposition towards the structure of missions and event handlers of SCJ. We also consider the integrated refinement of value-based specifications into class-based designs using SCJ scoped memory areas. We present a refinement strategy, a Circus variant that captures the essence of the SCJ paradigm, and a substantial example based approach on a concurrent version of a case study that has been used as a benchmark by the SCJ community: an aircraft collision detector.     

Tightening the contract refinements of a system architecture

Contract-based design is an emerging paradigm for correct-by-construction hierarchical systems: components are associated with assumptions and guarantees expressed as formal properties; the architecture is analyzed by verifying that each contract of composite components is correctly refined by the contracts of its subcomponents. The approach is very efficient, because the overall correctness proof is decomposed into proofs local to each component. However, the process for the contract specification and refinement is quite expensive because the requirements are formalised into formal properties, where part of the complexity is delegated to the designer, who has the burden of specifying the contracts. Typical problems include understanding which contracts are necessary, and how they can be simplified without breaking the correctness of the refinement and other refinements in case some subcontracts are shared. In this paper, we tackle these problems by proposing a technique to understand and simplify the contract refinements of a system architecture during the development process for the contract specification and refinement. The technique, called tightening, is based on parameter synthesis. The idea is to generate a set of parametric proof obligations, where each parameter evaluation corresponds to a variant of the original(s) contract refinement(s), and to search for tighter variants of the contracts that still ensure the correctness of the refinement(s). We cast this approach in the OCRA framework, where contracts are expressed with LTL formulas, and we evaluate its performance and effectiveness on a number of benchmarks.     

Formal methods for verification and validation of partial specifications: A case study

This paper describes our work exploring the suitability of formal specification methods for independent verification and validation (IV&V) of software specifications for large, safety-critical systems. An IV&V contractor often has to perform rapid analysis on incomplete specifications, with no control over how those specifications are represented. Lightweight formal methods show significant promise in this context, as they offer a way of uncovering major errors without the burden of full proofs of correctness. We describe a case study of the use of partial formal models for IV&V of the requirements for Fault Detection Isolation and Recovery on the space station. We conclude that the insights gained from formalizing a specification are valuable, and it is the process of formalization, rather than the end product, that is important. It was only necessary to build enough of the formal model to test the properties in which we were interested. Maintenance of fidelity between multiple representations of the same requirements (as they evolve) is still a problem, and deserves further study.     

Formal Verification of a Consensus Algorithm in the Heard-Of ModelReal-Time Embedded Systems Using VDM

Distributed algorithms are subtle and error-prone. Still, very few of them have been formally verified, most algorithm designers only giving rough and informal sketches of proofs. We believe that this unsatisfactory situation is due to a scalability problem of current formal methods and that a simpler model is needed to reason about distributed algorithms. We consider formal verification of algorithms expressed in the Heard-Of model recently introduced by Charron-Bost and Schiper. As a concrete case study, we report on the formal verification of a non-trivial Consensus algorithm using the proof assistant Isabelle/HOL.     

Formal specification and compositional verification of an atomic broadcast protocol

We apply a formal method based on assertions to specify and verify an atomic broadcast protocol. The protocol is implemented by replicating a server process on all processors in a network. We show that the verification of the protocol can be done compositionally by using specifications in which timing is expressed by local clock values. First the requirements of the protocol are formally described. Next the underlying communication mechanism, the assumptions about local clocks, and the failure assumptions are axiomatized. Also the server process is represented by a formal specification. Then we verify that parallel execution of the server processes leads to the desired properties by proving that the conjunction of all server specifications and the axioms about the system implies the requirements of the protocol.     

An incremental specification of the sliding-window protocol

Summary The sliding-window protocol is specified using the notation of communicating Sequential Processes and its partial correctness is proved using the trace semantics. First the stop-and-wait protocol is defined; its correctness, that it forms a 1-place buffer, is almost evident. Next the alternating-bit protocol is defined and described in terms of the stop-and-wait protocol, and its correctness deduced from that of the stop-and-wait protocol. Finally the sliding-window protocol is described in terms of the alternating-bit protocol and its correctness deduced accordingly. The paper has two thrusts: that modularity of a specification helps to structure proofs about it (in this case, proofs that the protocols implement buffers); and that refinement in CSP leads to structured, correct implementations in occam. In support of the latter point the appendix contains a refinement and implementation of the protocols in occam 2. Karen Paliwoda (now Seidel) received a degree in Mathematics (BSc) from Bradford University in 1986. She worked for two years as a research assistant at Oxford and University College, London, investigating both formal and applied aspects of communication protocols. She is currently working towards a PhD on a probabilistic model of CSP. Jeff Sanders holds degrees in Pure Mathematics from Monash University (BSc (Hons)) and the Australian National University (PhD). He is a University Lecturer at Oxford and a Tutorial Fellow at Lady Margaret Hall, with interests in the mathematics of Computation.