Explain unstructured loops in detail?

Loops are one of the most important of the languages like C and C++. They have greatly reduced the drudgery of the programmers and developers which would otherwise have made the programming of a software system or application more hectic. The necessity of the loops cannot be ignored when it comes to the repetition of a particular executable statement or a block of statements in a program. 

In other words,

Say we have the below written statement in C++ programming language that we need to print only one time:

“hello! Welcome to C++ programming”

To print it one time we shall write the code like this:

Cout<<”hello! Welcome to C++ programming\n”;

Say now you need to print this statement a 100 times! What you are going to do- write the above C++ statement a 100 times? No! Certainly not! This is unfeasible and a complete waste of time! So what is the alternative that we have? Yes of course we have the “loops”. 

Using loop we will have to write only a small code instead of writing that C++ statement again and again for 100 times. Using loop we shall write like this:

For( int i = 1; i <=100; i++ )

{

Cout<<”hello! Welcome to C++ programming\n”;

}

The above loop is a for loop and it will the statement that we wish to be printed 100 times. See to how much extent our task has been reduced! This would not have been possible without loops. 

Loops generally are classified based on their types namely in to:

1. The while loop
2. The for loop
3. The do – while loop

But based up on their structure, they are classified in to two types:

1. Structured loops and
2. Unstructured loops

This article is all about the unstructured loops. We shall discuss them in detail. 

The Unstructured Loops

- The unstructured loops can be defined as the loops that are void of a single header or a node in the control flow graph that has all the nodes dominating the whole loop body. 

- The main problem that arises with these unstructured loops is of managing them.

- Managing them is such a hectic task.

- For analyzing the unstructured loops the programmers, developers and researchers have come up with so many ways but none of them seems to be so efficient.

- One of the ways is to use a control flow graph along with the scope graph corresponding to the function containing the unstructured loop to be analyzed. 

- This method involves attaching of each and every iteration counter with each of the loop header.

- Attaching the iteration counters in such a way can cause over estimation of the control flow. 

- So to overcome this problem, the iteration counters are attached to each basic block and this helps a great deal in achieving a lot of flow information. Even this way results in some disadvantage! 

- Therefore another method of managing the unstructured loops has been developed. 

- Another method has been developed for transforming the unstructured loops in structured ones. 

- If one looks at the unstructured loop with a view of the control flow graph they seem to have entry edges to one or more than one node all over the loop. 

- In another way we can say that an unstructured consists of parts of several different loops. 

- Several structured loops can also be merged in to an unstructured loop with the help of a code size optimizing compiler.

- A straight way has been developed for the elimination of the unstructured loops which is creating a scope with a single header for each entry of the loop. 

How does a DU path segment play a role in data flow testing?

Whenever you would have came across the topic of data flow testing, you surely would have heard about the term “du path segment” but still not familiar with it! This article if focussed up on the du path segments and what role it has got to play in the data flow testing. 

We will discuss the du path segments under the context of data flow testing and not as a separate topic so that it becomes easy for you to understand. 

The whole process of data flow testing is guided by a control flow graph that apart from just guiding the testing process also helps in rooting out the anomalies present in the data flow. With all the anomalies being already discovered one can now design better path selection strategies taking in to consideration these data flow anomalies. 

There are nine possible anomalies combinations as mentioned below:

1. dd: harmless but suspicious
2. dk: might be a bug
3. du: a normal case
4. kd: a normal situation
5. kk: harmless but might be containing bugs
6. ku: a bug or error
7. ud: not a bug because of re- assignment
8. uk: a normal situation
9. uu: a normal situation

For data flow testing some data object states and usage have been defined as mentioned below:

1.      Defined, initialized, created à d

2.      Killed, undefined, unreleased àk

3.      Used for:

(a)    Calculations à c

(b)   Predictions à p

Terminology associated with Data Flow Testing

Almost all the strategies that are implemented for the data flow testing are structural in nature. There are certain terminologies associated with the data flow testing as stated below:

1. Definition clear path segment
2. Loop free path segment
3. Simple path segment and lastly
4. Du path

What is a DU path Segment?

- DU path segment can be defined as a path segment which is simple and definition clear if and only if the last link or node of the path has a use of the variable x.

Let us take an example to make the concept of du path segment clearer. 

- Suppose a du path for a variable X exists between two nodes namely A and B such that the last link between the two nodes consists of a computational use of the variable X. 

