Detection of Distributed Denial of Service Attacks in Autonomous System Domains

• US 20080028467A1
• Filed: 01/17/2007
• Published: 01/31/2008
• Est. Priority Date: 01/17/2006
• Status: Active Grant

• Current Assignee: University of Maryland
• Original Assignee: University of Maryland
• Inventors: Kommareddy, Chris, La, Richard, Shayman, Mark, Bhattacharjee, Samrat
• Granted Patent: US 8,397,284 B2
• Time in Patent Office: Days
• US Class Current: 726/23
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection
• CPC Class Codes: H04L 63/1458 Denial of Service

Abstract

A denial-of-service network attack detection system is deployable in single-homed and multi-homed stub networks. The detection system maintains state information of flows entering and leaving the stub domain to determine if exiting traffic exceeds traffic entering the system. Monitors perform simple processing tasks on sampled packets at individual routers in the network at line speed and perform more intensive processing at the routers periodically. The monitors at the routers form an overlay network and communicate pertinent traffic state information between nodes. The state information is collected and analyzed to determine the presence of an attack.

Claims

1. A method for detecting malicious communication traffic at an autonomous system domain comprising:

aggregating a plurality of flows traversing at least one routing node in the autonomous system domain into a plurality of flow aggregates, each of said flows including incoming packets having a common source address and outgoing packets having a common destination address, each of said flow aggregates having mapped thereto a set of said flows;

sampling packets of each of said flow aggregates during a predetermined time interval;

storing at least a flow identifier of suspect flows in each of said flow aggregates, said suspect flows corresponding to a flow aggregate having a number of said outgoing packets sampled therefrom exceeding by a predetermined value a number of said incoming packets sampled therefrom; and

determining from said suspicious flows a flow identifier of an attack flow.

2. The method for detecting malicious communication traffic as recited in claim 20, where said aggregating step includes applying a hash function to said flow identifier of said set of flows to form said flow aggregates and said reaggregating step includes applying another hash function in said subsequent predetermined time intervals to said flow identifiers to form said other flow aggregates.

3. The method for detecting malicious communication traffic as recited in claim 2 further including:

mapping each of said flow aggregates to a respective one of a plurality of bins through said hash function;

updating a count maintained in said respective one of said bins during said predetermined time interval responsive to each said incoming packet sampled from a corresponding one of said flow aggregates mapped thereto and responsive to each said outgoing packet sampled from said corresponding one of said flow aggregates mapped thereto;

mapping each of said other flow aggregates to a respective one of said plurality of bins through said other hash function during said subsequent predetermined time intervals;

clearing said count maintained in said plurality of bins subsequent to an end of said predetermined time interval and subsequent to said end of said subsequent predetermined time intervals; and

updating said count maintained in said respective one of said bins during said subsequent predetermined time intervals responsive to each said incoming packet sampled from said corresponding one of said other flow aggregates mapped thereto and responsive to each said outgoing packet sampled from said corresponding one of said other flow aggregates mapped thereto.

4. The method for detecting malicious communication traffic as recited in claim 3 further including providing each said bin with an in counter for counting said incoming packets and an out counter for counting said outgoing packets, said count updating steps including the step of incrementing said in counter for each said incoming packet and incrementing said out counter for each outgoing counter.

5. The method for detecting malicious communication traffic as recited in claim 4 further including:

determining a ratio of said out counter to said in counter for each of said flow aggregates and said other flow aggregates;

comparing said ratio to a threshold based on said predetermined number of outgoing packets exceeding said number of incoming packets; and

identifying a flow aggregate of said flow aggregates or said other flow aggregates as containing said suspect flows responsive to said ratio exceeding said threshold.

6. The method for determining malicious communication traffic as recited in claim 4 further including:

determining a ratio of said out counter to said in counter for each of said flow aggregates and said other flow aggregates;

comparing said ratio to an overflow threshold and an underflow threshold each based on said predetermined number of outgoing packets exceeding said number of incoming packets; and

identifying a flow aggregate of said flow aggregates and said other flow aggregates as containing said suspect flows responsive to said ratio being either greater than said overflow threshold or less than said underflow threshold.

7. The method for determining malicious communication traffic as recited in claim 6, where said comparing step is executed responsive to a packet being sampled from said flow aggregates or said other flow aggregates.

8. The method for determining malicious communication traffic as recited in claim 20 further including:

incrementing a score for each of said suspect flows that matches a corresponding one of said other suspect flows;

