Method and apparatus for analyzing information systems using stored tree database structures

• US 5,850,516 A
• Filed: 12/23/1996
• Issued: 12/15/1998
• Est. Priority Date: 12/23/1996
• Status: Expired due to Term

• Current Assignee: BT Americas Incorporated (BT Group PLC)
• Original Assignee: Bruce Schneier
• Inventors: Schneier, Bruce
• Primary Examiner(s): DeCady, Albert
• Assistant Examiner(s): ELISCA, PIERRE E
• Application Number:
  US08/772,413
• Time in Patent Office: 722 Days
• Field of Search: 395/186, 395/187.01, 395/200.59, 395/284, 707/9, 380/23, 380/25
• US Class Current: 726/25
• CPC Class Codes: G06F 21/57 Certifying or maintaining trusted computer platforms, e.g. secure boots or power-downs, version controls, system software checks, secure updates or assessing vulnerabilities
• CPC Class Codes: G06F 2211/008 Public Key, Asymmetric Key, Asymmetric Encryption
• CPC Class Codes: H04L 63/14 for detecting or protecting against malicious traffic
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

A computer-implemented method and apparatus electronically represent and quantify the security of a system as a logical tree structure including leaf nodes representing attacks against the system and intermediate nodes representing various logical combinations of attacks necessary to mount a successful overall attack. An indication of the overall security of the system is quantified in a value of a root node of the tree. The values of the various nodes can be Boolean or continuous, representing simple binary security attributes such as feasible/infeasible or more complicated attributes such as cost, time or probability. The nodes'"'"' attributes and values can also represent defenses as well as attacks. The attack trees can be used to calculate the cost, time or probability of an attack to list the security assumptions of a system, to compare competing systems, to evaluate system modifications, to perform security subsystem analysis, to allocate a security budget, and for many other uses.

Claims

1. A computer-implemented method for evaluating the security of a system, comprising the steps of:

(a) receiving an identifier of a particular system to be evaluated;

(b) storing in a computer-readable medium a logic tree data structure representing a security model which corresponds to the selected information protection system, said logic tree including;

(i) a plurality of leaf nodes, each of which represents a particular security attribute of the selected system,

(ii) a root node representing an overall indication of the security of the system and

(iii) at least one intermediate node located between said leaf nodes and said root node, said intermediate node representing a logical relationship between at least two of said particular security attributes; and

(c) receiving values for said leaf nodes quantifying said attributes;

(d) computing a value of said root node that provides an indication of the overall security of the system.

2. The method of claim 1 where said attribute is Boolean-valued.

3. The method of claim 2 where said attribute is continuous-valued.

4. The method of claim 3 where said value is a cost associated with said security attribute.

5. The method of claim 4 where said cost corresponds to a particular attack.

6. The method of claim 4 where said cost corresponds to defending against a particular attack.

7. The method of claim 3 where said attribute is a time associated with said security attribute.

8. The method of claim 1 where said attribute indicates a likelihood of occurrence of said security attribute.

9. The method of claim 8 where said value indicates a probability of occurrence of said security attribute.

10. The method of claim 9 where said security attribute pertains to a particular attack.

11. The method of claim 9 where said security attribute pertains to defending against a particular attack.

12. The method of claim 9 where said probability reflects an attacker'"'"'s awareness of said particular attack.

13. The method of claim 1 where at least one of said nodes also reflects a countermeasure.

14. The method of claim 13 where said node containing said countermeasure is a leaf node.

15. The method of claim 13 where said node containing said countermeasure is an intermediate node.

16. The method of claim 13 where said node containing said countermeasure points to a separate attack tree against that countermeasure.

17. The method of claim 1 where at least one of said logical relationships includes an algebraic relationship.

18. The method of claim 1 where at least one of said logical relationships is expressed with a relational operator.

19. The method of claim 1 where at least one of said logical relationships includes a Boolean relationship.

20. The method of claim 1 where at least one of said nodes has children representing different possible attacks against the node.

21. The method of claim 20 where said at least one of said nodes reflects a minimum of said children'"'"'s values.

22. The method of claim 1 where at least one of nodes has children representing different parts of a single attack against said node.

23. The method of claim 22 where said at least one of said nodes reflects a sum of its children'"'"'s values.

24. The method of claim 22 where said at least one of said nodes reflects a value exhibited by all of its children.

25. The method of claim 1 where said root node indicates the overall attackability of said system.

26. The method of claim 25 where said value of said root node represents a cost to attack said system.

27. The method of claim 25 where said value of said root node represents a probability of attacking said system.

28. The method of claim 1 where said root node indicates an overall defendability of said system.

29. The method of claim 28 where said value of said root node indicates a cost to de fend said system.

30. The method of claim 28 where said value of said root node indicates a probability of defending said system.

