Hardware assist for pattern matches

• US 7,526,804 B2
• Filed: 02/02/2004
• Issued: 04/28/2009
• Est. Priority Date: 02/02/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Garms, Jason, Shelest, Art
• Primary Examiner(s): Zand; Kambiz
• Assistant Examiner(s): Hailu; Teshome
• Application Number:
  US10/770,329
• Publication Number:
  US 20050261877A1
• Time in Patent Office: 1,912 Days
• Field of Search: 726/22, 726/23, 726/24, 726/25, 713/187, 713/188
• US Class Current: 726/22
• 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 Application Specific Integrated Circuit (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 application being instantiated on a processor of a computing device and the hardware device comprising an ASIC (Application Specific Integrated Circuit) card mounted to the computing device and communicatively coupled to the processor of the computing device, 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;

receiving the selected data stream at the ASIC card; and

matching the pattern set against the data stream at the ASIC card.

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 computing device having:

a processor upon which is instantiated an application; and

a hardware device that receives a request for a job from the application, the hardware device comprising an ASIC (Application Specific Integrated Circuit) card mounted to the computing device and communicatively coupled to the processor of the computing device, the request comprising a pattern set identification and a data stream identification, where the hardware device locates a pattern set for the received job based on the pattern set identification, selects a data stream based on the data stream identification, receives the selected data stream at the ASIC card, and matches the pattern set against the data stream at the ASIC card.

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 function 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 application being instantiated on a processor of a computing device, the hardware device comprising an ASIC (Application Specific Integrated Circuit) card mounted to the computing device and communicatively coupled to the processor of the computing device, 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;

receiving the selected data stream at the ASIC card; and

matching the pattern set against the data stream at the ASIC card,

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.

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

34. A hardware device comprising an ASIC (Application Specific Integrated Circuit) card for being mounted to the a computing device and communicatively coupled to a processor of the computing device, the ASIC card comprising:

a processor separate from the processor of the computing device, the processor of the ASIC card specialized for matching pattern sets against a data stream, receiving a job request, determining the priority of a job, selecting the data stream, and 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.

35. The hardware device of claim 34, 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.

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

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