Wyniki wyszukiwania - BazTech

1

Using Hoare Logic in a Process Algebra Setting

Bergstra J. A., Middelburg C. A.

Fundamenta Informaticae

|

2021

|

Vol. 179, nr 4

321--344

EN

This paper concerns the relation between process algebra and Hoare logic. We investigate the question whether and how a Hoare logic can be used for reasoning about how data change in the course of a process when reasoning equationally about that process. We introduce an extension of ACP (Algebra of Communicating Processes) with features that are relevant to processes in which data are involved, present a Hoare logic for the processes considered in this process algebra, and discuss the use of this Hoare logic as a complement to pure equational reasoning with the equational axioms of the process algebra.

2

Persistent Stochastic Non-Interference

Hillston Jane, Marin Andrea, Piazza Carla, Rossi Sabina

Fundamenta Informaticae

|

2021

|

Vol. 181, nr 1

1--35

EN

In this paper, we study an information flow security property for systems specified as terms of a quantitative Markovian process algebra, namely the Performance Evaluation Process Algebra (PEPA). We propose a quantitative extension of the Non-Interference property used to secure systems from the functional point view by assuming that the observers are able to measure also the timing properties of the system, e.g., the response time of certain actions or its throughput. We introduce the notion of Persistent Stochastic Non-Interference (PSNI) based on the idea that every state reachable by a process satisfies a basic Stochastic Non-Interference (SNI) property. The structural operational semantics of PEPA allows us to give two characterizations of PSNI : one based on a bisimulation-like equivalence relation inducing a lumping on the underlying Markov chain, and another one based on unwinding conditions which demand properties of individual actions. These two different characterizations naturally lead to efficient methods for the verification and construction of secure systems. A decision algorithm for PSNI is presented and an application of PSNI to a queueing system is discussed.

3

Causal Reasoning for Safety in Hennessy Milner Logic

Caltais Georgiana, Mousavi Mohammad Reza, Singh Hargurbir

Fundamenta Informaticae

|

2020

|

Vol. 173, nr 2-3

217--251

EN

Determining and computing root causes in system failures is a significant issue in science and engineering. In this paper, we introduce a notion of causality for explaining counter-examples in system analysis based on formal models. The counter-examples are produced by checking for hazardous situations expressed in the Hennessy-Milner Logic, in the context of Labelled Transition System models. We also introduce CauseJMu, a tool for automatically identifying such causal computations within a system model. CauseJMu relies on encoding causality in terms of an extension of Hennessy-Milner Logic to recursive formulae with data. The encodings enable deciding whether a certain computation is causal or not, using the mCRL2 model checker.

4

Reliable Restricted Process Theory

Ghassemi Fatemeh, Fokkink Wan

Fundamenta Informaticae

|

2019

|

Vol. 165, nr 1

1--41

EN

Malfunctions of a mobile ad hoc network (MANET) protocol caused by a conceptual mistake in the protocol design, rather than unreliable communication, can often be detected only by considering communication among the nodes in the network to be reliable. In Restricted Broadcast Process Theory, which was developed for the specification and verification of MANET protocols, the communication operator is lossy. Replacing unreliable with reliable communication invalidates existing results for this process theory. We examine the effects of this adaptation on the semantics of the framework with regard to the non-blocking property of communication in MANETs, the notion of behavioral equivalence relation and its axiomatization. To utilize our complete axiomatization for analyzing the correctness of protocols at the syntactic level, we introduce a precongruence relation which abstracts away from a sequence of multi-hop communications, leading to an application-level action preconditioned by a multi-hop constraint over the topology. We illustrate the applicability of our framework through a simple routing protocol. To prove its correctness, we introduce a novel proof process, based on our precongruence relation.

5

Contradiction-Tolerant Process Algebra with Propositional Signals

Bergstra J. A., Middelburg C. A.

Fundamenta Informaticae

|

2017

|

Vol. 153, nr 1/2

29--55

EN

In a previous paper, an ACP-style process algebra was proposed in which propositions are used as the visible part of the state of processes and as state conditions under which processes may proceed. This process algebra, called ACPps, is built on classical propositional logic. In this paper, we present a version of ACPps built on a paraconsistent propositional logic which is essentially the same as CLuNs. There are many systems that would have to deal with selfcontradictory states if no special measures were taken. For a number of these systems, it is conceivable that accepting self-contradictory states and dealing with them in a way based on a paraconsistent logic is an alternative to taking special measures. The presented version of ACPps can be suited for the description and analysis of systems that deal with self-contradictory states in a way based on the above-mentioned paraconsistent logic.

6

CCS(25,12) is Turing-complete

Gorrieri R.

Fundamenta Informaticae

|

2017

|

Vol. 154, nr 1/4

145--166

EN

CCS(h,k) is the CCS subcalculus which can use at most h constants and k actions. We show that CCS(25,12) is Turing-complete by simulating Neary and Woods’ universal Turing machine with 15 states and 2 symbols.

7

A process algebraic form to represent extensive games

Gheibi O., Ramezanian R.

Control and Cybernetics

|

2015

|

Vol. 44, no. 1

129--148

EN

In this paper, we introduce an agent-based representation of games, in order to propose a compact representation for multi-party games in game theory. Our method is inspired by concepts in process theory and process algebra. In addition, we introduce an algorithm whose input is a game in the form of process algebra (proposed in this paper) and as an output, the algorithm ﬁnds the Nash equilibrium of the game in linear space complexity.

8

FSP and FLTL framework for specification and verification of middle-agents

Bădică A., Bădică C.

International Journal of Applied Mathematics and Computer Science

|

2011

|

Vol. 21, no 1

9-25

EN

Agents are a useful abstraction frequently employed as a basic building block in modeling service, information and resource sharing in global environments. The connecting of requester with provider agents requires the use of specialized agents known as middle-agents. In this paper, we propose a formal framework intended to precisely characterize types of middle-agents with a special focus on matchmakers, brokers and front-agents by formally modeling their interactions with requesters and providers. Our approach is based on capturing interaction protocols between requesters, providers and middle-agents as finite state processes represented using FSP process algebra. The resulting specifications are formally verifiable using FLTL temporal logic. The main results of this work include (i) precise specification of interaction protocols depending on the type of middle-agent (this can also be a basis for characterizing types of middle-agents), (ii) improvement of communication between designers and developers and facilitation of formal verification of agent systems, (iii) guided design and implementation of agent-based software systems that incorporate middle-agents.