3 Analytical Techniques

No product of human intellect comes out right the first time. We rewrite sentences, rip out knitting stitches, replant gardens, remodel houses, and repair bridges. Why should software be any different?

—Ruth Wiener

This third chapter of the Advanced Level Syllabus – Technical Test Analyst is concerned with analytical techniques (which includes both static analysis and dynamic analysis). This chapter contains three sections:

1. Introduction

2. Static Analysis

3. Dynamic Analysis

3.1 Introduction

In the last chapter, you saw a number of different white-box (structure-based) ways to detect defects, all of which require the tester to execute code to force failures to show themselves. In this chapter, we will discuss several analytical techniques that can expose defects in different ways. The first of these is called static analysis.

We examined this topic briefly at the Foundation level; how to apply tools to find defects, anomalies, standards violations, and a whole host of maintainability issues without executing a line of the code. In the Advanced syllabus, ISTQB opens up the term to apply to more than just tool use. The definition of static analysis, as given in the Advanced Syllabus, is:

Static analysis encompasses the analytical testing that can occur without executing the software. Because the software is not executing, it is examined either by a tool or by a person to determine if it will process correctly when it is executed. This static view of the software allows detailed analysis without having to create the data and preconditions that would cause the scenario to be exercised.

Contrast that with the “official definition” found in the latest ISTQB glossary:

Analysis of software development artifacts, e.g., requirements or code, carried out without execution of these software development artifacts. Static analysis is usually carried out by means of a supporting tool.

It may be that the glossary definition is a bit too restricting. While tools are likely to be used most of the time, there certainly could be times when we do some static analysis manually.

We will examine such topics as control flow analysis, data flow analysis, compliance to standards, certain code maintainability improvement techniques, and call graphing.

Finally, in this chapter, we will discuss dynamic analysis, wherein we utilize tools while executing system code to help us find a range of failures that we might otherwise miss.

Remember to review the benefits of reviews and static analysis from the Foundation; we will try not to cover the same materials. In Chapter 5 we will further discuss reviews.

3.2 Static Analysis

3.2.1 Control Flow Analysis

We discussed control flow testing in the last chapter, mainly as a way to determine structural coverage. One of the ways we discussed control flow graphs was in reference to path testing. In that section, we started looking at cyclomatic complexity and Thomas McCabe’s research into what complexity means to software testing.

It is now common wisdom that the more complex the code is, the more likely it is to have hidden defects. This was not always considered, however. In his original 1976 paper, Thomas McCabe cited the (then new) practice of limiting the physical size of programs through modularization. A common technique he cited was writing a 50-line program that consisted of 25 consecutive if-then statements. He pointed out that such a program could have as many as 33.5 million distinct control paths, few of which were likely to get tested. He presented several examples of modules that were poorly structured having cyclomatic complexity values ranging from 16 to 64 and argued that such modules tended to be quite buggy. Then he gave examples of developers who consistently wrote low complexity modules—in the 3 to 7 cyclomatic complexity range—who regularly had far lower defect density.

In his paper, McCabe pointed out an anomaly with cyclomatic complexity analysis that we should discuss here.

Figure 3–1 Hexadecimal converter code

Refer to Figure 3–1, our old friend the hexadecimal converter code, which we introduced in Chapter 2. Following Boris Beizer’s suggestions, we created a control flow graph, which we re-create here in Figure 3–2.

Figure 3–2 Control flow graph (following Beizer)

Let’s look at a different kind of flow graph of that same code to analyze its cyclomatic complexity. See Figure 3–3.

Once we have the graph, we can calculate the cyclomatic complexity for the code.

There are 9 nodes (bubbles) and 14 edges (arrows). So using the formula we discussed in Chapter 2:

That is, using McCabe’s cyclomatic complexity analysis to determine the basis set of tests we need for minimal testing of this module, we come up with seven tests. Those seven tests will guarantee us 100 percent of both statement and decision coverage.

Hmmmmm.

Figure 3–3 Cyclomatic flow graph for hex converter code

If you look back at Beizer’s method of path analysis in Chapter 2, we seemed to show that we could achieve 100 percent statement and decision coverage with five tests. Why should a McCabe cyclomatic directed control graph need more tests to achieve 100 percent branch coverage than one suggested by Beizer?

It turns out that the complexity of switch/case statements can play havoc with complexity discussions. So we need to extend our discussion of complexity. McCabe actually noted this problem in his original paper:

The only situation in which this limit (cyclomatic complexity limit of 10) has seemed unreasonable is when a large number of independent cases followed a selection function (a large case statement), which was allowed.¹

What McCabe said is that, for reasons too deep to discuss here, switch/case statements maybe should get special dispensation when dealing with complexity. So, let’s look at switch statements and see why they are special.

The code we have been using for our hexadecimal converter code (Figure 3–1) contains the following switch statement (we have removed the non-interesting linear code):

switch (c) {
	case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':
	xxxxxx;
	break;
	case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
	xxxxxx;
	break;
	case 'A': case 'B': case 'C': case 'D': case 'E': case 'F':
	xxxxxx;
	break;
		default:
		break;
}

Because of the way this code is written, there are four different paths through the switch statement, as follows:

One path if the inputted character is a digit (‘0’..‘9’)

One path if the inputted character is an uppercase hex-legal character (‘A’..‘F’)

One path if the inputted character is a lowercase legal hex character (‘a’..‘f’)

One path if the inputted character is any other legal (but non-hex) character

We certainly could rewrite this code in a myriad of ways, each of which might appear to have a different number of paths through it. For example, in Delphi, we might use the characteristic of sets to make it easier to understand:

if (c IN ('0'..'9')) then begin
	xxxxx
end;
else if (c IN ('A'..'F')) then begin
	xxxxxx
end;
else if (c IN ('a'..'f') then begin
	xxxxxx
end;

This code appears to only have three paths through it, but of course that is illusory. We can take any one of the three paths, or we can still take the fourth by not having a legal hex value.

If the programmer was a novice, they might use an if/else ladder, which would get very ugly with a huge cyclomatic complexity hit:

if (c=='0') {
	xxxxxx;
} else if (c=='1'):
	xxxxx;
} else if (c=='2'):
	xxxxx;
}
etc.

This particular mess would add 22 new paths to the rest of the module. Of course, any real programmer who saw this mess in a review would grab the miscreant by the suspenders and instruct them on good coding practices, right?

Interestingly enough, with the way the original code was written

case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8':

case '9'…

case 'a': case 'b': case 'c': case 'd': case 'e': case 'f'…

case 'A': case 'B': case 'C': case 'D': case 'E': case 'F'…

there is a really good chance that the compiler will actually generate a unique path for every “case” token in each string anyway. That means that the source code would be deemed to have four paths, but the generated object code would still contain 22—or more—unique paths through it. The Delphi example would likely generate object code for only the four paths.

It would also be possible to use a complex data structure such as a hash or dictionary to represent this code rather than using the switch statement. That option would hide the complexity in an external call to the data-structure code making the choice.

From the preceding discussion, we can see that there are many different ways to code this specific functionality. All of those coding styles can have different cyclomatic complexity measures. But at the end of the day, all of the different ways of writing this code are going to take just about the same effort to test. This would appear to mean that cyclomatic complexity might not be the best measure to determine the amount of effort it actually takes to test a module.

So, is excessive cyclomatic complexity truly the enemy? In Chapter 2 we cited a NIST study that seemed to imply that.

We must understand that there are actually two different ways that we can look at complexity. One is the way we have been looking at it: how many tests do we need to get adequate coverage of the structure of the code? This conversation has much to do with the problems built into the design of the human brain.

In 1956, George A. Miller, a cognitive psychologist, wrote a paper called “The Magical Number Seven, Plus or Minus Two.”² In it he discussed the limits of human memory and specifically referred to short-term memory. While many of the individual details have been challenged over the years, it does appear that most people have problems keeping more than seven or eight chunks of information, sometimes called a working set, in their short-term memory for any appreciable time.

How does this affect our discussion of cyclomatic complexity? Our human brains appear to be spectacularly unsuited to keeping many complex concepts in our head at once. We tend to forget some chunks when we try to input too many others. Programmers have long recognized this concept and even have an acronym for it: KISS (keep it simple, stupid). The more complex the code in a module, the more stuff a test analyst needs to keep in their head when designing test cases. A cyclomatic complexity of 10 is about the outside limit for a tester to be able to grasp all of the nuances of the code that they want to test. We are not saying this is a definitive hard limit; just a common-sense rule of thumb (we will discuss this in more detail later).

The second way to look at complexity in software is much more intricate; McCabe called it essential complexity. Beyond the basis number of tests we need to test a module to a particular level, what is the reliability, maintainability, understandability, and so on of the module? Essential complexity looks for coding techniques that are not well structured; examples include entering or breaking out of a loop at more than one place, having multiple return statements in the module, and throwing an exception inside a function.

Certain programming languages can make testing much harder based on their features. For example, the programming language Scheme actually has—as a feature—the ability to traverse nondeterministic paths (via use of the operator amb) to facilitate searching problem spaces without having to program the search directly. Testing such code, however, becomes much more difficult because there is no guarantee which path is being traversed when.

A simplified definition we can use is that essential complexity measures how much complexity we have left after we have removed the well-structured basis paths. According to McCabe, we can work through the structured paths of a module (i.e., those paths that have a single entry and single exit point) and essentially ignore their complexity (since they could be replaced with a call to an external subroutine). All such structured paths in the module now are seen to have an essential complexity of one. Note that a switch/case statement has a single entry and exit, hence McCabe’s dismissal of it as contributing to cyclomatic complexity more than any if/else statement.

