Bo Jiang
email: bjiang@sjtu.edu.cn

Philippe Nain
email: philippe.nain@inria.fr

Don Towsley
email: towsley@cs.umass.edu

Covert Cycle Stealing in a Single FIFO Server

Keywords: Cycle stealing, Covert communication, Queue

Consider a setting where Willie generates a Poisson stream of jobs and routes them to a single server that follows the first-in first-out discipline. Suppose there is an adversary Alice, who desires to receive service without being detected. We ask the question: what is the number of jobs that she can receive covertly, i.e. without being detected by Willie? In the case where both Willie and Alice jobs have exponential service times with respective rates µ 1 and µ 2 , we demonstrate a phase-transition when Alice adopts the strategy of inserting a single job probabilistically when the server idles : over n busy periods, she can achieve a covert throughput, measured by the expected number of jobs covertly inserted, of O( √ n) when µ 1 < 2µ 2 , O( n/ log n) when µ 1 = 2µ 2 , and O(n µ2/µ1 ) when µ 1 > 2µ 2 . When both Willie and Alice jobs have general service times we establish an upper bound for the number of jobs Alice can execute covertly. This bound is related to the Fisher information. More general insertion policies are also discussed.

Introduction

This paper considers the following problem. Willie has a sequence of jobs that arrive at a first-in first-out (FIFO) queue with a single server, whose processing rate is known to Willie. There exists another actor, Alice, who wants to sneak jobs into the queue for the purpose of stealing processing cycles from Willie. This paper asks the following question: can Alice process her jobs without Willie being able to determine this occurrence beyond making a random guess and, if she can, what is her achievable job processing rate? Answers to this question may apply to several scenarios. Alice could administer a data center, contract to provide Willie with a server with a guaranteed performance, and then resell some of the processing cycles [START_REF] Emeakaroha | Casvid: Application level monitoring for SLA violation detection in clouds[END_REF]. Similar considerations apply to network contracts. Willie could own a home computer and Alice could install malware for the purpose of stealing computational resources.

In order to address this question of covert cycle stealing, we adopt the following model. Willie's jobs arrive according to a Poisson process to a FIFO queue served by a single server with a specified processing rate.

Service times of Willie's jobs are assumed to be independent and identically distributed (iid) according to a general distribution. Alice can insert jobs as she wishes. Her service times are also iid coming from a general distribution that may differ from that of Willie's. Once an Alice job starts service, it must remain in service until completion; this can interfere with the processing of Willie's jobs. Last, both Willie and Alice know their own and the other party's service time distributions and can observe the arrival and departure times of Willie's jobs.

We formulate the problem as a statistical hypothesis testing problem where Willie's task is to determine whether or not Alice is stealing cycles, based on observed arrivals and departures. We study the Insert-at-End-of-Busy-Period (IEBP) policy, where Alice (probabilistically) inserts a single job each time a Willie busy period (to be defined) ends. We obtain several results, of which the most interesting hold for exponential services for both Willie (rate µ 1 ) and Alice (rate µ 2 ) and establish that over n busy periods, Alice can achieve a covert throughput -defined as the expected number of covertly inserted jobs -of O( √ n) when µ 1 < 2µ 2 , O( n/ log n) when µ 1 = 2µ 2 , and O(n µ 2 /µ 1 ) when µ 1 > 2µ 2 . This is interesting in part because of the phase transition at µ 1 = 2µ 2 ; earlier studies of covert communications and in steganography focused on establishing O( √ n) behavior through the control of Alice's parameters, avoiding regions in the parameter space where this behavior might not hold.

In addition to the above results for the IEBP policy when service times are exponentially distributed, we show that IEBP can also achieve a covert throughput of O( √ n) when Willie jobs have general service times and Alice jobs have (hyper-)exponential service times, under some constraints on the service rates.

The rest of the paper is organized as follows. Section 2 discusses related work. Section 3 introduces the model and needed background on hypothesis testing. Section 4 introduces the IEBP policy. Section 5 lists the main results, and some preliminary results are established in Section 6. Sections 7-9 contain the proofs of the main results. Section 10 discusses alternative policies to the IEBP policy. Concluding remarks are given in Section 11.

A word on the notations. For any a ∈ [0, 1], let ā := 1 -a. We denote the convolution of f and g by f * g and the n-fold tensor product of f with itself is denoted by f ⊗n ; recall that f ⊗n (x 1 , . . . , x n ) = n i=1 f (x i ) with x i ∈ R d (d ≥ 1). Throughout we use the shorthand notations t i:j for t i , . . . , t j for i < j, a n ∼ n b n for lim n→∞ a n /b n = 1, and lim n a n (resp. lim inf n a n , lim sup n a n ) for lim n→∞ a n (resp. lim inf n→∞ a n , lim sup n→∞ a n ).

Related work

Cycle stealing has been analyzed in the queueing literature in the context of task assignment in multi-server systems. The goal is to allow servers to borrow cycles from other servers while they are idle so as to reduce backlogs and latencies and prevent servers from being under-utilized [START_REF] Harchol-Balter | Analysis of task assignment with cycle stealing under central queue[END_REF][START_REF] Osogami | Analysis of cycle stealing with switching times and thresholds[END_REF][START_REF] Osogami | Analysis of cycle stealing with switching times and thresholds[END_REF]. These papers focus on the performance analysis of such systems, in particular, mean response times with or without the presence of switching costs. There is no attempt to hide or cover up the theft of cycles. This paper focuses on the ability of an unknown user to steal cycles without the owner of the server detecting this. Thus it is an instance of a much broader set of techniques used in digital steganography and covert communications. Steganography is the discipline of hiding data in objects such as digital images. A steganographic system modifies fixed-size finite-alphabet covertext objects into stegotext containing hidden information. A fundamental result of steganography is the square root law (SRL), O( √ n) symbols of an n symbol covertext may safely be altered to hide an O( √ n log n)-bit message [START_REF] Fridrich | Steganography in Digital Media: Principles, Algorithms, and Applications[END_REF]. Covert communications is concerned with the transfer of information in a way that cannot be detected, even by an optimal detector. Here, there exists a similar SRL: suppose Alice may want to communicate to Bob in the face of a third party, Willie, without being detected by Willie. When communication takes place over a channel characterized by additive white Gaussian noise, it has been established that Alice can transmit O( √ n) bits of information in n channel uses [START_REF] Bash | Square root law for communication with low probability of detection on awgn channels[END_REF]. This result has been extended to optical (Poisson noise) channels [START_REF] Bash | Quantumsecure covert communication on bosonic channels[END_REF], binary channels [START_REF] Che | Reliable deniable communication with channel uncertainty[END_REF], and many others [START_REF] Bloch | Covert communication over noisy channels: A resolvability perspective[END_REF][START_REF] Wang | Fundamental limits of communication with low probability of detection[END_REF]. It has also been extended to include the presence of jammers [START_REF] Sobers | Covert communication in the presence of an uninformed jammer[END_REF], and to network settings [START_REF] Sheikholeslami | Multi-hop routing in covert wireless networks[END_REF]. Like our work, both steganography and covert communications rely on the use of statistical hypothesis testing. One difference from covert communications is that in our setting Alice hides her jobs in exponentially distributed noise (Willie's service times) and sometimes generally distributed noise, whereas Alice hides in zero mean Gaussian noise in covert communications. In addition, in the communications context, Alice has control over the power that she transmits at whereas in our context, Alice does not control the size of her jobs, only the rate at which they are introduced.

This work also has ties to the detection of service level agreement (SLA) violation problem. Detecting SLA violation in today's complex computing infrastructures, such as clouds infrastructures, presents challenging research issues [START_REF] Emeakaroha | Casvid: Application level monitoring for SLA violation detection in clouds[END_REF]. However no careful analysis of this problem has been conducted. Our work may provide an avenue to doing such.

During the review process a paper related to ours appeared [START_REF] Yardi | A Covert Queueing Problem with Busy Period Statistic[END_REF]. In [START_REF] Yardi | A Covert Queueing Problem with Busy Period Statistic[END_REF] Alice's jobs arrive continuously according to a Poisson process with rate λ b . It is shown that if Willie knows the number of his jobs successively served in a busy period and λ b lies below a certain threshold, then the expected number of jobs that Alice can covertly insert over n busy periods is O( √ n). If instead Willie knows the length of each busy period instead, the expected number of jobs that Alice can covertly insert is only O(1).

Model and Background

This section gives details about the model we use in the present work and the needed background on hypothesis testing. As mentioned in the introduction, there is a legitimate user, Willie, who sends a sequence of jobs to a single server with known service rate. There is also an illegitimate user, Alice, who wants to introduce a sequence of jobs to be serviced. The questions that we address are the following: can Alice covertly introduce her stream of jobs, i.e. without Willie being able to tell with confidence whether she has introduced the stream or not, and if so, at what rate can she introduce her jobs? We answer these questions under the following assumptions:

1. Willie jobs arrive at the server according to a Poisson process with rate λ ∈ (0, ∞); 2. the service times of all jobs are independent; 3. the service time distributions are known to both parties; 4. the server serves all jobs in a FIFO manner; 5. once in service, Alice jobs cannot be preempted; 6. Willie observes only his arrivals and departures; 7. Alice observes Willie's and her own arrivals and departures.

The first four assumptions are made mainly for tractability. If Alice jobs can be preempted whenever a Willie job arrives, then Alice can hide her jobs during Willie's idle periods without affecting his jobs. Consequently, we make the fifth assumption to make the problem interesting. Note that allowing Alice to also observe Willie arrivals and departures gives her the capability to identify idle periods within which to hide her jobs. Assumption 6 implies that Willie does not know the state of the server. If he does then Alice can only transmit during busy periods. However, if the scheduling policy is FIFO (Assumption 4) Alice cannot know if an inserted job of hers will not be the last one of the busy period, in which case it will be detected by Willie; relaxing the FIFO assumption appears to be very challenging. Assume that the system is empty at time 0. Denote by A i and D i the arrival and departure times of Willie's i-th job, respectively, for i ≥ 1. We assume that D 0 = 0. Note that 0 < A i < A i+1 and 0

< D i < D i+1 . Let A 1:m = {A 1 , . . . , A m }, D 1:m = {D 1 , . . . , D m }.
Let S 1:m = (S 1 , . . . , S m ) denote the reconstructed service times of the first m jobs, which satisfy the following recurrence relation,

S i = D 1 -A 1 , i = 1, D i -max{A i , D i-1 }, i ≥ 2.
(1)

These are the service times perceived by Willie. Note that (A 1:m , S 1:m ) and (A 1:m , D 1:m ) contain the same information, as they uniquely determine each other. It is also all the information available to Willie in our model.

We define a Willie Busy Period (W-BP) to be the time interval between the arrival of a Willie job that finds no other Willie job in the system and the first subsequent departure of a Willie job that leaves no other Willie jobs in the system. Let M j denote the number of Willie's jobs served in the first j W-BPs, which can be defined recursively by M 0 = 0 and

M j = min {i > M j-1 : A i+1 > D i } , j ≥ 1. (2)
Let N j = M j -M j-1 denote the number of Willie jobs served in the j-th W-BP.

Willie's observation is W 1:n , where

W j := M j = m j , A (m j-1 +1):m j = a (m j-1 +1):m j , S (m j-1 +1):m j = s (m j-1 +1):m j , j = 1, . . . , n. (3)
In words, Willie observes n W-BPs and for each W-BP records the number of his jobs that have been served, their arrival times and reconstructed service times.

The null hypothesis H 0 is that Alice does not insert jobs and the alternative hypothesis H 1 is that Alice inserts jobs. Willie's test may incorrectly accuse Alice when she does not insert jobs, i.e. he rejects H 0 when it is true. This is known as type I error or false alarm, and, its probability is denoted by P F A [START_REF] Lehmann | Testing Statistical Hypotheses[END_REF]. On the other hand, Willie's test may fail to detect insertions of Alice's jobs, i.e. he accepts H 0 when it is false. This is known as type II error or missed detection, and its probability is denoted by P M D . Assume that Willie uses classical hypothesis testing with equal prior probabilities of each hypothesis being true. Then, the lower bound on the sum P E = P F A + P M D characterizes the necessary trade-off between false alarms and missed detections in the design of a hypothesis test. If prior probabilities are not equal, P(H 0 ) = π 0 and P(H 1 ) = π 1 , then, P E ≥ min(π 0 , π 1 )(P F A + P M D ) [3, Sec. V.B]. Hence scaling results obtained for equal priors apply to the case of non-equal priors and we focus on the former in the remainder of the paper.

4 Insert-at-End-of-Busy-Period Policy

In this section, we consider the strategy that Alice inserts a job probabilistically at the end of each W-BP, which we call the Insert-at-End-of-Busy-Period (IEBP) Policy. Note that there may be an Alice job in the system at the start of a W-BP. This occurs when Alice has inserted a job at the end of a W-BP and that her job has not completed service by the time the next Willie job arrives.

Throughout the section, we assume that Willie jobs have service time distribution G 1 with continuous pdf g 1 and finite mean 1/µ

i pdf of (Y, V ) under H i , i = 0, 1 (f 0 (y, v) = g 1 (y)λe -λv ) q
probability Alice inserts a job (q = 1 -q); depends on n, the number of W-BPs Z(q, y, v) f 1 (y, v)/f 0 (y, v) C 0 Fisher information at origin (=E[ρ(X, V ) 2 ], with ρ(x, v) defined in [START_REF] Wang | Fundamental limits of communication with low probability of detection[END_REF])

f i pdf of Y under H i , i = 0, 1 ( f 0 (y) = g 1 (y)) Z(q, y) f 1 (y)/ f 0 (y) µr µ 1 µ µ 2 X r exponential rv, rate µr N j nb. Willie jobs served in j-th W-BP M j nb. Willie jobs served in first j W-BPs (M j = j l=1 N l ) T (n) expected nb. Alice jobs inserted in n W-BPs (T (n) = nq) T W (n)
expected nb. of Willie jobs served in n W-BPs ∞ 0 e -sx g i (x)dx the Laplace Stieltjes transform (LST) of g i for i = 1, 2. We also assume λ/µ 1 < 1 so that the system is stable under H 0 .

Introducing the IEBP Policy

To motivate the IEBP policy, we first find the minimum probability that an Alice job interferes with Willie's jobs. Suppose an Alice job is inserted at time t, with service time σ 2 ∼ G 2 . Let U t ≥ 0 be the unfinished work (of both Alice and Willie jobs) in the system just before time t. The newly inserted Alice job will affect Willie if he sends a job in the interval (t, t + U t + σ 2 ), the probability of which is P(at least one Willie job arrives in (t, t + U t + σ 2 )) ≥ P(at least one Willie job arrives in (t, t

+ σ 2 )) = ∞ 0 P(at least one Willie job arrives in (t, t + x))g 2 (x)dx = ∞ 0 (1 -e -λx )g 2 (x)dx = 1 -G * 2 (λ) := p. (4)
Thus if Alice is to insert a single job then she should insert it when the system is idle so as to minimize the probability of interfering with a Willie job. Motivated by this observation, we introduce the IEBP policy below.

