We examine the side-channel information leakage in first-come-first-serve (FCFS) packet schedulers. In this setup, an attacker aims to learn the packet arrival pattern of a private user that shares a FCFS packet scheduler with him, using the queuing delay information of his own packets. Under an information-theoretic metric for information leakage, we identify the optimal non-adaptive strategy for a given average probe rate of the attacker and report upto 1000% increase in information leakage compared to the attack strategy analyzed in the literature with the same average probe rate. The search for optimal strategies is reduced to linear programming, implying that the discovery of such strategies is in the domain of a real-world attacker.
