Software Validation and Verification: Course Notes

Zune 30, was released to the public in November 2006. It was the first portable media player released by Microsoft. Suddenly, on December 31^st 2008, all Zune devices hung and stopped working. The problem was traced back to a piece of code in the firmware equivalent to Listing 2.

The values of days and years did not change which produced a wrong internal state and thus the error. The software enters an infinite loop and the devices became non-responsive.

By the next day, days would be 367 and the code would run perfectly. So Zune devices stop working on December 31^st of every leap year. The problem could have been found if the code was tested with the right input date before releasing the product.

Heartbleed is a software vulnerability disclosed in April 2014 that granted attackers access to sensitive information. It was caused by a flaw in OpenSSL, an open source code library implementing the Transport Layer Security and Secure Sockets Layer protocols.

As part of these protocols, a computer should send a heartbeat, an encrypted message that the receiver should replay back, to keep the connection alive. The heartbeat contains information about its own length. The code for the receiver never verified that the message had the specified length. To answer, it should allocate a memory buffer to store the content of the heartbeat. If the message was longer, then there is a buffer overflow and the computer would send more data than requested (7).

The webcomic XKCD explains this vulnerability in a very intuitive manner. See Figure 2.

In Listing 3 you can see a fragment of the code containing the bug.

The USS Yorktown (CG-48) cruiser was selected in 1996 as the testbed for the Smart Ship program. The ship was equipped with a network of several 200 MHz Pentium processors. The computers abroad the ship ran Windows NT 4.0 and executed applications to run the control center, monitor the engines and navigate the ship. In September 21^st 1997 a crew member entered a zero into a database field causing a division by zero that resulted in a buffer overflow, which, in turn, made the propulsion system fail. The ship was dead for several hours and had to be towed back to port (8).

The Patriot missile defense system was able to track the trajectory of enemy projectiles and intercept them. The system stored the clock time in an integer that was converted to a fixed point number and multiplied by 1/10 to produce the time in seconds for the tracking estimation. The computation was performed in a 24-bit fixed point register and the time value was truncated. This would produce an error proportional to the uptime of the system (i.e. it grows in time). Apart from that, the system was updated several times to improve the conversion routine, but the patch was not placed in all the required code locations. On February 25^th, 1991 one of these Patriot batteries failed to intercept an Iraqi Scud missile. The battery had been up for 100 hours and the chopping error was around 0.34 seconds. Since a Scud travels at 1.676 m/s it reaches more than a half kilometer in this time. The Scud struck an American Army barracks killing 28 soldiers and injuring around 100 other people (9).

The Chemical Bank deducted by error about $15 million from more than 100000 customers in one night. The problem was caused by a line of code that should not be executed until further changes were made to the system. This line sent a copy of every ATM transaction to the machine processing paper checks so, all transactions were deducted twice (10).

A race condition appears when the output of a system depends on the sequence or timing of other uncontrollable events. This may lead to a bug when the effects of this assumption are not carefully considered. For example, in a multithreaded application, a piece of code may be (wrongly) assumed to run before another.

The code in Listing 4 shows a simplified example of a race condition.

To prevent this race condition, the code of paint should not assume that art will always point to an instance. To deal with this race condition it is enough to check if art is null or not.

On August 14^th, 2003 the alarm of FirstEnergy, an electric utility in Akron, Ohio, should have alerted about an overload in the electricity transmission lines. A race condition stalled the alarm and the primary sever went down. A backup server started processing all demands and also went down after 13 minutes. With both servers down, the information being shown in the screens passed from a refresh rate of 1 to 3 seconds to 59 seconds. The operators were not aware of the actual condition of the grid and the system collapsed affecting an estimated of 50 million people.

The Ariane 5 test launch is one of the most referenced examples of the impact that a software bug can have. On June 4^th 1996, the rocket was launched by the European Space Agency from the French Guiana. After 40 seconds the rocket exploded at more than 3700 meters of altitude.