At this point, any paths not yet counted are, by definition, nonstructured. Each nonstructured path then adds to the essential complexity value.

Sometimes, unstructured code makes a lot of sense to the understandability of the code. For example, suppose we are analyzing a function that accepts arguments when called. If you were to code the module such that the first thing you do is check to make sure each argument is correct—and, if not, immediately return an error to the caller—this would be considered unstructured. But, in our opinion, that extra complexity would actually make the code clearer.

The point of this discussion is to illustrate that cyclomatic complexity is not the be-all and end-all of how difficult it is to test a module. If the essential complexity is low (i.e., the code is well structured), it will be relative easy to refactor into smaller modules that have lower cyclomatic complexity. If, on the other hand, the essential complexity is high, the module will be harder to refactor successfully and will likely be less reliable and harder to maintain and understand.

Is this an argument for using well-structured code whenever possible? The way we look at it, if you smell smoke, you don’t have to wait to actually see the flames before getting worried. We believe that there is likely enough evidence for us to err on the conservative side and try to avoid unnecessary complexity. There may be certain techniques—such as noted above—where slightly unstructured code might make sense.

Of course, in software engineering, there are no free lunches. Every decision we make will have trade-offs, some of which may be undesirable. As someone who once wrote operating system code, Jamie can attest that sometimes high complexity is essential. When his organization tried to write some critical OS modules using a low-complexity approach, the trade-off was that the speed of execution was too slow—by a factor of 10. When they got rid of the nice structure and just wrote highly complex, tightly coupled code, it executed fast enough for their needs. To be sure, maintenance was highly problematic; it took much longer to bring the code to a high level of quality than it took for earlier, less complex modules they had written. As a wise man once said, “Ya pays your money and ya takes your choice.”

McCabe’s original paper suggested that 10 was a “reasonable but not magic upper limit” for cyclomatic complexity. Over the years, a lot of research has been done on acceptable levels of cyclomatic complexity; there appears to be general agreement with McCabe’s recommended limit of 10. The National Institute of Standards and Technology (NIST) agreed with this complexity upper end, although it noted that certain modules should be permitted to reach an upper end of 15, as follows:

The precise number to use as a limit, however, remains somewhat controversial. The original limit of 10 as proposed by McCabe has significant supporting evidence, but limits as high as 15 have been used successfully as well. Limits over 10 should be reserved for projects that have several operational advantages over typical projects, for example experienced staff, formal design, a modern programming language, structured programming, code walkthroughs, and a comprehensive test plan. In other words, an organization can pick a complexity limit greater than 10, but only if it is sure it knows what it’s doing and is willing to devote the additional testing effort required by more complex modules.³

To make this analysis worthwhile, every organization that is worried about complexity should also measure the essential complexity and limit that also.

To complete this discussion on complexity we will look at the output of an automation tool that measures complexity, a much more realistic way to deal with it—instead of using control flow graphs.

The cyclomatic complexity graphs in Figure 3–4 come from the McCabe IQ tool, showing the difference between simple and complex code. Remember that code that is very complex is not necessarily wrong, any more than simple code is always correct. But all things being equal, if we can make our code less complex, we will likely have fewer bugs and certainly should gain higher maintainability. By graphically seeing exactly which regions are the most complex, we can focus both testing and reengineering on the modules that are most likely to need it. We could conceivably have spent the time to map this out manually; however, tools are at their most useful when they allow us to be more productive by automating the low-level work for us.

Figure 3–4 Simple vs. complex graphs

Figure 3–4 was a close-up view of two different modules; Figure 3–5 is a more expansive view of our system. This image shows the modules for a section of the system we are testing, both for how they are interconnected and at individual module complexity. Green modules here have low complexity ratings, yellow are considered somewhat complex, and red means highly complex. A highly complex module as a “leaf” node, not interconnected with other modules, might be of less immediate concern than a somewhat complex module in the middle of everything. Without such a static analysis tool to help do the complexity analysis, however, we have very little in the way of options to compare where we should put more time and engineering effort.

While these tools tend to be somewhat pricey, their cost should be compared with the price tag of releasing a system that might collapse under real usage.

Figure 3–5 Module complexity view

3.2.2 Data Flow Analysis

Our next static analysis topic is data flow analysis; this covers a variety of techniques for gathering information about the possible set of values that data can take during the execution of the system. While control flow analysis is concerned with the paths that an execution thread may take through a code module, data flow analysis is about the life cycle of the data itself.

If we consider that a program is designed to create, set, read, evaluate (and make decisions on), and destroy data, then we must consider the errors that could occur during those processes.

Possible errors include performing the correct action on a data variable at the wrong time in its life cycle, doing the wrong thing at the right time, or the trifecta, doing the wrong thing to the wrong data at the wrong time.

In Boris Beizer’s book Software Testing Techniques, when discussing why we might want to perform data flow testing, he quoted an even earlier work as follows:

It is our belief that, just as one would not feel confident about a program without executing every statement in it as part of some test, one should not feel confident about a program without having seen the effect of using the value produced by each and every computation.⁴

Here are some examples of data flow errors:

• Assigning an incorrect or invalid value to a variable. These kinds of errors include data-type conversion issues where the compiler allows a conversion but there are side effects that are undesirable.

• Incorrect input results in the assignment of invalid values.

• Failure to define a variable before using its value elsewhere.

• Incorrect path taken due to the incorrect or unexpected value used in a control predicate.

• Trying to use a variable after it is destroyed or out of scope.

• Setting a variable and then redefining it before it is used.

• Side effects of changing a value when the scope is not fully understood. For example, a global or static variable’s change may cause ripples to other processes or modules in the system.

• Treating an argument variable passed in by value as if it were passed in by reference (or vice versa).

Many data flow issues are related to the programming languages being used.

Since some languages allow a programmer to implicitly declare variables simply by naming and using them, a misspelling might cause a subtle bug in otherwise solid code. Other languages use very strong data typing, where each variable must be explicitly declared before use, but then allow the programmer to “cast” the variable to another data type assuming that the programmer knows what they are doing (sometimes a dodgy assumption, we testers think).

Different languages have data scoping rules that can interact in very subtle ways. Jamie often finds himself making mistakes in C++ because of its scoping rules. A variable may be declared global or local, static or stack-based; it could even be specified that the variables be kept in registers to increase computation speed. A good rule of thumb for testers is to remember that, when giving power to the programmer by having special ways of dealing with data, they will sometimes make mistakes.

Complex languages also tend to have ‘gotchas.’ For example, C and C++ have two different operators that look much the same. The single equal sign (=) is an assignment operator, while the double equal sign (==) is a Boolean operator. When it’s used in a Boolean expression, you would expect that the equal-equal (“is equivalent to” operator) sign would be legal and the single equal sign (assignment operator) would not be. But, the output of an assignment, for some arcane reason, evaluates to a Boolean TRUE. So it is really easy to change the value of a variable unexpectedly by writing (X = 7) when the programmer meant (X==7). As previously mentioned, this particular bug is a really good reason to perform static analysis using tools.

The fact is that not all data anomalies are defects. Clever programmers often do exotic things, and sometimes there are even good reasons to do them. Written in a certain way, the code may execute faster. A good technical test analyst should be able to investigate the way data is used, no matter how good the programmer; even great programmers generate bugs.

Unfortunately, as we shall see, data flow analysis is not a universal remedy for all of the ways defects can occur. Sometimes the static code will not contain enough information to determine whether a bug exists. For example, the static data may simply be a pointer into a dynamic structure that does not exist until runtime. We may not be able to tell when another process or thread is going to change the variable—race conditions are extremely difficult to track down even when testing dynamically.

In complex code using interrupts to guide control flow, or when there are multiple levels of prioritization that may occur, leaving the operating system to decide what will execute when, static testing is pretty much guaranteed not to find all of the interesting bugs that can occur.

It is important to remember that testing is a filtering process. We find some bugs with this technique, some with that, some with another. There are many times that data flow analysis will find defects that might otherwise ship. As always, we use the techniques that we can afford, based on the context of the project we are testing. Data flow analysis is one more weapon in our testing arsenal.

3.2.2.1 Define-Use Pairs

Data flow notation comes in a few different flavors; we are going to look at one of them here called define-use pair notation. In the glossary, this is called “definition-use pair,” and we have seen it as “set-use.”

To use this notation, we split the life cycle of a data variable into three separate patterns:

d: This stands for the time when the variable is created, defined, initialized, or changed.

u: This stands for used. The variable may be used in a computation or in a decision predicate.

k: This stands for killed or destroyed, or the variable has gone out of scope.

These three atomic patterns are then combined to show a data flow. A ~ (tilde) is often used to show the first or last action that can occur.

Table 3–1 Data flow combinations

Referring to Table 3–1, there are 15 potential combinations of the atomic actions we are concerned with, as follows:

1. ~d or first define. This is the normal way a variable is originated; it is declared. Note that this particular data flow analysis methodology is somewhat hazy as to whether at this point the value is defined or not. A variable is declared to allocate space in memory for it; at that point, however, the value the variable holds is unknown (although some languages have a default value that is assigned, often zero or NULL). The variable needs to be set before it is read (or in other words, must be used in the left side of an assignment statement before it is used in the right side of an assignment statement, as an argument to a function, or in a decision predicate). Other data flow schemes have a special state for a ~d; when first declared, it holds a value of “uninitialized.”

