Control Flow Graphs

Control Flow Graphs:

A control-flow graph (CFG) is a representation, using graph notation, of all paths that might be traversed through a program during its execution. The control-flow graph is due to Frances E. Allen, who notes that Reese T. Prosser used boolean connectivity matrices for flow analysis before.

In a control-flow graph each node in the graph represents a basic block, i.e. a straight-line piece of code without any jumps or jump targets; jump targets start a block, and jumps end a block. Directed edges are used to represent jumps in the control flow.

Steps:

Number all the statements of a program.

Numbered statements represent nodes of the control flow graph.

An edge from one node to another node exists:

if execution of the statement representing the first node can result in transfer of control to the other node. 

Sequence: 

1. a=5;
2. b=a*b-1

Selection:

1. if(a>b) then
2. c=3;
3. Else
4. c=5;
5. c=c*c;

Iteration:

1. while(a>b){
2. b=b*a;
3. b=b-1;
4. }
5. c=b+d;

Path:

• A path through a program:
  • a node and edge sequence from the starting node to a terminal node of the control flow graph.
• There may be several terminal nodes for the program.
• Any path through the program: 
• introducing at least one new node that is not included in any other independent paths.
• Provides a practical way of determining the maximum number of linearly independent paths in a program.

Cyclomatic Complexity Measures

Cyclomatic  Complexity Measures:

McCabe proposed the cyclomatic number, V (G) of graph theory as an indicator of software complexity. The cyclomatic number is equal to the number of linearly independent paths through a program in its graph representation.

Cyclomatic complexity can be used in two ways, to:

• Limit code complexity.
• Determine the number of test cases required.

Cyclomatic complexity can be one of the most difficult software quality metrics to understand. And that makes it difficult to calculate.

 For a program control graph G, cyclomatic number, V (G), is given as:

              V (G) = E - N + 2 * P

E = The number of edges in graphs G

N = The number of nodes in graphs G

P = The number of connected components in graph G.

Properties:

1. V (G) is the maximum number of independent paths in the graph
2. V (G) >=1
3. G will have one path if V (G) = 1
4. Minimize complexity to 10

Example:

Another Example:

Advantages:

• Gives complexity of various designs
• Computed early in life cycle
• Easy to apply
• Measures minimum effort

Disadvantages: 

• Measures program’s control complexity and not the data complexity
• Nested conditional structures are harder to understand
• Ignore the size of the program

Function Point (FP) Based Measures

Function  Point  (FP)  Based  Measures,  

Internal Logical Files

It is a user identifiable group of logically related data or control information that resides entirely within the application boundary. The primary intent of an ILF is to hold data maintained through one or more elementary processes of the application being counted.

External Interface Files

It is a user identifiable group of logically related data or control information that is used by the application for reference purposes only. The data resides entirely outside the application boundary and is maintained in an ILF by another application. An EIF has the inherent meaning that it is externally maintained, an interface has to be developed to get the data from the file.

There are three types of transaction functions.

• External Inputs
• External Outputs
• External Inquiries

Transaction functions are made up of the processes that are exchanged between the user, the external applications and the application being measured.

External Inputs

External Inputs (EI) - is an elementary process in which data crosses the boundary from outside to inside. This data is coming external to the application. The data may come from a data input screen or another application.It is a transaction function in which Data goes “into” the application from outside the boundary to inside. This data is coming external to the application.

• Data may come from a data input screen or another application.
• An EI is how an application gets information.
• Data can be either control information or business information.
• Data may be used to maintain one or more Internal Logical Files.
• If the data is control information, it does not have to update an Internal Logical File. 

External Outputs

It is a transaction function in which data comes “out” of the system. Additionally, an EO may update an ILF. The data creates reports or output files sent to other applications.

External Inquiries

It is a transaction function with both input and output components that result in data retrieval.

Advantages:

• Size oriented metrics
• Language dependent
• Understood by the non technical user
• To estimate cost and resources required for software development 

Disadvantages:

• Manually Counting Process
• Difficult to Understand
• Requires Experience

Halstead’s Software Science

Halstead’s  Software  Science:

Statement:

A computer program is an implementation of an algorithm considered to be a collection of tokens which can be classified as either operators or operand.

