An automatic test case generation method based on user session and agglutinate hierarchical clustering algorithm

Abstract

The development of web applications based on the Internet, especially the mobile Internet, is very rapid and the traditional test methods have limitations. This paper proposes a method based on user session similarity and an improved agglutination clustering algorithm to automatically generate test cases. This approach not only guarantees the validity of the test, but also maintains the order in the user’s session. This method gives the definition of similarity between two URLs, and then uses a dynamic programming algorithm to calculate the similarity between two user sessions. Secondly, a bottom-up aggregation-level algorithm is used to similarly cluster user sessions. Finally, a new method was used to select representative test cases and remove redundant test cases. The experimental results show that the method of this paper can generate suitable test cases quickly and efficiently.

Keywords

User sessions test case test suits agglutinate hierarchy clustering

1. Introduction

There are many widely used tools and methods for automatic testing. For example, Xie and Luo [21] proposed a new automatic testing approach to check the invoke state of the appointed application interfaces (APIs) of software package, which is an important test item for the acceptance test Recording/Replay techniques are typically used for automated functional testing and performance testing. Record/Replay tools record the actions of test engineers. And under the pressure of high loads, executing them against the system can acquire the performance indexes such as throughput, user concurrency, response time. But test engineers usually spend plenty of time recording or scripting the actions, and generating test data manually. However, it only represents the operations of test engineers and cannot stand for all the realistic users. In other words, the generated loads by test script may not be in accordance with the scenario acted by actual users. Therefore, the validity of testing results cannot be guaranteed. Nowadays, web applications have the characteristics of distribution, heterogeneity and independent platform, which makes the performance testing technology for traditional web applications not suitable anymore.

To solve the problems mentioned above, this paper proposes a method that the user sessions data is utilized to improve the automatic performance testing. User sessions bring valuable insight into dynamic behavior of web applications. Over the past decade, many researchers have made important contributions to the testing method based on user sessions [1]. But seldom researchers have concerned about user-session-based technique with performance testing. The authors argue that it’s meaningful to combine performance testing with user-sessions-based technique. The data acquisition technique is used in user sessions, so the web testing method based on user sessions can create test cases automatically and reduce artificial efforts. Moreover, test cases generated by user-session-based approach can reflect the behaviors of real users, which is of significant importance for web applications performance testing; meanwhile, user sessions can be easily captured and available to test engineers. Thus, it is feasible to use user sessions which are recorded in server logs to generate performance test cases.

However, the number of test cases generated by user sessions without processing is usually enormous and possibly unfeasible. Besides, a considerable numbers of test cases are redundant. That is, the redundant test cases exercise the same behaviors and output similar test results. In addition, it’s time-consuming to execute all test cases. For these reasons, reduction, prioritization and selection of user sessions should be applied for user-session-based performance testing, which can effectively enhance the efficiency and performance of test suites. Clustering is a widely-used technique in the field of data mining that organizes similar objects into a single collection. By using cluster technology, user sessions can be clustered to different classes which can be taken as various test suites. From each test suites, typical test cases are selected and the redundant ones are deleted. Therefore, the remaining test cases are typical and valid.

The approach proposed in this paper aims at reducing the manual effort when test engineers design the performance test cases and output the realistic, valid, optimized test suites to simulate system behaviors. One of innovative key points is that sequence alignment algorithm is used to calculate the similarity between user sessions, which makes the generated test suites more meaningful because the order of user sessions is ensured. The other key point is that agglutinate hierarchy clustering algorithm is employed to cluster typical test cases based on user sessions and reduce redundant test cases.

2. Related work

2.1 Performance testing

There are currently two methods for generating test cases in the field of performance testing: handwritten scripts and recording/playback methods. In many cases, due to the complexity and the lack of effective automated test tools, performance testing is still done by hand-writing scripts that the user behaviors are described as a subprogram [2, 3]. For each virtual user, each subprogram is performed to describe certain aspects of each virtual user’s behaviors. The hand-written scripts method is the most flexible which is suitable for all kinds of web applications. However, it needs a lot of manual work to construct the scripts, contrary to the idea of automated testing.

Record/replay technology is also widely employed by many automated test tools. For example, software load testing tool Load Runner [4] can realize automation testing by recording and replaying the operations performed by real users. There is no demand for programming skills to conduct the test cases, but test engineers usually spend a lot of time in recording or designing the test scripts manually. Moreover, it only represents the operations of test engineers and cannot stand for all the true users, which means the loads generated by test script may not accord with the loads generated by actual users. Therefore, the validity of the testing results can not be ensured.

