Statement Decision Condition And Branch Coverage Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

The primary problem in all software testing is to effectively test all statements, decisions, conditions and branches within a program. Testing all the logic paths will preview the faults of the software and how efficient it is when under testing strain, i.e., branch testing. The obstacles in such a thorough testing process are many but the most important for the software project include specifically: time and cost. It has been calculated and estimated that in safety-critical software systems, verification/testing effort is usually 50% of the whole project time [1]. There are tools and the advancement of automated testing technology that will aide in the essential coverage testing.

1. Introduction

Software testing is a critical part of the software development cycle. It can consume the majority of the project's budget and time. Nearly all software needs meticulous testing in order to verify that it is in correct behavior before being released to the client. It also determines the software quality [2]. The core to a successful testing procedure is to be able to test the whole program thoroughly, with all its elements, to find problems and bugs before product deployment. This is the primary mission of coverage testing.

In an industrial software engineering environment, tools and software are used in helping the coverage testing process. The most common way of testing software is by the utilization of unit tests designed for the software. A popular tool for creating unit tests is xUnit, a testing framework widely recognized in the software industry. Such frameworks have capabilities to attach test coverage tools to perform coverage testing on the source code [3]. An example of such a test coverage tool is Cobertura, which approximates the branch coverage for each class in the unit after executing a unit test on the source code. Cobertura also outputs a status report of each component after the testing has concluded but one key detail is omitted; if the tests had successfully covered all the branches/statements in the target package [3]. The only way to coverage testing is by white-box testing and that will require the source code. All source code comprises of the software's branches, decisions, conditions and statements. These 4 terms always affect the program's control flow, which is the current or next instruction that will be executed by the program. Definitions for each term are as follows:

Branch coverage:

A branch in a program is a line/collective of code that is in the control flow usually executed as part of a conditional statement or a direct instruction (unconditional). The simplest way of determining individual branches of code is by looking at the machine/assembly code [4] (see Figure 1) and then separate each section of the code as possible branches, that could end up in the control flow. Branch coverage testing is achieved when "all edges of the control flow graph (see Figure 2) have been traversed by a program. That is, all statements have been executed, and all branch paths have been taken in each direction at least once" [5].

Figure : Loop with One Conditional Branch [4]


Figure : Example of a control flow graph/chart with 3 If conditions [17]

Decision coverage:

According to Bhansali and the DO-178B (Software Considerations in Airborne Systems and Equipment Certification standards document), "Every point of entry and exit in the program has be invoked at least once and every decision in the program has taken on all possible outcomes at least once" [6]. A decision consists of one or more branches [7].

Statement coverage:

Statement coverage measures the total number of statements in a program and in a statement coverage testing procedure, it would be ideal to execute all statements at least once [5].

Condition coverage:

Condition coverage consists of branches that precede with conditional instructions, example: If statements, Case statements, etc [8]. This type of testing is usually grouped with Branch coverage testing but includes foresight into conditional branches and statements.

To ensure that testing will cover all the branches, decisions, conditions and statements in the source code is an impossible task and for testers, the blueprint for planning the test and drawing the control flow chart is the source code. Coverage testing gets tougher when the complexity and the program size is large, making coverage testing a strenuous job for all involved. Coverage testing can be described as a "state" testing procedure, where apparent states of the software including the state of variables and the next to current function pointers [9]. These state diagrams can be either Markov chain usage models (see Figure 3),Petri nets or control flow charts (see Figure 2) that will signal the logic of the function and its concurrent branches that the function can return or follow through.

Full-size image (5 K)

Figure : A sample Markov chain state model [9]

Branch testing has been used for decades as the principle testing method of many software projects. Its core formula rests on [10]:

View the MathML source

Branch testing is the core of coverage testing. Elements such as decision, statement, and condition testing can be done to increase/decrease the overall cost effectiveness/time effort by using different strategies, such as: path selection method, extended shortest path method [10] Search Based Software Engineering [11] and the random branch/state from population [9].

Another key aspect of coverage testing is the language of the software being tested. If aspect-oriented/object oriented language is what is used then by tracking the data flow and control flow at all joint points in aspect-oriented languages, example: Java byte code, the structure of the program can be tested by method/advice [12]. In such a testing procedure, AODU (aspect-oriented def-use) graphs (see Figure 4) are designed for each unit to be tested, much like a Petri-net [12]. For procedural languages the standard state diagram flow chart or Petri-nets are suitable but the addition of control and data flow charts is important also.

Much research has been done for procedural language testing, but less so for OOP languages. Automated tools that generate unit tests for every object and container in an OOP-based software have been in use for the past few years [11] and have significantly assisted the endeavor of overall coverage testing, especially with the soaring popularity of Java and C++.

Full-size image (18 K)

Figure : Two examples of AODUs [12]

2. Coverage Testing In Depth

The majority of coverage testing requires graphical interpretations of the logic pathways/branches within the source code in order for the program to be successfully tested and for the unit test cases to be optimal.

