Granted Patent B1

US 7,203,963 · App. 10/172,740 · Granted Apr 10, 2007

Abstract

Claims (65)

1. A computer implemented method of adaptively classifying information using a binary tree, comprising:

establishing a binary tree including a set of binary sequences, each binary sequence of said set of binary sequences representing one or more network addresses;

receiving network traffic having identifiers describing network traffic sources;

correlating said identifiers to binary sequences within said binary tree;

forming a revision metric based upon said correlating; and

revising said binary tree according to said revision metric;

wherein said revising includes updating a particular binary sequence of said set of binary sequences so as to reduce the number of network addresses represented;

wherein said updating includes determining said revision metric based upon the percentage of said network traffic having said identifiers correlating to said particular binary sequence, and based upon the number of network addresses within said one or more network addresses, said updating further including lengthening said particular binary sequence according to an evaluation of said revision metric.

2. The computer implemented method of claim 1 wherein said establishing includes establishing binary sequences each having a long term count value for noting an amount of said network traffic received from said one or more network addresses and a short term count value for updating said long term count value, and wherein said correlating includes incrementing said short term count value and periodically incorporating said short term count value into said long term count value.

3. The computer implemented method of claim 1 wherein said revising includes revising said set of binary sequences so as to correlate a greater number of said identifiers to a smaller number of said network addresses.

4. The computer implemented method of claim 1 further including the step of blocking said network traffic upon correlating said identifiers to selected binary sequences within said binary tree.

5. The computer implemented method of claim 4 wherein said receiving includes receiving malicious network traffic involved in a distributed denial of service attack and benign network traffic not involved in a distributed denial of service attack, and wherein said blocking includes identifying selected binary sequences for blocking a large amount of said malicious network traffic while blocking a small amount of said benign network traffic.

6. The computer implemented method of claim 4 wherein said correlating includes correlating said identifiers so as to produce identified network traffic, and said blocking includes blocking said identified network traffic according to the rate at which said identified network traffic is received.

7. The computer implemented method of claim 6 wherein said blocking includes blocking said identified network traffic according to a token bucket rate limiting scheme.

8. The computer implemented method of claim 6 wherein said blocking includes blocking said identified network traffic according to a dual token bucket rate limiting scheme.

9. A computer implemented method of blocking a distributed denial of service attack, comprising:

establishing a binary tree including a set of binary sequences, each binary sequence of said set of binary sequences representing one or more network addresses;

receiving network traffic having identifiers describing network traffic sources;

correlating said identifiers to binary sequences within said binary tree;

receiving a distributed denial of service attack notification signal;

identifying a selected binary tree path within said binary tree, said identifying including identifying said selected binary tree path as a low cost blocking path within said binary tree;

blocking network traffic correlated to a binary sequence corresponding to said selected binary tree path; and

dynamically revising said set of binary sequences to reflect changes in said network traffic;

wherein said dynamically revising includes updating a particular binary sequence of said set of binary sequences so as to increase the number of said network addresses represented;

wherein said updating includes determining a revision metric based upon the percentage of said network traffic having said identifiers correlating to said particular binary sequence, and based upon the number of network addresses within said one or more network addresses, said updating further including shortening said particular binary sequence according to an evaluation of said revision metric.

10. A computer implemented method of blocking a distributed denial of service attack, comprising:

establishing a binary tree including a set of binary sequences, each binary sequence of said set of binary sequences representing one or more network addresses;

receiving network traffic having identifiers describing network traffic sources;

correlating said identifiers to binary sequences within said binary tree;

receiving a distributed denial of service attack notification signal;

identifying a selected binary tree path within said binary tree, said identifying including identifying said selected binary tree path as a low cost blocking path within said binary tree;

blocking network traffic correlated to a binary sequence corresponding to said selected binary tree path; and

dynamically revising said set of binary sequences to reflect changes in said network traffic;

wherein said dynamically revising includes updating a particular binary sequence of said set of binary sequences so as to reduce the number of network addresses represented;

wherein said updating includes determining a revision metric based upon the percentage of said network traffic having said identifiers correlating to said particular binary sequence, and based upon the number of network addresses within said one or more network addresses, said updating further including lengthening said particular binary sequence according to an evaluation of said revision metric.

