Bankrupting DoS Attackers Despite Uncertainty
On-demand provisioning in the cloud allows for services to remain available despite massive denial-of-service (DoS) attacks. Unfortunately, on-demand provisioning is expensive and must be weighed against the costs incurred by an adversary. This leads to a recent threat known as economic denial-of-sustainability (EDoS), where the cost for defending a service is higher than that of attacking. A natural approach for combating EDoS is to impose costs via resource burning (RB). Here, a client must verifiably consume resources – for example, by solving a computational challenge – before service is rendered. However, prior approaches with security guarantees do not account for the cost on-demand provisioning. Another valuable defensive tool is to use a classifier in order to discern good jobs from a legitimate client, versus bad jobs from the adversary. However, while useful, uncertainty arises from classification error, which still allows bad jobs to consume server resources. Thus, classification is not a solution by itself. Here, we propose an EDoS defense, RootDef, that leverages both RB and classification, while accounting for both the costs of resource burning and on-demand provisioning. Specifically, against an adversary that expends B resources to attack, the total cost for defending is Õ( √(B g) + B^2/3 + g), where g is the number of good jobs and Õ refers to hidden logarithmic factors in the total number of jobs n. Notably, for large B relative to g, the adversary has higher cost, implying that the algorithm has an economic advantage. Finally, we prove a lower bound showing that RootDef has total costs that are asymptotically tight up to logarithmic factors in n.
READ FULL TEXT