HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Covert Cycle Stealing in a Single FIFO Server

Bo Jiang 1 Philippe Nain 2 Don Towsley 3
2 DANTE - Dynamic Networks : Temporal and Structural Capture Approach
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme, IXXI - Institut Rhône-Alpin des systèmes complexes
Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Contributor : Philippe Nain Connect in order to contact the contributor
Submitted on : Tuesday, May 4, 2021 - 12:47:47 PM
Last modification on : Tuesday, May 17, 2022 - 2:34:26 PM
Long-term archiving on: : Thursday, August 5, 2021 - 7:34:19 PM


Files produced by the author(s)



Bo Jiang, Philippe Nain, Don Towsley. Covert Cycle Stealing in a Single FIFO Server. ACM Transactions on Modeling and Performance Evaluation of Computing Systems, ACM, 2021, 6 (2), pp.1-33. ⟨10.1145/3462774⟩. ⟨hal-03216762⟩



Record views


Files downloads