System and method for string filtering

• US 7,366,910 B2
• Filed: 07/15/2002
• Issued: 04/29/2008
• Est. Priority Date: 07/17/2001
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Hanner, Brian D.
• Primary Examiner(s): REVAK, CHRISTOPHER A
• Application Number:
  US10/196,509
• Publication Number:
  US 20030033531A1
• Time in Patent Office: 2,115 Days
• Field of Search: 726/13, 726 22- 24
• US Class Current: 713/179
• CPC Class Codes: H04L 63/12 Applying verification of the received information cryptographic mechanisms or cryptographic arrangements for data integrity or data verification H04L9/32
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC

Abstract

A computer-based method for scanning data using string filtering includes compressing a data string using a hashing algorithm to obtain a data-string signature, and then determining that the data-string signature matches a known data-string signatures stored in a lookup table if the signature is determined to have a match in the lookup table.

Claims

1. A computer-based method for scanning data for one or more known data strings, the method comprising:

(a) compressing a data string comprised of a plurality of characters to obtain a data string signature wherein compressing the data string comprises compressing each character in a manner independent of other characters in the data string and concatenating the compressed representations of each character;

(b) determining if the data-string signature matches a stored string signature; and

(c) if the signature is determined to have a match, then marking the data string with an indicator identifying the data string as a known data string.

2. The method of claim 1 wherein the data string is an eight-character data string, each character comprising eight bits.

3. The method of claim 1 wherein the data-string signature is a series of hash codes, each hash code comprising a three-bit representation of each character.

4. The method of claim 1 further comprising storing known data strings in a lookup table.

5. The method of claim 1 wherein the data is compressed using a hashing algorithm, the hashing algorithm comprising:

(a) receiving a character of the data string, the character comprising a plurality of bits, each bit having a logical value of one or zero; and

(b) setting the logical value of a first bit of a hash code to logical one only if a first pair of bits in the data string have different logical values.

6. The method of claim 5 wherein the hashing algorithm further comprises setting the logical value of a second bit of the hash code to logical one only if a second pair of bits in the data string have different logical values.

7. The method of claim 6 wherein the hashing algorithm further comprises setting the logical value of a third bit of the hash code to one only if a third pair of bits in the data string have different logical values.

8. The method of claim 1 wherein the data is compressed using a hashing algorithm, the hashing algorithm comprising:

(a) receiving a character of the data string, the character comprising a plurality of bits, each bit having a logical value of one or zero; and

(b) setting the logical value of a first bit of a hash code to logical zero only if a first pair of bits in the data string have different logical values.

9. The method of claim 8 wherein the hashing algorithm further comprises setting the logical value of a second bit of the hash code to logical zero only if a second pair of bits in the data string have different logical values.

10. The method of claim 9 wherein the hashing algorithm further comprises setting the logical value of a third bit of the hash code to logical zero only if a third pair of bits in the data string have different logical values.

11. The method of claim 1 further comprising sending data strings identified as known data-strings to be filtered.

12. The method of claim 1 further comprising providing the data string marked as a known data string to a filtering operation.

13. The method of claim 12 further comprising, if the data string is determined not to contain a known data string and if the data string includes a final character of data, then marking the data string with an indicator identifying the data string to be discarded from further filtering.

14. A computer-based method for scanning data for known strings of data, the method comprising:

(a) receiving a stream of data strings, each data string comprising a plurality of eight-bit characters;

(b) determining a three-bit hash code for each of the plurality of characters in the data string with the determination of the hash code for each character being independent of other characters in the data string;

(c) concatenating each determined three-bit hash code to create a string signature;

(d) determining that a data string contains a known data string if the string signature matches a string signature in a predetermined list of string signatures; and

(e) if the data string is determined to contain a known data string, then marking the data string with an indicator identifying the data string as a known data string.

15. The method of claim 14 further comprising sending known data strings identified by comparison to the list of data string signatures for filtering.

16. The method of claim 14 wherein the determining the three-bit hash code comprises:

(a) receiving a character of the data string, each character bit having a logical value of one or zero;

