Formal analysis of DeGroot Influence Problems using probabilistic model checking

DeGroot learning is a model of opinion diffusion and formation in a social network. We examine the behaviour of the DeGroot learning model when external strategic players that aim to influence the opinion formation process are introduced. More specifically, we consider the case of a single decision maker and that of two competing players, with a fixed number of possible influence actions for each of them. In the former case, the DeGroot model takes the form of a Markov Decision Process (MDP), while in the latter case it takes the form of a Stochastic Game (SG). These models are solved using probabilistic model checking techniques, as well as other solution techniques beyond model checking. The viability of our analysis is attested on a well-known social network, the Zachary’s karate club. Finally, the evaluation of influence in a social network simultaneously with the decision maker’s cost is supported, which is encoded as a multi-objective model checking problem.     

Parameterized model checking for security policy analysis

International Journal on Software Tools for Technology Transfer - We explain how a parameterized model checking technique can be exploited to mechanize the analysis of access control policies. The...     

密码协议的符号模型检测及分析

对密码协议模型检测的方法作了理论上的研究,并用SMV检测工具给出了一个实际分析的例子。结果表明,利用符号模型检测方法分析并发现密码协议重放攻击的漏洞是一种行之有效的方法。     

Security analysis of GTRBAC and its variants using model checking

Security analysis is a formal verification technique to ascertain certain desirable guarantees on the access control policy specification. Given a set of access control policies, a general safety requirement in such a system is to determine whether a desirable property is satisfied in all the reachable states. Such an analysis calls for the use of formal verification techniques. While formal analysis on traditional Role Based Access Control (RBAC) has been done to some extent, recent extensions to RBAC lack such an analysis. In this paper, we consider the temporal RBAC extensions and propose a formal technique using timed automata to perform security analysis by analyzing both safety and liveness properties. Using safety properties one ensures that something bad never happens while liveness properties show that some good state is also achieved. GTRBAC is a well accepted generalized temporal RBAC model which can handle a wide range of temporal constraints while specifying different access control policies. Analysis of such a model involves a process of mapping a GTRBAC based system into a state transition system. Different reduction rules are proposed to simplify the modeling process depending upon the constraints supported by the system. The effect of different constraints on the modeling process is also studied.     

On using data abstractions for model checking refinements

In this paper we investigate how standard model checkers can be applied to checking refinement relationships between Z specifications. The major obstacle to such a use are the (potentially) infinite data domains in specifications. Consequently, we examine the application of data abstraction techniques for reducing the infinite to a finite state space. Since data abstractions do, however, decrease the amount of information in a specification, refinement can—in general—not be proven on the abstractions anymore, it can only be disproved. The model checker can thus be used to generate counter examples to a refinement relationship. Here, we show how abstract specifications can be systematically constructed (from a given data abstraction) and how a standard model checker (FDR) can be applied to find counter examples in case when refinement is absent. We especially discuss the applicability of the construction method: it constructs abstract specifications which are either upward or downward simulations of the original specifications, and depending on the operations in the specification and the data abstraction chosen, such a construction might succeed or fail. The construction abstracts both the input/output as well as the state.     

基于CTL模型检测的胃腺癌核心路径形式化验证

胃腺癌是消化系统最常见的恶性肿瘤,死亡率居消化道各类癌症之首。其发生发展是多步骤、多因素参与的复杂过程,涉及到多种蛋白分子的改变以及信号通路的异常,但其确切发病机制目前尚不清楚,研究其发病机理,探索有效治疗方法一直是医学研究最重要的课题之一。因此,对胃腺癌信号转导网络的研究有助于阐明其发病机制。目前,在胃腺癌的发生发展过程中由于基因的改变而导致细胞功能的变化,以及癌细胞环境因子通过作用于其受体和信号转导通路而影响其他正常细胞的功能。胃腺癌的信号转导网络非常复杂,通过对胃腺癌信号转导网络离散值模型的分析和验证,说明靶向胃腺癌信号通路或蛋白治疗的优越性。应用符号模型检测技术自动分析靶向信号通路或蛋白是如何影响胃腺癌细胞命运,了解胃腺癌的发生发展机理,从中找到潜在靶点,为治疗胃腺癌提供建议,使研制新的抗癌药物成为可能。     

Local model checking and protocol analysis