2. du or define-use. This is the normal way a variable is used. Defined first and then used in an assignment or decision predicate. Of course, this depends on using the correct data type and size—which should be checked in a code review.

3. dk or define-kill. This is a likely bug; the variable was defined and then killed off. The question must be asked as to why it was defined. Is it dead? Or was there a thought of using it but the wrong variable was actually used in later code? If creating the variable caused a desirable side effect to occur, this might be done purposefully.

4. ~u or first use. This is a potential bug because the data was used without a known definition. It may not be a bug because the definition may have occurred at a different scope. For example, it may be a global variable, set in a different routine. This should be considered dodgy and should be investigated by the tester. After all, race conditions may mean that the variable never does get initialized in some cases. In addition, the best practice is to limit the use of global variables to a few very special purposes.

5. ud or use-define. This is allowed where the data is read and then set to a different value. This can all occur in the same statement where the use is on the right side of an assignment and the definition is the left side of the statement, such as X = X + 1, a simple increment of the value.

6. uk or use-kill. This is expected and normal behavior.

7. ~k or first kill. This is a potential bug, where the variable is killed before it is defined. It may simply be dead code, or it might be a serious failure waiting to happen, such as when a dynamically allocated variable is destroyed before actually being created, which would cause a runtime error.

8. ku or kill-use. This is always a serious defect where the programmer has tried to use the variable after it has gone out of scope or been destroyed. For static variables, the compiler will normally catch this defect; for dynamically allocated variables, it may cause a serious runtime error.

9. kd or kill-define. This is usually allowed where a value is destroyed and then redefined. Some theorists believe this should be disallowed; once a variable is destroyed, bringing it back is begging for trouble. Others don’t believe it should be an issue. Testers should evaluate this one carefully if it is allowed.

10. dd or define-define. In some languages, it is standard to declare a variable and then define it in a different line. In other languages, the variable may be declared and defined in the same line. As you will see in our example, there may be times when this is useful. And sometimes, it may indicate a defect.

11. uu or use-use. This is normal and done all of the time.

12. kk or kill-kill. This is likely to be a bug—especially when using dynamically created data. Once a variable is killed, trying to access it again—even to kill it—will cause a runtime error in most languages.

13. d~ or define last. While this is a potential bug—a dead variable that is never used, it might just be that the variable is meant to be global and will be used elsewhere. The tester should always check all global variable use very carefully. If not a global variable, this may result in a memory leak.

14. u~ or use last. The variable was used but not killed on this path. This may be a potential memory leak if the variable was created dynamically and not killed (deallocated) elsewhere in the code.

15. k~ or kill last. This is the normal case.

Following is an example to show how we use define-use pair analysis.

3.2.2.2 Define-Use Pair Example

Assume a telephone company that provides the following cell-phone plan:

If the customer uses up to 100 minutes (inclusive), then there is a flat fee of $40.00 for the plan. For all minutes used from 101 to 200 minutes (inclusive), there is an added fee of $0.50 per minute. Any minutes after that used are billed at $0.10 per minute. Finally, if the bill is over $100.00, a 10 percent discount on the entire bill is given.

A good tester might immediately ask the question as to how much is billed if the user does not use the cell phone at all. Our assumption—based on what we have seen in the real world—would be that the user would still have to pay the $40.00. However, the code as given in Figure 3–6 lets the user off completely free if the phone was not used for the month.

Figure 3–6 Cell phone billing example

Line 3 looks at the number of minutes billed. If none were billed, the initial $40.00 is not billed; instead, it evaluates to FALSE and a $0.00 bill is sent. Frankly, we want to do business with this phone company, and if we worked there, we would flag this as an error.

Assuming a little time was used, however, the bill is set to $40.00 in line 4. In line 6 we check to see if there were more than 100 minutes used; in line 7 we check if more than 200 minutes were used. If not, we simply calculate the extra minutes over 100 and add $0.50 for each one. If over 200 minutes, we take the base bill, add $50.00 for the first extra 100 minutes, and then bill $0.10 per minute for all extra minutes. Finally, we calculate the discount if the bill is over $100.00.

For each variable, we create a define-use pattern list that tracks all the changes to that variable through the module. In each case we track the code line(s) that an action takes place in.

For the code in Figure 3–6, here is the data flow information for the variable Usage:

Table 3–2 Variable usage define-use pattern list

1. The Usage variable is created in line 1. It is actually a formal parameter that is passed in as an argument when the function is called. In most languages, this will be a variable that is created on the stack and immediately set to the passed-in value.⁵

2. There is one du (define-use) pair at (1-3). This is simply saying that the variable is defined in line 1 and used in line 3 in the predicate for the if statement. This is expected behavior.

3. Each time that Usage is used following the previous du pair, it will be a uu (use-use) pair until it is defined again or killed.

4. So it is used in line 3 and line 6. Then comes (6-7), (7-8), and (7-11). Notice there is no (8-11) pair because under no circumstances can we execute that path. Line 7 is in the TRUE branch of the conditional and line 11 is in the FALSE path.

5. Under uk (use-kill), there are three possible pairs that we must deal with.

• (6-19) is possible when Usage has a value of 100 or less. We use it in line 6 and then the next touch is when the function ends. At that time, the stack-frame is unrolled and the variable goes away.

• (8-19) is possible when Usage is between 101 and 200 inclusive. The value of Bill is set and then we return.

• (11-19) is possible when Usage is greater than 200.

• Note that (3-19) and (7-19) are not possible because in each case, we must touch Usage again before it is destroyed. For line 3, we must use it again in line 6. For line 7, we must use it in either line 8 or 11.

6. Finally, at line 19 we have a kill last on Usage because the stack frame is removed.

It is a little more complicated when we look at the local variable Bill as shown in Table 3–3.

Table 3–3 Variable Bill define-use pattern list

1. ~d signifies that this is the first time this variable is defined. This is normal for a local variable declaration.

2. dd (define-define) could be considered suspicious. Generally, you don’t want to see a variable redefined before it is used. However, in this case it is fine; we want to make sure that Bill is defined before first usage even though it could be redefined. Note that if we did not set the value in line 2, then if there were no phone minutes at all, we would have returned an undefined value at the end. It might be zero—or it might not be. In some languages it is not permissible to assign a value in the same statement that a variable is declared in. In such a case, the if() statement on line 3 would likely be given an else clause where Bill would be set to the value of 0. The way this code is currently written is likely more efficient than having another jump for the else clause.

3. du (define-use) has a variety of usages.

• (2-18) happens when there are no phone minutes and ensures that we do not return an undefined value.

• (4-8) occurs when Usage is between 101 and 200 inclusive. Please note that the “use” part of it is on the right side of the statement—not the left side. The value in Bill must be retrieved to perform the calculation and then it is accessed again (after the calculation) to store it.

• (4-11) occurs when the Usage is over 200 minutes. Again, it is used on the right side of the statement, not the left.

• (11-12) occurs when we reset the value (in the left side of the statement on line 11) and then turn around and use it in the conditional in line 12.

4. ud (use-define) occurs when we assign a new value to a variable. Notice that in lines 8, 11, and 13, we assign new values to the variable Bill. In each case, we also use the old value for Bill in calculating the new value. Note that in line 4, we do not use the value of Bill in the right side of the statement. However, because we do not actually use Bill before that line, it is not a ud pair; instead, as mentioned in (2), it is a dd pair. In each case, this is considered acceptable behavior.

5. uu (use-use) occurs in lines (12-13). In this case, the value of Bill is used in the decision expression in line 12 and then reused in the right side of the statement in line 13. It can also occur at (12-18) if the value of Bill is less than $100.

6. uk (use-kill) can only occur once in this code (18-19) since all execution is serialized through line 18.

7. And finally, the k~ (kill last) occurs when the function ends at line 19. Since the local variable goes out of scope automatically when the function returns, it is killed.

Once the data flow patterns are defined, testing becomes a relatively simple case of selecting data such that each defined pair is covered. Of course, this does not guarantee that all data-related bugs will be uncovered via this testing. Remember the factorial example in Chapter 2? Data flow testing would tell us the code was sound; unfortunately, it would not tell us that when we input a value of 13 or higher, the loop would blow up.

A wise mentor who taught Jamie a great deal about testing once said, “If you want a guarantee, buy a used car!”

If you followed the previous discussion, where we were trying to do our analysis directly from the code, you might guess where we are going next. Code is confusing. Often, it is conceptually easier to go to a control flow diagram and perform the data flow analysis from that.

In Figure 3–7 we see the control flow diagram that matches the code. Make sure you match this to the code to ensure that you understand the conversion. We will use this in an exercise directly. From this, we can build an annotated control flow diagram for any variable found in the code.

Figure 3–7 Control flow diagram for example

Using the control flow diagram from Figure 3–7, we can build an annotated flow graph for the variable Bill as seen in Figure 3–8. It is much easier to find the data connections when laid out this way, we believe. Note that we have simply labeled each element of the flow with information about Bill based on d-u-k values.

Figure 3–8 Annotated flow graph for variable Bill

Table 3–4 Define-use pairs for the variable Bill

From the annotated flow graph, we can create a table of define-use pairs as shown in Table 3–4. To make it more understandable, we have expanded the normal notation (x-y) to show the intervening steps also.

Looking through this table of data flows, we come up with the following:

• One place where we have a first define (line 1)

• One potential bug where we double define (dd) in the flow 1-2-3

• Seven separate du pairs where we define and then use Bill

• Three separate ud pairs where we use and then redefine Bill

• Two separate uu pairs where we use and then reuse Bill

• One uk pair where we use and then kill Bill

• And finally, one place where we kill Bill last

Why use an annotated control flow rather than using the code directly? We almost always find more data flow pairs when looking at a control flow graph than at a piece of code.

3.2.2.3 Data Flow Exercise

Using the control flow and the code previously shown, build an annotated control flow diagram for the variable Usage.

Perform the analysis for Usage, creating a d-u-k table for it.

3.2.2.4 Data Flow Exercise Debrief

Here is the annotated data flow for the code:

Figure 3–9 Annotated flow graph for Usage

Below is the table that represents the data flows.

Table 3–5 Define-use pairs for Usage

• The variable is defined in 0.

• It is first used in 2 (0,1,2 is the path).

• There are four use-use relationships, at (2-3-4), (4-5), (5-6), and (5-9).

• There are five use-kill relationships, at (2-10-11), (4-10-11), (6-7-10-11), (6-7-8-10-11), and (9-10-11).

• There is a final kill at 11.

Note that all of the data flows appear normal.

3.2.2.5 A Data Flow Strategy

What we have examined so far for data flow analysis is a technique for identifying data flows; however, this does not rise to the status of being a full test strategy. In this section, we will examine a number of possible data flow testing strategies that have been devised. Each of these strategies is intended to come up with meaningful testing—short of full path coverage. Since we don’t have infinite time or resources, it is essential to figure out where we can trim testing without losing too much value.

The strategies we will look at all turn on how variables are used in the code. Remember that we have seen two different ways that variables can be used in this chapter: in calculations (called c-use) or in predicate decisions (called puse).

When we say that a variable is used in a calculation, we mean that it shows up on the right-hand side of an assignment statement. For example, consider the following line of code:

Z = A + X;

Both A and X are considered c-use variables; they are brought into the CPU explicitly to be used in a computation where they are algebraically combined and, in this case, assigned to the memory location, Z. In this particular line of code, Z is a define type use, so not of interest to this discussion. Other uses of cuse variables include as pointers, as parts of pointer calculations, and for file reads and writes.

For predicate decision (p-use) variables, the most common usage is when a variable appears directly in a condition expression. Consider this particular line of code:

if (A < X) { }

This is an if() statement where the predicate is (A<X). Both A and X are considered p-use variables. Other p-use examples include variables used as the control variable of a loop, used in expressions used to evaluate the selected branch of a case statement, or used as a pointer to an object that will direct control flow.

In some languages a variable may be used as both p-use and c-use simultaneously; for example a test-and-clear machine language instruction. That type of use is beyond the scope of this book so we will ignore it for now. We will simply assume that each variable usage is one or the other, p-use or c-use.

The first strategy we will look at is also the strongest. That is, it encompasses all of the other strategies that we will discuss. It is called the all du path strategy (ADUP). This strategy requires that every single du path, from every definition of every variable to every use of that variable (both p-use and c-use), be exercised. While that sounds scary, it might not be as bad as it sounds since a single test likely exercises many of the paths.

The second strategy, called all-uses (AU), relaxes the requirement that every path be tested to require that at least one path segment from every definition to every use (both p-use and c-use) that can be reached by that definition be tested. For ADUP coverage, we might have several paths that lead from a definition to a use of the variable, even though those paths do not have any use of the variable in question.

To differentiate the two, consider the following example. Assume a code module wherein a variable X is defined in line 10 and then used in line 100 before being defined again. Further, assume that there is a switch statement with 10 different branches doing something that has nothing to do with the variable X. To achieve ADUP, we would have to have 10 separate tests, one through each branch of the switch statement leading to the use of the variable X. AU coverage would require only 1 test for the du pair, through any single branch of the switch statement.

The all-definitions (AD) strategy requires only that every definition of every variable be covered by at least one use of that variable, regardless of whether it is a p-use or c-use.

The remaining strategies we will discuss differentiate between testing p-use and c-use instances for du pairs.

Two of these strategies are mirror images of each other. These include all puses/some c-uses (APU+C) and all c-uses/some p-uses (ACU+P). Each of these states that for every definition of a specific variable, you must test at least one path from the definition to every use of it. That is, to achieve APU+C coverage, for each variable (and each definition of that variable), test at least one definition-free path (du) to each predicate use of the variable. Likewise, for ACU+P, we must test every variable (and every definition of that variable) with at least one path to each computational use of the variable. Then, if there are definitions not yet covered, fill in with paths to the off-type of use. While the math is beyond the scope of this book, Boris Beizer claims that APU+C is stronger than decision coverage but ACU+P may be weaker or even not comparable to branch coverage.

Two more strategies, all p-uses (APU) and all c-uses (ACU), relax the requirement that we test paths not covered by the p-use or c-use tests. Note that this means some definition-use paths will not be tested.

We fully understand that the previous few paragraphs are information dense. Remember, our overriding desire is to come up with a strategy that gives us the right amount of testing for the context of our project at a cost we can afford. There is a sizable body of research that has been done trying to answer the most important question: Which of these strategies should I use for my project? The correct answer, as so often in testing, is it depends.

A number of books have dedicated a lot of space discussing these strategies in greater detail. A very thorough discussion can be found in The Compiler Design Handbook.⁶ A somewhat more comprehensive discussion can be found in Software Testing Techniques.⁷

Figure 3–10 Rapps/Weyuker hierarchy of coverage metrics

Figure 3–10 may help because it tries to put the preceding discussion into context. At the very top of the structure is all paths—the holy grail of testing which, in any non-trivial system, is impossible to achieve. Below that is ADUP, which gives the very best possible coverage at the highest cost in test cases. Next comes all uses, which will require fewer tests at the cost of less coverage.

At this point, there is a discontinuity between the testing methods. The all c-uses testing (ACU+P and ACU) are shown down the left-hand side of the figure. These are not comparable with their mirror image shown on the right-hand side; mathematically, they are inherently weaker than the other strategies at their same level. The all p-uses (APU+C and APU) are stronger than branch coverage. The all defs (AD) strategy is weaker than APU+C and ACU+P but possibly stronger than APU and ACU.

Figure 3–10 should make the relative bug detection strengths—and also the costs—of these strategies clearer. Bottom line, a technical tester should understand that there are different strategies, and if the context of your project requires a high level of coverage, one of these strategies may be the place to start.

3.2.3 Static Analysis to Improve Maintainability

Many years ago Jamie was doing some work as a C programmer, writing application code for Windows 3.1. As a voracious reader, he subscribed to a multitude of programming periodicals. In one of the journals, there was an interesting repeating feature article that used to excite him as a programmer but scandalize him as a tester. On the last page of the magazine was an obfuscation challenge: who could stick the most functionality in a single line of C code? Each time he got the magazine from the mailbox, it was always the first place he would look.

To be honest, most of the time Jamie was not able to comprehend exactly what the code was supposed to do.

This would be a funny anecdote and a happy memory if code we had tested didn’t so often appear to have been written by a programmer intent on winning the title for obfuscation of the month.

Very often programmers seem to write their code to be elegant—to them. However, this can be problematic if others (who may have to read, change, maintain, or test it) cannot understand it.

We will discuss the quality characteristic of maintainability more thoroughly in Chapter 4. In the following sections, we will discuss the capability of static analysis to help improve maintainability. A great deal of maintainability comes from programmers following a common set of standards and guidelines to ensure that everyone who reads the code can understand it. And, there are static analysis tools that can parse through the code to determine if those standards and guidelines have been followed.

3.2.3.1 Code Parsing Tools

In Figure 3–11, we show the output of a static code parsing tool that is looking for issues that the compiler would not flag because they are not syntactically incorrect.⁸ The code on the left is an example of a very poorly written C language module. The problem is that the code does not necessarily look bad. Many developers figure that as long as the compiler does not throw an error, the code probably is correct. Then they spend hours debugging it when it does not do what they expect. On the right is the output of a tool called Splint, an open-source static analysis tool for C that parsed this code.

Figure 3–11 Code parsing tools

Notice in item 1, the variable c is evaluated before it is set. That is not illegal, just dim-witted. The initial value of variable c is set to whatever random value it was when the code initialized. It probably is not equal to the character ‘x’, and so it will probably work almost every time. Almost! In those few cases when it does initialize to ‘x’, the system will just return, having done nothing. Some programming languages, such as C#, will flag this as an error when compiled; most programming languages allow it. Other programming languages will allow it but also will initialize the value of all variables to zero, which has the effect of preventing this particular problem but creating a certain problem if the value checked in the while condition were to be zero.

In item 2, the code is probably not doing what the user wanted; the static analysis tool is warning that there is no definite end to the loop. This is caused by the semicolon following the while statement. That signifies an empty statement (perfectly legal) but also represents an infinite loop. Many programmers reading this code do not see that the entire body of the while loop consists of the empty statement represented by the semicolon.

Item 3 is a data typing mistake that might cause problems on some architectures and not on others. The output of the common library routine getchar() is a data type int. It is being assigned to a data type char. It probably will work in most instances; years ago, this kind of assignment was common practice. We can foresee problems working with double-byte character sets and some architectures where an int is much larger than a char. The programmer is assuming that the assignment will always go correctly. They might be right...

