Search

Covert communication considers the ability of transmitter Alice to communicate reliably to receiver Bob without being detected by warden Willie. Previous work has generally considered a discrete-time model, and, in the standard Alice-Bob-Willie scenario, it has been shown that a discrete-time model captures the salient aspects of the underlying continuous-time covert communications system. However, in the presence of a jammer assisting Alice, where it has been shown in previous work that Alice can achieve a positive covert rate on a discrete-time model, we demonstrate here that a straightforward extension of the discrete-time construction to the continuous-time system does not guarantee a positive covert rate, hence indicating that the discrete-time model does not capture the salient aspects of the continuous-time system in such a scenario. This is because Willie is able to exploit excess bandwidth for co-channel interference suppression, as we demonstrate with an interference cancellation receiver. Hence, for the case when Alice is assisted by an uninformed jammer, we consider the continuous-time channel directly and study whether efficient covert communication can still be achieved against any possible receiver that Willie might employ. By presenting and characterizing an approach much different than that suggested by previous work for discrete-time systems in such a scenario, we establish that $\mathcal {O}(WT)$ information bits can be transmitted covertly and reliably on a continuous-time channel of asymptotic bandwidth $W$ in $T$ seconds, regardless of the receiver that Willie employs. This is done for two separate scenarios: 1) when there is perfect frame synchronization between Alice and the jammer’s signals; 2) when there is no frame synchronization between Alice and the jammer’s signals. Numerical results are provided to validate the theory. [ABSTRACT FROM AUTHOR]

Online monitoring user cardinalities in graph streams is fundamental for many applications such as anomaly detection. These graph streams may contain edge duplicates and have a large number of user-item pairs, which makes it infeasible to exactly compute user cardinalities due to limited computational and memory resources. Existing methods are designed to approximately estimate user cardinalities, but their accuracy highly depends on complex parameters and they cannot provide anytime-available estimation. To address these problems, we develop novel bit/register sharing algorithms, which use a bit/register array to build a compact sketch of all users’ connected items. Our algorithms exploit the dynamic properties of the bit/register arrays (e.g., the fraction of zero bits in the bit array) to significantly improve the estimation accuracy, and have low time complexity $O(1)$ O (1) to update the estimations for a new user-item pair. In addition, our algorithms are simple and easy to use, without requirements to tune any parameter. Furthermore, we extend our methods to detect super spreaders with large cardinalities in real-time. We evaluate the performance of our methods on real-world datasets. The experimental results demonstrate that our methods are several times more accurate and faster than state-of-the-art methods using the same amount of memory. [ABSTRACT FROM AUTHOR]

The problem of sequentially detecting the emergence of a moving anomaly in a sensor network is studied. In the setting considered, the data-generating distribution at each sensor can alternate between a nonanomalous distribution and an anomalous distribution. Initially, the observations of each sensor are generated according to its associated nonanomalous distribution. At some unknown but deterministic time instant, a moving anomaly emerges in the network. It is assumed that the number as well as the identity of the sensors affected by the anomaly may vary with time. While a sensor is affected, it generates observations according to its corresponding anomalous distribution. The goal of this work is to design detection procedures to detect the emergence of such a moving anomaly as quickly as possible, subject to constraints on the frequency of false alarms. The problem is studied in a quickest change detection framework where it is assumed that the spatial evolution of the anomaly over time is unknown but deterministic. We modify the worst-path detection delay metric introduced in prior work on moving anomaly detection to consider the case of a moving anomaly of varying size. We then establish that a weighted dynamic cumulative sum type test is first-order asymptotically optimal under a delay-false alarm formulation for the proposed worst-path delay as the mean time to false alarm goes to infinity. We conclude by presenting numerical simulations to validate our theoretical analysis. [ABSTRACT FROM AUTHOR]

The Transmission Control Protocol (TCP) utilizes a congestion avoidance and control mechanism as a preventive measure against congestive collapse and as an adaptive measure in the presence of changing network conditions. The set of available congestion control algorithms is diverse, and while many have been studied from empirical and simulation perspectives, there is a notable lack of analytical work for some variants. To gain more insight into the dynamics of these algorithms, we: (1) propose a general modeling scheme consisting of a set of functional differential equations of retarded type (RFDEs) and of the congestion window as a function of time; (2) apply this scheme to TCP Reno and demonstrate its equivalence to a previous, well known model for TCP Reno; (3) show applications of the new framework to the widely-deployed congestion control algorithm TCP CUBIC, for which analytical models are few and limited; as well as to H-TCP, another high-speed congestion control algorithm; and (4) validate the model using simulations. Our modeling framework yields a fluid model for window- or rate-based congestion control variants. From a theoretical analysis of this model with TCP CUBIC, we discover that CUBIC is locally uniformly asymptotically stable – a property of the algorithm previously unknown. Through further analysis, we derive a sufficient condition for H-TCP’s stability, but observe via a numerical analysis and simulations that H-TCP rarely converges to an equilibrium and is usually not asymptotically stable in practical high-speed settings. [ABSTRACT FROM AUTHOR]