This paper describes a local model-checking algorithm for the alternation-free fragment of the modal mu-calculus that has been implemented in the Concurrency Factory and discusses its application to the analysis of a real-time communications protocol. The protocol considered is RETHER, a software-based, real-time Ethernet protocol developed at SUNY at Stony Brook. Its purpose is to provide guaranteed bandwidth and deterministic, periodic network access to multimedia applications over commodity Ethernet hardware. Our model-checking results show that (for a particular network configuration) RETHER makes good on its bandwidth guarantees to real-time nodes without exposing non-real-time nodes to the possibility of starvation. Our data also indicate that, in many cases, the state-exploration overhead of the local model checker is significantly smaller than the total amount that would result from a global analysis of the protocol. In the course of specifying and verifying RETHER, we also identified an alternative design of the protocol that warranted further study due to its potentially smaller run-time overhead in servicing requests for data transmission. Again, using local model checking, we showed that this alternative design also possesses the properties of interest. This observation points out one of the often-overlooked benefits of formal verification: by forcing designers to understand their designs rigorously and abstractly, these techniques often enable the designers to uncover interesting design alternatives.     

Feasibility analysis for robustness quantification by symbolic model checking

We propose and investigate a robustness evaluation procedure for sequential circuits subject to particle strikes inducing bit-flips in memory elements. We define a general fault model, a parametric reparation model and quantitative measures reflecting the robustness capability of the circuit with respect to these fault and reparation models. We provide algorithms to compute these metrics and show how they can be interpreted in order to better understand the robustness capability of several circuits (a simple circuit coming from the VIS distribution, circuits from the itc-99 benchmarks and a CAN-Bus interface).     

E-process design and assurance using model checking

Trust in e-commerce is difficult to establish and maintain. Almost daily, news headlines cover some incident, causing users to question e-commerce systems' trustworthiness. Strong e-process design and implementation is the first line of defense against errors, fraud and hacking. Minimizing program faults in business operations is critical for an e-business's survival. Carefully designed and implemented code can handle most expected situations, so these e-processes often function well within their defined boundaries, but guaranteeing correct processing under all circumstances is extremely difficult, if not impossible. Hidden flaws and errors, triggered only under unexpected, hard-to-anticipate scenarios, lead to subtle mistakes and even catastrophic failures. The authors use an online ticket sales example to illustrate the potential of model checking (an advanced formal method) for economically finding certain flaws. Model checking is a powerful verification method that determines whether a system model satisfies certain specifications under all circumstances. It can locate subtle but critical flaws that conventional design and assurance methods, such as testing and simulation, often miss     

Formal concept analysis based user model for distributed systems

User profile has contributed to customize user access and adjusts applications to its needs. In this respect, automatically building of user profiles issue is an important research area. Nevertheless, standardizing these profiles in terms of representation and acquisition schemes, more especially in large scale systems like Peer-to-Peer systems (P2P), is a complex task. In this paper, we introduce a distributed user profile modelling approach based on user search topics history without the need of any external knowledge resource (e.g., ontology). This model learns from past interests to guess correlations between user requests, associated topics, relevant documents and nodes (i.e., peers) to enhance any information retrieval process. The solution is based on an extension of Formal Concept Analysis (FCA) theory. We also study, the integration of our model in query routing (i.e., content discovery) and results aggregation processes for P2P systems. Carried out experiments, performed under a P2P simulator environment, showed that our model outperforms its competitors in terms of effectiveness and efficiency.     

Learning and analysis of sensors behavior in IoT systems using statistical model checking

Software Quality Journal - Analyzing the behavior of sensors is becoming one of the key challenges due to their increasing use for decision making in IoT systems. The paper proposes an approach for...     

Bayesian analysis of robust Poisson geometric process model using heavy-tailed distributions

We propose a robust Poisson geometric process model with heavy-tailed distributions to cope with the problem of outliers as it may lead to an overestimation of mean and variance resulting in inaccurate interpretations of the situations. Two heavy-tailed distributions namely Student’s t and exponential power distributions with different tailednesses and kurtoses are used and they are represented in scale mixture of normal and scale mixture of uniform respectively. The proposed model is capable of describing the trend and meanwhile the mixing parameters in the scale mixture representations can detect the outlying observations. Simulations and real data analysis are performed to investigate the properties of the models.     

Scheduling analysis based on model checking for multiprocessor real-time systems

Real-time systems (RTS) are omnipresent in several domains. The trend is to use multiprocessor architecture to satisfy the timing constraints of such systems. The model-checking methods have proven to be useful for making the development process reliable at a high abstraction level. Based on this approach, the present paper proposes a new technique for scheduling analysis of a partitioned multiprocessor RTS. Starting from a model with dynamic priority time Petri Nets modeling the system, we have proposed a generation of a reduced states graph. Thus, through the properties of the graph the schedulability is checked. Our approach provides an implementation of a Partition Checker tool, which produces an affirmation of the schedulability or a counterexample in the case of non-schedulable system to reduce the SW/HW space exploration.     