Items 4 and 5 represent a definite bug. This is a common mistake that anyone new to C is going to make again and again. In C, the assignment operator is a single equal sign (=) while the Boolean equivalence operator is a double equal sign (==). Oops! Rather than seeing if the inputted char is an ‘x’, this code is explicitly setting it to ‘x’. Since the output of the assignment by definition is TRUE, we will return 0 immediately. No matter what character is typed in, this code will see it as an ‘x’.

Even if the Boolean expression was evaluated correctly, even if the assignment of the input was correct between the data types, this code would still not do what the programmer expected. Item 6 points out that a break reserved word was not used after the newline was outputted. That means that the default printf() would also be executed each time, rather than only when a newline or carriage return was entered. That means the formatting of the output would be incorrect.

Many compilers have the ability to return warnings such as we see here with the static analysis tool. Ofttimes, however, the warning messages given by a compiler are obtuse and difficult to understand. Sometimes the warning messages are for conditions that the programmers understand and wrote on purpose. For these and many other reasons, programmers often start ignoring various warning messages from the compiler. Some compilers and static analysis tools allow the user to selectively turn off certain classes of messages to avoid the clutter.

For testers, however, it is likely worth the time to make sure every type of warning is evaluated. The more safety or mission critical the software, the more this is true. Some organizations require that all compiler and static analysis tool warnings be turned over to the test team for evaluation.

Static analysis tools can also be used to check if the tree structure of a website is well balanced. This is important so that the end user can navigate to their intended pages easier, and it simplifies the testing tasks and reduces the amount of maintenance needed on the site by the developers.

3.2.3.2 Standards and Guidelines

Programmers sometimes consider programming standards and guidelines to be wasteful and annoying. We can understand this viewpoint to a limited extent; they are often severely time and resource constrained. Better written and better documented code takes a little more time to write. And, there may be times when standards and guidelines are just too onerous. Project stakeholders, however, should remind programmers that—in the long term—higher maintainability of the system will save time and effort.

Jamie once heard software developers described as the ultimate optimists. No matter how many times they get burned, they always seem to assume that “this time, we’ll get lucky and everything will work correctly.” A lament often heard after a new build turns out to be chock-full of creepy-crawlers: Why is it we never have time to do it right, but we always can take time to do it over?

Perhaps it is time to take the tester’s attitude of professional pessimism seriously and start taking the time to do it right up front.

There are a number of static analysis tools that can be customized to allow local standards and guidelines to be enforced. And, some features might be turned off at certain times if that makes economic or strategic sense. For example, if we are writing an emergency patch, the requirement for following exact commenting guidelines might be relaxed for this session. “Heck, we can fix it tomorrow!” Having said that, in many of the places we have worked, it often seemed that we were always in emergency mode. The operative refrain was always, “We’ll get to that someday!” As Credence Clearwater Revival pointed out, however, “Someday never comes.”

In the following paragraphs, we have recorded some of the standards and guidelines that can be enforced if we were programming in Java and using a static analysis tool called Checkstyle. This open-source tool was created in 2001 and is currently in use around the world.

• Check for embedded Javadoc comments. Javadoc is a protocol for embedding documentation in code that can be parsed and exhibited in HTML format. Essentially, this is a feature that allows an entire organization to write formal documentation for a system. Of course, it only works when every developer includes it in their code.

• Enforce naming conventions to make code self-documenting. For example, functions might be required to be named as action verbs with the return data type encoded in them (e.g., strCalculateHeader(), recPlotPath(), etc.). Constants may be required to be all uppercase. Variables might have their data type encoded (i.e., using Hungarian notation). There are many different naming conventions that have been used; if everyone in an organization were to follow the standards and guidelines, it would be much easier to understand all the code, even if you did not write it.

• Check the cyclomatic complexity of a routine against a specified limit automatically.

• Ensure that required headers are in place. These are often designed to help users pick the right routines to use in their own code rather than rewriting them. Often the headers will enclose parameter lists, return value, side effects, and so on.

• Check for magic numbers. Sometimes developers use constant values rather than named constants in their code. This is particularly harmful when the value changes because all occurrences must also be changed. Using a named constant allows all changes to occur at once by making the change in a single location.

• Check for white space (or lack of same) around certain tokens or characters. This gives the code a standardized look and often makes it easier to understand.

• Enforce generally agreed-upon conventions in the code. For example, there is a document called Code Conventions for the Java Programming Language.⁹ This document reflects the Java language coding standards presented in the Java Language Specification¹⁰ by Sun Microsystems (now Oracle). As such, it may be the closest thing to a standard that Java has. Checkstyle can be set to enforce these conventions, which include details on how to build a class correctly.

• Search the code looking for duplicate code. This is designed to discourage copy-and-paste operations, generally considered a really bad technique to use. If the programmer needs to do the same thing multiple times, they should refactor it into a callable routine.

• Check for visibility problems. One of the features of object-oriented design is the ability to hide sections of code. An object-oriented system is layered with the idea of keeping the layers separated. If we know how a class is designed, we might use some of that knowledge when deriving from that class. However, using that knowledge may become problematic if the owner of that class decides to change the base code. Those changes might end up breaking our code. In general, when we derive a new class, we should know nothing about the super class beyond what the owner of it decides to explicitly show us. Visibility errors occur when a class is not correctly designed, showing more than it should.

These are just a few of the problems this kind of static analysis tool can expose.

3.2.4 Call Graphs

In the Foundation level syllabus, integration testing was discussed as being either incremental or nonincremental. The incremental strategy was to build the system a few pieces at a time, using drivers and stubs to replace missing modules. We could start at the top level with stubs replacing modules lower in the hierarchy and build downward (i.e., top down). We could start at the bottom level and, using drivers, build upward (i.e., bottom up). We could start in the middle and build outward (the sandwich or the backbone method). We could also follow the functional or transactional path.

What these methods have in common is the concept of test harnesses. Consisting of drivers, stubs, emulators, simulators, and all manners of mock objects, test harnesses represent nonshippable code that we write to be able to test a partial system to some level of isolation.

There was a second strategy we discussed called the “big bang,” a nonincremental methodology that required that all modules be available and built together without incremental testing. Once the entire system was put together, we would then test it all together. The Foundation level syllabus is pretty specific in its disdain for the big bang theory: In order to ease fault isolation and detect defects early, integration should normally be incremental rather than “big bang.”¹¹

The incremental strategy has the advantage that it is intuitive. After all, if we have a partial build that appears to work correctly and then we add a new module and the partial build fails, we all think we know where the problem is.

In some organizations, however, the biggest roadblock to good incremental integration testing is the large amount of nonshippable code that must be created. It is often seen as wasteful; after all, why spend time writing code that is not included in the build or destined for the final users? Frankly, extra coding that is not meant to ship is very hard to sell a project manager when other testing techniques (e.g., the big bang) are available. In addition, when the system is non-trivial, a great number of builds are needed to test in an incremental way.

In his book Software Testing, A Craftsman’s Approach, Paul Jorgensen suggests another reason that incremental testing might not be the best choice. Functional decomposition of the structure—and therefore integration by that structure—is designed to fit the needs of the project manager rather than the needs of the software engineers. Jorgensen claims that the whole mechanism presumes that correct behavior follows from individually correct units (that have been fully unit-tested) and correct interfaces. Further, the thought is that the physical structure has something to do with this. In other words, the entire test basis is built upon the logic of the functional decomposition, which likely was done based on the ease of creating the modules or the ability to assign certain modules to certain developers.

3.2.4.1 Call-Graph-Based Integration Testing

Rather than physical structure being paramount, Jorgensen suggests that call-graph-based integration makes more sense. Simply because two units are structurally next to each other in a decomposition diagram, it does not necessarily follow that it is meaningful to test them together. Instead, he suggests that what makes sense is to look at which modules are working together, calling each other. His suggestion is to look at the behavior of groups of modules that cooperate in working together using graph theory.

Two arguments against incremental integration are the large number of builds needed and the amount of nonshippable code that must be written to support the testing. If we can reduce both of those and still do good testing, we should consider it. Of course, there are still two really good arguments for incremental testing: it is early testing rather than late, and when we find failures, it is usually easier to identify the causes of them. Using call graphs for integration testing would be considered a success if we can reduce the former two (number of builds and cost of nonshippable code) without exacerbating the latter two (finding bugs late and the difficulty of narrowing down where the bugs are).

Figure 3–12 Pairwise graph example

The graph from Paul Jorgensen’s book in Figure 3–12 is called a pairwise graph. The gray boxes shown on the graph denote pairs of components to test together. The main impetus for pairwise integration is to reduce the amount of test harness code that must be written. Each testing session uses the entire build but targets pairs of components that work together (found by looking at the call graph as shown here). Theoretically, at least, this reduces the problem of determining where the defect is when we find a failure. Since we are not concentrating on system-wide behavior but targeting a very specific set of behaviors, failure root cause should be easier to determine.

The number of testing sessions is not reduced appreciably, but many sessions can be performed on the same build, so the number of needed builds may be minimally reduced. On the other hand, the amount of nonshippable code that is required is reduced to almost nothing since the entire build is being tested.

In the graph of Figure 3–12, four sessions are shown, modules 9—16, 17—18, 22—24, and 4—27.

Figure 3–13 Neighborhood integration example

