System and method for mining execution traces with finite automata

• US 7,072,876 B1
• Filed: 09/19/2001
• Issued: 07/04/2006
• Est. Priority Date: 09/19/2000
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Cigital
• Inventors: Michael, Christoph Cornelius
• Primary Examiner(s): Hirl, Joseph P.
• Application Number:
  US09/955,165
• Time in Patent Office: 1,749 Days
• Field of Search: 706/45, 706/14, 706/12, 717/135
• US Class Current: 706/45
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

A system and method by which novel, malicious execution traces may be detected by applying a combination of finite automation and heuristic analysis techniques. Such execution traces may be obtained by instrumenting system-level operating system calls, as well as by other techniques, such as, but not limited to, reading error log files, such as Windows NT event logs. With proper instrumentation, known good and known malicious programs may be run and their execution traces monitored. From such monitoring, a model may be derived, which can indicate those execution traces typically associated with malicious software. With this information, novel malicious programs which invoke execution traces similar to known malicious traces may be detected, and such programs may be stopped before significant damage can occur.

Claims

1. A computerized method for detecting anomalous behavior in an executing software program, said method comprising the steps of:

generating a normal execution trace for the software program;

applying a learning algorithm to the normal execution trace to build a finite automaton;

applying an examination algorithm to the finite automaton to identify undesirable transition states in the finite automaton and to create a labeled finite automation; and

applying the labeled finite automaton to an execution trace associated with the executing software program to identify undesirable behavior.

2. The method of claim 1, wherein application of the learning algorithm occurs during a first learning, phase and application of the examination algorithm occurs during a second, examination phase and the learning phase occurs before and independently from the examination phase.

3. The method of claim 1, wherein application of the labeled finite automaton to the execution trace is performed to identify undesirable behavior in a execution trace.

4. The method of claim 3, wherein the undesirable behavior comprises the undesirable transition.

5. The method of claim 1, wherein the finite automaton comprises a tuple.

6. The method of claim 5, wherein the tuple comprises a set of possible states, a set of symbols comprising the input alphabet, a mapping function, a start state, and a set of final states.

7. The method of claim 5, wherein the tuple comprises a set of states interconnected by labeled transitions.

8. The method of claim 1, wherein the finite automaton comprises a prefix tree.

9. The method of claim 8, wherein the prefix tree comprises a plurality of nodes.

10. The method of claim 9, wherein the plurality of the nodes of the prefix tree correspond to states of the finite automaton.

11. The method of claim 10, wherein one of the plurality of nodes comprises a root node, with the root node serving as a start state.

12. The method of claim 11, wherein a remainder of the plurality of nodes comprise accepting states.

13. The method of claim 9, wherein the learning algorithm selectively merges nodes in the finite automaton.

14. The method of claim 1, wherein the learning algorithm comprises a state merging algorithm.

15. The method of claim 1, further comprising flagging the execution trace associated with the executing software program as malicious if the execution trace associated with the executing software program is rejected by the finite automaton.

16. The method of claim 1, wherein the execution trace associated with the executing software program is rejected if it does not end in an accepting state.

17. The method of claim 1, wherein the undesirable behavior comprises at least one of providing an undesired method of entry into the system to unauthorized users, damaging system resources, and elevating user privileges.

18. The method of claim 1, wherein the finite automaton is built using empirical data.

19. The method of claim 1, wherein the method is performed by monitoring processes at a system level.