Abstract: Oracle is one of the most difficult and expensive parts in automated software testing. It is explored in this paper to use Radial Basis Function Neural Networks (RBF NN) to construct an automated oracle model. The automated oracle generate the approximate outputs that are close to expected outputs after training. Actual outputs are then compared with the approximate outputs to determine if there is a failure when software is running. Oracle can therefore be implemented automatically and the precision be adjusted by parameters. It will save a lot of time and cost in software testing.
INTRODUCTION
Oracle includes two processes which are to generate expected outputs and to compare actual outputs with them (Memon et al., 2003). Oracle is generally implemented manually. It is important to automate the oracle in automated software testing in which these two processes are automatically implemented. A perfect automated oracle would be behaviorally equivalent to the Application Under Test (AUT) and completely trusted, i.e., for each possible input specified for the AUT it would always compute a correct output. As a result it is very difficult to develop a perfect oracle. There are very few techniques that have been proposed to automate oracle. Testers are in general assumed to provide the expected behavior of the software in the form of a table of pairs (Peters and Parnas, 1994), logical expressions which must be satisfied by the software (Bousquet et al., 1999), or temporal constraints that specify conditions which must not be violated during software execution (Dillon and Ramakrishna, 1996). In capture/replay tool which is used to test Graphical User Interfaces (GUI) software expected outputs are saved while recording test scripts or inserted in the test scripts manually (Andersson and Bache, 2004; Chen et al., 2005; Ostrand et al., 1998). It however need a lot of labor because there are different expected output for different input of the software. Chen proposes a specification based testing approach for GUI software. The expected behavior is manually contained in the model of the software (Chen and Subramaniam, 2002). Memon presents a planning method to generate expected outputs (Memon and Xie, 2005). It needs to construct GUI model and set conditions for each operator manually. Schroeder can automatically generate a large combinatorial test set that include inputs and expected outputs by manually generating the expected relationship between input and output from requirement specification documents (Schroeder et al., 2002). To implement more automated oracle, Aggarwal explores using neural networks based approach to generate expected outputs (Aggarwal et al., 2004) for the triangle classification problem (Aggarwal and Singh, 2001). By experiment they made the conclusion that neural networks can be used as oracle with reasonable degree of accuracy for classification problem in software testing.
GUI software can be logically divided into two parts, one is GUI and the other is underlying logic implementation. In the underlying logic implementation the relationship from inputs to outputs is in nature a function. When the function is continuous an automated oracle is designed in this paper to generate expected outputs and to compare actual outputs with them. AUT in this paper is used to represent the underlying logic implementation of the GUI software. Radial Basis Function Neural Networks (RBF NN) are then used to implement the oracle. RBF NN has gained much popularity for that it can approximate complex nonlinear mappings directly from the input and output data with a simple topology structure (Alippi et al., 2001; Duda et al., 2001; Karayiannis and Mi, 1997; Li et al., 2004; Roy et al., 1997). RBF NN can approximate arbitrary continuous function effectively without the need to have knowledge of that function. Few experiments have been conducted to validate the results of our method.
STATEMENT OF THE PROBLEM
AUT accepts inputs from a user or system, computes results and output them.
AUT discussed in the paper is a determined program. That is, for the same inputs,
program will always produce a determined output. Let x = (x1,…,xn)
be the input vector to AUT and y = (y1,…, ym) be the
output vector from the AUT. Then the relationship between x and y is y = f(x).
Each component yj in y is also a function of x, i.e., yj
= fj(x), j = 1,…,m.. The function investigated in this paper is
continuous. Let
(1) |
where ||.|| is the size of a set. From the Eq.
1 it can be seen that the size of Vx is determined by the size
of
RBF NEURAL NETWORKS
A RBF NN can be regarded as a three-layered networks with input, hidden and output layers (Alippi et al., 2001; Duda et al., 2001; Karayiannis and Mi, 2003; Li et al., 2004; Roy et al., 1997). Each hidden neuron in RBF NN represents a RBF. An output neuron computes the weighted sum of the hidden neurons’ outputs. The output of an output neuron is as follows:
(2) |
where xεRn is an input vector, φ is a radial basis function in hidden layer, wjεR is the weight between jth hidden neuron and the output neuron, cjεRn is the center of the RBF in the jth hidden neuron and m is the number of hidden neurons. ||x-cj|| stands for the distance between the input vector x and the RBF center cj . From the Eq. 2 it can be seen that the output of the RBF NN is a weight sum of the hidden layer’s RBF. A RBF is a local function. One of the special RBF commonly used is a Gaussian function which has the form as follows:
| Fig. 1: | The architecture of a RBF NN with two inputs, three neurons in hidden layer and one output |
(3) |
where σ>0 is a parameter. Generally Gaussian functions are superior to sigmoid function in estimating a broad class of functions. By using the Gaussian function RBF NN can approximate arbitrary continuous functions in theory. In MATLAB7 the parameter σ in the Eq. 3 is replaced by the parameter β:
(4) |
where β is the width of the neuron in hidden layer.
Figure 1 is the architecture of a RBF NN with two inputs, three neurons in hidden layer and 1 output.
A RBF NN is usually trained in two important steps. The first step is to find centers of the networks, which are parameters of hidden neurons. The second step is to determine the weights between the hidden layer and output layer. More information about training algorithm can be found in references (Chen et al., 1991; Roy et al., 1997; Schilling et al., 2001).
AUTOMATED ORACLE BASED ON RBF NEURAL NETWORKS
General model of oracle is as Fig. 2. The expected outputs of the AUT are generated according to inputs and then compared with the actual outputs from AUT. If they are not same, it implies a failure. The process of generating expected outputs is traditionally implemented manually or by formal specification such as Z specification which is manually generated from specification documents of the AUT. Expected outputs are then compared with actual outputs by determining if they are exactly same. If they are same, it means no failure. Otherwise a failure is reported. To automate oracle, a new oracle is presented in Fig. 3.
| Fig. 2: | General oracle model |
| Fig. 3: | Automated oracle model |
In our automated oracle model the relationship between inputs and outputs are learned from a small set of training data which consists of inputs and expected outputs and the relationship learned is then used to generate approximate outputs for AUT. Let X and Y be the domain and co-domain of the AUT. The training set is:
(5) |
where S(x) is the expected output which is computed from the specification of the AUT when the input is x. Train RBF NN from D to generate the relationship O:X→Y for AUT. Trained RBF NN is then used to generate the approximate outputs for any input of the AUT. The approximate outputs are not as same as the expected outputs. But they can approach the expected outputs in any precision. Comparison process is now implemented by computing the difference between the actual outputs and the approximated outputs as follows:
(6) |
where t and α are actual outputs and approximate outputs respectively and ε controls the criterion if an actual output t is right or not. We can adjust ε between test precision and test cost. In experiments we will describe t he effect of the ε. If |t-α|ε = 0, it means that the actual outputs are right within the precision ε. Otherwise, if |t-α|ε> 0, it means that a failure occurs because the actual outputs are not right within the precision ε. The difference between the actual and approximate outputs is described by |t-α|-ε. The larger it is, the more difference there is. RBF NN has been established to be an effective tool for approximations of the function. It can approach any continuous function in theory. This feature can be used to generate approximate outputs in an automated oracle. To implement the automated oracle, two processes must be automated. One is to generate approximate outputs by RBF NN and the other is to compare the actual outputs from AUT with the approximate outputs. Automated oracle can be summarized as follows.
| Step 1: | Generate training set and set the parameter β. |
| Step 2: | Train RBF NN by the training set. |
| Step 3: | When the training process finishes, keep the weight and go to step 4. |
| Step 4: | Set test precision ε. |
| Step 5: | Get an input from the specification of the AUT and then input it to RBF NN and AUT respectively. Get the approximate output α from the RBF NN and the actual output t from the AUT. |
| Step 6: | Compare α and t according to the Eq. 6. Determine if there is failure or not by the result. |
| Step 7: | Repeat step 5 and 6 until other inputs of the AUT are tested. |
| Step 8: | If it is needed to test in different precision, go to step 1. Otherwise, this process finishes. |
EXPERIMENTS
The goal of the experiments is whether the method proposed is effective, i.e., if the oracle can generate the approximate output which is close to the expected output and if the test precision can be adjusted by parameters. In our experiment we used single input variable, two input variables and multi input variables function respectively. The number of the output variables is one. It can be generalized to the situations of multi output variables. We use the parameter β in the Eq. 4 which is used in MATLAB 7 instead of the parameter σ in the Eq. 3.
AUT of single input variable function: Let the relationship between input and output of the AUT is as follows:
(7) |
Where 0≤x≤2π. It is a single input variable function. Generate training set of 100 samples manually. The variable x is evenly dropped from the interval [0,2π] and the variable y is computed manually. We set the parameter β = 0.1. When training process finishes, test the output on 10000 samples to see if the approximate output is close to the expected output. The expected outputs, approximate outputs obtained from RBF NN and the difference between them is as Fig. 4. The difference is in the interval [-0.0287,0.0834]. It shows the difference is small enough when β is set to 0.1.
Different test precision can be achieved when changing the value of β (Table 1). The column Min and Max in Table 1 are the min and max difference, respectively between the expected and approximate outputs. Column ε is the test precision that can be achieved under the different value of β. It shows that we can change the value of the parameter β to test the AUT in different demand of test precision in software testing. If a precision ε below 0.003 is needed, we can set β = 0.25. If the actual outputs are in the interval [α-0.0023, α+0.0023], where α are the approximate outputs obtained from the RBF NN, it means there is no failure. Otherwise, it means a failure occurs.
AUT of two input variables function: Let the relationship between input and output of the AUT is as follows:
| Fig. 4: | Plots of the expected, approximate outputs and their difference when β = 0.1 for the function in Eq. 7 |
| Table 1: | Precision achieved under the different value of β for the function in Eq. 7 |
| Fig. 5: | Figures of the expected, approximate outputs and their difference when β = 5 for the function in Eq. 8 |
Table 2: |
Precision achieved under the different value of β for the function in Eq. 8 |
(8) |
where 1≤x1,x2≤5. It is a two input variables function. Generate training set of 100 samples manually. The variables x1 and x2 are evenly dropped from the interval [1,5]. The variable y is computed manually. We set the parameter β = 5. When training process finishes, test the output on 400 samples to see if the approximate output is close to the expected output. The expected outputs, approximate outputs obtained from RBF NN and the difference between them is as Fig. 5.
| Table 3: | Precision achieved under the different value of β for the function in Eq. 9 |
The difference is in the interval [-0.0673,0.0687]. It shows the difference is small enough when β is set to 5.
Different test precision can be achieved when changing the value of β (Table 2). The column in Table 2 has the same meanings as Table 1. It shows that we can change the value of the parameter β to test the AUT in different demand of test precision in software testing. If a precision ε below 0.04 is needed, we can set β = 4. If the actual outputs are in the interval [α-0.0361,α+0.0361], where α are the approximate outputs obtained from the RBF NN, it means there is no failure. Otherwise, it means a failure occurs.
AUT of multi input variables function: Let the relationship between input and output of the AUT is as follows:
(9) |
where 1≤x1,x2,x3≤5. It is a three input variables function. Generate training set of 125 samples manually. The variable x1, x2 and x3 is evenly dropped from the interval [1,5] and the variable y is computed manually. We set the parameter β = 5. When training process finishes, test the output on 1000 samples to see if the approximate output is close to the expected output. The difference is in the interval [-0.1475,0.0657]. It shows the difference is small enough when β is set to 5.
Different test precision can be achieved when changing the value of β (Table 3). The column in Table 3 has the same meanings as Table 1. It shows that we can change the value of the parameter β to test the AUT in different demand of test precision in software testing. If a precision ε below 0.01 is needed, we can set β = 10. If the actual outputs are in the interval [α-0.0091, α+0.0091], where α are the approximate outputs obtained from the RBF NN, it means there is no failure. Otherwise, it means a failure occurs.
CONCLUSIONS
An automated oracle is proposed in this paper for automated software testing. From the results above we conclude that RBF NN can be used to implement the automated oracle. It can generate approximate outputs which are close to expected outputs for AUT. The test precision can be adjusted by parameters. As a result AUT can be tested in the precision needed. The actual outputs from AUT are compared with the approximate outputs in an interval to determine correctness. If actual outputs are in the interval specified by the approximate outputs and the test precision, it means there is no failure. Otherwise, a failure is exposed. By the method we need not to manually generate expected outputs for all possible inputs of the AUT. It can therefore save a lot time and cost in software testing.
ACKNOWLEDGMENT
The authors would like to thank the reviewers for their careful reading of this paper and for their helpful and constructive comments.