31. The method of claim 1 where at least one of said nodes represents a plurality of attributes.

32. The method of claim 31 where said attributes are represented directly by said at least one node.

33. The method of claim 32 where said attribute of said at least one node is vector-valued.

34. The method of claim 31 where said plurality of attributes are represented by a sub-tree structure.

35. The method of claim 1 where at least one of said nodes represents an attack about which there is currently no information.

36. The method of claim 1 where said value of at least one said leaf nodes is propagated through said intermediate nodes to said root node.

37. The method of claim 1 where said security attribute pertains to the safety of said system.

38. The method of claim 1 where said security attribute pertains to the reliability of said system.

56. The computer-readable medium of claim 38 wherein at least one of said logical relationships is expressed with a relational operator.

75. The computer-readable medium of claim 38 wherein said security attribute pertains to the safety of said system.

76. The computer-readable medium of claim 38 wherein said security attribute pertains to the reliability of said system.

39. A computer-readable medium storing a logic data tree structure comprising:

(a) a plurality of leaf nodes, each of which represents a particular security attribute of a system;

(b) a root node representing an overall indication of the security of said system; and

(c) at least one intermediate node located between said leaf nodes and said root node, said intermediate node representing a between at least two of said particular security attributes; and

said leaf nodes having values quantifying said attributes whereby a value of said root node provides said indication of said security of said system for use in evaluating said security of said system.

40. The computer-readable medium of claim 39 wherein said attribute is Boolean-valued.

41. The computer-readable medium of claim 40 wherein said attribute is continuous-valued.

42. The computer-readable medium of claim 41 wherein said value is a cost associated with said security attribute.

43. The computer-readable medium of claim 42 wherein said cost corresponds to a particular attack.

44. The computer-readable medium of claim 42 wherein said cost corresponds to defending against a particular attack.

45. The computer-readable medium of claim 41 wherein said attribute is a time associated with said security attribute.

46. The computer-readable medium of claim 39 wherein said attribute indicates a likelihood of occurrence of said security attribute.

47. The computer-readable medium of claim 46 wherein said value indicates a probability of occurrence of said security attribute.

48. The computer-readable medium of claim 47 wherein said security attribute pertains to a particular attack.

49. The computer-readable medium of claim 47 wherein said security attribute pertains to defending against a particular attack.

50. The computer-readable medium of claim 47 wherein said probability reflects an attacker'"'"'s awareness of said particular attack.

51. The computer-readable medium of claim 39 wherein at least one of said nodes also reflects a countermeasure.

52. The computer-readable medium of claim 51 wherein said node containing said countermeasure is a leaf node.

53. The computer-readable medium of claim 51 wherein said node containing said countermeasure is an intermediate node.

54. The computer-readable medium of claim 51 wherein said node containing said countermeasure points to a separate attack tree against that countermeasure.

55. The computer-readable medium of claim 39 wherein at least one of said logical relationships includes an algebraic relationship.

57. The computer-readable medium of claim 39 wherein at least one of said logical relationships includes a Boolean relationship.

58. The computer-readable medium of claim 39 wherein at least one of said nodes has children representing different possible attacks against the node.

59. The computer-readable medium of claim 58 wherein said at least one of said nodes reflects a minimum of said children'"'"'s values.

60. The computer-readable medium of claim 39 wherein at least one of nodes has children representing different parts of a single attack against said node.

61. The computer-readable medium of claim 60 wherein said at least one of said nodes reflects a sum of its children'"'"'s values.

62. The computer-readable medium of claim 60 wherein said at least one of said nodes reflects a value exhibited by all of its children.

63. The computer-readable medium of claim 39 wherein said root node indicates the overall attackability of said system.

64. The computer-readable medium of claim 63 wherein said value of said root node represents a cost to attack said system.

65. The computer-readable medium of claim 63 wherein said value of said root node represents a probability of attacking said system.

66. The computer-readable medium of claim 39 wherein said root node indicates an overall dependability of said system.

67. The computer-readable medium of claim 65 wherein said value of said root node indicates a cost to defend said system.

68. The computer-readable medium of claim 65 wherein said value of said root node indicates a probability of defending said system.

69. The computer-readable medium of claim 39 wherein at least one of said nodes represents a plurality of attributes.

70. The computer-readable medium of claim 69 wherein said attributes are represented directly by said at least one node.

71. The computer-readable medium of claim 70 wherein said attribute of said at least one node is vector-valued.

72. The computer-readable medium of claim 69 wherein said plurality of attributes are represented by a sub-tree structure.

73. The computer-readable medium of claim 39 wherein at least one of said nodes represents an attack about which there is currently no information.

74. The computer-readable medium of claim 39 wherein said value of at least one said leaf nodes is propagated through said intermediate nodes to said root node.