Alice's strategy. Alice inserts a job with probability q at the end of each W-BP. We refer to this as the Insert-at-End-of-Busy-Period (IEBP) policy. Given that Alice does insert a job, the probability that it interferes with a Willie job is given by p in (4). Thus pq is the probability that an interference occurs in a given W-BP.

Willie's Detector

It is not easy to work directly with the observation process W 1:n defined in (3) (Section 3). Instead, we will work with the statistic (Y 1:n , V 1:n ), with Y j denoting the reconstructed service time of the first Willie job in the j-th W-BP and V j the length of the idle period preceding it. These quantities are given by

Y j = S M j-1 +1 , (5)
V j = A M j-1 +1 -D M j-1 . (6)
Denote by

f i (y, v) the joint pdf of (Y, V ) at (Y = y, V = v) under H i for i = 0, 1. Also, let f i (y) := ∞ 0 f i (y, v)dv denote the pdf of Y at Y = y under H i for i = 0, 1.
Under H 0 the system is a standard M/G/1 queue; in particular, the random variables (rvs) Y and V are independent with pdf g 1 (y) and λe -λv , respectively, yielding

f 0 (y, v) = g 1 (y)λe -λv , (7)
f 0 (y) = g 1 (y). ( 8
)
Under H 1 , Y j is the sum of the remaining service time of Alice's job, if any, when a Willie job initiates the j-th W-BP, and of the service time of this Willie's job. Therefore, under H 1 the system is an M/G/1 queue with arrival rate λ, exceptional first service time in a busy period with pdf f 1 , and all other service times (the ordinary customers) in a busy period with pdf g 1 . In Proposition 5.5 (Section 5) we derive some performance metrics of interest for this queueing system.

An important feature of the process (Y

1:n , V 1:n ) is that (Y 1 , V 1 ), . . . , (Y n , V n ) form
iid rvs due to the Poisson nature of Willie job arrivals and the assumptions that Willie's and Alice's service times are mutually independent processes, further independent of the arrival process. This is the main benefit from using the statistic (Y

1:n , V 1:n ) instead of the statistic W n . From now on (Y, V ) denotes a generic (Y j , V j ).
The independence of the rvs (Y 1 , V 1 ), . . . , (Y n , V n ) under H i (i = 0, 1) implies that their joint pdf is given by f ⊗n i , the n-th fold tensor product of f i with itself. The following lemma shows that (Y 1:n , V 1:n ) is a sufficient statistic (e.g. see [15, Chapter 1.9]), that is, Willie does not lose any information by considering the statistic (Y 1:n , V 1:n ) instead of the statistic W 1:n in order to detect the presence of Alice. The proof is given in Appendix A.

Lemma 4.1. For every n ≥ 1, (Y 1:n , V 1:n ) is a sufficient statistic.
Theorem 13.1.1 in [START_REF] Lehmann | Testing Statistical Hypotheses[END_REF] is established in the case where a simple hypothesis P 0 is tested against a simple alternative P 1 . In our setting, q = 0 is the simple hypothesis against the simple alternative q = q(n), and we are asking how we can scale q(n) down to 0 so that we can not differentiate q = 0 and q = q(n), with n the number of observed W-BPs. Using the observed values (y

1:n , v 1:n ) of (Y 1:n , V 1:n ), any test accepting H 0 if n i=1 f 0 (y j , v j ) > n i=1 f 1 (y j , v j ) and rejecting H 0 if n i=1 f 0 (y j , v j ) < n i=1 f 1 (y j , v j ) minimizes P E .
Furthermore, the minimum P E is given by

P E = 1 -T V f ⊗n 0 , f ⊗n 1 , where T V (u 0 , u 1 ) = 1 2 |u 0 (x) -u 1 (x)|dx (9)
is the total variation distance between two distributions with densities u 0 and u 1 , respectively.

We will henceforth assume that for a given (Y 1:n , V 1:n ) Willie uses the above optimal test.

We say that Alice's insertions are covert provided that, for any > 0, she has an insertion strategy for each n such that lim inf

n P E ≥ 1 -, (10)
or equivalently from Theorem 1, if for any > 0,

lim sup n T V f ⊗n 0 , f ⊗n 1 ≤ . (11)
Note that a sufficient condition for Alice's insertions not being covert is that for some δ ∈ (0, 1) there exists a detector such that lim sup

n P E < δ. ( 12
)
Here the limit is taken over the number of busy periods that Willie observes. This covertness criterion was proposed in the context of low probability of detection (LPD) communications in [START_REF] Bash | Square root law for communication with low probability of detection on awgn channels[END_REF].

Theorem 1 suggests using the total variation distance to analyze Willie's detectors. However, the total variation distance is often unwieldy even for products of pdfs, like f ⊗n 0 and f ⊗n 1 . To overcome this drawback, it is common (e.g. see [START_REF] Bash | Square root law for communication with low probability of detection on awgn channels[END_REF]) to use the following Pinsker's inequality (Lemma 11.6.1 in [START_REF] Cover | Elements of Information Theory[END_REF])

T V (u 0 , u 1 ) ≤ KL(u 0 u 1 ), (13)
where KL(u 0 u 1 ) :=

R d u 0 (x) ln u 0 (x) u 1 (x)
dx is the Kullback-Leibler (KL) divergence between the probability distributions with pdf u 0 and u 1 , respectively. However, we will work with the Hellinger distance, which has the advantage of offering both lower and upper bounds on the total variation distance. The Hellinger distance between two probability distributions with pdf u 0 and u 1 respectively, denoted H(u 0 , u 1 ), is defined by

H(u 0 , u 1 ) = 1 2 R d u 0 (x) -u 1 (x) 2 dx. (14)
Note that

H(u 0 , u 1 ) = 1 - R d u 0 (x)u 1 (x)dx, ( 15
)
and 0 ≤ H(u 0 , u 1 ) ≤ 1. It is known [13, Lemma 4.1] that H(u 0 , u 1 ) ≤ T V (u 0 , u 1 ) ≤ 2H(u 0 , u 1 ). ( 16
)
The upper bound (resp. lower bound) in ( 16) will be used to establish covert (resp. non-covert) results.

We will also use the following well-known property of the Hellinger distance between pdfs u ⊗n 0 and u ⊗n 1 [16, Eq. (1.4)]:

H u ⊗n 0 , u ⊗n 1 = 1 - R d n j=1 u 0 (x j )u 1 (x j ) n j=1 dx j by (15) = 1 - R d u 0 (x)u 1 (x)dx n . (17)

Main Results

Let T (n) denote the expected number of jobs that Alice inserts in n W-BPs. Under the IEBP policy,

T (n) = nq. ( 18
)
This section presents the main results that characterize T (n) under various conditions as n becomes large. Implicit in all asymptotic results as n → ∞ is that q is a function of n.