Network flow fingerprinting can be used to de-anonymize communications on anonymity systems such as Tor by linking the ingress and egress segments of anonymized connections. Assume Alice and Bob have access to the input and the output links of an anonymous network, respectively, and they wish to collaboratively reveal the connections between the input and the output links without being detected by Willie who protects the network. Alice generates a codebook where each codeword is a unique fingerprint indicating a sequence of inter-packet delays, and shares it only with Bob. To trace each flow, Alice selects a fingerprint and manipulates the packet timings of the flow to follow the packet timings suggested by the fingerprint, and Bob extracts the fingerprints from it after it passes through the network. We model the network as parallel $M/M/1$ queues where each queue is shared by a flow $f_{i}$ from Alice to Bob and other flows independent of $f_{i}$. Packet timings of the flows are governed by independent Poisson processes. Assuming all input flows have equal packet rates and that Bob observes only flows with fingerprints, we first present two scenarios: 1) Alice fingerprints all the flows and 2) Alice fingerprints a subset of the flows, unknown to Willie. Then, we extend the construction and analysis to the case of arbitrary flow rates and the case where Bob observes flows with and without fingerprints. For each scenario, we derive the number of flows that Alice and Bob can trace by fingerprinting. [ABSTRACT FROM AUTHOR]

Covert communication conceals the existence of the transmission from a watchful adversary. We consider the fundamental limits for covert communications via packet insertion over packet channels whose packet timings are governed by a renewal process of rate $\lambda $. Authorized transmitter Jack sends packets to authorized receiver Steve, and covert transmitter Alice wishes to transmit packets to covert receiver Bob without being detected by watchful adversaries Willie 1 and Willie 2. Willies cannot authenticate the source of the packets or collaborate. Hence, each Willie looks for statistical anomalies in the packet stream from Jack to Steve to attempt detection of unauthorized packet insertion. First, we consider a special case where the packet timings are governed by a Poisson process and we show that Alice can covertly insert $\mathcal {O}(\sqrt {\lambda T})$ packets for Bob in a time interval of length $T$ ; conversely, if Alice inserts $\omega (\sqrt {\lambda T})$ packets, she will be detected by Willie 1 or Willie 2 with high probability. Then, we extend our results to general renewal channels and show that in a stream of $N$ packets transmitted by Jack, Alice can covertly insert $\mathcal {O}(\sqrt {N})$ packets; if she inserts $\omega (\sqrt {N})$ packets, she will be detected by Willie 1 or Willie 2, with high probability. [ABSTRACT FROM AUTHOR]

In this paper, we establish a framework for low probability of detection (LPD) communication from a sequential change-point detection (SCPD) perspective, where a transmitter, Alice, wants to hide her transmission to a receiver, Bob, from an adversary, Willie. The new framework facilitates modeling LPD communication and further evaluating its performance under the condition that Willie has no prior knowledge about when the transmission from Alice might start and that Willie wants to determine the existence of the communication as quickly as possible in a real-time manner. We consider three different sequential tests, i.e., the Shewhart, the cumulative sum (CUSUM), and the Shiryaev-Roberts (SR) tests, to model Willie’s detection process. Communication is said to be covert if it ceases before being detected by Willie with high probability. Covert probability defined as the probability that Willie is not alerted during Alice’s transmission is investigated. We formulate an optimization problem aiming at finding the transmit power and transmission duration so as to maximize the total amount of information that can be transmitted subject to a high covert probability. Under the Shewhart test, closed-form approximations of the optimal solutions are derived, which will approximate the solutions obtained from exhaustive search. As for the CUSUM and SR tests, we provide effective algorithms to search for the optimal solutions. Numeric results are presented to show the performance of LPD communication. [ABSTRACT FROM AUTHOR]

The problem of quickest detection of dynamic events in networks is studied. At some unknown time, an event occurs, and a number of nodes in the network are affected by the event, in that they undergo a change in the statistics of their observations. It is assumed that the event is dynamic, in that it can propagate along the edges in the network, and affect more and more nodes with time. The event propagation dynamics is assumed to be unknown. The goal is to design a sequential algorithm that can detect a “significant” event, i.e., when the event has affected no fewer than $\eta $ nodes, as quickly as possible, while controlling the false alarm rate. Fully connected networks are studied first, and the results are then extended to arbitrarily connected networks. The designed algorithms are shown to be adaptive to the unknown propagation dynamics, and their first-order asymptotic optimality is demonstrated as the false alarm rate goes to zero. The algorithms can be implemented with linear computational complexity in the network size at each time step, which is critical for online implementation. Numerical simulations are provided to validate the theoretical results. [ABSTRACT FROM AUTHOR]