概率非否认协议的模型检测分析

基于概率模型检测技术，建立了需要保证ε-公平性的非否认协议的概率模型，根据不同行为将主体建立有限状态机模型。使用概率模型检测器PRISM，验证了概率非否认协议的有效性、公平性和时限性。在恶意实体能力和网络环境等不同情况下，分析了破坏协议公平性的概率。     

Automatic Verification of the IEEE-1394 Root Contention Protocol with KRONOS and PRISM

We report on the automatic verification of timed probabilistic properties of the IEEE 1394 root contention protocol combining two existing tools: the real-time model-checker KRONOS and the probabilistic model-checker PRISM. The system is modelled as a probabilistic timed automaton. We first use KRONOS to perform a symbolic forward reachability analysis to generate the set of states that are reachable with non-zero probability from the initial state, and before the deadline expires. We then encode this information as a Markov decision process to be analyzed with PRISM. We apply this technique to compute the minimal probability of a leader being elected before a deadline, for different deadlines, and study the influence of using a biased coin on this minimal probability.     

匿名协议WonGoo的概率模型验证分析

Internet隐私的一个主要问题是缺乏匿名保护．近年来，人们已经针对这一问题做了很多工作．然而．如何利用已有的形式化方法分析匿名技术却是一个极具挑战的问题．对P2P匿名通信协议WonGoo进行了形式化分析．利用离散时问Markov链模型化节点和攻击者的行为．系统的匿名性质采用时序逻辑PCTI，进行描述．利用概率模型验证器PRISM对WonGoo系统的匿名性进行了自动验证．结果表明WonGoo的匿名性随着系统规模的增加而增加；但却随着攻击者观察到的源自同一个发送者的路径的增加而降低．另外，匿名路径越长，系统的匿名性越强．     

Quantitative Analysis With the Probabilistic Model Checker PRISM

Probabilistic model checking is a formal verification technique for establishing the correctness, performance and reliability of systems which exhibit stochastic behaviour. As in conventional verification, a precise mathematical model of a real-life system is constructed first, and, given formal specifications of one or more properties of this system, an analysis of these properties is performed. The exploration of the system model is exhaustive and involves a combination of graph-theoretic algorithms and numerical methods. In this paper, we give a brief overview of the probabilistic model checker PRISM (www.cs.bham.ac.uk/~dxp/prism) implemented at the University of Birmingham. PRISM supports a range of probabilistic models and specification languages based on temporal logic, and has been recently extended with costs and rewards. We describe our experience with using PRISM to analyse a number of case studies from a wide range of application domains. We demonstrate the usefulness of probabilistic model checking techniques in detecting flaws and unusual trends, focusing mainly on the quantitative analysis of a range of best, worst and average-case system characteristics.     

Mediator的概率扩展

Mediator是一种基于组件的形式化建模语言,它提供了分层的模块化结构,从而可以方便地对复杂系统进行建模。它以自动机为其底层单位,自动机连接成的系统作为高级结构,能在对模型进行形式化描述的同时让其本身简单易用。为了使Mediator具有更强的表达能力,可对具有概率行为的系统进行形式化建模,对Mediator做了概率方面的扩展,并对扩展后的语言给出了基于马尔可夫决策过程的语义。同时还介绍了由Mediator模型自动生成PRISM代码的方法,能够使用PRISM工具对Mediator模型的相关性质进行验证。     

Automated Game Analysis via Probabilistic Model Checking: a case study

It has been recognised for some time that there are close links between the various logics developed for the analysis of multi-agent systems and the many game-theoretic models developed for the same purpose. In this paper, we contribute to this burgeoning body of work by showing how a probabilistic model checking tool can be used for the automated analysis of game-like multi-agent systems in which both agents and environments can act with uncertainty. Specifically, we show how a variation of the well-known alternating offers negotiation protocol of Rubinstein can be encoded as a model for the PRISM model checker and its behaviour analysed through automatic verification of probabilistic CTL's properties.     

5G网络认证与密钥协商协议的形式化验证与分析