Recall that f i (y, v) is the joint pdf of (Y, V ) at (Y = y, V = v) under H i for i = 0, 1, with f 0 given in [START_REF] Cover | Elements of Information Theory[END_REF]. The likelihood ratio

Z(q, y, v) := f 1 (y, v) f 0 (y, v) , (19)
plays an important role in determining how many jobs Alice can insert covertly. It is shown in Lemma B.1 in Appendix B that Z has the following form,

Z(q, y, v) = 1 + qρ(y, v), (20)
where ρ(y, v) := 1 g 1 (y)

y 0 g 1 (u)g 2 (v + y -u)du -G 2 (v). ( 21
)
Since ρ(y, v) does not depend on the insertion probability q, this shows that the likelihood ratio Z(q, y, v) depends linearly on q. Define C

0 := E[ρ(X, V ) 2 ], (22)
where (X, V ) has pdf f 0 (x, v) at (x, v).

It is worth noting that C 0 = J(0), with J(q) := E

d dq log f 1 (X, V ) 2
the Fisher information of (Y, V ) about the parameter q. Indeed, since 19)-( 20), we have

f 1 (x, v) = f 0 (x, v)(1 + qρ(x, v)) by (
J(q) = 1 f 1 (x, v) 2 d dq f 1 (x, v) 2 f 0 (x, v)dxdv = ρ(x, v) 2 (1 + qρ(x, v)) 2 f 0 (x, v)dxdv,
and therefore J(0) = E[ρ(X, V ) 2 ]
. The Fisher information evaluates the amount of information that a random variable carries about an unknown parameter [START_REF] Kullback | Information Theory and Statistics[END_REF]. Proposition 5.1 gives the covert throughput for general service time distributions. Its proof is given in Section 7.

Proposition 5.1 (Covert throughput for general service time distr. and finite C 0 ).

Assume C 0 < ∞. Under the IEBP policy, the number of jobs Alice can insert covertly is

T (n) = O( √ n) if E[ρ(X, V )] = 0, and T (n) = O(1) if E[ρ(X, V )] = 0.
Remark 1. E[ρ(X, V )] = 0 for any pdf g 1 if g 2 is the pdf of an exponential or an hyper-exponential rv. Indeed, when

g 2 (x) = µ 2 e -µ 2 x , ρ(x, v) in (21) writes ρ(x, v) = e -µ 2 v (g 1 * g 2 )(x) g 1 (x) -1 . (23)
By the independence of X and V and the fact that

g 1 * g 2 is a pdf, E[ρ(X, V )] = E[e -µ 2 V ] • E (g 1 * g 2 )(X) g 1 (X) -1 = 0. ( 24
)
The proof when g 2 is the pdf of an hyper-exponential rv is a simple generalization. Note that E[ρ(X, V )] does not always vanish. In particular, E[ρ(X, V )] = 0 when G 2 is an Erlang distribution. Indeed, when g 2 (x) = (kµ 2 ) k (k-1)! x k-1 e -kµ 2 x , k ≥ 1 (Alice service times follow a k-Erlang distribution with mean 1/µ 2 ), it is easy to show that for any pdf

g 1 , E[ρ(X, V )] = (1 -G * 2 (λ)) (kµ 2 ) k µ 2 -1 = 0 for all k > 1.
The next lemma gives conditions for C 0 < ∞ under various distributional assumptions. Its proof is found in Appendix C.

Lemma 5.2 (Finiteness of C 0 ).

1. Suppose both Alice and Willie have exponential service times, i.e.

g i (x) = µ i e -µ i x for i = 1, 2. Then C 0 < ∞ if and only if µ 1 < 2µ 2 .
2. Suppose both Alice and Willie have hyper-exponential service times, i.e.

g i (x) = K i l=1 p i,l µ i,l e -µ i,l x , where K i l=1 p i,l = 1, for i = 1, 2. Then C 0 < ∞ if and only if max 1≤l≤K i µ 1,l ≤ 2 min 1≤m≤K 2 µ 2,m .
3. Suppose Willie has Erlang service times and Alice has hyper-exponential service times, i.e.

g 1 (x) = ν K 1 1 (K 1 -1)! x K 1 -1 e -ν 1 x
and

g 2 (x) = K 2 l=1 p 2,l µ 2,l e -µ 2,l x ,
where

K 2 l=1 p 2,l = 1. Then C 0 < ∞ if and only if ν 1 < 2 min 1≤l≤K 2 µ 2,l .
Proposition 5.1 gives sufficient conditions for Alice to be covert. This raises the following questions:

Q1: When C 0 < ∞, can Alice insert covertly more than O( √ n) jobs on average during n W-BPs? Q2: When C 0 = ∞,
what is the maximum number of jobs that Alice can insert covertly on average during n W-BPs?

We do not have full answers to the above questions. Proposition 5.3 first gives a necessary condition for Alice to be covert under IEBP. Proposition 5.4 then provides a partial answer for the IEBP policy when both Alice and Willie have exponential service times. Proofs are found in Sections 8 and 9.

Proposition 5.3 (Necessary condition for covertness).

Under IEBP Alice cannot be covert if lim sup n→∞ q > 0.

Consider now the situation when lim n→∞ q = 0. The result below is the main result of the paper.

Proposition 5.4 (Covert throughput and converse for exponential service time distr.). Assume that g i (x) = µ i e -µ i x for i = 1, 2, and Alice uses the IEBP policy with lim n→∞ q = 0. She can be covert if

T (n) =      O( √ n), if µ 1 < 2µ 2 , O( n/ log n), if µ 1 = 2µ 2 , O(n µ 2 /µ 1 ), if µ 1 > 2µ 2 . ( 25
)
She cannot be covert if

T (n) =      ω( √ n), if µ 1 < 2µ 2 , ω( n/ log n), if µ 1 = 2µ 2 , ω(n µ 2 /µ 1 ), if µ 1 > 2µ 2 . ( 26
)
The above results are in terms of T (n), the expected number of jobs inserted by Alice over n successive W-BPs. It is interesting to determine also the expected number of Willie jobs served during these n W-BPs under the IEBP policy. Let T W (n) be this number. When q = 0, the system behaves like a standard M/G/1 queue with traffic intensity λ/µ 1 < 1 and it is known that the expected number of jobs served in a busy period is (1 -λ/µ 1 ) -1 [START_REF] Kleinrock | Queueing Systems[END_REF], yielding T W (n) = n(1 -λ/µ 1 ) -1 . Proposition 5.5 below shows that the IEBP policy increases each W-BP by a constant factor. The proof is in Appendix H.

Proposition 5.5. Under IEBP, T W (n) = Θ(n). More precisely

T W (n) = n 1 -λ/µ 1 + λqn 1 -λ/µ 1 ∞ 0 tĝ 2 (t)dt, (27)
which gives the two-sided inequality

n ≤ T W (n) ≤ n 1 + qλ/µ 2 1 -λ/µ 1 . ( 28
)
If g 2 (x) = µ 2 e -µ 2 x , i.e. Alice job service times are exponentially distributed, then

T W (n) = n 1 + pqλ/µ 1 1 -λ/µ 2 . ( 29
)
Remark 2. Recall that the Fisher information regarding q is infinity at q = 0 when µ 1 ≥ µ 2 . It is interesting to speculate that this translates into facilitating Willie's detection task, which appears in the form of the phase transition in equations ( 25) and ( 26). Note that one implication of this transition is that Alice should select job sizes with mean size 1/µ 2 < 2/µ 1 to increase throughput without being detected.

Preliminary results

We first specialize the two-sided inequality in [START_REF] Oosterhoff | A note on contiguity and hellinger distance[END_REF] to the case where u 0 = f ⊗n 0 and u 1 = f ⊗n 1 and then develop a covert (resp. non-covert) criterion for Alice.

H f ⊗n 0 , f ⊗n 1 = 1 -E Z(q, X, V ) n . ( 30
)
Proof. By ( 17) and [START_REF] Sheikholeslami | Multi-hop routing in covert wireless networks[END_REF],

H f ⊗n 0 , f ⊗n 1 = 1 - [0,∞) 2 f 0 (y, v)f 1 (y, v) dydv n = 1 - f 0 (y, v) Z(q, y, v) dydv n = 1 -E Z(q, X, V ) n .
Specializing [START_REF] Oosterhoff | A note on contiguity and hellinger distance[END_REF] to the value of H f ⊗n 0 , f ⊗n 1 found in Lemma 6.1 gives, Lemma 6.2 (Lower & upper bounds on total variation distance for statistic {Y j , V j } j ). For every n ≥ 1

1 -E Z(q, X, V ) n ≤ T V f ⊗n 0 , f ⊗n 1 ≤ 2 1 -E Z(q, X, V ) n . (31)
Combining Lemma 6.2, the covert criterion [START_REF] Jiang | Covert cycle stealing in a single fifo server (extended version)[END_REF], and the non-covert criterion (12) yields the following covert/non-covert criterion for Alice:

Corollary 6.1 (Covert/non-covert criteria for the IEPB policy).

Assume that Willie uses an optimal detector for the sufficient statistic (Y 1:n , V 1:n ). Alice's insertions are covert if for any > 0, lim inf

n E Z(q, X, V ) n ≥ 1 -, (32)
and Alice's insertions are not covert if for any δ > 0 lim sup

n E Z(q, X, V ) n < δ. (33)
The lower bound (32) is used to derive the covert throughput (25) in Proposition 5.4.

We now state and prove a non-covert criterion for the IEPB policy. We do so by proposing and analyzing a detector that relies on the (non-sufficient) statistic {Y j } j . Recall that rvs Y 1 , . . . , Y n are iid with common pdf f i (y) under H i , for i = 0, 1. The non-covert criterion is obtained by applying Theorem 13.1.1 in [START_REF] Lehmann | Testing Statistical Hypotheses[END_REF] to the statistic Y 1:n , which yields the minimum P E to be 1 -

T V f ⊗n 0 , f ⊗n 1 .
The following lemmas are the analog of Lemmas 6.1 and 6.1 for the statistic {Y j }.

Lemma 6.3. The Hellinger distance between f ⊗n 0 and f ⊗n 1 is given by

H f ⊗n 0 , f ⊗n 1 = 1 -E Z(q, X) n , (34)
with

Z(q, x) := f 1 (x) g 1 (x) . ( 35
)
Lemma 6.4 (Lower bound on total variation distance for statistic Y 1:n ). For every n ≥ 1

1 -E Z(q, X) n ≤ T V f ⊗n 0 , f ⊗n 1 . ( 36
)
The proof of Lemma 6.3 mimics that of Lemma 6.1 and is omitted. Lemma 6.4 follows from Lemma 6.3 and the lower bound in [START_REF] Oosterhoff | A note on contiguity and hellinger distance[END_REF].

The non-covert criterion for the statistic {Y j } j announced earlier is given below. Its proof follows from ( 12) and (36).

Corollary 6.2 (Non-covert criterion for the IEPB policy).

Assume that Willie uses an optimal detector for the statistic {Y j } j . Alice's insertions are not covert if for any δ > 0 lim sup

n E Z(q, X) n < δ. ( 37
)
Corollary 6.2 is used in the proofs of Proposition 5.3 and of the converse (26) in Proposition 5.4.

Remark 3. In direct analogy with the upper bound in Lemma 6.2 it is worth noting that T V f ⊗n 0 , f ⊗n 1 in Lemma 6.4 is upper bounded by 2 1 -E Z(q, X) n . However, this bound is not useful for establishing a covert result since it does not use the sufficient statistic (Y

1:n , V 1:n ).
7 Proof of Proposition 5.1

The proof of Proposition 5.1 relies on an upper bound on the total variation distance between f ⊗n 0 and f ⊗n 1 , given in Lemma 7.1 below. Recall the definition of ρ(X, V ) given in [START_REF] Wang | Fundamental limits of communication with low probability of detection[END_REF].

Lemma 7.1. Let (X, V ) be rvs with density f 0 . Assume that E[ρ(X, V )] = 0. Then, for every n ≥ 1,

T V f ⊗n 0 , f ⊗n 1 ≤ 1 2 (1 + q 2 C 0 ) n -1, ( 38
)
where C 0 is defined in [START_REF] Yardi | A Covert Queueing Problem with Busy Period Statistic[END_REF].

Proof. Let {(X j , V j )} j be iid rvs with pdf f 0 . By [START_REF] Fridrich | Steganography in Digital Media: Principles, Algorithms, and Applications[END_REF],

2T V f ⊗n 0 , f ⊗n 1 = [0,∞) 2n n j=1 f 0 (y j , v j ) - n j=1 f 1 (y j , v j ) n j=1 dy j dv j = [0,∞) 2n n j=1 f 0 (y j , v j ) 1 - n j=1 Z(q, y j , v j ) n j=1 dy j dv j = E   1 - n j=1 Z(q, X j , V j )   , (39)
where the second equality follows from [START_REF] Sheikholeslami | Multi-hop routing in covert wireless networks[END_REF].

Using the inequality E|U

| ≤ E[U 2 ] in (39) yields 2T V f ⊗n 0 , f ⊗n 1 2 ≤ 1 -2E   n j=1 Z(q, X j , V j )   + E     n j=1 Z(q, X j , V j )   2   = 1 -2 [EZ(q, X, V )] n + E[Z(q, X, V ) 2 ] n (40) = -1 + 1 + 2qE[ρ(X, V )] + q 2 E[ρ(X, V ) 2 ] n = -1 + 1 + q 2 E[ρ(X, V ) 2 ] n ,
where we have used the value of Z(q, x, v) obtained in (80) in Appendix B and the assumption that E[ρ(X, V )] = 0 to establish the last two identities.

We are now in position to prove Proposition 5.1.

Proof of Proposition 5.1. In order to compute the covert throughput, assume that Willie uses an optimal detector for the sufficient statistic {(Y j , V j ), j = 1, . . . , n}. Let

q = δ φ(n) ,
with δ ∈ (0, 1] and φ : {1, 2, . . .} → [1, ∞), so that by ( 18)

T (n) = δn φ(n) . ( 41
) First consider the case E[ρ(X, V )] = 0. Note that T (n) = O( √ n) implies lim sup n √ n φ(n) < ∞. (42) By Lemma 7.1 sup k≥n T V f ⊗k 0 , f ⊗k 1 ≤ sup k≥n 1 2 1 + δ 2 C 0 φ(k) 2 k -1 ∼ δ √ C 0 2 sup k≥n k φ(k) 2 , as n → ∞ as lim n φ(n) = ∞ by Lemma D.1 in Appendix D. Therefore, lim sup n T V f ⊗n 0 , f ⊗n 1 ≤ δ √ C 0 2 lim sup n √ n φ(n) 2 . ( 43
)
By making δ small enough, lim sup n T V (f ⊗n 0 , f ⊗n 1 ) can be made arbitrarily small. We then conclude from (10) that Alice is covert when

T (n) = O( √ n), which completes the proof for the case E[ρ(X, V )] = 0. Now consider the case E[ρ(X, V )] = 0. Note that T (n) = δn φ(n) = O(1)
implies there exist k > 0 and n 0 such that for all n ≥ n 0 , 0 ≤ n φ(n) ≤ k. Using inequality (40) and the definition of Z(q, y, v) in [START_REF] Sobers | Covert communication in the presence of an uninformed jammer[END_REF] gives

2T V f ⊗n 0 , f ⊗n 1 2 ≤ 1 -2e n log 1+ δ φ(n) E[ρ(X,V )] + e n log 1+ 2δ φ(n) E[ρ(X,V )]+ δ 2 φ(n) 2 C 2 0 ∼ 1 -2e E[ρ(X,V )] δn φ(n) + e 2E[ρ(X,V )] δn φ(n) +δ 2 C 2 0 n φ(n) 2 , (44)
as n → ∞. Since n φ(n) and n φ(n) 2 are bounded away from infinity as n → ∞, we see that the r.h.s. of (44) can be made arbitrarily close to 0 by letting δ → 0. We then conclude from [START_REF] Harchol-Balter | Analysis of task assignment with cycle stealing under central queue[END_REF] that Alice is covert when T (n) = O(1), which completes the proof.

Proof of Proposition 5.3

The proof uses Corollary 6.2. Take q = 1 φ(n) with lim sup n q > 0 or, equivalently, lim inf n φ(n) < ∞. Assume that Willie uses an optimal detector for the statistic {Y j } j so that Corollary 6.2 applies. Recall (cf. Section 6) that f 1 (y) (resp. g 1 (y)) is the pdf of Y under H1 (resp. H 0 ), with Z(q, y) = f 1 (y) g 1 (y) being the associated likelihood ratio.

We first derive properties of Z(q, y), to be used in this proof and in the proof of Proposition 5.4.

We claim that

Z(q, y) = ∞ 0 λe -λv Z(q, y, v)dv. (45)
Indeed by ( 19) and ( 7)

∞ 0 λe -λv Z(q, y, v)dv = 1 g 1 (y) ∞ 0 f 1 (y, v)dv = f 1 (y) g 1 (y) = Z(q, y),
from the definition of Z(q, y) in (35). Hence by ( 20)

Z(q, y) = 1 + q ρ(y), (46)
with

ρ(y) := ∞ 0 λe -λv ρ(y, v)dv = 1 g 1 (y) ∞ 0 λe -λv y 0 g 1 (u)g 2 (v + y -u)dudv - ∞ 0 λe -λv G 2 (v)dv by (21) = (g 1 * ĝ2 )(y) g 1 (y) -p, (47)
by using the definition of p in (4), and where

ĝ2 (t) := ∞ 0 λe -λv g 2 (v + t)dv. (48)
We are now ready to prove Proposition 5.3. Recall that X is a rv with pdf g 1 . We have

E Z(q, X) = 1 i=0 f i (x)dx ≤ 1 i=0 f i (x)dx = 1, (49)
by Cauchy-Schwarz inequality. Equality holds in (49) if and only if (see e.g. [1, p. 14]) f 1 (x) = c f 0 (x) for some constant c > 0. Since both f 0 and f 1 are densities, integrating over [0, ∞) yields c = 1, which is equivalent to q = 0 from (35) and ( 46). This shows that E Z(q, X) < 1 if and only if 0 < q ≤ 1.

Since lim inf n φ(n) := d < ∞ by assumption, there exists a subsequence of {φ(n

)} n , say {φ(k n )} n , such that φ(k n ) ≥ d with lim n φ(k n ) = d.
Let M := sup 1/d≤q≤1 E Z(q, X) . Note Z(q, X) = 1 + q ρ(X)

≤ 1 + | ρ(X)| ≤ 1 + | ρ(X)|. By (47), E[|ρ(X)|] ≤ (g 1 * ĝ2
)(t)dt + p and g 1 * ĝ2 is integrable as both g 1 and ĝ2 are integrable. The Dominated Convergence Theorem then guarantees that the function q → E Z(q, X) is continuous.

Since E Z(q, X) < 1 for all q ∈ [1/d, 1] as shown above, we have M < 1. Therefore,

E Z(1/φ(k n ), X) ≤ M < 1 for all n. As a result lim n E Z(1/φ(k n ), X) n = 0,
which implies from Corollary 6.2 that Alice's insertions are not covert when lim inf n φ(n) < 0, or equivalently when lim sup n q = ∞.

9 Proof of Proposition 5.4

Throughout this section, we assume that Alice and Willie job service times are exponentially distributed with rate µ 2 and µ 1 , respectively, namely, g i (x) = µ i e -µ i x for i = 1, 2.

The proof of Proposition 5.4 relies on Corollaries 6.1 and 6.2, and Lemma 9.1 below. Before stating the latter, let us introduce some notation.

Henceforth we drop the argument n in q(n). Furthermore

T (n) = nq = δn φ(n) (58)
is the expected number of Alice's insertions in n W-BPs.

Proof of (25)

We assume that Willie uses an optimal detector for the sufficient statistic {(Y j , V j )} j , which allows us to apply Corollary 6.1.

9.1.1

Case

µ 1 < 2µ 2
The proof follows from Proposition 5.1 since E[ρ(X, V )] = 0 when Alice and Willie job service times are exponentially distributed (cf. Remark 1) and since C 0 < ∞ when µ 1 < 2µ 2 , as shown in Lemma 5.2-(1).

Case

µ 1 = 2µ 2
Without loss of generality we assume in this section that

φ(n) ≥ 8, ∀n ≥ 1. ( 59
)
This assumption is motivated by the need to have log φ(n) > 2 (for the proof of Lemma F.2 in Appendix F).

Recall that X 2 denotes an exponential rv with rate 2µ. By Lemma 9.1,

E Z(δ/φ(n), X 2 , V ) n = 1 + ∞ 0 λe -λv 1 4 ξ 2 2 log ξ 2 + ∆ 2 (ξ 2 ) dv n = e n log 1+ ∞ 0 λe -λv ξ 2 2 log ξ 2 × 1 4 + ∆ 2 (ξ 2 ) ξ 2 2 log ξ 2 dv , (60)
with ∆ 2 (z) = o(z 2 log z) and ξ 2 = δe -µv φ(n)-2δe -µv > 0 for all n ≥ 1 and for all v ≥ 0 thanks to (59). For v ≥ 0 notice that ξ 2 > 0 for all n and ξ 2 → 0 as n → ∞. Define

D n := ∞ 0 λe -(λ+2µ)v log ξ 2 (φ(n) -2δe -µv ) 2 1 4 + ∆ 2 (ξ 2 ) ξ 2 2 log ξ 2 dv, (61)
so that (60) rewrites

E Z(δ/φ(n), X 2 , V ) n = e n log(1+δ 2 Dn) . ( 62
)
The proof of (25) for µ 1 = 2µ 2 consists in showing that, as n → ∞, the r.h.s. of (62) can be made arbitrary close to one by selecting δ small enough, and to apply (32) in Corollary 6.1.

The first step is to show that D n → 0 as n → ∞. This result is shown in Lemma F.1 in Appendix F.

Hence,

E Z(δ/φ(n), X 2 , V ) n ∼ n e δ 2 nDn (63)
from (62). The second step is to show that nD n is bounded as n → ∞. This result is shown in Lemma F.2 in Appendix F under the condition that

T (n) = O( n/ log n).
The proof is concluded as follows: when

T (n) = O( n/ log n), by (63) and Lemma F.2, as n → ∞, E Z(δ/φ(n), X 2 , V )
n can be made arbitrarily close to one by taking δ small enough. The proof of (25) for µ 1 = 2µ 2 then follows from (32) in Corollary 6.1.

Case

µ 1 > 2µ 2 Fix r > 2 so that 1 < β < 2. By Lemma 9.1 E Z(δ/φ(n), X r , V ) n = e n log 1+ ∞ 0 λe -λv -I β ξ β r +∆r(ξr) dv = e n log(1+δ β (β-1) β En) , ( 64
) with ∆ r (z) = o(z β ), ξ r = δ(β-1)
e µv φ(n)-βδ , and

E n := - ∞ 0 λe -λv I β -∆ r (ξ r )/ξ β r (e µβ φ(n) -δβ) β dv. ( 65
) Lemma F.3 in Appendix F states that E n → 0 as n → ∞ and Lemma F.4 in Appendix F states that nE n is bounded as n → ∞ when T (n) = O(n µ 2 /µ 1 ). Therefore, cf (64), E Z(δ/φ(n), X r , V ) n ∼ n e δ β (β-1) β nEn , (66)
and when T (n) = O(n µ 2 /µ 1 ) as n → ∞ the r.h.s. of (66) can be made arbitrarily close to one by selecting δ small enough. The proof of (25) for µ 1 > 2µ 2 then follows from (32) in Corollary 6.1.

Proof of (26)

We assume that Willie uses an optimal detector for the statistic {Y j } j , which will allows us to use the non-covert criterion in Corollary 6.2. Since the proofs in Sections 9.2.1-9.2.3 will not depend on δ ∈ (0, 1], we assume without loss of generality that δ = 1, yielding q = 1 φ(n) and T (n) = n φ(n) .

Case

µ 1 < µ 2 Assume that T (n) = ω( √ n), or equivalently lim n→∞ n φ(n) 2 = ∞. ( 67
)
Assume first that 0 < r < 1. From (52) and Lemma 9.1 we obtain

E Z(p/φ(n), X r ) n = e n log 1+ p 2 4 ( 1-r r-2 )/φ(n) 2 +o(1/φ(n) 2 ) ∼ n e n φ(n) 2 p 2 4 ( 1-r r-2 ) as φ(n) → ∞ as n → ∞ ∼ n 0, ( 68
)
where the latter follows from (67) together with 1-r r-2 < 0 when 0 < r < 1. We invoke Corollary 6.2 to conclude that Alice is not covert when T (n) = ω( √ n) and 0 < r < 1.

It remains to show that Alice is not covert for 1 ≤ r < 2 when T (n) = ω( √ n) with lim n n/φ(n) 2 = ∞. Without any additional effort, we will prove a stronger result (to be used in the proof of the case µ 1 = 2µ 2 of (26)) that Alice is not covert when T (n) = ω( √ n) and r ≥ 1. By applying Lemma G.1 in Appendix G to (52), we obtain

E Z(p/φ(n), X r ) ≤ E Z(p/φ(n), X r ) ( 69
)
for any r ≥ r. Combining now (69) and ( 68) readily yields

lim n→∞ E[ Z(p/φ(n), X r ) n = 0
for any r ≥ 1. Similarly to the case 0 < r < 1 we then conclude from Corollary 6.2 that Alice is not covert

T (n) = ω( √ n) and r ≥ 1.
In summary, we have shown that Alice is not covert for all r > 0 when

T (n) = ω( √ n).

Case

µ 1 = 2µ 2 Assume that T (n) = ω( n/ log n) or, equivalently, lim n φ(n) √ n log n = 0. (70)
From (52) and Lemma 9.1

E Z(p/φ(n), X 2 ) n = e n log(1+ 1 4 ξ 2 2 log ξ 2 +o(ξ 2 2 log ξ 2 )) , (71)
with

ξ 2 = p φ(n)-2p . Since ξ 2 ∼ n 0 when lim n φ(n) = ∞, we have ξ 2 log ξ 2 → 0 as n → ∞.
Therefore, from (71),

E Z(p/φ(n), X 2 ) n ∼ n e n 4 ξ 2 2 log ξ 2 . (72)
We have proved in the case µ 1 < 2µ 2 of (26) that Alice is not covert for all r > 0 when

T (n) = ω( √ n).
As a result, it suffices to focus on T (n) satisfying (70) when

T (n) = ω( √ n). The latter is equivalent to φ(n) = Ω( √ n), that is, lim inf n φ(n) √ n > 0. ( 73
)
We have

nξ 2 2 log ξ 2 = p 2 φ(n) √ n log n -2p √ n log n 2 log p log n - log(φ(n) -2p) log n ∼ n -p 2 φ(n) √ n log n -2p √ n log n 2 × log(φ(n) -2p) log n . (74)
By (70) the first factor in the r.h.s. of (74) converges to -∞ as n → ∞. Let us focus on the second factor. We have

log(φ(n) -2p) log n = 1 2 + log φ(n)-2p √ n log n ∼ n 1 2 + log φ(n) √ n log n . Assumption (73) ensures that log φ(n) √ n log n → 0 as n → ∞ and log(φ(n) -2p) log n → 1 2 as n → ∞.
In summary, we have shown that nξ 2 2 log ξ 2 → -∞ as n → ∞ which, in turn, implies from (72) that lim n E Z(p/φ(n), X 2 ) n = 0. We conclude from Corollary 6.2 that Alice is not covert if r = 2 and

T (n) = ω( n/ log n). 9.2.3 Case µ 1 > 2µ 2 Assume that T (n) = n/φ(n) = ω(n µ 2 /µ 1 ) or, equivalently, lim n n β = 0. (75)
Let r > 2 so that β ∈ (1, 2). From (57),

E Z(p/φ(n), X r ) n = e n log 1-I β ξ β r +o(ξ β r ) ∼ n e -I β nξ β r , (76)
since ξ r = (β-1)p φ(n)-βp → 0 when lim n φ(n) = ∞. We have

nξ β r = (β -1)p) β φ(n) n β -βp n β β → +∞ as n → ∞.
Introducing the above limit in (76) and using the finiteness and positiveness of

I β for β ∈ (1, 2), gives lim n E Z(p/φ(n), X r ) n = 0
, which shows by using again Corollary 6.2 that Alice is not covert if

r > 2 and T (n) = ω(n µ 2 /µ 1 ).
This concludes the proof of Proposition 5.4.

Other policies

The first policy -called the Insert-at-Idle (II) policy -is a variant of the IEBP policy and works as follows: Alice inserts a job with probability q each time the server idles, and stop inserting with probability q (before she tries again at the end of the next W-BP). The difference between the IEBP and II policies is that under the former Alice inserts at most one job between the end of a W-BP and the start of the next W-BP, whereas under the II policy she may insert more than one job during this time period.

It is shown in [START_REF] Jiang | Covert cycle stealing in a single fifo server (extended version)[END_REF]Section 5] that when Alice job service times are exponentially distributed all covert/noncovert results obtained under the IEBP policy hold under the II policy. The intuition behind this is that when Alice job service times are exponentially distributed, Willie sees "the same system behavior" under either policy; indeed, under either policy a job of his can interfere with at most one Alice job in a W-BP, whose remaining service time is exponentially distributed.