The second technique, as shown in Figure 3–13, is called neighborhood integration. This uses the same integration graph that you saw in Figure 3–12 but groups nodes differently. The neighborhood integration theory allows us to reduce the number of test sessions needed by looking at the neighborhood of a specific node. That means all of the immediate predecessor and successor nodes of a given node are tested together. In Figure 3–13, two neighborhoods are shown: that of node 16 and that of node 26. By testing neighborhoods, we reduce the number of sessions dramatically, though we do increase the possible problem of localizing failures. Once again, there is little to no test harness coding needed. Jorgensen calls neighborhood testing “medium bang” testing.

Clearly we should discuss the good and bad points of call-graph integration testing. On the positive side, we are now looking at the actual behavior of actual code rather than simply basing our testing on where a module exists in the hierarchy. Savings on test harness development and maintenance costs can be appreciable. Builds can be staged based on groups of neighborhoods, so scheduling them can be more meaningful. In addition, neighborhoods can be merged and tested together to give some incrementalism to the testing (Jorgensen inevitably calls these merged areas villages).

The negative side of this strategy is appreciable. We can call it medium bang or target specific sets of modules to test, but the entire system is still running. And, since we have to wait until the system is reasonably complete so we can avoid the test harnesses, we end up testing later than if we had used incremental testing.

There is another, subtle issue that must be considered. Suppose we find a failure in a node in the graph. It likely belongs to several different neighborhoods. Each one of them should be retested after a fix is implemented; this means the possibility of appreciably more regression testing during integration testing.

In our careers, we have never had the opportunity to perform pairwise or neighborhood integration testing. In researching this course, we have not been able to find many published documents even discussing the techniques. While the stated goals of reducing extraneous coding and moving toward behavioral testing are admirable, one must wonder whether the drawbacks of late testing make these two methods less desirable.

3.2.4.2 McCabe’s Design Predicate Approach to Integration

How many test cases do we need for doing integration testing? Good test management practices and the ability to estimate how many resources we need both require an answer to this question. When we were looking at unit testing, we found out that McCabe’s cyclomatic complexity could at least reveal the basis set—the minimum number of test cases that we needed.

It turns out that Thomas McCabe also had some theories about how to approach integration testing. This technique, which is called McCabe’s design predicate approach, consists of three steps as follows:

1. Draw a call graph between the modules of a system showing how each unit calls and is called by others. This graph has four separate kinds of interactions, as you shall see in a bit.

2. Calculate the integration complexity.

3. Select tests to exercise each type of interaction, not every combination of all interactions.

As with unit testing, this does not show us how to exhaustively test all the possible paths through the system. Instead, it gives us a minimum number of tests that we need to cover the structure of the system through component integration testing.

We will use the basis path/basis tests terminology to describe these tests.

Figure 3–14 Unconditional call

The first design predicate (Figure 3–14) is an unconditional call. As shown here, it is designated by a straight line arrow between two modules. Since there is never a decision with an unconditional call, there is no increase in complexity due to it. This is designated by the zero (0) that is placed at the source side of the arrow connecting the modules.

Remember, it is decisions that increase complexity. Do we go here or there? How many times do we do that? In an unconditional call, there is no decision made—it always happens.

It is important to differentiate the integration testing from the functionality of the modules we are testing. The inner workings of a module might be extremely complex, with all kinds of calculations going on. For integration testing, those are all ignored; we are only interested in testing how the modules communicate and work together.

Figure 3–15 Conditional call

We might decide to call another module, or we might not. Figure 3–15 shows the conditional call, where an internal decision is made as to whether we will call the second unit. For integration testing, again, we don’t care how the decision is made. Because it is a possibility only that a call may be made, we say that the complexity goes up to one (1). Note that the arrow now has a small filled-in circle at the tail (source) end. Once again, we show the complexity increase by placing a 1 by the tail of the arrow.

It is important to understand that number. The complexity is not one—it is an increase of one. Suppose this graph represented the entire system. We have an increase of complexity of one—but the question is an increase from what? One way to look at it is to say that the first test is free, as it were. So the unconditional call does not increase the complexity, and we would need one test to cover it. One test is the minimum—would you ever feel free to test zero times? If you have gotten this far in the book, we would hope the answer is a resounding NO!

In this case, we start with that first test. Then, because we have an increase of one, we would need a second test. As you might expect, one test is where we call the module, the other is where we do not.

Figure 3–16 Mutually exclusive conditional call

The third design predicate (Figure 3–16) is called a mutually exclusive conditional call. This happens when a module will call one—and only one—of a number of different units. We are guaranteed to make a call to one of the units; which one will be called will be decided by some internal logic to the module.

In this structure, it is clear that we will need to test all of the possible calls at one time or another; that means there will be a complexity increase. This increase in complexity can be calculated based on the number of possible targets; if there are three targets as shown, the complexity increase would be two (2); calculated by the number of possibilities minus one. Note in the graph, a filled-in circle at the tail of the arrows shows that some of the targets will not be called.

Figure 3–17 Unconditional calls

In the next graph (Figure 3–17), we show something that looks about the same. It is important, however, to see the difference. Without the dot in the tail, there is no conditional. That means that the execution of any test must include Unit 0 to Unit 1 execution as well as Unit 0 to Unit 2 execution and Unit 0 to Unit n at one time or another. This would look much clearer if it were drawn with the three arrows each touching Unit 0 in different places instead of converging to one place. No matter how it is drawn, however, the meaning is the same. With no conditional dot, these are unconditional connections; hence there is no increase in complexity.

Figure 3–18 Iterative call

In (Figure 3–18) we have the iterative call. This occurs when a unit is called at least once but may be called multiple times. This is designated by the arcing arrow on the source module in the graph. In this case, the increase in complexity is deemed to be one, as shown in the graph.

Figure 3–19 Iterative conditional call

Last but not least, we have the iterative conditional call. As seen in this last graph (Figure 3–19), if we add a conditional signifier to the iterative call, it increases the complexity by one. That means Unit 0 may call Unit 1 zero times, one time, or multiple times. Essentially, this should be considered exactly the same as the way we treated loop coverage in Chapter 2.

3.2.4.3 Hex Converter Example

In several different exercises and examples earlier in the book, you saw the hex converter code in Figure 3–20.

Figure 3–20 Enhanced hex code converter code

This code is for UNIX or Linux; it will not work with Windows without modification of the interrupt handling. Here is a complete explanation of the code, which we will use for our integration testing example.

When the program is invoked, it calls the signal() function. If the return value tells main() that SIGINT is not currently ignored (i.e., the process is running in the foreground), then main() calls signal again to set the function pophdigit() as the signal handler for SIGINT. main() then calls setjmp() to save the program condition in anticipation of a longjmp() back to this spot. Note that when we get ready to graph this, signal is definitely called once. After that, it may or may not be called again to set the return value.

main() then calls getchar() at least once. If upon first call an EOF is returned, the loop is ignored and fprintf() is called to report the error. If not EOF, the loop will be executed. All legal hex characters (A..F, a..f, 0..9) will be translated to a hex digit and added to the hex number as the next logical digit. In addition, a counter will be incremented for each hex char received. This continues to pick up input chars until the EOF is found.

If an interrupt (Ctrl-C) is received, it will call the pophdigit() routine, which will pop off the latest value and decrement the hex digit count.

What we would like to do with this is figure out the minimum number of tests we need for integration testing of it.

Figure 3–21 Enhanced hex converter integration graph

Figure 3–21 is the call graph for the enhanced hex converter code. Let’s walk through it from left to right.

Module main (A) calls signal (B) once with a possibility of a second call. That makes it iterative, with an increase in complexity of 1.

The function pophdigit() (C) may be called any number of times; each time there is a signal (Ctrl-C), this function is called. When it is called, it always calls the signal (B) function. Since it might be called 0 times, 1 time, or multiple times, the increase in complexity is 2.

The function setjmp (E) may occur once in that case when signal (B) is called twice. That makes it conditional with an increase in complexity of 1.

The function getchar (F) is guaranteed to be called once and could be called any number of times. That makes it iterative with an increase in complexity of 1.

One of the functions, printf (G) or fprintf (H), will be called but not the other. That makes it a mutually exclusive conditional call. Since there are two possibilities, the increase in complexity is (N - 1), or 1.

Finally, the function pophdigit (C) always calls signal (B) and longjmp (D), so each of those has an increase in complexity of 0.

The integration complexity is seven, so we need seven distinct test cases, right? Not necessarily! It simply means that there are seven separate paths that must be covered. If that sounds confusing, well, this graph is different than the directed graphs that we used when looking at cyclomatic complexity. When using a call graph, you must remember that after the call is completed, the thread of execution goes back to the calling module.

So, when we start out, we are executing in main(). We call the signal() function, which returns back to main(). Depending on the return value, we may call signal() again to set the handler, and then return to main(). Then, if we called signal() the second time, we call setjmp() and return back to main(). This is not a directed graph where you only go in one direction and never return to the same place unless there is a loop.

Therefore, several basis paths can be covered in a single test. You might ask whether that is a good or bad thing. We have been saying all along that fewer tests are good because we can save time and resources. Well, Okay, that was a straw man, not really what we have been saying. The refrain we keep coming back to is fewer tests are better if they give us the amount of testing we need based on the context of the project.

Fewer tests may cause us to miss some subtle bugs. Jamie remembers going to a conference once and sitting through a presentation by a person who was brand-new to requirements-based testing. This person clearly had not really gotten the full story on RBT, because he kept on insisting that as long as there was one test per requirement, then that was enough testing. When asked if some requirements might need more than one test, he refused to admit that might even be possible.