In (11) the authors explain that, before liftoff, certain computations are performed to align the Inertial Reference System (SRI). These computations should cease at -9 seconds from the launching sequence. But, since there is a chance that a countdown could be put on hold and because resetting the SRI could take several hours, it was preferable to let the computation proceed than to stop it. The SRI continues for 50 seconds after the start of flight mode. Once the rocket is in the air this computation is not used anymore. However, it caused an exception which was not caught and produced the explosion of the rocket.

Part of the software of Ariane 5 was reused from Ariane 4. The later used 16-bit floating point numbers, while the former used 64-bit arithmetic. The conversion of a greater value caused the exception. The fact that this module used 16-bit floating point numbers was not documented in the code. The trajectory of Ariane 5 differed from that of Ariane 4. The former had considerably higher horizontal velocities that produced values above the initial range. This was the first launch after a decade of development with an estimated cost of US$7 billion plus the rocket and cargo were estimated in US$500 million.

The Mars Climate Orbiter probe crashed when entering the orbit of Mars. The cause was tracked to the fact that one development team was using the International System of Units (meters and kilometers) while another team was using the Imperial Unit System (miles and yards). The loss was estimated in US$235.9 million (12). The subject is still inspiration of many memes cruel jokes.

Part of the coding guidelines is devoted to help developers knowing how to name program elements such as classes or methods. These guidelines are different from one language to the other, although they share common ideas. This section contains three examples from Java, C# and Python.

The following Example 1 is an extract from the Java coding conventions (30). This fragment specifies how developers should name classes, interfaces and methods.

Listing 9 shows a piece of code respecting the naming conventions form Example 1.

Example 2 contains an extract of the naming conventions for C# (31).

There are similarities between the naming conventions for Java and C#. For example, class names should be noun phrases starting with a capital letter and using PascalCasing (Also called UpperCamelCase, DromedaryCase or CapWords). While method names in both languages should be verb phrases indicating an action, in Java developers use camelCasing. Notice that, in C#, interfaces should be prefixed with I but classes should not be prefixed with C. Listing 10 shows a code fragment matching these naming conventions. The I prefix helps to quickly differentiate between classes and interfaces.

Python developers use conventions to further differentiate method and functions from classes and user defined classes from built-in types (32). See Example 3.

With this, one can easily infer that Node names a class, str is a built-in type and remove_node is a function.

Naming conventions are derived in most of the cases from the taste and practice of the community around a language or framework. In the end, these conventions help improving the readability of the code as developers can quickly understand the role of each element in a program.

In most languages extra white spaces do not change the semantics of a program but they may play an important role in readability. For example, the indentation is useful to know the limit of methods, classes, nested instructions and any block in general. Each programming language tries to enforce an indentation style, but even for the same language different developers may follow different styles. Keeping a consistent style improves the understanding of a program.

Table 1 shows three examples of different indentation styles applied to the same fragment of code. Notice how different the program looks in each case.

The Kernighan & Ritchie style, also known as “_the one true brace style_” and “Egyptian braces” was used in the influential book The C Programming Language written by Brian Kernighan and Dennis Ritchie (creator of C). Besides C, this style is also used in C++ and Java. C# however, uses the Allman style, in which the first brace is written in a separated line. The Allman style is also used in Pascal and SQL.

Wikipedia lists nine different indentation styles most of them with additional variants [wikipedia20202indentation].

Companies and even communities around a framework or project may impose specific guidelines to override or extend language conventions.

Sometimes these guidelines have a concrete goal other than readability. For instance, Example 4 shows an extract of the guidelines Microsoft enforces to write secure code using the .NET framework (34).

Example 5 shows how Google extends the Java coding conventions to their own projects (35).

Conventions are created to set a common ground for understanding. This is especially useful when we are learning a new language and to ease the collaboration between different developers in a project. However, there are cases in which strictly following these conventions actually has the opposite effect. For example, when dealing with legacy code that followed different guidelines, it is better to stick to the practices in place rather than introducing new conventions.