We have observed at the beginning of Section 4.1 that Alice should preferably inserts jobs at idle times; this was the motivation for introducing and investigating the IEBP policy in Section 4 and its variant, the II policy. But can Alice submit more jobs covertly if she also inserts jobs at other times than at idle times, typically, just after an arrival /departure of a Willie job? Note that, because of the FIFO assumption, Alice cannot benefit from inserting a job at a time t+ if time t is neither an arrival time nor a departure time of a Willie job. This is the motivation for introducing the class of the so-called Insert-at-Idle-and-at-Arrivals (II-A) policies, in which

• each time the server idles Alice inserts one job with probability q and does not insert a job with probability q;

• after the arrival of each Willie job, Alice inserts a batch of s ≥ 0 jobs with probability qQ(s) and with probability 1 -q she does not insert any job.

Notice that the II-A policy reduces to the II policy when Q B (0) = 1 (no job inserted at arrival times).

Only non-covert results are obtained in [START_REF] Jiang | Covert cycle stealing in a single fifo server (extended version)[END_REF]Section 6]. More specifically, for exponential service times for both Alice and Willies, Alice is non-covert if T (n) = ω( √ n) when the support of Q is finite. A variant of the II-A policy is when Alice inserts a batch of jobs that is geometrically distributed at times the server becomes idle and immediately after the arrival of a Willie job, both with probability q. Non-covert results are also obtained for this policy. The obtained results indicate that batching may be harmful and that Alice should insert only one job at a time.

