  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 sends messages to another user via his
pattern of access to the shared resource, which serves the users according to a
first come first served (FCFS) policy. 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.
