The goal of (network) intrusion detection systems is to identify unauthorized or malicious activities within a computer network. In this work we consider the following theoretical model for intrusion detection systems in large data center networks. We assume that the network is modeled as a leaf-spine-architecture with$m$spine nodes and$n$leaves. In a sequence of observation periods, each spine node stores a snapshot of the communication graph and accumulates (an approximation of) the number of alerts caused by suspicious behavior. To identify the responsible malicious nodes, we apply a distributed reconstruction algorithm based on quantitative group testing: In quantitative group testing we are given a binary signal of Hamming weight$k$along with a querying method. Each query pools multiple entries of together and returns the sum of the entries in the pool. The goal is to reconstruct using as few queries as possible. Our contributions in this paper are three-fold. First we mathematically analyze a distributed reconstruction algorithm for the quantitative group testing instance induced by our intrusion detection model. In particular, we analyze the performance assuming a communication graph where each leaf sends Geom(p) many packets to the spine nodes in each time interval, where$p$is a parameter of the model. Second, we prove that our algorithm achieves a performance that is optimal up to logarithmic factors. Finally, we simulate our approach and provide empirical data that show that our approach works well in practice. The main novelty of our analysis is that the test-design is given by the communication graphs that are accumulated in multiple observation periods. This is in contrast to classical group testing where the algorithm is allowed to decide on the test design, and we believe that our analysis of non-standard test designs is of independent interest to the distributed group testing community.

We derive a sufficient condition for a sparse random matrix with given numbers of non-zero entries in the rows and columns having full row rank. The result covers both matrices over finite fields with independent non-zero entries and $\{0,1\}$-matrices over the rationals. The sufficient condition is generally necessary as well.

Epidemic spreading processes have been widely studied over the last years, with an additional boost due to the ongoing COVID-19 pandemic. However, epidemic spreading is not limited to infectious diseases; it forms the basis of understanding opinion formation processes in social networks, or models the spread of computer viruses in network security. In all of these application domains, the forward processes are typically well understood, both from a theoretical and a practical point of view. Interestingly, much less is known about the converse direction: suppose we are given “sensors” that report on the infection status, can we recover the source of the epidemic? This problem is known under the name of patient zero, rumor source detection, or finding the point of entrance in the context of intrusion detection systems. In this work we assume that the epidemic process spreads according to the classical Independent Cascade Model, and we are given sensors on edges of the communication network. We rigorously analyze under which sensor placement one can recover the source of the epidemic process. Our main contribution is an impossibility result: we formally prove a lower bound on the number of sensors required to recover the source of the epidemic process. Furthermore, we introduce a monitoring strategy that succeeds in recovering the patient zero with the minimum number of sensors possible for acyclic networks. Finally, we discuss unreliable sensor measurements and provide extensive simulations of according heuristics on realistic communication networks.

We consider the so-called Independent Cascade Model for rumor spreading or epidemic processes popularized by Kempe et al. (2003). In this model, a node of a network is the source of a rumor – it is informed. In discrete time steps, each informed node “infects” each of its uninformed neighbors with probability p. While many facets of this process are studied in the literature, less is known about the inference problem: given a number of infected nodes in a network, can we learn the source of the rumor? In the context of epidemiology this problem is often referred to as patient zero problem. It belongs to a broader class of problems where the goal is to infer parameters of the underlying spreading model. In this work we present a maximum likelihood estimator for the rumor’s source, given a snapshot of the process in terms of a set of active nodes X after t steps. Our results show that, for acyclic graphs, the likelihood estimator undergoes a phase transition as a function of $t$. We provide a rigorous analysis for two prominent classes of acyclic network, namely d-regular trees and Galton-Watson trees, and verify empirically that our heuristics work well in various general networks.

We study the group testing problem where the goal is to identify a set of k infected individuals carrying a rare disease within a population of size n, based on the outcomes of pooled tests which return positive whenever there is at least one infected individual in the tested group. We consider two different simple random procedures for assigning individuals to tests: the constant-column design and Bernoulli design. Our first set of results concerns the fundamental statistical limits. For the constant-column design, we give a new information-theoretic lower bound which implies that the proportion of correctly identifiable infected individuals undergoes a sharp “all-or-nothing” phase transition when the number of tests crosses a particular threshold. For the Bernoulli design, we determine the precise number of tests required to solve the associated detection problem (where the goal is to distinguish between a group testing instance and pure noise), improving both the upper and lower bounds of Truong, Aldridge, and Scarlett (2020). For both group testing models, we also study the power of computationally efficient (polynomial-time) inference procedures. We determine the precise number of tests required for the class of low-degree polynomial algorithms to solve the detection problem. This provides evidence for an inherent computational-statistical gap in both the detection and recovery problems at small sparsity levels. Notably, our evidence is contrary to that of Iliopoulos and Zadik (2021), who predicted the absence of a computational-statistical gap in the Bernoulli design.

