Dynamic control graphs for analysis of coordination-centric software designs
First Claim
1. A static error checking system for analyzing a software system in order to detect design errors prior to system execution, the software system comprising a set of software elements which expose control interactions between the software elements, by representing the control interactions in a control graph, the control graph comprising:
- a set of conjunctive nodes, each of which represents a conjunctive boolean guard on state changes within the software system;
a set of disjunctive nodes, each of which represents a boolean guard on a functional object within one of the software elements;
a set of action nodes, each of which represents a functional object within one of the software elements that responds to control interactions and produces control interactions; and
a set of directed edges, each of which connect two nodes and represents implication between the two nodes.
2 Assignments
0 Petitions
Accused Products
Abstract
Static analysis can be of great benefit in debugging complex systems. Traditional runtime debugging is necessary because certain software errors cannot be detected until after they are compiled into execution errors. Static analysis can reduce the number of such errors and can aid designers by illuminating subtle design interactions. Disclosed are various systems and methods for static analysis that can be applied to coordination-centric systems, including typechecking, consistency checking, and conflict detection through automatically derived abstract views, and model checking. The static analyses presented here comprise a form of preemptive debugging for coordination-centric software systems.
-
Citations
25 Claims
-
1. A static error checking system for analyzing a software system in order to detect design errors prior to system execution, the software system comprising a set of software elements which expose control interactions between the software elements, by representing the control interactions in a control graph, the control graph comprising:
-
a set of conjunctive nodes, each of which represents a conjunctive boolean guard on state changes within the software system;
a set of disjunctive nodes, each of which represents a boolean guard on a functional object within one of the software elements;
a set of action nodes, each of which represents a functional object within one of the software elements that responds to control interactions and produces control interactions; and
a set of directed edges, each of which connect two nodes and represents implication between the two nodes. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A data structure for representing control constraints and control actions of a software system, the software system comprising at least two software elements with explicit control interactions between the software elements, the data structure comprising:
-
a set of conjunctive boolean guards on state changes within the software system;
a set of boolean guards on functional objects within the software elements;
a set of functional control objects within the software elements, each functional control object being responsive to a control interaction and capable of producing a control interaction; and
a set of relational connections between two elements from the set of conjunctive boolean guards, the set of boolean guards on objects, and the set of functional control objects, each pointer representing implication between the two elements it connects. - View Dependent Claims (7, 8, 9, 10)
-
-
11. A static error checking system for debugging a software system, the software system comprising software elements which expose control interaction and data flow interactions between the software elements, by representing the control interactions and the data flow interactions in a graph, the graph comprising:
-
a set of conjunctive nodes, each of which represents a conjunctive boolean guard on state changes within the software system;
a set of disjunctive nodes, each of which represents a boolean guard on a functional object within one of the software elements;
a set of action nodes, each of which represents a functional object within one of the software elements that is responsive to a control interaction and capable of producing a control interaction;
a set of data flow nodes, each of which represents a data flow interaction between a first and a second software elements; and
a set of directed edges, each of which connects a first node to a second node and represents implication between the first and second nodes. - View Dependent Claims (12, 13, 14, 15, 17, 18, 19, 20)
-
-
16. A data structure for representing control constraints and control actions of a software system, the software system comprising at least two software elements with explicit control interactions between the software elements, the data structure comprising:
-
a set of conjunctive boolean guards on state changes within the software system;
a set of boolean guards on functional objects within the software elements;
a set of functional control objects within the software elements, each functional control object being responsive to a control interaction and capable of producing a control interaction;
a set of data flow nodes, each of which represents a data flow interaction between a first and a second software elements; and
a set of relational connections between two elements from the set of conjunctive boolean guards, the set of boolean guards on objects, and the set of functional control objects, each pointer representing implication between the two elements it connects.
-
-
21. A method for converting a control graph representation of a software system, having a state space and an initial state, into a binary decision diagram of the software system comprising:
-
transforming the control graph to express a potential next state of the software system after a predetermined period of time; and
generating a binary decision diagram based on the transformed control graph, whereby known static error checking techniques may be used to further identify any unexpected behavior of the software system without incurring the cost of fully elaborating the state space of the software system. - View Dependent Claims (22, 23, 24)
-
-
25. A bit vector for use in debugging software systems, the software system comprising at least a first and second component and a coordinator for implementing a predetermined coordination scheme for managing control and dataflow interactions between the first and second components, the first and second components connected to the coordinator by a first and second pair of complimentary coordination interfaces, respectively, each coordination interface in the first pair of complimentary coordination interfaces comprising a control port for transferring control state between the respective component and the coordinator, each control port having a control state value representing on or off, the bit vector comprising:
-
one bit corresponding to each control port within the software system, each bit having a boolean value representing the control state value of its corresponding control port at a predetermined time.
-
Specification