Bayes, not Naïve: Security Bounds on Website Fingerprinting Defenses
This provides a method for formal security bounds in privacy attacks, potentially impacting ML-based security research, though it is incremental in applying existing ML concepts to a specific domain.
The paper tackles the problem of evaluating security guarantees for Website Fingerprinting defenses by reducing attacks to a classification task to determine the smallest achievable error (Bayes error), which can be estimated in practice as a lower bound for adversaries. This allows black-box security assessment and shifts focus to identifying optimal feature sets.
Website Fingerprinting (WF) attacks raise major concerns about users' privacy. They employ Machine Learning (ML) to allow a local passive adversary to uncover the Web browsing behavior of a user, even if she browses through an encrypted tunnel (e.g. Tor, VPN). Numerous defenses have been proposed in the past; however, it is typically difficult to have formal guarantees on their security, which is most often evaluated empirically against state-of-the-art attacks. In this paper, we present a practical method to derive security bounds for any WF defense, which depend on a chosen feature set. This result derives from reducing WF attacks to an ML classification task, where we can determine the smallest achievable error (the Bayes error); such error can be estimated in practice, and is a lower bound for a WF adversary, for any classification algorithm he may use. Our work has two main consequences: i) it allows determining the security of WF defenses, in a black-box manner, with respect to the state-of-the-art feature set and ii) it favors shifting the focus of future WF research to the identification of optimal feature sets. The generality of the approach further suggests that the method could be used to define security bounds for other ML-based attacks.