Analyzing Network Topology for DDoS Mitigation Using the Abelian Sandpile Model

Bhavana Panchumarthi, Reed College
Monroe Ame Stephenson, Reed College


A Distributed Denial of Service (DDoS) is a cyber attack, which is capable of triggering a cascading failure in the victim network. While DDoS attacks come in different forms, their general goal is to make a network's service unavailable to its users. A common, but risky, countermeasure is to blackhole or null route the source, or the attacked destination. When a server becomes a blackhole, or referred to as the sink in the paper, the data that is assigned to it "disappears" or gets deleted. Our research shows how mathematical modeling can propose an alternative blackholing strategy that could improve the efficiency of this countermeasure. We want to optimize efficiency in terms of obtaining the least possible data loss, which may include both legitimate and malicious traffic.The mathematical model previously mentioned is the Abelian Sandpile Model (ASM). Using the notion of self-organized criticality (SOC), the ASM can be extended to optimize the efficiency of using a blackholing strategy to drive the network to a stable state. To investigate the optimization of blackholing, we propose a chip-firing game that aims to determine the best server to blackhole, or enable as the sink, for each server acting as a potential source. Additionally, our research on this chip-firing game suggests a feasible server to enable as the sink for situations where mitigation takes priority over identifying the source. The undirected graphs of Internet backbone networks act as a playing field for the proposed chip-firing game. Our model, built in Sage, outputs matrices representing values of data preserved for each combination of source and sink. In addition to ranking servers by their susceptibility as a source and efficiency as a sink, analyzing such matrices serves a greater incentive that can allow us to learn hidden characteristics of the graph. For example, we found consequences of prolonged attacks that indicate there exists a certain limit point to an attack. Additionally, graphs that share similar structures end up having shared total values when the sink and the source match. Finally, when two networks of the same size take the structure of a tree graph, the vulnerability of the total networks are identical. Our research approaches a common network security issue, and abstracts the ideas in order to discover non-trivial properties of the networks at risk.