US5278901A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Pattern-oriented intrusion-detection system and method
Assignee: International Business Machines Corp
•
Filing: 1992-04-30
•
Granted: 1994-01-11
•
Expires: 2012-04-30
Abstract
Abstract The present invention provides a pattern-oriented intrusion detection system and method that defines patterns of intrusion based on object privilege and information flow in secure computer systems to detect actual intrusion occurrences. This approach has the advantage of detecting context-dependent intrusions such as those caused by inadvertent execution of foreign programs containing viruses or Trojan Horses and also those caused by unintended use of foreign input data. The present invention can track both information and privilege flows within a system, and has the ability to uniformly define various types of intrusion patterns. Operational security problems can lead to intrusion in secure computer systems. With this approach, explicitly defined types of intrusion patterns due to operational security problems can be detected.
Inventors
- 👤 Shiuh-Pyung W. Shieh
- 👤 Virgil D. Gligor
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 09:30
CPC Classifications
G; G06; G06F; G06F21/00; G06F21/50; G06F21/55; G06F21/552
Claims Analysis
Total Claims: 53
Claim 1
Independent Claim
128 words
A method for detecting intrusion patterns in a secure computer system having a Central Processing Unit and a data storage memory, the method comprising the steps of: (1) performing an access operation on one or more components of the computer system; (2) inputting a first protection graph into an intrusion detection system, said first protection graph including direct and indirect relations between subjects and objects; (3) applying a set of model rules to said first protection graph and said access operation to generate a second protection graph; (4) comparing said second protection graph with a set of intrusion patterns to generate an exception condition, said exception condition indicative of whether there has been an intrusion; and (5) indicating the existence of an intrusion based on said exception condition.
Claim 2
Independent Claim
128 words
A method for detecting intrusion patterns in a secure computer system having a Central Processing Unit and a data storage memory, the method comprising the steps of: (1) performing an access operation on one or more components of the computer system; (2) inputting a first protection graph into an intrusion detection system, said first protection graph including direct and indirect relations between subjects and objects; (3) applying a set of model rules to said first protection graph and said access operation to generate a second protection graph; (4) comparing said second protection graph with a set of intrusion patterns to generate an exception condition, said exception condition indicative of whether there has been an intrusion; and (5) indicating the existence of an intrusion based on said exception condition.
Claim 3
Dependent Claim
51 words
The method of claim 1, wherein said first and second protection graphs are generated by storing access relations in access logging lists (ALLs), wherein said All is associated with either a subject or an object and contains indentities of all other subjects or objects that accessed said associated subject or object.
Claim 4
Dependent Claim
62 words
The method of claim 2, wherein said ALL can be simplified, said simplification comprising the steps of: (a) replacing all subjects in said at least one ALL with said subjects owner's name; (b) removing all entries from said at least one ALL that represent indirectly-written-by relations with other objects; and (c) deleting all redundant past relations from said at least one ALL.
Claim 5
Dependent Claim
30 words
The method of claim 2, wherein said ALL can be simplified by determining whether a first subject in said ALL indirectly reads a second subject or object in said ALL.
Claim 6
Dependent Claim
31 words
The method of claim 2, wherein said ALL can be simplified by determining whether a subject or a first object in said ALL indirectly writes a second object in said ALL.
Claim 7
Dependent Claim
32 words
The method of claim 2, wherein said ALL can be simplified by determining whether a first subject in said ALL is indirectly controlled by a second subject or object in said ALL.
Claim 8
Dependent Claim
30 words
The method of claim 2, wherein said ALL can be simplified by determining whether a first subject or object in said ALL indirectly drives a second subject in said ALL.
Claim 9
Dependent Claim
28 words
The method of claim 2, wherein said ALL can be simplified by determining whether a first object in said ALL indirectly writes a second object in said ALL.
Claim 10
Dependent Claim
26 words
The method of claim 2, wherein said ALL can be simplified by determining whether a subject in said ALL indirectly writes an object in said ALL.
Claim 11
Dependent Claim
33 words
The method of claim 1, further comprising the step of detecting virus propagation by observing indirect write patterns in said second protection graph, wherein said indirect write patterns may appear individually or simultaneously.
Claim 12
Dependent Claim
66 words
The method of claim 1, wherein said first protection graph contains all past direct and indirect relations, and said second protection graph contains all present and past direct and indirect relations, and wherein said step of generating a second protection graph further comprises the step of applying only said model rules to those relations adjacent to said present direct relations to generate said present indirect relations.
Claim 13
Dependent Claim
24 words
The method of claim 1, further comprising the step of delineating a protection set and a core subset from said subjects and said objects.
Claim 14
Dependent Claim
38 words
The method of claim 12, further comprising the step of checking to determine whether said protection set is a virus-free set by determining if any object in said protection set have been written to by other protection sets.
Claim 15
Dependent Claim
37 words
The method of claim 12, further comprising the step of checking to determine whether said protection set is a virus-confinement set by determining if any subjects in said protection set have written objects of other protection sets.
Claim 16
Dependent Claim
56 words
The method of claim 12, wherein said step of generating exception conditions comprises the step of determining if an intrusion has occurred by checking whether any element of said core subset is accessed by a subject or an object outside of its protection set and whether the access violates a given restriction of said core subset.
Claim 17
Dependent Claim
67 words
The method of claim 1, wherein said step of generating a second protection graph comprises the step of providing an indirect read relation in said protection graph between a first subject and a second subject if a direct wrote operation or an indirect wrote operation exists between said first subject and a first object and a read operation exists between said second subject and said first object.
Claim 18
Dependent Claim
60 words
The method of claim 1, wherein said step of generating a second protection graph comprises the step of providing an indirect read relation in said protection graph between a subject and a first object if an indirect wrote operation exists between said first object and a second object and a read operation exists between said subject and said second object.
Claim 19
Dependent Claim
73 words
The method of claim 1, wherein said step of generating a second protection graph comprises the step of providing an indirect write relation in said protection graph between a first object and a second object if a read operation or an indirect read operation or a is-controlled-by operation or a indirectly is-controlled-by operation exists between a subject and said first object and a write operation exists between said subject and said second object.
Claim 20
Dependent Claim
64 words
The method of claim 1, wherein said step of generating a second protection graph comprises the step of providing an indirect write relation in said protection graph between a first object and a subject if an indirect read operation or an indirect is-controlled-by operation exists between said subject and said first object and a write operation exists between said subject and said second object.
Claim 21
Dependent Claim
61 words
The method of claim 1, wherein said step of generating a second protection graph comprises the step of providing an indirect is-controlled-by relation in said protection graph between a first subject and a second subject if a wrote operation or an indirect wrote operation exists between said first subject and an object and said second subject is controlled by said object.
Claim 22
Dependent Claim
57 words
The method of claim 1, wherein said step of generating a second protection graph comprises the step of providing an indirect is-controlled-by relation in said protection graph between a subject and a first object if an indirect wrote operation exists between said first object and a second object and said subject is controlled by said second object.
Claim 23
Dependent Claim
52 words
The method of claim 1, wherein said step of generating a second protection graph comprises the step of providing an indirect drive relation in said protection graph between an object and a first subject if said first subject is-controlled-by or indirectly is-controlled-by said object and said first subject drives said second subject.
Claim 24
Dependent Claim
53 words
The method of claim 1, wherein said step of generating a second protection graph comprises the step of providing an indirect drive relation in said protection graph between a first subject and a second subject if said first subject is indirectly controlled-by a third subject and said third subject drives said second subject.
Claim 25
Dependent Claim
54 words
The method of claim 1, wherein said step of generating a second protection graph comprises the step of providing an indirect drive relation in said protection graph between a first subject and a second subject if said first subject drove or indirectly drove a third subject and said third subject drives said second subject.
Claim 26
Dependent Claim
50 words
The method of claim 1, wherein said step of generating a second protection graph comprises the step of providing an indirect drive relation in said protection graph between an object and a first subject if said object indirectly drove a second subject and said second subject drives said first subject.
Claim 27
Dependent Claim
22 words
The method of claim 1, wherein the first protection graph and said second protection graph are stored in the data storage memory.
Claim 28
Dependent Claim
18 words
The method of claim 1, wherein said set of intrusion patterns are stored in the data storage memory.
Claim 29
Dependent Claim
30 words
The method of claim 1, further comprising the step of analyzing the privilege and data flows captured in said second protection graph to determine which access operation caused said intrusion.
Claim 30
Dependent Claim
138 words
In a secure computer system having a central processing unit and a data storage memory, and intrusion detection system for detecting intrusion patterns and unauthorized access, comprising: (1) means for performing an access operation on one or more components of the computer system; (2) means for inputting a first protection graph into an intrusion detection system, said first protection graph including direct and indirect relations between subjects and objects; (3) means for applying a set of model rules to said first protection graph and said access operation to generate a second protection graph; (4) means for comparing said second protection graph with a set of instruction patterns to generate an exception condition, said exception condition indicative of whether there has been an intrusion; and (5) means for indicating the existence of an intrusion based on said exception condition.
Claim 31
Dependent Claim
138 words
In a secure computer system having a central processing unit and a data storage memory, and intrusion detection system for detecting intrusion patterns and unauthorized access, comprising: (1) means for performing an access operation on one or more components of the computer system; (2) means for inputting a first protection graph into an intrusion detection system, said first protection graph including direct and indirect relations between subjects and objects; (3) means for applying a set of model rules to said first protection graph and said access operation to generate a second protection graph; (4) means for comparing said second protection graph with a set of instruction patterns to generate an exception condition, said exception condition indicative of whether there has been an intrusion; and (5) means for indicating the existence of an intrusion based on said exception condition.
Claim 32
Dependent Claim
50 words
The system of claim 29, wherein said first and second protection graphs are generated by storing access relations in access logging lists (ALLs), said ALL is associated with either a subject or an object and contains identities of all other subjects or object that accessed said associated subject or object.
Claim 33
Dependent Claim
64 words
The system of claim 29, wherein said first protection graph contains all past direct and indirect relations, and said second protection graph contains all present and past direct and indirect relations, and wherein said means for generating a new protection graph comprises means for applying only said model rules to those relations adjacent to said present direct relations to generate said present indirect relations.
Claim 34
Dependent Claim
23 words
The system of claim 29, further comprising means for delineating a protection set and a core subset from said subjects and said objects.
Claim 35
Dependent Claim
53 words
The system of claim 32, further comprising means for generating exception conditions by determining whether an intrusion has occurred by checking whether any element of said core subset is accessed by a subject or an object outside of its protection set and whether the access violates a given restriction of said core subset.
Claim 36
Dependent Claim
35 words
The system of claim 32, further comprising means for checking whether said protection set is a virus-free set by determining if any object in said protection set have been written to by other protection sets.
Claim 37
Dependent Claim
35 words
The system of claim 32, further comprising means for checking whether said protection set is a virus-confinement set by determining if any subjects in said protection set have written to objects of other protection sets.
Claim 38
Dependent Claim
66 words
The system of claim 29, wherein said means for generating a new protection graph comprises means for providing an indirect read relation in said protection graph between a first subject and a second subject if a direct wrote operation or an indirect wrote operation exists between said first subject and a first object and a read operation exists between said second subject and said first object.
Claim 39
Dependent Claim
59 words
The system of claim 29, wherein said means for generating a new protection graph comprises means for providing an indirect read relation in said protection graph between a subject and a first object if an indirect wrote operation exists between said first object and a second object and a read operation exists between said subject and said second object.
Claim 40
Dependent Claim
72 words
The system of claim 29, wherein said means for generating a new protection graph comprises means for providing an indirect write relation in said protection graph between a first object and a second object if a read operation or an indirect read operation or a is-controlled-by operation or a indirectly is-controlled-by operation exists between a subject and said first object and a write operation exists between said subject and said second object.
Claim 41
Dependent Claim
63 words
The system of claim 29, wherein said means for generating a new protection graph comprises means for providing an indirect write relation in said protection graph between a first object and a subject if an indirect read operation or an indirect is-controlled-by operation exists between said subject and said first object and a write operation exists between said subject and said second object.
Claim 42
Dependent Claim
60 words
The system of claim 29, wherein said means for generating a new protection graph comprises means for providing an indirect is-controlled-by relation in said protection graph between a first subject and a second subject if a wrote operation or an indirect wrote operation exists between said first subject and an object and said second subject is controlled by said object.
Claim 43
Dependent Claim
56 words
The system of claim 29, wherein said means for generating a new protection graph comprises means for providing an indirect is-controlled-by relation in said protection graph between a subject and a first object if an indirect wrote operation exists between said first object and a second object and said subject is controlled by said second object.
Claim 44
Dependent Claim
51 words
The system of claim 29, wherein said means for generating a new protection graph comprises means for providing an indirect drive relation in said protection graph between an object and a first subject if said first subject is-controlled-by or indirectly in-controlled-by said object and said first subject drives said second subject.
Claim 45
Dependent Claim
52 words
The system of claim 29, wherein said means for generating a new protection graph comprises means for providing an indirect drive relation in said protection graph between a first subject and a second subject if said first subject is indirectly controlled-by a third subject and said third subject drives said second subject.
Claim 46
Dependent Claim
53 words
The system of claim 29, wherein said means for generating a new protection graph comprises means for providing an indirect drive relation in said protection graph between a first subject and a second subject if said first subject drove or indirectly drove a third subject and said third subject drives said second subject.
Claim 47
Dependent Claim
49 words
The system of claim 29, wherein said means for generating a new protection graph comprises means for providing an indirect drive relation in said protection graph between an object and a first subject if said object indirectly drove a second subject and said second subject drives said first subject.
Claim 48
Dependent Claim
22 words
The system of claim 29, wherein the first protection graph and said second protection graph are stored in the data storage memory.
Claim 49
Dependent Claim
18 words
The system of claim 29, wherein said set of intrusion patterns are stored in the data storage memory.
Claim 50
Independent Claim
134 words
A method for detecting intrusion patterns in a secure computer system, wherein the state of actions in the audit trail of the secure computer system are represented by a first protection graph that includes direct and indirect relations between subjects and objects, the method comprising the steps of: (1) performing an access operation on one or more components of the computer system; (2) generating a second protection graph from the first protection graph and said access operation by applying a set of model rules, wherein said second protection graph represents the present state of action in the audit trail in the secure computer system; (3) comparing said second protection graph with a set of intrusion patterns to generate an exception condition; and (4) indicating the existence of an intrusion based on said exception condition.
Claim 51
Independent Claim
134 words
A method for detecting intrusion patterns in a secure computer system, wherein the state of actions in the audit trail of the secure computer system are represented by a first protection graph that includes direct and indirect relations between subjects and objects, the method comprising the steps of: (1) performing an access operation on one or more components of the computer system; (2) generating a second protection graph from the first protection graph and said access operation by applying a set of model rules, wherein said second protection graph represents the present state of action in the audit trail in the secure computer system; (3) comparing said second protection graph with a set of intrusion patterns to generate an exception condition; and (4) indicating the existence of an intrusion based on said exception condition.
Claim 52
Independent Claim
197 words
A system for detecting intrusion patterns in a secure computer system, wherein the state of actions in the audit trail of the secure computer system are represented by a first protection graph that includes direct and indirect relations between subjects and objects comprising: (1) a secure computer system comprising a central processing unit and a data storage memory, wherein the operation of said secure computer system is controlled by an operating system, said secure computer system further having means for performing an access operation on one or more components of said secure computer system; (2) an intrusion detection system operating concurrently with said operating system, said intrusion detection system comprising, (a) means for applying a set of model rules to the first protection graph and said access operation to generate a second protection graph, wherein said second protection graph is stored in said data storage memory; (b) means for comparing said second protection graph with a set of intrusion patterns stored in said data storage memory to generate an exception condition, said exception condition indicative of whether there has been an intrusion; and (c) means for indicating the existence of an intrusion based on said exception conditions.
Claim 53
Independent Claim
197 words
A system for detecting intrusion patterns in a secure computer system, wherein the state of actions in the audit trail of the secure computer system are represented by a first protection graph that includes direct and indirect relations between subjects and objects comprising: (1) a secure computer system comprising a central processing unit and a data storage memory, wherein the operation of said secure computer system is controlled by an operating system, said secure computer system further having means for performing an access operation on one or more components of said secure computer system; (2) an intrusion detection system operating concurrently with said operating system, said intrusion detection system comprising, (a) means for applying a set of model rules to the first protection graph and said access operation to generate a second protection graph, wherein said second protection graph is stored in said data storage memory; (b) means for comparing said second protection graph with a set of intrusion patterns stored in said data storage memory to generate an exception condition, said exception condition indicative of whether there has been an intrusion; and (c) means for indicating the existence of an intrusion based on said exception conditions.
References Cited (Backward Citations)
US4124848A
Cited
US4685056A
Cited
US4639902A
Cited
US5117457A
Cited
US4845682A
Cited
US4975950A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-01-10 | 1997-07-12 | 1998-01-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-01-10 | 2001-07-12 | 2002-01-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-01-10 | 2005-07-12 | 2006-01-11 | $7700.00 | Window Closed / Lapsed |