determining if said score exceeds a score threshold and upon a positive determination thereof, forwarding said flow identifier of said suspect flows to a rendezvous monitor; and

identifying said attack flow as one of said suspect flows received at said rendezvous monitor and identified as such by a predetermined number of said monitors along a path corresponding to said flow identifier of said one of said suspect flows.

20. The method for determining malicious communication traffic as recited in claim 1 further including the steps of:

reaggregating said flows into another plurality of flow aggregates in subsequent predetermined time intervals such that each of said other flow aggregates contains other than said flows of a previous one of said predetermined time intervals;

sampling packets of said other flow aggregates during each of said subsequent predetermined time intervals;

storing at least said flow identifier of other suspect flows in each of said other flow aggregates during said subsequent predetermined time intervals, said other suspect flows having said number of said outgoing packets sampled therefrom exceeding by said predetermined value said number of said incoming packets sampled therefrom; and

determining from at least said flow identifier of said suspicious flows and said flow identifier of said other suspicious flows a flow identifier of an attack flow.

21. The method for determining malicious communication traffic as recited in claim 1, where said attack flow determining step includes identifying said attack flow as one of said suspect flows received at said rendezvous monitor and identified as such by a predetermined number of said monitors along a path corresponding to said flow identifier of said one of said suspect flows.

22. The method for determining malicious communication traffic as recited in claim 20, where said attack flow determining step includes:

computing an average packet rate of flows traversing said routing nodes in a path of said suspect flow;

determining if said average packet rate is greater than a predetermined value and upon a positive determination thereof incrementing by said average packet rate a score at said rendezvous monitor responsive to each of said suspect flows in said subsequent predetermined time intervals;

decrementing said score by a predetermined value upon a negative determination of said average packet rate being greater than said predetermined value; and

removing from said suspect flows any thereof having a zero value of said score a predetermined number of said subsequent predetermined time intervals.

23. The method for detecting malicious flows as recited in claim 20, where said attack flow determining step includes:

incrementing during said predetermined time interval a vote count at a rendezvous monitor responsive to said outgoing packets belonging to said suspect flows;

incrementing during said subsequent predetermined time intervals said vote count at said rendezvous monitor responsive to said outgoing packets belonging to said other suspect flows; and

identifying after a predetermined number of said subsequent predetermined time intervals said attack flow as one of said suspect flows corresponding to said vote count exceeding a predetermined score threshold.

9. A method for detecting malicious communication traffic at an autonomous network domain comprising:

sampling packets of a plurality of flows at each of a plurality of routing nodes in the autonomous network domain, each of said flows including incoming packets having a common source address and outgoing packets having a common destination address;

counting at each of said routing nodes said sampled packets into at least one counter mapped to said plurality of flows;

determining at each of said routing nodes a residual count of said outgoing packets exceeding said incoming packets;

transmitting said count from said each of said routing nodes to at least one rendezvous node; and

determining at said rendezvous node at least one flow identifier of an attack flow.

10. The method for detecting malicious communication traffic as recited in claim 9 further including decrementing said counter upon receiving an incoming packet and incrementing said counter when receiving an outgoing packet.

11. The method for detecting malicious communication traffic as recited in claim 10 further decrementing said counter by a value greater than a value used for incrementing said counter.

12. The method for detecting malicious communication traffic as recited in claim 11, where said decrementing value is a maximum allowable outgoing-to-incoming packet ratio.

13. The method for detecting malicious communication traffic as recited in claim 12, where said decrementing is performed responsive to said incoming packet only when all values in a memory table of such counters are at least equal to said decrementing value.

14. The method for detecting malicious communication traffic as recited in claim 9 where said counting step includes:

providing a first plurality of counters each addressable in accordance with a first mapping;

providing a second plurality of counters each addressable in accordance with a second mapping;

incrementing by a first value at least one of said first counters responsive to said sampling one of said outgoing packets;

decrementing by a second value greater than said first value said first counters responsive to said sampling one of said incoming packets and all of said first counters being at least said second value; and

neither incrementing nor decrementing said first counters responsive to said sampling one of said incoming packets if less than all of said first counters are at least said second value.

24. The method for detecting malicious communication traffic as recited in claim 14, where said providing said first plurality of counters includes respectively mapping an internet protocol address to said first counters as said first mapping and said providing said second plurality of counters includes respectively mapping by a hashing function of said internet protocol address to said second counters as said second mapping.

25. The method for detecting malicious communication traffic as recited in claim 24, where said internet protocol address mapping includes mapping segments of said internet protocol address to a set of said first counters such that more than one of said segments is mapped to one of said first counters of said set.

