Record Details

Using Explicit State Space Enumeration For Specification Based Regression Testing

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title Using Explicit State Space Enumeration For Specification Based Regression Testing
 
Creator Chakrabarti, Sujit Kumar
 
Subject Computer Software - Testing And Measurement
Regression Analysis
Reactive Systems
Formal Software Specification
Application Programming Interface
Reactive Systems - Regression Testing
API Libraries - Regression Testing
State Space Model
State Variable
Test Sequence Computation
Graphmaker
Modest
State Space Explosion
Formal Software Specification
Computer Science
 
Description Regression testing of an evolving software system may involve significant challenges. While, there would be a requirement of maximising the probability of finding out if the latest changes to the system has broken some existing feature, it needs to be done as economically as possible. A particularly important class of software systems are API libraries. Such libraries would typically constitute a very important component of many software systems. High quality requirements make it imperative to continually optimise the internal implementation of such libraries without affecting the external interface. Therefore, it is preferred to guide the regression testing by some kind of formal specification of the library.
The testing problem comprises of three parts: computation of test data, execution of test, and analysis of test results. Current research mostly focuses on the first part. The objective of test data computation is to maximise the probability of uncovering bugs, and to do it with as few test cases as possible. The problem of test data computation for regression testing is to select a subset of the original test suite running which would suffice to test for bugs probably inserted in the modifications done after the last round of testing. A variant of this problem is that of regression testing of API libraries. The regression testing of an API is usually done by making function calls in such a way that the sequence of function calls thus made suffices a test specification. The test specification in turn embodies some concept of completeness.
In this thesis, we focus on the problem of test sequence computation for the regression testing of API libraries. At the heart of this method lies the creation of a state space model of the API library by reverse engineering it by executing the system, with guidance from an formal API specification. Once the state space graph is obtained, it is used to compute test sequences for satisfying some test specification. We analyse the theoretical complexity of the problem of test sequence computation and provide various heuristic algorithms for the same.
State space explosion is a classical problem encountered whenever there is an attempt of creating a finite state model of a program. Our method also faces this limitation. We explore a simple and intuitive method of ameliorating this problem – by simply reducing the size of the state vector. We develop the theoretical insights into this method. Also, we present experimental results indicating the practical effectiveness of this method.
Finally, we bring all this together into the design and implementation of a tool called Modest.
 
Contributor Srikant, Y N
 
Date 2010-07-08T08:36:34Z
2010-07-08T08:36:34Z
2010-07-08
2008-01
 
Type Thesis
 
Identifier http://hdl.handle.net/2005/738
 
Language en_US
 
Relation G22336