Consider $n$ items, each of which is characterised by one of $d+1$ possible features in $\{0, \ldots, d\}$. We study the inference task of learning these types by queries on subsets, or pools, of the items that only reveal a form of coarsened information on the features - in our case, the sum of all the features in the pool. This is a realistic scenario in situations where one has memory or technical constraints in the data collection process, or where the data is subject to anonymisation. Related prominent problems are the quantitative group testing problem, of which it is a generalisation, as well as the compressed sensing problem, of which it is a special case. In the present article, we are interested in the minimum number of queries needed to efficiently infer the features, in the setting where the feature vector is chosen uniformly while fixing the frequencies, and one of the features, say $0$, is dominant in the sense that the number $k = n^{\theta}, \theta \in (0,1)$, of non-zero features among the items is much smaller than $n$. It is known that in this case, all features can be recovered in exponential time using no more than $O(k)$ queries. However, so far, all \emph{efficient} inference algorithms required at least $\Omega(k\ln n)$ queries, and it was unknown whether this gap is artificial or of a fundamental nature. Here we show that indeed, the previous gap between the information-theoretic and computational bounds is not inherent to the problem by providing an efficient algorithm that succeeds with high probability and employs no more than $O(k)$ measurements. This also solves a prominent open question for the quantitative group testing problem.

In the pooled data problem we are given a set of n agents, each of which holds a hidden state bit, either 0 or 1. A querying procedure returns for a query set the sum of the states of the queried agents. The goal is to reconstruct the states using as few queries as possible.In this paper we consider two noise models for the pooled data problem. In the noisy channel model, the result for each agent flips with a certain probability. In the noisy query model, each query result is subject to random Gaussian noise.Our results are twofold. First, we present and analyze for both error models a simple and efficient distributed algorithm that reconstructs the initial states in a greedy fashion. Our novel analysis pins down the range of error probabilities and distributions for which our algorithm reconstructs the exact initial states with high probability. Secondly, we present simulation results of our algorithm and compare its performance with approximate message passing (AMP) algorithms that are conjectured to be optimal in a number of related problems.

In the pooled data problem the goal is to efficiently reconstruct a binary signal from additive measurements. Given a signal$\sigma\in \{0, 1\}^{n}$, we can query multiple entries at once and get the total number of non-zero entries in the query as a result. We assume that queries are time-consuming and therefore focus on the setting where all queries are executed in parallel. For the regime where the signal is sparse such that$\Vert\sigma\Vert_{1}= o(n)$our results are twofold: First, we propose and analyze a simple and efficient greedy reconstruction algorithm. Secondly, we derive a sharp information-theoretic threshold for the minimum number of queries required to reconstruct σ with high probability. Our first result matches the performance guarantees of much more involved constructions (Karimi et al. 2019). Our second result extends a result of Alaoui et al. (2014) and Scarlett & Cevher (2017) who studied the pooled data problem for dense signals. Finally, our theoretical findings are complemented with empirical simulations. Our data not only confirm the information-theoretic thresholds but also hint at the practical applicability of our pooling scheme and the simple greedy reconstruction algorithm.

We study the Consensus problem among $n$ agents, defined as follows. Initially, each agent holds one of two possible opinions. The goal is to reach a consensus configuration in which every agent shares the same opinion. To this end, agents randomly sample other agents and update their opinion according to a simple update function depending on the sampled opinions. We consider two communication models: the gossip model and a variant of the population model. In the gossip model, agents are activated in parallel, synchronous rounds. In the population model, one agent is activated after the other in a sequence of discrete time steps. For both models we analyze the following natural family of majority processes called $j$-Majority: when activated, every agent samples $j$ other agents uniformly at random (with replacement) and adopts the majority opinion among the sample (breaking ties uniformly at random). As our main result we show a hierarchy among majority protocols: $(j+1)$-Majority (for $j > 1$) converges stochastically faster than $j$-Majority for any initial opinion configuration. In our analysis we use Strassen's Theorem to prove the existence of a coupling. This gives an affirmative answer for the case of two opinions to an open question asked by Berenbrink et al. [2017].

The group testing problem asks for efficient pooling schemes and inference algorithms that allow to screen moderately large numbers of samples for rare infections. The goal is to accurately identify the infected individuals while minimizing the number of tests. We propose the novel adaptive pooling scheme adaptive Belief Propagation (ABP) that acknowledges practical limitations such as limited pooling sizes and noisy tests that may give imperfect answers. We demonstrate that the accuracy of ABP surpasses that of individual testing despite using few overall tests. The new design comes with Belief Propagation as an efficient inference algorithm. While the development of ABP is guided by mathematical analyses and asymptotic insights, we conduct an experimental study to obtain results on practical population sizes.