Concluding remarks

In this paper we have studied covert cycle stealing in an M/G/1 queue. We have obtained a phase transition result on the expected number of jobs that Alice can covertly insert in n busy periods when both Alice and Willie's jobs have exponential service times and established partial covert results for arbitrary service times. Several research directions present themselves. We conjecture that Proposition 5.4 holds for a more general class of distributions; it would be interesting to verify this. It would be useful to weaken the assumption that Willie's detectors rely on observations being independent and identically distributed random variables; this would lead to consideration of a larger class of policies on Alice's behalf. Another direction would be to allow Alice to control her job sizes and study what benefit this would provide her. Yet another is to consider other hypothesis testing techniques including generalized likelihood ratio test (GLRT), sequential detection, etc. GLRT could lead to relaxing the need for Willie to know Alice's parameters whereas sequential detection could lead to more timely detection of Alice.

Lemma B.1.

Z(q, y, v) = 1 + qρ(y, v), (80)
where ρ(y, v) := 1 g 1 (y)

x 0 g 1 (u)g 2 (v + y -u)du -G 2 (v).
(81)

Proof. Consider a generic W-BP. Let σ 1 (resp. σ 2 ) denote a generic service time of a Willie (resp. Alice) job. Let A be the event that Alice inserts a job at the end of the W-BP. Then

Y = σ 1 + 1{A} • (σ 2 -V ) + ,
where (z) + = max{z, 0}. We first compute the conditional density

f 1 (y | v) of Y given V . Given A C , Y = σ 1 , so f 1 (y | v, A c ) = g 1 (y).
Given A and V = v, we have

Y = σ 1 + (σ 2 -v) + , so that f 1 (y | v, A) = g 1 (y)G 2 (v) + y 0 g 1 (u)g 2 (y + v -u)du.
Recall the probability of A under H 1 is q, so

f 1 (y | v) = qf 1 (y | v, A) + qf 1 (y | v, A c ) = g 1 (y) + q y 0 g 1 (u)g 2 (y + v -u)du -g 1 (y) Ḡ2 (v) = g 1 (y)[1 + qρ(y, v)], (82)
by using the definition of ρ(y, v) in (81). Therefore,

