Transcript Chapter 10 - University of Wisconsin

Chapter 10:
Structured Analysis
Omar Meqdadi
SE 3860 Lecture 10
Department of Computer Science and Software Engineering
University of Wisconsin-Platteville
Topic Covered




Why Structured Analysis?
Data Dictionary
Structured Diagrams
Static Program Slicing
2
Reverse Engineering

Recall:
 Forward
Engineering is the traditional process of moving
from high-level abstractions and logical, implementationindependent designs to the physical implementation of a
system.
 Reverse Engineering is the process of analyzing a subject
system to


Identify the system's components and their interrelationships
and
Create representations of the system in another form or a
higher level of abstraction.
3
Structured Analysis



Structured analysis : static representations of the code
Part of the impact analysis of required change
Why
 Help
maintainer gain initial understanding of a software
system
 Determine which functions call which other functions and
what data are passed.
 Keep track of data identifiers and how and where they are
used
4
Data Dictionary


Data dictionary is a repository of information about the
data in a system.
It is usually alphabetical
 Easily
lookup information about the usage of the constants,
variables and structures.

Items may have a secondary key
 Help
us look up an identifier in other ways other than name
 Secondary key Example: function name, logical
relationships
Data Dictionary

A Data Diction may contains:
A
description of the data
 A formal definition of the data, which may include:

Data type (and size for strings, arrays, structures, etc.)
Initial and/or default value
Range of values (valid values)
Logical relationships with other fields

Cross references to other functions, which use this data



Data Dictionary

Example:
Data id Description
Type
Initial
value
Range
Logical
Function
Cross Reference
relation-ships
score
A test score
float
N/a
(0,100)
N/a
processOneSection
Max( num1)
sum
Sum of scores
Float
0.0
GE 0.0
The more scores
and higher the
scores the larger
sum will be
main
processOneSection

processClassTotals
A data dictionary can be the start of a database schema.
7
Data Dictionary Generation

Automated tools that helps generating the data dictionary
from the source code
 Static program

Slicing
Generate dictionary for every variable of the existing system
 Many
CASE workbenches support data dictionaries.
Structure Diagrams

Graphical representation of existing system
 Traceability Graph
 Flow



Chart (Graph)
Show all branches
Show all execution paths
Linear code sequences
 Structure Call
Graph
 Program Dependency Graph
Traceability Graph (TG)




TG is a graphical representation of existing system
TG shows the relationships among work products (
requirements, design, code, and test cases)
TG is used to find the impact of a given maintenance
change
TG contains two edge types:
 Horizontal: relationships between
different work products
 Vertical: relationships between entities within the same
kind of work
TG Example:
Analysis of TG Example 1:

Impact Analysis : from slide 11 , if some changes are
made to the requirement object R4, the results of the
horizontal traceability and vertical traceability are
Analysis of TG

Changes in one part of the software system may have
direct impacts or indirect impacts on other parts.
 Direct
impact: A direct impact relation exists between two
entities if they are connected by an edge in the TG
 Indirect impact: If an entity A directly impacts another
entity B and B directly impacts a third entity C, then we
can say that A indirectly impacts C.
Analysis of TG

For a node A in a TG:
 in-degree of
A (in(A)) : the number of edges for which A is
the destination node


Represents the number of nodes having a direct impact on A
Low in-degrees of nodes are an indication of a good design
 out-degree of
A (out(A)): the number of edges for which A
is the source


Represents the number of nodes which are likely to be
modified because of A
To minimize the impact of a change, out-degrees of nodes
need to be made small
Analysis of TG Example2:

Consider the following figure
 Each
SLO represents a
software artifact connected to
other artifacts.
 Dependencies among SLOs
are represented by arrows.
 The out-degree of SLO1 is 3
 The in-degree of SLO1 is 4
 SLO1 has an indirect impact
