Graph-based modeling apparatus and techniques

• US 8,204,720 B2
• Filed: 06/01/2007
• Issued: 06/19/2012
• Est. Priority Date: 06/01/2007
• Status: Expired due to Fees

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Chow, Stanley Taihai, Li, Jennifer, Kwan, Louie, Valiyapalathingal, Mohammed Riyas, Wiemer, Douglas
• Primary Examiner(s): Silver, David
• Assistant Examiner(s): CALLE, ANGEL J.
• Application Number:
  US11/756,970
• Publication Number:
  US 20080300834A1
• Time in Patent Office: 1,845 Days
• Field of Search: 703/1, 703/2, 707/1, 345/619, 3/1
• 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 for a graph-based model, the graph-based 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, the subset computations comprising computing subsets of the model nodes that can impact operational dependencies between other model nodes, each computed subset comprising a subset of the model nodes that, if the model nodes of the subset are removed from the graph-based model, would separate other model nodes, between which there is an operational dependency, into different disconnected sub-graphs of the graph-based model; and

a control module operatively coupled to the computation module and operable to determine whether, due to a change to the graph-based model that results in a changed graph-based model, a partial subset computation to compute one or more subsets for only one or more particular operational dependencies between model nodes in the changed graph-based model should be performed, and to cause the computation module to perform the partial subset computation based on the determination, the one or more particular operational dependencies comprising fewer than all operational dependencies in the changed graph-based model,

at least one of the computation module and the control module being implemented using hardware,

wherein the control module is further operable to determine whether no subset computation or a full subset computation should be performed to compute subsets for all operational dependencies between model nodes in the changed graph-based model due to the change to the graph-based model, and, based on the determination, to cause the computation module to perform the full subset computation, the partial subset computation, or no subset computation,

wherein the control module is operable to determine whether the full, the partial, or no subset computation should be performed by determining that the full subset computation is to be performed where the change comprises adding to the graph-based model a model node that is not a leaf model node or adding to the graph-based model a model edge between model nodes;

determining that the partial subset computation is to be performed where the change comprises deleting from the graph-based model a model node that is not a leaf model node, adding to or deleting from the graph-based model an operational dependency between model nodes, or deleting from the graph-based 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 graph-based model a leaf model node having no operational dependencies with other model nodes.

2. The apparatus of claim 1, wherein the control module is further operable to determine whether the partial subset computation should be performed by identifying in the graph-based model a model node that is affected by the change, and determining whether the affected model node comprises one of the computed subsets of model nodes.

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

a subset computation to compute one or more subsets for a new operational dependency between model nodes, and a subset computation to compute one or more subsets for an existing operational dependency between model nodes.

4. The apparatus of claim 1, further comprising:

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

5. 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.

6. The apparatus of claim 1, wherein the change to the graph-based model reflects a change in the modeled system.

7. The apparatus of claim 1, further comprising:

an analysis system operatively coupled to the 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, a partial analysis for only one or more particular operational dependencies between model nodes in the changed graph-based model, or no analysis of the modeled system should be performed due to the change, and, based on the determination, to cause the analysis system to perform the full analysis, the partial analysis, or no analysis of the modeled system.

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

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

10. A method comprising:

a computation module performing subset computations for a graph-based model, the

graph-based 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, the subset computations comprising computing subsets of the model nodes that can impact operational dependencies between other model nodes, each computed subset comprising a subset of the model nodes that, if the model nodes of the subset are removed from the graph-based model, would separate other model nodes, between which there is an operational dependency, into different disconnected sub-graphs of the graph-based model;

a control module, operatively coupled to the computation module, determining whether, due to a change to the graph-based model that results in a changed graph-based model, a partial subset computation to compute one or more subsets for only one or more particular operational dependencies between model nodes in the changed graph-based model should be performed; and

the computation module performing the partial subset computation based on the determination, the one or more particular operational dependencies comprising fewer than all operational dependencies in the changed graph-based model,

at least one of the computation module and the control module being implemented using hardware,

the method 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 graph-based model due to the change to the graph-based model; and

performing the full subset computation, the partial subset computation, or no subset computation, based on the determination,

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

wherein determining whether no subset computation or the full subset computation should be performed comprises determining that the full subset computation is to be performed where the change comprises adding to the graph-based model a model node that is not a leaf model node or adding to the graph-based 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 graph-based model a leaf model node haying no operational dependencies with other model nodes.

11. The method of claim 10, wherein determining whether the partial subset computation should be performed further comprises identifying in the graph-based model a model node that is affected by the change, and determining whether the affected model node comprises one of the computed subsets of model nodes.

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

a subset computation to compute one or more subsets for a new operational dependency between model nodes, and a subset computation to compute one or more subset for an existing operational dependency between model nodes.

13. The method of claim 10, 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, a partial analysis for only one or more particular operational dependencies between model nodes in the changed graph-based model, or no analysis of the modeled system should be performed due to the change; and

performing the full analysis, the partial analysis, or no analysis of the modeled system, based on the determination.

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

15. A non-transitory computer-readable medium storing instructions which when executed perform the method of claim 10.