Z(q, y, v) = f 1 (y | v)λe -λv f 0 (y, v) = 1 + qρ(y, v),
by using [START_REF] Cover | Elements of Information Theory[END_REF], which concludes the proof.

C Appendix: Proof of Lemma 5.2

Let g 2 (x) = K 2 l=1 p 2,l g 2,l (x) with g 2,l (x) := µ 2,l e -µ 2,l x , p 2,l ≥ 0 for all l and K 2 l=1 p 2,l = 1, namely, Alice job service times follow an hyper-exponential distribution with mean 1/µ 2 = K 2 l=1 1/µ 2,l . Denote by

G * 1 (s) =
∞ 0 e -sx g 1 (x)dx the Laplace transform of Willie job service times.

By using [START_REF] Wang | Fundamental limits of communication with low probability of detection[END_REF], we find

ρ(x, v) = 1 g 1 (x) K 2 l=1 p 2,l e -µ 2,l v (g 1 * g 2,l )(x) - K 2 l=1 p 2,l e -µ 2,l v , so that E ρ(X, V ) 2 = α 1 -2α 2 + α 3 with α 1 := [0,∞) 2 λe -λv g 1 (x) K 2 l=1 p 2,l e -µ 2,l v (g 1 * g 2,l )(x) 2 dvdx (88) Q 2,l (x) := η l K 1 i=1 (K 1 -1)! (K 1 -i)! x K 1 -i (ν 1 -µ 2,l ) i 1(ν 1 = µ 2,l ). (89)
When ν 1 = µ 2,l or ν 1 = µ 2,m it is easily seen from ( 87)-(89) that β(l, m) < ∞ if and only if ν 1 < µ 2,l + µ 2,m .

Let us investigate the (less trivial) remaining case when ν 1 = µ 2,l and ν 1 = µ 2,m . In this case we have, from (87)-( 89),

(g 1 * g 2,l )(x)(g 1 * g 2,m )(x) g 1 (x) = η l η m ν K 1 1 x K 1 e -ν 1 x (K 1 -1)! (ν 1 -µ 2,l ) K 1 e -µ 2,l x - K 1 i=1 (K 1 -1)! (K 1 -i)! x K 1 -i (ν 1 -µ 2,l ) i e -ν 1 x × (K 1 -1)! (ν 1 -µ 2,lm ) K 1 e -µ 2,m x - K 1 i=1 (K 1 -1)! (K 1 -i)! x K 1 -i (ν 1 -µ 2,m ) i e -ν 1 x = η l η m ((K -1)!) 2 ν K 1 1 (ν 1 -µ 2,l ) K 1 (ν 1 -µ 2,m ) K 1 × e (ν 1 -µ 2,l )x - K 1 -1 j=0 (x(ν 1 -µ 2,l )) j j! × 1 x K 1 e -µ 2,m x -e -ν 1 x K 1 -1 j=0 (x(ν 1 -µ 2,m ) j j! , which shows that (g 1 * g 2,l )(x)(g 1 * g 2,m )(x)/g 1 (x) is well-defined when x → 0 and is [0, ∞)-integrable if and only if ν 1 < µ 2,l + µ 2,m .
In summary, C 0 < ∞ if and only if ν 1 < 2 min 1≤l≤K 2 µ 2,l or, equivalently, if and only if

µ 1 < 2 K 1 min 1≤l≤K 2 µ 2,l . D Appendix Lemma D.1. Let f, g : N → [0, ∞). If lim sup n g(n) f (n) < ∞ with lim n g(n) = ∞ then lim n f (n) = ∞. Proof. If lim n g(n) f (n) = 0 then clearly lim n f (n) = ∞.
Assume now that there exist 0 < L < ∞ and n 0 such that for all n > n 0

sup k≥n g(k) f (k) < L. Since sup k≥n g(k) f (k) ≥ g(n) f (n) , f (n) > L -1 g(n)
for n > n 0 , which proves the lemma since lim n g(n) = ∞.

E Appendix: Proof of Lemma 9.1

Proof. Assume that 0 < r < 1 (i.e. β < 0). Recalling that X r is an exponential rv with rate µr, definition (53) yields

P Ξ(θ, X r ) > z =      0 if z > √ 1 -θβ 1-θβ-z 2 θ(1-β) -β if √ 1 -θ ≤ z ≤ √ 1 -θβ 1 if z < √ 1 -θ, which gives E Ξ(θ, X r ) = ∞ 0 P Ξ(θ, X r ) > z dz = √ 1 -θ + (θ(1 -β)) β √ 1-θβ √ 1-θ (-y 2 + 1 -θβ) -β dy = √ 1 -θ + θ(1 -β) 1 -θβ β (1 -θβ) 1/2 1 1-θ 1-θβ (1 -y 2 ) -β dy. (90)
Recall that ξ r (θ) = (1 -β)θ/(1 -θβ), so that θ = ξ r (θ)/(1 -β + βξ r (θ)). Substitution into (90) yields (with ξ r ≡ ξ r (θ) with a slight abuse of notation)

E Ξ(θ, X r ) = 1 - ξ r 1 -β + βξ r + ξ β r 1 + βξ r 1 -β -1/2 1 √ 1-ξr (1 -y 2 ) -β dy = 1 - ξ r 1 -β + βξ r + 1 2 ξ β r 1 + βξ r 1 -β -1/2 ξr 0 x -β √ 1 -x dx. When x is small, x -β / √ 1 -x ∼ x -β + x 1-β /2, so that ξr 0 x -β √ 1-x dx ∼ ξ 1-β r /(1 -β) + ξ 2-β r /(2(2 -β)) as ξ r is small. With this, we obtain E Ξ(θ, X r ) = 1 + 1 -4β + 2β 2 4(2 -β)(1 -β) 2 ξ 2 r + o(ξ 2 r ) = 1 + 1 -4β + 2β 2 4(2 -β) θ 2 + o(θ 2 ). (91)
Since 1-4β+2β 2 4(2-β) = 1-r 4(r-2) , this proves the lemma when r < 1.

Consider now the case where r ≥ 2. Notice that 1 < β ≤ 2 when r ≥ 2. It is easily seen from (50) that, for r > 1,

d dz P(Ξ(θ, X r ) < z) = β(θ(β-1)) β (z-1+θβ) β+1 if z ≥ 1 -θ 0 if z < 1 -θ, which yields E Ξ(θ, X r ) = βθ β (β -1)) β ∞ 1-θ √ z (z -1 + θβ) β+1 dz = 2βθ β (β -1) β (1 -θβ) β-1/2 ∞ 1-θ 1-θβ t 2 (t 2 -1) β+1 dt. (92)
We are now ready to address the case when r ≥ 2.

Assume first that r = 2, so that β = 2, ξ 2 ≡ ξ 2 (θ) = θ 1-2θ , and θ = ξ 2ξ+1 . By (92) we have

E Ξ(θ, X 2 ) = 4 (1 + 2ξ 2 ) -1/2 ξ 2 2 ∞ √ ξ 2 +1 t 2 (t 2 -1) 3 dt = 2 (1 + 2ξ 2 ) -1/2 ξ 2 2 ∞ ξ 2 √ y + 1 y 3 dy. Let h(y) = 1+ 1 2 y- √ y+1 y 3 .
We have (Hint: use L'Hôpital's rule to get the 2nd equality) lim

ξ 2 →0 2ξ 2 2 ∞ ξ 2 √ y+1 y 3 dy -1 -ξ 2 2ξ 2 2 log ξ 2 = lim ξ 2 →0 - ∞ ξ 2 h(y)dy log ξ 2 = lim ξ 2 →0 h(ξ 2 ) ξ -1 2 = lim ξ 2 →0 1 + 1 2 ξ 2 - √ ξ 2 + 1 ξ 2 2 = 1 8 , and 2ξ 2 2 ∞ ξ 2 √ y + 1 y 3 dy = 1 + ξ 2 + 1 4 ξ 2 2 log ξ 2 + o(ξ 2 2 log ξ 2 ). It follows that E Ξ(θ, X 2 ) = (1 + 2ξ 2 ) -1/2 2ξ 2 2 ∞ ξ 2 √ y + 1 y 3 dy = 1 -ξ 2 + O(ξ 2 2 ) 1 + ξ 2 + 1 4 ξ 2 2 log ξ 2 + o(ξ 2 2 log ξ 2 ) = 1 + 1 4 ξ 2 2 log ξ 2 + o(ξ 2 2 log ξ 2 ). ( 93
)
This proves the lemma when r = 2.

Finally, assume that r > 2. Recall that ξ r ≡ ξ r (θ) = (β-1)θ 1-βθ , so that θ = ξr βξr+β-1 and, by ( 92),

E Ξ(θ, X r ) = 2β 1 + β β -1 ξ r -1/2 ξ β r ∞ √ ξr+1 x 2 (x 2 -1) β+1 dx = β 1 + β β -1 ξ r -1/2 ξ β r ∞ ξr √ y + 1 y β+1 dy. Let h(y) = 1 + 1 2 y - √ y + 1 y β+1 .
Note that h(y) > 0 for y > 0. As y → ∞, h(y) ∼ 1 2 y -β . As y → 0, h(y) ∼ 1 8 y 1-β . Since β ∈ (1, 2) for r > 2, the generalized integral I β := β ∞ 0 h(y)dy is finite and positive. Therefore,

