Arunkumar Khannur's Software Testing Knowledge Center

9.7 Test Case Design Using Boolean Algebra

In this section, we discuss on use of Boolean algebra in reporting any deviation from specification. In order to perform this, using Theorems and Laws of Boolean algebra, we simplify

In order to do this, we perform following steps:

Step 1: Arrive at flow chart of a given specification and express path expressions in the form of predicate expressions
Step 2: Arrive at Boolean expression of the program segment
Step 3: Simplify each predicate expression using theorems and laws of Boolean Algebra
Step 4: Examine the logical sum of those predicate expressions for consistency and ambiguity; and
Step 5: Design Test Case
Step 6:
We consider following example and describe each of these steps in the following sections. Report any deviation from specification.

9.7.1 Arrive at flow chart of a given specification and perform path tracing to list out all path expressions in the flow graph

Given a flow chart corresponding to specification, we perform path tracing to list out all path expressions. We consider each such path expression and convert it into Boolean algebra using the predicates’ truth values as weights. Following are the steps taken to arrive at the predicate expression of a path.

  1. Label output of each decision of a predicate with an uppercase letter that represents the truth value of the predicate. For exam- ple, for the predicate A, truth value YES or TRUE is represented as A and truth value NO or FALSE is represented as Ā. We con- tinue this exercise of labelling till we cover all predicates in the path.
  2. Now we write the truth value of a path as the product of the individual labels. Here product or concatenation means “AND” operation. In the flow chart, consider a path that goes through nodes 1, 3, 4, 2. The truth value of this path is AB
  3. Like this we proceed till we cover predicate expressions of all paths. Other truth values of other paths in the flow chart are:
    For path via nodes 1, 3, 4, 6, 2 the truth value is A B–
    For path via nodes 1, 3, 5, 6, 2 the truth value is - B
    For path via nodes 1, 3, 5, 6, 2 the truth value is – –

9.7.2 Arrive at Boolean Expression of the Program Segment

Boolean expression of the program segment is a logical sum of those predicate expressions. For the given program segment, Boolean expression is:

9.7.3 Simplify Each Predicate Expression using Theorems and Laws of Boolean Algebra

The Boolean expression, using Theorems and Laws of Boolean Algebra, can be simplified as follows:

9.7.4 Examine the logical sum of those predicate expressions for consistency and ambiguity

In a product term, if literal appears twice then the decesion is reduntant and we can remove one appearance. In a product term, If a literal appears both barred and unbarred, then according to law of complimentation the term is equal to 0 indicating that the path is unachievable.

A product term on entry exit / specify a domain because each of the underline predicate expressions specifies a domain boundary over that inputs space.

When the predicates are compund, the boolean expressions corresponding to that path takes a form of a sum of product term such as ABC + DE + FGH. This expression also specifies a domain since it was derived from one path. However each of the product term ABC, DE, FGH corresponds to 3 seperate, disconnected sub domains.

If we have the product term like ABCD + CD then CD is included in ABCD. This means that the domain ABCD wholly contains sub domain CD. Using boolean alegbra simplification it is always possible to eliminate included subdomain.

If the product of any two terms is not 0, then the two domains overlap even though one may not be containied in the other.

Alternatively we can perceive any sum of product terms as separate paths that specifies separate domains. For example ABC+DE+FGH can be treated as combination of three separate domains, namely, ABC, DE, FGH.

Let us consider the product term as combination of domains D1, D2, Di Dj Dm. From these domains, consider any two of product terms DiDj. For every i not equal to j, DiDj must equal to 0. If the product doesn’t equal to 0, then there is an overlap of the domain. If this happens then we say that a contradictory domain specifications has been done. Further more, the sum of all the Di must equal to 1 or else there is an ambiguity.

9.7.5 Design Test Case

Test case, in principle, need to be designed for each possible TRUE/ FALSE combination of the predicate. However, in most of the cases predicates are correlated and so all paths in predicates are not achievable paths. If the predicates are all uncorrelated, then for each combination of TRUE/FALSE there would be a different path a different domain and their sum would correspond to a minimum covering set.

In a specification, there can be many ambiguities since the sum of all the Di may not be equal to 1 and also there can be contradictory domain specifications since the product Di Dj where i not equal to j, the product doesn’t equal to 0. However in a program it is not possible to have contradiction or ambiguities if:

  1. The routine fulfils a single entry and a single exit conditions.
  2. None of the combination of predicate values leads to non terminating loops
  3. The code does not have any dangling piece of code in it.

During test case design, we try to evaluate the code by taking into consideration the three conditions listed above. By arriving at Boolean algebra expression corresponding to all entry and exit path in a program segment we try to check whether that Boolean algebra expression is equal to 1. If it is not so then there can be unreachable segment in the code or non terminating code for some predicate value combinations or we might have made a mistake in evaluating that code.

while designing test cases to evaluate a code using boolean algebraic, what are the three conditions that need to be considered? If boolean algebra expresses results in “1”, then what does it indicate? If it does not result in ‘1’, then what is the intercept be? How can we write test cases for putting in a flow graph from one node to another node where these nodes are not entry or exit nodes? What criteria need to be considered in order to write a test case?

Thus the entire test case designing involves arriving at sum of products corresponding to a programming segment, and then considering each domain and writing a set of test cases based Boolean algebra to evaluate for ambiguities and contradictions, and then repeating this exercises for all the domains in that program segment.

If there are “n” predicates then there are 2n combinations of predicate values. Under these conditions the most complete test case designing involves a set of test cases which can cover all 2n combinations. However testing can be usually be achieved with fewer test cases.

In case we wish to write test cases for paths in a flow graph from one node to another but not entry node to exit node, we can use Boolean algebra expressions corresponding to paths from one node to another node at which processing specific to a domain takes place.

Under such situations the simplified product form corresponding of the Boolean algebraic expression for those nodes will be of use to specify test cases. In these situations we are interested in designing test cases between those nodes and we are not interested in understanding on what happens subsequently.

Thus in order to write more test cases from one node to any other node of interest in the set of paths. We consider following criteria:
  1. Simplest: Identify and focus on any prime implicant in the predicate expressions to the point of interest as a basis for a path. Pick only those values that appear in the prime implicant and ignore all the literals. For example, If we pick up B as a prime implicant, we need not bother about what we do with A or C.
  2. Covering Prime Implicant: It is important to pick input values in such a manner that there is atleast one path for each prime implicant at the node of interest in the predicate.
  3. Test all terms: There can be many expanded terms for the node of interest that we consider in the path. We need to test all expanded terms for that node. This ensures that atleast one path for each term is considered in our test.
  4. Path Dependence: Before arriving at any predicate, there can be more than one path to get that predicate. Also the truth value of that predicate depends on the path taken to get there. Thus we need to consider every path and its corresponding terms that would lead to the predicate.
Khannur's Book
Arunkumar Khannur, Software Testing - Techniques and Applications, Published by Pearson Publications, 2011 (ISBN:978-81-317-5836-6; Pages:341 + xxii)
Follow Khannur
Khannur's Company
ISQT Process & Consulting Services Pvt. Ltd., Bangalore, INDIA
Khannur's Software Testing Forum
 Contact Khannur
ISQT Process & Consulting Services Pvt. Ltd.
#732, 1st Floor, 12th Main,
3rd Block, Rajajinagar,
Bangalore - 560010, INDIA
Phone: +91 80 23012511
Skype: arun.isqt