Exact Persistent Stochastic Non-Interference
Carla Piazza, Riccardo Romanello, Sabina Rossi · 2025
Read Exact Persistent Stochastic Non-Interference by Carla Piazza, Riccardo Romanello, Sabina Rossi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-19110.txt.
Introduction
Carla Piazza, Riccardo Romanello, and Sabina Rossi go back to a trait of stochastic systems called persistent stochastic non-interference. The trait asks that a high-level process cannot shape what a low-level viewer sees, not even in fine numeric detail. Their aim is a view of that pledge built around how well the system runs.
They bring in weak-exact equivalence, a way to match how systems act that treats quiet inner steps in a loose way while it keeps what can be seen exact. Built on it, exact persistent stochastic non-interference mirrors how the first trait is described. The new form takes the same bisimulation-based and unwinding-style descriptions, and keeps much the same way its parts fit as a whole. The team present this match as a firm base to reason on interference in stochastic process algebras.
Catalog record
| CREATOR | Carla Piazza, Riccardo Romanello, Sabina Rossi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-19110
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Exact Persistent Stochastic Non-Interference Carla Piazza, Riccardo Romanello, Sabina Rossi Abstract Persistent Stochastic Non-Interference (PSNI) was introduced to capture a quantitative security property in stochastic process algebras, ensuring that a high-level process does not influence the observable behaviour of a low-level component, as formalised via lumpable bisimulation. In this work, we revisit PSNI from a performance-oriented perspective and propose a new characterisation based on a refined behavioural relation. We introduce weak-exact equivalence , which extends exact equivalence with a relaxed treatment of internal ( τ \tau ) actions, enabling precise control over quantitative observables while accommodating unobservable transitions. Based on this, we define Exact PSNI (EPSNI), a variant of PSNI characterised via weak-exact equivalence. We show that EPSNI admits the same bisimulation-based and unwinding-style characterisations as PSNI, and enjoys analogous compositionality properties. These results confirm weak-exact equivalence as a robust foundation for reasoning about non-interference in stochastic systems. 1 Introduction Formal notions of non-interference have long been central to the specification and analysis of information flow properties in secure systems. Traditionally studied in deterministic or nondeterministic process models, non-interference ensures that high-level (secret) actions do not affect the observable behaviour of low-level (public) components. More recently, attention has turned to quantitative settings, where systems are described using stochastic process algebras, and the need arises to reason not only about qualitative properties but also about the performance and probabilistic characteristics of a system’s execution. In this context, the recent work of Hillston, Piazza, and Rossi [ 10 ] introduced the notion of Persistent Stochastic Non-Interference (PSNI), a security property formulated within the PEPA process algebra [ 8 ] . PSNI leverages the theory of lumpability for Markov chains to define a compositional and performance-aware form of non-interference. Specifically, PSNI ensures that the behaviour of a low-level process remains indistinguishable to an external observer regardless of the high-level environment in which it is placed. The notion is persistent in that it requires this indistinguishability to hold at every reachable state, not just at the initial configuration. PSNI admits multiple characterisations, including a bisimulation-based formulation and a set of unwinding-style local conditions, and it has been shown to be preserved under key operations of the PEPA calculus. Building on this foundation, the aim of this work is to re-express PSNI using a more fine-grained behavioural equivalence that more directly captures the quantitative structure of stochastic systems. Our starting point is the classical notion of exact equivalence , which requires two processes to exhibit the same apparent rates and to behave identically in all contexts. Exact equivalence provides a strong notion of behavioural indistinguishability, particularly suited to performance modeling, as it ensures that two processes can be interchanged without affecting any quantitative measure derived from the underlying Markov process. It thus seemed a natural candidate for reformulating the PSNI property in a more precise way. However, applying exact equivalence directly to the setting of non-interference raises a subtle challenge. In particular, the presence of internal ( \tau ) actions—which are intended to be unobservable—clashes with the strict matching requirements of exact equivalence. When internal transitions differ across components, exact equivalence is too rigid to identify them, even when their observable behaviour is identical. As a consequence, exact equivalence fails to support the abstraction necessary for reasoning about security properties in systems where internal actions encode confidential or implementation-specific behaviour. To overcome this limitation, we introduce a new equivalence relation, which we call weak-exact equivalence . This relation extends exact equivalence by relaxing its requirements for \tau -transitions. While it continues to enforce matching of apparent rates and incoming transition rates for visible actions, it allows for a controlled discrepancy in internal behaviour, provided that such differences do not affect observability at the level of equivalence classes. The key intuition is that weak-exact equivalence preserves the precise quantitative structure of a system, while abstracting away from internal transitions in a way that remains compatible with security analysis. With this new equivalence in place, we define a corresponding security property, Exact Persistent Stochastic Non-Interference (EPSNI), which mirrors the structure of PSNI but uses weak-exact equivalence as its semantic foundation. We show that EPSNI admits two out of the three characterisations of PSNI: a semantic definition quantifying over high-level contexts and a bisimulation-based reformulation that avoids universal quantification. We further prove that EPSNI is preserved under PEPA operators such as prefix and hiding on low-level actions, and that it supports a notion of steady-state independence between high-level behaviour and low-level observations. These results demonstrate that EPSNI provides a robust and expressive framework for reasoning about non-interference in stochastic systems, with strong guarantees on both performance preservation and security. Compared to PSNI, EPSNI offers a stricter form of behavioural indistinguishability, capturing finer-grained aspects of process interaction while maintaining compatibility with internal abstraction. At the same time, the similarity of its structural and compositional properties confirms that weak-exact equivalence is well-suited as a semantic foundation for quantitative security analysis in stochastic models. Structure of the paper. In Section 2 , we introduce the process algebra PEPA, its structural operational semantics, and the observation equivalence named weak-exact equivalence . The notion of Exact Persistent Stochastic Non-Interference ( \mathit{EPSNI} ) and its characterizations are presented in Section 4 . In Section 5 , we prove some compositionality results and other properties of \mathit{EPSNI} . Section 6 concludes the paper. 2 The Calculus PEPA (Performance Evaluation Process Algebra) [ 8 ] is an algebraic calculus enhanced with stochastic timing information which may be used to calculate performance measures as well as prove functional system properties. The basic elements of PEPA are components and activities . Each activity is represented by a pair (\alpha,r) where \alpha is a label, or action type , and r is its activity rate , that is the parameter of a negative exponential distribution determining its duration. We assume that there is a countable set, {\cal A} , of possible action types, including a distinguished type, \tau , which can be regarded as the unobservable type. Activity rates may be any positive real number, or the distinguished symbol \top which should be read as unspecified . The syntax for PEPA terms is defined by the grammar: \begin{array}[]{cclccl}N&::=&(\alpha,r).N\mid N+N\mid X\\[2.84526pt] P&::=&N\mid P/A\mid P\raisebox{-4.30554pt}{$\;\stackrel{{\scriptstyle\mbox{\large$\rhd\!\!\!\lhd$}}}{{\scriptscriptstyle A}}\,$}P\end{array} where N denotes a sequential component , X is a constant from a countable set \mathcal{X} , A\subset\mathcal{A} is a set of actions, and P denotes a model component . We write {\cal C} for the set of all possible components. \dfrac{}{(\alpha,r).N\xrightarrow{(\alpha,r)}N} \dfrac{N\xrightarrow{(\alpha,r)}N^{\prime}}{X\xrightarrow{(\alpha,r)}N^{\prime}} (X\stackrel{{\scriptstyle\mbox{{\tiny def}}}}{{=}}N) \dfrac{N\xrightarrow{(\alpha,r)}N^{\prime}}{N+M\xrightarrow{(\alpha,r)}N^{\prime}} \dfrac{M\xrightarrow{(\alpha,r)}M^{\prime}}{N+M\xrightarrow{(\alpha,r)}M^{\prime}} \dfrac{P\xrightarrow{(\alpha,r)}P^{\prime}}{P/A\xrightarrow{(\alpha,r)}P^{\prime}/A} (\alpha\not\in A) \dfrac{P\xrightarrow{(\alpha,r)}P^{\prime}}{P/A\xrightarrow{(\tau,r)}P^{\prime}/A} (\alpha\in A) \dfrac{P\xrightarrow{(\alpha,r)}P^{\prime}}{P\raisebox{-4.30554pt}{$\;\stackrel{{\scriptstyle\mbox{\large$\rhd\!\!\!\lhd$}}}{{\scriptscriptstyle A}}\,$}Q\xrightarrow{(\alpha,r)}P^{\prime}\raisebox{-4.30554pt}{$\;\stackrel{{\scriptstyle\mbox{\large$\rhd\!\!\!\lhd$}}}{{\scriptscriptstyle A}}\,$}Q} (\alpha\not\in A) \dfrac{Q\xrightarrow{(\alpha,r)}Q^{\prime}}{P\raisebox{-4.30554pt}{$\;\stackrel{{\scriptstyle\mbox{\large$\rhd\!\!\!\lhd$}}}{{\scriptscriptstyle A}}\,$}Q\xrightarrow{(\alpha,r)}P\raisebox{-4.30554pt}{$\;\stackrel{{\scriptstyle\mbox{\large$\rhd\!\!\!\lhd$}}}{{\scriptscriptstyle A}}\,$}Q^{\prime}} (\alpha\not\in A) \dfrac{P\xrightarrow{(\alpha,r_{1})}P^{\prime}\ \ Q\xrightarrow{(\alpha,r_{2})}Q^{\prime}}{P\raisebox{-4.30554pt}{$\;\stackrel{{\scriptstyle\mbox{\large$\rhd\!\!\!\lhd$}}}{{\scriptscriptstyle A}}\,$}Q\xrightarrow{(\alpha,R)}P^{\prime}\raisebox{-4.30554pt}{$\;\stackrel{{\scriptstyle\mbox{\large$\rhd\!\!\!\lhd$}}}{{\scriptscriptstyle A}}\,$}Q^{\prime}} R=\dfrac{r_{1}}{r_{\alpha}(P)}\dfrac{r_{2}}{r_{\alpha}(Q)}\ \mathrm{min}(r_{\alpha}(P),r_{\alpha}(Q)) (\alpha\in A) Table 1: Operational semantics for PEPA components Structural Operational Semantics. Table 1 gives the structural operational semantics for PEPA. Component (\alpha,r).N carries out the activity (\alpha,r) of type \alpha at rate r and subsequently behaves as N . When a=(\alpha,r) , component (\alpha,r).N may be written as a.N . Component N+M represents a system which may behave either as N or as M . N+M enables all the current activities of both N and M . The first activity to complete decides whether N or M will proceed. The other component of the