System and method for providing a data structure representative of a fault tree

• US 7,516,025 B1
• Filed: 06/29/2004
• Issued: 04/07/2009
• Est. Priority Date: 06/29/2004
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Williams, Emrys, Rudoff, Andrew
• Primary Examiner(s): Dunn; Drew A
• Assistant Examiner(s): Suarez; Felix E
• Application Number:
  US10/880,000
• Time in Patent Office: 1,743 Days
• Field of Search: 702/58, 702/59, 702/119, 702/123, 702/126, 702/182, 702/183, 702/198, 702/185, 702/186, 702/57, 707/101, 711/122, 714/25
• US Class Current: 702/57
• CPC Class Codes: G05B 23/0278 Qualitative, e.g. if-then rules; Fuzzy logic; Lookup tables; Symptomatic search; FMEA
• CPC Class Codes: G06F 11/0706 the processing taking place on a specific hardware platform or in a specific software environment
• CPC Class Codes: G06F 11/079 Root cause analysis, i.e. error or fault diagnosis in a hardware test environment G06F11/22; in a software test environment G06F11/36

Abstract

One embodiment of the invention provides apparatus including a data structure representing a fault tree for a system. The data structure comprises a plurality of events linked by propagations. Each event is classified as one of at least three possible event types. A first type of event is a problem event, which represents an underlying cause of misbehavior in the system. A second type of event is an error event, which represents an error in the system comprising an incorrect signal or datum. A third type of event is a report event, representing the formal detection by the system of an error. Each propagation in the fault tree denotes a cause and effect linkage from one event to another event. There are no propagations within the fault tree to a problem event.

Claims

1. An apparatus, comprising:

a processor; and

a memory comprising program instructions executable by the processor to implement a data structure representing a fault tree for a system;

wherein said data structure comprises indications of a plurality of events;

wherein the indications of the events are linked in the data structure according to propagations in the fault tree, each event being classified as one of at least three possible event types;

a problem event, representing an underlying cause of misbehaviour in the system;

an error event, representing an error in the system comprising an incorrect signal or datum; and

a report event, representing the formal detection by the system of an error;

wherein at least one of each of the at least three possible three event types are indicated in said data structure;

wherein each propagation in the fault tree denotes a cause and effect linkage from one event to another event; and

wherein there are no propagations within the fault tree to a problem event.

2. The apparatus of claim 1, wherein said fault tree includes at least one propagation from a problem event to an error event, and at least one propagation from an error event to a report event.

3. The apparatus of claim 2, wherein said fault tree includes at least one propagation from one error event to another error event.

4. The apparatus of claim 2, wherein there are no propagations within the fault tree from a report event.

5. The apparatus of claim 1, wherein one or more propagations from an event are associated with an effect specifier, said effect specifier denoting a minimum number of said one or more propagations that occur in response to said event.

6. The apparatus of claim 5, wherein an effect specifier denoting the number zero represents a “

may”

propagation.

7. The apparatus of claim 5, wherein an effect specifier may denote that all propagations associated with said effect specifier occur in response to said event.

8. The apparatus of claim 5, wherein an effect specifier may denote that all propagations associated with said effect specifier occur in response to said event, except for propagations forbidden by constraints.

9. The apparatus of claim 1, wherein one or more propagations to an event are associated with a cause specifier, said cause specifier denoting the minimum number of said one or more propagations that must occur together for said event to occur.

10. The apparatus of claim 9, wherein said cause specifier can denote that all propagations associated with said cause specifier must occur together for said event to occur.

11. The apparatus of claim 9, wherein said cause specifier may denote that all propagations associated with said cause specifier must occur together for said event to occur, except for propagations forbidden by constraints.

12. The apparatus of claim 1, wherein a propagation to an event may be used to inhibit said event.

13. The apparatus of claim 12, wherein one or more propagations to an event are associated with an inhibit specifier, said inhibit specifier denoting the minimum number of said one or more propagations that must occur together for said event to be inhibited.

14. The apparatus of claim 1, wherein a time value may be associated with a propagation from an event, wherein if the propagation occurs in response to said event, then the propagation occurs no later than said time value after the event.

15. The apparatus of claim 1, wherein a minimum time value and a maximum time value may be associated with a propagation from an event, wherein if the propagation occurs in response to said event, then the propagation occurs no earlier than said minimum time value after the event and no later than said maximum time value after the event.

16. The apparatus of claim 1, wherein a propagation may be denoted as only occurring in response to a polling routine.

17. The apparatus of claim 1, wherein a constraint may be associated with a propagation, and wherein the propagation can only occur if the constraint is satisfied.

18. The apparatus of claim 17, wherein said constraint relates to the configuration of the system.

19. The apparatus of claim 17, wherein said constraint relates to a value of a parameter associated with a propagation.

20. The apparatus of claim 1, wherein said data structure is invariant with respect to configuration changes in said system.

21. The apparatus of claim 20, further including stored information describing a system configuration, wherein said data structure can be combined with said stored information in order to represent error propagations in accordance with said system configuration.

22. An apparatus, comprising:

a processor; and

a memory comprising program instructions executable by the processor to implement a data structure representing a fault tree for a system;

wherein said data structure comprises indications of a plurality of events;

wherein the indications of the events are linked in the data structure according to propagations in the fault tree;

wherein each propagation in the fault tree denotes a cause and effect linkage from one event to another event; and

wherein one or more propagations from an event are associated with an effect specifier, said effect specifier denoting the minimum number of said one or more propagations that occur in response to said event.

23. An apparatus, comprising:

a processor; and

a memory comprising program instructions executable by the processor to implement a data structure representing a fault tree for a system;

wherein said data structure comprises indications of a plurality of events;

wherein the indications of the events are linked in the data structure according to propagations in the fault tree;

