Software Testing And Software Bugs 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 above reasons make software testing an important part of software design cycle and there are some classic methods in order to test software. These methods are divided in two categories the white and the black-box tests. The white box testing is when the tester has access to algorithms and internal data structures and the black-box when for the tester the software is like a "black-box" , has no knowledge about its implementation.

Software testing is important because it builds confidence between users - consumers to software products. That's way that we are trying to find new techniques for software testing. One of these techniques is trying to apply Artificial Intelligence techniques in software development. The first approach to this direction was by using the fuzzy theory [1] as a generalization of black box technique. This technique provides the application with invalid, unexpected data the programs trying to undercover defects of it. This seems to be good for some problem (bugs) categories but when we have to do with qualitative values as input the theory is reflecting an uncertainty about these inputs. But the model outputs are affected by this uncertainty [2].

Another technique [3] that it is proposed was the use of genetic algorithms. This algorithm randomly generates an initial test set which is modeled as a chromosome representing a possible test set. This method this to improve black box testing but removing some "bad" test cases which are unlikely to find a software bug and increasing the number of "good" cases which have more probability to produce an output with error .

Latest years the Ant Colony Optimization (ACO) started to be used in software testing. There are already some applications [4, 5] of this theory which are producing test data for evolutionary testing but the results are preliminary and none of them addressed specification-based software testing. Another approach which was proposed [6] was the use of UML Statechart diagrams and ACO for generation of test data.

This paper tries to list some of the attempts on usage of ACO in software testing describing the main idea behind of them and a small comparison between them .

The paper is organized as follows. Section 2 is an introduction to ACO theory, Section 3 refers to application of ACO theory in software testing, section 4 refers to additional considerations about testing software methods section 5 refers to a comparison with other techniques as simulated annealing and section 6 concludes.

Ant Colony Optimization Algorithm

The Ant Colony Optimization (ACO) algorithm is a probabilistic theory which is trying to find good paths through graphs. It was proposed at 1992 [6] and it was trying to find paths following the behavior of ants and the paths (between colony and food source) they use, in order to get their food. The idea behind this is simple: The ants usually move randomly . When they find a source of food while they are returning to colony they mark their way with pheromone. The next time an other ant will pass from that way will stop walking randomly and will follow the marked path. If they finally find the food source they will also mark this way with pheromones, making mark stronger. We must have also in mind the pheromones evaporation which makes pheromone to weaken by time. If the path is short enough then by time the pheromone becomes stronger and the ants are walking on the shortest path. In a long path it takes more time to ants to walk on the shortest path. The pheromone evaporation helps also in finding the shortest path because if the first ant didn't find the shortest path all other ants will follow the first, not shortest, path.

The following diagram shows what we already described.

Figure 1. The Ant Colony Optimization algorithm

The ACO algorithm since then, has been used in many scientific areas. It used giving almost optimal result in the solution of the Knapsack problem and generally to combinatorial optimization problems. Like job-shop scheduling problems, assignment problems, vehicle routing problems, routing problems, data mining and protein folding. A new area for ACO application is the software testing which is the subject of this paper.

ACO and Software testing

A first approach in using ACO for software testing [4] was involving ACO and a Markov Software Usage model. The Markov chains in mathematics is a random process where there is no need for keeping information about the past , the property of the next step depends only from the current step. In software development the Markov usage model it based on the Markov chains. The Markov chains in this case are the representation of software usage. At this point we have to mention that in software there are features that users use every day and other they use rarely or never. In software testing we must take consideration of this and do not spend too many resources and doing exhausting tests for features used rarely. In Markov chain representation we identify software states, possible transitions between them and probabilities for going from one stage to another. We can use all the above with the usage of directed graphs: where states are represented as nodes and the edges are the transitions and the probability fro going from one stage to another is the weight of the edges. What they tried [4] was to find a suitable set of test paths , through the graph representation we described above for Markov chains in software usage, which may evolve to complete test case for software products. The most common solution for solving problems of minimum graph paths are the greedy algorithms but in case of software testing this has the problem that it doesn't use many paths on graph giving short coverage. The idea here is to use the ACO which for some type of convergence has a better behavior than the greedy algorithms. As we show before on ACO introduction the ACO fits very well with graph structured problems. The ACO implementation is considered as a learning system with a fixed number of cooperative agents. These agents use a blackboard mechanism which represents the collective memory of the community. Every time an agent finds a the best, till now solution, or the best in certain time of period are allowed to write on this blackboard which means the pheromone levels for this particular solution are increased . The construction of the solution is characterized also by randomness and a pre-evaluation of possible construction steps.

The results of the proposed method we already described give results providing test paths for software testing but their results are considered preliminary [7] and they don't give answers to specification-based software testing. Instead to what already proposed it is [7] proposed the combination of Statechart diagrams and ACO for generating test data. The benefits of this method are that they use standard Statechart diagrams which usually are created during software design process and the generated test sequence covers all stages. But in order to use the ACO algorithm the first thing that must be done is to convert the Statechart diagram into a graph. An example of how this is possible is the Statechart diagram of Coffee and Cocoa Vendor Machine.

