Finite Models Flashcards
What are the main four properties of models?
- Compact - representable, manipulable in a compact form
- Predictive - represents salient characteristics enough to distinguish good and bad outcomes of analysis.
- Semantically Meaningful - necessary to interpret analysis results to allow diagnosis of causes of failure.
- Sufficiently general - models must be general enough to be used in the domain of the application
What is a directed graph?
A directed graph has a set of nodes N, and a set of relations of the nodes E, edges
What are labels and code in graphs?
You can label nodes with the names or descriptions of the entities they represent. E.g. program regions of assigning statements.
What is a multidimensional graph representation?
You can draw a single diagram to represent more than one directed graph, like extensions of classes or showing a class has an instance of another.
What is meant by a finite abstraction of behaviour?
An abstraction function suppresses some details of program execution and lumps together execution states that differ with respect to suppressed details but otherwise identical.
What is a Control Flow Graph (intraprocedural)?
Like an activity diagram, but shows regions of code as nodes.
What are the elements of a Control Flow Graph?
Nodes - source code in basic blocks with a single entry and exit point. Statements can be grouped to get a compact model. Statements can also be broken down to model control flow within.
Directed edges - possibility the program execution goes from end of one region DIRECTLY to the beginning of another.
What are Linear Code Sequence and Jumps (LCSJ)?
Subpaths of a control flow graph from one branch to another. There is a lookup table with From, Sequence of blocks, To.
What are interprocedural control flow graphs?
Also called call graphs, they have Nodes that represent procedures (methods, c functions) and Edges that represent CALLS relation. Can often overestimate the CALLS relation. You can have context sensitive graphs that
Why do interprocedural control flow graphs overestimate CALLS relations?
The static graph includes calls through dynamic bindings that never occur in execution.
Context sensitive vs insensitive call graphs?
Sensitive - the most precise type, means that for every procedure the graph contains a node for each call stack the procedure can be activated with. Insensitive - only one node for each procedure.
