Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

A Combinatorial Approach to Building Navigation Graphs for Dynamic Web Applications



Raghu N. Kacker, David R. Kuhn, James F. Lawrence, Wenhua Wang, Yu Lei, Sreedevi Sampath


Modeling the navigation structure of a dynamic web application is a challenging task because of the presence of dynamic pages. In particular, there are two problems to be dealt with: (1) the page explosion problem, i.e., the number of dynamic pages may be huge or even infinite; and (2) the request generation problem, i.e., many dynamic pages may not be reached unless appropriate user requests are supplied. As a user request typically consists of multiple parameter values, the request generation problem can be further divided into two problems: (1) How to select appropriate values for individual parameters? (2) How to effectively combine individual parameter values to generate requests? This paper presents a combinatorial approach to building a navigation graph. We report a prototype tool called Tansuo, and apply the tool to five open source web applications. Our empirical results indicate that Tansuo can efficiently generate web navigation graphs for these applications.
Proceedings Title
25th IEEE International Conference on Software Maintenance (ICSM)
Conference Dates
September 20-26, 2009
Conference Location
Conference Title
Proceedings of ICSM


combinatorial testing, navigation graphs, software testing, web application testing


Kacker, R. , Kuhn, D. , Lawrence, J. , , W. , Lei, Y. and Sampath, S. (2009), A Combinatorial Approach to Building Navigation Graphs for Dynamic Web Applications, 25th IEEE International Conference on Software Maintenance (ICSM), Edmonton, -1, [online], (Accessed April 21, 2024)
Created September 20, 2009, Updated February 19, 2017