Recent advances in noiseless non-adaptive group testing have led to a precise asymptotic characterization of the number of tests required for high-probability recovery in the sublinear regime$k = n^{\theta }$(with$\theta \in (0,1)$), with$n$individuals among which$k$are infected. However, the required number of tests may increase substantially under real-world practical constraints, notably including bounds on the maximum number$\Delta $of tests an individual can be placed in, or the maximum number$\Gamma $of individuals in a given test. While previous works have given recovery guarantees for these settings, significant gaps remain between the achievability and converse bounds. In this paper, we substantially or completely close several of the most prominent gaps. In the case of$\Delta $-divisible items, we show that the definite defectives (DD) algorithm coupled with a random regular design is asymptotically optimal in dense scaling regimes, and optimal to within a factor of e more generally; we establish this by strengthening both the best known achievability and converse bounds. In the case of$\Gamma $-sized tests, we provide a comprehensive analysis of the regime$\Gamma = \Theta (1)$, and again establish a precise threshold proving the asymptotic optimality of SCOMP (a slight refinement of DD) equipped with a tailored pooling scheme. Finally, for each of these two settings, we provide near-optimal adaptive algorithms based on sequential splitting, and provably demonstrate gaps between the performance of optimal adaptive and non-adaptive algorithms.

Random factor graphs provide a powerful framework for the study of inference problems such as decoding problems or the stochastic block model. Information-theoretically the key quantity of interest is the mutual information between the observed factor graph and the underlying ground truth around which the factor graph was created; in the stochastic block model, this would be the planted partition. The mutual information gauges whether and how well the ground truth can be inferred from the observable data. For a very general model of random factor graphs we verify a formula for the mutual information predicted by physics techniques. As an application we prove a conjecture about low-density generator matrix codes from [Montanari: IEEE Transactions on Information Theory 2005]. Further applications include phase transitions of the stochastic block model and the mixed $k$-spin model from physics.

Guided by the theory of graph limits, we investigate a variant of the cut metric for limit objects of sequences of discrete probability distributions. Apart from establishing basic results, we introduce a natural operation called pinning on the space of limit objects and show how this operation yields a canonical cut metric approximation to a given probability distribution akin to the weak regularity lemma for graphons. We also establish the cut metric continuity of basic operations such as taking product measures.

In the group testing problem, which goes back to the work of Dorfman (1943), we aim to identify a small set of $k\sim n^\theta$ infected individuals out of a population size $n$, $0<\theta<1$.We avail ourselves to a test procedure that can test a group of individuals, with the test returning a positive result iff at least one individual in the group is infected. All tests are conducted in parallel. The aim is to devise a test design with as few tests as possible so that the infected individuals can be identified with high probability. We establish an explicit sharp information-theoretic/algorithmic phase transition $m_{inf}$, showing that with more than $\minf$ tests the infected individuals can be identified in polynomial time, while this is impossible with fewer tests. In addition, we obtain an optimal two-stage adaptive group testing scheme. These results resolve problems prominently posed in [Aldridge et al. 2019, Johnson et al. 2018, Mézard and Toninelli 2011].

In the group testing problem we aim to identify a small number of infected individuals within a large population. We avail ourselves to a procedure that can test a group of multiple individuals, with the test result coming out positive iff at least one individual in the group is infected. With all tests conducted in parallel, what is the least number of tests required to identify the status of all individuals? In a recent test design [Aldridge et al. 2016] the individuals are assigned to test groups randomly with replacement, with every individual joining an almost equal number of groups. We pinpoint the sharp threshold for the number of tests required in this randomised design so that it is information-theoretically possible to infer the infection status of every individual. Moreover, we analyse two efficient inference algorithms. These results settle conjectures from [Aldridge et al. 2014, Johnson et al. 2019].

In the group testing problem we aim to identify a small number of infected individuals within a large population. We avail ourselves to a procedure that can test a group of multiple individuals, with the test result coming out positive iff at least one individual in the group is infected. With all tests conducted in parallel, what is the least number of tests required to identify the status of all individuals? In a recent test design [Aldridge et al. 2016] the individuals are assigned to test groups randomly, with every individual joining an equal number of groups. We pinpoint the sharp threshold for the number of tests required in this randomised design so that it is information-theoretically possible to infer the infection status of every individual. Moreover, we analyse two efficient inference algorithms. These results settle conjectures from [Aldridge et al. 2014, Johnson et al. 2019].