- This path is definition clear and simple. 

- If there exists a node C  at the last but one position that is the path is having a predicate use and the path from the node A to node C is definition clear and does not contain any loop. 

- Several strategies have been defined for carrying out the data flow testing like:

1. ADUP or all du paths strategy
2. AU or all uses strategy
3. APU+ C or all p uses/ some c uses strategy
4. ACU +P or all c uses/ some p uses strategy
5. AD or all definitions strategy
6. APU or all predicate uses strategy
7. ACU or all computational uses strategy

Strategy for DU Path Strategy

We shall describe in detail here only the ADUP or all du paths strategy. 

- This strategy is considered to be one of the most reliable and strongest data flow testing strategy. 

- It involves the use or exercising of all the du paths included in the definition of the variables that have defined to every use of the definition.

- All the du paths suppose to be a strong criterion for testing but it does not involve as many tests as it seems.

- Simultaneously many criterion are satisfied by one test for several definitions and uses of the variables.

How does a definition use association play a role in data flow testing?

Definition use association is one of the terms that appear at the scene of data flow testing and quite many of us are unaware of it. This article is all about the concepts of the definition use associations and what role does they have got to play in the data flow testing. 

The definition use association forms quite an important part of the data flow testing. Let us see how! 

First we are going to discuss some concepts of the data flow testing in regard with the definition use associations and then we will discuss the role of the definition use associations in the data flow testing. 

About Data Flow Testing

- A control flow graph is an important tool that is used by the data flow testing so that the anomalies related to the data can be explored. 

- A proper path selection strategy is what that is required for detection of such anomalies. 

- The path strategy which is to be used can be decided on the basis of the data flow anomalies discovered earlier. 

- Data flow testing is nothing but a family of path testing strategies through the control of a software program or application. 

- The path testing is required so that the sequence of possible events associated with the objects’ status can be explored.

- It is necessary that you keep the number of paths sufficient and sensible so that no object is left without initialization and without being used at least once in its life time without carrying out unnecessary testing. 

- Data flow testing is comprised of two types of anomaly detection namely:

1. Static analysis: It is carried out on the program code without its actual execution. It involves finding syntax errors.

2. Dynamic analysis: It is carried out on a program while it is in a state of execution. It involves finding the logical errors.

- The data objects have been categorized in to several categories so as to make data flow testing much easy:

1. Defined, created, initialized (d)
2. Killed, undefined, released (k)
3. Used (u): in calculations (c)
4. In predicates (p)

Anomalies discovered by the static analysis are meant to be handled by the compiler itself. But the static analysis and the dynamic analysis do not suffice altogether. A rigorous path testing is required. 

About Definition Use Associations

- The definition use associations or the “du segments” are the path segments whose last links have a use of variable X and are simple and definition clear. 

- Typically  a definition use association is a combination of triple elements (x, d, u) where:

1. X is the variable
2. D is the node consisting of a definition of variable x
3. U is either a predicate node or a statement depending up on the case and consists of a use of x.

- A sub path from d to u is also included in the flow graph with no definition of variable x occurring in between the d and u. 

- Below mentioned are some examples of the def use associations:

1. (x, 3, 4)
2. (x, 1, 4)
3. (y, 2, (4, t))
4. (z, 2, (3, t)) etc.

- Some of the most common data flow testing strategies are:

1. All uses (AU)
2. All DU paths (ADUP) and many more.

- First advice for effective data flow testing would be to resolve all the data flow anomalies discovered above. 

- Carrying out data flow operations on the same variable and within the same routines can also reap you good results. 

- It is advisable to use defined types and strong typing wherever it is possible in the program. 

How does a definition clear path play a role in data flow testing?

Definition clear path is a quite less heard term! This article is focussed up on the concept of definition clear path and what role do it plays in the data flow testing. First let us define what is a definition clear path in actual. 

"A definition clear path as it can made out from the term itself that it is a path through which other variables cannot be defined or through which other variable definitions cannot be made."

To make the meaning of definition clear path clearer we shall look up to an example:

- Suppose X be a variable declared or appearing in a software program or procedure. 

- Suppose there is a path $which\; do\; not\; contain\; any\; nodes\; with\; definition\; of\; the\; variable\; X.$

- Such a path not containing any variable definitions has been termed as a definition clear path. 

We can now define this definition clear path as a path between the two nodes namely A and B, with X being defined in A and an use in node B and there exists no other definition of variable X between the two nodes present in the path. 