A good rule of thumb is the more complex the software, the bigger the system, the more difficult the system is to debug, the more test cases you should plan on running—even if the strict minimum is fewer tests. Look for interesting interactions between modules, and plan on executing more iterations and using more and different data.

For now, let’s assume that we want the minimum number of tests. We always like starting with a simple test to make sure some functionality works—a “Hello World” type test.

1. We want to input just an “A” while running the application in the foreground to make sure we get an output. We would expect it to test the following path: ABBEFFG and give an output of “a”. This will test the paths between main(), signal(), setjmp(), getchar(), and printf().

2. Our second test is to make sure the system works when no input is given. This test will invoke the program but input an immediate EOF without any other characters: ABFH. We would expect that it would exercise the main(), signal(), getchar(), and, differently this time, the fprintf(). Output should be the no input message.

3. Our third test would be designed to test the interrupt handler. The input would be F5^CT9a. The interrupt is triggered by typing in the Ctrl-C keys together (shown here by the caret-C). Note that we have also included a non-hex character to make sure it gets sloughed off. The paths covered should be ABBEFFFCBDFFFG and should execute in the following order: main(), signal, signal, setjmp(), getchar(), getchar(), getchar(), pophdigit(), longjmp(), getchar(), getchar(), getchar(), printf(). We would expect an output of “f9a”.

At this point, we have executed each one of the paths at least once. But have we covered all of the design predicates? Notice that the connection from main (A) to pophdigit (C) is an iterative, conditional call. We have tested it 0 times and 1 time, but not iteratively. So, we need a fourth test.

4. This test is designed to test the interrupt handler multiple times. Ideally we would like to send a lot of characters at it with multiple Ctrl-C (signal) characters. Our expected output would be all hex characters; the number of them would be the number inputted less the number of Ctrl-Cs that were inputted.

Would we want to test this further? Sure. For example, we have not tested the application running in the background. That is the only way to get the SIGNAL to be ignored. We would have to use an input file and feed it to the application through redirection.¹²

In working with this example, we found a really subtle bug. Try tracing out what happens if the first inputted character is a Ctrl-C signal. In addition, the accumulator is defined as an unsigned long int; we wonder what happens when we input more characters than it can hold?

Typically, we want to start with the minimum test cases as sort of a smoke test and then continue with interesting test cases to check the nuances. Your mileage may vary!

3.2.4.4 McCabe Design Predicate Exercise

Calculate the integration complexity of the following call graph.

Figure 3–22 Design predicate exercise

3.2.4.5 McCabe Design Predicate Exercise Debrief

We tend to try to be systematic when going through a problem like this. We have modules A–H, each one has zero to five arrows coming from it. Our first pass through we just try to capture that information. We should have as many predicates as arrows. Then, for each one, we identify the predicate type and calculate the increase of paths needed. Don’t forget that the first test is free!

Module A

• A to B: Conditional call (+1)

• A to C, A to F, A to E: Mutually exclusive conditional call (n-1, therefore +2)

• A to D: Iterative conditional call (+2)

Module B

• B to C: Conditional call (+1)

Module C

• C to H: Conditional call (+1)

Module D

• D to H: Conditional call (+1)

Module E

• E to G: Iterative call (+1)

Module F

• F to H: Unconditional call (+0)

Module G

• G to H: Unconditional call (+0)

Therefore, the calculation is as follows:

IC = (1 + 2 + 2 + 1 + 1 + 1 + 1 + 1) == 10

3.3 Dynamic Analysis

In the previous section, we discussed static analysis. In this section, we will discuss dynamic analysis. As the name suggests, this is something that is done while the system is executing. Dynamic analysis always requires instrumentation of some kind. In some cases, a special compiler creates the build, putting special code in that writes to a log. In other cases, a tool is run concurrently with the system under test; the tool monitors the system as it runs, sometimes reporting in real time and almost always logging results.

Dynamic analysis is a solution to a set of common problems in computer programs. While the system is executing, a failure occurs at a point in time, but there are no outward symptoms of the failure for the user to see. If a tree falls in the woods and no one hears it, does it make a sound? We don’t know if a failure that we don’t perceive right away makes a sound, but it almost always leaves damage behind. The damage may be corrupted data, which could be described as a land mine waiting for a later user to step on, a general slowdown of the system, or an upcoming blue screen of death; there are a lot of eventual symptoms possible.

So what causes these failures? Here are some possibilities.

It may be a minor memory leak where a developer forgets to deallocate a small piece of memory in a function that is run hundreds of times a minute. Each leak is small, but the sum total is a crash when the system runs out of RAM a few hours down the road. Historically, even some Microsoft Windows operating system calls could routinely lose a bit of memory; every little bit hurts.

It may be a wild pointer that changes a value on the stack erroneously; the byte(s) that were changed may be in the return address so that when the jump to return to the caller is made, it jumps to the wrong location, ensuring that the thread gets a quick trip to never-never land.

It may be an API call to the operating system that has the wrong arguments—or arguments in the wrong order—so the operating system allocates too small a buffer and the input data from a device is corrupted by being truncated.

The fact is there are likely to be an uncountable number of different failures that could be caused by the smallest defects. Some of those bugs might be in the libraries the programmers use, the programming languages they write in, or the compilers they build with.

Dynamic analysis tools work by monitoring the system as it runs. Some dynamic analysis tools are intrusive; that is, they cause extra code to be inserted right in the system code, often by a special compiler. These types of tools tend to be logging tools. Every module, every routine gets some extra logging code inserted during the compile. When a routine starts executing, it writes a message to the log, essentially a “Kilroy was here” type message.

The tool may cause special bit patterns to be automatically written to dynamically allocated memory. Jamie remembers wondering what a DEAD-BEEF was when he first started testing, because he kept seeing it in test results. It turns out that DEADBEEF is a 32-bit hex code that the compiler generated to fill dynamically allocated memory with; it allowed developers to find problems when the (re-)allocated heap memory was involved in anomalies. This bit pattern made it relatively simple when looking at a memory dump to find areas where the pattern is interrupted.

Other dynamic analysis tools are much more active. Some of them are initialized before the system is started. The system then (essentially) executes in a resource bubble supplied by the tool. When a wild pointer is detected, an incorrect API call is made, or when an invalid argument is passed in to a method, the tool determines it immediately. Some of these tools work with a MAP file (created by the compiler and used in debugging) to isolate the exact line of code that caused the failure. This information might be logged, or the tool might stop execution immediately and bring up the IDE with the module opened to the very line of code that failed.

Logging-type dynamic analysis tools are very useful when being run by testers; the logs that are created can be turned over to developers for defect isolation. The interactive-type tools are appropriate when the developers or skilled technical testers are testing their own code.

These tools are especially useful when failures occur that cannot be replicated, because they save data to the log that indicates what actually happened. Even if we cannot re-create the failure conditions, we have a record of them. And, by capturing the actual execution profile in logs, developers often glean enough information that they can improve the dynamic behavior of the runtime system.

Dynamic analysis tools can be used by developers during unit and integration testing and debugging. We have found them very useful for testers to use during system testing. Because they may slow down the system appreciably, and because they are sometimes intrusive to the extent of changing the way a system executes, we don’t recommend that they be used in every test session. There certainly is a need to execute at least some of the testing with the system configured the way the users will get it. But some testing, especially in early builds, can really benefit from using dynamic analysis tools.

There are some dynamic tools that are not intrusive. These do not change the system code; instead, they sit in memory and extrapolate what the system is doing by monitoring the memory that is being used during execution. While these type of tools tend to be more expensive, they are often well worth the investment.

All of these tools generate reports that can be analyzed after the test run and turned over to developers for debugging purposes.

These tools are not perfect. Because many of them exhibit the probe effect—that is, they change the execution profile of the system—they do force more testing to be done. Timing and profile testing certainly should not be performed with these tools active because the timing of the system can change radically. And, some of these tools require the availability of development artifacts, including code modules, MAP files, and so on.

In our experience, the advantages of these tools generally far outweigh the disadvantages. Let’s look at a few different types of dynamic analysis tools.

3.3.1 Memory Leak Detection

Memory leaks are a critical side effect of developer errors when working in environments that allow allocation of dynamic memory without having automatic garbage collection. Garbage collection means that the system automatically recovers allocated memory once the developer is done with it. For example, Java has automatic garbage collection, while standard C and C++ compilers do not.

Memory can also be lost when operating system APIs are called with incorrect arguments or out of order. There have been times when compilers generated code that had memory leaks on their own; much more common, however, is for developers to make subtle mistakes that cause these leaks.

The way we conduct testing is often not conducive to finding memory leaks without the aid of a dynamic analysis tool. We tend to start a system, run it for a relatively short time for a number of tests, and then shut it down. Since memory leaks tend to be a long-term issue, we often don’t find them during normal testing. Customers and users of our systems do find them because they often start the system and run it 24/7, week after week, month after month. What might be a mere molehill in the test lab often becomes a mountain in production.

A dynamic analysis tool that can track memory leaks generally monitors both the allocation and deallocation of memory. When a dynamically allocated block of memory goes out of scope without being explicitly deallocated, the tool notes the location of the leak. Most tools then write that information to a log; some might stop the execution immediately and go to the line of code where the allocation occurred.

All of these tools write voluminous reports that allow developers to trace the root cause of failures.

Figure 3–23 Memory leak logging file

