Discrete Math Approach to Software Testing

Mathematics helps to put our thoughts in order and is very effective in developing logical thinking. Meanwhile, testing is fundamentally concerned with behavior, and behavior is orthogonal to the structural view common to software developers. The difference between the two is that the structural view focuses on what software is, while the behavioral view considers what it is doing.

 

One of the difficulties for testers is that the base technical documentation or software development guides are usually written by and for developers, and the emphasis is generally on structural instead of behavioral information. Of course, both structural and behavioral parts are very important for testing because programming mistakes can be found in each part. That’s why we will speak about discrete mathematical methods to show the relationship between a program structure and behavior.

 

In their daily job, software quality assurance engineers are working with formula operations, functions behavior, and data structures. They always control and check a constantly changing state of systems, so they need to have algorithmic and mathematical thinking to understand the software logic.

 

If a software engineer uses a mathematical approach in his work, he will be exposed to the following characteristics: all logical operations will be connected with each other, actions will follow a logical chain, and every function will be viewed structurally.

 

Discrete math helps us find the optimal decision in different kinds of situations. For example, it’s possible to find the most appropriate set of test cases without covering all possible cases. Moreover, discrete mathematics helps us visualize an exact part of software that was implemented and covered by tests. Unfortunately, we don’t live in an ideal world, and the expected real-life results of software application and actual outcomes may differ. So, the main goal of the Quality Assurance department is to cover as many test cases as possible, in the most efficient manner.

 

To show you this concept in more detail, we’ve created the following Venn diagram, with the example we previously outlined colored darkest blue:

Image_1

The Venn diagram above describes a lot of situations to help illustrate and define situation sets. For example, it can help us see the difference between some sets of objects. In software testing, discrete math helps analyze and streamline sets of action which can influence the software.

Set Theory

By using base set theory principles, we can create pseudo code to illustrate all possible cases for “Next Day” application (software which calculates what day will be the next one using an inputted date):

 

M1={month:month has 30 days}

M2={month:month has 31 days except December}

M3={month:month is February}

M4={month:month is December}

D1={day:1<=day<=28}

D2={day:1<=day<=29}

D3={day:1<=day<=30}

D4={day:1<=day<=31}

Y1={year:year is a leap year}

Y2={year:year is not a leap year}

 

This pseudo code is already prepared for the application, so testers are also able to apply all possible test cases. The use of data in this format will help increase the development speed and exclude misunderstanding and mistakes.

Graph Theory

A big part of discrete mathematics is so-called “graph theory,” which studies graphs. Graphs are used to represent communication between some entities or data, and a computer network is an appropriate example of a graph.

 

Graphs are also fundamental to the software development process. For example, by using graphs, we can decompose complex functions to several smaller parts, which helps us understand business logic more efficiently.

 

Graphs can be directed and undirected, meaning that we can move from node to node in one direction or in two directions (in case of a directed graph), or we can’t move from one node to another (if a graph is undirected).

 

So let’s come back to software testing and imagine that we have a flow of some process (like moving a ticket in some task-tracking system); we have some task’s condition and we can move it to a different stage (directed graph), or we can get to some point where we can’t do anything with the entity (undirected graph). With such an approach to visualization, we can easily collect the set of all possible actions available with the entity:

Image_5

 Let’s move on and have a look at the adjacency matrix, which can be built on the base of an undirected graph. In the example below, the elements of the adjacency matrix indicate whether pairs of vertices are adjacent or not:

Image_2

Now imagine that nodes are the conditions of some entities, and if we build the adjacency matrix for this graph (set of entities), we will see a finite set of actions which we can take. For example, the change of the status  from “0” node to “1” node is available because they are connected with each other. But “0” entity can’t be changed to “2” or “3” stage, as we can see from our matrix—there are “zero” in cells. Using this matrix, we can exclude unnecessary sets of entity stages and reduce the set of test cases.

 

Another matrix we can use for collecting test cases is the incidence matrix that shows the relationship between two classes of objects. In the following picture, we can see an undirected graph and its incidence matrix: “1”,”2”,”3,” and “4” are nodes (entities), “e1”,”e2”,”e3,” and “e4” are edges of the graph, and the matrix illustrates the entities and the actions that we can do with them. With node “1,” we can perform “e1”,”e2,” and “e3” actions, but the “e4” action isn’t available for node “1.” This method is very helpful for creating test cases.

Image_3

Imagine that a tester received the list of entities and actions. With the help of this matrix, he can reduce the set of test cases. Reducing the number of test cases is a very important part of the software testing process. Software testing relies heavily on reducing the number of test cases, and with this approach, test coverage and avoidance of redundancy are both maximized.

 

The goal of software testers is to cover the product by using effective test cases, which allow for testing of all possible combinations of actions. Testers can achieve success while making minimum effort by using discrete mathematical approaches (algorithms) to find the optimal set of test cases and maximize the effectiveness of the software testing process.

 

Discrete math also helps us understand how software is actually built, because all software uses the algorithms and methods of discrete mathematics and math logic. So if we understand how it works, we can find bugs or problems inside the program, which can’t be found from the user side.

Petri Nets

Let’s consider the example of how the application works on the microservice technology with the help of a “Petri net” (dynamic graph):

dynamic graph

 Here we can see that a system has an initial state, and should receive some status which is sent from another service (a marker appears). Depending on the received result, the next action should be executed. So a Petri net illustrates the whole system’s dynamics. If any problem exists, we will localize the defect faster.

Neural Nets

 Artificial neural nets are also based on graph principles. They are emulating the information-processing capabilities of neurons of the human brain. Each part of the neural system is based on the graph, which contains “Input” nodes, a “Hidden” layer, and “Output” nodes.

Image_6Some data comes to the input layer, while algorithms in the hidden layer process this data and send the result to the output stage. So a neural net can perform an action based on this data. Neural nets also consist of many similar graphs with a different logic, so they can make a decision based on the parameters that are input.

Millenium Testing 

Our final example of using discrete mathematics in testing involves building the software-testing process. Nowadays, we have a lot of methodologies and approaches that are called “Millenium testing,” which were developed long before their actual use starting in the 2000s, when software development began to change rapidly.


BDD (Behavior Driven Development) is one part of Millenium testing, and this methodology is an extension of TDD (Test Driven Development). BDD allows testers to build a closer relationship to acceptance criteria for a given function and the tests used to validate that functionality. BDD can convert structured natural language statements into executable tests, and the main structure of the BDD workflow is also based on a dynamic graph (Petri Net).

 

Image_4

As we can see in this structure, each process is followed by another process, and we can’t move it to the next stage until the previous stage is finished. Once again, the principles of discrete mathematics help us understand the process more efficiently.

 

In conclusion, the advantages of applying discrete mathematics in the software development process involve:

- Helping us understand the business logic of the required functionality

- Making it easier to divide complex tasks into simpler stages

- Allowing specialists to test efficiently with fewer efforts

- Helping us understand and visualize the structure of anything we wish to


The above examples showcase how discrete math can be used to effectively increase testing performance. Each aspect of discrete math can help developers understand the working order of the software and its principles during the entire software development lifecycle.

Author: Alina Penkina, QA Engineer at Zensoft

 

 Start Your Project

QA

Follow Us