• All software science metrics can be defined in terms of these basic symbols. These symbols are called as a token.
• The basic measures are
  • n1 = count of unique operators.
  • n2 = count of unique operands.
  • N1 = count of total occurrences of operators.
  • N2 = count of total occurrence of operands.
  • Size of the program can be expressed as N = N1 + N2.
• Program Volume (V)

The unit of measurement of volume is the standard unit for size "bits." It is the actual size of a program if a uniform binary encoding for the vocabulary is used.        V=N*log2n

• Program Level (L)

The value of L ranges between zero and one, with L=1 representing a program written at the highest possible level (i.e., with minimum size).

        L=V*/V

• Program Difficulty

The difficulty level or error-proneness (D) of the program is proportional to the number of the unique operator in the program.D= (n1/2) * (N2/n2)

• Programming Effort (E)

The unit of measurement of E is elementary mental discriminations.

    E=V/L=D*V

• Estimated Program Length

According to Halstead, The first Hypothesis of software science is that the length of a well-structured program is a function only of the number of unique operators and operands.  N=N1+N2.And estimated program length is denoted by N^

      N^ = n1log2n1 + n2log2n2

• Potential Minimum Volume

The potential minimum volume V* is defined as the volume of the most short program in which a problem can be coded.

     V* = (2 + n2*) * log2 (2 + n2*)

Here, n2* is the count of unique input and output parameters

• Size of Vocabulary (n)

The size of the vocabulary of a program, which consists of the number of unique tokens used to build a program, is defined as: n=n1+n2

Where n =vocabulary of a program

n1=number of unique operators

n2=number of unique operands

• Language Level - Shows the algorithm implementation program language level. The same algorithm demands additional effort if it is written in a low-level program language. For example, it is easier to program in Pascal than in Assembler.

        L' = V / D / D

lambda = L * V* = L2 * V

Advantages:

• Predicts error rate.
• Predicts maintenance effort
• Simple to calculate
• Measure overall quality
• Used for any language

Disadvantages:

• Depends on complete code
• Complexity increases as program level decreases
• Difficult to compute

Various Size Oriented Measures

Various   Size   Oriented   Measures: 

These are derived by normalizing quality and productivity measures by considering the size of software that has been produced.

Choose LOC as normalization value.Then we can develop a set of simple size-oriented metrics:

• Errors per KLOC
• Defects per KLOC
• $ per KLOC
• Page of documentation per KLOC
• Errors per Person-Months
• LOC per Person-Months
• $ per page of documentation

Function - Oriented Metrics:

• Uses a measure of the functionality delivered by the application as a normalization value.
• Functionality cannot be measured directly,it must be derived indirectly using other direct measures.A measure called Function Point.

Software Measurement and Metrics

Software   Measurement   and   Metrics:  

• It refers to numerical data related to software development. Strongly support software project management activities.
• Measurement is fundamental to any engineering discipline and can be directly observable quantities or can be derived from one.
• Software Metrics - Broad range of measurements for computer software Software Process - Measurement can be applied to improve it on a continuous basis Software Project - Measurement can be applied in estimation, quality control, productivity assessment & project control
• Measurement can be used by software engineers in decision making.

 

• Measure - Quantitative indication of the extent, amount, dimension, capacity or size of some attribute of a product or process
• Measurement - The act of determining a measure
• Metric - A quantitative measure of the degree to which a system, component, or process possesses a given attribute
• Process metrics are measures of the software development process, such as Used in estimation techniques & other technical work. Metrics collected from past projects are used as a basis from which effort and time estimates are made for current software projects.
• Overall development time: Type of methodology used Process metrics are collected across all projects and over long periods of time. Their intent is to provide indicators that lead to long-term software process improvement. 
• To improve any process, the rational way is: Measure Specific attributes of the process. Derive meaningful metrics from these attributes. Use these metrics to provide indicators. The indicators lead to a strategy for improvement
• Direct Metrics: Easy to collect, Execution speed, memory size, defects, etc.
• Indirect Metrics: More difficult to assess & can be measured indirectly only.
• As a project proceeds, actual values of human & calendar time expended are compared to the original estimates.

Top-Down and Bottom-Up Design

Top-Down  and Bottom-Up   Design:

Top Down Design

