System and method for string filtering

• US 20030033531A1
• Filed: 07/15/2002
• Published: 02/13/2003
• Est. Priority Date: 07/17/2001
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Hanner, Brian D.
• Granted Patent: US 7,366,910 B2
• Time in Patent Office: Days
• US Class Current: 713/176
• 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, the method comprising:

(a) compressing a data string to obtain a data string signature;

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

(c) if the signature is determined to have a match, then 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 character signatures, each character signature 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;

(b) setting the logical value of a first bit of a character signature to logical one if a first bit and a second bit 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 character signature to logical one if a first bit and a second bit 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 character signature to one if a first bit and a second bit 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;

(b) setting the logical value of a first bit of a character signature to logical zero if a first bit and a second bit 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 character signature to logical zero if a first bit and a second bit 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 character signature to logical zero if a first bit and a second bit 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. 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 character signature for each a the plurality of characters in the data string;

(c) concatenating each determined three-bit character signature to create a string signature; and

(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.

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

14. The method of claim 12 wherein the determining the three-bit character signature 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 character signature to one 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 character signature to one 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 character signature to one 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.

15. 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 character signature for the first character in the stream of data,

(c) determining a second character signature for the second character in the stream of data;

(d) concatenating the first character signature with the second character signature; and

(e) comparing the concatenated character signatures to a list of known concatenated character signatures.

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

17. The method of claim 15 further comprising

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

(b) concatenating the second character signature with the third character signature; and

(c) comparing the concatenated character signatures to a list of known concatenated character signatures.

18. The method of claim 16 wherein determining a character signature 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 character signature to logical one if a first bit and a second bit in the data string have different logical values.

19. The method of claim 16 wherein determining a character signature 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 character signature to logical one if a first bit and a second bit in the data string have the same logical values.

20. 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 to obtain a data string signature; and

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

21. The system of claim 20 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 character signature to logical one if a first bit and a second bit in the data string have different logical values.

22. The system of claim 21 wherein the hashing algorithm further comprises setting the logical value of a second bit of the character signature to logical one if a first bit and a second bit in the data string have different logical values.

23. The system of claim 22 wherein the hashing algorithm further comprises setting the logical value of a third bit of the character signature to logical one if a first bit and a second bit in the data string have different logical values.