FIELD OF THE INVENTION

The invention relates in general to Internet security and in particular to detection of denial of service (DoS) attacks and distributed denial of service (DDoS) attacks, and more particularly to detecting changes in recent cardinality associated with network traffic flows for detecting DDoS attacks.

BACKGROUND OF THE INVENTION

In recent years, denial of service (DoS) attacks and distributed denial of service (DDoS) attack has become a major security threat to Internet service. A DoS attack and DDoS attack can completely consume the resources of a server, which will be unable to provide services for legitimate users. With the exponential increase of Internet-based e-business and e-commence, the damage of DoS attacks and DDoS attacks is becoming more and more significant. Therefore, how to handle DoS attacks and DDoS attacks and protect the access of legitimate users has become a crucial challenge and has attracted the attention of both the industry and academia.

Due to the readily available tools and its simple nature, flooding packets is the most common and effective DoS attack. While flooding tools have been become more sophisticated, they have been getting easier to use. An adversary without much knowledge of programming can download a flooding tool and then launch a DoS attack. The flooding traffic of a DoS attack may originate from either a single source or multiple sources. We call the latter case a distributed denial of service (DDoS) attack. Briefly, a DDoS attack works as follows. An attacker sends control packets to the previously-compromised flooding sources, instructing them to target at a given victim. The flooding sources then collectively generate and send an excessive number of flooding packets to the victim, but with fake and randomized source addresses, so that the victim cannot locate the flooding sources.

To prevent DoS attacks, researchers have designed and implemented a number of countermeasures. In general, the countermeasures of DoS attacks can be classified into three different categories: detection, defense (or mitigation), and IP trace-back mechanisms. Detecting DoS attacks in real time is the first step of combating DoS attacks. An automated and fast detection is essential to the protection against DoS attacks. Upon timely detection of a DoS attack, more sophisticated defense mechanisms will be triggered to shield victim servers or link bandwidth from DoS traffic, and block the prorogation of DDoS traffic at routers. At the same time, more expensive IP trace-back to single out flooding sources is performed. Unlike defense and trace-back mechanisms, detection itself should be an always-on function with little overhead, causing minimal disruption to normal operations and withstanding any flooding attacks. Basically, detecting DoS attacks belongs to network-based intrusion detection. A network-based intrusion detection system (NIDS) is based on the idea that an intruder's behavior will be noticeably different from that of a legitimate user and that many unauthorized actions are detectable. A commonly used detection approach is either signature-based or anomaly-based. A signature-based NIDS inspects the passing traffic and searches for matches against already-known malicious patterns. A key advantage of signature-based detection algorithms is their high degree of accuracy in detecting known attacks and their variations. Their obvious drawback is the inability to detect attacks whose instances have not yet been observed.

Anomaly detection approaches, on the other hand, build models of normal data and detect deviations from the normal model in observed data. Anomaly detection have the advantage that they can detect new types of attacks as deviations from normal usage. However, current anomaly detection schemes suffer from a high rate of false alarms. This occurs primarily because previously unseen (yet legitimate) system behaviors are also recognized as anomalies, and hence flagged as potential attacks.

Moreover anomaly detection algorithms need to be adaptive, which means they must be able to cope with constantly changing network conditions. Therefore, sophisticated traffic analysis is required to manage the strong non-stationary behavior of normal Internet traffic and at the same time distinguish between natural variations in traffic profiles, such as changed usage patterns between day and night, week-days and weekend or a flash-crowd to a web-site, and truly anomalous traffic variations, such as DDoS attacks. Second, the algorithms need to show a good trade-off between false positive/negative ratio and detection lag (time interval between the time at which the attack starts and the time at which the anomaly is detected). Third, the algorithms need to be computationally simple because of the multi-Gigabit per second (Gbps) links used by most of the carriers today and limited memory usage for on-fly information storage. Forth, the algorithms should detect both low and high-volume attacks. Current detection algorithms typically process high-volume attacks but their performance degrades severely as soon as the attacks rate drops below a specific threshold becoming almost undistinguishable with “Internet noise”. To gain a thorough picture of the overall traffic in a network, it is important for an adaptive anomaly detection solution to see the complete traffic profiles. Therefore, to handle the typical large, distributed networks of carriers and service providers, anomaly detection solutions need to be deployable such that a large number of links must be monitored in a cost-effective, yet scalable manner. Moreover, in order to detect low-volume attacks, the algorithm must extract and correlate a few key features that represent sufficiently well normal traffic behavior such to guarantee a fast and efficient detection of anomalies in their infancy stage.

It is to be further appreciated that a number of unique items or attributes in a stream of network traffic may be analyzed to detect hidden characteristics present in that network traffic. Since maintaining exact counts of unique items, or cardinality, in an unbounded network traffic stream is infeasible when processing network traffic on a scale typically handled by service providers—estimating algorithms is preferably utilized to provide a reasonably accurate measure of the cardinality of the network traffic. It is to be appreciated, and in accordance with the illustrated embodiments, this estimated cardinality can in turn be used to detect sudden changes in the profile of the network traffic, enabling dynamic detection of the certain classes of HTTP DDoS attacks.

SUMMARY OF THE INVENTION

The purpose and advantages of the illustrated embodiments will be set forth in and apparent from the description that follows. Additional advantages of the illustrated embodiments will be realized and attained by the devices, systems and methods particularly pointed out in the written description and claims hereof, as well as from the appended drawings.

In accordance with a purpose of the illustrated embodiments, it is to be understood that certain types of HTTP request flooding permute the parameters of the requested resource continuously with random values, which often evades simple request filtering. To obviate this occurrence, the method and system of the illustrated embodiments preferably maintains a series of recent, overlapping cardinalities of different specific or combined attributes of recently received packets present in a network data traffic stream. This series of cardinalities is utilized to represent a profile of the recently received network traffic.

In a further aspect of the illustrated embodiments, discussed is a computer method and system for detecting a DoS attack by detecting changes in recent cardinality values associated with captured network traffic flow. Packet traffic flows are intercepted/captured from one or more external devices (via one or more networks) such that a cardinality estimation is performed on the received packet traffic flow. A series of cardinalities is maintained for prior packet traffic flows. Changes in cardinalities associated with prior packet traffic flows are detected when compared to cardinalities of a current packet traffic flow. An alert condition for the network traffic flow is generated regarding a suspected denial of service attack based upon the detected changes in cardinalities regarding comparison of the cardinalities associated with prior packet traffic flows compared to cardinalities of a current packet traffic flow.