In any case, the ultimate goal must be to write consistent code that can be understood by all team/project members. Common sense is always the best guideline.

Example 6 explains how to name extending classes with respect to the base class, but it also warns against over-use (31).

Example 7 shows an extract from the Python coding guidelines stressing the idea that keeping consistency is more important than following the guidelines (32).

The simplest code metric is, maybe, the already mentioned number of Lines of Code (LoC) of a method.

A long method is hard to understand, maintain and evolve. LoCs can be used to compare the length of the methods in a project and detect those that are too longer than a given threshold. However, this threshold depends on the development practices used for the project. The programming language as well as the frameworks and libraries supporting the code, have an impact on the length of the methods. For example, a small study made by Jon McLoone from Wolfram (40), observed in the Rosetta Code corpus of programs, that many of those written with Mathematica require less than a third of the length of the same tasks written in other languages.

Including blank lines or lines with comments in the metric could be misleading. Therefore, LoC is often referred as Physical Lines of Code while developers also measure Logical Lines of Code (LLoC) which counts the number of programming language statements in the method.

A method with many branches and logical decisions is, in general, hard to understand. This affects the maintainability of the code. Back in 1976, Thomas J. McCabe proposed a metric to assess the complexity of a program (41). McCabe’s original idea was to approximate the complexity of a program by computing the cyclomatic number of its control flow graph. This is why the metric is also known as McCabe’s Cyclomatic Complexity. The goal of the metric was to provide a quantitative basis to determine whether a software module was hard to understand, maintain and test.

A sequence of code instructions, and by extension the body of a method, could be represented by a directed graph named control flow graph. The procedure is as follows:

For example, the method in Listing 12 computes the maximum of three given integers. The control flow graph for this method is shown in Figure 7.

The cyclomatic complexity of a program, represented by its control flow graph, is defined as \$v(G) = E - V + 2P\$, where \$N\$ is the number of nodes, \$E\$ the number of edges and \$P\$ the number of connected components of the underlying undirected graph. In the way we have defined the control flow graph, \$P\$ is always 1. This metric is directly derived from the cyclomatic number or circuit rank of the undirected graph. This property represents the minimum number of edges that has to be removed in order to break all cycles and obtain a spanning tree.

McCabe showed that the computation of the cyclomatic complexity could be simplified as the number of predicate nodes (conditionals) plus one. The method in Listing 12 has a cyclomatic complexity of \$v(G) = 4 = 3 + 1\$, as it has three conditionals: a > b, a > c and b > c. It can be also computed as \$v(G) = 4 = 11 - 9 + 2\$, as it has eleven edges, nine nodes and only one connected component.

McCabe’s cyclomatic complexity is well known and widely used. It is frequently accompanied by a scale. Values below 10 are usually considered as good. However, some caveats of the metrics must be taken into account. First, it was conceived for unstructured programs and some aspects of its original definition are vague. Modern tools implementing the metric work under different assumptions, therefore two different tools may not produce the same result for the same method. Logical conjunctions and disjunctions (&& and || in some programming languages) also produce branches but not all tools include them in their results.

Not always the cyclomatic complexity matches the developer’s idea of what is a complex method. For example, the metric does not consider nested structures. It produces the same value for the two code fragments in Listing 13.

In (42), the author advocates against the use of the metric. Besides showing concrete examples where tools produce different results, he discusses the method in Listing 14. The author explain that this method is fairly easy to understand, yet it has a cyclomatic complexity of 13 while the more complex method in Listing 15 has a cyclomatic complexity of 5.

A class is coupled to another if the former uses a method or a field from the latter. Coupling between classes can not be avoided, it is, in fact, desirable. We create classes as functional units for reuse. At some point, existing classes will be leveraged to create new functionalities. However, coupling has important implications: changing a class will, most of the times, require changing its dependent classes. Therefore, tight coupling between classes harms modularity and makes a software too sensitive to change and harder to maintain (43) (44).

