1,721,049 research outputs found
Approximating Imperfect Cryptography in a Formal Model
No full textWe present a formal view of cryptography that overcomes the usual assumptions of formal models for reasoning about security of computer systems, i.e. perfect cryptography and Dolev-Yao adversary model. In our framework, equivalence among formal cryptographic expressions is parameterized by a computational adversary that may exploit weaknesses of the cryptosystem to cryptanalyze ciphertext with a certain probability of success. To validate our approach, we show that in the restricted setting of ideal cryptosystems, for which the probability of guessing information that the Dolev-Yao adversary cannot derive is negligible, the computational adversary is limited to the allowed behaviors of the Dolev-Yao adversary
Team bisimilarity, and its associated modal logic, for BPP nets
Full text linkBPP nets, a subclass of finite Place/Transition Petri nets, are equipped with an efficiently decidable, truly concurrent, bisimulation-based, behavioral equivalence, called team bisimilarity. This equivalence is a very intuitive extension of classic bisimulation equivalence (over labeled transition systems) to BPP nets and it is checked in a distributed manner, without necessarily building a global model of the overall behavior of the marked BPP net. An associated distributed modal logic, called team modal logic (TML, for short), is presented and shown to be coherent with team bisimilarity: two markings are team bisimilar if and only if they satisfy the same TML formulae. As the process algebra BPP (with guarded summation and guarded body of constants) is expressive enough to represent all and only the BPP nets, we provide algebraic laws for team bisimilarity as well as a finite, sound and complete, axiomatization
An algebraic theory of nondeterministic finite automata
No full textA process algebra is proposed, whose semantics maps a term to a nondeterministic finite automaton (NFA, for short). We prove a representability theorem: for each NFA N, there exists a process algebraic term p such that its semantics is an NFA isomorphic to N. Moreover, we provide a concise axiomatization of language equivalence: two NFAs N1 and N2 recognize the same language if and only if the associated terms p1 and p2, respectively, can be equated by means of a set of axioms, comprising 7 axioms plus 3 conditional axioms, only
A study on team bisimulation and H-team bisimulation for BPP nets
No full textA subclass of finite Petri nets, called BPP nets (acronym of Basic Parallel Processes), was recently equipped with an efficiently decidable, truly concurrent, bisimulation-based, behavioral equivalence, called team bisimilarity. This equivalence is a very intuitive extension of classic bisimulation equivalence (over labeled transition systems) to BPP nets and it is checked in a distributed manner. This paper has three goals. First of all, we provide BPP nets with various causality-based observational semantics, notably a novel semantics, called causal-net bisimilarity. Then, we define a variant semantics, called h-team bisimilarity, coarser than team bisimilarity, for which we adapt the modal logic characterization and the axiomatization of team bisimilarity. Then, we complete the study about team bisimilarity and h-team bisimilarity, by comparing them with the causality-based semantics we have introduced: the main results are that team bisimilarity coincides with causal-net bisimilarity, while h-team bisimilarity with fully-concurrent bisimilarity
Causal Semantics for BPP Nets with Silent Moves
Full text linkBPP nets, a subclass of finite Place/Transition Petri nets, are equipped with some causal behavioral semantics, which are variations of fully-concurrent bisimilarity [3], inspired by weak [28] or branching bisimulation [12] on labeled transition systems. Then, we introduce novel, efficiently decidable, distributed semantics, inspired by team bisimulation [17] and h-team bisimulation [19], and show how they relate to these variants of fully-concurrent bisimulation
A Classification of Security Properties for Process Algebras
No full textSeveral information flow security definitions, proposed in the literature, are generalized and adapted to the model of labelled transition systems. This very general model has been widely used as a semantic domain for many process algebras, e.g. CCS. As a by-product, we provide a process algebra similar to CCS with a set of security notions, hence relating these two areas of concurrency research. A classification of these generalized security definitions is presented, taking into account also the additional property of input totality, which can influence this taxonomy. We also show that some of these security properties are composable w.r.t. the operators of parallelism and action restriction
Formal Performance Modelling and Evaluation of an Adaptive Mechanism for Packetised Audio over the Internet
No full textA case study is presented which concerns the design of an adaptive mechanism for packetised audio for use over the Internet. During the design process, the audio mechanism was modelled with the stochastically timed process algebra EMPA and analysed via simulation by the EMPA based software tool TwoTowers in order to predict the percentage of packets that are received in time for being played out. The predicted performance figures obtained from the algebraic model illustrated in advance the adequacy of the approach adopted in the design of the audio playout delay control mechanism. Based on these performance figures, it was possible to implement and develop the complete mechanism without incurring additional costs due to the late discovery of unexpected errors or inefficiency. Performance results obtained from experiments conducted on the field confirmed the predictive simulative results
Decidability of Two Truly Concurrent Equivalences for Finite Bounded Petri Nets
Full text linkWe prove that (strong) fully-concurrent bisimilarity and causal-net bisimilarity are decidable for finite bounded Petri nets. The proofs are based on a generalization of the ordered marking proof technique that Vogler used to demonstrate that (strong) fully-concurrent bisimilarity (or, equivalently, historypreserving bisimilarity) is decidable on finite safe nets
A theory of processes with durational actions
No full textA new bisimulation based semantics, called performance equivalence, is proposed for a process algebra equipped with the TCSP parallel operator. This semantics relies on the basic assumption that actions are time-consuming, where their duration is statically fixed. Performance equivalence equates systems whenever they perform the same actions in the same amount of time, thus introducing a simple form of performance evaluation in process algebras. A comparison with other equivalences is provided; in particular, we show that performance equivalence is strictly finer than step bisimulation equivalence and strictly coarser than partial ordering bisimulation equivalence. © 1995
- …
