Statistical model checking of Timed Rebeca models

The actor-based language, Timed Rebeca, was introduced to model distributed and asynchronous systems with timing constraints and message passing communication. A toolset was developed for automated translation of Timed Rebeca models to Erlang. The translated code can be executed using a timed extension of McErlang for model checking and simulation. In this work, we added a new toolset that provides statistical model checking of Timed Rebeca models. Using statistical model checking, we are now able to verify larger models against safety properties compared to McErlang model checking. We examine the typical case studies of elevators and ticket service to show the efficiency of statistical model checking and applicability of our toolset.     

基于Rebeca模型的硬件设计形式化验证

形式化验证是对传统验证方法的补充,是数字电路验证的一条有效途径,对于并发系统,行为建模是一种非常合适的建模方法;Rebeca是由Sirjani和Movaghar提出的一种基于行为的建模语言,支持形式化,一方面,Rebeca是一种类Java的语言,软件工程师很容易使用,另一方面,它是一种支持形式化验证及其相关理论的模型语言,可以为不精通于形式化方法的开发人员和研究人员提供方便的验证过程;在深入研究Rebeca的基础上,采用Rebeca对硬件设计进行建模,然后Modere形式化验证工具对AES密码芯片进行形式化验证。     

Symmetry and partial order reduction techniques in model checking Rebeca

Rebeca is an actor-based language with formal semantics which is suitable for modeling concurrent and distributed systems and protocols. Due to its object model, partial order and symmetry detection and reduction techniques can be efficiently applied to dynamic Rebeca models. We present two approaches for detecting symmetry in Rebeca models: One that detects symmetry in the topology of inter-connections among objects and another one which exploits specific data structures to reflect internal symmetry in the internal structure of an object. The former approach is novel in that it does not require any input from the modeler and can deal with the dynamic changes of topology. This approach is potentially applicable to a wide range of modeling languages for distributed and reactive systems. We have also developed a model checking tool that implements all of the above-mentioned techniques. The evaluation results show significant improvements in model size and model-checking time.     

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.     

Actor-based slicing techniques for efficient reduction of Rebeca models

Slicing is a program analysis technique which can be used for reducing the size of the model and avoid state space explosion in model checking. In this work a static slicing technique is proposed for reducing Rebeca models with respect to a property. For applying the actor-based slicing techniques, the Rebeca control flow graph (RCFG) and the Rebeca dependence graph (RDG) are introduced. We propose two different approaches for constructing the RDG, where each approach can be more effective under certain conditions. As the static slicing usually produces large slices, two other slicing-based reduction techniques, step-wise slicing and bounded slicing, are proposed as simple novel ideas. Step-wise slicing first generates slices that overapproximate the behavior of the original model and then refines it, and bounded slicing is based on the semantics of nondeterministic assignments in Rebeca. We also propose a static slicing algorithm for deadlock detection (in absence of any particular property). The efficiency of these techniques is checked by applying them to several case studies which are included in this paper. Similar techniques can be applied on the other actor-based languages.     

分析安全协议猜测攻击的模态逻辑方法

以CKT5逻辑为基础,对其进行了多方面重要的扩展;在原有对称密钥机制的基础上,增加了公开密钥机制和vernam加密机制以增强其描述协议的能力;打破完善加密假设,给出了一组定义和规则使主体具备猜测和验证口令的能力;给出了与在线猜测攻击相关的定理以反映在线猜测攻击的特点;通过相关引理和定理的证明,简化了猜测攻击的分析过程,使该文方法比现有方法更加简洁高效.扩展后的逻辑能够用于分析安全协议的猜测攻击,包括在线猜测攻击.     

基于DTE策略的安全域隔离Z形式模型

基于DTE策略的安全域隔离技术是构造可信系统的基本技术之一.但现有DTE实现系统存在安全目标不明确、缺乏对系统及其安全性质的形式定义和分析的缺点,导致系统安全性难以得到保证.定义了一个基于DTE策略的安全域隔离模型,采用Z语言形式定义了系统状态、基于信息流分析的不变量和安全状态,并借助Z/EVES工具给出验证系统安全的形式分析方法.解决了DTE系统的形式化建模问题,为安全域隔离技术的实现和验证奠定了基础.     

模式驱动的系统安全性设计的验证

