Pattern matching using embedded functions

• US 7,861,304 B1
• Filed: 05/07/2004
• Issued: 12/28/2010
• Est. Priority Date: 05/07/2004
• Status: Active Grant

• Current Assignee: NortonLifeLock Inc.
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Weinstein, Alex, Nachenberg, Carey
• Primary Examiner(s): PATEL, NIRAV B
• Application Number:
  US10/841,376
• Time in Patent Office: 2,426 Days
• Field of Search: 726 22- 25, 726 11- 13, 713/151, 713/152, 713187-189, 713/193, 713/154, 380/1, 717124-161, 706/48, 712/300, 707/6, 707/705, 707687-704, 707/758, 707/797, 707/803, 707/809, 707/922
• US Class Current: 726/24
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 21/564 by virus signature recognition

Abstract

Methods, apparati, and computer-readable media for matching patterns of symbols within computer systems. A method embodiment of the present invention comprises composing (11) a pattern matching expression; and embedding (12) a function using storage means within the expression to form a character matching string. The expression may be a regular expression. The character matching string is compared (13) against a target string. The target string may be one that is suspected to contain malicious computer code.

Claims

1. A computer-implemented method for composing a character matching string for use in detecting malicious computer code within a computer system, said method comprising the steps of:

using a computer to perform steps comprising;

composing a pattern matching expression formed of a symbol string, wherein the pattern matching expression is representable by a deterministic finite state automaton having only a single state at each point in time;

embedding a function within the symbol string of the pattern matching expression to form the character matching string, wherein the function is described by a second symbol string bounded by designated symbols, the function accesses state memory storing values used by the function to perform algorithmic processing of a target string, the function expands the pattern matching expression into an expanded pattern matching expression not representable by a deterministic finite state automaton, and the function provides one or more abilities from the set of abilities consisting of;

a) moving around a packet or stream to scan at arbitrary locations, b) performing arbitrary mathematical calculations based on data found within the packet or stream, c) fetching, decoding, and/or evaluating binary-encoded values in the stream, and d) performing algorithmic analysis of the packet or stream; and

providing the character matching string to the computer system, wherein the computer system is adapted to use the expanded pattern matching expression and execute the function to compare the character matching string against the target string and declare a suspicion that the target string contains malicious computer code responsive to a match.

3. The method of any of claim 1 or 2, wherein the pattern matching expression is a regular expression.

4. The method of any of claim 1 or 2, wherein:

non-CPU-intensive functions are positioned earlier in the character matching string than CPU-intensive functions or matching primitives.

2. A computer-implemented method for composing a character matching string for use in detecting malicious computer code within a computer system, said method comprising the steps of:

using a computer to perform steps comprising;

composing a pattern matching expression formed of a symbol string, wherein the pattern matching expression is representable by a push-down automaton, wherein the push-down automaton is a state machine that uses a stack to push data onto the stack or to pop data off of the stack;

embedding a function within the symbol string of the pattern matching expression to form the character matching string, wherein the function is described by a second symbol string bounded by designated symbols, the function accesses state memory storing values used by the function to perform algorithmic processing of a target string, the function expands the pattern matching expression into an expanded pattern matching expression not representable by a push-down automaton, and the function provides one or more abilities from the set of abilities consisting of;

a) moving around a packet or stream to scan at arbitrary locations, b) performing arbitrary mathematical calculations based on data found within the packet or stream, c) fetching, decoding, and/or evaluating binary-encoded values in the stream, and d) performing algorithmic analysis of the packet or stream; and

providing the character matching string to the computer system, wherein the computer system is adapted to use the expanded pattern matching expression and execute the function to compare the character matching string against the target string and declare a suspicion that the target string contains malicious computer code responsive to a match.

5. A non-transitory computer-readable storage medium containing executable computer program instructions for composing a character matching string for use in detecting malicious computer code within a computer system, said computer program instructions performing the steps of:

composing a pattern matching expression formed of a symbol string, wherein the pattern matching expression is representable by a deterministic finite state automaton having only a single state at each point in time;

embedding a function within the symbol string of the pattern matching expression to form the character matching string, wherein the function is described by a second symbol string bounded by designated symbols, the function accesses state memory storing values used by the function to perform algorithmic processing of a target string, the function expands the pattern matching expression into an expanded pattern matching expression not representable by a deterministic finite state automaton, and the function provides one or more abilities from the set of abilities consisting of;

a) moving around a packet or stream to scan at arbitrary locations, b) performing arbitrary mathematical calculations based on data found within the packet or stream, c) fetching, decoding, and/or evaluating binary-encoded values in the stream, and d) performing algorithmic analysis of the packet or stream; and

providing the character matching string to the computer system, wherein the computer system is adapted to use the expanded pattern matching expression and execute the function to compare the character matching string against the target string and declare a suspicion that the target string contains malicious computer code responsive to a match.

7. The non-transitory computer-readable storage medium of claim 5 wherein the function seeks forward in the pattern matching expression by a specified number of bytes.

8. The non-transitory computer-readable storage medium of claim 5 wherein the function seeks backward in the pattern matching expression by a specified number of bytes.

9. The non-transitory computer-readable storage medium of claim 5 wherein the function gets a size of a current packet where a scan pointer is positioned, and stores said size in a specified storage means.

10. The non-transitory computer-readable storage medium of claim 5 wherein the function gets a packet or stream offset of a current scan pointer.

11. The non-transitory computer-readable storage medium of claim 5 wherein the function seeks to a specified absolute offset in packet-relative or stream-relative terms.

12. The non-transitory computer-readable storage medium of claim 5 wherein the function gets a Big-Endian or a Little-Endian word at a current scan pointer from a packet or cache, and the function stores the word into a specified storage means.

13. The non-transitory computer-readable storage medium of claim 5 wherein the function is an arithmetic function.

14. The non-transitory computer-readable storage medium of claim 5 wherein the function calls byte code or machine code.

6. A non-transitory computer-readable storage medium containing executable computer program instructions for composing a character matching string for use in detecting malicious computer code within a computer system, said computer program instructions performing the steps of:

composing a pattern matching expression formed of a symbol string, wherein the pattern matching expression is representable by a push-down automaton, wherein the push-down automaton is a state machine that uses a stack to push data onto the stack or to pop data off of the stack;

embedding a function within the symbol string of the pattern matching expression to form the character matching string, wherein the function is described by a second symbol string bounded by designated symbols, the function accesses state memory storing values used by the function to perform algorithmic processing of a target string, the function expands the pattern matching expression into an expanded pattern matching expression not representable by a push-down automaton, and the function provides one or more abilities from the set of abilities consisting of;

a) moving around a packet or stream to scan at arbitrary locations, b) performing arbitrary mathematical calculations based on data found within the packet or stream, c) fetching, decoding, and/or evaluating binary-encoded values in the stream, and d) performing algorithmic analysis of the packet or stream; and

providing the character matching string to the computer system, wherein the computer system is adapted to use the expanded pattern matching expression and execute the function to compare the character matching string against the target string and declare a suspicion that the target string contains malicious computer code responsive to a match.

15. The non-transitory computer-readable storage medium of claim 6, wherein the function seeks forward in the pattern matching expression by a specified number of bytes.

16. The non-transitory computer-readable storage medium of claim 6, wherein the function seeks backward in the pattern matching expression by a specified number of bytes.

17. The non-transitory computer-readable storage medium of claim 6, wherein the function gets a size of a current packet where a scan pointer is positioned, and the function stores said size in a specified storage means.

18. The non-transitory computer-readable storage medium of claim 6, wherein the function gets a packet or stream offset of a current scan pointer.

19. The non-transitory computer-readable storage medium of claim 6, wherein the function seeks to a specified absolute offset in packet-relative or stream-relative terms.