Let us see another example to explore another type of definition clear path that can exist. 

- Suppose the above same variable X be defined at a node A along with an use defined at the another node B.

- Suppose the path formed by these two nodes A and B does not appears in the sub path, then such a path is also defined as a definition clear path for the X variable defined by the nodes A and B if the variable X is not defined in the sub path. 

- There is another common name for the definition clear path which is “def- clear path”. 

Now let us talk about the role that the definition clear path plays in the data flow testing. Actually in the data flow testing, there are three types of coverage that have to be provided namely:

1. Statement coverage
2. Branch coverage and lastly
3. Path coverage

Basically problems are faced with the path selection process. A definition of the variable X reaches a use if and only if there exists a sub path such that the sub path is a definition clear path with respect to the variable X. The path selection in the data flow testing is based up on the two criteria:

1. Rapps and Weyuker criteria: Under these criteria the definition clear sub paths from definitions to uses are listed.
2. Laski and Korel criteria: Under these criteria the various combinations that reach uses at a node via some sub path are listed.

How does Definition Clear Path play a role in Data Flow Testing?

- Definition clear paths have been known to make remarkable improvements in the control flow techniques for data flow testing.

- A rational is obtained for which there is a need to take in to consideration all the combinations of the sub paths. 

- The “all uses” is the most commonly preferred criteria.

- There are some paths in a program that are infeasible and it is these paths that pose a big problem in the data flow testing. 

- The path testing strategies are based up on the data flow anomalies. 

- Enough paths are required to be tested so that it is ensured that every object in the program has been initialized before use and have been used at least once during the program execution. 

- For a complete data flow testing it is required that definition clear paths are executed by the test cases from each node that contains a defined variable.

How does a loop free path segment play a role in data flow testing?

The loop free path segments form a very important terminology in the path of data flow testing. But many of us are not well familiar with the concept of loop free path segments and the role that they have got to play in the data flow testing or path testing. In this article we have tried to explain in the easiest way possible the concept of the loop free path and the role it plays in the data flow testing. 

Before taking up the topic of the loop free path segment and its role in data flow testing we shall discuss a little about the data flow testing. 

The control flow graph is the best tool that the data flow testing can use in exploring all the weird or unreasonable things that can affect the data objects. These weird and unreasonable things are nothing but the anomalies.

Till now nine types of anomalies have been defined as mentioned below:

1. dd: harmless but suspicious
2. dk: might be a bug
3. du: a normal case
4. kd: a normal situation
5. kk: harmless but might be containing bugs
6. ku: a bug or error
7. ud: not a bug because of re- assignment
8. uk: a normal situation
9. uu: a normal situation

 - If these anomalies are taken in to consideration, one can develop very effective and reliable path selection strategies which can be then used in filling the gaps that are present in between the branch testing and the complete path testing. 

- The strategies that are followed for carrying out a data flow test are based up on the selection of the paths via the flow of control of the software system or application.

- These path selection strategies are quite useful when it comes to exploring the sequences of the events that are in a way related to the status of the data objects. 

- The paths are so selected that they cover up all the objects, i.e. they ensure the initialization of each and every data object before it is used in the program and also that they are used for a minimum of one time. 

Categories of Data Objects

- The data objects have been categorized in to three different categories for making the path selection process easier:

1. Defined, created, initialized (d)
2. Killed, undefined, released (k)
3. Used:

(a)    In calculations (c)

(b)   In predicates (p)

- An object is said to be defined whenever it has an occurrence in a data declaration or is assigned with a new value or is dynamically allocated. 

- On the other hand an object is said to be used whenever it becomes a part of a predicate or a calculation. - The anomaly detection process relies heavily on the following two anomaly detection techniques:

1. Static anomaly detection (responsible for syntax errors) and
2. Dynamic anomaly detection (responsible for logical errors).

What are Loop Free Path Segments

- Now coming to the loop free path segments, this is a terminology that is usually used under the context of the data flow modelling. 

- Loop free path segments are discovered using the control flow graph.

- The loop free path segments are basically a derivative of the simple path segments.

- It depends on the simple path segment that whether or not it is a loop free path segment also. 

- If the simple path segment consisting of two nodes A and B is having loop in both the nodes, then it cannot be called as a loop free path. 

- Loop free paths are the simple paths segments consisting of loop only in one of the either nodes.