The ideal scenario for coverage testing to start is when the control- and data-flow diagrams from the Design phase of a software development project match the source code, assuming that testing has been done in the Design phase. Almost all the branch, decision, statement and condition coverage testing will require graphs of the logic flow in order for the unit tests to be created. This will reinforce that as much of source code is covered and the paths that are unclear in the source code will be visually displayed on the graphs. The graphs will also demonstrate the data inputs required and the predicted output for each branch to be tested by the unit test cases. As a last resort, if graphs are unavailable then truth tables/heuristics have to be used [13].

The key notion is that every unit test covers as much of the selected code as possible. Coverage testing like "decision" testing will need not only "data-related decision" but also "event alternatives" pathways [14]. Priorities should also be highlighted on every section/object of the source code, if a section has critical code that defines the system's work flow, then this section must be tested thoroughly first [13]. This is ever so important when a safety critical, such as aviation and hospital software systems, are being tested.

There are a few variables dependent on the type of coverage testing that will be in process when the unit tests are written. The main observation will be the language type of the software, be it procedural or object-oriented, as each has different tools and aides focused on the strengths and weaknesses of the particular language type. Also, it needs to be defined how many statements and decisions are in the source code so that efficiency can be calculated.

After the prerequisites are attained, the process of writing the unit test cases can be initialized. Each unit test shall target a specific section/function of the source code. Priorities must also be taken under acknowledgement by the writers of the unit tests. With the help of the graphs and other material, the unit tests will need to cover as much of the branches in the software as possible. A 100% coverage testing (where all target elements are covered by test) is what needs to be strived for when conducting coverage testing but this is unrealistic when enormous software systems are being tested. Current trends are moving towards testing frameworks that will allow automated testing to take hold as it's more efficient and cost-effective. There are also algorithms and methods that aid in code coverage, like the Substring Hole Analysis algorithm that is designed specifically for code coverage in large code [15]. The Substring Hole Analysis algorithm parses the source code and the leading function names to detect hidden sections that would be normally omitted in coverage testing, example: error handling code, which in many cases hides holes that can make the software vulnerable to errors. The algorithm was used in 2 IBM systems and the heuristics (40 holes found) have proven that such algorithms like the Substring Hole Analysis, detect and cover code that would be otherwise forgotten to be tested [15].

2 a. Real-world Examples, Solutions and Problems

At the Daimler Automotive center (maker of Mercedes Benz), where testing is conducted on the automotive systems that are in charge of the braking and cruising speeds of vehicles, the coverage testing is done by generating Search-Based Test Data from state-flow charts [16] (see Figure 5 for a sample real-world state-flow chart). Given the nature of the test subjects and their safety critical requirements, the testing has to cover most, if not all, of the system. The Search-based Test Data uses all input states and it mathematically calculates the distance between states with determinations made for the entry, during and exit phases of states [16]. The entry phase is triggered when entering a state after a condition has been satisfied or a procedure call. The during phase is what actions occur during the state execution, while the exit phase is when the state exits and ceases to run. This is a prime real-world example of a coverage testing done by the usage of state-flow charts.

Figure : A sample state-flow chart for the Daimler Automotives, and its safety critical nature [16]

In commercial aviation systems, the main testing method is the modified condition/decision (MCDC) coverage testing. But even with such a testing method, many common errors are not found by the MCDC even when it consumes 25% of the verification project budget [6]. The MCDC is defined as:

"Every point of entry and exit in the program has been invoked at least once, every condition in a decision in the program has taken all possible outcomes at least once, and each condition in a decision has been shown to independently affect that decision's outcome. A condition is shown to independently affect a decision's outcome by varying just that condition while holding fixed all other possible conditions." [6]

The MCDC uses Boolean expressions as the precursor for the testing, but it has been pointed out that in systems where assembly language is used, the MCDC continues to not find common errors. The weakness of coverage testing is the programming language used, and this looks to be a continuous problem as many systems are old and with languages that have lost interest or expertise by the software engineers. MCDC also fails when conditions are coupled in one statement [6] and because of these weaknesses of MCDC, it puts a costly strain on the testing budget and incurs expenses because bugs are left unfound. The solution, currently proven to be currently successful, is presented as:

1) Conduct independent code review using a checklist

2) Conduct module-level requirements-based testing using equivalence classes and boundary values for variables.

3) Monitor the machine instruction and branch coverage using a monitoring tool

4) Augment test cases until there is 100% machine and

branch coverage for Level A software. [6]

3. Conclusion

Coverage testing is a key testing practice used in the software industry for many years and it shows no sign of losing its importance. There are problems associated with coverage testing, mostly associated with the increasing size of systems and how strategies have to be uniquely derived for the target software system, including drawing control-, data- and state-charts that will consume a huge chunk of the project's budget, but it is a necessity. As research is put into coverage testing, and systems are written with the coverage testing phase in mind, it will prove to be a solution to finding numerous bugs that have to be found before releasing the software to the customer.