A Covert Queueing Channel

1

in FCFS Schedulers
AmirEmad Ghassami and Negar Kiyavash

arXiv:1707.07234v1 [] 23 Jul 2017

Abstract
We study covert queueing channels (CQCs), which are a kind of covert timing channel that may be exploited in
shared queues across supposedly isolated users. In our system model, a user modulates messages to another user via
his pattern of access to the shared resource scheduled in a first-come-first-served (FCFS) manner. One example of
such a channel is the cross-virtual network covert channel in data center networks resulting from the queueing effects
of the shared resource. First, we study a system comprising a transmitter and a receiver that share a deterministic and
work-conserving FCFS scheduler, and we compute the capacity of this channel. We also consider the effect of the
presence of other users on the information transmission rate of this channel. The achievable information transmission
rates obtained in this study demonstrate the possibility of significant information leakage and great privacy threats
brought by CQCs in FCFS schedulers.
Index Terms
Covert Queueing Channel, First-Come-First-Served Scheduler, Capacity Limit.

I. I NTRODUCTION
The existence of side and covert channels due to the fragility of isolation mechanisms is an important privacy
and security threat in computer networks. Such channels may be created across users which were supposed to be
isolated, resulting in information leakage. By definition, a covert channel is a hidden communication channel which
is not intended to exist in the system and is created furtively by users [2]. Covert channels may be exploited by a
trusted user, or possibly a malware inside a system with access to secret information to leak it to a distrusted user.
On the other hand, in a side channel a malicious user attempts to learn private information by observing information
not intended for him. In this scenario, there is no collaboration between the source of information and the recipient
[3].
AmirEmad Ghassami is with the Department of Electrical and Computer Engineering and, the Coordinated Science Lab, University of
Illinois at Urbana-Champaign, Urbana, IL, email: ghassam2@illinois.edu. Negar Kiyavash is with the Department of Electrical and Computer
Engineering, Department of Industrial and Enterprise Systems Engineering and, the Coordinated Science Lab, University of Illinois at UrbanaChampaign, Urbana, IL, email: kiyavash@illinois.edu. The results in this paper were presented in part at the 2015 IEEE International Symposium
on Information Theory, Hong Kong, June 14 - June 19, 2015 [1].

A special case of covert and side channels is a timing channel in which information is conveyed through timing
of occurrence of events (e.g., inter-arrival times of packets). For instance, queueing covert/side timing channels may
arise between users who share a packet scheduler in a network.
Packet schedulers serve packets from multiple streams which are queued in a single queue. This causes dependencies between delays observed by users. Particularly, the delay that one user experiences depends on the amount of
traffic generated by other streams, as well as his own traffic. Hence, a user can gain information about other users’
traffic by observing delays of his own stream. This dependency between the streams can breach private information
as well as create hidden communication channels between the users.
One example of a covert/side queueing channel is the cross-virtual network covert channel in data center networks
and cloud environments. In recent years, migrating to commercial clouds and data centers is becoming increasingly
popular among companies that deal with data. The multi-tenant nature of cloud and sharing infrastructure between
several users has made data protection and avoiding information leakage a serious challenge in such environments
[4]. In data center networks, software-defined-networks are frequently used for load balancing [5]. This generates
logically isolated virtual networks and prevents direct data exchange. However, since packet flows belonging to
different VNs inevitably share underlying network infrastructure (such as a router or a physical link), it is possible
to transfer data across VNs through timing channels resulting from the queueing effects of the shared resource(s).
In this paper, we study covert queueing channels (CQCs) in a shared deterministic and work-conserving firstcome-first-served (FCFS) scheduler. We present an information-theoretic framework to describe and model the data
transmission in this channel and calculate its capacity. First, we consider the two users setting and then study the
effect of the presence of a third user on the information transmission rate. The approach for analyzing the effect
of the presence of the third user may be extended to calculate the capacity of the covert queueing channel serving
any number of users.
The rest of this paper is organized as follows: We review related works in Section II. In Section III, we describe
the system model. The capacities of the introduced channel for the two and three user cases are calculated in
Sections IV and V, respectively. Our concluding remarks are presented in Section VI.
II. R ELATED W ORKS
The existing literature on covert/side timing channels has mainly concentrated on timing channels in which the
receiver/adversary has direct access to the timing sequence produced by the transmitter/victim or a noisy version
of it. However, in a covert/side queueing channel, the receiver/adversary does the inference based on the timing of
his own packets which has been influenced by the original stream.
In a queuing side channel, where a malicious user, called an attacker, attempts to learn another user’s private
information, the main approach used by the attacker is traffic analysis. That is, the attacker tries to infer private
information from the victim’s traffic pattern. The attacker can have an estimation of the features of the other user’s

2

Node 𝑈𝑒𝑇

FCFS
Scheduler

Node 𝑈𝑑𝑇

Node 𝑈𝑒𝑅

Node 𝑈𝑑𝑅

Fig. 1: Covert queueing channel in a system with 2 users.

stream such as packet size and timing by emitting frequent packets in his own sequence. Previous work shows
that through traffic analysis, the attacker can obtain various private information including visited web sites [6], sent
keystrokes [7], and even inferring spoken phrases in a voice-over-IP connection [8].
In [9], Gong et al. proposed an attack where a remote attacker learns about a legitimate user’s browser activity by
sampling the queue sizes in the downstream buffer of the user’s DSL link. The information leakage of a queueing
side channel in an FCFS scheduler is analyzed in [10]. The analysis of more general work-conserving policies has
been done in [11] and [12]. The authors in [12] present an analytical framework for modeling information leakage
in queuing side channels and quantify the leakage for several common scheduling policies.
Most of the work in covert timing channels is devoted to the case in which two users communicate by modulating
the timings, and the receiver sees a noisy version of the transmitter’s inputs [13]–[21]. Also, there are many works
devoted to the detection of such channels [14], [22], [23]. The setup of CQC is new in the field of covert channels
and as far as the authors are aware, there are very few works on this setup [24], [25].
III. S YSTEM D ESCRIPTION
Consider the architecture depicted in Figure 1. In this model, a scheduler serves packets from 2 users: Ue and Ud .
Each user, Ui , i ∈ {e, d}, is modeled by a transmitter and a receiver node, denoted by UiT and UiR , respectively.
UiR is the node which receives UiT ’s packet stream. Note that UiT and UiR could correspond to the uplink and
downlink of the same entity. Ue intends to send a message to Ud , but there is no direct channel between them.
However, since UeT and UdT ’s packets share the same queue, UeT can encode messages in the arrival times of its
packets, which are passed onto Ud via queueing delays. Therefore, a timing channel is created between users via
the delays experienced through the coupling of their traffic due to the shared scheduler.
To receive the messages from Ue , user Ud sends a packet stream from the node UdT . He then uses the delays
he experiences by receiving the packet stream at UdR to decode the message. Therefore, effectively, the nodes UeT

3

Arrived stream
of the scheduler

Ai

A i+1

Time

User e's output
stream

User d's output
stream

Time

Di

D i+1
Time

Fig. 2: An example of the input and output streams of the FCFS scheduler serving two users. Red packets belong
to Ue and blue packets belong to Ud . We assume that one packet is buffered in the queue at time Ai .

and UeR are on the encoder side and the nodes UdT and UdR are on the decoder side of the channel of our interest.
Throughout the paper, we call Ud ’s sent stream the probe stream.
We consider an FCFS scheduler, which is commonly used in DSL routers. We assume this scheduler is deterministic and work-conserving. Time is discretized into slots, and the scheduler is capable of processing at most one
packet per time slot. At each time slot, each user either issues one packet or remains idle. Furthermore, we assume
that all packets are the same size.
Figure 2 shows an example of the input and output streams of the system depicted in Figure 1 with an FCFS
scheduler. In this figure, the first stream is the arrival stream i.e., arrivals from both UeT and UdT , depicted by red
and blue, respectively. The second stream is the output stream of user Ue (received by UeR ), and the third one is the
output stream of user Ud (received by UdR ). In this example, we assume that one packet is buffered in the queue at
time Ai , where a packet arrives from both UdT and UeT . If user Ue had not sent the two packets (depicted in red),
the second packet of user Ud which arrives at time Ai+1 could have departed one time slot earlier. Therefore, Ud
knows that Ue has issued two packets.
Throughout the paper, we assume that the priorities of the users are known. Particularly, without loss of generality,
we assume that Ud has the highest priority among all users; i.e., in the case of simultaneous arrivals, Ud ’s packet
will be served first.
As mentioned earlier, at each time slot, each user is allowed to either send one packet or none; hence, the input
and output packet sequences of each user could be viewed as a binary bitstream, where ‘1’ and ‘0’ indicates whether
a packet was sent or not in the corresponding time slot.

4

Assume message W drawn uniformly from the message set {1, 2, ..., M } is transmitted by UeT , and Ŵ is Ud ’s
estimate of the sent message. Our performance metric is the average error probability, defined as follows:
Pe , P (W 6= Ŵ ) =

M
X
1
P (Ŵ 6= m|W = m).
M
m=1

Ue encodes each message into a binary sequence of length n, ∆n , to create the codebook, which is known at the
decoder, Ud .
In order to send a message, UeT emits a packet in the i-th time slot if ∆i = 1 and remains idle otherwise, i.e.,


 1
⇒ UeT issues a





packet in time slot i.
∆i =


0
⇒ UeT remains





idle in time slot i.
To decode this message, UdT sends a binary length n stream (the probe stream) to the scheduler during the same
length n time period. User Ud will use this stream and the response stream received at node UdR to decode the sent
message.

We define the code, rate of the code, and the channel capacity similar to the definitions in [13], [26] and [27], as
follows:
Definition 1. An (n, M, )-code consists of a codebook of M equiprobable binary codewords, where messages take
on average n time slots to be received, and the error probability satisfies Pe ≤ .
Definition 2. The information transmission rate, R, of a code is the amount of conveyed information (logarithm
of the codebook size) normalized by the average number of used time slots for the message to be received, i.e.,
R=

log M
.
n

Rate may be interpreted as the average amount of information conveyed in a single time slot.
Definition 3. (Channel Capacity) The Shannon capacity, C, for a channel is the maximum achievable rate at which
one can communicate through the channel when the average probability of error goes to zero. In other words, C
is the suprimum of rates, R, which satisfies the following property [27]:
∀δ > 0, ∃(n, M, n )-code

 log M > R − δ
n
s.t.
  →0
n
The following notations will be used through out the paper:

5

as n → ∞.

•

ri : UiT ’s packet rate.

•

Ai : Arrival time of the i-th packet in the probe stream.

•

Di : Departure time of the i-th packet of the probe stream.

•
•

m
We assume m packets are sent by Ud during n time slots and we have: rd = lim
.
n→∞ n
PAi+1 −1
Xi : Number of Ue ’s packets sent in the interval [Ai , Ai+1 ). Note that Xi = j=Ai ∆j .
Ti = Ai+1 − Ai : inter-arrival time between i-th and (i + 1)-th packet of the probe stream. We denote a
realization of T by τ .

•

Yi = Di+1 − Di − 1

•

X̂i : estimation of Xi by decoder.

•

Ŵ : decoded message.

In an FCFS scheduler, Ud can have an estimation of the number of the packets of other users between any of
his own consecutive packets. The estimation of the number of packets in the interval [Ai , Ai+1 ) is accurate if the
scheduler is deterministic and work-conserving and a sufficient number of packets is buffered in the queue at time
Ai 1 . In that case, the number of other users’ packets arriving in the interval [Ai , Ai+1 ) could be simply calculated
by Di+1 − Di − 1. Note that Ud cannot pinpoint the location of the sent packets; that is, if the inter-arrival time is
τ , Ud can distinguish between τ + 1 different sets of bit streams sent during this time. Therefore, we look at any
probe stream sent during n time slots as a combination of different inter-arrival times.
If the sum of the packet rates of the users used during sending a message of length n is on average larger than
1, then the message will be arrived on average during more than n time slots. Also, this will destabilize the input
queue of the scheduler. For example, for a system with two users Ud and Ue , if UdT sends packets in every time
slot, then sending a packet by UeT in any time slot would cause a delay in the serving of the next packet of UdT
and hence could be detected. Therefore, in each time slot, UeT could simply idle to signal a bit ‘0’ or send a packet
to signal a bit ‘1’, resulting in the information rate of

1
1.5

bit per time slot in the case that bits are equiprobable.

But, this scheme is not feasible in practice as it would destabilize the queue and result in severe packet drops.
In order to have queue stability, it suffices that the total packet arrival rate does not exceed the service rate, which
for a deterministic and work-conserving scheduler is equal to 1 (see Appendix A for the proof of stability which
is based on a Lyapunov stability argument for the general case that the serving rate is assumed to be 0 ≤ ρ ≤ 1
1 If

the service rate of the scheduler is equal to 1, there should be at least Ai+1 − Ai − 1 packets buffered in the queue at time Ai . Therefore,

user Ud needs to know the queue length. This is feasible using the following formula:
q(Ai ) = Di − Ai − 1
where q(Ai ) denotes the queue length at the time that the i-th packet in the probe stream arrives at the queue. The extra 1 in the formula is
the time needed for the i-th packet of the probe stream to be served. Therefore, user Ud should always be aware of the queue length and keep
it sufficiently large by sending extra packets when needed.

6

and arbitrary number of users is considered). Specifically, for the case of two users we need
re + rd < 1.

(1)

On the other hand, if the sum of the packet rates of the users used during sending a message of length n is
on average less than 1, the length of the input queue may go to zero, and consequently Ud may not be able to
count the number of packets of other users correctly. Note that increasing rd increases the resolution available for
user Ud and hence this user can have a better estimation of the number of other users’ sent packets. Therefore, in
the case of two users, in order to achieve the highest information rate, the operation point should tend to the line
re + rd = 1. Therefore, we focus on the coding schemes where the sum of the rates is held at 1, with considering
a preamble stage in our communication to guarantee sufficient queue length.
IV. T WO - USER C ASE
In this section, using achievability and converse arguments, the capacity of the introduced system is calculated
for a system with a deterministic and work-conserving FCFS scheduler serving packets from two users.
As depicted in Figure 1, user Ue is attempting to send a message to Ud through the covert queueing channel
between them. Note that since we have considered service rate of 1 for the FCFS scheduler and users can agree
on the packet stream sent by UdT ahead of time, the feedback UeR is already available at the encoder. Therefore,
the following Markov chain holds
W → X m → Y m → Ŵ .

(2)

Note that as mentioned earlier, if there is a sufficient number of packets buffered in the shared queue, X̂i could be
accurately estimated as Yi .
The main result of this section is the following theorem, the proof of which is developed in the rest of the section.
Theorem 1. The capacity of the timing channel in a shared FCFS scheduler with service rate 1 depicted in Figure
1 is equal to 0.8114 bits per time slot, which can be obtained by solving the following optimization problem:
1
C = sup αH̃(γ1 , 1) + (1 − α)H̃(γ2 , )
2
α,γ1 ,γ2
(3)

s.t.
1
α(γ1 + 1) + (1 − α)(γ2 + ) = 1,
2
where 0 ≤ α ≤ 1 and 0 ≤ γ1 , γ2 ≤

1
2

and the function H̃ : [0, 1] × { k1 : k ∈ N} 7→ [0, 1] is defined as:

1
1
H̃(γ, ) =
k
k

sup

H(X),

X∈{0,1,...,k}
E[X]=kγ

We first investigate some of the properties of the function H̃.

7

k ∈ N, 0 ≤ γ ≤ 1.

(4)

Lemma 1. Let Uk ∼ unif ({0, 1, ..., k}). The distribution which achieves the optimum value in (4) is the tilted
version of unif ({0, 1, ..., k}) with parameter λ:
eiλ
PX (i) = Pk
i=0

eiλ

,

i ∈ {0, 1, ..., k},

0
0
where λ = (ψU
)−1 (kγ), where the function ψU
(·) is the derivative of the log-moment generating function of Uk .
k
k

See Appendix B for the proof of Lemma 1.
Lemma 2. The function H̃ could be computed using the following expression:
1
1
∗
H̃(γ, ) = [log2 (k + 1) − ψU
(kγ) log2 e],
k
k
k

(5)

∗
where Uk ∼ unif ({0, 1, ..., k}), and the function ψU
(·) is the rate function given by the Legendre-Fenchel transform
k

of the log-moment generating function, ψUk (·):
∗
ψU
(γ) = sup{λγ − ψUk (λ)}.
k

(6)

λ∈R

In order to prove this lemma, first we note that for any random variable X defined over the set {0, 1, ..., k},
H(X) =

k
X

PX (i) log

i=0

=

k
X

1
PX (i)

PX (i) log (k + 1) −

i=0

k
X

PX (i) log

i=0

PX (i)
1
k+1

= log (k + 1) − D(PX ||Uk ),
where D(PX ||Uk ) denotes the KL-divergence between PX and Uk . Therefore, in order to maximize H(X), we
need to minimize D(PX ||Uk ). Using the following well-known fact [28] concludes the lemma.
∗
min D(PX ||Uk ) = ψU
(kγ) log2 e.
k

(7)

E[X]=kγ

Figure 3 shows the function H̃(γ, k1 ) for different values of γ and k ∈ {1, 2, 3}.
1
Lemma 3. The function H̃(·, ·) is concave in pair (γ, ) in the sense that for integers k1 , k2 , k3 , and for values
k
1
1
1
0 ≤ γ1 , γ2 , γ3 ≤ 1, and for α ∈ [0, 1] such that α(γ1 , ) + (1 − α)(γ3 , ) = (γ2 , ), we have:
k1
k3
k2
1
1
1
αH̃(γ1 , ) + (1 − α)H̃(γ3 , ) ≤ H̃(γ2 , ).
(8)
k1
k3
k2
See Appendix C for the proof of Lemma 3.
Substituting (5) in (3) and solving it, the capacity of the timing channel in the shared FCFS scheduler with
service rate 1 depicted in Figure 1 is equal to 0.8114 bits per time slot, achieved by α = 0.177, γ1 = 0.43 and
γ2 = 0.407.

8

1

k=1

1

k=2

0.8

0.8

k=3
0.6

~
H

0.6
0.4
0.4

0.2

0
1

0.2

0.8

1
0.6

0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

0.8
0.6

0.4

1

.

1
k

0.4

0.2

0.2
0

0

.

Fig. 3: H̃(γ, k1 ) for different values of γ and k ∈ {1, 2, 3}.

1
1
Lemma 4. For all γ ∈ [0, 1] and k ∈ N, we have H̃(γ, ) = H̃(1 − γ, ).
k
k
See Appendix D for the proof of Lemma 4.
In the following, the proof of Theorem 1 is given. The proof is based on converse and achievability arguments.
A. Converse
In the converse side, the ultimate goal is to prove that
1
C ≤ sup αH̃(γ1 , 1) + (1 − α)H̃(γ2 , )
2
α,γ1 ,γ2
s.t.
1
α(γ1 + 1) + (1 − α)(γ2 + ) = 1,
2
where 0 ≤ α ≤ 1 and 0 ≤ γ1 , γ2 ≤ 12 . We break the proof into two lemmas.
Lemma 5. For the timing channel in a shared FCFS scheduler with service rate 1 depicted in Figure 1, any code
consisting of a codebook of M equiprobable binary codewords, where messages take on average n time slots to
be received, satisfies

n

X
1
1
log M ≤
[πτ H̃(µτ , )] + n
n
τ
τ =1
where

Pn

τ =1

πτ (µτ + τ1 ) = 1 and for all τ , 0 ≤ µτ ≤ 12 . In this expression, n =

(9)
1
n (H(Pe )

+ Pe log2 (M − 1)),

πτ is the portion of time that user Ud sends packets with inter-arrival time equal to τ in the probe stream, and µτ
is UeT ’s average packet rate when the inter-arrival time is equal to τ .

9

Proof. We first we note that

1
(a) 1
log M = H(W )
n
n
(b) 1
= H(W |τ m )
n
1
1
= I(W ; Ŵ |τ m ) + H(W |Ŵ , τ m )
n
n
(c) 1
≤ I(W ; Ŵ |τ m ) + n
n
(d) 1
≤ I(X m ; Y m |τ m ) + n ,
n
where (a) holds because W is a uniform random variable over the set of messages {1, ..., M }, (b) follows from the
fact that the chosen message is independent of the inter-arrival time of decoder’s packets, (c) follows from Fano’s
inequality with n =

1
n (H(Pe )

chain in (2). Therefore

+ Pe log2 (M − 1)), and (d) follows from data processing inequality in Markov

1
1
log M ≤ [H(X m |τ m ) − H(X m |Y m , τ m )] + n
n
n
1
≤ H(X m |τ m ) + n
n
m
1X
≤
H(Xj |τ m ) + n
n j=1
m

≤

1X
max H(Xj |τ m ) + n ,
n j=1 PXj |τ m

In the maximization above, the mean of the distribution PXj |τ m is E[Xj |τ m ]. As mentioned in Section III, in
order to find the maximum information rate while having stability, we are interested in the asymptotic regime in
which the operating point is converging to the line re + rd = 1. Therefore, the information rate is upper bounded by
m
1X
E[Xj |τ m ] + rd = 1.
having the set of means, {E[X1 |τ m ], E[X2 |τ m ], ..., E[Xm |τ m ]} satisfying the constraint
n j=1
Let ξj =

E[Xj |τ m ]
.
τj

Using (4), we have
max

PXj |τ m
E[Xj |τ m ]=τj ξj

H(Xj |τ m ) = τj H̃(ξj ,

1
),
τj

(10)

where as mentioned in Lemma 1, the distribution for each Xj which achieves the maximum value in (10) is the
0
tilted distribution of Uτj with parameter λ, such that λ = (ψU
)−1 (τj ξj ). Therefore, we will have:
τ
j

1
1
log M ≤
n
n

m
X

τj H̃(ξj ,

j=1
m

1
) + n ,
τj

1X
τj ξj + rd = 1. The inter-arrival times take values in
n j=1
the set {1, 2, ..., n}. Therefore, in the summation above we can fix the value of inter-arrival time on the value τ
such that the set {ξ1 , ξ2 , ..., ξm } satisfies the constraint

10

and count the number of times that τj has that value. Defining mτ as the number of times that the inter-arrival
Pn
time is equal to τ (note that n = τ =1 τ · mτ ), we can break the summation above as follows
m

n

τ
1
1XX
1
log M ≤
[
τ H̃(µτ,k , )] + n
n
n τ =1
τ

k=1

mτ
n
1X X
1
=
[τ
H̃(µτ,k , )] + n
n τ =1
τ
k=1

mτ
n
X
1
1
1X
[τ · mτ
H̃(µτ,k , )] + n ,
=
n τ =1
mτ
τ
k=1

where µτ,k is equal to the k-th ξj which has τj = τ .
By Lemma 3, the function H̃(·, ·) is a concave function of its first argument. Therefore, by Jensen’s inequality,
mτ
X
1
1
1
H̃(µτ,k , ) ≤ H̃(µτ , ),
mτ
τ
τ

(11)

k=1

where µτ =

mτ
n
X
1 X
µτ,k . Using (11) and the equation n =
τ · mτ , we have:
mτ
τ =1
k=1

n

X
τ · mτ
1
1
[ Pn
log M ≤
H̃(µτ , )] + n
n
τ
τ =1 τ · mτ
τ =1
n
X

(12)

1
[πτ H̃(µτ , )] + n ,
=
τ
τ =1
where πτ =

Pnτ ·mτ
τ =1 τ ·mτ

.

The packet rates of the users could be written as follows:
m

n

m

τ
1X
1 XX
re =
τj ξj =
τ µτ,k
n j=1
n τ =1

k=1

mτ
n
n
X
1 X
1
1X
τ mτ
µτ,k =
τ mτ µτ
=
n τ =1
mτ
n
τ =1
k=1

=

n
X

n

X
τ · mτ
Pn
πτ µτ ,
µτ =
τ =1 τ · mτ
τ =1
τ =1

and
rd =

n
X

1
πτ .
τ
τ =1

Therefore, the constraint could be written as follows:
n
X
1
πτ (µτ + ) = 1.
τ
τ =1

(13)

Suppose the set of pairs {(µτ , τ1 )}nτ=1 satisfies (13) and maximizes the right hand side of (12). By Lemma 4, there
exists another set of pairs {(µ̂τ , τ1 )}nτ=1 with µ̂τ defined as

 µ
if 0 ≤ µτ ≤ 12 ,
τ
µ̂τ =
 1−µ
if 12 ≤ µτ ≤ 1,
τ

11

that gives the same value for the right-hand side of (12), but it has

Pn

τ =1

πτ (µ̂τ + τ1 ) ≤

Pn

τ =1

πτ (µτ + τ1 ). Therefore,

Ud can increase his packet rate and increase the information rate using the values µ̂τ . Hence, in the maximizing
set, for all τ , we have 0 ≤ µτ ≤ 12 . Therefore, the optimal operating point will be on the line re + rd = 1, with
0 ≤ re ≤

1
2

and

1
2

≤ rd ≤ 1.

Applying Lemma 3, we can replace all pairs of form (µτ , τ1 ), τ ≥ 2, with a single pair of form (µ, 21 ):
Lemma 6. For any set of pairs S = {(µτ , τ1 ), τ ∈ [n]} where for all τ , 0 ≤ µτ ≤ 21 , with weights {πτ , τ ∈ [n]}
with operating point on the line 0 ≤ re ≤

1
2

and

1
2

≤ rd ≤ 1, there exists 0 ≤ α ≤ 1 and 0 ≤ γ1 , γ2 ≤

1
2

such that

1
α(γ1 + 1) + (1 − α)(γ2 + ) = 1,
2
and

n
X

1
1
[πτ H̃(µτ , )] ≤ αH̃(γ1 , 1) + (1 − α)H̃(γ2 , ).
τ
2
τ =1
Proof. For all τ ∈ {3, ..., n}, there exists βτ ∈ [0, 1], such that
1
1
βτ (µ1 , 1) + (1 − βτ )(µτ , ) = (µτ2 , ),
τ
2
Clearly, the set {(µ1 , 1), (µ2 , 12 ), (µ32 , 12 ), ..., (µn2 , 12 )} can also give the same operating point as S does. By Lemma
3,
1
1
βτ H̃(µ1 , 1) + (1 − βτ )H̃(µτ , ) ≤ H̃(µτ2 , ),
τ
2

∀τ ∈ {3, ..., n},

Therefore,
n
X
1
1
1
ζτ (βτ H̃(µ1 , 1) + (1 − βτ )H̃(µτ , ))
πτ H̃(µτ , ) = ζ1 H̃(µ1 , 1) + ζ2 H̃(µ2 , ) +
τ
2
τ
τ =3
τ =1
n
X

n
X
1
1
ζτ H̃(µτ2 , )
≤ ζ1 H̃(µ1 , 1) + ζ2 H̃(µ2 , ) +
2
2
τ =3
Pn
ζ2 µ2 + τ =3 ζτ µτ2 1
≤ ζ1 H̃(µ1 , 1) + (1 − ζ1 )H̃(
, ),
1 − ζ1
2

where π1 = ζ1 +

Pn

τ =3 ζτ βτ ,

(14)

π2 = ζ2 and πτ = ζτ (1 − βτ ) for 3 ≤ τ ≤ n and we have used Lemma 3 again in

the last inequality.

From Lemmas 5 and 6, we have:
1
1
log M ≤ αH̃(γ1 , 1) + (1 − α)H̃(γ2 , ) + n
n
2
1
≤ sup αH̃(γ1 , 1) + (1 − α)H̃(γ2 , ) + n .
2
α,γ1 ,γ2

12

Letting n → ∞, n goes to zero and we have
1
C ≤ sup αH̃(γ1 , 1) + (1 − α)H̃(γ2 , )
2
α,γ1 ,γ2
s.t.
1
α(γ1 + 1) + (1 − α)(γ2 + ) = 1,
2
where 0 ≤ α ≤ 1 and 0 ≤ γ1 , γ2 ≤ 12 . This completes the proof of the converse part.
B. Achievability
The sequence of steps in our achievability scheme is as follows:
•

Set α = 0.177 − δ, for a small and positive value of δ.

•

Fix a binary distribution P1 such that P1 (1) = 0.43 and P1 (0) = 0.57. Generate a binary codebook C1
containing 2αnR1 sequences of length αn of i.i.d. entries according to P1 .
Fix a ternary distribution P2 over set of symbols {a0 , a1 , a2 } such that P2 (a0 ) = 0.43, P2 (a1 ) = 0.325 and
P2 (a2 ) = 0.245. Generate a ternary codebook C2 containing 2(1−α)nR2 sequences of length 21 (1 − α)n of i.i.d.
entries according to P2 . Substitute a0 with 00, a1 with 10 and a2 with 11, so we will have 2(1−α)nR2 binary
sequences of length (1 − α)n.
Combine C1 and C2 to get C, such that C has 2n(αR1 +(1−α)R2 ) binary sequences of length n where we
concatenate i-th row of C1 with j-th row of C2 to make the ((i − 1)(2(1−α)nR2 ) + j)-th row of C (note that
2(1−α)nR2 is the number of rows in C2 ). Rows of C are our codewords. In above, n should be chosen such
that αnR1 , αn, (1 − α)nR2 and 12 (1 − α)n are all integers.

•

Encoding: UdT sends the stream of all ones (one packet in each time slot) in the first αn time slots and sends
bit stream of concatenated 10’s for the rest of (1 − α)n time slots.
To send message m, UeT sends the corresponding row of C, that is, it sends the corresponding part of m from
C1 in the first αn time slots and the corresponding part of m from C2 in the rest of (1 − α)n time slots.

•

Decoding: Assuming the queue is not empty,2 since there is no noise in the system, the decoder can always
learn the exact sequence sent by Ue .

Consequently, we will have:
C≥

log2 2n(αR1 +(1−α)R2 )
n

= αR1 + (1 − α)R2 .
2 Since

in our achievable scheme, UdT ’s packets are spaced by either one or two time slots, it is enough to have one packet buffered in the

queue, where since we are working in the heavy traffic regime, it will not be a problem.

13

Node 𝑈𝑒𝑅

Node 𝑈𝑒𝑇
FCFS
Scheduler
Node 𝑈𝑝𝑇

Node 𝑈𝑝𝑅

Node 𝑈𝑑𝑇

Node 𝑈𝑑𝑅

Fig. 4: Covert queueing channel in a system with three users.

In infinite block-length regime, where n → ∞, we can choose R1 = H(P1 ), R2 = 21 H(P2 ) and find codebooks
C1 and C2 such that this scheme satisfies the rate constraint. Therefore,
1
C ≥ αH(P1 ) + (1 − α) H(P2 ).
2
Substituting the values in the expression above, and letting δ go to zero, we see that the rate 0.8114 bits per time
slot is achievable.
V. T HREE - USER C ASE
As an extension to the basic problem, in this section we consider the case that a third user is also using the
shared scheduler. We add user Up to our basic system model. This user has nodes UpT and UpR as his transmitter
and receiver nodes, respectively (Figure 4). We assume that the node UpT sends packets according to a Bernoulli
process with rate rp to the shared scheduler. The shared scheduler is again assumed to be FCFS with service rate
1 and we analyze the capacity for coding schemes satisfying queueing stability condition in the asymptotic regime
where the operating point is converging to the line re + rp + rd = 1. Also, in this section we consider the extra
assumption that the inter-arrival time of the packets in the probe stream is upper bounded by the value τmax .
Assuming that a sufficient number of packets are buffered in the shared queue, user Ud can still count the number
of packets sent by the other two users between any of his own consecutive packets, yet he cannot distinguish between
packets sent by user Ue and the packets sent by user Up . Hence, user Ud has uncertainty in estimating the values
of X. We model this uncertainty as a noise in receiving X. Suppose UdT sends two packets with τi = 2. Each
of the other users can possibly send at most 2 packets in the interval [Ai , Ai+1 ) and hence, Y ∈ {0, 1, 2, 3, 4}.
Therefore, we have the channel shown in Figure 5 for this example. In the general case, for the inter-arrival time

14

(1 − 𝑟𝑝 ) 2

0

(1 − 𝑟𝑝 ) 2

1
X

0
1

(1 − 𝑟𝑝 ) 2

2

2

Y

3
4
Fig. 5: Channel between the encoder and the decoder of the system for the case that the inter-arrival time of two
packets of the probe stream is 2.

𝑊

𝑋1

𝑌1

𝑋2

𝑌2

⁞

⁞

𝑋𝑚

𝑌𝑚

𝑊

Fig. 6: The graphical model representing the statistical relation between W , X m , Y m and Ŵ .

τ , given X = x, we have Y ∈ {x + 0, ..., x + τ } such that
 
τ
P r(Y = i + x|X = x) =
(rp )i (1 − rp )τ −i ,
i

i ∈ {0, ..., τ },

(15)

which is a binomial distribution Bin(τ, rp ). Therefore, the support of the random variable Y is {0, 1, ..., 2τ }. For
the mean of Y , we have:
E[Y |τ ] = E[E[Y |X, τ ]|τ ] = E[X + τ rp |τ ] = τ (re + rp ).

(16)

Because of user Up ’s stream, the encoder is not aware of the stream received at node UeR beforehand and
this output can provide information to the encoder about UpT ’s stream. The more packets node UeT sends to the
scheduler, the more information this stream contains about UpT ’s stream. Using this information, the encoder can
have an estimation of the output of the channel at the decoder’s side and hence it could be considered as a noisy
feedback to the encoder. Figure 6 shows the graphical model for random variables in our system.

15

The main result of this section is evaluation of the capacity of the introduced channel, presented in Theorem 2.
In the following, the subscript rp denotes that the calculation is done when the rate of Up is rp .
Theorem 2. If the rate of Up is rp , the capacity of the timing channel in a shared FCFS scheduler with service
rate 1 depicted in Figure 4 is given by
C(rp ) =

1
1
αI˜rp (γ1 , ) + (1 − α)I˜rp (γ2 ,
)
τ
τ
+
1
α,γ1 ,γ2 ,τ
sup

(17)

s.t.
α(γ1 +

1
1
) + (1 − α)(γ2 +
) = 1 − rp ,
τ
τ +1

where 0 ≤ α ≤ 1 and 0 ≤ γ1 , γ2 ≤ 1 and 1 ≤ τ ≤ τmax − 1. The function I˜rp : [0, 1] × { k1 : k ∈ N} 7→ [0, 1] is
defined as:
1
1
I˜rp (γ, ) =
k
k

sup

Irp (X; Y ),

k ∈ N, 0 ≤ γ ≤ 1.

(18)

X∈{0,1,...,k}
E[X]=kγ

The proof is based on converse and achievability arguments. Before giving the proof, we first investigate some
˜
of the properties of the function I.
Lemma 7. The function I˜rp could be computed using the following expression:
1
1
1
1
I˜rp (γ, ) = Ȟrp (γ, ) − H(Bin(k, rp )),
k
k
k
k
1
where Ȟrp (γ, ) =
k

sup

(19)

Hrp (Y ) and the second term is the entropy of the binomial distribution with

X∈{0,1,...,k}
E[X]=kγ

parameters k and rp .
See Appendix E for the proof of Lemma 7.
In order to calculate Ȟrp (γ, k1 ), the following optimization problem should be solved:
max log2 e

PX ≥0

2k
X
i=0

s.t.

PY (i) ln(

1
)
PY (i)


 Pk iP (i) = E[X] = kγ,
X
i=0
 Pk P (i) = 1,
i=0 X

(20)

where PY = PX ∗ PBin(k,rp ) , that is,
PY (i) =

k
X

PX (j)PBin(k,rp ) (i − j),

i ∈ {0, 1, ..., 2k}.

j=0

Figure 7 shows the functions I˜0 (γ, k1 ), I˜0.1 (γ, k1 ) and I˜0.2 (γ, k1 ) for different values of γ and k ∈ {1, 2, 3}.

16

(21)

1

0.9

k=1

0.8

k=2
k=3

0.7

1

1

0.9

0.9

0.8

0.8

0.7

0.7

k=1
0.6

0.6

0.6

I~0:2

I~0

I~0:1

k=2
0.5

0.5

k=3

k=2

0.4

0.4

0.3

0.3

0.3

0.2

0.2

0.2

0.1

0.1

0.1

0

0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

k=1

0.5

0.4

k=3

0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

0

1

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

.

.

.

Fig. 7: I˜rp (γ, k1 ) for different values of γ and k ∈ {1, 2, 3} and rp ∈ {0, 0.1, 0.2}.
1

0.9

0.8

0.7

C(rp )

0.6

0.5

0.4

0.3

0.2

0.1

0
0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

rp

Fig. 8: capacity of the timing channel in the shared FCFS scheduler of Figure 4 for different values of rp .

Lemma 8. For all 0 ≤ rp ≤ 1, integers 1 ≤ k1 , k2 , k3 ≤ τmax , values 0 ≤ γ1 , γ2 , γ3 ≤ 1, and α ∈ [0, 1] such
1
1
1
that α(γ1 , ) + (1 − α)(γ3 , ) = (γ2 , ), we have:
k1
k3
k2
1
1
1
(22)
αI˜rp (γ1 , ) + (1 − α)I˜rp (γ3 , ) ≤ I˜rp (γ2 , )
k1
k3
k2
See Appendix F for the proof of Lemma 8.
Using the mentioned properties, the capacity of the timing channel in the shared FCFS scheduler of Figure 4 for
different values of rp can be calculated. Figure 8 shows the value of the capacity with respect to rp .
The following proof of Theorem 2 is based on converse and achievability arguments.
A. Converse
Suppose the rate of Up is rp . Similar to the proof of Lemma 5, for the timing channel in a shared FCFS scheduler
with service rate 1 depicted in Figure 4, any code consisting of a codebook of M equiprobable binary codewords,

17

where messages take on average n time slots to be received, satisfies
1
1
log M ≤ Irp (W ; Ŵ |τ m ) + n
n
n
(a) 1
≤ Irp (W ; Y m |τ m ) + n ,
n
where n =

1
n (H(Pe )

+ Pe log2 (M − 1)) and (a) follows from data processing inequality in the model in Figure

6. Therefore,

m

1X
1
log M ≤
Ir (W ; Yj |Y j−1 τ m ) + n
n
n j=1 p
m

≤
(a)

1X
Ir (W, Y j−1 ; Yj |τ m ) + n
n j=1 p
m

≤

1X
Ir (Xj ; Yj |τ m ) + n
n j=1 p

≤

1X
max Ir (Xj ; Yj |τ m ) + n ,
n j=1 PXj |τ m p

m

where (a) again follows from data processing inequality in the model in Figure 6. In the maximization above, the
mean of the distribution PXj |τ m is E[Xj |τ m ] and in order to find the maximum information rate, the set of means,
m
1X
E[Xj |τ m ] +
{E[X1 |τ m ], E[X2 |τ m ], ..., E[Xm |τ m ]}, should satisfy the constraint re + rp + rd = 1, that is,
n j=1
rp + rd = 1. Let ξj =

E[Xj |τ m ]
.
τj

Using (18), we have:
max

PXj |τ m
E[Xj |τ m ]=τj ξj

Irp (Xj ; Yj |τ m ) = τj I˜rp (ξj ,

This implies that

1
).
τj

(23)

m

1X ˜
1
1
log M ≤
τj I(ξj , ) + n .
n
n j=1
τj
Next, using Lemma 8 and similar to the proof of Lemma 5, by breaking the summation, using Jensen’s inequality
τX
max
τ · mτ , we will have:
and the equation n =
τ =1
τX
max
1
1
log M ≤
πτ I˜rp (µτ , ) + n ,
n
τ
τ =1

(24)

τ · mτ
where µτ is the average of ξj ’s which have τj = τ and πτ = Pτmax
. In this expression, πτ could be
τ =1 τ · mτ
interpreted as the portion of time that user Ud sends packets with inter-arrival time equal to τ .
Also, using the same approach as the one used in the proof of Lemma 5, the constraint of the problem could be
written as follows:
τX
max
τ =1

πτ (µτ +

1
) = 1 − rp .
τ

18

(25)

Pτ
1
˜
Suppose the set of pairs S = {(µτ , τ1 ), τ ∈ [τmax ]} with weights {πτ , τ ∈ [τmax ]} gives τmax
=1 πτ Irp (µτ , τ )
P
τmax
1
1
and has its operating point on the line re + rd = 1 − rp , and we have τ1∗ ≤
τ =1 πτ τ ≤ τ ∗ +1 , for some
1 ≤ τ ∗ ≤ τmax − 1. We have

 β (µ ∗ , 1 ) + (1 − β )(µ , 1 ) = (µτ ∗ , 1 )
τ
τ +1 τ ∗ +1
τ
τ τ
τ
τ∗
 β (µ ∗ , 1 ) + (1 − β )(µ , 1 ) = (µτ ∗ , 1 )
τ

τ

τ∗

τ

τ τ

τ +1 τ ∗ +1

τ ≤ τ ∗ − 1,
τ ≥ τ ∗ + 2,

for some βτ ∈ [0, 1]. Clearly, the set
{(µ1τ ∗ ,

∗
∗
1
1
1
1
1
1
), · · · , (µττ ∗ −1 , ∗ ), (µτ ∗ , ∗ ), (µτ ∗ +1 , ∗
), (µττ ∗ +2
), · · · , (µττmax
)}
∗ +1 ,
+1 , ∗
∗
∗
τ
τ
τ
τ +1
τ +1
τ +1

can give the same operating point as S does. Therefore, using the technique presented in (14) and twice use of
Lemma 8 we have

1
1
1
log M ≤ αI˜rp (γ1 , ∗ ) + (1 − α)I˜rp (γ2 , ∗
) + n
n
τ
τ +1
1
1
) + n .
≤ sup αI˜rp (γ1 , ) + (1 − α)I˜rp (γ2 ,
τ
τ +1
α,γ1 ,γ2 ,τ

Letting n → ∞, n goes to zero and we get the desired result.
B. Achievability
Achieving the proposed upper bound could be done by a method exactly like the one used in Subsection IV-B.
We need to solve the optimization problem (17) to find parameters α, γ1 , γ2 and τ . Because of Lemma 8, in order
to find the optimal τ , we can start with τ = 1 and optimize other parameters and then calculate αI˜rp (γ1 , τ1 ) + (1 −
1
α)I˜rp (γ2 , τ +1
) and, in each step, increase the value of τ by 1, stopping whenever the obtained value is decreased

compared to the previous step. For instance, for rp ≤ 0.1, the optimal τ is 1, and hence the procedure stops after
checking two steps. After calculating parameters γ1 , γ2 and τ , the optimal input distribution could be obtained
using optimization problem (20).
VI. C ONCLUSION
We studied convert queueing channels (CQCs) that can occur through delays experienced by users who are
sharing a scheduler. As the scheduling policy plays a crucial role in the possible information transmission rate in
this type of channel, we focused on deterministic and work-conserving FCFS scheduling policy. An informationtheoretic framework was proposed to derive the capacity of the CQC under this scheduling policy. First, we studied
a system comprising a transmitter and a receiver that share a deterministic and work-conserving FCFS scheduler.
We obtained the maximum information transmission rate in this CQC and showed that an information leakage rate
as high as 0.8114 bits per time slot is possible. We also considered the effect of the presence of other users on
the information transmission rate of this channel. We extended the model to include a third user who also uses
the shared resource and studied the effect of the presence of this user on the information transmission rate. The
solution approach presented in this extension may be applied to calculate the capacity of the covert queueing channel

19

among any number of users. The achievable information transmission rates obtained from this study demonstrate
the possibility of significant information leakage and great privacy threats brought by CQCs in FCFS schedulers.
Based on this result, special attention must be paid to CQCs in high security systems. Finding the capacity of CQCs
under other scheduling policies, especially non-deterministic policies, remains to be done in the research area of
covert communications and is considered as the main direction for future work. Furthermore, a comprehensive study
is required to design suitable scheduling policies that can simultaneously guarantee adequate levels of both security
and throughput.
A PPENDIX A
P ROOF OF S TABILITY
For the system model with M users and service rate ρ, the arrival process has a Poisson binomial distribution
with probability mass function
P (K = k) =

X Y
A∈Fk i∈A

Y

ri

(1 − rj ),

j∈Ac

with support k ∈ {0, 1, ..., M }, where Fk is the set of all subsets of k integers that can be selected from
M
X
ri .
{1, 2, 3, ..., M }. The mean of this distribution is µ =
i=1

We denote arrival, service and queue length at time k, with a(k), s(k) and q(k), respectively, and we have
q(k + 1) = (q(k) + a(k) − s(k))+ .
Using Foster-Lyapunov theorem with Lyapunov function V (q(k)) = (q(k))2 and calculating the drift, we have
E[q 2 (k + 1) − q 2 (k)|q(k) = q] ≤ E[(q + a − s)2 − q 2 ]
= E[2q(a − s)] + E[(a − s)2 ],
where E[(a − s)2 ] is a constant and we denote it by K. Therefore, for some  > 0, if µ < ρ, for large enough
value of q, we have
E[q 2 (k + 1) − q 2 (k)|q(k) = q] ≤ 2q(µ − ρ) + K ≤ −,
which implies the stability.
A PPENDIX B
P ROOF OF L EMMA 1
In order to find the optimum distribution, PX , the optimization problem could be written as follows:
max log2 e

PX ≥0

k
X
i=0

s.t.

PX (i) ln(

1
)
PX (i)


 Pk iP (i) = E[X] = kγ,
X
i=0
 Pk P (i) = 1,
i=0 X

20

(26)

which could be solved using the Lagrange multipliers method. The Lagrangian function would be as follows:
k
X

PX (i) ln(

i=0

k
k
X
X
1
) + λ(
iPX (i) − kγ) + ρ(
PX (i) − 1).
PX (i)
i=0
i=0

Setting the derivative with respect to PX (i) equal to zero, we get ln( PX1(i) ) − 1 + iλ + ρ = 0, which implies that
PX (i) = eρ−1 · eiλ .

(27)

Also, from the second constraint we have
k
X
i=0

eρ−1 · eiλ = 1 ⇒ eρ−1 = Pk

1

i=0

eiλ

.

(28)

Combining (27) and (28), we have:
eiλ
PX (i) = Pk
i=0

eiλ

,

which is the tilted distribution of Uk with parameter λ.
In order to calculate λ, from the first constraint:
k
X

kγ =

k
X

iPX (i) =

k
X
i=0

i=0

eiλ

i Pk

i=0

eiλ

=

ieiλ

i=0
k
X

=
eiλ

E[Uk eUk λ ]
d
=
(ln E[eUk λ ])
U
λ
k
E[e
]
dλ

i=0
0
= ψU
(λ).
k

A PPENDIX C
P ROOF OF LEMMA 3
First we note that
1
1
∗
(kγ) log2 e]
H̃(γ, ) = [log2 (k + 1) − ψU
k
k
k
Pk
eiλ
1
1
)} log2 e]
= [ log2 (k + 1) − sup{kγλ − log( i=0
k
k λ
k+1
= −sup{γλ log2 e −
λ

k
X
1
log2 (
eiλ )}.
k
i=0

k
X
1
1
Therefore, if we can show that for any given λ the function h(γ, ) = γλ log2 e − log2 (
eiλ ) is convex, then
k
k
i=0

since the supremum of convex functions is convex, we can conclude the desired concavity of the function H̃(·, ·).
k
X
1
1
1 − e(k+1)λ
Noting that log2 (
eiλ ) = log2 (
), to prove the convexity of h(·, ·), it suffices to prove that the
k
k
1 − eλ
i=0
1

1 − e( x +1)λ
function g(x) = x log(
), 0 < x ≤ 1, is concave. This is true from the concavity of the function
1 − eλ
(x+1)λ
1−e
ĝ(x) = log(
), and the fact that for any function f , xf ( x1 ) is concave if f (x) is concave. The concavity
1 − eλ
of the function ĝ(·) can be easily seen by taking its second derivative.

21

A PPENDIX D
P ROOF OF L EMMA 4
∗
For a given γ and support set {0, 1, ..., k}, suppose the distribution PX
is defined over {0, 1, ..., k} and has mean

EP ∗ [X] = kγ and
sup
X∈{0,1,...,k}
E[X]=kγ

1
1
∗
H(X) = H(PX
).
k
k

Define distribution QX as follows:
∗
QX (i) = PX
(k − i),

0 ≤ i ≤ k,

∗
Therefore the entropy of QX will be the same as the entropy of PX
and we have

EQ [X] =

k
X

iQX (i) =

i=0

k
X

∗
iPX
(k − i) = −

i=0
k
X

=k−

k
X

∗
(−k + (k − i))PX
(k − i)

i=0

∗
(k − i)PX
(k − i) = k − kγ = k(1 − γ).

i=0

Hence, we have
1
1
1
1
∗
sup
H(X) = H(PX
) = H(QX ) ≤
H̃(γ, ) =
k
k
k
k
X∈{0,1,...,k}
E[X]=kγ

sup
X∈{0,1,...,k}
E[X]=k(1−γ)

1
1
H(X) = H̃(1 − γ, ).
k
k

(29)

Similarly, suppose for the distribution Q∗X , defined over {0, 1, ..., k} and with mean EQ∗ [X] = k(1 − γ),
sup
X∈{0,1,...,k}
E[X]=k(1−γ)

1
1
H(X) = H(Q∗X ).
k
k

Define distribution PX as follows:
PX (i) = Q∗X (k − i),

0 ≤ i ≤ k,

Therefore the entropy of PX will be the same as the entropy of Q∗X and we have
EP [X] =

k
X

iPX (i) =

iQ∗X (k

k
X
(−k + (k − i))Q∗X (k − i)
− i) = −

i=0

i=0

=k−

k
X

i=0

k
X

(k − i)Q∗X (k − i) = k − k(1 − γ) = kγ.

i=0

Hence, we have
1
H̃(1 − γ, ) =
k

sup
X∈{0,1,...,k}
E[X]=k(1−γ)

1
1
1
1
1
H(X) = H(Q∗X ) = H(PX ) ≤
sup
H(X) = H̃(γ, ).
k
k
k
k
X∈{0,1,...,k} k
E[X]=kγ

Comparing (29) and (30) gives the desired result.

22

(30)

A PPENDIX E
P ROOF OF L EMMA 7
1
1
I˜rp (γ, ) =
sup
Irp (X; Y )
k
k
X∈{0,1,...,k}
E[X]=kγ

=

1
[Hrp (Y ) − Hrp (Y |X)]
X∈{0,1,...,k} k
sup

E[X]=kγ

=

k
X
1
[Hrp (Y ) −
PX (x)Hrp (Y |X = x)]
X∈{0,1,...,k} k
x=0

sup

E[X]=kγ
(a)

=

k
X
1
[Hrp (Y ) −
PX (x)H(Bin(k, rp ))]
X∈{0,1,...,k} k
x=0

sup

E[X]=kγ

=

1
[Hrp (Y ) − H(Bin(k, rp ))]
k
X∈{0,1,...,k}
sup

E[X]=kγ

=

1
1
Hrp (Y ) − H(Bin(k, rp ))
k
k
X∈{0,1,...,k}
sup

E[X]=kγ

1
1
1
= Ȟrp (γ, ) − H(Bin(k, rp )),
k
k
k
where (a) follows from (15).
A PPENDIX F
P ROOF OF L EMMA 8
˜ ·) is concave in its first argument. Let P ∗ and P ∗ be the optimum
We first prove that the function I(·,
X1
X3
distributions resulted from optimization problem (20) for parameters (γ1 , k1 ) and (γ3 , k1 ), respectively. Therefore
for any 0 ≤ α ≤ 1,
1
1
αI˜rp (γ1 , ) + (1 − α)I˜rp (γ3 , )
k
k
1
1
(a) 1
∗
∗
= αH(PX
∗ Bin(k, rp )) + (1 − α)H(PX
∗ Bin(k, rp )) − H(Bin(k, rp ))
1
3
k
k
k
(b) 1
1
∗
∗
∗ Bin(k, rp )) + (1 − α)(PX
∗ Bin(k, rp ))) − H(Bin(k, rp ))
≤ H(α(PX
1
3
k
k
1
1
sup
H(PX ∗ Bin(k, rp )) − H(Bin(k, rp ))
≤
k
k
X∈{0,1,...,k}
E[X]=k(αγ1 +(1−α)γ3 )

1
= I˜rp (αγ1 + (1 − α)γ3 , ),
k
where (a) follows from Lemma 7 and (b) follows from the concavity of the entropy function.

23

˜ there is no straightforward analytic
Because of the complexity and lack of symmetry or structure in the function I,
method for proving its concavity. But we notice that it is suffices to show that for all 2 ≤ k ≤ τmax − 1, and α
such that
α

1
1
1
+ (1 − α)
= ,
k−1
k+1
k

(31)

we have
αI˜rp (γ1 ,
From (31) we have α =

1
1
1
) + (1 − α)I˜rp (γ3 ,
) ≤ I˜rp (αγ1 + (1 − α)γ3 , ).
k−1
k+1
k

k−1
, hence using Lemma 7, (32) reduces to
2k
1
1
1
) − Ȟrp (γ3 ,
) + f (k, rp ) ≥ 0,
2Ȟrp (γ2 , ) − Ȟrp (γ1 ,
k
k−1
k+1

(32)

(33)

where f (k, rp ) = H(Bin(k − 1, rp )) + H(Bin(k + 1, rp )) − 2H(Bin(k, rp )). Noting that the left-hand side is a
Lipschitz continuous function of γ1 , γ3 (away from zero), and rp and the fact that k takes finitely many values,
the validation of inequality (33) can be done numerically.
R EFERENCES
[1] A. Ghassami, X. Gong, and N. Kiyavash, “Capacity limit of queueing timing channel in shared FCFS schedulers,” in 2015 IEEE
International Symposium on Information Theory (ISIT), pp. 789–793, IEEE, 2015.
[2] V. Gligor, “Covert channel analysis of trusted systems. a guide to understanding,” tech. rep., DTIC, 1993.
[3] S. Kadloor, X. Gong, N. Kiyavash, T. Tezcan, and N. Borisov, “Low-cost side channel remote traffic analysis attack in packet networks,”
in Communications, 2010 IEEE International Conference on, IEEE, 2010.
[4] D. Wakabayashi, “Breach complicates Sony’s network ambitions,” The Wall Street Journal, April 28, 2011.
[5] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, “Openflow: enabling innovation
in campus networks,” ACM SIGCOMM Computer Communication Review, vol. 38, no. 2, pp. 69–74, 2008.
[6] M. Liberatore and B. N. Levine, “Inferring the source of encrypted http connections,” in Proceedings of the 13th ACM conference on
Computer and communications security, pp. 255–263, ACM, 2006.
[7] D. X. Song, D. Wagner, and X. Tian, “Timing analysis of keystrokes and timing attacks on SSH.,” in USENIX Security Symposium,
vol. 2001, 2001.
[8] C. V. Wright, L. Ballard, S. E. Coull, F. Monrose, and G. M. Masson, “Uncovering spoken phrases in encrypted voice over ip conversations,”
ACM Transactions on Information and System Security (TISSEC), vol. 13, no. 4, p. 35, 2010.
[9] X. Gong, N. Borisov, N. Kiyavash, and N. Schear, “Website detection using remote traffic analysis,” in International Symposium on Privacy
Enhancing Technologies Symposium, pp. 58–78, Springer, 2012.
[10] X. Gong, N. Kiyavash, and P. Venkitasubramaniam, “Information theoretic analysis of side channel information leakage in FCFS schedulers,”
in Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on, pp. 1255–1259, IEEE, 2011.
[11] S. Kadloor, N. Kiyavash, and P. Venkitasubramaniam, “Mitigating timing based information leakage in shared schedulers,” in INFOCOM,
2012 Proceedings IEEE, pp. 1044–1052, IEEE, 2012.
[12] X. Gong and N. Kiyavash, “Quantifying the information leakage in timing side channels in deterministic work-conserving schedulers,”
arXiv preprint arXiv:1403.1276, 2014.
[13] V. Anantharam and S. Verdu, “Bits through queues,” IEEE Transactions on Information Theory, vol. 42, no. 1, pp. 4–18, 1996.
[14] S. Cabuk, C. E. Brodley, and C. Shields, “Ip covert timing channels: design and detection,” in Proceedings of the 11th ACM Conference
on Computer and Communications Security, pp. 178–187, ACM, 2004.
[15] S. J. Murdoch and S. Lewis, “Embedding covert channels into TCP/IP,” in International Workshop on Information Hiding, 2005.

24

[16] D. Llamas, A. Miller, and C. Allison, “An evaluation framework for the analysis of covert channels in the TCP/IP protocol suite.,” in
ECIW, pp. 205–214, 2005.
[17] M. H. Kang, I. S. Moskowitz, and D. C. Lee, “A network pump,” IEEE Transactions on Software Engineering, vol. 22, no. 5, pp. 329–338,
1996.
[18] S. K. Gorantla, S. Kadloor, N. Kiyavash, T. P. Coleman, I. S. Moskowitz, and M. H. Kang, “Characterizing the efficacy of the nrl network
pump in mitigating covert timing channels,” IEEE Transactions on Information Forensics and Security, vol. 7, no. 1, pp. 64–75, 2012.
[19] R. Soltani, D. Goeckel, D. Towsley, and A. Houmansadr, “Covert communications on poisson packet channels,” in Communication, Control,
and Computing (Allerton), 2015 53rd Annual Allerton Conference on, pp. 1046–1052, IEEE, 2015.
[20] R. Soltani, D. Goeckel, D. Towsley, and A. Houmansadr, “Covert communications on renewal packet channels,” in Communication, Control,
and Computing (Allerton), 2016 54th Annual Allerton Conference on, pp. 548–555, IEEE, 2016.
[21] P. Mukherjee and S. Ulukus, “Covert bits through queues,” in Communications and Network Security (CNS), 2016 IEEE Conference on,
pp. 626–630, IEEE, 2016.
[22] V. Berk, A. Giani, G. Cybenko, and N. Hanover, “Detection of covert channel encoding in network packet delays,” Rapport Technique
TR536, de lUniversité de Dartmouth, p. 19, 2005.
[23] S. Gianvecchio and H. Wang, “Detecting covert timing channels: an entropy-based approach,” in Proceedings of the 14th ACM conference
on Computer and communications security, pp. 307–316, ACM, 2007.
[24] R. Tahir, M. T. Khan, X. Gong, A. Ahmed, A. Ghassami, H. Kazmi, M. Caesar, F. Zaffar, and N. Kiyavash, “Sneak-peek: High speed
covert channels in data center networks,” in IEEE International Conference on Computer Communications (INFOCOM), IEEE, 2016.
[25] A. Ghassami, A. Yekkehkhany, N. Kiyavash, and Y. Lu, “A covert queueing channel in round robin schedulers,” arXiv preprint
arXiv:1701.08883, 2017.
[26] T. M. Cover and J. A. Thomas, Elements of Information Theory. John Wiley & Sons, 2012.
[27] I. Csiszar and J. Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems. Cambridge University Press, 2011.
[28] Y. Polyanskiy and Y. Wu, “Lecture notes on information theory, MIT (6.441), UIUC (ECE 563),” 2014.

25

