Fundamental Limits of Covert queueing under Busy-Period Observations

• Bob's covert-queueing problem asks how many additional jobs he can serve without detection from the busy-period statistics Willie observes.Source: §I · p. 1
• Willie observes either the number of jobs served or the duration of each busy period.Source: §I · p. 1
• Earlier work established square-root achievability for the job-count statistic but only constant-order achievability for busy-period duration.Source: §I · p. 2
• Bob can covertly serve on the order of √n additional jobs under either statistic, while serving asymptotically more enables reliable detection.Source: §I · p. 2
• The paper characterizes the square-root scaling constants for both statistics, called covert queueing constants.Source: §I · p. 2

• The M/M/1 queue has arrival rate λ and service rate µ, with λ < µ ensuring stability.Source: 1) Preliminaries on the M/M/1 Queue · p. 2
• A session begins with an arrival to an empty queue and ends when service leaves the system empty.Source: 1) Preliminaries on the M/M/1 Queue · p. 2
• The number of jobs served and the duration of a session are i.i.d. across sessions, with their M/M/1 distributions specified.Source: 1) Preliminaries on the M/M/1 Queue · p. 2

• f(x) = O(g(x)) means the ratio |f(x)|/|g(x)| has a finite limit superior.Source: 2) Order Notations · p. 2
• f(x) = Ω(g(x)) means the ratio |f(x)|/|g(x)| has a positive limit superior.Source: 2) Order Notations · p. 2
• f(x) = Θ(g(x)) holds when f(x) is both O(g(x)) and Ω(g(x)).Source: 2) Order Notations · p. 2
• f(x) = o(g(x)) is defined by a ratio |f(x)|/|g(x)| tending to zero.Source: 2) Order Notations · p. 2

• Willie's jobs arrive at rate λw < µ, while Bob may add an independent Poisson stream at rate λb; stability is assumed.Source: B. Problem formulation · p. 2
• For each session, Willie receives either the number of jobs served or the session duration.Source: B. Problem formulation · pp. 2–3
• Willie tests whether Bob added jobs using the observed statistics, with false-alarm and missed-detection probabilities defining detection error.Source: B. Problem formulation · pp. 2–3
• Definition 1 says Bob’s additional arrival process is δ-covert with respect to statistic U if a condition holds, but the cited excerpt stops before giving that condition.Source: B. Problem formulation · p. 3
• The objectives are to characterize the maximum covert-job scaling and the covert queueing constants for the job-count and duration statistics.Source: B. Problem formulation · p. 3

III. MAIN RESULTS

• For uniformly stable insertion rates, Proposition 1 establishes a scaling relation between the insertion rate and expected additional jobs for U = X or U = Y.The section treats the number of jobs served and session duration as the two statistics.Source: §III · pp. 3–4
• The section presents separate results for the job-count statistic U = X and duration statistic U = Y.It introduces the scaling relation before treating the two statistics in separate subsections.Source: §III · p. 3
• A Taylor expansion around γ = 0 is used to characterize KL divergence between nearby distributions, assuming smoothness in γ.The divergence is minimized at γ = 0 because the two distributions coincide there and KL divergence is nonnegative.Source: §III · p. 4

A. Results on Statistic U = X

• The earlier result in [20, Theorem 1] established achievable √n scaling for X, while this section establishes the maximum scaling.The present result adds a converse to the earlier achievability result.Source: A. Results on Statistic U = X · p. 4
• √n is the maximum achievable scaling of expected covert jobs under Statistic-1; any strictly larger scaling lets Willie detect insertion with vanishing error.The converse is paired with the achievable bound to establish the square-root law.Source: A. Results on Statistic U = X · p. 4
• Under each hypothesis, the distribution of the jobs-served statistic X is parameterized by ρj.The statistic is the number of jobs served during a session.Source: A. Results on Statistic U = X · p. 4
• Theorem 1 characterizes KX for an M/M/1 queue with 0 < λw < μ under the asymptotic KL-divergence covertness constraint.The paper states that KX is finite and strictly positive.Source: A. Results on Statistic U = X · p. 4
• The achievability argument chooses an insertion rate that satisfies the asymptotic KL-divergence covertness constraint.The section then combines achievability and converse bounds to complete the proof.Source: A. Results on Statistic U = X · p. 5

B. Results on Statistic U = Y

