GRAPH-BASED MODELING APPARATUS AND TECHNIQUES

• US 20080300834A1
• Filed: 06/01/2007
• Published: 12/04/2008
• Est. Priority Date: 06/01/2007
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Chow, Stanley TaiHai, Wiemer, Douglas, Li, Jennifer, Valiyapalathingal, Mohammed Riyas, Kwan, Louie
• Granted Patent: US 8,204,720 B2
• Time in Patent Office: Days
• US Class Current: 703/2
• CPC Class Codes: G06F 30/3323 using formal methods, e.g. equivalence checking or property checking

Abstract

Graph-based modeling apparatus and techniques are disclosed. Based on a model including model nodes that represent components of a modeled system, operational dependencies between model nodes, and model edges that interconnect the nodes and represent relationships between the components in the modeled system, subset computations are performed to compute subsets of the model nodes that can impact operational dependencies between other model nodes. When the model changes, a determination is made as to whether an incremental subset computation should be performed for one or more particular operational dependencies between model nodes in the changed model, and if so, an incremental subset computation is performed. Otherwise, a full subset computation or no subset computation might be performed. In this manner, model changes are considered on a case-by-case basis to determine an extent, if any, to which subsets should be re-computed.

Claims

1. An apparatus comprising:

a computation module operable to perform subset computations, based on a model comprising model nodes that represent components of a modeled system, operational dependencies between model nodes, and model edges that interconnect the nodes and represent relationships between the components in the modeled system, so as to compute subsets of the model nodes that can impact operational dependencies between other model nodes; and

a control module operatively coupled to the computation module and operable to determine whether, due to a change to the model, an incremental subset computation should be performed for one or more particular operational dependencies between model nodes in the changed model, and to cause the computation module to perform an incremental subset computation where it is determined that an incremental subset computation should be performed.

2. The apparatus of claim 1, wherein the control module is further operable to determine whether no subset computation or a full subset computation should be performed for all operational dependencies between model nodes in the changed model due to the change to the model, and to cause the computation module to perform a full subset computation where it is determined that full subset computation should be performed or an incremental subset computation where it is determined that an incremental subset computation should be performed, and wherein no subset computation is performed where it is determined that no subset computation should be performed.

3. The apparatus of claim 1, wherein the control module is operable to determine whether an incremental subset computation should be performed by identifying a model node that is affected by the change, and determining whether the affected model node comprises a subset of model nodes that can impact an operational dependency between other model nodes.

4. The apparatus of claim 1, wherein the incremental subset computation comprises at least one of:

a subset computation for a new operational dependency between model nodes, and a subset computation for an existing operational dependency between model nodes.

5. The apparatus of claim 1, further comprising:

a change detector operatively coupled to the control module and operable to detect the change to the model and to provide to the control module an indication of detection of the change.

6. The apparatus of claim 1, further comprising:

a user interface operatively coupled to the control module and operable to receive inputs from a user, wherein the change comprises a change entered by a user through the user interface.

7. The apparatus of claim 1, wherein the change to the model reflects a change in the modeled system.

8. The apparatus of claim 2, wherein the control module is operable to determine whether a full, an incremental, or no subset computation should be performed by at least one of:

determining that no subset computation is to be performed where the change comprises adding to or deleting from the model a leaf model node having no operational dependencies with other model nodes;

determining that a full subset computation is to be performed where the change comprises adding to the model a model node that is not a leaf model node;

determining that an incremental subset computation is to be performed where the change comprises deleting from the model a model node that is not a leaf model node;

determining that an incremental subset computation is to be performed where the change comprises adding to or deleting from the model an operational dependency between model nodes;

determining that a full subset computation is to be performed where the change comprises adding to the model a model edge between model nodes; and

determining that an incremental subset computation is to be performed where the change comprises deleting from the model a model edge between model nodes.

9. The apparatus of claim 1, further comprising:

an analysis system operatively coupled to the subset computation module and to the control module and operable to perform an analysis of a parameter associated with the modeled system based on the computed subsets,

wherein the control module is further operable to determine whether a full analysis of the modeled system, an incremental analysis for one or more particular operational dependencies between model nodes in the changed model, or no analysis of the modeled system should be performed due to the change, and to cause the analysis system to perform a full analysis where it is determined that a full analysis should be performed or an incremental analysis where it is determined that an incremental analysis should be performed, and wherein no analysis of the modeled system is performed where it is determined that no analysis of the modeled system should be performed.

10. The apparatus of claim 9, wherein the analysis system comprises a security risk analysis system operable to perform a security risk analysis based on the computed subsets.

11. The apparatus of claim 1, wherein each of the subsets comprises a minimal cut-set.

12. A method comprising:

performing subset computations, based on a model comprising model nodes that represent components of a modeled system, operational dependencies between model nodes, and model edges that interconnect the nodes and represent relationships between the components in the modeled system, so as to compute subsets of the model nodes that can impact operational dependencies between other model nodes;

determining whether, due to a change to the model, an incremental subset computation should be performed for one or more particular operational dependencies between model nodes in the changed model; and

performing an incremental subset computation where it is determined that an incremental subset computation should be performed.

13. The method of claim 12, further comprising:

determining whether no subset computation or a full subset computation should be performed for all operational dependencies between model nodes in the changed model due to the change to the model; and

performing a full subset computation where it is determined that a full subset computation should be performed,

wherein no subset computation is performed where it is determined that no subset computation should be performed.

14. The method of claim 12, wherein determining comprises identifying a model node that is affected by the change, and determining whether the affected model node comprises a subset of model nodes that can impact an operational dependency between other model nodes.

15. The method of claim 12, wherein the incremental subset computation comprises at least one of:

a subset computation for a new operational dependency between model nodes, and a subset computation for an existing operational dependency between model nodes.

16. The method of claim 13,

wherein determining whether an incremental subset computation should be performed comprises determining that an incremental subset computation is to be performed where the change comprises deleting from the model a model node that is not a leaf model node, adding to or deleting from the model an operational dependency between model nodes, or deleting from the model a model edge between model nodes, and

wherein determining whether no subset computation or a full subset computation should be performed comprises determining that a full subset computation is to be performed where the change comprises adding to the model a model node that is not a leaf model node or adding to the model a model edge between model nodes, and determining that no subset computation is to be performed where the change comprises adding to or deleting from the model a leaf model node having no operational dependencies with other model nodes.

17. The method of claim 12, further comprising:

performing an analysis of a parameter associated with the modeled system based on the computed subsets;

determining whether a full analysis of the modeled system, an incremental analysis for one or more particular operational dependencies between model nodes in the changed model, or no analysis of the modeled system should be performed due to the change; and

performing a full analysis where it is determined that a full analysis should be performed or an incremental analysis where it is determined that an incremental analysis should be performed,

wherein no analysis of the modeled system is performed where it is determined that no analysis of the modeled system should be performed.

18. The method of claim 12, wherein each of the subsets comprises a minimal cut-set.

19. A computer-readable medium storing instructions which when executed perform the method of claim 12.

20. A computer-readable medium storing a data structure, the data structure comprising:

a plurality of model node fields comprising information indicative of respective model nodes that represent components of a modeled system, the model nodes comprising a model that further comprises operational dependencies between the model nodes, and model edges, which interconnect the model nodes and represent relationships between the components in the modeled system; and

a plurality of operational dependency fields respectively associated with the model node fields, the operational dependency field associated with a model node field for a model node comprising information indicative of an operational dependency between other model nodes for which the model node comprises a subset of model nodes that can impact the operational dependency,

the operational dependency fields enabling a determination to be made as to whether, due to a change to the model that affects one or more of the model nodes, an incremental subset computation should be performed to compute subsets of model nodes that can impact one or more particular operational dependencies of the respective operational dependencies.