Methods and system for simultaneous multiple rules checking

• US 8,566,444 B1
• Filed: 10/30/2008
• Issued: 10/22/2013
• Est. Priority Date: 10/30/2008
• Status: Active Grant

• Current Assignee: F5 Networks, Inc. (F5 Incorporated)
• Original Assignee: F5 Networks, Inc. (F5 Incorporated)
• Inventors: Yona, Shlomo
• Primary Examiner(s): Pwu, Jeffrey
• Assistant Examiner(s): Woldemariam, Nega
• Application Number:
  US12/261,714
• Time in Patent Office: 1,818 Days
• Field of Search: 726/9, 726/26, 726/27, 726/28, 726/29, 713/224, 713/201, 713/212, 713/213, 713/220, 713/223, 709/204, 709/201, 709/220, 709/227, 707/600, 707/607, 707/608, 707/609, 707/687, 707/821, 380/200, 380/201, 380/202, 380/293, 380/227
• US Class Current: 709/225
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/2483 involving identification of individual flows
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: H04L 63/1441 Countermeasures against malicious traffic countermeasures against attacks on cryptographic mechanisms H04L9/002
• CPC Class Codes: H04L 67/564 Enhancement of application control based on intercepted application data

Abstract

A method and system for checking data against a plurality of rules simultaneously. A data string having keywords in the data string is received. All of the keywords in the data string are simultaneously examined against rule keywords using for example, a finite state machine constructed by the Aho-Corasick algorithm. The rule keyword represents at least one rule of the plurality of rules. It is determined which of the plurality of rules are satisfied by the data string based on whether each keyword matches the rule keywords. Such rules may be used for application such as negative security policies.

Claims

1. A method for filtering network packets, the method comprising:

receiving, with the network traffic appliance, a data string associated with one or more of the network packets and identifying one or more keywords in the data string;

iteratively examining, with the network traffic appliance, the one or more keywords in the data string against at least one rule keyword associated with each of a plurality of rules to determine whether the one or more keywords matches at least a portion of the at least one rule keyword for each of the plurality of rules, wherein each of the plurality of rules represents one or more network access policies;

updating, with the network traffic appliance, a counter associated with each of the plurality of rules for each of the one or more keywords that matches the at least a portion of the at least one rule keyword associated with each of the plurality of rules;

determining, with a network traffic appliance, whether the updated counter associated with each of the plurality of rules is equal to a preset matched keyword value for each of the plurality of rules;

writing, with the network traffic appliance, one or more of the plurality of rules into a list of satisfied rules associated with the data string when it is determined that the updated counter associated with the one or more of the plurality of rules is equal to the preset matched keyword value for the one or more of the plurality of rules; and

determining, with the network traffic appliance, whether to grant access of the one or more network packets to at least one server based on the list of satisfied rules.

2. The method of claim 1, wherein the examination is performed by a finite state machine operational according to an Aho-Corasick algorithm and the data string is either full text, chunked text, or streaming text.

3. The method of claim 1, wherein the keywords are stored as keyword data structures in a keywords array and the rules are stored as rules data structures in a rules array.

4. The method of claim 3, wherein each of the plurality of rules is associated with at least one keyword and the rules data structures each include a counter representing the number of keywords matching the data string, and wherein the rule is satisfied when the counter is equivalent to an expected number of keywords value.

5. The method of claim 3, wherein the keyword data structure and the rules data structure includes a flag indicating a match, the flag having a true value and a false value, the flag being reset by incrementing the true value and the rules data structures and the keyword data structures are reset only when the counter is dirty.

6. The method of claim 3, wherein the rules data structures and the keyword data structures are read only and allow simultaneous access by different threads of keyword matching.

7. The method of claim 1, wherein when a keyword is determined to be matched, the corresponding matching rules are flagged and a second occurrence of the keyword is not checked in future iterations.

8. The method of claim 1, wherein each rule is satisfied when a plurality of keywords match a plurality of keywords associated with the rule and each rule is not satisfied when a plurality of keywords match a plurality of keywords associated with the rule.

9. The method of claim 1, further comprising:

determining, with the network traffic appliance, whether the keyword is a Perl Compatible Regular Expression (PCRE) expression;

buffering, with the network traffic appliance, the keyword when it is determined that the keyword is a PCRE expression; and

proceeding, with the network traffic appliance, with determining which of the plurality of rules are satisfied by the data string based on whether each keyword matches the rule keywords when the PCRE expression is completed.

10. The method of claim 1, wherein the rule keywords include at least one constraint and wherein a corresponding rule is satisfied when the at least one constraint is satisfied.

11. A non-transitory machine readable medium having stored thereon instructions for filtering network packets, comprising machine executable code which when executed by at least one processor, causes the processor to perform steps comprising:

receiving a data string associated with one or more of the network packets and identifying one or more keywords in the data string;

iteratively examining the one or more keywords in the data string against at least one rule keyword associated with each of a plurality of rules to determine whether the one or more keywords matches at least a portion of the at least one rule keyword for each of the plurality of rules, wherein each of the plurality of the rules represents one or more network access policies;

updating a counter associated with each of the plurality of rules for each of the one or more keywords that matches the at least a portion of the at least one rule keyword associated with each of the plurality of rules;