lim ξr→0 βξ β r ∞ ξr √ y+1 y β+1 dy -1 -β 2(β-1) ξ r βξ β r = lim ξr→0 ∞ ξr √ y + 1 y β+1 dy - 1 β ξ -β r - 1 2(β -1) ξ 1-β r = lim ξr→0 - ∞ ξr h(y)dy = - I β β , and
βξ β r ∞ ξr √ y + 1 y β+1 dy = 1 + β 2(β -1) ξ r -I β ξ β r + o(ξ β r ). It follows that E Ξ(θ, X r = 1 + β β -1 ξ r -1/2 βξ β r ∞ ξr √ y + 1 y β+1 dy = 1 - β 2(β -1) ξ r + O(ξ 2 r ) 1 + β 2(β -1) ξ r -I β ξ β r + o(ξ β r ) = 1 -I β ξ β r + o(ξ β r ). (94)
This proves the lemma when r > 2.

F Appendix

Lemma F.1.

lim n D n = 0, (95)
where D n is defined in (61).

Proof. Fix > 0. Since ∆ 2 (z) = o(z 2 log z) there exists z > 0 such that for all 0 < z < z , ∆ 2 (z) z 2 log z < . Since for all n such that δ φ(n)-2δ < z we have ξ 2 = δe -µv φ(n)-2δe -µv < z for all v ≥ 0 (Hint: the mapping v → ξ 2 is nonincreasing in [0, ∞) and ξ 2 = δ φ(n)-2δ when v = 0), we conclude that for n large enough,

sup v≥0 ∆ 2 (ξ 2 ) ξ 2 2 log ξ 2 < . (96)
Hence, for n large enough,

|D n | ≤ 1 4 + ∞ 0 λe -(λ+2µ)v log ξ 2 (φ(n) -2δe -µv ) 2 dv = 1 4 + ∞ 0 λe -(λ+2µ)v log(φ(n) -2δe -µv ) + µv -log δ (φ(n) -2δe -µv ) 2 dv. (97)
For n large enough

a n (v) := log(φ(n) -2δe -µv ) + µv -log δ (φ(n) -2δe -µv ) 2 (98)
≤ µv -log δ + | log(φ(n) -2δe -µv )| (φ(n) -2δe -µv ) 2
for all v ≥ 0. It is easy to check that for all n such that φ(n) > 2δ + √ e, the mapping v → log(φ(n)-2-δe -λv ) (φ(n)-2δe -λv ) 2

is non-decreasing in [0, ∞). Therefore, for all n such that φ(n

) > 2δ + √ e, log(φ(n) -2δe -µv ) (φ(n) -2δe -µv ) 2 ≤ log(φ(n) -2δ) (φ(n) -2δ) 2 for all v ≥ 0.
This shows that for all n such that φ

(n) > 2δ + √ e [Hint: φ(n) -2δe -λv > 1 for all v ≥ 0 when φ(n) > 2δ + √ e] | log(φ(n) -2δe -µv )| (φ(n) -2δe -µv ) 2 = log(φ(n) -2δe -µv ) (φ(n) -2δe -µv ) 2 ≤ log(φ(n) -2δ) (φ(n) -2δ) 2 ∀v ≥ 0. ( 99
)
We conclude from (98) and (99) that for n large enough [Hint: for n large enough, log(φ

(n) -2δ)/(φ(n) - 2δ) 2 ) < 1 since log t/t 2 → 0 as t → ∞ and φ(n) → ∞ as n → ∞] 0 ≤ a n (v) ≤ µv + 1 -log δ for all v ≥ 0.
Since for every v ≥ 0, a n (v) → 0 as n → ∞ (cf. (98)), and

∞ 0 λe -(λ+2µ)v (µv + 1 -log δ)dv = λµ (λ + 2µ) 2 + λ(1 -log δ) λ + 2µ < ∞,
f n (v) = n (log (φ(n) -2δe -µv ) -log δ + µv) (φ(n) -2δe -µv ) 2 1 4 + ∆ 2 (ξ 2 ) ξ 2 2 log ξ 2 . ( 101
)
For any v ≥ 0 and δ ∈ (0, 1), we see from (101) that

f n (v) ≥ n(log φ(n) -2) (φ(n) -2δe -µv ) 2 1 4 + ∆ 2 (ξ 2 ) ξ 2 2 log ξ 2 . ( 102
)
Thanks to assumption (59), log φ(n) > 2 for n large enough. Also, by (96) sup v≥0

∆ 2 (ξ 2 ) ξ 2 2 log ξ 2
can be made arbitrarily small by letting n → ∞. These two properties combined show from (102) that f n (v) ≥ 0 for n large enough.

On the other hand, from (96) and (101) we see that, for n large enough,

f n (v) ≤ 1 4 + n log φ(n) -log δ + µv (φ(n) -2) 2
, ∀v ≥ 0.

Therefore, for n large enough ,

0 ≤ ∞ 0 λe -(λ+2µ)v f n (v)dv ≤ 1 4 + ∞ 0 λe -(λ+2µ)v n log φ(n) -log δ + µv (φ(n) -2) 2 dv = 1 4 + λ λ + 2µ n log φ(n) -log δ + µ/(λ + 2µ) (φ(n) -2) 2 ∼ n 1 4 + λ λ + 2µ n log φ(n) φ(n) 2 , (103)
by using that lim n φ(n) = ∞. We are left with finding φ such that n log φ(n) φ(n) 2

= O(1).

To this end let T (n) = O( n/ log n) or, equivalently by (58), lim inf n φ(n) √ n log n = a for some a > 0. Let us write n log φ(n)/φ(n)

when T (n) = O( n/ log n), which completes the proof.

Lemma F. [START_REF] Bash | Square root law for communication with low probability of detection on awgn channels[END_REF].

lim n E n = 0, ( 106
)
where E n is defined in (65).

Proof. Fix > 0. Since ∆ r (z) = o(z β ) when r > 2, there exists z > 0 such that for all 0 < z < z , ∆r(z) z β < . Since for all n such that δ(β-1) φ(n)-δβ < z we have ξ r = δ(β-1) e µv φ(n)-δβ < z for all v ≥ 0 (Hint: the mapping v → ξ r is nonincreasing in [0, ∞) and ξ r = δ(β-1) φ(n)-δβ when v = 0), we conclude that for n large enough,

G Appendix

Lemma G.1. For any θ ∈ [0, 1], r ≥ r, E Ξ(θ, X r ) ≤ E Ξ(θ, X r ) .

Proof. Fix θ ∈ [0, 1]. When r ≥ r then X r ≤ st X r , which in turn implies that Ξ(θ, X r ) ≤ st Ξ(θ, X r ) as the mapping x → Ξ(θ, x) in (50) is nondecreasing in [0, ∞),

Therefore, E Ξ(θ, X r ) ≤ E Ξ(θ, X r ) , as the mapping x → √ x is nondecreasing in [0, ∞).

H Appendix: Proof of Proposition 5.5

Recall that under the IEBP policy the system behaves as an M/G/1 queue with an exceptional first job in each busy period. The service times of first jobs in busy periods have pdf f 1 and the service times of the other jobs have pdf g 1 . The numbers of jobs served in different busy periods are iid rvs, characterized by the random variable M , so that the expected number of Willie jobs served during n W-BPs is

T W (n) = nE[M ].

Figure 1 :

 1 Figure 1: Glossary of main notations

Theorem 1 .

 1 ([15, Theorem 13.1.1])

Lemma 6 . 1 .

 61 The Hellinger distance between f ⊗n 0

4 + ∆ 2 (ξ 2 ) ξ 2 2 log ξ 2 ,

 422 we may apply the Bounded Convergence Theorem to the sequence {a n (v)} n , to get from (λ+2µ)v lim n a n (v)dv = 0. This concludes the proof of the lemma.Lemma F.2. Assume that T (n) = O( n/ log n). Then nD n is bounded as n → ∞. Proof. Define f n (v) := -n log ξ 2 (φ(n) -2δe -µv ) 2 1 so that (cf. (61)) nD n = -∞ 0 λe -(λ+2µ)v f n (v)dv. (100) Since ξ 2 = δe -µv φ(n)-2δe -µv , f n (v) rewrites

= 0 thanks again to lim x→∞ log x x = 0 . 2 = O( 1 )

 021 This shows thatn log φ(n) φ(n) when T (n) = O( n/ log n),and therefore by (103) and (100), that nD n = O(1),

  n large enough,|E n | ≤ (I β + ) ∞ 0 λe -λv (φ(n)e µv -δβ) β dv ≤ I β + (φ(n) -δβ) β ∞ 0 λe -λv dv = I β + (φ(n) -δβ) β → 0 as n → ∞. Lemma F.4. Assume that T (n) = O(n µ 2 /µ 1 ) with µ 1 > 2µ 2 . Then E n defined in (65) is bounded as n → ∞. Proof. Define k n (v) = n I β -∆ r (ξ r )/ξ β r (e µβv φ(n) -δβ) β ,(108)where I β is defined in (54). With this new function we can rewrite nE n (cf. (65)) asnE n = ∞ 0 λe -λv k n (v)dv. (109)Notice thatk n (v) = I β -∆ r (ξ r )/ξ β r (e µβv φ(n)/n 1/β -δβ/n 1/β ) β ≤ I β -∆ r (ξ r )/ξ β r (φ(n)/n 1/β -δβ/n 1/β ) β ,(110)for all n ≥ 1 and v ≥ 0. Recall that I β > 0. Let < I β in (107). From (110) we see that for n large enough0 ≤ k n (v) ≤ I β + (φ(n)/n 1/β -δβ/n 1/β ) β for all v ≥ 0. (111) Recall that β = r r-1 yielding r = β β-1 . Assume that T (n) = δ nφ(n) = O(n 1/r ) for δ ∈ (0, 1), or equivalently lim inf n φ(n) n 1/β = bfor some b > 0. From (111) we obtain0 ≤ lim sup n ∞ 0 λe -λv k n (v)dv ≤ lim sup n I β + (φ(n)/n 1/β -δβ/n 1/β ) β = I β + (lim inf n φ(n)/n 1/β ) β = I β + b β .(112)This shows that nE n ∈ O(1).

  1 > 0, and that Alice jobs have service time distribution G 2 with continuous pdf g 2

	General
	λ	arrival rate Willie jobs
	G 1 , g 1	cdf, pdf Willie job service time
	G 2 , g 2	cdf, pdf Alice job service time
	1/µ 1	Willie job expected service time
	1/µ 2	Alice job expected service time
	H 0	null hypothesis (Alice does not insert jobs)
	H 1	alternate hypothesis (Alice inserts jobs)
	T V (u 0 , u 1 )	variation distance between pdfs u 0 and u 1
	H(u 0 , u 1 )	Hellinger distance between pdfs u 0 and u 1
	X	random variable (rv) with pdf g 1
	IEBP policy
	W-BP	Willie Busy Period
	Y	Willie first job reconstructed service time
	V	Willie idle period duration (exp. rate λ)
	f

Clearly pi,j(wj) = R n-1 pi,n(w1:n)dw1 • • • dwj-1dwj+1 • • • dwn.

The research of this author was supported by the US NSF grant CNS-1564067 and the LABEX MILYON (ANR-10-LABX-0070) of Universit de Lyon, within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR).

Let µ 1 = rµ and µ 2 = µ. For r = 1, define β = r r-1 and note that r = β β-1 and 1 -β = 1 r-1 . Let X r denote an exponential rv with rate µr.

For θ ∈ [0, 1], x ≥ 0, define Ξ(θ, x) = 1 + θ(µx -1) if r = 1 1 + θ e (r-1)µx r-1

By specializing Z(q, x, v) in [START_REF] Sobers | Covert communication in the presence of an uninformed jammer[END_REF] to the case where g i (x) = µ i e -µ i x for i = 1, 2, we obtain from (23) that

One the other hand, by (45) and the fact that Ξ(θ, x) is linear in θ,

where we have used that p = λ/(µ 2 +λ) (see ( 4)) when Alice job service times are exponentially distributed.

For θ ∈ [0, 1], define

for r ≥ 2 (i.e. 1 < β ≤ 2), and

for r > 2. Since β ∈ (1, 2) when r > 2, the generalized integral I β is finite and positive.

where, for t > 0,

Then, for r

The proof of Lemma 9.1 is given in Appendix E.

Since ξ r (θ) defined in (53) will only be evaluated at θ = qe -µv with q = δ/φ(n) and δ ∈ [0, 1], thereby yielding ξ r (θ) = (β-1)δ e µv φ(n)-βδ , we omit the argument θ in ξ r (θ) to simplify notation.

