Hardware assist for pattern matches

• US 20050261877A1
• Filed: 02/02/2004
• Published: 11/24/2005
• Est. Priority Date: 02/02/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Garms, Jason, Shelest, Art
• Granted Patent: US 7,526,804 B2
• Time in Patent Office: Days
• US Class Current: 702/186
• CPC Class Codes: G06F 21/55 Detecting local intrusion or implementing counter-measures
• CPC Class Codes: G06F 21/564 by virus signature recognition
• CPC Class Codes: G06F 21/567 using dedicated hardware

Abstract

An application contacts the ASIC with a request for a job, along with the name or identifier of a data stream to pattern match against, the name or identifier of the pattern set to use, and whether the job is partial or full. Depending on the priority rules set by the ASIC administrator, the ASIC may stop the job it is currently doing and begin work on the new job, or wait until the current job is finished before starting the new job. The ASIC determines if the pattern set for the new job is already stored in the cache, and contacts the calling application if it is not. Once the correct pattern set is loaded, the ASIC begins pattern matching on the requested data stream. The data stream is compared byte by byte with the each of the patterns in the loaded set. The ASIC will return a match to the calling application if a match has been made with one of the patterns in the pattern set.

Claims

1. A method for pattern matching comprising:

receiving a request for a job at a hardware device from an application, the request comprising a pattern set identification and a data stream identification;

locating a pattern set for the received job based on the pattern set identification;

selecting a data stream based on the data stream identification; and

matching the pattern set against the data stream.

2. The method of claim 1, further comprising determining if the received job has a higher priority than a current job.

3. The method of claim 2, wherein the request further comprises an application identification, and wherein determining if the received job has a higher priority than the current job is performed by the hardware device using the application identification.

4. The method of claim 3, wherein the priority of the received job is predetermined.

5. The method of claim 1, wherein the request further comprises an application identification, and wherein locating the pattern set for the received job comprises:

searching for the pattern set in a cache using the pattern set identification and application identification by the hardware device;

requesting the pattern set from the application if the pattern set is not in the cache;

receiving the requested pattern set by the hardware device; and

storing the received pattern set in the cache.

6. The method of claim 1, further comprising loading the pattern set into a processor that is optimized for pattern matching.

7. The method of claim 1, wherein the data stream is selected by the hardware device.

8. The method of claim 1, wherein matching the pattern set against the data stream is performed by a processor at the hardware device.

9. The method of claim 8, further comprising returning the results of the matching to the application, wherein the returned results include at least one match found by the processor.

10. The method of claim 9, wherein at least two of the steps of receiving, locating, selecting, matching, and returning the results are performed in parallel.

11. The method of claim 9, wherein the pattern set includes partial patterns and the application is configured to verify partial matches.

12. The method of claim 8, wherein patterns in the pattern set are matched against the data stream in parallel.

13. The method of claim 1, wherein matching the pattern set against the data stream comprises:

receiving a byte from the data stream;

determining if the byte satisfies a function of a pattern in the pattern set; and

continuing to determine if subsequent received bytes satisfy subsequent functions of the pattern set, until a subsequent received byte does not satisfy a subsequent function of the pattern set, or a partial or complete match is found.

14. A system for pattern matching comprising:

a hardware device that receives a request for a job from an application, the request comprising a pattern set identification and a data stream identification, locates a pattern set for the received job based on the pattern set identification, selects a data stream based on the data stream identification, and matches the pattern set against the data stream.

15. The system of claim 14, wherein the hardware device determines if the received job has a higher priority than a current job.

16. The system of claim 15, wherein the request further comprises an application identification, and wherein determining if the received job has a higher priority than the current job is performed by the hardware device using the application identification.

17. The system of claim 16, wherein the priority of the received job is predetermined.

18. The system of claim 14, wherein the request further comprises an application identification, and wherein the hardware device locates the pattern set for the received job by:

searching for the pattern set in a cache using the pattern set identification and application identification by the hardware device;

requesting the pattern set from the application if the pattern set is not in the cache;

receiving the requested pattern set by the hardware device; and

storing the received pattern set in the cache.

19. The system of claim 14, wherein the hardware device loads the pattern set into a processor that is optimized for pattern matching.

20. The system of claim 14, wherein the hardware device selects the data stream.

21. The system of claim 14, wherein the hardware device matches the pattern set against the data stream using a processor.

22. The system of claim 21, wherein the hardware device returns the results of the matching to the application, wherein the returned results include at least one match found by the processor.

23. The system of claim 21, wherein patterns in the pattern set are matched against the data stream by the processor in parallel.

24. The system of claim 21, wherein multiple pattern sets are matched against the data stream by the processor in parallel.

25. The system of claim 22, wherein the pattern set includes partial patterns, and the application is configured to verify partial matches.

26. The system of claim 14, wherein the hardware matches the pattern set against the data stream by:

receiving a byte from the data stream;

determining if the byte satisfies a first finction of a pattern in the pattern set; and

continuing to determine if subsequent received bytes satisfy subsequent functions of the first pattern set, until a subsequent received byte does not satisfy a subsequent function of the pattern set, or a partial or complete match is found.

27. The system of claim 14, wherein the hardware device is an application specific integrated circuit.

28. The system of claim 27, wherein the hardware device is part of a network interface device.

29. The system of claim 27, wherein the hardware device is part of a motherboard.

30. A computer-readable medium having stored thereon computer-executable instructions for performing a method of pattern matching, the method comprising:

receiving a request for a job at a hardware device from an application, the request comprising a pattern set identification and a data stream identification;

locating a pattern set for the received job based on the pattern set identification;

selecting a data stream based on the data stream identification; and

matching the pattern set against the data stream.

31. The computer-readable medium of claim 30, further comprising computer executable instructions for determining if the received job has a higher priority than a current job.

32. The computer-readable medium of claim 30, wherein the request further comprises an application identification, and wherein determining if the received job has a higher priority than the current job is performed by the hardware device using the application identification.

33. The computer-readable medium of claim 30, wherein the request further comprises an application identification, and wherein locating the pattern set for the received job comprises computer-executable instructions for:

searching for the pattern set in a cache using the pattern set identification and application identification by the hardware device;

requesting the pattern set from the application if the pattern set is not in the cache;

receiving the requested pattern set by the hardware device; and

storing the received pattern set in the cache.

34. The computer-readable medium of claim 30, wherein matching the pattern set against the data stream comprises computer-executable instructions for:

receiving a byte from the data stream;

determining if the byte satisfies a function of a pattern in the pattern set; and

continuing to determine if subsequent received bytes satisfy subsequent finctions of the pattern set, until a subsequent received byte does not satisfy a subsequent finction of the pattern set, or a partial or complete match is found.

35. A hardware device comprising:

a processor specialized for matching pattern sets against a data stream, receiving a job request, determining the priority of a job, selecting the data stream, and a returning a result;

a queue specialized for storing and retrieving the job request; and

a cache specialized for storing at least one pattern set, and retrieving a pattern set.

36. The hardware device of claim 35, wherein the processor matches pattern sets against the data stream by:

receiving a first byte from the data stream;

determining if the first byte satisfies a first function of a first pattern in the pattern set; and

continuing to determine if subsequent received bytes satisfy subsequent functions of the first pattern set, until a subsequent received byte does not satisfy a subsequent function of the first pattern set, or a partial or complete match is found.

37. The hardware device of claim 35, wherein the processor, queue, and cache are comprised within an application specific integrated circuit.

38. The hardware device of claim 37, wherein the application specific integrated circuit is comprised within a network interface device.