determining whether the updated counter associated with each of the plurality of rules is equal to a preset matched keyword value for each of the plurality of rules;

writing one or more of the plurality of rules into a list of satisfied rules associated with the data string when it is determined that the updated counter associated with the one or more of the plurality of rules is equal to the preset matched keyword value for the one or more of the plurality of rules; and

determining whether to grant access of the one or more network packets to at least one server based on the list of satisfied rules.

12. The machine readable medium of claim 11, wherein the examination is performed by a finite state machine operational according to an Aho-Corasick algorithm and the data string is either full text, chunked text, or streaming text.

13. The machine readable medium in claim 11, wherein the keywords are stored as keyword data structures in a keywords array and the rules are stored as rules data structures in a rules array.

14. The machine readable medium of claim 13, wherein each of the plurality of rules is associated with at least two keywords and the rule data structure includes a counter representing the number of keywords matching the data string, and wherein the rule is satisfied when the counter is equivalent to an expected number of keywords value.

15. The machine readable medium of claim 14, wherein the keyword data structure and the rules data structure includes a flag indicating a match, the flag having a true value and a false value, and wherein the instructions cause the machine to reset the flag by incrementing the true value and the rules data structures and the keyword data structures are reset only when the counter is dirty.

16. The machine readable medium of claim 14, wherein the rules data structures and the keyword data structures are read only and allow simultaneous access by different threads of keyword matching.

17. The machine readable medium in claim 11, wherein when a keyword is determined to be matched, the corresponding matching rules are flagged and a second occurrence of the keyword is not checked in future iterations.

18. The machine readable medium in claim 11, wherein each rule is satisfied when a plurality of keywords match a plurality of keywords associated with the rule and each rule is not satisfied when a plurality of keywords match a plurality of keywords associated with the rule.

19. The machine readable medium in claim 11, wherein the instructions cause the machine to:

determine whether the keyword is a Perl Compatible Regular Expression (PCRE) expression;

buffer the keyword when it is determined that the keyword is a PCRE expression; and

proceed with determining which of the plurality of rules are satisfied by the data string based on whether each keyword matches the rule keywords when the PCRE expression is completed.

20. The machine readable medium in claim 11, wherein the rule keywords include at least one constraint and wherein a corresponding rule is satisfied when the at least one constraint is satisfied.

21. A network traffic appliance for filtering network packets, the network traffic appliance comprising:

one or more processors and a network interface, at least one of the processors or the network interface configured to be capable of executing instructions to implement;

receiving a data string associated with one or more of the network packets and identifying one or more keywords in the data string;

iteratively examining the one or more keywords in the data string against at least one rule keyword associated with each of a plurality of rules to determine whether the one or more keywords matches at least a portion of the at least one rule keyword for each of the plurality of rules, wherein each of the plurality of the rules represents one or more network access policies;

updating a counter associated with each of the plurality of rules for each of the one or more keywords that matches the at least a portion of the at least one rule keyword associated with each of the plurality of rules;

determining whether the updated counter associated with each of the plurality of rules is equal to a preset matched keyword value for each of the plurality of rules;

writing one or more of the plurality of rules into a list of satisfied rules associated with the data string when it is determined that the updated counter associated with the one or more of the plurality of rules is equal to the preset matched keyword value for the one or more of the plurality of rules; and

determining whether to grant access of the one or more network packets to at least one server based on the list of satisfied rules.

22. The network traffic appliance in claim 21, wherein the examination is performed by a finite state machine operational according to an Aho-Corasick algorithm and the data string is either full text, chunked text, or streaming text.

23. The network traffic appliance in claim 21, wherein the keywords are stored as keyword data structures in a keywords array and the rules are stored as rules data structures in a rules array.

24. The network traffic appliance in claim 23, wherein each of the plurality of rules is associated with at least two keywords and the rule data structure includes a counter representing the number of keywords matching the data string, and wherein the rule is satisfied when the counter is equivalent to an expected number of keywords value.

25. The network traffic appliance in claim 24, wherein the keyword data structure and the rules data structure includes a flag indicating a match, the flag having a true value and a false value, and wherein the instructions cause the machine to reset the flag by incrementing the true value and the rules data structures and the keyword data structures are reset only when the counter is dirty.

26. The network traffic appliance in claim 24, wherein the rules data structures and the keyword data structures are read only and allow simultaneous access by different threads of keyword matching.

27. The network traffic appliance in claim 21, wherein when a keyword is determined to be matched, the corresponding matching rules are flagged and a second occurrence of the keyword is not checked in future iterations.

28. The network traffic appliance in claim 21, wherein each rule is satisfied when a plurality of keywords match a plurality of keywords associated with the rule and each rule is not satisfied when a plurality of keywords match a plurality of keywords associated with the rule.

29. The network traffic appliance in claim 21, wherein the instructions cause the machine to:

determine whether the keyword is a Perl Compatible Regular Expression (PCRE) expression;

buffer the keyword when it is determined that the keyword is a PCRE expression; and

proceed with determining which of the plurality of rules are satisfied by the data string based on whether each keyword matches the rule keywords when the PCRE expression is completed.

30. The network traffic appliance in claim 21, wherein the rule keywords include at least one constraint and wherein a corresponding rule is satisfied when the at least one constraint is satisfied.