from SLO8 and a direct
impact from SLO9.
Flow Graph Example- Binary Search
int search ( int key, int [] elemArray)
{
int bottom = 0;
int top = elemArray.length - 1;
int mid;
int result = -1;
while ( bottom <= top )
{
mid = (top + bottom) / 2;
if (elemArray [mid] == key)
{
result = mid;
return result;
} // if part
else
{
if (elemArray [mid] < key)
bottom = mid + 1;
else
top = mid - 1;
}
} //while loop
return result;
} // search
1
bottom > top
Binary Search Flow Graph
while bottom < = top
2
3
if (elemArray [mid] == key
4
8
5
(if (elemArray [mid]< key
6
9
7
Flow Graph Terminologies

Dominators:
 Given


a Flow Graph with nodes D and N:
D dominates N if every path from the initial node to N goes
through D
Properties of dominance:
Every node dominates itself
 Initial node dominates all others

Flow Graph Terminologies

Dominators- Example:
Flow Graph Terminologies

Dominator Tree:
 In


a dominator tree of a flow graph
The initial node N is the root of the Flow Graph
The parent of a node X is its immediate dominator (i.e., the
last dominator of X on any path)

The parent (immediate dominator) for X is unique
Flow Graph Terminologies

Dominator Tree - Example:
Flow Graph Application: Loops

Algorithm for finding loops from the Flow Graph:
 Given


a Flow Graph:
Find back edges in the graph
Given a back edge N  D , loop corresponding to this edge is:
{D} + {N} + { all nodes that can reach the N without going
f
through D }
Flow Graph Application: Loops

Example 1:
Flow Graph Application: Loops

Example 2: Finding Nested Loops
L2  B, S2
L1  A,S1,B,S2
L2 nested in L1
While A do
S1
While B do
S2
Endwhile
Endwhile
Flow Graph Terminologies

Post-Dominators :
 Given

a Flow Graph with nodes PD and N:
PD post dominates N if every path from N to the final nodes
goes through PD
Flow Graph Terminologies

Post-Dominator - Example:
Flow Graph Terminologies

Post-Dominator Tree:
 In


a post-dominator tree of a flow graph
The initial node N is the exit node of the Flow Graph
The parent of a node X is its immediate post dominator (i.e.,
the first post dominator of X on any path)

The parent (immediate post dominator) for X is unique
Flow Graph Terminologies

Post-Dominator Tree - Example:
Structure Call Graph


A call graph is a directed graph in which a node
represents a function, a component, or a method.
An edge between two nodes A and B means that A
invokes B
 Each
edge is annotated with all parameters that are
exchanged between the calling and called function.

Use the parameter id of the called function
Structure Call Graph

Each edge has arrow indicating its parameter’s usage
(IN, OUT , INOUT).
 An
edge with an arrow pointing into the called function
would be an IN parameter.
 An edge with an arrow pointing into the calling function
would be an OUT parameter.
 INOUT parameters would have arrows point into both the
calling and called functions.
 Example:
Example: Structure Call Graph
//------- main () -----------------------------------------------int main()
{
float sum, sumAll = 0.0;
int sections = 1; // section number being processed
int count, countAll = 0; // count of students
//------------------------------------// PRIMING READ FOR eof LOOP
cin >> count; // how many scores in a section
while ( ! cin.eof() ) // loop till eof
{
//---------------------------------// PROCESS ONE SECTION OF GRADES
processOneSection( sum, sections, count );
//---------------------------------// ACCUMULATE CLASS SUM AND COUNT
processClassTotals( sumAll, countAll, sum, count );
cin >> count;
sections++;
} //------ END WHILE
displayClassResults( sections, countAll, sumAll );
cout << endl << "That's all the sections!! Normal Termination.";
return 0;
}
Example: Structure Call Graph
//-----------------------------------------------------------------// Function to process a section's worth of data
// PARAMS (
OUT, IN,
IN )
void processOneSection( float & sum, int sections, int count )
{
int a_count, b_count, c_count, d_count, f_count, loopEnd;
float score, hi_score, lo_score;
cout << "Scores for section " << sections << endl;
//--------------------------------------------// INTIALIZE SECTION ACCUMULATORS AND COUNTERS
initSection( a_count, b_count, c_count, d_count, f_count,
loopEnd, sum, hi_score, lo_score );
while ( loopEnd < count ) // loop to read section scores
{
cin >> score;
//-------------------------------// COUNT A's, B's, etc.
determineGrade( score, a_count, b_count, c_count, d_count, f_count );
//--------------------------------// FIND HIGHEST AND LOWEST SCORES
hi_score = max ( score, hi_score );
min ( lo_score, score );
//----------------------------------// SECTION SUM OF SCORES FOR AVERAGE
// to compute the average
sum += score;
loopEnd++; // COUNT CONTROL LOOP UPDATE
}//------ END WHILE -- SECTION END -------//--------------------------------// DISPLAY THIS SECTION'S RESULTS
displaySectionResults( a_count, b_count, c_count, d_count, f_count,
count, sum, hi_score, lo_score );
Example: Structure Call Graph
// function to return the larger of two numbers
// PARAMS (
IN,
IN )
float max( float num1, float num2 )
{
float max;
if ( num1 < num2 )
max = num2;
else
max = num1;
return max;
} //--------------END OF max( )--------------------------------------
Example: Structure Call Graph
main( )
sum
sections,
count
processOneSection( )
//reads and processed one
sections worth of grades.
max
num1 , num2
max()
How do changes propagate?
Assume the following change:
char G (void) {
int x;
char y;
….
if (x == 0)
y = true;
else
y = false;
return y;
}
35
char G (void) {
int x;
char y;
….
if (x != 0)
y = true;
else
y = false;
return y;
}
How do changes propagate?
Assume the following main:
void main (void) {
….
if ( G() == true)
}
36
Do1;
else
Do2;
….
Q: Do we modify
the main because of
the change in G?
Call Graph : Impact of Change


Programmers use call graphs to understand the
potential impacts that a software change may have.
Change impact assumption:
 Some
change in method p has the potential to impact
changes in all nodes reachable from p in the call graph.
 Change propagates between methods through



Parameters(call by reference )
Return values
Global variables
Call Graph Example
Impact of G:
Main,A,B,H
int G (void)
Impact of C:
E,F,D
G
v
main
r
int H (int x)
v
H
void C (void)
B
r
r
C
A
r: ref. edge
v: val. edge
(none):
call edge
38
v, r
void A (struct_type &x)
r
F
E
D
Program Dependency Graph(PDG)

In the PDG of a program:
(i) each simple statement is represented by a node, also called
a vertex;
(ii) each predicate expression is represented by a node.

Types of edges in a PDG:
 Data
dependency (solid edge): from node A to node B
indicates that computations performed at node A are
directly dependent upon the results of computations
performed at node B .
 Control dependency (dashed edge) : from node A to node B
indicates that node A may execute based on the result of
evaluation of a condition at B .
PDG Example
Program Slicing

Program Slice : a subset of a program that contains the
relevant code to the computation of interest
 The
parts of a program which have a direct or indirect
effect on the computation of interest
 Program slicing provides a useful way of filtering out
irrelevant code.

A slice S(V, N) produces the portions of the program that
contribute to the value of the variable V at statement N
 (V,N

) is called a slicing criterion
Application:

Debugging
 Testing
Program Slicing

Program Slicing types:
 Static: does
not make assumptions regarding the input
 Dynamic: assumes fixed input for a program (next chapter)
 Backward: S(V,N): all statements and predicates in the
program that may affect the value of variable V at
statement N
 Forward: S(V,N): all statements and predicates in the
program that may be affected by the value of variable V at
statement N
Static Backward Slicing
void main ( ) {
1. int I=0;
2. int sum=0;
3. while (I<N) {
4. sum=add(sum,I);
5. I=add(I,1);
6. }
7. cout << sum << endl;
8. cout << I << endl;
}

S(V,N) : Slice of
variable V at
statement ( node ) N
is the set of
statements involved
in computing V’s
value at N.
Example: S < I , 8 >
Static Backward Slicing Example:
int main() {
1. int max, min, avg;
2. int val, sum, num;
3.
4. cin >> val ;
5. max = val;
6. min = val;
7. sum = val;
8. num = 1;
9.
10. while(val >= 0)
11. {
12. if (max < val)
13.
max = val;
14. if (min > val)
15.
min = val;
16. sum += val;
17. Add (num);
18. cin >> val;
19. }
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
avg = sum / num;
cout << max << endl;
cout << min << endl;
cout << avg <<endl;
cout << sum << endl;
cout << num << endl;
return 0;
}
void Add (int & x){
++x;
}
Example : Slice S(avg, 24)
int main() {
1. int avg;
2. int val, sum, num;
4. cin >> val;
7. sum = val;
8. num = 1;
10. while(val >= 0)
11. {
16. sum += val;
17. Add (num);
18. cin >> val;
19. }
21. avg = sum / num;
24. cout << avg << endl;
28. }
29. void Add (int & x){
30. ++x;
31. }
Static Backward Slicing

Using PDG

A static program slice is identified from a PDG as follows:
for a variable V at node N, identify all reaching
definitions of V.
 find all nodes in the PDG which are reachable from
those nodes.
 The visited nodes in the traversal process constitute the
desired slice.



Consider the program in the slide 40 and variable Y at S10.
First, find all the reaching definitions of Y at node S10 – and the
answer is the set of nodes {S3, S6 and S8}.
 Next, find the set of all nodes which are reachable from {S3, S6
and S8} – and the answer is the set {S1, S2, S3, S5, S6, S8}.
Static Forward Slicing

Example1: Find Static Forward Slicing: S ( sum , 3 )
1. cin >> n ;
2. i = 1;
3. sum = 0;
4. product = 1;
5. while (i <= n){
6. sum = sum + i;
7. product = product * i ;
8. i = i + 1;}
9. cout << sum ;
10. cout << product ;
Static Forward Slicing

Example1: S ( sum , 3 )
1. cin >> n ;
2. i = 1;
3. sum = 0;
4. product = 1;
5. while (i <= n){
6. sum = sum + i;
7. product = product * i ;
8. i = i + 1;}
9. cout << sum ;
10. cout << product ;
Static Forward Slicing

Example2: Static Forward Slicing: S ( n , 1 )
1. cin >> n ;
2. i = 1;
3. sum = 0;
4. product = 1;
5. while (i <= n){
6. sum = sum + i;
7. product = product * i ;
8. i = i + 1;}
9. cout << sum ;
10. cout << product ;
Static Slicing : Problem

Problems:
 Static analysis
is very imprecise
 Inefficient in identifying the errors and bugs.

Solution:
 Dynamic
Slicing