Class coupling or Coupling Between Objects (CBO) of a class is the number of external classes it uses. In Listing 16, Point has CBO of 0. It only depends on double and the metric does not consider primitive types. Line, on the other hand, depends on Point and has a CBO of 1. The metric counts only unique classes. In the example, Line uses Point several times, but it is counted only once.

Classes with low CBO values, or loosely coupled are easier to reuse. Classes with large CBO values or tightly coupled should be avoided and refactored. If a tightly coupled class is necessary, then it requires rigorous testing to correctly verify how it interacts with all its dependencies.

Coupling could be measured not only at the class level but also between any modules at all granularity levels (e.g., packages, components…​).

The Law of Demeter (LoD) or principle of least knowledge is a guideline aiming to keep classes loosely coupled (46). Its idea is that any unit should only "talk" to "its closest friends" and not to "strangers". In the context of Object-Oriented Programming, it means that a method can only invoke methods from the receiver (this), a parameter, an object instantiated in the method or an attribute of the class. Listing 17 shows examples of a good use and some violations of this principle.

LoD has downsides as well. A strict adherence to its postulates may produce many unnecessary wrapper methods. In Listing 17 the class Bar should had a wrapper method doItInC whose code could be this.getC().doIt() or something alike. This kind of wrapper would be widespread in the code and it could become a challenge for maintenance. On the other hand, fluent APIs encourage the use of method chains, which also tends to improve readability.

A class in an object-oriented program, or a module in general, is expected to have a responsibility over a single and well defined part of the software’s functionalities. All services/methods of the module/class should be aligned with this responsibility and this responsibility should be entirely encapsulated in the class. This ensures that the module/class is only changed when the requirements concerning the specific responsibility change. Changes to different requirements should not make a single class to change (47) (48). This is known as the The Single Responsibility Principle and it was coined by Robert C. Martin in the late 1990’s. This principle puts the S in the SOLID principles of object-oriented programming.

If a class violates this principle, then it can probably be divided in two or more classes with different responsibilities. In this case we say that the class lacks cohesion. In a more concrete view, a cohesive class performs different operations on the same set of instance variables (43).

There are several metrics to evaluate cohesion in classes, but most of them are based in the Lack of Cohesion Of Methods (LCOM) (43). This metric is defined as follows:

Let \$C\$ be a class with \$n\$ methods: \$M_1, ..., M_n\$, let \$I_j\$ the set of instance variables used by the method \$M_j\$. Let \$P = { (I_i, I_j) | I_i \cap I_j = \emptyset, i \gt j }\$, that is, the pairs of methods that use disjoint sets of instance variables, and \$Q = { (I_i, I_j) | I_i \cap I_j \ne \emptyset, i \gt j}\$, all pairs of methods using at least one instance variable in common. Then \$\text{LCOM}(C) = |P| - |Q| \text{ if } |P| \gt |Q| \text{ 0} \text{ otherwise}\$.

This means that LCOM is equal to the number of pairs of methods using a disjoint set of instance variables minus the number of pairs of methods using variables in common. If the class has more methods using disjoint sets of instance variables then it is less cohesive. A class is cohesive if its methods use the same variables to compute different things. Low values of LCOM are preferred.

Table 2 shows the set of all instance variables used by each method declared in the Point class shown in Listing 16. Constructors are not used to compute this metric, as their role is to initialize the variables and they virtually access all of them. In this particular example, all methods use the instance variables directly. However, a method could use an instance variable indirectly by invoking other methods. In that case, the variables are also said to be used by the initial method. For example, any new method invoking getX in Point would also use variable x.

Table 3 shows the instance variables used un common for all pairs of methods declared in Point. Only getX and getY do not use any variable in common.

Given that we obtain: \$ | P | = | \{ (I_\text{getX},I_\text{getY}) \} | = 1 \$ and: \$ | Q | = | \{ (I_\text{getX},I_\text{sub}), (I_\text{getX},I_\text{dot}), (I_\text{getY},I_\text{sub}), (I_\text{getY},I_\text{dot}), (I_\text{dot},I_\text{sub}) \} | = 4\$ producing: \$ \text{LCOM}(C) = 0 \$ as \$ | P | \lt | Q | \$. Which means that the Point class is cohesive, its carries the responsibility to represent the concept of a two-dimensional point. Only a change in the requirements of this representation will make this class change.