网络攻击的手段层出不穷, 如中间人攻击, 重放攻击, DoS攻击等, 以此获取不当利益. 密钥协商协议的设立是为合法用户提供正确认证入口, 并拒绝攻击者的非法接入和攻击. 密钥协商协议是保护移动通信提高服务质量的第一道安全防线, 5G网络密钥协商协议在实际环境中仍然存在安全隐患, 其协议本身的安全特性能否满足要求仍未可知, 本文提出使用基于概率模型检测的方法, 通过对5G网络密钥协商协议的各协议方实体进行建模, 建立离散时间马尔科夫链模型, 在建模过程中考虑外界的攻击影响, 引入攻击率来描述外界的影响程度, 通过攻击率对5G网络密钥协商协议的研究进行定量分析, 使用概率计算树逻辑对待验属性规约进行编码描述, 利用概率模型检测工具PRISM进行实验. 实验结果表明: 在引入攻击率的5G网络密钥协商协议模型中, 5G网络密钥协商协议各协议方实体所受攻击的影响对该协议的时延性, 有效性, 保密性等属性规约的性能有不同程度的影响, 因此, 研究外界网络攻击对协议的安全性能的影响, 对加强协议安全性能及其改进具有一定借鉴意义, 并对5G网络密钥协商协议的安全特性的提升和保护用户的经济与信息安全具有很大的意义.     

Modeling and Analysis of Data Flow-Oriented ROS2 Data Distribution Service

Robot Operating System (ROS) is an open-source, meta-operating system, which can provide a structured communication layer based on the message mechanism on heterogeneous computing clusters. To improve the unsatisfactory real-time performance and reliability of data distribution in ROS1, ROS2 is proposed with a data flow-oriented data distribution service mechanism. This study validates the real-time performance and reliability of the ROS2 data distribution mechanism by means of probabilistic model checking. Firstly, a formal validation framework is put forward for the data flow-oriented ROS2 data distribution service system, and the probabilistic timed automata model is set up for the communication system module. Secondly, the probabilistic model checker PRISM is used to verify the real-time performance and reliability of data flow-oriented ROS2 data distribution service through the analysis of data loss rate and system response time. Finally, depending on the retransmission mechanism and Quality of Service (QoS) policy analysis, different data requirements and quantitative performance analysis of the transmission mode are achieved through the setting and adjustment of QoS parameters. This study can provide references for ROS2 application designers and the formal modeling, validation, and quantitative performance analysis of the distributed data distribution service based on the data flow.     

Probabliistic Analysis Of Electrocardiogram (Ecg) Heart Signal

Electrocardiography (ECG) is a heart signal wave that is recorded using medical sensors, which are normally attached to the human body by the heart. ECG waves have repetitive patterns that can be efficiently used in the diagnosis of heart problems as they carry several characteristics of heart operation. Traditionally, the analysis of ECG waves is done using informal techniques, like simulation, which is in-exhaustive and thus the analysis results may lead to ambiguities and life threatening scenarios in extreme cases. In order to overcome such problems, we propose to analyze ECG heart signals using probabilistic model checking, which is a formal methods based quantitative analysis approach. This work presents the formal probabilistic analysis of ECG signal abnormalities where the likelihood of abnormal patterns is studied and analyzed using the PRISM model checker.     

Probabilistic model checking for the quantification of DoS security threats

Secure authentication features of communication and electronic commerce protocols involve computationally expensive and memory intensive cryptographic operations that have the potential to be turned into denial-of-service (DoS) exploits. Recent proposals attempt to improve DoS resistance by implementing a trade-off between the resources required for the potential victim(s) with the resources used by a prospective attacker. Such improvements have been proposed for the Internet Key Exchange (IKE), the Just Fast Keying (JFK) key agreement protocol and the Secure Sockets Layer (SSL/TLS) protocol. In present article, we introduce probabilistic model checking as an efficient tool-assisted approach for systematically quantifying DoS security threats. We model a security protocol with a fixed network topology using probabilistic specifications for the protocol participants. We attach into the protocol model, a probabilistic attacker model which performs DoS related actions with assigned cost values. The costs for the protocol participants and the attacker reflect the level of some resource expenditure (memory, processing capacity or communication bandwidth) for the associated actions. From the developed model we obtain a Discrete Time Markov Chain (DTMC) via property preserving discrete-time semantics. The DTMC model is verified using the PRISM model checker that produces probabilistic estimates for the analyzed DoS threat. In this way, it is possible to evaluate the level of resource expenditure for the attacker, beyond which the likelihood of widespread attack is reduced and subsequently to compare alternative design considerations for optimal resistance to the analyzed DoS threat. Our approach is validated through the analysis of the Host Identity Protocol (HIP). The HIP base-exchange is seen as a cryptographic key-exchange protocol with special features related to DoS protection. We analyze a serious DoS threat, for which we provide probabilistic estimates, as well as results for the associated attacker and participants' costs.     

