Fundamental Limits of Covert Packet Insertion

Ramin Soltani, Dennis Goeckel, Don Towsley, Amir HoumansadrIEEE Trans. Communications 2019 · DOI · OpenReview

Abstract

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 adversary Willie. Willie cannot authenticate the source of the packets. Hence, he 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})$, she will be detected by Willie 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 with high probability.

Introduction

Standard security focuses on secrecy (encryption) or anonymity (hiding identities). Covert communication goes a step further: it aims to hide the very existence of a transmission. In this scenario, an authorized user (Jack) is sending packets to another (Steve). A covert sender (Alice) wants to "piggyback" on this stream to send her own packets to a covert receiver (Bob). A watchful adversary (Willie) monitors the channel. While Willie cannot decrypt the packets or authenticate their source, he knows the statistical "rhythm" (the inter-packet delays) of Jack’s legitimate traffic. If Alice simply injects too many packets, she will disrupt this rhythm, allowing Willie to detect the anomaly. This research establishes the fundamental limit: exactly how many packets can Alice sneak in before she is caught?

Methods and Network Settings

The authors analyze the problem using a binary hypothesis testing framework. Willie must decide between $H_0$ (Alice is silent) and $H_1$ (Alice is transmitting). The study considers two primary network configurations to evaluate Willie's detection capabilities based on his location in the network.

Network settings for covert packet insertion. In Setting 1, Willie monitors the link between Alice and Bob. In Setting 2, Willie monitors the link between Bob and Steve.

Poisson and Renewal Channels

  • Poisson Channels: For traffic where inter-packet delays (IPDs) follow an exponential distribution, Alice generates her own low-rate Poisson stream and merges it with Jack's. The sum of two independent Poisson processes remains a Poisson process, which Alice exploits to maintain statistical invisibility.
  • General Renewal Channels: Since merging renewal processes is mathematically complex, the authors propose a two-phase scheme. First, Bob builds a buffer of Jack's packets. Then, Alice replaces some of Jack's packets with her own, and Bob uses his buffer to "fill the gaps," ensuring the outgoing stream matches the original statistical distribution intended by Jack.

Key Results: The Square Root Law

The most significant insight is that covert capacity scales with $\sqrt{N}$ (or $\sqrt{T}$ for time). This "Square Root Law" suggests a universal limit for hiding information in statistical processes, mirroring results found in other covert communication domains like AWGN channels.

  • Poisson Limit: In a time interval $T$ with traffic rate $\lambda$, Alice can covertly insert $O(\sqrt{\lambda T})$ packets. Exceeding this leads to near-certain detection as $T \to \infty$.
  • Renewal Limit: For general renewal processes, Alice can covertly insert $O(\sqrt{N})$ packets into a stream of $N$ legitimate packets.
  • The "Cleaning" Receiver: In Setting 2, where Willie is located after Bob, Bob can effectively "clean" the channel. By removing Alice's packets and re-timing Jack's packets using a buffer, Bob can make the communication completely invisible to an observer further down the line.

Limitations and Future Work

The model assumes Willie has perfect knowledge of Jack's traffic distribution. In practice, Willie might need to estimate these parameters, potentially increasing Alice's covert capacity. Furthermore, the renewal model assumes independent and identically distributed (i.i.d.) delays, whereas real network traffic often exhibits burstiness or long-range dependence. Future research will explore general point processes and scenarios with variable legitimate traffic rates to further generalize these fundamental limits.

Summary updated

Abstract

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 adversary Willie. Willie cannot authenticate the source of the packets. Hence, he 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})$, she will be detected by Willie 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 with high probability.
BibTeX
@article{soltani2019fundamental,
  author = {Ramin Soltani and Dennis Goeckel and Don Towsley and Amir Houmansadr},
  title = {{Fundamental Limits of Covert Packet Insertion}},
  journal = {IEEE Transactions on Communications},
  year = {2019},
  doi = {10.1109/tcomm.2020.2980788},
}
Figure