Click here to Skip to main content
15,665,942 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more: (untagged)
Hello everybody,
I ‘am working in software testing, specifically automatic test cases generation. Among the existing forms of test cases, my focus is on the test cases that are composed of sequences of events such as _.event1.event2…eventx()

However, the events can be classified into: sensitive and insensitive. The latter does not affect the system’s states, and hence, it can be ignored; while the former affects the states. Anyhow, the sensitive events in the test cases may lead to states explosion and there is a need to prevent that. Therefore, some techniques suggest using one variable to present states and group all similar states together such as using len variable in circular queue. Relatively, the states can be represented by using specific drawings such FSM.

For example, the test cases for circular queue may look like:


which produce the following states:
len=1, rear=0, front=0 and dataQ[0]=0
len=0, rear=0, front=1 and dataQ={0}
len=1, rear=1, front=1 and dataQ[1]=1
len=1, rear=0, front=0 and dataQ[0]=0
len=2, rear=1, front=0 and dataQ[1]=1
len=1, rear=1, front=1 and dataQ={1,0}

As can be seen, every addition/deletion produces a new state. A state is composed of 4 variables: len, rear, front and dataQ. The 1st three variables are integers while the dataQ is an integer array. Nonetheless, the states produced by different test cases can be identical which wastes effort and time. So, there is a need to optimize these states. The search techniques were suggested where the problem can be represented as a search problem and the technique is applied. If we consider Len as a state, then we will have: len=0; 0QSize. However, this does not represent the state but it suits for classifying the states into groups.

In terms of states representation, State Machine/Map Compiler (SMC) was suggested as a modeling mechanism that takes the state machines (i.e. FSM) drawing and generates the code in any preferred language. In SMC, the FSM is represented in a specific syntax (state---transition----next state) and saved in a file (.sm). This file will be compiled by SMC to generate a context class which includes definitions of states, transitions and actions in FSM but still need to be triggered by another class. This class has to call the transitions that modifies the state.

We had created that class and implemented all the methods with their transitions. However, the FSM used was based on 1 variable only (i.e. len). Besides, we are still looking for the SMC results as they will be the input for any search technique to be applied. Supposedly, the states generated by SMC can be used directly in the search technique but this is still questionable. Kindly, we need your help with this matter.


1 solution

Sorry for not giving you a positive answer. The answer has to be negative, because you just demonstrated entering such domain where the FSM approach would be absurd, and also the domain of the non-testable algorithms.

Yes, many algorithms are not testable by definition, and many are testing-infeasible. For some of such algorithms infeasible for testing, some stochastic testing may make sense, but not for all of them; and, anyway, there is no feasible exhaustive testing. To give one obvious example of non-testable algorithm, consider the problem of testing if some cryptographic algorithm is cryptographically strong or not. Of course, if you know that the algorithm has the flaw, it could be theoretically possible to find out just one counter-example which is computationally feasible to demonstrate the flaw. But it such counter-example is not found, it is infeasible, just because the goal of the algorithm is to make reverse operation infeasible. Of course, the projects of testing of the cryptographic algorithms exist, but the result can be used as a proof only in the case when algorithm is successfully broken. And there are the algorithms which are not testable in principle.

But why do I think you are coming to this situation? First of all, let's consider FSM approach. FSM approach is really oriented to exhaustive testing. FSM is not "based on a variable". It is based on the set of states, and the set of transitions can be understood as the subset of Cartesian square of the set of states. But in practice, it should rather be a function over this subset. All the elements of the Cartesian square (maybe not only its subset) may carry some useful information; for example, the cell representing invalid transition may carry information explaining the reason for prohibiting the transition (for example, you should not move the door into open position when the lock is not open, you should not close the door when operator's hand is detected inside the machine). Something like that.

Now, consider the set of some Length values. The absurdity of FSM becomes especially apparent if you use floating-point value, such as double. Apparently, you have 2⁶⁴ values (some of them are semantically identical, such as different representations of NaN, but it does not change the picture). The Cartesian square will have 2⁶⁴*2⁶⁴ cells. If this is not enough, consider more realistic case, when the state is described with x, y, z, θ coordinates. Not enough? It could be easily some 100 degrees of freedom. I'll leave for your home exercise to calculate the number of states in such a FSM and the feasibility of testing. But the problem is not even the number of states, the idea is the principle: even though the set of floating-point values is formally a finite set, the idea of such data type is to represent the set of real numbers, with some limited accuracy. That model is finite, but modeled object is not only infinite set, it is also a continuum (do you understand the difference? you need to). That makes the criteria of testing itself quite fuzzy. That's why many floating-point algorithms are not only infeasible for testing, but not testable in principle.

But will the model based on purely integer state values improve the situation? Yes, it can, but it won't remove the feasibility problem. I you can figure it out by yourself.

Please see also:[^],[^],[^],[^].

So, even though I did not offer you a solution, I hope my post will help you to save time by not ramming the brick wall. You can address some stochastic testing approaches instead.

Share this answer

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900