Malicious fault list generation method

• US 5,561,762 A
• Filed: 06/06/1995
• Issued: 10/01/1996
• Est. Priority Date: 06/06/1995
• Status: Expired due to Fees

• Current Assignee: Union Switch & Signal, Inc. (Hitachi, Ltd.)
• Original Assignee: Union Switch & Signal, Inc. (Hitachi, Ltd.)
• Inventors: Johnson, Barry W., Smith, D. Todd, Giras, Theo C., Profeta, Joseph A.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): HUA, LY
• Application Number:
  US08/471,417
• Time in Patent Office: 483 Days
• Field of Search: 395/183.09, 395/184.01, 395/183.17, 395/183.01
• US Class Current: 714/33
• CPC Class Codes: G06F 11/16 Error detection or correction of the data by redundancy in hardware
• CPC Class Codes: G06F 11/2257 using expert systems
• CPC Class Codes: G06F 11/261 by simulating additional hardware, e.g. fault simulation

Abstract

A method for selecting and responding to a malicious fault in a reconfigurable electronic apparatus that can perform multiple tasks, and that has fault processing for counteracting a class of faults which can generally cause the apparatus to fail during the execution of a preselected task if the fault processor is unavailable and to which class the malicious fault can belong. The reconfigurable electronic apparatus can be a fault processing system, which can be an interlocking control circuit, or a combinational circuit. The method includes constructing an information flow representation of at least a portion of the apparatus executing the preselected task of interest; applying a preselected fault representation to the information flow representation and producing multiple input error conditions corresponding to at least one preselected output condition, the preselected fault representation including recursive reverse implication and, where reconvergent fanout occurs, a forward consistency check; selecting from the aforementioned multiple input error conditions at least one fault condition corresponding to the class of faults; injecting the at least one fault condition into the information flow representation and producing a malicious fault condition representative of said malicious fault; and modifying the apparatus responsive to the malicious fault condition, thereby counteracting the malicious fault. The malicious fault can belong to the class of faults occurring during execution of the preselected task by the apparatus and causing the apparatus to fail during such execution.

Claims

1. A method for selecting and responding to a malicious fault in a reconfigurable electronic apparatus, said apparatus for performing a plurality of tasks and having a first configuration and fault processes for counteracting a class of faults generally causing said apparatus to fail if said fault processor is unavailable, said malicious fault belonging to said class, occurring during execution of a preselected task by said apparatus, and causing said apparatus to fail during such execution, said preselected task being selected from said plurality of tasks, said method comprising the steps of:

a. constructing an information flow representation of at least a portion of said apparatus executing said preselected task;

b. applying a preselected fault representation to said information flow representation and producing a plurality of input error conditions corresponding to at least one preselected output condition;

c. selecting from said plurality of input error conditions at least one fault condition corresponding to said class of faults;

d. injecting said at least one fault condition into said information flow representation and producing a malicious fault condition representative of said malicious fault, said malicious fault belonging to said class of faults occurring during execution of said preselected task by said apparatus and causing said apparatus to fail during such execution; and

e. modifying said apparatus from said first configuration to a second configuration responsive to said malicious fault condition and counteracting said malicious fault thereby.

2. The method of claim 1 wherein said information flow representation of step (a) includes a directed graph data structure having a plurality of nodes and a plurality of arcs.

3. The method of claim 1 wherein said preselected fault representation includes reverse implication.

4. The method of claim 3 wherein said reverse implication is recursive reverse implication.

5. The method of claim 3 wherein step (b) of claim 1 further comprises the step of generating a fault tree using said reverse implication fault representation.

6. The method of claim 1 wherein step (a) further comprises the step of generating a simulation trace file representative of said at least a portion of said apparatus executing said preselected task.

7. The method of claim 6 further comprising the step of constructing from said simulation trace file a directed graph data structure having a plurality of nodes and a plurality of arcs.

8. The method of claim 1 wherein step (d) further includes the step of fault collapsing.

9. The method of claim 1 wherein said selecting further includes selecting selected ones of unevaluated faults which occur earliest in time relative to others of said unevaluated faults.

10. The method of claim 1 wherein said selected ones of unevaluated faults excludes latent faults.