11. The computer implemented method of claim 9 wherein said blocking includes discarding said network traffic based upon the result of said correlating.

12. A computer readable memory that can direct a computer to function in a specified manner, comprising:

instructions to establish a binary tree including a set of binary sequences, each binary sequence of said set of binary sequences representing one or more network addresses;

instructions to receive network traffic having identifiers describing network traffic sources;

instructions to correlate said identifiers to binary sequences within said binary tree;

instructions to form a revision metric based upon said correlating; and

instructions to revise said binary tree according to said revision metric;

wherein said instructions to revise include instructions to update a particular binary sequence of said set of binary sequences so as to increase the number of said network addresses represented;

wherein said instructions to update include instructions to determine said revision metric based upon the percentage of said network traffic having said identifiers correlating to said particular binary sequence, and based upon the number of network addresses within said one or more network addresses, said instructions to update further including instructions to shorten said particular binary sequence according to an evaluation of said revision metric.

13. The computer readable memory of claim 12 wherein said instructions to establish include instructions to establish binary sequences each having a long term count value for noting an amount of said network traffic received from said one or more network addresses and a short term count value for updating said long term count value, and wherein said instructions to correlate include instructions to increment said short term count value and instructions to periodically incorporate said short term count value into said long term count value.

14. The computer readable memory of claim 12 wherein said instructions to revise include instructions to revise said set of binary sequences so as to correlate a greater number of said identifiers to a smaller number of said network addresses.

15. The computer readable memory of claim 12 further including instructions to block said network traffic upon correlating said identifiers to selected binary sequences within said binary tree.

16. The computer readable memory of claim 15 wherein said instructions to receive include instructions to receive malicious network traffic involved in a distributed denial of service attack and benign network traffic not involved in a distributed denial of service attack, and wherein said instructions to block include instructions to identify selected binary sequences for blocking a large amount of said malicious network traffic while blocking a small amount of said benign network traffic.

17. The computer readable memory of claim 15 wherein said instructions to correlate include instructions to correlate said identifiers so as to produce identified network traffic, and said instructions to block include instructions to block said identified network traffic according to the rate at which said identified network traffic is received.

18. The computer readable memory of claim 17 wherein said instructions to block include instructions to block said identified network traffic according to a token bucket rate limiting scheme.

19. The computer readable memory of claim 17 wherein said instructions to block include instructions to block said identified network traffic according to a dual token bucket rate limiting scheme.

20. A computer implemented method of classifying information utilizing a binary tree for identifying a distributed denial of service attack, comprising:

establishing a binary tree including a set of binary sequences, each binary sequence of said set of binary sequences representing one or more network addresses;

receiving network traffic;

identifying a distributed denial of service attack associated with said network traffic utilizing said binary tree; and

dynamically revising said set of binary sequences to reflect changes in said network traffic;

wherein said dynamically revising includes updating a particular binary sequence of said set of binary sequences so as to increase the number of said network addresses represented;

wherein said updating includes determining a revision metric based upon the percentage of said network traffic having identifiers correlating to said particular binary sequence, and based upon the number of network addresses within said one or more network addresses, said updating further including shortening said particular binary sequence according to an evaluation of said revision metric.

21. A computer program product embodied on a computer readable medium for classifying information utilizing a binary tree for identifying a distributed denial of service attack, comprising:

computer code of establishing a binary tree including a set of binary sequences, each binary sequence of said set of binary sequences representing one or more network addresses;

computer code for receiving network traffic;

computer code for identifying a distributed denial of service attack associated with said network traffic utilizing said binary tree; and

computer code for dynamically revising said set of binary sequences to reflect changes in said network traffic;

wherein said dynamically revising includes updating a particular binary sequence of said set of binary sequences so as to reduce the number of network addresses represented;

wherein said updating includes determining a revision metric based upon the percentage of said network traffic having identifiers correlating to said particular binary sequence, and based upon the number of network addresses within said one or more network addresses, said updating further including lengthening said particular binary sequence according to an evaluation of said revision metric.

Assignments (9)