Role updating in information systems using model checking

The role-based access control (RBAC) has significantly simplified the management of users and permissions in information systems. In dynamic environments, systems are constantly undergoing changes, and accordingly, the associated configurations need to be updated in order to reflect the systems’ security evolutions. However, such updating process is generally complicated as the resulting system state is expected to meet necessary constraints. This paper presents an approach for assisting administrators to make a desirable update, in light of changes in RBAC systems. We propose a formalization of the update approach, investigate its properties, and develop an updating algorithm based on model checking techniques. Our experimental results demonstrate the effectiveness of the proposed approach.     

Scaling model checking of dataraces using dynamic information

Dataraces in multithreaded programs often indicate severe bugs and can cause unexpected behaviors when different thread interleavings are executed. Because dataraces are a cause for concern, many works have dealt with the problem of detecting them. Works based on dynamic techniques either report errors only for dataraces that occur in the current interleaving, which limits their usefulness, or produce many spurious dataraces. Works based on model checking search exhaustively for dataraces and thus can reveal even those that occur in rarely executed paths. However, the applicability of model checking is limited because the large number of thread interleavings in realistic multithreaded programs causes state space explosion. In this work, we combine the two techniques in a hybrid scheme which overcomes these difficulties and enjoys the advantages of both worlds. Our hybrid technique succeeds in providing thread interleavings that prove the existence of dataraces in realistic programs. The programs we experimented with cannot be checked using either an ordinary industrial strength model checker or bounded model checking.     

Extending typestate checking using conditional liveness analysis

The authors present a practical extension to typestate checking, which is capable of proving programs free of uninitialized variable errors even when these programs contain conditionally initialized variables where the initialization of a variable depends upon the equality of one or more tag variables to a constant. The user need not predeclare the relationship between a conditionally initialized variable and its tags, and this relationship may change from one point in the program to another. The technique generalizes liveness analysis to conditional liveness analysis. Like typestate checking, this technique incorporates a dataflow analysis algorithm in which each point in a program is labeled with a lattice point describing statically tracked information, including the initialization of variables. The labeling is then used to check for programming errors such as referencing a variable which may be uninitialized     

Analysing a stream authentication protocol using model checking

In this paper, we consider how one can analyse a stream authentication protocol using model checking techniques. In particular, we will be focusing on the Timed Efficient Stream Loss-tolerant Authentication Protocol, TESLA. This protocol differs from the standard class of authentication protocols previously analysed using model checking techniques in the following interesting way: an unbounded stream of messages is broadcast by a sender, making use of an unbounded stream of keys; the authentication of the n-th message in the stream is achieved on receipt of the n+1-th message. We show that, despite the infinite nature of the protocol, it is possible to build a finite model that correctly captures its behaviour.     

An evaluation framework for energy aware buildings using statistical model checking

Cyber-physical systems are to be found in numerous applications throughout society.The principal barrier to develop trustworthy cyber-physical systems is the lack of expressive modelling and specification formalisms supported by efficient tools and methodologies.To overcome this barrier,we extend in this paper the modelling formalism of the tool UPPAAL-SMC to stochastic hybrid automata,thus providing the expressive power required for modelling complex cyber-physical systems.The application of Statistical Model Checking provides a highly scalable technique for analyzing performance properties of this formalisms.A particular kind of cyber-physical systems are Smart Grids which together with Intelligent,Energy Aware Buildings will play a major role in achieving an energy efficient society of the future.In this paper we present a framework in UPPAAL-SMC for energy aware buildings allowing to evaluate the performance of proposed control strategies in terms of their induced comfort and energy profiles under varying environmental settings(e.g.weather,user behavior etc.).To demonstrate the intended use and usefulness of our framework,we present an application to the Hybrid Systems Verification Benchmark.     

Test generation from P systems using model checking

This paper presents some testing approaches based on model checking and using different testing criteria. First, test sets are built from different Kripke structure representations. Second, various rule coverage criteria for transitional, non-deterministic, cell-like P systems, are considered in order to generate adequate test sets. Rule based coverage criteria (simple rule coverage, context-dependent rule coverage and variants) are defined and, for each criterion, a set of LTL (Linear Temporal Logic) formulas is provided. A codification of a P system as a Kripke structure and the sets of LTL properties are used in test generation: for each criterion, test cases are obtained from the counterexamples of the associated LTL formulas, which are automatically generated from the Kripke structure codification of the P system. The method is illustrated with an implementation using a specific model checker, NuSMV.