• The analysis approximates DKL(g0∥g1) by a second-order Taylor expansion, a nontrivial step because the densities contain a Bessel-function term.The detailed derivation is placed in Appendix E.Source: B. Results on Statistic U = Y · p. 5
• The optimal expected number of covert jobs under duration observations follows a Θ(√n) square-root law.The result is established for the busy-period duration statistic Y.Source: B. Results on Statistic U = Y · p. 5
• Insertions above the square-root scale admit a Willie test whose total error tends to zero.The duration-statistic result connects the above-scale insertion condition to asymptotic detectability.Source: B. Results on Statistic U = Y · p. 5
• Theorem 2 characterizes the duration-based covert queueing constant KY for an M/M/1 queue with 0 < λw < µ.The theorem refers to C(λw, µ), defined separately.Source: B. Results on Statistic U = Y · p. 5

IV. DISCUSSION

• Because Y given X has the same conditional distribution under both hypotheses, the data processing inequality makes X at least as informative as Y in KL divergence.The conditional distribution is Erlang with shape k and rate µ.Source: §IV · p. 6
• Every arrival-rate sequence covert under X is also covert under Y, implying the optimal expected covert-job count under Y cannot be smaller.The argument compares the admissible sequence sets and then their normalized limits.Source: §IV · p. 6
• KY is at least KX, so duration observations permit at least as many covert jobs as job-count observations under the same covertness constraint.The numerical comparison for µ = 5 confirms KX ≤ KY throughout the plotted λw range.Source: §IV · p. 6
• Both constants appear to diverge as λw approaches 0 or µ, but their limiting behavior is left for future work.The discussion says an analytical characterization requires further investigation of J(λw, µ) and C(λw, µ).Source: §IV · p. 6

V. CONCLUSION AND FUTURE WORK

• For either statistic, the maximum expected number of covert jobs over n busy periods is Θ(√n); inserting ω(√n) jobs enables reliable detection.The conclusion covers job counts X and busy-period durations Y.Source: §V · p. 6
• KX ≤ KY, so the number of jobs served is at least as informative for detecting covert traffic as busy-period length.Fig. 1 compares KX and KY for µ = 5.Source: §V · p. 6, Figure 1 · p. 7
• Open directions include characterizing the constants’ endpoint behavior and extending the analysis beyond Poisson insertions and single-server queues.The endpoints are λw → 0 and λw → µ−; the corresponding asymptotics of J(λw, µ) and C(λw, µ) are also open.Source: §V · p. 6

APPENDIX A PROOF FOR PROPOSITION 1

• Under H1, the proof computes covert jobs by using Bob’s share of arrivals, λb(n)/(λw + λb(n)), alongside the session’s total jobs.It then considers the expected number of Bob jobs over n sessions.Source: Appendix A · p. 7

APPENDIX B PROOF OF PROPOSITION 2

• The converse proof uses a threshold test on S; under uniform stability, the alternative-hypothesis variance is O(1).The proof bounds false alarms and missed detections to establish the converse.Source: Appendix B · pp. 7–8

OF STATISTIC-1

• For Statistic-1, the proof approximates the KL divergence by a second-order Taylor expansion around λb = 0.The expansion uses the distributions under H0 and H1.Source: OF STATISTIC-1 · pp. 8–9

A. Proof of Achievability for statistic U = Y

• For duration observations, achievability is shown by bounding the KL divergence across independent busy periods and choosing an insertion rate meeting the asymptotic covertness condition.The proof states that an insertion rate satisfying the derived condition is achievable.Source: A. Proof of Achievability for… · p. 9

B. Proof of Converse

• The converse analyzes Willie’s threshold test using hypothesis means and variances, with Chebyshev bounds for false alarms and missed detections, to complete Proposition 3.The proof assumes uniform queue stability and chooses a threshold sequence between the hypotheses’ means.Source: B. Proof of Converse · p. 9

APPENDIX E PROOF OF LEMMA 2

• The Lemma 2 proof establishes a second-order Taylor expansion of the KL divergence around λb = 0, with a nonnegative quadratic coefficient.It restricts the expansion to 0 < λw < μ and insertion rates bounded by η < μ − λw.Source: Appendix E · pp. 10, 12

APPENDIX F PROOF OF THEOREM 2

• Theorem 2’s proof establishes an achievable insertion-rate bound under the asymptotic KL-divergence covertness constraint, then combines achievability and converse bounds.The converse considers sequences of insertion rates satisfying that constraint.Source: Appendix F · pp. 12–13