Figure 3. The Coffee and Cocoa Vendor Machine (CCVM) Statechart.

The above Statechart can be converted to the following graph:

Figure 4. The converted graph of CCVM.

The next issues that this method must address are : a way to measure how good is path in the graph, a criterion of when a solution is good enough , a method for updating the pheromone , and a way to determinate the probability from one stage to another.

After all these problems solved the application of ACO to the above graph gives an optimal solution. We are not going to explain algorithm they used to find the final solution as it is out of the scope of this paper. The only things we have to mention are that a group of ants can explore the graph produce an optimal test set of data and achieve coverage requirements.

The following figure is the optimal solution for the graph of figure 4.

Figure 5. The optimal solution for CCVM graph.

The work of Li and Lam [7] used a combination of state graphs and ACO algorithm but it didn't take in consideration the criticality of the stages. The Srivastava and others [8] compared their work with the work of Li and Lam and they proved that their Markov chain model is better that a Statechart model when using the ACO algorithm.

Their [8] technique takes in consideration the critical states of software and needs to cover them and the transitions attached to them not caring about the strict of cost [8]. But it is known that the software testing consumes around 40% of development effort. They [4] tried to do a tradeoff between coverage and cost, if the cost limitation doesn't allows full coverage they ensure that all critical states are covered. Of course there consideration about what we think as critical states, is what the developer is thinking as critical, the user or the project manager? In order to maintain a balance [8] they assumed that the critical states are the output of developer and user and project manager. After the model is build , the critical states are defined and the transition weights are know the proposed model is: Calculation of average visits in a node , then using ACO we are creating test sequences and continues to do this till we exceed the cost limit or till finding an optimal solution. The following figure 2 presents the proposed architecture we described. The benefits of this technique are: has proven effectiveness in generating test cases for software testing from a Markov chain model , it takes consideration the critical states but also takes care number of times it visits a node. Even if the cost limits are very restricting it covers most of critical nodes. Also it proved the efficiency of ACO in graph based models.

Figure 2 . The proposed architecture by [7]

Additional Considerations about methods in software testing.

Testing and validation is especially important in safety-critical software such as nuclear plants, control of planes and medical tools. A lot of effort has been spent in order to develop and improve methods for testing and validation. Two questions arise when we are talking about software methods: if the software qualifies the specification and if not why?

The method that gives answers to both questions is the checking of all possible states of program. The drawback of this method is the state explosion. The memory required to check the system increases exponentially with the number of the states. This makes this method not applicable for large systems. The memory usage becomes more reasonable if we concentrate to the second question (why my software doesn't fulfils the specifications) . If there is a software error we can discover this error without having to check all states with the usage of a guided search.

The usage of ACO helps in finding errors in states of graph without the need to pass from all graphs simulating the mechanisms the real ants use in food seeking. As we already discussed the artificial "ants" pass from one state to the other using software transitions. In their pass from the states they use the pheromone trails which in our case are suggesting paths which lead to an error state. This method has good results in practice. We don't need large amounts of memory even in large systems and gives us results in cases where other methods can't work due to memory limitations .And this is not the only benefit of this method. As we already described real ants are trying to find short paths to target (food source) . This is very useful for the developers which prefer short error traces which are easier to understand [9].

Comparison with Simulated annealing

Before starting comparing ACO and simulated annealing we must do an introduction of what is simulated annealing (SA). It is a generic probabilistic metaheuristic method which locates a good approximation to the global optimum of a given function in a large search. Sometimes provides better results than exhaustive enumeration especially in cases where the time to finish the enumeration is the first criterion and the best solution. The method is the following: Suppose that every state s of the search system is like the state of a physical system and there is a function E(s) is something like the internal energy of the system. What this algorithm is trying to do is bring the system to the state with the minimum energy. In every step the algorithm is trying to decide if it will stay to the current state or jump to state with lower energy. This continues till we have an optimal result or the available time finished. The most famous problem that solved with this method is the travelling salesman.

In software testing the algorithm selects candidate solutions which are in the neighborhood of a given candidate solution. Better candidate solution is always accepted. But sometimes not optimal solutions are accepted also hoping that later will give better solutions. When starting this method the "temperature" (the energy levels we discussed above) is high allowing any movement in search space. When the movement continues the temperature is reduced. Finally the process freezes. When we are talking about software testing a candidate solution is set of data values which represent a test-case [10] .

I tried finding some scientific papers which will compare the two methods in the field of software testing. I didn't find a paper that direct compares the two methods in this field as simulated annealing (SA) is older method than ACO. But I found a paper [11] that compares the two methods in a problem that both can solve the salesman problem (TSP). I will not get into technical details regarding the comparison test . The next table gives the performance of the two algorithms in solving the salesman problem.

Table 1. Comparison of ACO algorithm and simulated annealing in solving TSP

Other researchers [12] who study the meta-heuristics which can find the optimal solution at short time also report that the ACO algorithm shows better performance than simulated annealing when trying to solve the traveling salesman problem (TSP). It is obvious that ACO Algorithm which is newer that SA is faster in solving the TSP problem