Patent Description:
Communication networks may be subject to various kinds of attacks from malicious entities.

<NPL> relates to the design and implementation of a new approach for anomaly detection and classification over high speed networks. The proposed approach is based on a data reduction phase through flow sampling by focusing mainly on short lived flows. The second step is a random aggregation of some descriptors such as a number of SYN packets per flow in two different data structures called Count Min Sketch and Multi-Layer Reversible Sketch.

<NPL> relates to leveraging data streaming techniques such as the reversible sketch, to design High-speed Flow-level Intrusion Detection system (HiFIND). HiFIND is scalable to flow-level detection on high-speed networks, DoS resilient, can distinguish SYN flooding and various port scans for effective mitigation, enables aggregate detection over multiple routers and separates anomalies to limit false positives in detection.

Various example embodiments relate generally to providing security for communication networks.

In at least some example embodiments, a method is provided. The method includes receiving, from each edge device in a set of edge devices of a communication network, a respective set of network traffic information including a first traffic record indicative of respective measures of request packets exiting the communication network via the respective edge device for respective data flows and a second traffic record indicative of respective measures of response packets entering the communication network via the respective edge device for respective data flows, wherein, for at least one of the edge devices, the first traffic record comprises a first reversible sketch and the second traffic record comprises a second reversible sketch. The method includes determining, based on the sets of network traffic information of the edge devices, whether a traffic anomaly indicative of an attack on the communication network is detected. In at least some embodiments determining whether a traffic anomaly indicative of an attack on the communication network is detected includes aggregating the first traffic records of the edge devices and the second traffic records of the edge devices to form thereby an aggregated traffic record and determining, based on the aggregated traffic record, whether a traffic anomaly indicative of an attack on the communication network is detected. In at least some embodiments, aggregating the first traffic records of the edge devices and the second traffic records of the edge devices to form the aggregated traffic record includes applying a first set of weights to values of the first traffic records of the edge devices to provide respective weighted first traffic records, applying a second set of weights to values of the second traffic records of the edge devices to provide respective weighted second traffic records, and aggregating the weighted first traffic records of the edge devices and the weighted second traffic records of the edge devices to form thereby the aggregated traffic record.

In at least some example embodiments, an apparatus is provided. The apparatus includes means for receiving, from each edge device in a set of edge devices of a communication network, a respective set of network traffic information including a first traffic record indicative of respective measures of request packets exiting the communication network via the respective edge device for respective data flows and a second traffic record indicative of respective measures of response packets entering the communication network via the respective edge device for respective data flows, wherein, for at least one of the edge devices, the first traffic record comprises a first reversible sketch and the second traffic record comprises a second reversible sketch. The apparatus includes means for determining, based on the sets of network traffic information of the edge devices, whether a traffic anomaly indicative of an attack on the communication network is detected. In at least some embodiments, the means for determining whether a traffic anomaly indicative of an attack on the communication network is detected includes means for aggregating the first traffic records of the edge devices and the second traffic records of the edge devices to form thereby an aggregated traffic record and means for determining, based on the aggregated traffic record, whether a traffic anomaly indicative of an attack on the communication network is detected. In at least some embodiments, the means for aggregating the first traffic records of the edge devices and the second traffic records of the edge devices to form the aggregated traffic record includes means for applying a first set of weights to values of the first traffic records of the edge devices to provide respective weighted first traffic records, means for applying a second set of weights to values of the second traffic records of the edge devices to provide respective weighted second traffic records, and means for aggregating the weighted first traffic records of the edge devices and the weighted second traffic records of the edge devices to form thereby the aggregated traffic record. In at least some embodiments, the first traffic record is keyed based on destination address information and the second traffic record is keyed based on source address information. In at least some embodiments, the respective measures of request packets sent by the edge device for the respective data flows and the respective measures of response packets received by the edge device for the respective data flows include flow size information. In at least some embodiments, the means for aggregating the first traffic records of the edge devices and the second traffic records of the edge devices to form the aggregated traffic record includes means for aggregating the first traffic records of the edge devices and the second traffic records of the edge devices in a manner for cancelling the respective measures of request packets exiting the communication network via the respective edge device for respective data flows and the respective measures of response packets entering the communication network via the respective edge device for respective data flows. In at least some embodiments, the means for determining whether a traffic anomaly indicative of an attack on the communication network is detected based on the aggregated traffic record includes means for determining, for each of a plurality of keys of the aggregated traffic record, whether a value associated with the respective key satisfies a threshold. In at least some embodiments, the means for determining whether a traffic anomaly indicative of an attack on the communication network is detected based on the aggregated traffic record includes means for generating, based on the aggregated traffic record, a list of anomalous keys including keys of the aggregated traffic record for which respective values satisfy a threshold and means for determining, from the list of anomalous keys, whether any of the anomalous keys are included in the list of anomalous keys at least a threshold number of times.

Various example embodiments relate generally to providing security for communication networks. Various example embodiments relate generally to providing security for a communication network based on detection and mitigation of an attack in the communication network. Various example embodiments supporting attack detection and mitigation may be configured to support detection and mitigation of an attack in a communication network based on the one-to-one mapping relationship between request packets and response packets supported by many protocols used by attackers to initiate attacks (e.g., various protocols of the Transmission Control Protocol (TCP) / Internet Protocol IP) model, such as a Transmission Control Protocol (TCP), a User Datagram Protocol (UDP), a Domain Name System (DNS) protocol, a Network Time Protocol (NTP), a Trivial File Transfer Protocol (TFTP), or a Simple Network Management Protocol (SNMP), an Internet Control Message Protocol (ICMP), or the like). Various example embodiments supporting attack detection and mitigation may be configured to support detection and mitigation of an attack in a communication network based on distributed collection of network traffic information at network elements and analysis of aggregated network traffic information at a network controller. Various example embodiments supporting attack detection and mitigation may be configured to support detection and mitigation of an attack in a communication network based on use of network traffic data structures configured to support the collection, aggregation, and analysis of network traffic information (e.g., reversible sketches or other types of data structures configured to support collection, aggregation, and analysis of network traffic information as discussed herein). Various example embodiments supporting attack detection and mitigation, by combining one-to-one mapping detection techniques with use of configured to return identification information associated with devices exhibiting anomalous behavior, is able to support accurate and efficient detection and mitigation of attacks in communication networks. Various example embodiments supporting attack detection and mitigation may be configured to support detection and mitigation of attacks in a communication network in a protocol-independent manner (e.g., for various protocols which may be used to initiate attacks which, as indicated above, may include TCP, UDP, DNS, NTP, TFTP, SNMP, ICMP, or the like), in the presence of large-scale network traffic, in high-speed data networks, or the like, as well as various combinations thereof. Various example embodiments supporting attack detection and mitigation may be configured to support detection and mitigation of various types of attacks, such as amplification attacks or other types of attacks. It will be appreciated that these and various other embodiments and advantages and potential advantages of attack detection and mitigation may be further understood by way of reference to the example communication system of <FIG>.

<FIG> depicts an example communication system configured to support detection and mitigation of an attack in a communication network.

The communication system <NUM> includes a communication network <NUM>, a set of reflectors <NUM>-<NUM> - <NUM>-R (collectively, reflectors <NUM>), an attacker <NUM>, and a botnet <NUM>.

The communication network <NUM> includes a set of communication devices <NUM>-<NUM> - <NUM>-C (collectively, communication devices <NUM>), a set of edge routers <NUM>-<NUM> - <NUM>-E (collectively, edge routers <NUM>), and a central controller <NUM>). It will be appreciated that the communication network <NUM> also may include various other elements (e.g., devices, subnets, or the like).

The communication devices <NUM> may include any communication devices which may be located with the communication network <NUM>. The device types of the communication devices <NUM> may depend on the network type of the communication network <NUM>.

The edge routers <NUM> may be configured to support communications of the communication network <NUM>, operating as ingress points into the communication network <NUM> and as egress points out of the communication network <NUM>. The edge routers <NUM> may be configured to support communications by elements within the communication network <NUM> with elements outside of the communication network <NUM>, by elements outside of the communication network <NUM> with elements within the communication network <NUM>, or the like, as well as various combinations thereof.

The central controller <NUM> is configured to provide various control functions for the communication network <NUM>. The central controller <NUM> may be configured to support control functions for controlling edge routers <NUM> (e.g., configuration of edge routers (e.g., installing and removing routes, installing and removing traffic control rules (e.g., traffic filtering rules, traffic blocking rules, or the like), or the like)).

The reflectors <NUM> are servers that may be configured to provide various functions based on use of request/response transactions. For example, the reflectors <NUM> may include DNS servers, NTP servers, TFTP servers, servers providing TCP-based service, or the like.

It will be appreciated that, although primarily presented with respect to a specific configuration of communication network <NUM> (e.g., specific types, numbers, and arrangements of elements of communication network <NUM>), the communication network <NUM> may be configured in various other ways (e.g., including various other types, numbers, or arrangements of the elements).

The communication network <NUM> supports typical communications of the communication devices <NUM>. The communication devices <NUM> may send request packets to the reflectors <NUM> and receive associated response packets from the reflectors <NUM>. It is noted that examples of such legitimate request and response packets are depicted in <FIG> for one of the communication devices <NUM> (illustratively, communication device <NUM>-<NUM> sends a request packet to reflector <NUM>-<NUM> via edge router <NUM>-<NUM> and receives an associate response packet from reflector <NUM>-<NUM> via edge router <NUM>-<NUM>). It will be appreciated that any of the communication devices <NUM> may send any suitable numbers and types request packets to any reflectors <NUM> (or other devices or servers) and similarly, may receive the respective response packets from the reflectors <NUM> (or other devices or servers). These request and response packets may be based on various protocols of the TCP/IP model that support a request-response relationship (e.g., TCP, UDP, DNS, NTP, TFTP, SNMP, ICMP, or the like). It is noted that examples of specific request-response packets which may be used by communication devices <NUM> and reflectors <NUM> for legitimate purposes are presented below in Table <NUM>. These request and response packets traverse the edge routers <NUM>.

The communication network <NUM>, however, may be subject to various types of attacks. For example, distributed Denial of Service (DDoS) flooding attacks are very prevalent over the Internet. DDoS flooding attacks aim to prevent normal users from accessing specific network resources. DDoS flooding attacks can be generated in two ways: direct flooding attacks and indirect flooding attacks. In direct DDoS flooding attacks, such as network/transport layer DDoS flooding attacks and application layer DDoS flooding attacks, attackers typically spoof the source IP address of attack packets and send the attack packets to the victims directly. In indirect DDoS flooding attacks, such as Distributed Reflection DoS (DRDoS) attacks and link flooding attacks, attackers use many innocent intermediates to flood victims indirectly. Among these various types of attacks, DRDoS attacks have gained popularity and have become serious threats to the Internet due to their characteristics of anonymity and amplification. In DRDoS flooding attacks, an attacker (such as attacker <NUM>) typically commands a botnet (such as the botnet <NUM>) to send a large number of relatively large spoofed request packets (having a spoofed source address, which is the address of the victim) to reflectors (such as reflectors <NUM>) in order to trigger a relatively large number of relatively large response packets to be sent by the reflectors to a victim (illustratively, communication device <NUM>-<NUM> is the victim in <FIG>), thereby causing system resources of the victim to be consumed. It is noted that examples of such attack request and response packets are depicted in <FIG> for one of the communication devices <NUM> (illustratively, communication device <NUM>-<NUM> which, as indicated above, is the victim in <FIG>), where attacker <NUM> causes botnet <NUM> to send attack request packets to each of the reflectors <NUM>, which in turn causes each of the reflectors <NUM> to send corresponding response packets to the communication device <NUM>-<NUM> via the edge routers <NUM>. The attacker typically uses a protocol of the TCP/IP model that supports a request-response relationship (e.g., TCP, UDP, DNS, NTP, TFTP, SNMP, ICMP, or the like). It is noted that examples of specific request-response packets which may be used to initiate an attack are presented above in Table <NUM>. Typically, the number/size of response packets is many times larger than the number/size of request packets, so this type of DRDoS flooding attack is often referred to as a reflection amplification DDoS flooding attack (typically referred to more generally as an amplification attack). The impact of an amplification attacks is typically measured by two amplification factors: (<NUM>) Packet Amplification Factor (PAF), which is the ratio of the number of response packets to the number of request packets and (<NUM>) Bandwidth Amplification Factor (BAF), which is the ratio of the payload size of response packets to the payload size of request packets. Attackers are trending toward use of such amplification attacks at least for these two reasons: (i) anonymity: an attacker can hide its location by using a spoofed source IP address and (ii) amplification: an attacker can amplify the impact of attacks by exploiting bots for increasing both the number and size of spoofed request packets and unsymmetrical size of response packets. As such, amplification attacks have distinct characteristics that make them particularly serious threats to network security.

The communication network <NUM> of <FIG> is configured to support detection and mitigation of attacks (e.g., amplification attacks, as discussed above, or other types of attacks). The communication network <NUM> of <FIG> may be configured to support detection and mitigation of attacks by exploiting basic attack characteristics of amplification attacks (e.g., the one-to-one relationship between request packets and response packets in the absence of an amplification attack and the unbalanced relationship between request packets and response packets during an amplification attack) to perform attack detection. The communication network <NUM> of <FIG> may be configured to support detection and mitigation of attacks by exploiting the attack characteristics of amplification attacks based on use of network traffic data structures configured to support collection, aggregation, and analysis of network traffic information in a manner enabling identification of devices exhibiting anomalous behavior. The network traffic data structures may be reversible sketches (which, generally speaking, are compact, constant-size data structures configured to summarize network traffic by using hash functions to randomly aggregate traffic and to support identification of keys exhibiting anomalous behavior by reversely recovering the keys associated with anomalous traffic) or other types of data structures configured to support collection, aggregation, and analysis of network traffic information in a manner enabling identification of devices associated with traffic exhibiting anomalous behavior. Various example embodiments are primarily discussed herein within the context of embodiments in which the traffic records used for attack detection and mitigation are reversible sketches; however, as noted above, the traffic records used for attack detection and mitigation may be based on other types of data structures.

The communication network <NUM>, as discussed above, may be configured to perform attack detection and mitigation based on use of reversible sketches. In general, a sketch is a data structure that is composed of H hash tables of size M. In general, a sketch, models network traffic as a stream of (key, value) pairs, where the key can be one or more fields in packet headers of packets of the traffic and the value represents an accumulative feature of the packets (e.g., the number of packets, packet size, or the like). In the sketch, each bucket is represented as T[i][j], i=(<NUM>, <NUM>,. , H), j=(<NUM>, <NUM>,. , M), and each row i is associated with an independent hash function hi that maps the incoming keys into a hashing space of (<NUM>, <NUM>,. The hashed outputs are associated with their corresponding columns. For example, when a new pairwise item (key, value) arrives, the key will be hashed H times by {h<NUM>, h<NUM>,. , hH} and the value will be added to the corresponding bucket in each column, namely T[i] [hi(key)] = T[i] [hi(key)] + value, i=(<NUM>, <NUM>,. The purpose of applying H hash functions is to avoid the collisions between different keys. The probability that two keys are hashed in the same value is bounded if the function is selected from a kind of hash family. Typically, H hash functions in a sketch are chosen from the family of k-universal hash functions as defined in the following equation: <MAT>, where p is an arbitrary prime (e.g., Mersenne prime numbers may be chosen for fast implementation, although it will be appreciated that other prime numbers may be used), ai (≠<NUM>) and bi are randomly selected from the set of (<NUM>, <NUM>,. , p-<NUM>), and M is the width of sketch. Using k-universal hash functions, the probability that two keys are aggregated in the same bucket over H hash tables is (<NUM>/M) k*H. This type of sketch can be used to detect anomalies by monitoring the variation of the value in each bucket (e.g., whether the number of packets is larger than a given threshold, whether the amount of packet data is larger than a given threshold, or the like); however, this type of sketch cannot report the keys that are exhibiting the anomalies. In other words, such a sketch, which may be referred to as a traditional sketch so as to distinguish it from a reversible sketch, is not reversible. By contrast, a reversible sketch is configured to detect anomalies by monitoring the variation of the value in each bucket (e.g., whether the number of packets is larger than a given threshold, whether the amount of packet data is larger than a given threshold, or the like) and to identify the keys that are exhibiting the anomalies. A reversible sketch may use modular hashing and IP mangling technologies in order to modify the input keys and hash functions such that it becomes possible to recover the keys that exhibit anomalous behavior. In general, a reversible sketch supports a number of basic functions, including an UPDATE function that is configured to update a reversible sketch when new traffic arrives, a COMBINE function that is configured to linearly combine multiple reversible sketches into a single combined reversible sketch (e.g., using bucket-by-bucket aggregation), and an INFERENCE function that is configured to return a set of keys exhibiting anomalous behavior. The use of such functions for detection and mitigation of attacks is discussed further below.

The communication network <NUM>, as discussed above, may be configured to perform attack detection and mitigation based on the use of reversible sketches. The edge routers <NUM> may be configured to monitor network traffic for request packets and response packets, generate reversible sketches for the request packets and the response packets, and provide the reversible sketches to the central controller <NUM>. The edge routers <NUM>-<NUM> - <NUM>-E include network traffic collection elements <NUM>-<NUM> - <NUM>-E (collectively, network traffic collection elements <NUM>), respectively, that may be configured to provide such functions in support of attack detection and mitigation for communication network <NUM>. The central controller <NUM> is configured to receive the reversible sketches from the edge routers <NUM> and to determine, based on the reversible sketches, whether a traffic anomaly indicative of an attack on the communication network <NUM> is detected. The central controller <NUM> is configured to aggregate the reversible sketches from the edge routers <NUM> to form an aggregated reversible sketch, analyze the aggregated reversible sketch to identify anomalies indicative of an attack on the communication network <NUM>, and to initiate mitigation of the attack on the communication network <NUM>. The central controller <NUM> includes a network traffic analysis element <NUM> configured to provide such functions in support of attack detection and mitigation for communication network <NUM>. It is noted that distributed collection of network traffic information across the edge routers <NUM> and centralized aggregation and analysis of the network traffic information at the central controller <NUM> ensures that domain level network traffic information is collected and analyzed (which accounts for various types of network technologies - such as load balancing, fragmentation, or the like - which may cause pairwise request-response packet pairs to traverse different paths in the communication network <NUM>). These and various other functions supported by elements of communication network <NUM> for performing attack detection and mitigation are discussed further below.

The edge routers <NUM> may be configured to support attack detection and mitigation for communication network <NUM>.

The edge routers <NUM> may be configured to monitor network traffic, generate network traffic information based on monitoring of the network traffic, and send the network traffic information to the central controller <NUM>.

The edge routers <NUM> may be configured to monitor network traffic and generate the network traffic information at the data flow level. The edge routers <NUM> may be configured to aggregate packets into flows using the NetFlow standard or other mechanisms configured for use in aggregating packets into flows. It is noted that collection of network traffic information at the data flow level reduces collection cost.

The edge routers <NUM> may be configured to monitor network traffic and generate the network traffic information based on reversible sketches. The edge routers <NUM> may be configured to monitor network traffic and generate the network traffic information using a pair of reversible sketches including: (<NUM>) a reversible sketch configured to record outgoing request packets exiting the communication network via the edge router <NUM> (denoted as Out-RS) and (<NUM>) a reversible sketch configured to record incoming response packets entering the communication network via the edge router <NUM> (denoted as In-RS). The edge routers <NUM> may be configured to generate the reversible sketches based on use of the UPDATE function, which is configured to update a reversible sketch when new traffic arrives, thereby enabling monitoring of network traffic in real time. It is noted that use of reversible sketches for collection of network traffic information at the edge routers <NUM> reduces storage cost.

In Out-RS, the key that identifies a data flow may be the combination of destination IP address and destination port (denoted as {DIP, DP}) and the value may be the flow size of the data flow (e.g., the number of packets in the data flow, the amount of packet data in the data flow, or the like). In this case, the UPDATE function in Out-RS may be written as T[i][hi(DIP&DP)] += flow size, i=(<NUM>, <NUM>,. It will be appreciated that other keys may be used and that data flows may be defined in other ways (e.g., based on other combinations of fields of the packet headers).

In In-RS, the key that identifies a data flow may be the combination of source IP address and source port (denoted as {SIP, SP}) and the value may be the flow size of the data flow (e.g., the number of packets in the data flow, the amount of packet data in the data flow, or the like). In this case, the UPDATE function in In-RS may be written as T[i][hi(SIP&SP)] += flow size, i=(<NUM>, <NUM>,. It will be appreciated that other keys may be used and that data flows may be defined in other ways (e.g., based on other combinations of fields of the packet headers).

It is noted that, while selecting the key as {SIP, SP} in Out-RS and selecting the key as {DIP, DP} in In-RS also would satisfy the purpose of matching incoming response packets entering the communication network <NUM> with the corresponding outgoing request packets that were previously sent out from the communication network <NUM>, selecting the key as {DIP, DP} in Out-RS and selecting the key as {SIP, SP} in In-RS enables identification of the addresses of the reflectors <NUM> (since a reflector <NUM> that is used to facilitate an attack would be a destination (i.e., DIP) of request packets exiting the communication network <NUM> and a source (i.e., SIP) of response packets entering the communication network <NUM>), such that attack mitigation may be performed when a traffic anomaly indicative of an attack is detected (e.g., controlling traffic coming from a reflector <NUM> that is being used to facilitate an attack).

It will be appreciated that use of flow-level network traffic information collection based on reversible sketches may be considered to be use of dual efficient capabilities for reducing both collection and storage costs at the edge routers <NUM>, thereby enabling collection of network traffic information in the presence of massive volumes of traffic with reduced system burden.

The edge routers <NUM> may be configured to send the network traffic information to the central controller <NUM>. The network traffic information of an edge router <NUM>, as discussed above, includes the Out-RS reversible sketch of the edge router <NUM> and the In-RS reversible sketch of the edge router <NUM>. The edge routers <NUM> may send the network traffic information to the central controller <NUM> using various protocols, message formats, or the like, as well as various combinations thereof. It is noted that the sending of the network traffic information by the edge routers <NUM> to the central controller <NUM> is illustrated in <FIG> as the TRAFFIC RECORD elements.

The central controller <NUM> is configured to support attack detection and mitigation for communication network <NUM>.

The central controller <NUM> is configured to receive the network traffic information from the edge routers <NUM>. The network traffic information of an edge router <NUM>, as discussed above, includes the Out-RS reversible sketch of the edge router <NUM> and the In-RS reversible sketch of the edge router <NUM>. The central controller <NUM> may receive the network traffic information from the edge routers <NUM> using various protocols, message formats, or the like, as well as various combinations thereof. It is noted that the receipt of the network traffic information at the central controller <NUM> from the edge routers <NUM> is illustrated in <FIG> as the TRAFFIC RECORD elements.

The central controller <NUM> is configured to aggregate the reversible sketches from the edge routers <NUM> to form an aggregated reversible sketch, analyze the aggregated reversible sketch to identify anomalies indicative of an attack on the communication network <NUM>, and to initiate mitigation of the attack on the communication network <NUM>.

The central controller <NUM> is configured to aggregate the reversible sketches from the edge routers <NUM> to form an aggregated reversible sketch. The aggregated reversible sketch includes the network traffic information of the edge routers <NUM>, as if the traffic of the edge routers <NUM> had passed through a single router.

The central controller <NUM> may be configured to aggregate the reversible sketches from the edge routers <NUM> by applying a COMBINE function, which is configured to linearly combine multiple reversible sketches into a single reversible sketch (e.g., using bucket-by-bucket aggregation).

In applying the COMBINE function, in order to identify mismatches between request packets and response packets (which might be indicative of an attack on the communication network <NUM>), weights are applied to the Out-RS reversible sketches and the In-RS reversible sketches of the edge routers <NUM> to reflect matching of request packets and response packets. The weights may be applied in a manner that cancels the respective measures of request packets exiting the communication network <NUM> via the respective edge routers <NUM> for respective data flows and the respective measures of response packets entering the communication network <NUM> via the respective edge routers <NUM> for respective data flows. The weights may be applied in a manner that produces anomalous values in buckets of the aggregated reversible sketch during an attack. For example, for a given data flow defined for a specific address and port of a reflector <NUM>, if there are <NUM> request packets associated with the data flow (i.e., that left the communication network <NUM> for the data flow, based on {DIP, DP}) and <NUM> response packets associated with the data flow (i.e., that entered the communication network <NUM> for the data flow, based on {SIP, SP}), the weights may be applied such that <NUM> of the response packets are matched to (and, thus, cancel out) <NUM> of the response packets, thereby leaving <NUM> unmatched response packets that should not have been entered the communication network <NUM> since no corresponding request packets were sent.

In at least some embodiments, for example, weights may be applied such that outgoing request packets exiting the communication network <NUM> are weighted negatively and incoming response packets entering the communication network <NUM> are weighted positively. For example, weights of-<NUM> and +<NUM> (or other suitable weights, such as -<NUM>/+<NUM> or the like) may be allocated to Out-RS reversible sketches and the In-RS reversible sketches, respectively. The definition of weights such that outgoing request packets are weighted negatively and incoming response packets are weighted positively ensures that, when an amplification attack occurs, large positive values will be observed in buckets of the aggregated reversible sketch (due to the large number of response packets associated with given request packets). The formula for the aggregation of reversible sketches of the edge routers <NUM> using the COMBINE function, where outgoing request packets are weighted negatively and incoming response packets are weighted positively, may be specified as follows: <MAT>, where TRS[i][j] is represented as each bucket in the aggregated reversible sketch, TOut-RS[i][j] and TIn-RS[i][j] are represented as each bucket in Out-RS and In-RS respectively, N is the number of edge routers (n = <NUM>, <NUM>,. , N), and i=(<NUM>, <NUM>,. , H) and j=(<NUM>, <NUM>,.

In at least some embodiments, for example, weights may be applied such that outgoing request packets are weighted positively and incoming response packets are weighted negatively. For example, weights of +<NUM> and -<NUM> (or other suitable weights, such as +<NUM>/-<NUM> or the like) may be allocated to Out-RS reversible sketches and the In-RS reversible sketches, respectively. The definition of weights such that outgoing request packets are weighted positively and incoming response packets are weighted negatively ensures that, when an amplification attack occurs, large negative values will be observed in buckets of the aggregated reversible sketch (due to the large number of response packets associated with given request packets). The formula for the aggregation of reversible sketches of the edge routers <NUM> using the COMBINE function, where outgoing request packets are weighted positively and incoming response packets are weighted negatively, may be specified in a manner similar to that described above for the case in which positive/negative weighting is reversed.

The central controller <NUM> is configured to analyze the aggregated reversible sketch to identify anomalies indicative of an attack on the communication network <NUM>.

The central controller <NUM> is configured to analyze the aggregated reversible sketch to identify anomalies by analyzing each bucket of the aggregated reversible sketch to determine whether the bucket is anomalous. The buckets correspond to keys which in turn correspond to flows associated with destination addresses. The determination as to whether a given bucket is anomalous may be based on a comparison of a value of the bucket to a threshold (denoted as R). The value of R may be set in various ways, depending on various factors (e.g., application of weights to the reversible sketches from the edge routers <NUM>, protocol type, or the like, as well as various combinations thereof. For example, in some embodiments, since a host should not receive a response packet from a server if it did not send a request packet to that server, any bucket with a non-zero value (e.g., a positive value where outgoing request packets are weighted negatively and incoming response packets are weighted positively or a negative value where outgoing request packets are weighted positively and incoming response packets are weighted negatively) may be identified as being anomalous. However, considering the IP fragmentation transmission of response packets of some protocols, the value of R may be set to be a small non-zero value (it is noted that such non-zero values are suitable since, when an amplification attack takes place, the values in the anomalous buckets, generally, are much larger than such small non-zero values due to the large number of response packets that are generated). It will be appreciated that the buckets of the aggregated reversible sketch may be analyzed in other ways for determining whether the buckets are anomalous.

In at least some embodiments, identification of an anomalous bucket for a key results in identification of the key as being an anomalous key for which attack mitigation is initiated.

In at least some embodiments, identification of an anomalous bucket for a key may or may not result in identification of the key as being an anomalous key for which attack mitigation is initiated. In at least some embodiments, a mechanism for reducing false positives may be utilized. In at least some embodiments, identification of an anomalous bucket for a key results in inclusion of the key in a list of potentially anomalous keys. The aggregated reversible sketch may be analyzed on a per-row basis in order to produce, for each of the rows of the aggregated reversible sketch, a respective list of potentially anomalous keys (i.e., the list of potentially anonymous keys includes each key of the row that is associated with an anomalous bucket of that row). This may be based on use of the INFERENCE function and a threshold (where this threshold may be denoted as R) which is used to determine, for each key in the row, whether the value associated with the key is potentially anomalous (e.g., satisfying the threshold) and, thus, whether that key is considered to be potentially anomalous. This results in a set of H lists of potentially anomalous keys (i.e., a respective list for each of the H rows of the aggregated reversible sketch). The set of H lists of potentially anomalous keys may then be analyzed to determine which of the potentially anonymous keys are identified as actual anomalous keys for which attack mitigation is initiated. In at least some embodiments, analysis of the set of H lists of potentially anomalous keys to determine which of the potentially anonymous keys are identified as actual anomalous keys may be based on a voting process that is configured to reduce the false positive rate for anomalous keys. In at least some embodiments, the voting process is configured such that a potentially anomalous key is identified as an actual anomalous key based on a determination that the key is included in at least a threshold number of lists of potentially anomalous keys (where this threshold may be denoted as W). The threshold number of lists of potentially anonymous keys may be set based on the number of hash tables H (e.g., to H/<NUM>, H/<NUM>, or in any other suitable manner configured to balance identification of attacks versus suppression of false positives).

The central controller <NUM> is configured to initiate mitigation of the attack. The central controller <NUM> is configured to identify the source address of a reflector <NUM> associated with the identified attack and, based on identification of the source address of the reflector <NUM> associated with the identified attack, to initiate one or more or more actions for mitigating the identified attack.

The central controller <NUM> is configured to identify the source address of a reflector <NUM> associated with the identified attack. The central controller <NUM>, for a key identified as being an anomalous key associated with an attack, is configured to identify the source address of the reflector <NUM> associated with the key. It is noted that, while the reflector <NUM> is innocent (namely, it is merely performing its function of sending response packets in response to request packets, without knowledge that the request packets are spoofed by a malicious entity), it is sending a large quantity of response packets and, thus, facilitating the attack. The central controller <NUM> may obtain the source address of the reflector <NUM> from the aggregated reversible sketch.

The central controller <NUM> is configured to initiate one or more actions for mitigating an identified attack. The central controller <NUM> may be configured to send instructions to edge routers <NUM> for triggering the edge routers <NUM> to mitigate an identified attack. For example, the central controller <NUM> may be configured to send, toward the edge routers <NUM>, instructions for the edge routers <NUM> to control traffic of a data flow identified as having a traffic anomaly associated therewith (e.g., an anomalous traffic flow which comes from a particular address and port of a particular reflector <NUM>, as identified by the central controller <NUM> from the aggregated reversible sketch). The instruction to control traffic of a data flow identified as having a traffic anomaly associated therewith may be sent to all of the edge routers <NUM> or to a subset of the edge routers <NUM> (e.g., where it is known that packets of the data flow may only enter communication network <NUM> via that subset of edge routers <NUM>). The traffic control instructions may include instructions to filter traffic, instructions to block traffic, or the like, as well as various combinations thereof. It is noted that the sending of the traffic control instructions from the central controller <NUM> to edge routers <NUM> is illustrated in <FIG> as the TRAFFIC CONTROL COMMAND elements. The central controller <NUM> may be configured to initiate one or more other actions for mitigating an identified attack.

The edge routers <NUM> may be configured to perform one or more actions for mitigating an attack identified by the central controller <NUM>. The edge routers <NUM> may be configured to perform the one or more actions for mitigating an attack based on instructions received from the central controller <NUM> (or from any other suitable source of such instructions). For example, the edge routers <NUM> may be configured to receive, from the central controller <NUM>, instructions to control traffic of data flows identified as having traffic anomalies associated therewith and to control the traffic of the data flows identified as having traffic anomalies associated therewith based on the instructions from the central controller <NUM> (e.g., controlling traffic of an anomalous traffic flow which comes from a particular address and port of a particular reflector <NUM>, as identified by the central controller <NUM> from the aggregated reversible sketch). The traffic control instructions may include instructions to filter traffic, instructions to block traffic, or the like, as well as various combinations thereof. It is noted that the receipt of the traffic control instructions by the edge routers <NUM> from the central controller <NUM> is illustrated in <FIG> as the TRAFFIC CONTROL COMMAND elements. The edge routers <NUM> may be configured to perform one or more other actions for mitigating an attack identified by the central controller <NUM>.

It will be appreciated that the collection of network traffic information based on reversible sketches by the edge routers <NUM> and aggregation and analysis of the network traffic information of the edge routers <NUM> based on reversible sketches by the central controller <NUM> continues over time. When the central controller <NUM> initiates control of traffic from an anomalous source address (e.g., filtering, blocking, or the like), the control of traffic from the anomalous source address by the edge routers <NUM> should mitigate the attack over time. This will cause the counts of incoming response packets from the anomalous source address to fall over time. This drop in the number of incoming response packets from the anomalous source address, over time, will be reflected in the In-RS reversible sketches generated by the edge routers <NUM> and, thus, after being provided to the central controller <NUM>, also will be reflected in the aggregated reversible sketches generated by the central controller <NUM> based on the In-RS reversible sketches received from the edge routers <NUM>. The value in the bucket of the key associated with the source address will fall over time such that, eventually, the key associated with the source address will be removed from the list of anomalous keys for which attack mitigation is performed. The removal of the key associated with the source address from the list of anomalous keys for which attack mitigation is performed triggers the central controller <NUM> to initiate removal of attack mitigation for the source address. The removal of attack mitigation may use a process that is a reverse of the process used to apply attack mitigation. For example, the central controller <NUM> may send instructions to edge routers <NUM> for triggering the edge routers <NUM> to stop attack mitigation functions (e.g., for example, the central controller <NUM> may be configured to send, toward the edge routers <NUM>, instructions for the edge routers <NUM> to stop controlling the traffic of data flows which come from anomalous source addresses identified by the central controller <NUM> from the aggregated reversible sketch) and the edge routers <NUM> may stop attack mitigation functions based on the instructions from the central controller <NUM> (e.g., for example, the edge routers <NUM> may be configured to receive, from the central controller <NUM>, instructions to stop controlling traffic of the data flows identified as having traffic anomalies associated therewith and to stop controlling the traffic of the data flows identified as having traffic anomalies associated therewith). In other words, controlling of traffic from the anomalous source address continues until the anomalous source address disappears from the list of anomalous keys for which attack mitigation was initiated. This enables reevaluation of the situation by the central controller <NUM> over time to ensure that attack mitigation is applied when needed and remove when no longer needed.

It will be appreciated that the detection and mitigation of attacks over time may be based on an attack detection and mitigation schedule.

The edge routers <NUM> may be configured to monitor network traffic to generate network traffic information and to send the network traffic information to the central controller <NUM> based on attack detection and mitigation schedule. The attack detection and mitigation schedule defines collection times during which the edge routers <NUM> collect the network traffic information and after which the edge routers <NUM> send the network traffic information to the central controller <NUM>. The collection time for the edge routers <NUM> may be set to be equal to or a little greater than the round trip time (RTT), since it is expected that the corresponding response packet for a given request packet should be received within the RTT. The edge routers <NUM> may be configured such that, during a given collection time, the Out-RS and In-RS reversible sketches at the respective edge routers <NUM> continuously record traffic information associated with traffic at the respective edge routers <NUM> in real time. The edge routers <NUM> may be configured such that the network traffic information collected by the respective edge routers <NUM> (namely, the Out-RS and In-RS data structures) during a given collection time are delivered to the central controller <NUM> after the collection time.

The central controller <NUM> is configured to aggregate the reversible sketches from the edge routers <NUM> to form the aggregated reversible sketch and analyze the aggregated reversible sketch to identify anomalies indicative of an attack on the communication network <NUM> based on the attack detection and mitigation schedule. The attack detection and mitigation schedule defines collection times during which the edge routers <NUM> collect the network traffic information and after which the edge routers <NUM> send the network traffic information to the central controller <NUM> for aggregation and analysis. As previously discussed, the collection time for the edge routers <NUM> may be set to be equal to or a little greater than RTT. The central controller <NUM> may be configured to aggregate the reversible sketches from the edge routers <NUM> to form the aggregated reversible sketch and analyze the aggregated reversible sketch to identify anomalies indicative of an attack on the communication network <NUM> once per collection period, once every other collection period, or the like.

It will be appreciated that the detection and mitigation of attacks over time may be based on various other suitable types of timing and control information.

The edge routers <NUM> and the central controller <NUM> may be configured to provide various other functions supporting detection and mitigation of attacks in communication network <NUM>.

The communication network <NUM> is configured to control detection and mitigation of attacks based on various parameters discussed above. For example, four of the parameters discussed herein in conjunction with detection and mitigation of attacks include the number of hash functions (H), the sketch width (M), the bucket threshold for determining whether a bucket is anomalous (R), and a list threshold for determining whether a key is anomalous (W).

The communication network <NUM> may be configured to control the values of these parameters, including dynamic modification of these parameters, in order to provide finer control over detection and mitigation of attacks in terms of resources consumed in detection and mitigation of attacks, balancing identification of attacks with false positives, or the like, as well as various combinations thereof. The impacts of using various values for such parameters is discussed further below.

For parameters H and M, it is noted that the performance of attack detection and memory consumption primarily depends on the values of H and M. The values of H and M within the context of communication network <NUM> may be determined based on a combination of the theoretical derivation of reversible sketch data structures and an experimental environment. It will be appreciated that the values of parameters H and M within the context of communication network <NUM> may be determined in other ways.

For parameter R, it is noted that, if a host does not send out any request packets to a given server, then it should not receive response packets from that server. Hence, any bucket with a positive value can be regarded as anomalous. However, considering the IP fragmentation transmission of response packets of some protocols, R may be set to be a small non-zero value, such as a small positive value (e.g., <NUM>, <NUM>, <NUM>, <NUM>, or the like) where outgoing request packets are weighted negatively and incoming response packets are weighted positively or a small negative value (e.g., -<NUM>, -<NUM>, -<NUM>, -<NUM>, or the like) where outgoing request packets are weighted positively and incoming response packets are weighted negatively. It is noted that such values are suitable since, when an amplification attack takes place, the values in anomalous buckets, generally, are much larger than such values due to the large number of response packets that are generated. It will be appreciated that the value of parameter R within the context of communication network <NUM> may be set in other ways.

For parameter W, it is noted that the value of W may be set based on the value of the number of hash functions (H). For example, W can be set as [H/<NUM>]. That is to say, a key may be considered to be an attacking source if that key exhibits anomalous behavior in at least [H/<NUM>] rows. It will be appreciated that the value of parameter W within the context of communication network <NUM> may be set in other ways.

<FIG> depicts an example attack detection and mitigation system configured to support detection and mitigation of an attack in a communication network.

The attack detection and mitigation system <NUM> includes a set of edge routers <NUM> and a central controller <NUM>.

The edge routers <NUM> each monitor traffic, generate reversible sketches for outgoing request packets and incoming response packets (illustrative, two reversible sketches, denoted as RS-Out and RS-In, are depicted as being generated by each edge router <NUM>), and send the reversible sketches to the central controller <NUM>.

The central controller <NUM> receives the reversible sketches from the edge routers <NUM>, aggregates the reversible sketches from the edge routers <NUM> to form an aggregated reversible sketch, performs attack detection based on the aggregated reversible sketch (e.g., by identifying a list of anomalous keys associated with traffic anomalies and using a voting mechanism to identify a final list of anomalous keys) to identify an attack, and initiates attack mitigation in order to mitigate the attack.

It will be appreciated that the various functions performed by the edge routers <NUM> and the central controller <NUM> in the attack detection and mitigation system <NUM> may be further understood when considered in conjunction with the description of the communication system <NUM> of <FIG>.

It will be appreciated that, although primarily presented herein within the context of example embodiments in which a particular type of data structure (namely, a reversible sketch) is used to provide traffic records used in attack detection and mitigation, various other data structures supporting collection, aggregation, and analysis of traffic information for anomaly detection may be used to provide traffic records for attack detection and mitigation.

<FIG> depicts an example embodiment of a method for use by an edge device to support detection and mitigation of an attack in a communication network. The edge device may be an edge router (e.g., an edge router <NUM> of <FIG>) or other suitable type of edge device. It will be appreciated that, although primarily presented as being performed serially, at least a portion of the functions may be performed contemporaneously or in a different order than as presented in <FIG>. At block <NUM>, method <NUM> begins. At block <NUM>, traffic at the edge device of the communication network is monitored for request packets and response packets. At block <NUM>, a first traffic record indicative of respective measures of request packets exiting the communication network via the edge device for respective data flows is generated and a second traffic record indicative of respective measures of response packets entering the communication network via the edge device for respective data flows is generated. At block <NUM>, the first traffic record and the second traffic record are sent from the edge device toward a controller. At block <NUM>, method <NUM> ends.

<FIG> depicts an example embodiment of a method for use by a controller to support detection and mitigation of an attack in a communication network. The controller may be a central controller (e.g., central controller <NUM> of <FIG>) or other suitable type of controller. It will be appreciated that, although primarily presented as being performed serially, at least a portion of the functions may be performed contemporaneously or in a different order than as presented in <FIG>. At block <NUM>, method <NUM> begins. At block <NUM>, for each edge device in a set of edge devices of a communication network, a respective set of network traffic information is received where the network traffic information for the respective edge device includes a first traffic record indicative of respective measures of request packets exiting the communication network via the respective edge device for respective data flows and a second traffic record indicative of respective measures of response packets entering the communication network via the respective edge device for respective data flows. At block <NUM>, a determination is made, based on the sets of network traffic information of the edge devices, as to whether a traffic anomaly indicative of an attack on the communication network is detected. At block <NUM>, method <NUM> ends.

<FIG> depicts an example embodiment of a method for use by a controller to support detection and mitigation of an attack in a communication network. The controller may be a central controller (e.g., central controller <NUM> of <FIG>) or other suitable type of controller. The method <NUM> of <FIG> may be suitable for use as block <NUM> of method <NUM> of <FIG>. It will be appreciated that, although primarily presented as being performed serially, at least a portion of the functions may be performed contemporaneously or in a different order than as presented in <FIG>. At block <NUM>, method <NUM> begins. At block <NUM>, the first traffic records of the edge devices (indicative of respective measures of request packets exiting the communication network via the respective edge devices for respective data flows) and the second traffic records of the edge devices (indicative of respective measures of response packets entering the communication network via the respective edge devices for respective data flows) are aggregated to form an aggregated traffic record. As indicated by block <NUM>, the aggregation of the first traffic records of the edge devices and the second traffic records of the edge devices to form the aggregated traffic record may be performed in a manner for cancelling the respective measures of request packets exiting the communication network via the respective edge devices for respective data flows and the respective measures of response packets entering the communication network via the respective edge devices for respective data flows, may be performed based on weightings (e.g., weighting respective measures of request packets exiting the communication network via the respective edge device for respective data flows and the respective measures of response packets entering the communication network via the respective edge device for respective data flows in a manner tending to enabling matching of request and response packets), or the like, as well as various combinations thereof. At block <NUM>, a determination is made, based on the aggregated traffic record, as to whether a traffic anomaly indicative of an attack on the communication network is detected. A traffic anomaly indicative of an attack on the communication network is associated with a data flow (e.g., the key defines the data flow). As indicated by block <NUM>, the determination as to whether a traffic anomaly indicative of an attack on the communication network is detected may include identifying anomalous keys (e.g., having anomalous flow size measures, such as flow size measures indicative of a greater number of response packets than request packets or greater quantity of response packet data than request packet data) based on a threshold (e.g., flow size threshold), based on voting (e.g., identifying a key as being anomalous based on a determination that the key appears in an aggregated packet record a threshold number of times), or the like, as well as various combinations thereof. As indicated by block <NUM>, the determination as to whether a traffic anomaly indicative of an attack on the communication network is detected may be based on various other types of information or analysis of the aggregated traffic record. At block <NUM>, method <NUM> ends.

<FIG> depicts an example embodiment of a method for use by a controller to support detection and mitigation of an attack in a communication network. The controller may be a central controller (e.g., central controller <NUM> of <FIG>) or other suitable type of controller. It will be appreciated that, although primarily presented as being performed serially, at least a portion of the functions may be performed contemporaneously or in a different order than as presented in <FIG>. At block <NUM>, method <NUM> begins. At block <NUM>, a traffic anomaly indicative of an attack on the communication network is detected. The traffic anomaly indicative of the attack on the communication network is associated with a data flow (e.g., the key defines the data flow). As indicated by block <NUM>, the traffic anomaly indicative of the attack on the communication network may be detected by identifying anomalous keys (e.g., having anomalous flow size measures, such as flow size measures indicative of a greater number of response packets than request packets or greater quantity of response packet data than request packet data) based on a threshold (e.g., flow size threshold), based on voting (e.g., identifying a key as being anomalous based on a determination that the key appears in an aggregated packet record a threshold number of times), or the like, as well as various combinations thereof. As indicated by block <NUM>, the traffic anomaly indicative of the attack on the communication network may be detected based on various other types of information or analysis. At block <NUM>, attack mitigation is initiated for the attack on the communication network. As indicated by block <NUM>, attack mitigation may include identifying the reflector(s) associated with the attack, sending various traffic control instructions (e.g., filtering, blocking, or the like), or the like, as well as various combinations thereof. At block <NUM>, method <NUM> ends.

Various example embodiments supporting attack detection and mitigation may provide various advantages or potential advantages.

For example, various example embodiments supporting attack detection and mitigation may be configured to support detection and mitigation of attacks in a protocol-independent manner. Various example embodiments supporting attack detection and mitigation may be configured to exploit basic attack characteristic of amplification attacks that cause the unbalanced relationship between request packets and response packets in order to detect such amplification attacks. There are many protocols that can be exploited for launching amplification attacks and, since it is unlikely to be able to predict which type of amplification attacks will occur, a protocol-independent method is highly valuable for evaluating Internet security as a whole.

For example, various example embodiments supporting attack detection and mitigation may be configured to support detection and mitigation of attacks in the presence of large quantities of network traffic with high accuracy and efficiency. Various example embodiments supporting attack detection and mitigation may be configured to support efficient processing of large-scale traffic, thereby ensuring that large quantities of valid network traffic do not swamp significant signals of attacks and, thus, enabling detection and mitigation of attacks in the presence of large quantities of network traffic. It will be appreciated that such support for efficient processing of large-scale traffic enables detection and mitigation of attacks at the victim end, thereby obviating the need for use of reflector-end detection methods which typically have the following drawbacks: (i) the large number of potential reflectors makes detection methods difficult to deploy in practice, and (ii) illegitimate requests with spoofed addresses might look the same as legitimate requests. Thus, various example embodiments supporting attack detection and mitigation can alleviate the impact of large-scale network traffic on attack detection, supporting more efficient and accurate attack detection while handling a massive volume of network traffic.

For example, various example embodiments supporting attack detection and mitigation may be configured to support detection and mitigation of attacks in high-speed networks. In high-speed networks (e.g., with rates of up to hundreds of Gigabits per second), collection of packets generally relies upon expensive hardware and infrastructures. Various example embodiments supporting attack detection and mitigation may be configured to utilize flow-level data, which is suitable for collection in high-speed networks, as flow-level data generally has a more macroscopic view of the network traffic. Various example embodiments supporting attack detection and mitigation may be configured to, at each of the network elements at which data is collected, aggregate packets into flows (e.g., based on the NetFlow standard or using other suitable flow-level packet aggregation functions) and directly collect flow-level data, thereby providing improved support for deployment of attack detection and mitigation functions in high-speed networks.

For example, various example embodiments supporting attack detection and mitigation may be configured to support detection and mitigation of attacks with relatively low memory consumption. In IPv4, for example, the size of SIP/DIP is <NUM> bits and the size of SP/DP is <NUM> bits such that, if keeping per-flow status for each {SIP&SP} / {DIP&DP} pair, then the size of monitored key space is at least <NUM><NUM> bits. Various example embodiments supporting attack detection and mitigation may be configured to reduce memory consumption by utilizing reversible sketch data structures to record traffic information. As discussed herein, a reversible sketch data structure is a compact, constant-sized data structure that summarizes network traffic by using hash functions to randomly aggregate traffic. In the case of IPv4, for example, use of reversible sketch data structures reduces the monitored key space of at least <NUM><NUM> bits to a fixed size (e.g., M=<NUM><NUM>, H =<NUM>) by aggregating multiple {SIP&SP} / {DIP&DP} pairs into common buckets. It is noted that, while there is a chance for collisions, there are various mechanisms available for resolving recording errors caused by such collisions. It is noted that memory savings also may be realized for other protocols (e.g., IPv6 or the like).

Various example embodiments supporting attack detection and mitigation may provide various other advantages or potential advantages.

<FIG> depicts a high-level block diagram of a computer suitable for use in performing various functions described herein.

The computer <NUM> includes a processor <NUM> (e.g., a central processing unit (CPU), a processor having a set of one or more processor cores, or the like) and a memory <NUM> (e.g., a random access memory (RAM), a read only memory (ROM), or the like). The processor <NUM> and the memory <NUM> are communicatively connected.

The computer <NUM> also may include a cooperating element <NUM>. The cooperating element <NUM> may be a hardware device. The cooperating element <NUM> may be a process that can be loaded into the memory <NUM> and executed by the processor <NUM> to implement functions as discussed herein (in which case, for example, the cooperating element <NUM> (including associated data structures) can be stored on a non-transitory computer-readable storage medium, such as a storage device or other storage element (e.g., a magnetic drive, an optical drive, or the like)).

The input/output devices <NUM> may include one or more of a user input device (e.g., a keyboard, a keypad, a mouse, a microphone, a camera, or the like), a user output device (e.g., a display, a speaker, or the like), one or more network communication devices or elements (e.g., an input port, an output port, a receiver, a transmitter, a transceiver, or the like), one or more storage devices or elements (e.g., a tape drive, a floppy drive, a hard disk drive, a compact disk drive, or the like), or the like, as well as various combinations thereof.

It will be appreciated that computer <NUM> of <FIG> may represent a general architecture and functionality suitable for implementing functional elements described herein, portions of functional elements described herein, or the like, as well as various combinations thereof. For example, computer <NUM> may provide a general architecture and functionality that is suitable for implementing one or more of a communication device <NUM>, an edge router <NUM>, a network traffic collection element <NUM>, central controller <NUM>, network traffic analysis element <NUM>, a reflector <NUM>, an attacker <NUM>, an element of a botnet <NUM>, an edge router <NUM>, central controller <NUM>, or the like.

It will be appreciated that the functions depicted and described herein may be implemented in software (e.g., via implementation of software on one or more processors, for executing on a general purpose computer (e.g., via execution by one or more processors) so as to provide a special purpose computer, and the like) and/or may be implemented in hardware (e.g., using a general purpose computer, one or more application specific integrated circuits (ASIC), and/or any other hardware equivalents).

It will be appreciated that at least some of the functions discussed herein as software methods may be implemented within hardware, for example, as circuitry that cooperates with the processor to perform various functions. Portions of the functions/elements described herein may be implemented as a computer program product wherein computer instructions, when processed by a computer, adapt the operation of the computer such that the methods and/or techniques described herein are invoked or otherwise provided. Instructions for invoking the various methods may be stored in fixed or removable media (e.g., non-transitory computer-readable media), transmitted via a data stream in a broadcast or other signal bearing medium, and/or stored within a memory within a computing device operating according to the instructions.

It will be appreciated that the term "or" as used herein refers to a non-exclusive "or" unless otherwise indicated (e.g., use of "or else" or "or in the alternative").

Claim 1:
An apparatus, comprising at least:
means for receiving (<NUM>), from each edge device (<NUM>, <NUM>) in a set of edge devices of a communication network (<NUM>), a respective set of network traffic information comprising a first traffic record indicative of respective measures of request packets exiting the communication network (<NUM>) via the respective edge device (<NUM>, <NUM>) for respective data flows and a second traffic record indicative of respective measures of response packets entering the communication network (<NUM>) via the respective edge device (<NUM>, <NUM>) for respective data flows, wherein, for at least one of the edge devices (<NUM>, <NUM>), the first traffic record comprises a first reversible sketch and the second traffic record comprises a second reversible sketch; and
means for determining (<NUM>), based on the sets of network traffic information of the edge devices (<NUM>, <NUM>), whether a traffic anomaly indicative of an attack on the communication network (<NUM>) is detected, wherein, to determine whether the traffic anomaly indicative of an attack on the communication network (<NUM>) is detected, the apparatus at least comprises:
means for aggregating (<NUM>) the first traffic records of the edge devices (<NUM>, <NUM>) and the second traffic records of the edge devices (<NUM>, <NUM>) to form thereby an aggregated traffic record; and
means for determining (<NUM>), based on the aggregated traffic record, whether a traffic anomaly indicative of an attack on the communication network (<NUM>) is detected, wherein to form the aggregated traffic record, the apparatus further at least comprises:
means for applying a first set of weights to values of the first traffic records of the edge devices (<NUM>, <NUM>) to provide respective weighted first traffic records;
means for applying a second set of weights to values of the second traffic records of the edge devices (<NUM>, <NUM>) to provide respective weighted second traffic records; and
means for aggregating the weighted first traffic records of the edge devices (<NUM>, <NUM>) and the weighted second traffic records of the edge devices (<NUM>, <NUM>) to form thereby the aggregated traffic record.