Zhen and Yun [5] proposed a method which leverages user session data to assist web application performance testing. The researchers discussed the prospect of performance test area and indicated the insufficiency of traditional performance test approach. But there only presents a process model without a specific method to cluster the user sessions or optimize the test cases. Quan and Lu [6] presented a session-based user behaviors Meta model (SUBM) to automatically generate test cases for user level QoS load testing. SUBM applied decision-tree-based algorithm to cluster name-value pairs in server logs for automatic test data generation and employed the Longest Common Subsequence (LCS) algorithm to seek common Hyper Text Transfer Protocol (HTTP) request sequences for test scripts generation. However, they did not apply cluster algorithm but simply used LCS algorithm to process the Uniform Resource Location (URL) sequences, so the time complexity is high and the test suite is incomplete.

2.2 User-session-based technique and web sessions clustering

Although most of researches on user-session-based technique were done for functional testing, it’s still worth reviewing predecessors’ work. For example, Elbaum et al. [7] firstly leveraged the collection of client’s request information in server logs to conduct test cases and reported the experiment results by comparing new test generation techniques with traditional ones. Rothermel and Harrold [8] and Chen et al. [9] proposed a theory that the selection of test cases can improve the test efficiency because a considerable test cases can lead to similar test results. Nowadays, some researchers have applied cluster algorithm to assist test cases selection. For example, Sampath et al. [10] regarded user sessions as entities when apply it to cluster user sessions, and on that basis, they achieved user-session clusters by using clustering algorithm, then found out the representative user session from each test suite for simplifying the test suites. They also programmed a practical user-session-based test tools and showed the experimental results in their researches [13]. In the research of Wu and Gao [14], hierarchy clustering technique was firstly applied to a huge set of real internet traffic traces so as to identify web user sessions. A novel bottom-up clustering algorithm is proposed and compared with the classical threshold-based scheme. Liu et al. [15] proposed a method called User Sessions Clustering based on Hierarchical Clustering algorithm (USCHC) for test cases optimization. The distance between user sessions is calculated and agglutinate hierarchical clustering algorithm is adopted to cluster the initial test cases, then the test suited with various types are produced. The research not only considers the similarities of the URLs sets, but also the similarities of data type.

However, for most of the methods in the literature to deal with cluster user sessions, sessions are regarded as sets of visited pages within a time period without considering the sequence of click-stream visitation. In this paper, the authors argue that it’s significant to maintain the order of user sessions because the order of URLs in user sessions reflects the operation order of real users. In order to generate the real loads, it’s essential to consider the sequentiality of each user sessions. For most of the cluster algorithms, when clustering user sessions are used, sessions are treated as unordered sets of URLs. The measures used to compare the similarity between sessions are simply based on intersections of these sets such as cosine measure and Jaccard measure [20] which is as follow. X and Y mean the set of elements.

$\displaystyle\textit{sim(X,Y)}=\frac{X^{t}\cdot Y}{\left\|X\right\|\left\|Y% \right\|}$ (1) $\displaystyle\textit{sim(X,Y)}=\left|{\frac{X\cap Y}{X\cup Y}}\right|$ (2)

3. User-session-based performance testing based on a modified hierarchy clustering algorithm

The process model and algorithm of the proposed method are shown in Fig. 1. A detailed description of the algorithm will be given later.

Figure 1.

Process model of the modified hierarchy clustering algorithm.

Firstly, the server logs are preprocessed, and a dynamic programming algorithm is utilized to calculate the similarities between two user sessions. Secondly, a bottom-up agglutinate hierarchical algorithm is employed to cluster the similar user-sessions. Thirdly the authors propose a method to select the representative test cases and delete the redundant test cases. Finally, the typical test suites are generated.

The under-mentioned algorithm firstly measures the distance between user sessions on the basis of the similarity between user sessions, then clusters initial user-session-based test cases; after the test cases are clustered into test suites, relevant and typical test cases are selected to replace suites.