A formal verification framework for SysML activity diagrams

SysML activity diagrams are OMG/INCOSE standard diagrams used for modeling and specifying probabilistic systems. They support systems composition by call behavior and send/receive artifacts. For verification, the existing approaches dedicated to these diagrams are limited to a restricted set of artifacts. In this paper, we propose a formal verification framework for these diagrams that supports the most important artifacts. It is based on mapping a composition of SysML activity diagrams to the input language of the probabilistic symbolic model checker called “PRISM”. To prove the soundness of our mapping approach, we capture the underlying semantics of both the SysML activity diagrams and their generated PRISM code. We found that the probabilistic equivalence relation between both semantics preserve the satisfaction of the system requirements. Finally, we demonstrate the effectiveness of our approach by presenting real case studies.     

Verifying concurrent probabilistic systems using probabilistic-epistemic logic specifications

In this paper, we address the problem of verifying probabilistic and epistemic properties in concurrent probabilistic systems expressed in PCTLK. PCTLK is an extension of the Probabilistic Computation Tree Logic (PCTL) augmented with Knowledge (K). In fact, PCTLK enjoys two epistemic modalities K_i for knowledge and \(Pr_{\triangledown b}K_{i}\) for probabilistic knowledge. The approach presented for verifying PCTLK specifications in such concurrent systems is based on a transformation technique. More precisely, we convert PCTLK model checking into the problem of model checking Probabilistic Branching Time Logic (PBTL), which enjoys path quantifiers in the range of adversaries. We then prove that model checking a formula of PCTLK in concurrent probabilistic programs is PSPACE-complete. Furthermore, we represent models associated with PCTLK logic symbolically with Multi-Terminal Binary Decision Diagrams (MTBDDs), which are supported by the probabilistic model checker PRISM. Finally, an application, namely the NetBill online shopping payment protocol, and an example about synchronization illustrated through the dining philosophers problem are implemented with the MTBDD engine of this model checker to verify probabilistic epistemic properties and evaluate the practical complexity of this verification.     

LTL概率模型检验工具的实现与优化

概率模型检验建立在非概率模型检验技术的基础上,不仅能够对系统进行定性的验证,还能够定量判断系统满足相关性质的概率,具有广泛的适用性。LTL概率模型检验算法的复杂度较高,达到双重指数级别,现有的工具如PRISM与MRMC均不支持对LTL性质的验证。针对这个问题,通过对原有的LTL概率模型检验算法进行优化,实现了一个高效的LTL概率模型检验工具。通过对比实验验证了该工具的有效性。     

A formal analysis of bluetooth device discovery

This paper presents a formal analysis of the device discovery phase of the Bluetooth wireless communication protocol. The performance of this process is the result of a complex interaction between several devices, some of which exhibit random behaviour. We use probabilistic model checking and, in particular, the tool PRISM to compute the best- and worst-case performance of device discovery: the expected time for the process to complete and the expected power consumption. We illustrate the utility of performing an exhaustive, low-level analysis to produce exact results in contrast to simulation techniques, where additional probabilistic assumptions must be made. We demonstrate an example of how seemingly innocuous assumptions can lead to incorrect performance estimations. We also analyse the effectiveness of improvements made between versions 1.1 and 1.2 of the Bluetooth specification.     

基于概率模型检测和遗传算法的基因调控网络的无限范围优化控制