26. The method for detecting malicious communication traffic as recited in claim 9 including:

providing in memory at each of said routing nodes an IP-mapped symmetric flow table of counters and an IP-mapped asymmetric flow table of counters, each counter of said IP-mapped symmetric flow table and said IP-mapped asymmetric flow table mapped to at least a portion of a corresponding internet protocol address;

providing in said memory at each of said routing nodes a hashed-mapped symmetric flow table of counters and a hashed-mapped asymmetric flow table of counters, each counter of said hash-mapped symmetric flow table and said hash-mapped asymmetric flow table mapped by a hashing function of said internet protocol address;

updating said counters in said IP-mapped symmetric flow table, said hash-mapped symmetric flow table, said IP-mapped asymmetric flow table and said hash-mapped asymmetric flow table responsive to said sampled packets in said counting step;

aggregating at each of said routing nodes said IP-mapped symmetric flow table and said hash-mapped symmetric flow table of others of said routing nodes;

adding at each of said routing nodes said counters of said aggregated IP-mapped symmetric flow table to corresponding said counters in said IP-mapped asymmetric flow table and said counters of said aggregated hash-mapped symmetric flow value to said hash-mapped asymmetric flow table;

aggregating at said rendezvous node said IP-mapped asymmetric flow table and said hash-mapped asymmetric flow table from said routing nodes; and

determining from said aggregated IP-mapped asymmetric flow table and said aggregated hash-mapped asymmetric flow table at said rendezvous node said attack flow.

27. The method for detecting malicious communication traffic as recited in claim 26, where said counter updating includes:

incrementing by a first value at least one of said counters in said IP-mapped symmetrical flow table and at least one of said counters in said hash-mapped symmetric flow table responsive to said sampling one of said outgoing packets;

decrementing by a second value greater than said first value said counters in said IP-mapped symmetrical flow table and said counters in said hash-mapped symmetric flow table responsive to said sampling one of said incoming packets and all of said counters in said IP-mapped symmetrical flow table and all of said counters in said hash-mapped symmetric flow table being at least said second value;

decrementing by said second value said one of said counters in said IP-mapped asymmetrical flow table and said one of said counters in said hash-mapped asymmetric flow table responsive to;

said sampling one of said incoming packets;

less than all of said counters in said IP-mapped symmetrical flow table or less than all of said counters in said hash-mapped symmetric flow table being at least said second value; and

all of said counters in said IP-mapped asymmetrical flow table and all of said counters in said one of said counters in said hash-mapped asymmetric flow table being at least said second value; and

neither incrementing nor decrementing said counters in said IP-mapped symmetrical flow table and said counters in said hash-mapped symmetric flow table responsive to said sampling one of said incoming packets if less than all of said counters in said IP-mapped symmetrical flow table and less than all of said counters in said hash-mapped symmetric flow table are at least said second value.

15. A system for detecting malicious communication traffic at an autonomous system domain having a plurality of routers addressable through at least one border gateway, the system comprising:

a plurality of monitors respectively coupled to at least a number of the routers, and each of said monitors receiving a plurality of flows from a respective port thereof, each of said flows including incoming packets having a common source address and outgoing packets having a common destination address, each of said monitors including;

a per-packet processor forming aggregates of said flows in accordance with a mapping of respective flow identifiers thereof and sampling packets thereof in accordance with a predetermined sampling rate, said per-packet processor including;

at least one counter for each of said aggregates and maintaining a count therein responsive to a number of said outgoing packets and a number of said incoming packets; and

a record store storing a flow record for each suspect flow in each said aggregate having said number of said outgoing packets exceeding by a predetermined value a number of said incoming packets, each said flow record having stored therein at least a flow identifier of said suspect flow corresponding thereto; and

a periodic processor receiving said flow record for each said suspect flow at predetermined intervals, said periodic processor computing a score for each said suspect flow and comparing said score with a predetermined threshold, said periodic processor providing said flow identifier of each said suspect flows having said score exceeding said predetermined threshold, wherein a time between said periodic intervals is greater than said sampling rate.

16. The system as recited in claim 15 further including an overlay network interconnecting said monitors and providing a communication path therebetween.

17. The system as recited in claim 15, wherein said monitors are coupled to said respective one of the routers through a mirrored port thereof.

18. The system as recited in claim 15, wherein said sampling rate of each of said monitors is independent of said sampling rate of another of said monitors.

19. The system as recited in claim 15, where said periodic processor maintains said flow record for symmetric flows and asymmetric flows.