Computer Science Thesis Proposal
— 3:30pm
Location:
In Person and Virtual - ET
-
Traffic21 Classroom, Gates Hillman 6501 and Zoom
Speaker:
NIRAV ATRE
,
Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://www.cs.cmu.edu/~natre/
Securing Middleboxes Against Temporal Algorithmic Complexity Attacks
Denial-of-Service (DoS) attacks are the bane of public-facing network deployments. Temporal algorithmic complexity attacks (t-ACAs) are a class of DoS attacks where an attacker uses a small amount of adversarial traffic to induce a large amount of work in the target system, pushing the system into overload and causing it to drop packets from innocent users. t-ACAs are particularly dangerous because, unlike volumetric DoS attacks, they don’t require a significant network bandwidth investment from the attacker. Today, middleboxes on the Internet must be designed and engineered on a case-by-case basis to mitigate the debilitating impact of t-ACAs; worse, the resulting designs tend to be overly conservative in their attack mitigation strategy, either throttling the middlebox’s common-case performance, limiting the innocent traffic that it can serve, or both.
In this work, we propose the first general, systematic approach to make middleboxes resilient to t-ACAs. We design a framework, called SurgeProtector, that uses packet scheduling to mitigate the impact of t-ACAs using a well-known scheduling algorithm: Weighted Shortest Job First (WSJF). To evaluate SurgeProtector, we propose a new metric of vulnerability called the Displacement Factor (DF), which quantifies the “harm per unit effort” that an adversary can induce. We provide novel, adversarial analysis of WSJF and show that any system using this policy has a worst-case DF of only a small constant, where traditional schedulers place no upper bound on the DF. Applying job size-based scheduling in an adversarial context also requires us to harden against attacks: (1) the scheduler’s priority queue, and (2) heuristics used for job size estimation. To that end, we present a novel, adversary-proof hardware priority queue architecture, BBQ, that achieves 3X the packet processing rate of state-of-the-art hardware priority queue designs.
Finally, we propose Cassandra, a tool to automatically generate adversary-resistant heuristics for arbitrary middleboxes. Illustrating that our framework is not only theoretically, but practically robust, we integrate SurgeProtector (with BBQ) into an open source intrusion detection system (IDS). Under simulated attack, the SurgeProtector-augmented IDS suffers 90-99% lower innocent traffic loss than the original system.
Thesis Committee:
Justine Sherry (Chair)
Vyas Sekar
Weina Wang
Brighten Godfrey (University of Illinois at Urbana-Champaign)
Additional Information
In Person and Zoom Participation. See announcement.