Most software development, testing and debugging tools use flow graphs analysis techniques. The simplest weight we can give to a link is a name. Using link names as weights, we then convert the graphical flow graph into an equivalent algebraic like expressions which denotes the set of all possible paths from entry to exit for the flow graph. Every link of a graph can be given a name.
The link name will be denoted by lower case italic letters. In tracing a path or path segment through a flow graph, you traverse a succession of link names. The name of the path or path segment that corresponds to those links is expressed naturally by concatenating those link names. For example, if you traverse links a,b,c and d along some path, the name for that path segment is abcd.
This path name is also called a path product. Figure 5. Denote that set of paths by Upper case letter such as X,Y. From Figure 5. Any expression that consists of path names and "OR"s and which denotes a set of paths between two nodes is called a " Path Expression.
The path product is Associative. The zeroth power of a link name, path product, or path expression is also needed for completeness. It is denoted by the numeral "1" and denotes the "path" whose length is zero - that is, the path that doesn't have any links. Links a and b in Figure 5. For example, in Figure 5. Say that the loop consists of a single link b.
The procedure is a node-by-node removal algorithm. The steps in Reduction Algorithm are as follows: Combine all serial links by multiplying their path expressions. Combine all parallel links by adding their path expressions.
Replace it with a set of equivalent links whose path expressions correspond to all the ways you can form a product of the set of inlinks with the set of outlinks of that node. Combine any remaining serial links by multiplying their path expressions.
Remove all self-loops as in step 3. Does the graph consist of a single link between the entry node and the exit node? If yes, then the path expression for that link is a path expression for the original flowgraph; otherwise, return to step 4. A flowgraph can have many equivalent path expressions between a given pair of nodes; that is, there are many different ways to generate the set of all paths between two nodes without affecting the content of that set.
The appearance of the path expression depends, in general, on the order in which nodes are removed. It removes a node, thereby reducing the number of nodes by one. Successive applications of this step eventually get you down to one entry and one exit node. Every application follows this common pattern: Convert the program or graph into a path expression. Identify a property of interest and derive an appropriate set of "arithmetic" rules that characterizes the property.
Replace the link names by the link weights for the property of interest. The path expression has now been converted to an expression in some algebra, such as ordinary algebra, regular expressions, or boolean algebra. This algebraic expression summarizes the property of interest over the set of all paths.
Simplify or evaluate the resulting "algebraic" expression to answer the question you asked. The question is not simple. Here are some ways you could ask it: What is the maximum number of different paths possible? What is the fewest number of paths possible? How many different paths are there really? What is the average number of paths?
Determining the actual number of different paths is an inherently difficult problem because there could be unachievable paths resulting from correlated and dependent predicates. If we know both of these numbers maximum and minimum number of possible paths we have a good idea of how complete our testing is. Asking for "the average number of paths" is meaningless.
Also mark each loop with the maximum number of times that loop can be taken. If the answer is infinite, you might as well stop the analysis because it is clear that the maximum number of paths will be infinite.
There are three cases of interest: parallel links, serial links, and loops. This arithmetic is an ordinary algebra. The weight is the number of paths in each set. Each link represents a single link and consequently is given a weight of "1" to start.
B: Combine the first pair of parallel loops outside the loop and also the pair in the outer loop. C: Multiply the things out and remove nodes to clear the clutter. For the Inner Loop: D: Calculate the total weight of inner loop, which can execute a min.
Average rating 4. Vote count: No votes so far! Be the first to rate this post. Tags software testing methodologies lecture notes software testing methodologies notes software testing methodologies pdf stm download STM Notes stm pdf. How useful was this post? The effectiveness of path testing rapidly deteriorates as the size of the software aggregate under test increases. It uses the elements named process blocks, decisions, and junctions.
The flow graph is similar to the earlier flowchart, with which it is not to be confused. Flow Graph Elements: A flow graph contains four different types of elements. It is a sequence of statements such that if any one of statement of the block is executed, then all statement thereof are executed.
Formally, a process block is a piece of straight line code of one statement or hundreds of statements. A process has one entry and one exit. Decisions: A decision is a program point at which the control flow can diverge.
Machine language conditional branch and conditional skip instructions are examples of decisions. Most of the decisions are two-way but some are three way branches in control flow.
Case Statements: A case statement is a multi-way branch or decisions. From the point of view of test design, there are no differences between Decisions and Case Statements Junctions: A junction is a point in the program where the control flow can merge.
Figure 2. In flow graphs, we don't show the details of what is in a process block. In flow charts every part of the process block is drawn. The flowchart focuses on process steps, where as the flow graph focuses on control flow of the program. The act of drawing a control flow graph is a useful tool that can help us clarify the control flow and data flow issues. The notation changes made in creation of control flow graphs: The process boxes weren't really needed. There is an implied process on every line joining junctions and decisions.
We don't need to know the specifics of the decisions, just the fact that there is a branch. The specific target label names aren't important-just the fact that they exist.
So we can replace them by simple numbers. To understand this, we will go through an example Figure 2. The program's corresponding flowchart Figure 2. The first step in translating the program to a flowchart is shown in Figure 2. Note that complexity has increased, clarity has decreased, and that we had to add auxiliary labels LOOP, XX, and YY , which have no actual program counterpart.
In Figure 2. We now have a control flowgraph. But this representation is still too busy. We simplify the notation further to achieve Figure 2. The way to work with control flowgraphs is to use the simplest possible representation - that is, no more information than you need to correlate back to the source program or PDL. In linked list representation, each node has a name and there is an entry on the list for each link in the flow graph.
Linked List representation of Flow Graph: Figure 2. You cant always associate the parts of a program in a unique way with flowgraph parts because many program structures, such as if-then-else constructs, consists of a combination of decisions, junctions, and processes. The translation from a flowgraph element to a statement and vice versa is not always unique. See Figure 2. An improper translation from flowgraph to code during coding can lead to bugs, and improper translation during the test design lead to missing test cases and causes undiscovered bugs.
Automatically produced by a flowcharting program based on a mechanical analysis of the source code. Semi automatically produced by a flow charting program based in part on structural analysis of the source code and in part on directions given by the programmer. There are relatively few control flow graph generators. A path may go through several junctions, processes, or decisions, one or more times. Paths consists of segments. The segment is a link - a single process that lies between two nodes.
A path segment is succession of consecutive links that belongs to some path. The length of path measured by the number of links in it and not by the number of the instructions or statements executed along that path. The name of a path is the name of the nodes along the path.
Every decision doubles the number of potential paths. And every loop multiplies the number of potential paths by the number of different iteration values possible for the loop. Defining complete testing: Exercise every path from entry to exit Exercise every statement or instruction at least once Exercise every branch and case statement, in each direction at least once If prescription 1 is followed then 2 and 3 are automatically followed.
But it is impractical for most routines. It can be done for the routines that have no loops, in which it is equivalent to 2 and 3 prescriptions.
Following prescription 2 and executing every statement, but not every branch, would not reveal the bug in the following incorrect version: A negative value produces the correct answer.
Every statement can be executed, but if the test cases do not force each branch to be taken, the bug can remain hidden. The next example uses a test based on executing each branch but does not force the execution of all statements: The hidden loop around label is not revealed by tests based on prescription 3 alone because no test forces the execution of statement and the following GOTO statement.
Furthermore, label is not flagged by the compiler as an unreferenced label and the subsequent GOTO does not refer to an undefined label. A Static Analysis that is, an analysis based on examining the source code or structure cannot determine whether a piece of code is or is not reachable. There could be subroutine calls with parameters that are subroutine labels, or in the above example there could be a GOTO that targeted label but could never achieve a value that would send the program to that label.
Only a Dynamic Analysis that is, an analysis based on the code's behavior while running - which is to say, to all intents and purposes, testing can determine whether code is reachable or not and therefore distinguish between the ideal structure we think we have and the actual, buggy structure. A set of tests that does this is not complete in an absolute sense, but it is complete in the sense that anything less must leave something untested.
So we have explored three different testing criteria or strategies out of a potentially infinite family of strategies. This is the strongest criterion in the path testing strategy family: it is generally impossible to achieve. Statement Testing P 1 : Execute all statements in the program at least once under some test.
We denote this by C1. This is the weakest criterion in the family: testing less than this for new software is unconscionable unprincipled or can not be accepted and should be criminalized. Branch Testing P 2 : Execute enough tests to assure that every branch alternative has been exercised at least once under some test. For structured software, branch testing and therefore branch coverage strictly includes statement coverage. We denote branch coverage by C2.
Commonsense and Strategies: Branch and statement coverage are accepted today as the minimum mandatory testing requirement. The question "why not use a judicious sampling of paths? Not testing a piece of a code leaves a residue of bugs in the program in proportion to the size of the untested code and the probability of bugs.
The high probability paths are always thoroughly tested if only to demonstrate that the system works properly. Which paths to be tested?
The question of what is the fewest number of such paths is interesting to the designer of test tools that help automate the path testing, but it is not crucial to the pragmatic practical design of tests.
It is better to make many simple paths than a few complicated paths.
0コメント