Figure 3–23 shows the output of such a tool. For a developer, this is very important information. It shows the actual size of every allocated memory block that was lost, the stack trace of the execution, and the line of code where the memory was allocated. A wide variety of reports can be derived from this information:

• Leak detection source report (this one)

• Heap status report

• Memory usage report

• Corrupted memory report

• Memory usage comparison report

Some of this information is available only when certain artifacts are available to the tool at runtime. For example, a MAP file and a full debug build would be needed to get a report this detailed.

3.3.2 Wild Pointer Detection

Another major cause of failures that occur in systems written in certain languages is pointer problems. A pointer is an address of memory where something of importance is stored. C, C++, and many other programming languages allow users to access these with impunity. Other languages (Delphi, C#, Java) supply functionality that allows developers to do powerful things without explicitly using pointers. Some languages do not allow the manipulation of pointers at all due to their inherent danger.

The ability to manipulate memory using pointers gives a programmer a lot of power. But, with a lot of power comes a lot of responsibility. Misusing pointers causes some of the worst failures that can occur.

Compilers try to help the developers use pointers more safely by preventing some usage and warning about others; however, the compilers can usually be overridden by a developer who wants to do a certain thing. The sad fact is, for each correct way to do something, there are usually many different ways to do it poorly. Sometimes a particular use of pointers appears to work correctly; only later do we get a failure when the (in)correct set of circumstances occurs.

The good news is that the same dynamic tools that help with memory leaks can help with pointer problems.

Some of the consequences of pointer failures are listed here:

1. Sometimes we get lucky and nothing happens. A wild pointer corrupts something that is not used throughout the rest of the test session. Unfortunately, in production we are not this lucky; if you damage something with a pointer, it usually shows a symptom eventually.

2. The system might crash. This might occur when the pointer trashes an instruction of a return address on the stack.

3. Functionality might be degraded slightly—sometimes with error messages, sometimes not. This might occur with a gradual loss of memory due to poor pointer arithmetic or other sloppy usage.

4. Data might be corrupted. Best case is when this happens in such a gross way that we see it immediately. Worst case is when that data is stored in a permanent location where it will reside for a period before causing a failure that affects the user.

Short of preventing developers from using pointers (not likely), the best prevention of pointer-induced failures is the preventive use of dynamic analysis tools.

3.3.3 Dynamic Analysis Exercise

1. Read the HELLOCARMS system requirements document.

2. Outline ways to use dynamic analysis during system testing.

3. Outline ways to use dynamic analysis during system integration testing.

3.3.4 Dynamic Analysis Exercise Debrief

Your solution should include the following main points:

• Memory leak detection tools can be used during both system test and system integration test, on at least two servers on which HELLOCARMS code runs (web server and application server). The database server might not need such analysis.

• Assuming that a programming language that allows pointer usage (e.g., C++) is used on some or all parts of the system, wild pointer tools might be used. These would be deployed during selected cycles of system test and system integration test, especially if any odd behaviors or illegal memory access violations are observed. As with memory leak detection, the main targets would be the web server and application server. The database server would only need such analysis if code that uses pointers is written for it.

• Performance analysis tools should definitely be used during system test and system integration test, and in this case on all three servers.

• API tracking tools could certainly be used during both cycles of test. During system test, these could find anomalies in the way the application works with the local operating system. During system integration, it would be able to look for irregularities in the API, RPC, and any middleware function calls that occur on the distributed system.

You might also identify additional opportunities for use of dynamic analysis.

3.4 Sample Exam Questions

1. Given the following:

I. Changing the index variable from the middle of a loop

II. Using a neighborhood rather than pairwise relationship

III. Jumping to the inside of a loop using a GOTO

IV. Non-deterministic target of a Scheme function call

V. Avoiding the use of a McCabe design predicate

VI. Cyclomatic complexity of 18

VII. Essential complexity of 18

VIII. Use-use relationship of a passed in argument

Which of the possible defects or design flaws above can be detected by control flow analysis?

A. All of them

B. II, IV, V, VII, VIII

C. I, III, IV, VI, VII

D. I, III, V, VI, VII

2. Your flagship system has been experiencing some catastrophic failures in production. These do not occur often; sometimes a month can go between failures. Unfortunately, to this point the test and support staff have not been able to re-create the failures. Investigating the issue, you have not found any proof that specific configurations have caused these problems; failures have occurred in almost all of the configurations. Which of the following types of testing do you believe would have the most likely chance of being able to solve this problem?

A. Soak-type performance testing

B. Keyword-driven automated testing

C. Static analysis

D. Dynamic analysis

3. Your organization has hired a new CIO due to several poor releases in the past year. The CIO came from a highly successful software house and wants to make immediate changes to the processes currently being used at your company. The first process change to come down is a hard and fast rule that all code must be run through a static analysis tool and all errors and warnings corrected before system test is complete. As the lead technical test analyst for the current project, which of the following options best describes the explanation you should give to the CIO about why this new rule is a bad idea?

A. Your staff has no training on these tools.

B. There is no budget for buying or training on these tools.

C. Changing existing, working code based on warnings from static analysis tools is not wise.

D. Given the current work load, the testers do not have time to perform static testing.

4. The following code snippet reads through a file and determines whether the numbers contained are prime or not:

1   Read (Val);
2   While NOT End of File Do
3        Prime := TRUE;
4        For Holder := 2 TO Val DIV 2 Do
5             If Val - (Val DIV Holder)*Holder= 0 Then
6                  Write (Holder, ` is a factor of', Val);
7                  Prime := FALSE;
8             Endif;
9        Endfor;
10       If Prime = TRUE Then
11            Write (Val , ` is prime'),
12       Endif;
13       Read (Val);
14   Endwhile;
15   Write('End of run)

Calculate the cyclomatic complexity of the code.

A. 3

B. 5

C. 7

D. 9

5. When you’re calculating complexity of a function, which of the following control structures is most likely to give a misleading cyclomatic complexity value?

A. Switch/case statement

B. Embedded loop inside another loop

C. While loop

D. For statement

6. A code module is measured and determined to have a cyclomatic complexity of 16. Under which of the following circumstances would the development group be least likely to refactor the module into two different modules?

A. They are building a mission-critical application.

B. The project time constraints are very tight.

C. They are building a real-time critical application.

D. They are building a safety-critical application.

7. Consider the following code snippet:

1.  #include<windows.h>
2.  #include<wininet.h>
3.  #include<stdio.h>
4.  int main()
5.  {
6.
7.     HINTERNET Initialize,Connection,File;
8.     DWORD dwBytes;
9.     char ch;
10.    Connection = InternetConnect(Initialize,"www.xxx.com",
11.                 INTERNET_DEFAULT_HTTP_PORT,NULL,NULL,
12.                 INTERNET_SERVICE_HTTP,0,0);
13.
14.    File = HttpOpenRequest(Connection,NULL,"/index.html",
15.           NULL,NULL,NULL,0,0);
16.
17.    if(HttpSendRequest(File,NULL,0,NULL,0))
18.    {
19.       while(InternetReadFile(File,&ch,1,&dwBytes))
20.       {
21.          if(dwBytes != 1)break;
22.          putchar(ch);
23.       }
24.    }
25.    InternetCloseHandle(File);
26.    InternetCloseHandle(Connection);
27.    InternetCloseHandle(Initialize);
28.    return 0;
29. } 

With regards to the variable Connection and looking at lines 10–14, what kind of data flow pattern do we have?

A. du

B. ud

C. dk

D. There is no defined data flow pattern there.

8. Which of the following should always be considered a possible serious defect?

A. ~u

B. dk

C. kk

D. dd

9. Your team has decided to perform data flow analysis in the software you are developing to be placed in a satellite system. Which of the following defect would be least likely found using this analysis technique?

A. Failure to initialize a variable that is created on the stack as a local variable.

B. A race condition occurs where an array value is changed by another thread unexpectedly.

C. An allocated heap variable is killed inside a called function because a break statement is missing.

D. A passed-by-reference variable is unexpectedly changed before the original value is used.

10. Which of these data flow coverage metrics is the strongest of the four listed?

A. All-P uses

B. All-C uses

C. All Defs

D. All DU paths

11. You have been tasked by the QA manager to come up with some common sense standards and guidelines for programmers to follow when they are writing their code. Which of the following possible standards are likely to be included in the standards and guidelines?

I. Every method requires a header (describing what the method does) and listing parameters.

II. Every variable must use Hungarian notation when it is named.

III. Comments must be meaningful and not just repeat what the code says.

IV. No module may have a cyclomatic complexity over 10 without formal review sign-off.

V. Static analysis tool must indicate high coupling and low cohesion of each module.

VI. Code that is copied and pasted must be marked by comments and change bars.

VII. No magic numbers may appear in the code; instead, named constants must be used.

A. I, II, III, VI, VII

B. I, II, III, IV, VII

C. All of them

D. I, III, IV, V

12. Given the integration call graph below, and using McCabe’s design predicate approach, how many basis paths are there to test?

A. 12

B. 10

C. 13

D. 14

13. Given the following list, which of these are most likely to be found through the use of a dynamic analysis tool?

I. Memory loss due to wild pointers

II. Profiling performance characteristics of a system

III. Failure to initialize a local variable

IV. Argument error in a Windows 32 API call

V. Incorrect use of equality operator in a predicate

VI. Failure to place a break in a switch statement

VII. Finding dead code

A. I, III, IV, and VII

B. I, II, III, IV, and VI

C. I, II, and IV

D. II, IV, and V