Extracting Signatures and Filters for Zero-day Sophisticated DNS and other DDoS Attacks

Distributed Denial of Service (DDoS) attacks keep being the number one worry of many infrastructure providers as well as of different enterprises.   Usually not only the targeted victim suffers, but there is collateral damage and the neighboring servers and customers suffer from these attacks.  In the past three years the first two PIs with their students have developed algorithms for zero-day signature extraction for html based DDoS attacks, and the goal of this proposal is to extend this work in several directions. The proposal will entail the development of new algorithms for the analysis of high throughput streaming data (aka big data) to detect heavy hitters with high distinct counts that were not such at peace time (i.e., are very likely malicious and not legitimate). 

Recently the attackers have developed code (zombie agents) that go under the radar screen of existing defenses, thus evading the mitigation.  In the past ten years, these new attack methods included huge (~1 million) zombie armies of agents, each making seemingly legitimate, non-spoofed html (or other such as smtp and DNS) requests.  Each of the agents makes the requests at a very low rate (say one every two minutes), however combined from all the zombie agents together it is a large volumetric attack that knocks down the victim servers.  To overcome these attacks the first two PIs with their students (Shir Landau-Feibish, and others) have developed a tool that extracts a signature (string of characters) for these attacks within a minute or two from the attack detection.  These signatures are then applied at the mitigation device and stop the attack.  The premise is that most if not all the agents in the zombie army use the same code, and the code leaves some characteristic finger print on which the mitigation can be based.  This has proven to be correct in the mitigation and study of several attacks on actual customers of a local vendor.  This vendor has recently successfully used our tool to generate signatures with which it has mitigated the attacks. 

That previous work has resulted in the development of new heavy hitters algorithms tuned to the efficient extraction of varying length signatures.   However, in the last two years new DDoS attacks have appeared, specifically DNS reflection attacks and DNS amplification attacks.  These attacks require the adaptation and extension of our basic tool to deal with these new attacks.  Moreover, some of the new DNS attacks and others, use randomization to fool signature extraction based techniques.  Basically, by issuing millions of DNS requests, each with a slightly different variant using a short randomized string.  From discussions we had with ISPs and local network operators, these attacks are causing major problems, even though often the providers or their clients are not the end target of the attack, but a secondary unintentional victim. 

Motivated by a particular randomized DNS attack we will develop new and efficient distinct heavy hitters algorithms and build a system to identify these attacks using the new techniques.  Heavy hitter detection in streams is a fundamental problem with many applications, which include detecting certain DDoS attacks and anomalies. A (classic) heavy hitter (HH) in a stream of elements is a key which appears in many elements.  When stream elements consist of {key, subkey} pairs, a distinct heavy hitter is a key that is paired with a large number of different subkeys and a combined heavy hitter is a key with a large combination of distinct and classic weights.  Classic heavy hitters detection algorithms date back to a seminal work of Misra and Gries (1982) which achieves an optimal tradeoff of structure size to detection quality.  We will develop new algorithms for distinct and combined HH detection which will improve on previous designs in both the asymptotic (theoretical) sense and practicality and nearly match the performance tradeoffs of the best algorithms for classic HH detection.  Our approach will be based on a novel combination of Sample and Hold weighted sampling and state of the art approximate distinct counters.  Finally, we will design a system for detecting randomized attacks on the Domain Name System (DNS) service, which will be based on our distinct and combined HH detection algorithms, and demonstrate its effectiveness through an experimental evaluation on both real and synthetic attacks.