随着万维网和移动计算技术的广泛应用,系统安全性得到了越来越多的关注,使用安全模式对系统安全解决方案进行设计并验证是提升系统安全性的一种有效途径。现有方法根据系统安全需求选择适用的安全模式,在此基础上将模式组合为系统的安全解决方案,并通过模型检测方法验证其安全性。但是,这些方法往往将方案看作整体进行验证,忽略了内部安全模式的组合细节,难以在包含大量模式的复杂系统中定位缺陷。提出一种模式驱动的系统安全性设计的验证方法,首先使用代数规约语言SOFIA描述安全模式及其组合,以构建系统安全解决方案的形式化模型;然后将SOFIA规约转换为Alloy规约后,使用模型检测工具验证模式组合的正确性和系统的安全性。案例研究表明,该方法能够有效地验证系统安全解决方案的正确性。     

基于强化学习的安全协议形式化验证优化研究

使用形式化方法能够找到安全协议设计中存在的漏洞,但高效地对安全协议进行自动的形式化分析仍然是一个挑战。针对现有形式化自动验证工具无泛化性和效率低的不足,对基于强化学习的安全协议形式化验证框架smartVerif进行优化。使用无人工特征、完全进行自我学习的蒙特卡洛树搜索与深度神经网络相结合的强化学习框架,同时设计能够保留形式化数据结构信息的数据转换方法。实验结果表明,利用该优化方案训练的强化学习模型具有泛化性且能高效地验证安全协议。     

基于UPPAAL的微内核操作系统程序验证方法研究

随着航天、航空工业的发展,机载嵌入式软件的可信属性验证是新一代飞机研制最关注的软件质量保障问题。形式化方法具有严密的数学基础,能够准确的对系统进行建模、描述和验证,能够在软件系统的设计初期发现潜在的错误,是保证机载软件可信性和安全性的软件正确性验证技术。形式化验证以形式化描述为基础,对所描述系统的特性进行分析和验证,以评判系统是否满足期望的性质,分为定理证明和模型检测两类。文章研究模型检测方法应用于程序形式化描述和验证的技术,提出基于模型检测的验证程序正确性的方案,并进行微内核操作系统程序分析,最后在UPPAAL中进行程序属性的验证。     

基于时间戳私钥签名技术的Nayak-T协议安全性分析

随着信息网络的快速发展,云服务走进人们视野,云环境下信息安全问题成为人们关注的焦点。Nayak协议是一种云环境下基于口令身份认证,实现双向认证和会话密钥交换的协议。针对Nayak协议存在的中间人攻击,提出改进协议Nayak-T。Nayak-T协议在消息项内增加时间戳并更改加密手段,通过双重加密的手段来保证双方通信安全。利用四通道并行建模法对Nayak-T协议建模,运用SPIN对该协议进行验证,验证结果得出Nayak-T协议安全的结论。模型优化策略分析表明,采用静态分析、类型检查、语法重定序模型优化策略的模型检测效率最佳,可运用于类似复杂协议的形式化分析与验证。     

Formal Verification of Activity-Based Specification of Protocols

In this paper, we describe a method to formally verify activity-based specifications such as EBSDL. Starting from EBSDL-like specifications that specify engineering activities in terms of input and output behaviors, we derive programs in an asynchronous language CSP-R. CSP-R programs are then verified by the Maxpar method by composing them with the programs abstracting their environment. EBSDL-like specification and its verification using our method, is illustrated through the example of a fragment of LAPD protocol. The derivation of programs from the specification of activities of the underlying protocols through EBSDL-like specifications provides an important useful tool for formal verification of real-time protocols. We shall also discuss a translation of EBSDL-like specifications to synchronous languages such as Esterel. In the method proposed, it is possible for the user to choose asynchronous or synchronous formalisms depending upon the requirements of verification vis-a-vis logical specification.     

基于Spi演算的SSL3.0安全协议仿真分析

安全协议中的错误和漏洞很难完全由人工来发现,借助形式化方法对其进行分析可以保证安全协议的正确件和完整性。目前安全协议的形式化分析和验证已成为网络安全的研究热点,其中基于Spi演算的模型验证方法足当前的一个重要研究领域。文章介绍了SSL3．0安全协议的握手过程和Spi演算的基本概念,包括基于spi演算认证性的验证方法。存此基础上,基于spi演算形式化地建立了SSL3．0安全协议的仿真模型,给出了分析SSL3．0安全协议的详细过程,最终验证了SSL3．0安令协议的认证性。仿真分析的结果表明,Spi演算能够为安全协议的分析和验证提供可靠和有效的支持。     