(b) setting the logical value of a first bit of a hash code to one only if the first received bit and the fourth received bit in the data string have different logical values;

(c) setting the logical value of a second bit of the hash code to one only if the second received bit and the fifth received bit in the data string have different logical values;

(d) setting the logical value of a third bit of the hash code to one only if the third received bit and the seventh received bit in the data string have different logical values; and

(e) repeating steps (a) through (c) for all characters in the data string.

17. The method of claim 14 further comprising providing the data string marked as a known data string to a filtering operation.

18. The method of claim 17 further comprising, if the data string is determined not to contain a known data string and if the data string includes a final character from the stream, then marking the data string with an indicator identifying the data string to be discarded from further filtering.

19. A computer-based method of scanning data for known strings of data, the method comprising:

(a) receiving a stream of data strings at a filter, the stream of data comprising a plurality of characters;

(b) determining a first hash code for the first character in the stream of data,

(c) determining a second hash code for the second character in the stream of data in a manner independent of the first character;

(d) concatenating the first hash code with the second hash code;

(e) comparing the concatenated hash codes to a list of known concatenated hash codes; and

(f) if the concatenated hash codes match known concatenated hash codes, then marking the data string with an indicator identifying the data string as a known string of data.

20. The method of claim 19 wherein each character comprises a plurality of bits set to a logical one or a logical zero.

21. The method of claim 20 wherein determining a hash code comprises:

(a) receiving a character of the data string, each character bit having a logical value of one or zero; and

(b) setting the logical value of a first bit of a hash code to logical one only if a first pair of bits in the data string have different logical values.

22. The method of claim 21 wherein determining a hash code comprises:

(a) receiving a character of the data string, each character bit having a logical value of one or zero; and

(b) setting the logical value of a second bit of a hash code to logical one only if a second pair of bits in the data string have the same logical values.

23. The method of claim 22 wherein determining a hash code comprises:

(a) receiving a character of the data string, each character bit having a logical value of one or zero; and

(b) setting the logical value of a third bit of a hash code to logical one only if a third pair of bits in the data string have the same logical values.

24. The method of claim 19 further comprising

(a) determining a third hash code for the third character in the stream of data;

(b) concatenating the second hash code with the third hash code; and

(c) comparing the concatenated hash codes to a list of known concatenated hash codes.

25. The method of claim 19 further comprising providing the data string marked as a known data string to a filtering operation.

26. The method of claim 25 further comprising, if the data string is determined not to contain a known data string and if the data string includes a final character from the stream, then marking the data string with an indicator identifying the data string to be discarded from further filtering.

27. A system for scanning data for known strings of data, the system comprising:

(a) a lookup table in a memory operable to store known data-string signatures; and

(b) a string-filtering unit connected to a network and coupled to the memory, the string filtering unit operable to;

(i) compress a data string comprised of a plurality of characters to obtain a data string signature;

(ii) determine if the data string signature matches a known data-string signatures in the lookup table; and

(iii) if the data string signature is determined to match a known data-string signature, then marking the data string with an indicator identifying the data string as a known string of data,

wherein the string-filtering unit is operable to compress the data string by compressing each character in a manner independent of other characters in the data string and concatenating the compressed representations of each character.

28. The system of claim 27 wherein the data string is compressed with a hashing algorithm, the hashing algorithm comprising:

(a) receiving a data string as an eight bit string of data, each bit having a logical value of one or zero;

(b) setting the logical value of a first bit of a hash code to logical one only if a first pair of bits in the data string have different logical values.

29. The system of claim 28 wherein the hashing algorithm further comprises setting the logical value of a second bit of the hash code to logical one only if a second pair of bits in the data string have different logical values.

30. The system of claim 29 wherein the hashing algorithm further comprises setting the logical value of a third bit of the hash code to logical one only if a third pair of bits in the data string have different logical values.

31. The system of claim 27 wherein the string-filtering unit is further operable to provide the data string marked as a known data string to a filtering operation.

32. The system of claim 31 wherein the string-filtering unit is further operable, if the data string is determined not to contain a known data string and if the data string includes a final character of data, to then mark the data string with an indicator identifying the data string to be discarded from further filtering.