• We know that a system is composed of more than one subsystem and it contains a number of components. Further, these subsystems and components may have their own set of sub-system and components and create hierarchical structure in the system.
• Top-down design takes the whole software system as one entity and then decomposes it to achieve more than one sub-system or component based on some characteristics. Each sub-system or component is then treated as a system and decomposed further. 
• This process keeps on running until the lowest level of the system in the top-down hierarchy is achieved.
• They allow us to quickly and efficiently specify, design, synthesize and verify designs ready for fabrication. The key to these methodologies is synthesis, which relies on a mapping between the logical functions we use in a design and the physical circuits that realize the functions.

Characteristics of Top-Down Design:

• Top-down design can be perceived as visionary. Because top-down designs are not constrained by current work practice, they can turn out startlingly different and even futuristic designs, which shows how top-down design can be visionary.
• Top-down design is heavily driven by domain knowledge. Designers need extensive domain knowledge to be able to abstract the nature of work in that domain. This usually translates to the need for designers to envision multiple work activity instances in that domain.
• Being a potential user in the domain is good for a designer

Bottom-up Design

• The bottom up design model starts with most specific and basic components. It proceeds with composing higher level components by using basic or lower level components.
• It keeps creating higher level components until the desired system is not evolved as one single component. With each higher level, the amount of abstraction is increased.
• Any design method in which the most primitive operations are specified first and the combined later into progressively larger units until the whole problem can be solved: the converse of TOP-DOWN DESIGN. 
• For example, a communications program might be built by first writing a routine to fetch a single byte from the communications port and working up from that.
• Bottom-up strategy is more suitable when a system needs to be created from some existing system, where the basic primitives can be used in the newer system.
• Both, top-down and bottom-up approaches are not practical individually. Instead, a good combination of both is used.

Top Down	Bottom Up
A module cannot be tested in isolation because they invoke some other modules. To allow the modules to be tested before their subordinates have been coded, stubs simulate the behavior of the subordinates.	It starts from the bottom of the hierarchy. First the modules at the very bottom, which have no subordinates, are tested. Then these modules are combined with higher-level modules for testing. At any stage of testing all the subordinate modules exist and have been tested earlier.
Here,we start by testing the top of the hierarchy and we incrementally add modules that it calls and then test the new combined system. This approach of testing requires stubs to be written. A stub is a dummy routine that simulates a module.	Drivers are needed to set up the appropriate environment and invoke the module. It is the job of the driver to invoke the module under testing with the different set of test cases
Targets given by executives	Executives set the direction and define the mission
Long execution time	Short execution time
More stable and accurate at the aggregate level	Higher accuracy at the granular level.

Object Oriented Design

Object  Oriented  Design,  

• Object-oriented design is the process of planning a system of interacting objects for the purpose of solving a software problem. It is one approach to software design.
• In the object-oriented design method, the system is viewed as a collection of objects (i.e., entities). 

• The state is distributed among the objects, and each object handles its state data. For example, in a Library Automation Software, each library representative may be a separate object with its data and functions to operate on these data. 
• The tasks defined for one purpose cannot refer or change data of other objects. Objects have their internal data which represent their state. Similar objects create a class.
• In the object-oriented approach, the focus is on capturing the structure and behavior of information systems into small modules that combine both data and process. The main aim of Object Oriented Design (OOD) is to improve the quality and productivity of system analysis and design by making it more usable.

Design Strategies

Design  Strategies: 

 

Function  Oriented  Design:

• Function Oriented Design is an approach to software design where the design is decomposed into a set of interacting units where each unit has a clearly defined function.
• Relies on identifying functions which transform inputs to outputs.
• Practised informally since programming began 

• Thousands of systems have been developed using this approach 
• Supported directly by most programming languages 

• Most design methods are functional in their approach 
• CASE tools are available for design support 

Techniques used by Function Oriented Design are:

• Data Flow Diagram(A data flow diagram (DFD) maps out the flow of information for any process or system. )
• Data Dictionaries(Data dictionaries are simply repositories to store information about all data items defined in DFDs. At the requirement stage, data dictionaries contain data items.)
• Structure Charts(Components are read from top to bottom and left to right. When a module calls another, it views the called module as black box, passing required parameters and receiving results)
• Pseudo Codes(It uses keywords and indentation. Pseudo codes are used as replacement for flow charts. It decreases the amount of documentation required.)