wherein each propagation in the fault tree denotes a cause and effect linkage from one event to another event; and

wherein one or more propagations to an event are associated with a cause specifier, said cause specifier denoting the minimum number of said one or more propagations that must occur together for said event to occur.

24. An apparatus, comprising:

a processor; and

a memory comprising program instructions executable by the processor to implement a data structure representing a fault tree for a system;

wherein said data structure comprises indications of a plurality of events;

wherein the indications of the events are linked in the data structure according to propagations in the fault tree;

wherein each propagation in the fault tree denotes a cause and effect linkage from one event to another event; and

wherein;

one or more propagations from an event are associated with an effect specifier, said effect specifier denoting the number of said one or more propagations that occur in response to said event, and

one or more propagations to an event are associated with a cause specifier, said cause specifier denoting the number of said one or more propagations to an event that must occur for said event to occur.

25. The apparatus of claim 24, wherein each propagation in the fault tree starts at an effect specifier and terminates at a cause specifier.

26. An apparatus, comprising:

a processor; and

a memory comprising program instructions executable by the processor to implement a data structure representing a fault tree for a system;

wherein said data structure comprises indications of a plurality of events;

wherein the indications of the events are linked in the data structure according to propagations in the fault tree;

wherein each propagation in the fault tree denotes a cause and effect linkage from one event to another event; and

wherein at least one event in the fault tree has;

a first propagation to the event, wherein said first propagation acts to cause the event to occur; and

a second propagation to the event, wherein said second propagation inhibits the event from occurring, and wherein the inhibiting of said second propagation takes precedence over the causing of the first propagation.

27. The apparatus of claim 26, wherein said second propagation and one or more additional propagations to said event are associated with an inhibit specifier, said inhibit specifier denoting the number of propagations to said inhibit specifier that must occur for said event to be inhibited.

28. A computer readable storage medium, comprising program instructions computer-executable to implement a data structure representing a fault tree for a system;

wherein said data structure comprises indications of a plurality of events;

wherein the indications of the events are linked in the data structure according to propagations in the fault tree, each event being classified as one of at least three possible event types;

a problem event, representing an underlying cause of misbehaviour in the system;

an error event, representing an error in the system comprising an incorrect signal or datum; and

a report event, representing the formal detection by the system of an error;

wherein at least one of each of the at least three possible three event types are indicated in said data structure;

wherein each propagation in the fault tree denotes a cause and effect linkage from one event to another event; and

wherein there are no propagations within the fault tree to a problem event.

29. A computer-implemented method for providing a data structure representing a fault tree for a system, said method including:

defining a set of events that may occur within the fault tree, each event in the fault tree being classified as one of at least three possible event types;

a problem event, representing an underlying cause of misbehaviour in the system;

an error event, representing an error in the system comprising an incorrect signal or datum; and

a report event, representing the formal detection by the system of an error;

specifying propagations between said events; and

storing the data structure in a memory accessible by a system processor or application specific integrated circuit of a computer system;

wherein at least one of each of the at least three possible three event types are indicated in said data structure;

wherein a propagation in the fault tree denotes a cause and effect linkage from one event to another event; and

wherein there are no propagations within the fault tree to a problem event.

30. The method of claim 29, wherein said fault tree includes at least one propagation from a problem event to an error event, and at least one propagation from an error event to a report event.

31. The method of claim 30, wherein said fault tree includes at least one propagation from one error event to another error event.

32. The method of claim 30, wherein there are no propagations within the fault tree from a report event.

33. The method of claim 29, further comprising:

associating one or more propagations from an event with an effect specifier, said effect specifier denoting a minimum number of said one or more propagations that occur in response to said event.

34. The method of claim 33, wherein an effect specifier denoting the number zero represents a “

may”

propagation.

35. The method of claim 33, wherein an effect specifier may denote that all propagations associated with said effect specifier occur in response to said event.

36. The method of claim 33, wherein an effect specifier may denote that all propagations associated with said effect specifier occur in response to said event, except for propagations forbidden by constraints.

37. The method of claim 29, further comprising

associating one or more propagations to an event with a cause specifier, said cause specifier denoting the minimum number of said one or more propagations that must occur together for said event to occur.

38. The method of claim 37, wherein said cause specifier may denote that all propagations associated with said cause specifier must occur together for said event to occur.

39. The method of claim 37, wherein said cause specifier may denote that all propagations associated with said cause specifier must occur together for said event to occur, except for propagations forbidden by constraints.

40. The method of claim 29, wherein a propagation to an event may be used to inhibit said event.

41. The method of claim 40, further comprising:

associating one or more propagations to an event with an inhibit specifier, said inhibit specifier denoting the minimum number of said one or more propagations that must occur together for said event to be inhibited.

42. The method of claim 29, further comprising:

associating a time value with a propagation from an event, wherein if the propagation occurs in response to said event, then the propagation occurs no later than said time value after the event.

43. The method of claim 29, further comprising:

associating a minimum time value and a maximum time value with a propagation from an event;

wherein if the propagation occurs in response to said event, then the propagation occurs no earlier than said minimum time value after the event and no later than said maximum time value after the event.

44. The method of claim 29, wherein a propagation may be denoted as only occurring in response to a polling routine.

45. The method of claim 29, further comprising:

associating a constraint with a propagation;

wherein the propagation can only occur if the constraint is satisfied.

46. The method of claim 45, wherein said constraint relates to the configuration of the system.

47. The method of claim 45, wherein said constraint relates to a value of a parameter associated with a propagation.

48. The method of claim 29, wherein said data structure is invariant with respect to configuration changes in said system.

49. The method of claim 48, further comprising:

storing information describing a system configuration; and

combining said data structure with said stored information in order to represent error propagations in accordance with said system configuration.