Verifying a signature architecture: a comparative case study

We report on a case study in applying different formal methods to model and verify an architecture for administrating digital signatures. The architecture comprises several concurrently executing systems that authenticate users and generate and store digital signatures by passing security relevant data through a tightly controlled interface. The architecture is interesting from a formal-methods perspective as it involves complex operations on data as well as process coordination and hence is a candidate for both data-oriented and process-oriented formal methods. We have built and verified two models of the signature architecture using two representative formal methods. In the first, we specify a data model of the architecture in Z that we extend to a trace model and interactively verify by theorem proving. In the second, we model the architecture as a system of communicating processes that we verify by finite-state model checking. We provide a detailed comparison of these two different approaches to formalization (infinite state with rich data types versus finite state) and verification (theorem proving versus model checking). Contrary to common belief, our case study suggests that Z is well suited for temporal reasoning about process models with complex operations on data. Moreover, our comparison highlights the advantages of proving theorems about such models and provides evidence that, in the hands of an experienced user, theorem proving may be neither substantially more time-consuming nor more complex than model checking.     

安全网络并行计算环境SNPCE

由于网络并行计算环境建立在飞速发展的互联网上,容易受到各种黑客攻击,而目前各种流行的并行计算环境都没有提供完整的安全保护机制,因此,建立一个安全的网络并行计算环境,将并行程序设计人员从复杂的安全防范措施中解脱出来成为一个非常重要的研究方向。该文针对网络并行计算环境可能遭受的各种攻击,设计并实现了一种综合利用认证、加密、签名、消息摘要等多种安全防范手段的安全网络并行计算环境SNPCE系统。该系统能对其用户提供透明的安全防范措施,极大地减轻了并行程序设计人员的负担,同时也大大增加了系统对抗各种攻击的健壮性。     

反例引导的C代码空间流模型检测方法

软件验证一直是确保软件正确性和安全性的热点研究问题.然而,由于程序语言复杂的语法语义特性,应用形式化方法验证程序的正确性存在准确度低和效率差的问题.其中,由指针操作带来的地址空间的状态变化使得现有模型检测方法的检测准确度难以得到保证.为此,通过结合模型检测与稀疏值流分析方法,设计了一种空间流模型,实现了对C程序在符号变量层面和地址空间层面的状态行为的有效描述,并提出了一种反例引导的抽象细化和稀疏值流强更新算法(CEGAS),实现了C程序指向信息敏感的形式化验证.建立了包含多种指针操作的C代码基准库,并基于该基准库进行了对比实验.实验结果表明:所提出的模型检测算法CEGAS在分析含有多种C代码特性的任务中,与现有模型检测工具相比均能取得突出的结果,其检测准确度为92.9%,每行代码的平均检测时间为2.58 ms,优于现有检测工具.     

基于MQTT协议扩展的IoT设备完整性监控

随着物联网飞速发展,设备数量呈指数级增长,随之而来的IoT安全问题也受到了越来越多的关注.通常IoT设备完整性认证采用软件证明方法实现设备完整性校验,以便及时检测出设备中恶意软件执行所导致的系统完整性篡改.但现有IoT软件证明存在海量设备同步证明性能低、通用IoT通信协议难以扩展等问题.针对这些问题,本文提供一种轻量级的异步完整性监控方案,在通用MQTT协议上扩展软件证明安全认证消息,异步推送设备完整性信息,在保障IoT系统高安全性的同时,提高了设备完整性证明验证效率.我们的方案实现了以下3方面安全功能:以内核模块方式实现设备完整性度量功能,基于MQTT的设备身份和完整性轻量级认证扩展,基于MQTT扩展协议的异步完整性监控.本方案能够抵抗常见的软件证明和MQTT协议攻击,具有轻量级异步软件证明、通用MQTT安全扩展等特点.最后在基于MQTT的IoT认证原型系统的实验结果表明, IoT节点的完整性度量、MQTT协议连接认证、PUBLISH报文消息认证性能较高,都能满足海量IoT设备完整性监控的应用需求.     

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.