Lack of cohesion implies that a class violates the principle of single functionality and could be split in two different classes. Listing 18 shows the Group class. The only two methods in this class use a disjoint set of fields. compareTo uses weight while draw uses color and name. Computing the metric we get: \$\text{LCOM}(C = |P| - |Q| = 1 - 0 = 1\$.

Tight Class Cohesion (TCC) and Loose Class Cohesion (LCC) are other two well known and used metrics to evaluate the cohesion of a class (49). Both these metrics start by creating a graph from the class. The graph is constructed as follows: Given a class C, each method m declared in the class becomes a node. Given any two methods m and n declared in C we add an edge between m and n if and only if, m and n use at least one instance variable in common. Going back to the definition of LCOM, we add an edge between m and n if \$I_{m,n} \ne \emptyset\$. TCC is defined as the ratio of directly connected pairs of node in the graph to the number or all pairs of nodes. On its side, LCC is the number of pairs of connected (directly or indirectly) nodes to all pairs of node. As before, constructors are not used.

Figure 8 shows the graph that results from the class Point. In this example there are 5 edges or direct connections, and, as there are 4 nodes, then there are 6 node or methods pairs in total. Therefore \$\text{TCC = 5/6 = 0.83\$. On the other hand, all nodes are connected and \$\text{LCC} = 6/6 = 1\$.

If we do the same for the Group class, we obtain a graph where all nodes are disconnected and both LCC and TCC are 0.

In object-oriented programs a class may inherit methods and instance variables from its base classes. In those cases, computing the cohesion of a subclass may: include only inherited methods, only inherited fields, or both. The original definitions of TCC and LCC are open with respect of inherited members. Users of the metrics should decide whether to include them or not (49).

This section explains how to implement a simple static analysis tool using JavaParser. As a library, JavaParser provides a hierarchy of classes to represent ASTs for Java programs and implementations of the visitor pattern to help analyze and transform those ASTs.

Figure 10 shows a selection of classes representing AST nodes. Node is the base class of the hierarchy. The instances of ClassOrInterfaceDeclaration represent declarations of classes and interfaces in the program. These nodes contain information about the type parameters, base class and interfaces implemented in the corresponding declaration. ClassOrInterfaceDeclaration inherits from the more general TypeDeclaration, which contains, among other properties, a name. TypeDeclaration inherits from BodyDeclaration which is also the base class for all elements that could be included in the body of a type declaration. Expression is the super class of all abstractions of expressions as it is the case for MethodCallExpr and FieldAccessExpr. Both these classes contain information about the scope or receiver of the method call or the field access, as well as the name of the method or the field. MethodCallExpr also provides information about the arguments. On its side,Statement is the base class for all types representing statements in the program, as it is the case of the IfSmt. This last class has an Expression representing the condition and two Statement instances for the then and else branches of the conditional statement.

The visitor pattern is implemented in JavaParser by the interfaces VoidVisitor (Listing 21) and GenericVisitor (Listing 22). Both interfaces are very similar. They both contain visit methods for all concrete classes representing AST nodes. In the former interface these methods are void while the latter allows to return a value. This is the only difference. All visit overloads also accept an arg parameter to share information among nodes in the traversal of the AST.

There is no need to directly implement these two interfaces. The library also provides some default implementations to ease reuse. For example, VoidVisitorAdapter and GenericVisitorAdapter implement the visitor interfaces and perform a depth-first traversal of the AST. A new visitor could extend one of these adapter classes and just redefine the visit overloads it actually needs and not all of them. ModifierVisitor enables a similar reuse, but specialized on the use case where the AST should be modified. Listing 23 shows a fragment of the code of this class implementing the visit method overload for IfStmt.

With the help of JavaParser we will implement a small tool to enforce a coding convention. In Java, and many other languages, it is optional to use braces ({}) in loops and conditionals if the body contains only one statement. For example, it is not easy to see that the else belongs to the inner conditional statement in Listing 24. Also it is easy to missplace code when not using the braces.

Using ModifierVisitor as base, we will implement a visitor that modifies the AST so that the then and else parts of all conditional statements are enclosed in braces, that is, the statements must be contained in a block. The implementation of this custom visitor is shown in Listing 25. The BlockEnforcer traverses the AST and modifies only IfStmt nodes. It ensures that each then and else parts are instances of BlockStmt. Notice the use of Void as a type parameter for the implementation as no extra information will be passed between nodes.

Listing 26 shows how to use BlockEnforcer to analyze a single Java file. The first step is to obtain an instance of CompilationUnit. A compilation unit in Java is a file that optionally declares a package and contains an arbitrary number of imports and type declarations. StaticJavaParser provides shortcut methods to get such objects from common String, InputStream, Reader and File inputs. Then the visitor is applied through the accept method. This snippet prints on the screen the result of the analysis by invoking the toString method of CompilationUnit. The result cane be also saved to a file or we can even rewrite the original source code.

When given the code in Listing 24, Listing 26 produces Listing 27 as result.

Of course, JavaParser also includes functionalities to analyze a full Java project and more. Further information can be found in the project’s website.

The input domain of a system under test is the set of all possible values that the input parameters can take. If there are more than one parameter, then the input domain is the cartesian product of the domains of all parameters. The input domain also includes values that could be incorrect for the program. These are also very important for testing purposes. A test input is then a tuple of values from the domain, one for each parameter.

For example, Listing 52 shows the signature of the findLast method introduced first in Listing 48. This method takes as input an array of integers and an integer. Therefore its input domain is a tuple of all possible integer arrays, including null and empty arrays and all possible integers. Test inputs for this method could be { array: null, element: 1 }, { array: {}, element: 2 }, { array: {1, 2, 3}, element: 4 }.

Listing 53 shows the signature of a method that takes three integers and says if they form a valid date according to the Gregorian Calendar. The input domain is the set of all possible tuples of three integer elements, including negative integers and zero. Possible test inputs may include: { day: 1, month: 2, year: 200 }, { day: 19, month: 9, year: 1983 } or { day: 33, month: 12, year: 1990 }.

Listing 54 shows an extract of the BoundedStack class shown in Listing 33. In case we are testing methods push and pop, we should consider all possible values of elements and count. That is, when testing classes, instance fields, and even global static fields used by the method are also part of the input. Observe that in this case, elements will never be null since it is created in the constructor.

The input space partitioning technique design tests based on a model of the input domain. From this model it is possible to derive several coverage criteria which result in a broad selection of potential test inputs. The technique uses only the interface of the program, the signature of the method or even the specification, but does not need to observe the internal structure of the artifact being tested. In this sense it is said to be a blackbox technique, as opposed to whitebox techniques, that heavily rely on the internal structure, for example, the code of the method.

To model the input, this technique creates partitions of the domain. A partition is a subdivision of the domain into subsets or blocks in such a way that the union of all blocks results in the entire input domain and all blocks are disjoint, that is, no element, or test input, can be included in more than one block for the same partition. Each partition is created by identifying characteristics which describe the structure of the input domain. Characteristics and blocks should be designed in such a way that all values in one block are equivalent according to the characteristic that defines the partition.

Identifying the right characteristics is hard and requires expertise. There are two main approaches: interface based modeling and functionality based modeling.

Interface based modeling considers each parameter separately and takes information only from their specific domain. It is a simple alternative that makes it easier to identify the characteristics. However, it does not use all the information available like the specification and fails to capture the interaction between parameters.

Using interface based modeling to describe the input of findLast from Listing 52 we may identify the characteristics shown in Table 4. Two characteristics are identified: `array` is null` and `array is empty. Each characteristic defines a partition with two blocks, one to contain the arrays for which the condition of the characteristic is true and another containing arrays for which the characteristic is false.

The same could be done in the parameter element, but it will not yield characteristics interesting enough for the tests. The values of element are irrelevant in isolation. It makes sense to look at them only in relation to the content of array.

Functionality based modeling uses semantic information and plays with the specification, the domain of each parameter and the interplay between the values of different parameters. Identifying good characteristics with this approach is harder but may yield better results.

For the same findLast method in Listing 52, with this approach we may identify the characteristics in Table 5. The table shows a characteristic that captures the number of times element appears in array which yields three blocks: one for arrays that do not contain element, one for arrays containing only one occurrence of element, and another for arrays in which element appears more than once. The other two characteristics consider the position of element in the array and each of them yields a partition with two block.

All characteristics in Table 4 and Table 5 could be used in conjunction to design test inputs.

Now we shall model the input of isValidDate from Listing 53. We first identify characteristics with the interface based approach. This may yield the following result:

There is one characteristic for each parameter and they consider their values separately with respect to their domain. All possible values, valid or invalid are included and all blocks for the same characteristic are disjoint. Values close to the boundaries between valid and invalid inputs tend to be problematic and often source of bugs. So it is a good idea to include blocks reflecting these values. This way we can expand our initial characteristics as follows:

These blocks may be too broad for testing purposes. Sometimes it is useful to partition blocks into sub-partitions specially in the case of valid inputs.

In our example, the meaningful values of month and day depend on each other and the value of year. Actually, the number of valid days depend on the month, and even the year in the case of February, so we turn to a functionality based approach for new characteristics.

We first include the notion of leap year and subdivide years greater than 0 into leap and non-leap. Another almost equivalent solution for this could be to add a new characteristic reflecting this condition. We then include a block for valid month numbers and another for valid days which depend on the maximum valid number according to the month, represented as max(month, year).

We can go further and sub-partition valid month numbers into groups matching the maximum number of days on each. The result would be as follows:

Now we have a block for months with 31 days, another for months with 30 days and one for February which is a very special case.

If the input contains a parameter with a enumerative domain of a few values, it could make sense to create a partition with one block per value. In our example we could have one block for each month, but there is no substantial different among months with the same amount of days for this particular method we are testing.

It should be taken into account that, when testing classes, different methods of the same class could share the same characteristics to define partitions. For example, both the push and pop methods in the stack implementation shown in Listing 33 could partition the input considering when the stack is empty or not. Therefore it is a good idea, when testing a class, to first find the characteristics for all methods and reuse them.

Once the features and blocks have been identified, the concrete test inputs are built by picking values matching a selection of blocks from different partitions. For example: {day: 1, month: 2, year:2000} is an input matching the third block for each of the partitions identified in Table 6, that is, blocks q1b3, q2b3`and `q3b3.

Test inputs can be immediately translated to concrete test cases. For example, if we select blocks q1b4, q2b5 and q3b4 we can pick { day: 29, month: 2, year: 2019}. The test case could be written as follows:

Notice how designing test cases from block selections makes the test case clear and helps trace it back to the requirements.

The challenge now is to create effective block combinations. For that we can use the following coverage criteria:

The following set of inputs achieve ECC coverage. All blocks from Table 6 are covered by at least one input:

Sometimes it is not feasible to select certain blocks at the same time. For example, we should not pick q3b3: day larger than the maximum according to month and year, if month does not have a valid value, for example if we pick q2b1. Such combinations can be dropped when creating test inputs. However, if an input model contains too many of these restrictions it might be a good idea to redesign the partitions.

While this coverage criterion is easy to achieve, it may not yield good results, as it may miss interesting combinations between blocks.

An extension of PWC is to combine T characteristics or partitions at the same time (aka. T-wise test case generation), but it has been shown that this does not produce any improvement in practice.

Combining more than one invalid value is not useful in general. Most of the times, the program recognizes only of them and the effects of the others are masked. The following two criteria provide a good alternative to avoid that and produce a smaller number of inputs.

For partitions in Table 6, we can pick q1b3 and q1b4 as base choices for the first characteristic, q2b3, q2b4, q2b5 for the second and q3b3 for the third one. With this setup we could pick the following inputs covering base choices: { day: 1, month: 3, year: 2019 }, { day: 30, month: 9, year: 2018 }, { day: 29, month: 2, year: 2020 }. Then, more inputs could be added by exchanging one basic block by another non-basic choice. For example, if we take { day: 29, month: 2, year: 2020 }, it matches blocks q1b4, q2b5 and q3b3. Changing q3b3 by q3b4 implies to change the value of day to a value larger than the maximum according to the month. With this we could change 29 by 30 and obtain a new input { day: 30, month: 2, year: 2020 }. The process continues until no new inputs can be added.

Input space partitioning helps defining an initial set of tests inputs. However, the criteria explained in this section do not ensure any of the conditions to discover a fault as stated by the RIPR model.

As their name implies, structural coverage criteria rely on the internal structure of the artifact under test, that is, the code of the method, class or complete program we are testing. This section present some of the more commonly used criteria in this category.

Other structural criteria can be defined over the control flow graph of a method or a sequence of instructions. Recalling the procedure explained in [cyclomatic], the control flow graph of a method is built as follows:

Figure 14 shows the control flow of the findLast method presented in Listing 46.

The execution of a test case produces an execution path or execution test over the control flow graph. This path goes from the start node to the end node and includes all nodes containing instructions executed by the test case and all edges connecting those nodes.

For example, the test case in Listing 48 produces the following path start ⇒ (1) ⇒ (2) ⇒ (3) ⇒ (5) ⇒ end. With this path, the test case covers the nodes/blocks (1), (2), (3) and (5). Nodes start and end are covered by all execution paths. The same path covers edges start ⇒ (1), (1) ⇒ (2), (2) ⇒ (3), (3) ⇒ (5), (5) ⇒ end. The test does not cover nodes (4) and (6) and edges (3) ⇒ (4), (4) ⇒ (2), (2) ⇒ (6) and (6) ⇒ end. Figure 15 shows in blue the elements covered by this test case in the graph.

The following coverage criteria are precisely defined over the nodes, edges and paths of a control flow graph.

The cyclomatic complexity sets a lower bound for the number of different tests executing all branches. In this example the cyclomatic complexity is 3 which is also the number of test cases that cover the basis.

Many software artifacts can be represented as graphs. As an example, Finite State Machines are a special type of graph that have been widely used to represent the behavior of software elements. Actually, most embedded software is modeled as a state machine. Finite state machines can also be used to describe specifications for software and even how a user interface should behave.

In a finite state machine, a node represent a state of the artifact and edges represent changes in those states. As an example, recall Figure 5 where a state machine was used to model the behavior of a microwave oven.

The structural criteria defined over the control flow graph of a method can be extended to any type of graph. Branch coverage can be generalized as edge coverage and block coverage is just a special case of node coverage. In the particular case of finite state machines, designing test cases to achieve edge coverage ensures that all state transitions are explored and targeting node coverage ensures that all possible states of the artifact have been observed in at least one test case.

But, as explained before, the structural criteria discussed in this section only ensure that most parts of the software under test are executed. Therefore they guarantee that, if there is a fault, it will be executed by at least one test case. However, these criteria do not ensure that the input will infect the program state, or that the effects will be propagated to an observable point or that there will be an oracle strong enough observing the right portion of the state.

A predicate is a boolean expression. They are used in all kinds of software. Predicates define branches in source code and also define the state of finite state machines like the microwave oven in Figure 5.

The coverage criteria presented in this section are designed specifically for predicates. They are also designed in such a way that, if there is a fault, test cases created with the help of these criteria guarantee that the state of the program will be, at least, infected by the fault. This means that, if there is a fault in the code of the predicate, there will be at least one test case where the predicate will produce the wrong result.

A predicate is defined as follows: