Discrete probabilistic programs (DPPs) provide a highly expressive formalism for compactly defining arbitrary finite probabilistic models. This expressivity comes at a price: DPP inference is PSPACE-hard. In this work, we show that DPP inference only takes polynomial time for programs that are "structurally simple". More precisely, inference can be performed in polynomial time when the primal graph of each function appearing in the probabilistic program has bounded treewidth, and the inverse acceptance probability is at most exponential in the size of the probabilistic program. Existing algorithms do not achieve this performance guarantee. Our method relies on finding suitable decompositions, algebraisations, of the string diagrams underlying DPPs, employing existing algorithms for tree decompositions. This is independent of the probabilistic setting of DPPs and has direct applications to many problems, such as evaluating queries on relational databases and cybersecurity risk assessment via attack trees.

Effective risk management in cybersecurity requires a thorough understanding of the interplay between attacker capabilities and defense strategies. Attack-Defense Trees (ADTs) are a commonly used methodology for representing this interplay; however, previous work in this domain has only focused on analyzing metrics such as cost, damage, or time from the perspective of the attacker. This approach provides an incomplete view of the system, as it neglects to model defender attributes: in real-world scenarios, defenders have finite resources for countermeasures and are similarly constrained. In this paper, we propose a novel framework that incorporates defense metrics into ADTs, and we present efficient algorithms for computing the Pareto front between defense and attack metrics. Our methods encode both attacker and defender metrics as semirings, allowing our methods to be used for many metrics such as cost, damage, and skill. We analyze tree-structured ADTs using a bottom-up approach and general ADTs by translating them into binary decision diagrams. Experiments on randomly generated ADTS demonstrate that both approaches effectively handle ADTs with several hundred nodes.

Abstract Systematic spare management is important to optimize the twin goals of high reliability and low costs. However, existing approaches to spare management do not incorporate a detailed analysis of the effect on the absence of spares on the system’s reliability. In this work, we combine fault tree analysis with statistical model checking to model spare part management as a stochastic priced timed game automaton (SPTGA). We use Uppaal Stratego to find the number of spares that minimizes the total costs due to downtime and spare purchasing. The resulting SPTGA model can then additionally be analyzed according to a wide range of other metrics, including expected availability. We apply these techniques to the emergency shutdown system of a research nuclear reactor. In this case study, the failure probability is low, so we change the settings of Uppaal Stratego setting to obtain reliable results about rare events. We consider both a single subsystem and the combination of two subsystems. In both situations, our methods find the optimal number of spares, minimizing cost while ensuring an expected availability of 99.96% and 99.93%, respectively.

Federated learning (FL) emerged as a paradigm designed to improve data privacy by enabling data to reside at its source, thus embedding privacy as a core consideration in FL architectures, whether centralized or decentralized. Contrasting with recent findings by Pasquini et al., which suggest that decentralized FL does not empirically offer any additional privacy or security benefits over centralized models, our study provides compelling evidence to the contrary. We demonstrate that decentralized FL, when deploying distributed optimization, provides enhanced privacy protection - both theoretically and empirically - compared to centralized approaches. The challenge of quantifying privacy loss through iterative processes has traditionally constrained the theoretical exploration of FL protocols. We overcome this by conducting a pioneering in-depth information-theoretical privacy analysis for both frameworks. Our analysis, considering both eavesdropping and passive adversary models, successfully establishes bounds on privacy leakage. In particular, we show information theoretically that the privacy loss in decentralized FL is upper bounded by the loss in centralized FL. Compared to the centralized case where local gradients of individual participants are directly revealed, a key distinction of optimization-based decentralized FL is that the relevant information includes differences of local gradients over successive iterations and the aggregated sum of different nodes’ gradients over the network. This information complicates the adversary’s attempt to infer private data. To bridge our theoretical insights with practical applications, we present detailed case studies involving logistic regression and deep neural networks. These examples demonstrate that while privacy leakage remains comparable in simpler models, complex models like deep neural networks exhibit lower privacy risks under decentralized FL. Extensive numerical tests further validate that decentralized FL is more resistant to privacy attacks, aligning with our theoretical findings.

Attack Trees (ATs) are a widely used tool for security analysis. ATs can be employed in quantitative security analysis through metrics, which assign a security value to an AT. Many different AT metrics exist, and there exist multiple general definitions that aim to study a wide variety of AT metrics at once. However, these all have drawbacks: they do not capture all metrics, and they do not easily generalize to extensions of ATs. In this paper, we introduce a definition of AT metrics based on category theory, specifically operad algebras. This encompasses all previous definitions of AT metrics, and is easily generalized to extensions of ATs. Furthermore, we show that under easily expressed operad-theoretic conditions, existing metric calculation algorithms can be extended in considerable generality.

Abstract Attack trees are important for security, as they help to identify weaknesses and vulnerabilities in a system. Quantitative attack tree analysis supports a number security metrics, which formulate important KPIs such as the shortest, most likely and cheapest attacks. A key bottleneck in quantitative analysis is that the values are usually not known exactly, due to insufficient data and/or lack of knowledge. Fuzzy logic is a prominent framework to handle such uncertain values, with applications in numerous domains. While several studies proposed fuzzy approaches to attack tree analysis, none of them provided a firm definition of fuzzy metric values or generic algorithms for computation of fuzzy metrics. In this work, we define a generic formulation for fuzzy metric values that applies to most quantitative metrics. The resulting metric value is a fuzzy number obtained by following Zadeh’s extension principle, obtained when we equip the basis attack steps, i.e., the leaves of the attack trees, with fuzzy numbers. In addition, we prove a modular decomposition theorem that yields a bottom-up algorithm to efficiently calculate the top fuzzy metric value.