Algorithm 1 A modified hierarchy clustering algorithm for user-session-based performance testing
Input
Initial User Sessions $U=\left\{{\textit{US}_{1},\textit{US}_{2},\ldots,\textit{US}_{n}}\right\}$
Each User session includes the url requests $US_{i}=\left\{{\textit{url}_{1},\textit{url}_{2},\ldots,\textit{url}_{n}}% \right\}\left({1\leqslant i\leqslant n}\right)$
Output
optimized test cases R
Algorithm Procedure Initialization. Calculate distance matrix $M$ according to the following formula $d\left({\textit{US}_{i},\textit{US}_{j}}\right)=\left\|{1-\textit{sim}\left({% \textit{US}_{i},\textit{US}_{j}}\right)}\right\|$ , (The definition of $\textit{sim}(\textit{US}_{i}$ , $\textit{US}_{j}$ ) will be given later) Initial cluster set $C_{i}=\textit{US}_{i}\left({1\leqslant i\leqslant n}\right)$ Obtain the most approximate set of $C_{j}$ by the above formula Then $C_{i}=C_{i}\cup C_{j},C=C-C_{j}$ Recalculate the distance between $C_{i}$ and $C_{k}$ , $k=1,2,\ldots,n\ \ k\neq i$ $d_{\textit{avg}}\left({C_{i},C_{j}}\right)=\frac{1}{n_{i}\times n_{j}}\mathop{% \sum}\limits_{\textit{US}\in C_{i}}\mathop{\sum}\limits_{\textit{US}^{\prime}% \in C_{j}}\textit{sim}\left({\textit{US},\textit{US'}}\right)$ Repeat Steps 2 and 3 until no more user sessions can be clustered and test suites are acquired.
$C=\left\{{C_{1},C_{2},\ldots,C_{m}}\right\},C_{i}$ means the set of user sessions $\left\{{\textit{US}_{1},\textit{US}_{2},\ldots}\right\}$ Check the redundancy, $\textit{TS}_{i}=\emptyset$
for each $C_{i}$ in $C$
for each $\textit{US}_{t}$ in $C_{i}$
if $\textit{US}_{t}$ is the longest in $C_{i}$
then $C_{i}=C_{i}-\left\{{us_{t}}\right\}$
for each url ${}_{i}$ in $\textit{US}_{t}$
if url ${}_{i}$ is fully contained in $\textit{TS}_{i}$ , continue
else $\textit{TS}_{i}=\textit{TS}_{i}+\left\{{us_{t}}\right\}$
$T=\left\{{\textit{TS}_{1},\textit{TS}_{2},\textit{TS}_{3},\ldots,\textit{TS}_{% m}}\right\}$ is the set of test suites acquired

3.1 Similarities between user sessions

The first problem is how to measure the similarity between sessions on the premise of ensuring the sessions’ sequentiality. Most of the previous related works apply either Euclidean distance for vector or set similarity measures, but the disadvantages are obvious: (1) The transferred space could be high-dimensional; (2) The original click stream is naturally a click sequence. It cannot be fully represented by a vector or a set of URLs without considering the order of clicks; (3) Euclidean distance has proven not suitable for measuring similarity in categorical vector space.

The authors consider the original session data as a set of sequences, and apply sequence similarity measure to measure similarity between sessions. Sequence alignment actually is not a new topic; in the field of biology research, there already exist several algorithms for solving sequence alignment problems [16, 17]. In the light of the basic ideas of these algorithms, the technique is put forward to measure the similarity between session sequences.

There exist two steps in definition of session similarity in this paper. Firstly, it’s necessary to define similarity between two web pages because each session includes several web pages; the second step is to define session similarity using page similarity as an inner function.

3.2 Preprocess server logs files and calculate the similarity between web pages

It’s known that most of the web applications use directory tree to organize web pages or other kinds of recourses. Therefore, every URL is layered. It can make use of this characteristic to measure the difference between each URL.

One example is the following three URL:

1.
http://www.unl.edu/ucomm/research/index.html
2.
http://www.unl.edu/ucomm/research/current.html
3.
http://www.unl.edu/newsroom/index.html

It’s not difficult to find out that URL1 and URL2 are very similar pages in the same subdirectory “research”. Besides, there is some similarity between URL#1 and URL#3, but the similarity is obviously not as strong as the similarity between URL#1 and URL#2 in the previous example. A systematic method is needed to give a numerical measure for calculating the similarity between two URLs.

In order to measure the similarity between two web pages, each level of a URL is presented by a token. Thus, the token string of the full path of a URL is the concatenation of all the representative tokens of each level. This process corresponds to the labeled tree structure of a website as shown in Fig. 2.

Figure 2.
A labeled tree structure of a web application.

For example, ‘www.unl.edu/ucomm/current/information.html’ in Fig. 1 is presented by the token string as ‘0111’, and ‘www.unl.edu/newsroom/realeases/publications.html’ is presented by token string as ‘0200’. Every url of the Web application can be translated into a token string.

The web similarity computation is divided into two steps:

Step 1
Each corresponding token of the two token strings is compared one by one from the beginning, and this process stops when the first pair of different tokens appears, then record the number of the tokens which are the same as $N$ .
Step 2
Suppose the number of the longest token string is $M$ . The similarity of two web pages is computed by the length of the longest token string in the web pages; and then a weight is given to each level of tokens: the last level of the longest token string is given weight 1; The second to the last is given weight 2, etc. Next, the similarity between two token strings is defined as the sum of the weight of those matching tokens which are divided by the sum of the total weights. The formula is as follow:

$\frac{\sum\limits_{i=M-N+1}^{M}i}{\sum\limits_{j=1}^{M}j}$ (3)

The variables $i$ and $j$ are the weights of the $i$ and $j$ positions of the token string. For example, the similarity between strings “010” and “011” is 0.833.

If the two pages are totally different, which means that they have no same corresponding tokens, their similarity is 0.0. If the two pages are exactly same, their similarity would be 1.0.
3.3 Calculate the similarity between two user sessions

After defining the method of calculating the similarity between two URLs, we can measure sessions’ similarity on this foundation, and use dynamic programming technique to find the best matching between two sequences. Most of the sequence alignment algorithms are on the basis of dynamic programming. In fact, Sequence alignment is a fundamental operation in bioinformatics [18]. Pairwise sequence alignment is used to determine homology (i.e., similar structure) in both DNA and protein sequences, so we can gain insight into the functions of DNA and protein sequences. In this paper, Basic ideas from Sequence alignment are used to calculate the similarity between each session.

A scoring system is used to find out the optimal matching between two session sequences. An optimal matching is an alignment with the highest score [19]. The score for the optimal matching is then used to calculate the similarity between two sessions. The followings are the principles in matching the sequences:

Definition 1 The session sequences can be shifted to the right or left to align the pages as many as possible. For example, session# 1 includes a sequence of URLs 1, 12, 121, 122; here each web page is represented by its token string as described previously. Suppose session#2 includes a sequence of visiting to URLs 12, 121, and 122. The best matching between the two session sequences can be achieved by shifting session#2:

US#1	1	12	121	122
US#2	$-$	12	121	122

Definition 2 Gaps are allowed to be inserted into the middle, beginning or end of session sequences, which is helpful for achieving better matching.

Definition 3 Each identical matching such as a pair of pages with similarity 1.0, is given a positive score 20; each mis-matching such as a pair of pages with similarity 0.0 or a matched page with a gap, is given a penalty score $-$ 10. The variable a is defined as the similarity between two pages, apparently $\textbf{0.0}\leqslant{\bm{\alpha}}\leqslant\textbf{1.0}$ , and the score for their matching is between $-$ 10 and 20. However, the matching score is corresponding with the length of the longest token string. The final matching score is:

$\textit{sim}(\textit{US}_{1},\textit{US}_{2})=\frac{\textit{Score}}{\textit{% Maxlength}(\textit{US}_{1},\textit{US}_{2})\cdot 20}$ (4)

The matching score of US1 and US2 is as followed.

US#1	1	12	21	22
US#2	$-$	12	21	22
Score	$-$ 10	20	20	20

According to the Eq. (4), the similarity between US#1 and US#2 is 0.625.

It is not simply counts the number of identical web pages when session sequences are aligned. Instead, a scoring function based on web page similarity measure is employed. For each pair of web pages, the scoring function gives a similarity score where higher score indicates higher similarity between web pages. A pair of identical web pages is only a special case of matching – the scoring function returns 1.0 which means that the two pages are exactly the same.

The problem of finding out the optimal matching can typically be solved by using dynamic programming method. Here a specific example is presented to describe the process of the method.

Suppose there are two user sessions:

US#3

=

{1, 123, 126, 1, 2},

US#4

=

{1, 12, 123, 124, 12, 22}

Figure 3.

Session matching matrix.

The process can be described by using a matrix as shown in Fig. 3. One sequence is placed along the top of the matrix and the other sequence is placed along the left side. A gap, being added to the start of each sequence, indicates the starting point of matching. The process of looking for the optimal matching between two sequences is actually to search an optimal path from the top left corner to the bottom right corner of the matrix. Any step in any path can only go right, down or diagonal. Each shift based on diagonal corresponds to the matching between two web pages. The right shift means that a gap is inserted into the vertical webpage sequence to match the webpage in the horizontal sequence. And the downward shift means that a gap is inserted into the horizontal webpage sequence to match the webpage in the vertical sequence.

In order to solve the optimal matching problem, the dynamic programming algorithm propagates scores from the matching start point (upper-left corner) to the destination point (lower-right corner) of the matrix. The optimal path is then achieved through the back propagation from destination point to starting point. In the given example, the optimal path is connected by arrows where the numbers in brackets indicate the step number in back propagation. Besides, it shows the best matching pattern. The scores of any element in the matrix are the maximums in the following three directions: left, upper and upper-left. For example:

Figure 4.

Calculation example.

The score of $x_{4}$ is the maximum score among $x_{1}+\textit{sim(c,d)}$ , $x_{2}-10$ and $x_{3}-10$ .

The score in the lower-right corner is the optimal sequence alignment score. After finding out the final score for the optimal session alignment, the final similarity between the two sessions is computed by considering the final optimal score and the length of the two sessions.

The algorithm of this part is concluded as followed.

Algorithm 2
Input
Initial user sessions US ${}_{1}$ and US ${}_{2}$
$\textit{US}_{i}=\left\{{\textit{url}_{1},\textit{url}_{2},\ldots,\textit{url}_% {n}}\right\}$
The length of US ${}_{1}$ is $M$ and the length of US ${}_{2}$ is $N$
Output
The matching score between US ${}_{1}$ and US ${}_{2}$
Algorithm Procedure
Initial the matching matrix Ma
Ma[0][0] $=$ 0;
for( $i=$ 1; $i<=M$ ; $i++$ )
Ma[0][ $i$ ] $=$ $M$ [0][ $i-$ 1] $-$ 10;
for( $j=$ 1; $i<=N$ ; $j++$ )
Ma[ $j$ ][0] $=$ $M$ [ $j-$ 1][0] $-$ 10;
One sequence is placed along the top of the matrix and the other sequence is placed along the left side
for( $i=$ 1; $i<=M$ ; $i++$ ){
for( $j=$ 1; $j<=N$ ; $j++$ ){
Ma[ $i$ ][ $j$ ] $=$ Max(Ma[ $i-1$ ][ $j-1$ ] $+$ sim(US ${}_{1}$ [ $i$ ], US ${}_{2}$ [ $j$ ]), Ma[ $i-1$ ][ $j$ ] $-$ 10, Ma[ $i$ ][ $j-1$ ] $+$ 10)
}
}
Calculate the final matching score
Score $=$ Ma[ $M$ ][ $N$ ];
$\textit{sim}\left({\textit{US}_{1},\textit{US}_{2}}\right)=\frac{\textit{Score% }}{\textit{Maxlength}\left({\textit{US}_{1},\textit{US}_{2}}\right)\times 20}$

3.4 Clustering user sessions with hierarchy clustering algorithm

On the basis of the distance measure method in the above description, agglutinate hierarchy clustering algorithm is employed to cluster the test cases generated from user sessions now. In data mining, agglutinate hierarchical clustering is a method of cluster analysis which seeks to build a hierarchy of clusters. Each cluster starts from its own set. When each set gradually moves up to the hierarchical structure, the sets conforming to the clustering are merged. And the cycle repeats itself until the terminal condition of clustering is satisfied. Compared to K partitioning clustering, the agglutinate hierarchical clustering has the advantage of fewer input parameters. More importantly, agglutinate hierarchical clustering can apply to numerical data as well as categorical data. Figure 5 shows how the agglutinate hierarchical clustering algorithm is working.

Figure 5.

Agglutinate hierarchical clustering.

The modified clustering algorithm is described as follow.

Step 1:

Initially, each test case is regarded as a test suite. The initial distance matrix is generated, then two sessions with the minimum distance are clustered into one test suite from the distance matrix.

Step 2:

If the number of test suites meets the demand, then quit, otherwise continue clustering (a minimum distance $d_{\min}(i,j)$ is defined to stop the algorithm), then calculate the distance matrix. The distance between new suites can be calculated by Eq. (3).

$d_{\textit{avg}}(C_{i},C_{j})=\frac{1}{n_{i}n_{j}}\sum\limits_{\textit{us}\in C% _{i}}{\sum\limits_{\textit{us' }\in C_{j}}{\left|{\textit{US}-\textit{US'}}% \right|}}$ (5)

Where $C_{i}$ denotes the $i^{th}$ test suite, and $C_{j}$ denotes the $j^{th}$ test suite; $n_{i}$ and $n_{j}$ are the size of each test suite; $d_{\textit{avg}}(C_{i},C_{j})$ denotes the average distance between two test suites.

Step 3:

Output the final clustering result of test cases as the input for optimizing the test suites.

3.5 Delete redundant test cases

The test cases in each test suit generated by agglutinate hierarchy clustering exercise similar features of the application, and the performance results are still the same. It means that a considerable number of test cases are reluctant. If test cases picked in a test suite can cover the code area just as the corresponding test suit, so the test cases set can be formed a new test suite to replace the older one.

Suppose

$C_{i}=\left\{{\textit{US}_{1},\textit{US}_{2},\ldots,\textit{US}_{n}}\right\},% \quad\textit{US}_{k}=\left\{{\textit{url}_{1},\textit{url}_{2},\ldots,\textit{% url}_{n}}\right\}\left({1\leqslant k\leqslant n}\right),\quad\textit{TS}_{i}=\emptyset$

Step 1
Choose one test case US ${}_{k}$ whose sequence is the longest into TS ${}_{i}$ , so $C_{i}=C_{i}-\left\{{US_{k}}\right\}$ .
Step 2
Keep looking for the test case US ${}_{p}$ with the longest sequence in new $C_{i}$ , then judge if each URL fragment in test case US ${}_{p}$ appears in TS ${}_{i}$ , then $C_{i}=C_{i}-\left\{{US_{p}}\right\}$ , and $C_{i}$ remains unchanged, otherwise $C_{i}=C_{i}-\left\{{US_{p}}\right\}$ , $TS_{i}=TS_{i}+\left\{{US_{p}}\right\}$ .
Step 3
Repeat step 2 until $C_{i}=\emptyset$ , and TS ${}_{i}$ can replace the original test suite.

Finally, the further optimized set of test suites can be acquired.
4. Case study

This paper will show a running example with an e-business ordering web application to illustrate the test cases generation process.

4.1 E-commerce site

An online book shopping site is used in this experiment. The website can be downloaded at http://www.gotocode.com. Both the Tomcat server and the SQLServer database have been used. The main functional modules include home page, registration, shopping cart, management and login. The experiment focuses on website search, browsing, registration, shopping cart and other functions which are similar to those in other popular websites. The database consists of 12 tables for recording book information, transaction information and other data objects. It uses JavaScript and cookies to provide authentication and personalization services. The site has a total of 145 books in 8 types.

Figure 6.

E-commerce site used in experiment.

4.2 Collecting user sessions

In order to collect user session data, our study team recruited some college students as volunteers. Volunteers were instructed to play the role of customers and encouraged to access e-commerce sites according to their own habits. Web logs are collected in a week after taking into account the time and efficiency of the experiment.

4.3 Preprocess the user session

After collecting the user sessions from the sever logs, it is needs to preprocess the session data. Uncorrelated and invalid data should be eliminated from the user sessions. There are two types of invalid data that should be eliminated:

1.
Usually, the users of Web application do not explicitly request the graphics files and css files. Therefore, ending of the URL with jsp, jpeg, jpg, gif, css and js should be deleted.
2.
The failed requests whose return code is 4xx (request error) or 5xx (server error).

After the user sessions are cleaned, each URL is represented by a token string.

4.4 Experimental results and analysis

After the data preprocessing, a total of 120 valid user sessions were collected. And there are 10 user session examples as follows:

$\displaystyle u_{1}[\ ]=\{``0",``0",``01",``0",``3"\}$ $\displaystyle u_{2}[\ ]=\{``0",``01",``016",``21"\}$ $\displaystyle u_{3}[\ ]=\{``0",``012",``023",``233",``2331"\}$ $\displaystyle u_{4}[\ ]=\{``3",``22",``21",``0",``012"\}$ $\displaystyle u_{5}[\ ]=\{``0",``0",``01",``21",``213"\}$ $\displaystyle u_{6}[\ ]=\{``2",``01",``21",``22"\}$ $\displaystyle u_{7}[\ ]=\{``2",``01",``012",``21"\}$ $\displaystyle u_{8}[\ ]=\{``0",``01",``013",``22",``31^{\prime\prime}\}$ $\displaystyle u_{9}[\ ]=\{``0",``0",``01",``213",``21"\}$

The characters in quotes indicate that URL the user is accessing.

According to the algorithm in this paper, firstly it is needs to determine a similar distance threshold for stopping the clustering cycle. Due to the relatively simple business process of the book shopping website, the distance threshold of this experiment is set to 0.6 in order to reduce the number of test cases.

The first distance matrix calculation is performed firstly. The results are as follows:

	$u0$	$u1$	$u2$	$u3$	$u4$	$u5$	$u6$	$u7$	$u8$	$u9$
$u0$	0.00	0.37	0.13	0.55	0.80	0.36	0.24	0.58	0.20	0.61
$u1$	0.37	0.00	0.36	0.44	0.73	0.59	0.78	0.19	0.37	0.59
$u2$	0.13	0.36	0.00	0.60	0.80	0.44	0.38	0.56	0.34	0.70
$u3$	0.55	0.44	0.60	0.00	0.71	0.70	0.78	0.70	0.55	0.70
$u4$	0.80	0.73	0.80	0.71	0.00	1.37	1.13	0.77	0.58	1.37
$u5$	0.36	0.59	0.44	0.70	1.37	0.00	0.55	0.51	0.61	0.10
$u6$	0.24	0.78	0.38	0.78	1.13	0.55	0.00	0.78	0.45	0.78
$u7$	0.58	0.19	0.56	0.70	0.77	0.51	0.78	0.00	0.58	0.51
$u8$	0.20	0.37	0.34	0.55	0.58	0.61	0.45	0.58	0.00	0.61
$u9$	0.61	0.59	0.70	0.70	1.37	0.10	0.78	0.51	0.61	0.00

The minimum distance in the matrix is d(u5, u9) $=$ 0.10, so user cases $u5$ and $u9$ are clustered into one test suite, then the new distances among new test suites are calculated and the first clustering result is as follows:

	$u0$	$u1$	$u2$	$u3$	$u4$	( $u5$ , $u9$ )	$u6$	$u7$	$u8$
$u0$	0.00	0.37	0.13	0.55	0.80	0.49	0.24	0.58	0.20
$u1$	0.37	0.00	0.36	0.44	0.73	0.59	0.78	0.19	0.37
$u2$	0.13	0.36	0.00	0.60	0.80	0.57	0.38	0.56	0.34
$u3$	0.55	0.44	0.60	0.00	0.71	0.70	0.78	0.70	0.55
$u4$	0.80	0.73	0.80	0.71	0.00	1.37	1.13	0.77	0.58
$(u5,u9)$	0.49	0.59	0.57	0.70	1.37	0.00	0.67	0.51	0.61
$u6$	0.24	0.78	0.38	0.78	1.13	0.67	0.00	0.78	0.45
$u7$	0.58	0.19	0.56	0.70	0.77	0.51	0.78	0.00	0.58
$u8$	0.20	0.37	0.34	0.55	0.58	0.61	0.45	0.58	0.00

In the same way, we find out the minimum distance $d(u0,u2)=$ 0.13, then cluster $u0$ and $u2$ into one test suite, and calculate the distances among new test suites.

Repeat the same calculation cycle, and the sixth clustering result is:

	( $u0$ , $u2$ , $u6$ , $u8$ )	( $u1$ , $u5$ , $u7$ , $u9$ )	$u3$	$u4$
( $u0$ , $u2$ , $u6$ , $u8$ )	0.00	0.69	0.63	0.83
( $u1$ , $u5$ , $u7$ , $u9$ )	0.69	0.00	0.64	1.06
$u3$	0.63	0.64	0.00	0.71
$u4$	0.83	1.06	0.71	0.00

The test suite set calculated from the cluster result is as below:

$S_{1}=\left\{{u0,u2,u6,u8}\right\},S_{2}=\left\{{u1,u5,u7,u9}\right\},S_{3}=% \left\{{u3}\right\},S_{4}=\left\{{u4}\right\}$

Then representative test cases are selected from each test suite:

For $S_{1}$ , we find out that $u2$ is a redundant test case, and the representative test cases are $u0$ , $u6$ , $u8$ ; $u7$ in $S_{2}$ is a superfluous test case, so the representative test cases are $u1$ , $u5$ , $u9$ ; $S_{3}$ and $S_{4}$ are not optimized, so the representative test cases are themselves. At last, three test suites ( $\textit{TS}_{1}=\left\{{u0,u6,u8}\right\},\textit{TS}_{2}=\left\{{u1,u5,u9}% \right\},\textit{TS}_{3}=\left\{{u3}\right\},\textit{TS}_{4}=\left\{{u4}\right\})$ are produced.

Under the premise of guaranteeing the order of the user’s session sequence, we compare the method of this paper with the traditional method. Methods without considering the order of the user’s session sequence are not in the context of comparison. According to the traditional user session-based test case generation method, all valid user sessions belong to a test case, so there are 120 test cases. And the test time takes 225 minutes. If use the proposed technique in this article, it only needs to generate 72 test cases, and the test time takes 72 minutes. Compared with the traditional method, proposed technique reduces test case number and test time by more than 40%, which can be shown in Table 1.

Table 1
Comparison between the proposed method in this paper and traditional method

Test case selection method	Test case number	Test time (minutes)
Proposed technique	72	155
Traditional method	120	225

From the experimental results, it shows that the proposed technique in this paper can effectively reduce the number of test cases and generate valid test suites.

5. Conclusion

For the web application, which has been released for a period of time, this paper proposed a novel method named user-session-based performance testing based on a modified hierarchy clustering algorithm. The sequence alignment algorithm and the bottom-up hierarchical clustering algorithm are employed to select and optimize the test cases produced from user sessions. And the key technique is to calculate the diverging distance between user sessions on the premise of ensuring their sequentiality. From the experimental results, a prototype for online book shopping website demonstrates that the proposed technique costs less time and redundant test cases than the one that uses the user sessions directly to test the web application. And the proposed technique is significantly better than the other method which treats the sessions as sets of visited pages over a period of time and does not consider the sequence of click-stream visitation.

However, the work of testing web applications based on mining user sessions is a complex systematic project. It is not easy to get an effective and practical tool because the testing is over-dependent on the session data.

In the future, the authors plan to deploy more testing services and collect a variety of runtime information to perform corresponding analysis. Furthermore, performance evaluation of web application after performance testing is also needed to be researched.

Footnotes

Acknowledgments

This work was supported in part by the National Nature Science Foundation of China (No. 61370103), Guangdong Province Application Major Fund (2015B010131013) and Zhongshan Produce and Research Fund (2016A1038).

References

Erlbaum

Karre

and Rothermel

, Improving Web Application Testing with User Session Data, in: International Conference on Software Engineering, IEEE Press, Portland, 2003, pp. 49–59.

Rudolf

and Pirker

, E-Business Testing: User Perceptions and Performance Issues, in: First Asia-Pacific Conference on Quality Software, IEEE Press, Hong Kong, 2000, pp. 231–239.

Subraya

B.M.

and Subrahmanya

S.V.

, Object Driven Performance Testing of Web Applications, in: First Asia-Pacific Conference on Quality Software, IEEE Press, Hong Kong, 2000, pp. 117–125.

Mercury Interactive Corporation, Load Testing to Predict Web Performance, Technical Report WP-1079-0604, Mercury Interactive Corporation, 2004.

Zhen

H.H.

and Yun

X.B.

, Applying user-sessions to Web Applications performance testing, Master Dissertation, Southeast University, 2010.

Quan

and Lu

, Session-Based User Behavior Meta-Model of Web Applications for User-Level QoS Load Testing, Supply Chain Management and Information Systems 4(4) (2010), 152–167.

Elbaum

Rothermel

Karre

and Fisher II

, Leveraging User-Session Data to Support Web Application Testing, IEEE Transactions on Software Engineering 31(3) (2005), 187–202.

Rothermel

and Harrold

, A Safe, Efficient Regression Test Selection Technique, ACM Transaction on Software Engineering and Methods 6(2) (1997), 173–210.

Chen

Y.F.

Rosenblum

D.S.

and Vo

K.P.

, TESTTUBE: A System for Selective Regression Testing, in: International Conference on Software Engineering, IEEE Press, Sorrento, 1994, pp. 211–222.

10.

Sampath

et al., Prioritizing User-session-based Test Cases for Web Applications Testing, in: International Conference on Software Testing, Verification, and Validation, IEEE Press, Lillehammer, 2008, pp. 142–152.

11.

Sampath

and Souter

, A Scalable Approach to User-session-based Testing of Web Applications Through Concept Analysis, in: Automated Software Engineering Conference, IEEE Press, Linz, 2004, pp. 132–141.

12.

Sampath

Pollock

and Souter

, Applying Concept Analysis to User-session-based Testing of Web Applications, in: IEEE Transactions on Software Engineering 33(10) (2007), 643–658.

13.

Sampath

Bryce

R.C.

Jain

and Manchester

, A tool for combination-based prioritization and reduction of user-session-based test suites, in: International Conference on Software Maintenance, IEEE Press, Williamsburg, 2011, pp. 574–577.

14.

J.N.

and Gao

J.H.

, Test Suite Reduction Approach for Web Applications based on User-session, Computer Engineering and Design 31(6) (2010), 1230–1235.

15.

Liu

et al., User-session-based Test Cases Optimization Method based on Agglutinate Hierarchy Clustering, in: International Conferences on Internet of Things, and Cyber, Physical and Social Computing, IEEE Press, Dalian, 2011, pp. 413–418.

16.

Charter

Schaeffer

and Szafron

, Sequence alignment using FastLSA, in: International Conference on Mathematics and Engineering Techniques in Medicine and Biological Sciences, CSREA Press, Las Vegas, 2000, pp. 239–245.

17.

Myers

and Miller

, Optimal alignments in linear space, Computer Applications in the Biosciences Cabios 4(1) (1988), 11–17.

18.

Hirschberg

D.S.

, A linear space algorithm for computing longest common subsequences, Communications of the ACM 18(18) (1975), 341–343.

19.

Needleman

S.B.

and Wunsch

C.D.

, A general method applicable to the search for similarities in the amino acid sequence of two proteins, Journal of Molecular Biology 48(3) (1970), 443–453.

20.

Wang

, Clustering Web Sessions by Sequence Alignment, in: International Workshop on Database and Expert Systems Applications, IEEE Press, Aix-en-Provence, 2002, pp. 394–398.

21.

Xie

Y.Y.

and Luo

, An approach to the acceptance test of AUTOSAR, Journal of Computational Methods in Sciences and Engineering 17(4) (2017), 837–847.

An automatic test case generation method based on user session and agglutinate hierarchical clustering algorithm

Abstract

Keywords

1. Introduction

2. Related work

2.1 Performance testing

2.2 User-session-based technique and web sessions clustering

3.2 Preprocess server logs files and calculate the similarity between web pages

4.1 E-commerce site

4.3 Preprocess the user session

Table 1 Comparison between the proposed method in this paper and traditional method

Footnotes

Acknowledgments

References

Table 1
Comparison between the proposed method in this paper and traditional method