基因调控网络是一类基本且重要的生物网络,通过对其进行控制可以实现生物系统功能的调节。在生物系统中,通过外部的干预控制构造关于基因调控网络的控制理论成为了非常热门的研究主题。目前,作为一种重要的网络模型,带有干扰且上下文相关的概率布尔网络已经被广泛地应用于基因调控网络优化控制问题的研究中。针对无限范围的优化控制问题,文中提出了一种基于概率模型检测和遗传算法的近似最优控制策略的计算方法。首先,该方法将无限范围控制中定义的期望总成本归约为离散时间马尔科夫链上的平稳状态回报;然后,构建包含固定控制策略的带有干扰且上下文相关的概率布尔网络模型,采用带回报属性的时序逻辑公式表示固定控制策略的成本,采用概率模型检测器PRISM进行自动计算。进一步,采用遗传算法,将固定控制策略编码为遗传算法解空间中的个体,基于其控制成本,定义个体的适应度值,将PRISM作为求解器,通过在解空间上迭代地执行遗传操作获取近似最优解。将所提方法应用于WNT5A网络中,实验结果证明了该方法的有效性。     

Probabilistic symbolic model checking with PRISM: a hybrid approach

In this paper we present efficient symbolic techniques for probabilistic model checking. These have been implemented in PRISM, a tool for the analysis of probabilistic models such as discrete-time Markov chains, continuous-time Markov chains and Markov decision processes using specifications in the probabilistic temporal logics PCTL and CSL. Motivated by the success of model checkers such as SMV which use BDDs (binary decision diagrams), we have developed an implementation of PCTL and CSL model checking based on MTBDDs (multi-terminal BDDs) and BDDs. Existing work in this direction has been hindered by the generally poor performance of MTBDD-based numerical computation, which is often substantially slower than explicit methods using sparse matrices. The focus of this paper is a novel hybrid technique which combines aspects of symbolic and explicit approaches to overcome these performance problems. For typical examples, we achieve a dramatic improvement over the purely symbolic approach. In addition, thanks to the compact model representation using MTBDDs, we can verify systems an order of magnitude larger than with sparse matrices, while almost matching or even beating them for speed.     

Using PRISM model checker as a validation tool for an analytical model of IEEE 802.15.4 networks

Commonly, simulation by using an existing network simulation tool or a simulator developed from scratch is employed for validation of analytical network performance models. An analytical model of star-shaped wireless sensor networks has been proposed in the literature in which, upon receiving a query from the coordinator, each sensor node sends one data frame to it by executing the IEEE 802.15.4 unslotted carrier-sense multiple access with collision avoidance algorithm. The model consists of expressions for calculation of the probability of successful receipt of the data at a certain time and the like. The authors of the model have written a special simulation program in order to validate the expressions. Our aim was to employ probabilistic model checker PRISM instead. PRISM only requires the user to formally specify the network as a kind of state machine and the queries about the probabilities sought in the form of logical formulas. It finds the probabilities automatically and can present them on graphs. We show how to specify the networks formally in such a way that all the expressions from the analytical model can be validated with PRISM. For those networks containing a few nodes, the validation can be carried out by normal model checking, which, in contrast to the simulation, always checks all the possible network behaviors, whereas statistical model checking can be used for the larger networks.     

使用模型检测解决概率布尔网络优化控制

系统生物学期望对复杂生物系统建立一个真实的、可计算的模型,以便于以系统的角度去理解生物系统的演变过程。在系统生物学中,一个重要的主题是通过外部的干预控制发展关于基因调控网络的控制理论,以作为未来基因治疗技术。目前,布尔网络及其扩展的概率布尔网络已经被广泛用于对基因调控网络进行建模。在控制问题的研究中,概率布尔控制网络的状态迁移本质上构成一条有限状态空间的离散时间马尔科夫决策过程。依据马尔科夫决策过程的理论,通过概率模型检测方法解决网络中有限范围优化控制问题和无限范围优化控制问题。针对带有随机干扰且上下文相关的概率布尔控制网络,使用概率模型检测器PRISM对其进行形式化建模,然后将两类优化控制问题描述为相应的时序逻辑公式,最后通过模型检测寻找出最优解。实验结果表明,提出的方法可以有效地用于生物网络的分析和优化控制。     

基于Web Services的网格数据传输子系统

数据是网格环境中一类特殊的资源,它的流动、管理以及统一视图是网格系统的重要组成部分。该文分析数据的特点并设计实现一个基于FTP协议,支持多线程、断点续传、异常识别、连接维持以及第三方传输和“中转不落地传输”两种传输模式的数据传输子系统。该子系统提供了数据的动、静态部署能力,为在超级计算机和集群上运行作业提供数据支持,形成在各个网格资源上所部署的数据的统一视图,方便对数据的进一步操作。