We are now ready to prove Proposition 5.4. Recall that at the beginning of an idle period, Alice inserts a job with probability q(n)

A Appendix: Proof of Lemma 4.1

Let p i,n (w 1:n ) be the pdf of W 1:n = (W 1 , . . . , W n ) at w 1:n = (w 1 , . . . , w n ) under H i for i = 0, 1. Also let p i,j (w j ) be the pdf 1 of W j at w j under H i for i = 0, 1. Note that p i,n (resp. p i,j ) is a generalized pdf since W 1:n (resp. W j ) contains integer and continuous components.

By the general multiplicative formula,

Let w j = (m j , a (m j-1 +1):m j , s (m j-1 +1):m j ), y j = s m j-1 +1 , and v j = a m j-1 +1 -d m j-1 . We have

since the probability distribution of the number of customers served in a busy period in an M/G/1 queue is entirely determined once we know the duration of the first service time in this busy period [12, Chapter 5.9]. Hence,

where the latter density is independent of H 0 and H 1 . The pdf p i,1 (w 1 ) is given by the r.h.s. of (78) by letting j = 1. Putting (77) and (78) together yields the factorization result

which proves that (Y

B Appendix

Recall that Z(q, y, v)

We conclude from the above that E[ρ(X, V ) 2 ] < ∞ if and only if

for all l, m = 1, . . . , K 2 .

Case 1:

,i ≥ 0 for all i and K 1 i=1 p 1,i = 1, namely, Willie job service times follow an hyper-exponential distribution with mean 1/µ 1 = K 1 i=1 1/µ 1,i . We have

The second, third, and fourth integrals in the r.h.s. of (84) are finite since lim x→∞

This shows that C 0 < ∞ when (85) holds.

In particular, when K 1 = K 2 = 1 (exponential service times for both Alice and Willie jobs) then C 0 < ∞ if and only if µ 1 < 2µ 2 . For further reference, note that

Case 2:

We have, with η l :=

Integrating by part gives

with

|z| ≤ 1, the generating function of the number of jobs served in a busy period. Recall (Section 4) that the reconstructed service times of the first job served in different busy periods are iid rvs, and let Y be a generic reconstructed service time. Let τ * (s) = E[e -Y s ] = ∞ 0 e -sx f 1 (x)dx be the LST of the reconstructed service time. Since the LTS of the service times all the other Willie jobs in a W-BP is G * 1 (s), we get from [START_REF] Bhat | On the busy period of a single server bulk queue with modified service mechanism[END_REF] G

where d(z) is the root with the smallest modulus of the equation t = zG * 1 (λ(1 -t)). Noting that d(1) = 1 and d d(z) | z=1 = 1 1-λ/µ 1 , we obtain from ( 113)

provided that the stability condition λ/µ 1 < 1 holds. It remains to find E[Y ]. For that, we will use the identity E[Y ] = -dτ * (s) ds | s=0 . But before that we need to calculate τ * (s). When IEBP is enforced (or, equivalently, under H 1 ) we know that Y has pdf f 1 (see Section 4.2) . Multiplying both sides of (46) by g 1 (x) and using the definition of Z(q, x) in (35) along with (47) gives

where ĝ2 (x) is defined in (48). Therefore,

Differentiating (115) with respect to s at s = 0 and using the identity 2 ∞ 0 ĝ2 (t)dt = p yields

,

and

Now we upper bound the integral in (116) and (117). We have Hence, E[M ] ≤ 1+qλ/µ 2 1-λ/µ 1 and T W (n) ≤ n 1+qλ/µ 2 1-λ/µ 1 . This shows the upper bound in (28). The lower bound is trivial.

If g 2 (x) = µ 2 e -µ 2 x then from (48) and (4) we find p = λ µ 2 +λ and ĝ2 (x) = λµ 2 (λ+µ 2 ) e -µ 2 x = pµ 2 e -µ 2 x , which yields (29).


Harold Van Heerde
email: h.j.w.vanheerde@ewi.utwente.nl

Nicolas Anciaux
email: nicolas.anciaux@inria.fr

Ling Feng

Peter M G Apers
email: apers@ewi.utwente.nl

Balancing smartness and privacy for the Ambient Intelligence

Ambient Intelligence (AmI) will introduce large privacy risks. Stored context histories are vulnerable for unauthorized disclosure, thus unlimited storing of privacy-sensitive context data is not desirable from the privacy viewpoint. However, high quality and quantity of data enable smartness for the AmI, while less and coarse data benefit privacy. This raises a very important problem to the AmI, that is, how to balance the smartness and privacy requirements in an ambient world. In this article, we propose to give to donors the control over the life cycle of their context data, so that users themselves can balance their needs and wishes in terms of smartness and privacy.

Introduction

A smart, anticipating, and learning environment will have a great impact on privacy. Ambient Intelligence will be everywhere, is invisible, has powerful sensing capabilities, and most of all has a memory [START_REF] Langheinrich | Privacy by design -principles of privacy-aware ubiquitous systems[END_REF]. One of the main difficulties with privacy in the ubiquitous computing, is the way how data is collected. When making a transaction with a web shop, it could be quite clear which kind of data is exchanged. Ubiquitous computing techniques however, such as small sensors, active badges [START_REF] Want | The active badge location system[END_REF], or cameras equipped with powerful image recognizing algorithms, often collect data when people are not aware of it [START_REF] Jiang | Approximate information flows: Socially-based modeling of privacy in ubiquitous computing[END_REF][START_REF] Little | Tumult and turmoil: privacy in an ambient world[END_REF]. In that case it is possible that people think they are in a closed private area (such as coffee rooms), but in reality they could be monitored by sensors in that room without being aware of it. This leads to asymetric information [START_REF] Jiang | Approximate information flows: Socially-based modeling of privacy in ubiquitous computing[END_REF]. Xiaodong et al state that the presence of asymmetric information is the heart of the information privacy problem in ubiquitous computing. In environments with significant asymmetry between the information knowledge of donor and collector, negative side effects as privacy violations are much harder to overcome.

Several techniques have been proposed in the literature which let donors of the data specify privacy policies, in order to give control about their data to the owners of that data [START_REF]W3C: Platform for privacy preferences (P3P) project[END_REF][START_REF] Byun | Micro-views, or on how to protect privacy while enhancing data usability[END_REF]. Although such policies are rich enough to let people control who, when, how long, and what kind of information can be disclosed to specific applications, enforcing those policies is usually done through access control. Only relying on access control mechanisms to protect against unauthorized disclosure of data, is not sufficient enough in terms of privacy protection [START_REF] Agrawal | Hippocratic databases[END_REF][START_REF] Hong | An architecture for privacy-sensitive ubiquitous computing[END_REF]. Perhaps the context databases can be trusted now, but they might not be in the future (due to the change of privacy regulation laws for example). Therefore, limited retention techniques are highly desirable to prevent large context histories to be disclosed.

A second problem of traditional privacy policies found in the literature is that they only provide means to express privacy wishes for specific applications. Usage of the data is known in advance, as is the purpose for which the data will be used. Purposes of traditional applications requiring (context) data are atomic in the sense that it is clearly known when purposes are fulfilled or not. For applications which will use context data to learn, infer, and thus to become smarter, it is not clear when such a purpose has been fulfilled, in other words, purposes are non-atomic. It is even unclear which services and applications will use the context data in the future.

For static databases containing large datasets with privacy sensitive data (like medical data), anonymization can be used to prevent disclosure of individual privacy sensitive data [START_REF] Sweeney | k-anonymity: A model for protecting privacy[END_REF][START_REF] Machanavajjhala | l-diversity: Privacy beyond k-anonymity[END_REF][START_REF] Chawla | Toward privacy in public databases[END_REF]. However, anonymization does not always give adequate privacy protection to everyone, and the usability of the data becomes sometimes lower than needed because individual privacy concerns and personal interests are not taken into account. Xiao et al [START_REF] Xiao | Personalized privacy preservation[END_REF] recognize this problem and propose to personalize the anonymization of privacy sensitive data.

The nature of data used in the ambient smart environments is different and more dynamic than that of traditional static data. The amount of smartness of applications is bound to the quantity and quality of the data they can use. The more accurate the data is, and the more data has been gathered from a certain individual, the better a smart application can learn from that data without user interaction [START_REF] Doom | Get smart: How intelligent technology will enhance our world[END_REF]. The challenge is to find the best balance between the quality and quantity of data at the one side, and the privacy sensitivity of the data at the other side.

Motivation

Consider a working environment where employees can access the Internet and rank their visited websites. These Internet browsing behaviors are monitored and recorded in a database. Employees can query the database to find interesting websites based on the ranking, and discuss with other employees who have visited and ranked the websites. However, because the starting and end times when an employee made a website visit are also recorded, it is possible to deduce the duration that an employee spends on the Internet per day. Thus, most employees may not want the system to record such sensitive information in the database although the employees do benefit from the offered smart query services. To compromise the smartness and privacy requirements, a self-regulation of sensitive information could be like: one hour/day later, degrade the employee id to his/her group id or even faculty id. In this way, s/he can still use such a query service as "give me interesting websites visited by the people from the database group last week ".

Approach

We let people (the authors of monitored events) specify Life-Cycle Policies which will be bound to the acquired sensitive data [START_REF] Anciaux | Implanting life-cycle privacy policies in a context database[END_REF]. Events are monitored and bound to a context tuple, which could contain author, location, time et cetera. This data is stored in a privacy aware context database system, which degrades the data progressively according to the policy. This way, context history can be considered as events (like a door has been opened ) bound to attributes describing those events. The context values exhibit a certain level of accuracy based on domain generalization graphs. Such generalization graphs together form a n-dimensional space, in which each dimension represents the accuracy of an attribute of the original data tuple. We consider that those levels of accuracy can be classified given the privacy of the information they represent, such that all possible combinations of accuracies form a n-dimensional cube. A life-cycle policy can be viewed as a path specification in this cube. Triggered by events (we consider both time and contextual events), the accuracy of context tuples progressively decreases when specified conditions are satisfied.

Case Study

A prototype of a system which monitors the Internet browsing behavior of users has been implemented. Websites visited by users will be monitored, enabling smart services like ranking websites, contacting users of the same interests, finding interesting websites visited by members of a certain group, calculation of anonymized statistics, and so on. From the privacy perspective, collecting this data (including times when people were active on the Internet) makes it for malicious parties possible to deduce (for the user) confronting information. Users can specify their life-cycle policies (e.g., degrade time to hour and person id to group after one hour, degrade URL to category after one month, see Figure 1), which are attached with the data and will be stored and executed within a privacy aware context database. By specifying a life-cycle policy, users are sure that data which has been degraded can no longer be misused by malicious parties. Hence, the amount of smartness is reduced to decrease the possibility of misusing the data, consequently increasing privacy.

Acknowledgments

Fig. 1 .

 1 Fig. 1. A LCP example with states (time, id, url) where φ stands for a deleted (or completely degraded) value