11. The method of claim 1 wherein said reconfigurable electronic apparatus is at least one of a fault processing system and a combinational circuit.

12. The method of claim 11 wherein step (a) of claim 1 further comprises the step of generating a simulation trace file representative of said at least a portion of said apparatus executing said preselected task.

13. The method of claim 12 further comprising the step of constructing a directed graph data structure having a plurality of nodes and a plurality of arcs from said simulation trace file.

14. The method of claim 13 wherein said preselected fault representation includes reverse implication and wherein step (b) of claim 1 comprises the step of applying said reverse implication fault representation to selected ones of said plurality of nodes and said plurality of arcs, producing said plurality of input error conditions thereby.

15. The method of claim 14 wherein said applying said reverse implication fault representation further comprises the step of generating a fault tree.

16. The method of claim 14 wherein step (d) of claim 1 further includes fault collapsing.

17. The method of claim 14 wherein said selecting excludes latent faults.

18. The method of claim 11 wherein said fault processing system is an interlocking control system.

19. The method of claim 14 wherein step (b) of claim 1 further comprises the step of performing a forward consistency check on said selected ones of said plurality of nodes having a plurality of outputs to selected others therefrom, said selected others having reconvergent fanout.

20. The method of claim 1 wherein said constructing an information flow representation of at least a portion of said apparatus executing said preselected task comprises the steps of:

a. isolating said preselected task from others of said plurality of tasks;

b. generating a simulation file representative of said apparatus executing said preselected task; and

c. generating an information flow representation of said apparatus executing said preselected task from said simulation file.

21. A method for responding to a malicious fault in a reconfigurable electronic apparatus, said apparatus for performing a plurality of tasks and having a first configuration and a fault processor for counteracting a class of faults generally causing said apparatus to fail if said fault processor is unavailable, said malicious fault belonging to said class of faults, occurring during execution of a preselected task by said apparatus, and causing said apparatus to fail during such execution, said preselected task being selected from said plurality of tasks, said method comprising the steps of:

a. isolating said preselected task from others of said plurality of tasks;

b. generating a simulation file representative of said apparatus executing said preselected task;

c. generating an information flow representation of said apparatus executing said preselected task from said simulation file;

d. applying a preselected fault representation to said information flow representation and producing a plurality of input error conditions corresponding to at least one preselected output condition;

e. selecting from said plurality of input error conditions at least one fault condition corresponding to said class of faults;

f. injecting said at least one fault condition into said information flow representation and producing a malicious fault condition representative of said malicious fault, said malicious fault belonging to said class of faults generally causing said apparatus to fail if said fault processor is unavailable, said malicious fault occurring during execution of said preselected task by said apparatus and causing said apparatus to fail during such execution; and

g. modifying said apparatus from said first configuration to a second configuration responsive to said malicious fault condition and counteracting said malicious fault thereby.

22. The method of claim 21 wherein said information flow representation of step (c) includes a directed graph data structure having a plurality of nodes and a plurality of arcs.

23. The method of claim 22 wherein step (b) of claim 21 further comprises the step of performing a forward consistency check on said selected ones of said plurality of nodes having a plurality of outputs to selected others therefrom, said selected ones having reconvergent fanout.

24. The method of claim 21 wherein said preselected fault representation includes reverse implication fault representation.

25. The method of claim 24 wherein said reverse implication fault representation is recursive reverse implication fault representation.

26. The method of claim 21 wherein step (f) further includes the step of fault collapsing.

27. The method of claim 21 wherein said selecting further includes the step of selecting selected ones of unevaluated faults which occur earliest in time relative to others of said unevaluated faults.

28. The method of claim 21 wherein said selected ones of said unevaluated faults excludes latent faults.

29. The method of claim 21 wherein said reconfigurable electronic apparatus is at least one of a fault processing system and a combinational circuit.

30. The method of claim 29 wherein said fault processing system is an interlocking control system.

31. The method of claim 30 wherein said interlocking control system is an interlocking control system for railroad switching and signaling.

32. The method of claim 24 wherein step (c) of claim 21 further comprises the step of generating a fault tree using said reverse implication fault representation.