Privacy-preserving distributed average consensus has received significant attention recently due to its wide applicability. Based on the achieved performances, existing approaches can be broadly classified into perfect accuracy-prioritized approaches such as secure multiparty computation (SMPC), and worst-case privacy-prioritized approaches such as differential privacy (DP). Methods of the first class achieve perfect output accuracy but reveal some private information, while methods from the second class provide privacy against the strongest adversary at the cost of a loss of accuracy. In this paper, we propose a general approach named adaptive differentially quantized subspace perturbation (ADQSP) which combines quantization schemes with so-called subspace perturbation. Although not relying on cryptographic primitives, the proposed approach enjoys the benefits of both accuracy-prioritized and privacy-prioritized methods and is able to unify them. More specifically, we show that by varying a single quantization parameter the proposed method can vary between SMPC-type performances and DP-type performances. Our results show the potential of exploiting traditional distributed signal processing tools for providing cryptographic guarantees. In addition to a comprehensive theoretical analysis, numerical validations are conducted to substantiate our results.

Attack trees (ATs) are a widely deployed modelling technique to categorize potential attacks on a system. An attacker of such a system aims at doing as much damage as possible, but might be limited by a cost budget. The maximum possible damage for a given cost budget is an important security metric of a system. In this paper, we find the maximum damage given a cost budget by modelling this problem with ATs, both in deterministic and probabilistic settings. We show that the general problem is NP-complete, and provide heuristics to solve it. For general ATs these are based on integer linear programming. However when the AT is tree-structured, then one can instead use a faster bottom-up approach. We also extend these methods to other problems related to the cost-damage tradeoff, such as the cost-damage Pareto front.

Numerous analysis methods for quantitative attack tree analysis have been proposed. These algorithms compute relevant security metrics, i.e., performance indicators that quantify how good the security of a system is; typical metrics being the most likely attack, the cheapest, or the most damaging one. However, existing methods are only geared towards specific metrics or do not work on general attack trees. This article classifies attack trees in two dimensions: proper trees versus directed acyclic graphs (i.e., with shared subtrees); and static versus dynamic gates. For three out of these four classes, we propose novel algorithms that work over a generic attribute domain, encompassing a large number of concrete security metrics defined on the attack tree semantics; dynamic attack trees with directed acyclic graph structure are left as an open problem. We also analyse the computational complexity of our methods.

We consider the setting of publishing data without leaking sensitive information. We do so in the framework of Robust Local Differential Privacy (RLDP). This ensures privacy for all distributions of the data in an uncertainty set. We formulate the problem of finding the optimal data release protocol as a robust optimization problem. By deriving closed-form expressions for the duals of the constraints involved we obtain a convex optimization problem. We compare the performance of four possible optimization problems depending on whether or not we require robustness in i) utility and ii) privacy.

We consider data release protocols for data$X= (S, U)$, where$S$is sensitive; the released data$Y$contains as much information about$X$as possible, measured as$\mathrm{I}(X;Y)$, without leaking too much about$S$. We introduce the Robust Local Differential Privacy (RLDP) framework to measure privacy. This framework relies on the underlying distribution of the data, which needs to be estimated from available data. Robust privacy guarantees ensure privacy for all distributions in a confidence set based on this estimate. We also present three algorithms that construct RLDP protocols from a given dataset. One of these approximates the confidence set by a polytope and uses results from robust optimisation to yield high utility release protocols. However, it relies on vertex enumeration and becomes computationally infeasible for large input alphabets. The other two algorithms are low-complexity and build on randomised response. Experiments verify that all three algorithms offer significantly improved utility over regular LDP.

The application of differential privacy in privacy-preserving data analysis has gained momentum in recent years. In particular, it provides an effective solution for the construction of privacy-preserving classifiers, in which one party owns the data and another party is interested in obtaining a classifier model from this data. While several approaches have been proposed in the literature to employ differential privacy for the construction of classifiers, an understanding of the difference in performance of these classifiers is currently missing. This knowledge enables the data owner and the analyst to select the most appropriate classification algorithm and training parameters in order to guarantee high privacy requirements while minimizing the loss of accuracy. In this study, we investigate the impact of the use of differential privacy on three well-known classifiers, i.e., Naïve Bayes, SVM, and Decision Tree classifiers. To this end, we show how these classifiers can be trained in a differential privacy setting and perform extensive experiments to evaluate the effect of this privacy enforcement on their performance.

When collecting information, local differential privacy (LDP) relieves the concern of privacy leakage from users' perspective, as user's private information is randomized before sent to the aggregator. We study the problem of recovering the distribution over a numerical domain while satisfying LDP. While one can discretize a numerical domain and then apply the protocols developed for categorical domains, we show that taking advantage of the numerical nature of the domain results in better trade-off of privacy and utility. We introduce a new reporting mechanism, called the square wave (SW) mechanism, which exploits the numerical nature in reporting. We also develop an Expectation Maximization with Smoothing (EMS) algorithm, which is applied to aggregated histograms from the SW mechanism to estimate the original distributions. Extensive experiments demonstrate that our proposed approach, SW with EMS, consistently outperforms other methods in a variety of utility metrics.