PD007333IN-SC
FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
COMPLETE SPECIFICATION
(See section 10, rule 13)
1. Title of the invention: MODEL BASED REGRESSION TEST SELECTION
2. Applicant(s)
NAME NATIONALITY ADDRESS
TATA CONSULTANCY
SERVICES LIMITED
Indian Nirmal Building, 9th Floor, Nariman
Point, Mumbai-400021, Maharashtra
India
3. Preamble to the description
COMPLETE SPECIFICATION
The following specification particularly describes the invention and the manner in which it
is to be performed.
1
2
TECHNICAL FIELD
[0001] The present subject matter relates, in general, to software testing and, in
particular, to regression testing of software.
BACKGROUND
[0002] Software systems are continuously modified during development and working for
reasons, such as correction of errors, addition of new features, porting to new environments, and
improvement of performance. Further, software systems are modified to adapt to the everchanging
state of business process they support. Changes made to the software systems are tested
to ensure that the software systems behave as defined and that the modifications have not had an
adverse impact on the performance of the software. Software testing is an important part in the
life cycle of any software system. Generally software testing requires resources which consume
time as well as incur huge expenditure. There are different types of software testing methods
presently available to software testing teams for testing the developed software systems. Such
methods are essentially classified based on either the objectives utilized or the methodology used
that include installation testing, compatibility testing, regression testing, acceptance testing,
usability testing, black-box testing, white-box testing, and grey-box testing.
[0003] Regression testing is the process of validating modified software to detect
whether new errors have been introduced into previously developed software system, and
provide confidence that modifications are correct. Regression testing consists of regression test
suite based on the required outcome, business process, quality standards. Complete regression
testing is hard to perform periodically due to quick-release cycles for modified software, size of
the regression test size, limited time, and utilization of resources. Regression testing may be used
in different methods of software testing, such as black-box testing, white-box testing, grey-box
testing.
[0004] Black-box testing is a testing method which examines functionality without any
knowledge of internal implementation or the code of the software system. Black-box testing is
based on the business requirement or the output of the software without knowing the changes in
code structure or the changes made in the code itself. Many a times, software testing teams
utilize black-box testing based regression testing to assure correct functionality of a modified
software where the code or changes to the code is unavailable.
3
SUMMARY
[0005] This summary is provided to introduce a concept related to regression tests
selection and the concept is further described below in the detailed description. This summary is
neither intended to identify essential features of the claimed subject matter nor is it intended for
use in determining or limiting the scope of the claimed subject matter.
[0006] In an embodiment, a method for regression test selection is described. The
method includes generating an original control flow graph (OCFG) and a modified control flow
graph (MCFG) associated with an original software system and a modified software system,
respectively, where the OCFG and MCFG are based on an original business process model
notation (OBPMN) of the original software system and a modified business process model
notation (MBPMN) of the modified software system, respectively. The method further includes,
identifying a set of primary impacted elements (PIE) and a set of other impacted elements (OIE),
based on a control flow analysis utilizing the OCFG and the MCFG, where the set of PIE signify
differences based on data modification between the OCFG and MCFG, and where the set of OIE
signify differences based on other modification between the OCFG and MCFG.
BRIEF DESCRIPTION OF THE FIGURES
[0007] The detailed description is described with reference to the accompanying figures.
In the figures, the left-most digit(s) of a reference number identifies the figure in which the
reference number first appears. The same numbers are used throughout the drawings to reference
like features and components.
[0008] Fig.1 illustrates a software development environment implementing a regression
test selection system for implementing the model based regression test selection method in
accordance with an embodiment of the present subject matter;
[0009] Fig.2 illustrates a method for regression test selection, in accordance with an
embodiment of the present subject matter.
[0010] In the present document, the word "exemplary" is used herein to mean "serving as
an example, instance, or illustration." Any embodiment or implementation of the present subject
matter described herein as "exemplary" is not necessarily to be construed as preferred or
advantageous over other embodiments.
4
[0011] It should be appreciated by those skilled in the art that any block diagrams herein
represent conceptual views of illustrative systems embodying the principles of the present
subject matter. Similarly, it will be appreciated that any flow charts, flow diagrams, state
transition diagrams, pseudo code, and the like represent various processes which may be
substantially represented in computer readable medium and so executed by a computer or
processor, whether or not such computer or processor is explicitly shown.
DETAILED DESCRIPTION
[0012] Systems and method for regression test selection (RTS) is described herein. In an
embodiment methods of a model based regression test selection for black box testing are
described. The methods utilize control flow analysis and data flow analysis to obtain regression
tests to be performed. The systems and method can be implemented in a variety of systems or
devices. The system or devices further can be implemented in various testing environments such
as, black box testing, white-box testing, and grey-box testing and categories of systems, such as
web based, desktop based, and the like. Further, the system or devices may further be
implemented in, for example, desktop computers, hand-held devices, laptops or other portable
computers, mobile phones, landline phones, and the like. Although the description herein is with
reference to black-box testing, it would understood that the systems and methods may be
implemented in other testing, such as white-box testing, albeit with a few variations, as will be
understood by a person skilled in the art.
[0013] Regression testing is a software testing method based on ‘objective of testing’ that
helps in identifying any new errors in a modified software system. Regression testing allows
identification of shortcomings in existing functional and non-functional areas of a software
system after changes, such as enhancements and patches or configuration changes have been
made. One of the objectives of regression testing is to ensure that a change, such as a bug-fix or a
hot-patch, has not introduced any new faults or errors. Regression testing also determines
whether a change in one part of the software system affects other parts of the software system.
[0014] Conventional methods of regression testing include rerunning previously run tests
and checking whether software system behavior has changed and whether previously fixed faults
have re-emerged. However, such methods of regression test are expensive due to continuously
increasing regression test suite based on the modification of the software system which take high
procession time, effort, and cost.
5
[0015] A regression test selection (RTS) technique is a method of selection, from an
existing test suite, tests that are important to validate modified software system, reducing the
required testing effort and cost. RTS techniques attempt to reduce costs by selecting and running
only a subset of the test cases in the software system's existing test suite. The RTS may be
applied in different software testing methods such as, black-box testing, white-box testing, and
grey-box testing. The black-box testing is the process of giving input to the system and checking
the output of the system without considering the process of output generation where as white-box
testing considers the process of generating the output and grey-box testing is a combination of
white-box and black-box testing, where the output as well as process carried out to generate the
output is tested.
[0016] The regression testing for business applications is generally black box testing due
to confidentiality or unavailability of the source code or byte code of the software system. Such
regression tests are performed on system executables in absence of the source code or byte code
of the software system. Conventional RTS techniques are white box testing techniques which
require either availability of source code or byte code of a software system. Huge software
systems, for example, a supply chain management system for a multinational company with
numerous products, the regression test suite containing millions of tests and expand continuously
due to modifications in original software system. Such software systems face scalability issue as
the conventional RTS techniques are unable to accommodate the increasing regression tests suite
due to need of source code or byte code of a software system.
[0017] Further, conventional regression tests selection technique from the regression test
suite is manual. Furthermore, such selection of tests for regression testing from a huge regression
test suite manually requires a high amount of effort and time, resulting in wastage of resources
and increased testing costs. Also, there is a risk of failure in detection of errors due to manual
inaccuracy, further resulting in faulty or inefficient testing.
[0018] According to an implementation of the present subject matter, systems and
method for regression test selection is described. In one implementation, a model based
regression test selection system, performs control and data flow analysis on business process
models to identify the changes done on the original software system. Further based on the
identified changes, regression tests are selected from a regression tests suite.
6
[0019] In an implementation, RTS includes selection of regression tests for performing
regression testing of a modified software system. RTS is performed on the regression tests suite
which contains all the tests used for testing the original software system. As described before, the
original software system undergoes addition, deletion, and modification of various processes,
during the development and implementation of the original software system. The selection of the
regression tests is based on the identified changes in software system, where a set of impacted
elements (IE) represent the elements of the original software system impacted by changes.
Generally, to identify the tests for regression testing, the selection of the regression tests is based
on a traceability matrix, where the traceability matrix maps the elements of the software system
to an exhaustive list of regression tests cases generated during the regression testing of original
software. Furthermore, the traceability matrix signifies the relation between the elements and the
tests cases.
[0020] According to an implementation of the present subject matter, identification of IE
is carried out as a two step process where in first step, control flow analysis technique is
performed to obtain a set of primary impacted elements (PIE), where the PIE represents a set of
impacted elements due to data modification in the original software obtained by control flow
analysis. Further, a set of other impacted elements (OIE) is also obtained, where the OIE
represent a set of impacted elements due to other modifications, such as, process element
modification and edge modification. In second step, a data flow analysis technique is performed
to obtain a set of secondary impacted elements (SIE), where the SIE represents a set of impacted
elements due to modification in the original software obtained by data flow analysis. Further an
intersection process of the obtained PIE and SIE provides with a set of data impacted elements
(DIE) that represent the identified changes due to data modification. Furthermore, a combination
of DIE and OIE provides a set of IE that represent the total identified change in the original
software system. The intersection process of the obtained PIE and SIE improves precision of the
DIE identification process.
[0021] In an implementation, in step first, control flow analysis technique performs
control flow graph (CFG) differentiation to obtain a set of PIE and a set of OIE. A CFG is a
directed graph which represents all paths that may be traversed during the execution of the
software system. The CFG differentiation represents the difference identified between the
original control flow graph (OCFG) and modified control flow (MCFG), where the OCFG is the
7
CFG for original software system and the MCFG is the CFG for modified software system. The
difference identified comprises a set of added, deleted and modified elements between the
original software system and the modified software system.
[0022] The CFG differentiated in step first, is based on business process model notation
of a software system. In one implementation, the OCFG is obtained based on an original
business process model notation where, the original business process model notation is generated
using the business process model and set of business rules of the original software system.
Further, the original business process model notation is annotated with tests conditions. The set
of business rules and test conditions in the original business process model notation are
expressed in object constraint language which is a declarative language for describing rules. In
one implementation, the MCFG is obtained based on a modified business process model
notation, where the modified business process model notation is generated using business
process model and set of business rules of the modified software system. Further, the modified
business process model notation is annotated with tests conditions. The set of business rules and
test conditions in the modified business process model notation are expressed in object constraint
language. Thus, the obtained OCFG and the MCFG are differentiated using control flow analysis
in step first, to obtain a set of PIE and a set of OIE.
[0023] In step second, data flow analysis is performed on the MCFG based on reaching
definition, where the reaching definitions are a type of data flow analysis which statically
determines, which modified definition may reach a predetermined point in the source code of the
original software system. The reaching definition is further used to identify a set of secondary
impacted elements (SIE).
[0024] In another implementation, an intersection of PIE and SIE is performed to obtain
a set of data impact elements (DIE). Further combination of DIE and OIE is performed to obtain
a set of IE. The IE and traceability matrix obtained, are further used for RTS from regression test
suite. The model base RTS method as described is not dependent on the source code or byte code
of the software system thus not facing any scalability issues. Further, the model base RTS
method may be implemented as an automated system thus removing manual selection.
Furthermore the model base RTS method is automated and is fast and free of manual errors thus
saving resources. The reduction in errors due to manual selection makes the method more precise
and safe.
8
[0025] These and other advantages of the present subject matter would be described in
greater detail in conjunction with the following figures. While aspects of described systems and
methods for the RTS can be implemented in any number of different computing systems,
environments, and/or configurations, the embodiments are described in the context of the
following exemplary system(s).
[0026] The described methodologies can be implemented in hardware, firmware,
software, or a combination thereof. For a hardware implementation, the processing units can be
implemented within one or more application specific integrated circuits (ASICs), digital signal
processors (DSPs), digital signal processing devices (DSPDs), programmable logic devices
(PLDs), field programmable gate arrays (FPGAs), processors, controllers, micro-controllers,
microprocessors, electronic devices, other electronic units designed to perform the functions
described herein, or a combination thereof. Herein, the term "system" encompasses logic
implemented by software, hardware, firmware, or a combination thereof.
[0027] For a firmware and/or software implementation, the methodologies can be
implemented with modules (e.g., procedures, functions, and so on) that perform the functions
described herein. Any machine readable medium tangibly embodying instructions can be used in
implementing the methodologies described herein. For example, software codes and programs
can be stored in a memory and executed by a processing unit. The memory can be implemented
within the processing unit or may be external to the processing unit. As used herein the term
"memory" refers to any type of long term, short term, volatile, nonvolatile, or other storage
devices and is not to be limited to any particular type of memory or number of memories, or type
of media upon which memory is stored.
[0028] In another firmware and/or software implementation, the functions may be stored
as one or more instructions or code on a non transitory computer-readable medium. Examples
include computer-readable media encoded with a data structure and computer-readable media
encoded with a computer program. The computer-readable media may take the form of an article
of manufacturer. The computer-readable media includes physical computer storage media. A
storage medium may be any available medium that can be accessed by a computer. By way of
example, and not limitation, such computer-readable media can comprise RAM, ROM,
EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic
9
storage devices, or any other medium that can be used to store desired program code in the form
of instructions or data structures and that can be accessed by a computer; disk and disc, as used
herein, includes compact disc (CD), laser disc, optical disc, digital versatile disc (DVD), floppy
disk, and Blue-ray disc where disks usually reproduce data magnetically, while discs reproduce
data optically with lasers. Combinations of the above should also be included within the scope of
computer-readable media.
[0029] In addition to storage on computer readable medium, instructions and/or data may
be provided as signals on transmission media included in a communication apparatus. For
example, a communication apparatus may include a transceiver having signals indicative of
instructions and data. The instructions and data are configured to cause one or more processors to
implement the functions outlined in the claims. That is, the communication apparatus includes
transmission media with signals indicative of information to perform disclosed functions. At a
first time, the transmission media included in the communication apparatus may include a first
portion of the information to perform the disclosed functions, while at a second time the
transmission media included in the communication apparatus may include a second portion of
the information to perform the disclosed functions.
[0030] It should be noted that the description merely illustrates the principles of the
present subject matter. It will thus be appreciated that those skilled in the art will be able to
devise various arrangements that, although not explicitly described herein, embody the principles
of the present subject matter and are included within its spirit and scope. Furthermore, all
examples recited herein are principally intended expressly to be only for pedagogical purposes to
aid the reader in understanding the principles of the invention and the concepts contributed by
the inventor(s) to furthering the art, and are to be construed as being without limitation to such
specifically recited examples and conditions. Moreover, all statements herein reciting principles,
aspects, and embodiments of the invention, as well as specific examples thereof, are intended to
encompass equivalents thereof.
[0031] The manner in which the systems and methods of regression test selection (RTS)
shall be implemented, has been explained in details with respect to the Figures 1 and 2. While
aspects of described systems and methods for RTS can be implemented in any number of
10
different computing systems, transmission environments, and/or configurations, the
embodiments are described in the context of the following exemplary system(s).
[0032] It will also be appreciated by those skilled in the art that the words during, while,
and when as used herein are not exact terms that mean an action takes place instantly upon an
initiating action but that there may be some small but reasonable delay, such as a propagation
delay, between the initial action and the reaction that is initiated by the initial action.
Additionally, the word “connected” and “coupled” is used throughout for clarity of the
description and can include either a direct connection or an indirect connection.
[0033] Fig.1 illustrates a software development environment implementing a RTS system
102 for implementing the model based regression test selection method. For the sake of
explanation, the RTS system 102 is referred to as the system 102, hereinafter. In one
implementation the system 102 is connected to one or more software development sites (SDS)
104-1, 104-2, …, 104-N, individually and commonly referred to as SDS(s) 104 hereinafter,
through a communication network 106.
[0034] The system 102 can be implemented as a variety of communication devices, such
as a laptop computer, a desktop computer, a notebook, a workstation, a mainframe computer, a
server and the like. The system 102 described herein, can also be implemented in any network
environment comprising a variety of network devices, including routers, bridges, servers,
computing devices, storage devices, etc.
[0035] The SDSs 104 may be implemented as, but are not limited to, desktop computers,
hand-held devices, laptops or other portable computers, tablet computers, mobile phones, PDAs,
Smartphone, and the like. The SDSs 104 may be located within the vicinity of the system 102 or
may be located at different geographic location as compared to that of the system 102. Further,
the SDSs 104 may themselves be located either within the vicinity of each other, or may be
located at different geographic locations.
[0036] The network 106 may be a wireless or a wired network, or a combination thereof.
The network 106 can be a collection of individual networks, interconnected with each other and
functioning as a single large network (e.g., the internet or an intranet). Examples of such
individual networks include, but are not limited to, Global System for Mobile Communication
(GSM) network, Universal Mobile Telecommunications System (UMTS) network, Personal
Communications Service (PCS) network, Time Division Multiple Access (TDMA) network,
11
Code Division Multiple Access (CDMA) network, Next Generation Network (NGN), Public
Switched Telephone Network (PSTN), and Integrated Services Digital Network (ISDN).
Depending on the technology, the network 106 includes various network entities, such as
gateways, routers; however, such details have been omitted for ease of understanding.
[0037] In one implementation, the system 102 includes processor(s) 108. The processor
108 may be implemented as one or more microprocessors, microcomputers, microcontrollers,
digital signal processors, central processing units, state machines, logic circuitries, and/or any
devices that manipulate signals based on operational instructions. Among other capabilities, the
processor(s) is configured to fetch and execute computer-readable instructions stored in a
memory.
[0038] The functions of the various elements shown in the figure, including any
functional blocks labeled as “processor(s)”, may be provided through the use of dedicated
hardware as well as hardware capable of executing software in association with appropriate
software. When provided by a processor, the functions may be provided by a single dedicated
processor, by a single shared processor, or by a plurality of individual processors, some of which
may be shared. Moreover, explicit use of the term “processor” should not be construed to refer
exclusively to hardware capable of executing software, and may implicitly include, without
limitation, digital signal processor (DSP) hardware, network processor, application specific
integrated circuit (ASIC), field programmable gate array (FPGA), read only memory (ROM) for
storing software, random access memory (RAM), non-volatile storage. Other hardware,
conventional and/or custom, may also be included.
[0039] Also, the system 102 includes interface(s) 110. The interfaces 110 may include a
variety of software and hardware interfaces that allow the system 102 to interact with the entities
of the network 106, or with each other. The interfaces 110 may facilitate multiple
communications within a wide variety of networks and protocol types, including wire networks,
for example, LAN, cable, etc., and wireless networks, for example, WLAN, cellular, satellitebased
network, etc.
[0040] The system 102 may also include a memory 112. The memory 112 may be
coupled to the processor 108. The memory 112 can include any computer-readable medium
known in the art including, for example, volatile memory, such as static random access memory
(SRAM) and dynamic random access memory (DRAM), and/or non-volatile memory, such as
12
read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical
disks, and magnetic tapes.
[0041] Further, the system 102 may include module(s) 114 and data 116. The modules
114 may be coupled to the processors 108 and amongst other things, include routines, programs,
objects, components, data structures, etc., which perform particular tasks or implement particular
abstract data types. The modules 114 may also be implemented as, signal processor(s), state
machine(s), logic circuitries, and/or any other device or component that manipulate signals based
on operational instructions.
[0042] Further, the modules 114 can be implemented in hardware, instructions executed
by a processing unit, or by a combination thereof. The processing unit can comprise a computer,
a processor, a state machine, a logic array or any other suitable devices capable of processing
instructions. The processing unit can be a general-purpose processor which executes instructions
to cause the general-purpose processor to perform the required tasks or, the processing unit can
be dedicated to perform the required functions.
[0043] In another aspect of the present subject matter, the modules 114 may be machinereadable
instructions (software) which, when executed by a processor/processing unit, perform
any of the described functionalities. The machine-readable instructions may be stored on an
electronic memory device, hard disk, optical disk or other machine-readable storage medium or
non-transitory medium. In one implementation, the machine-readable instructions can be also be
downloaded to the storage medium via a network connection.
[0044] In an implementation, the module(s) 114 includes CFG generation module 118,
control flow analysis module 120, DFA module 122, RTS module 124 and other module(s) 126.
The other module(s) 126 may include programs or coded instructions that supplement
applications or functions performed by the system 102. In said implementation, the data 116
includes CFG data 128, flow analysis data 130, RTS data 132, and other data 134. The other data
134, amongst other things, may serve as a repository for storing data that is processed, received,
or generated as a result of the execution of one or more modules in the module(s) 114. Although
the data 116 is shown internal to the system 102, it may be understood that the data 116 can
reside in an external repository (not shown in the figure), which may be coupled to the system
13
102. The system 102 may communicate with the external repository through the interface(s) 114
to obtain information from the data 116.
[0045] As described before, in one implementation of the present subject matter, the
system 102 is configured to carry out regression test selection (RTS) for performing regression
testing of a modified software system. In said implementation, the system 102 connects to the
software development sites (SDS) 104 by the network 106. At the SDS 104 an original software
system may undergoes addition, deletion, and modification of various processes, during the
development and implementation of the original software system. The system 102 performs
selection of the regression tests based on the identified impacted elements, as described before
for regression tests of modified software in the SDS 104.
[0046] In an implementation of the present subject matter, the CFG generation module
118 of system 102 is configured to generate a control flow graph based on the software system.
CFG generation module 118 obtains business process model and set of business rules and tests
condition in object constraint language as input and generates a business process model notation
(BPMN) which is annotated with tests conditions. In one implementation, the CFG generation
module 118 is configured to obtain original CFG (OCFG) based on an original BPMN
(OBPMN) of the original software. The CFG generation module 118 is further configured to
generate a traceability matrix by mapping the business process elements to the tests cases. The
CFG generation module 118 based on the process elements, generates tests cases and maps the
tests cases to the process elements. The tractability matrix so obtained provided a relation
between the elements and the tests cases. Further the CFG generation module 118 forms a union
of all the generated tests to form a regression tests suite.
[0047] The BPMN can be expressed as a function of different elements and nodes of the
software system, as depicted below:
P=< PE, F, s, E, C > ...Equation 1
[0048] In the above described relation of equation 1, PE denotes set of process elements,
F denotes set of flow elements, s denotes start node, E denotes of end nodes, and C denotes set of
tests conditions. Based on tests condition, BPMN, coverage criteria like exhaustive, minimal and
combinatorial, test scenarios are selected for tests case generation. For each scenario, a test case
is generated and tagged along with the scenario in the process. The union of all of these test
14
cases forms a regression test suite. The data generated by the CFG generation module 118 is
stored in CFG data 128.
[0049] In an example, CFG generation module 118 obtains a process model for flight
reservation software system and set of rules such as registered user can login, can search for
flight, can book a flight, can logout, and also, a guest user can view information,. Based on the
received information, the CFG generation module 118 generates an original business process
model notation (OBPMN). The CFG generation module 118 further converts the generated
OBPMN to an original control flow graph (OCFG). Based on the process model information,
three tests scenarios may be considered which are:
S1=start (S)-registered user (RU)-login (LI)-search flight (SF)-book flight (BF)-logout (LO)-end
(E);
S2=start (S)-registered user (RU)-login (LI)-search flight (SF) - logout (LO)-end (E); and
S3= start (S)-guest user (GU)-view information (VI)-end (E).
[0050] For the above mentioned test scenarios, three test cases t1, t2, and t3 are
generated, for testing the corresponding three tests scenarios S1, S2, and S3 by the CFG generation
module 118. The set of all tests cases, in the above example t1, t2, and t3 form the regression
tests suite. Furthermore the CFG generation module 118 generates a traceability matrix by
mapping the process entities such as S, LI, LO to the test cases t1, t2, and t3. For instance, S may
map to test cases t1, t2, and t3, while RU may map to t1, and t2; and VI may only map to t3.
[0051] As described before, the original software system developed by any of the SDSs
104 may undergo addition, deletion or modification to obtain a modified software system as per
the business requirements. In an implementation, the CFG generation module 118 of system 102
may be configured to develop a modified business processes module notation (MBPMN) for the
modified software system. The CFG generation module 118 of system 102 may be further
configured to develop a modified control flow graph (MCFG), based on the MBPMN. The
MCFG and the MBPMN developed by the CFG generation module 118 is stored in the CFG data
128.
[0052] In an example, the original flight reservation software system may undergo
modification to form a modified flight reservation system. The modification may be in form of
addition of new process 'unregistered user ', modification of a pervious process 'guest user' and
addition of a new precondition 'start-time' attached to the login element (LI) where the login time
15
is calculated. Based on the modifications and a set of test rules obtained in object constraint
language, the CFG generation module 118 generates the MBPMN and further a modified control
flow graph. Based on the MBPMN and the tests rules, new and modified test scenarios S3 and
S4 may be considered.
S3= start (S)-guest user (GU)-enter name (N)-view information (VI)-end (E);
S4= start (S)-unregistered user (UU)-Register (R)-end (E).
[0053] In an implementation, the CFA module 120 of the system 102 is configured to
identify primary impacted elements (PIE) and other impacted elements (OIE) based on control
flow analysis. The CFA module 120 obtains the OCFG and the MCFG stored in the CFG data
128 as input and performs CFG differencing using control flow analysis to obtain the PIE and the
OIE. In said implementation, the result of the CFG differencing is stored in flow analysis data
130. As would be known to a person skilled in the art, the modifications performed on the
original software system to obtain modified software may include task modification, gateway
edge deletion, gateway edge addition, param modification, and condition modification. Based on
the nature of the modification, in one implementation of the present subject matter, the CFA
module 120 is configured to prompt generation of new tests cases and deletion of existing tests
cases based on gateway edge addition and deletion. The CFA module 120 further marks the tests
case based on the other changes such as task modification in the existing regression test suite.
The control flow analysis difference, which enables the identification of the PIE and OIE based
on the OCFG and MCFG is represented as:
δ = Diff (G, G') ≡ (A, D, M) ... Equation 2
[0054] In the above depicted equation 2, δ represents the PIE, G represents the OCFG of
the original software system, and G' represents the MCFG of the modified software system.
Further, A represents set of additions to the MCFG, D represents set of deletions to the MCFG,
and M represents set of modifications to the MCFG.
[0055] In the above described example, the MCFG of the modified flight reservation
software system and the OCFG of original flight reservation software system are compared by
the CFA module 120. Further, the CFA module 120 performs the differentiation based on control
flow analysis. The control flow analysis by the CFA module 120 of the OCFG and MFCG shows
that the process 'registered user' is not impacted by the addition of process 'unregistered user' or
the modification of process 'guest user' but, the new rule of 'start-time' impacts the login element.
16
Based on equation 2, the CFG differentiation by CFA module 120 results in to PIE identification
δ = (UU, R, N, VI, LI, SF, LO, E), where (UU, R, N) is obtained by 'unregistered user' process
addition, (VI) is obtained by 'guest user' process modification and (LI, SF, LO, E) is obtained by
the new rule addition of 'start time'. The CFA module 120 further prompts generation of a new
test t4 for scenario S4 based on the modifications and changes done in the original software
system.
[0056] In an implementation, the DFA module 122 of the system 102 is configured to
obtain the MCFG from the CFG data 128 as input and perform data flow analysis to obtain a set
of secondary impacted elements (SIE) which is stored in the flow analysis data 130. Data flow
analysis is performed by the DFA module 122 on the MCFG based on reaching definitions. The
reaching definitions are further used by the DFA module 122 to compute the set of SIEs. The
DFA module 122 is further configured to mark the tests cases in the existing regression test suite
based on parameter changes and condition modifications done on the original software system.
The generated SIEs are stored in the flow analysis data 130. The set of SIE can be represented
as:
δ' = {set of process entities impacted after data flow analysis} ..Equation 3
Where δ' represents a set of SIE.
[0057] In an example, the DFA module 122 performs data flow analysis on the MCFG of
the modified flight reservation software system. Based on the data flow analysis, the DFA
module 122 further computes the reaching definitions. In the said example, the definition of new
condition 'start-time' on login element does not affect the original output. In other words the
definition of 'start-time' is not reaching the login element to cause any impact. Further, DFA
module 122 obtains set of SIE from the data flow analysis, which is represented by δ' = (UU, R,
N, VI). The DFA module 122 further marks the test t4 in the regression test suite i.e. to obtain
(t1, t2, t3, t4).
[0058] In an implementation, the RTS module 124 of the system 102 is configured to
compute a set of data impacted elements (DIE) by obtaining PIE and SIE as input from the flow
analysis data 130. The RTS module 124 performs an intersection operation on the obtained PIE
and SIE to compute DIE. The RTS module 124 further configured to combine the OIE obtained
by the CFA module 120 and the DIE to compute impacted elements (IE). The computed IE is
17
further stored in the RTS data 132. The RTS module 124 uses equation 4 to compute DIE and
equation 5 to compute IE.
DIE = (PIE ∩ SIE) ....Equation 4
IE = (DIE + OIE) ...Equation 5
[0059] In an implementation, the RTS module 124 is configured to perform selection of
regression tests based on the set of IE obtained from the RTS data 132 and, the traceability
matrix from the CFG data 128. The RTS module 124 is further configured to compute test cases
for the regression testing of the modified software system, based on the IE utilizing the mapping
among the elements and the test cases, provided in the traceability matrix. Further a union of all
the computed tests cases is performed to obtain a sub set of regression tests of the regression
tests suite that have to be run to regression tests the modified software system.
[0060] For example, the RTS module 124 may obtain SIE and PIE computed for the
modified flight reservation software system. The RTS module 124 may further perform an
intersection operation, as represented in equation 4 to obtain a set of IE. The obtained IE for the
modified flight reservation software system as per the described scenario based on equation 4
and equation 5 may be (UU, R, N, VI). Further the RTS module 124 based on the obtained set of
IE = (UU, R, N, VI) and the traceability matrix, may perform a selection of regression tests. The
RTS module 124 performs the said selection of regression test on the previously obtained
regression tests suite (t1, t2, t3, t4). The subset of tests obtained may be the tests t3, and t4.
[0061] Fig. 2 illustrates an exemplary method 200 for model based RTS for black box
testing, according to an embodiment of the present subject matter, whereas the method 200 may
be described in the general context of computer executable instructions. Generally, computer
executable instructions can include routines, programs, objects, components, data structures,
procedures, modules, functions, which perform particular functions or implement particular
abstract data types. The method 200 may also be practiced in a distributed computing
environment where functions are performed by remote processing devices that are linked through
a communication network. In a distributed computing environment, computer executable
instructions may be located in both local and remote computer storage media, including memory
storage devices.
[0062] The order in which the method 200 is described is not intended to be construed as
a limitation, and any number of the described method blocks can be combined in any order to
18
implement the method 200, or alternative method. Additionally, individual blocks may be
deleted from the method 200 without departing from the spirit and scope of the subject matter
described herein. Furthermore, the method 200 can be implemented in any suitable hardware,
software, firmware, or combination thereof.
[0063] Referring to method 200, at bock 202, an Original Control Flow Graph (OCGF)
and a traceability matrix for an original Business Process Model Notation associated to an
original software are generated. In one implementation, the business process and the rules
associated with the original software system are acquired and original business process model
notation annotated with tests conditions in object constraint language (OCL) is generated. The
traceability matrix is also generated during the original business process model notation
generation, which maps the process model elements of the software system to the tests cases
generated. Furthermore, a regression tests suite is obtained which comprise of all the regression
tests generated for regression testing of the original software system.
[0064] At block 204, a Modified Control Flow Graph (MCFG) based on a modified
business process model notation (MBPN) of a modified software is developed. The original
software system may be modified by way of addition, deletion or modification of business
process or pre-condition with respect to the original working of business process. The obtained
MBPMN is further annotated with tests conditions in object constraint language (OCL) based on
the modified software system and is further converted to the MCFG.
[0065] At block 206, primary impacted elements (PIE) and other impacted elements
(OIE) are identified based on control flow analysis, where the control flow analysis comprises of
comparison between the OCFG and the MCFG. In on implementation, the obtained OCFG and
the MCFG are compared. The comparison process involves control flow analysis which
identifies the set of PIE for data modifications and OIE for other modifications. In said
implementation, the control flow analysis further generates new tests for the added business
process and the tests cases generated.
[0066] At block 208, reaching definitions based on Data Flow Analysis of the MCFG are
obtained, where the reaching definitions are indicative of Secondary Impacted Elements (SIE). In
one implementation, the data flow analysis technique is utilized to process the MCFG. Based on
the processing, the set of SIE are obtained. In said implementation, the data flow analysis further
19
marks the tests cases generated to the previously existing regression tests suite for regression
testing of the modified software system.
[0067] At block 210, a subset of Impacted Elements (IE) is computed based on PIE and
SIE. In one implementation, an intersection process is performed on the previously obtained PIE
and SIE to compute a set of DIE. Further DIE and OIE are combined to compute IE
[0068] At block 212, Regression Test Selection (RTS) based on the traceability Matrix
and the set of IE is performed. In one implementation, the test cases to be performed on the
modified system software are selected from the previously obtained regression tests suite.
Therefore, the selected test cases essentially correspond to the IE identified as the modifications
done to the original software system, based on the control flow analysis and data flow analysis of
the original and modified software system. As described, the test cases are selected based on the
traceability matrix which maps all the process elements to identified tests cases. A set of test
cases is identified based on the IE is a subset of the regression tests suite and, is run for
regression testing of the modified software system.
[0069] Although implementations for RTS have been described in language specific to
structural features and/or method, it is to be understood that the appended claims are not
necessarily limited to the specific features or method described. Rather, the specific features and
method are disclosed as exemplary implementations for RTS.
20
I/we claim:
1. A computer implemented method for regression test selection, the method comprising:
generating an original control flow graph (OCFG) and a modified control flow
graph (MCFG) associated with an original software system and a modified software
system, respectively, wherein the OCFG and the MCFG are based on an original business
process model notation (OBPMN) of the original software system and a modified
business process model notation (MBPMN) of the modified software system,
respectively, and wherein a business process model notation is indicative of business
rules and test conditions associated with a business process; and
identifying a set of primary impacted elements (PIE) and a set of other impacted
elements (OIE), for selecting regression tests, based on a control flow analysis utilizing
the OCFG and the MCFG, wherein the set of PIE signify differences between the OCFG
and the MCFG based on data modification, and wherein the set of OIE signify
differences between the OCFG and MCFG based on other modification.
2. The method as claimed in claim 1, the method further comprising:
obtaining a set of secondary impacted elements (SIE) based on a data flow
analysis of the MCFG, wherein the data flow analysis develops reaching definitions to
obtain the set of SIE;
generating a set of data impacted elements (DIE) based on the identified PIE and
the obtained SIE, wherein the set of DIE are indicative of data modifications done to the
original software system; and
computing a set of impacted elements (IE) based on the generated DIE and the
indentfied OIE, wherein the IE are indicative of modifications done to the original
software system.
3. The method as claimed in claim 1, wherein the method further comprises selecting a set
of regression tests based on the set of PIE, OIE, and a traceability matrix, and wherein the
traceability matrix comprises a mapping among elements of the original software system and the
modified software system; and test cases for regression testing of the original software system
and the modified software system.
21
4. The method as claimed in claim 2, wherein the method further comprises selecting a set
of regression test based on the set of IE and a traceability matrix, and wherein the traceability
matrix comprises a mapping among elements of the original software system and the modified
software system; and test cases for regression testing of the original software system and the
modified software system
5. The method as claimed in claim 1, wherein the OBPMN and the MBPN are based on a
business process and, a test case of the original software system and the modified software
system, wherein the business process is indicative of a function provided by the original software
system and the modified software system.
6. The method as claimed in claim 2, wherein the generating the set of DIE is based on
intersection process utilizing the PIE and the SIE, wherein elements common among the PIE and
the SIE are chosen to identify the DIE in the intersection process.
7. The method as claimed in claim 2, wherein the computing the set of IE is based on
combination of the OIE and the DIE.
8. The method as claimed in claim 1, wherein the other modification comprises at least one
of process element modification and edge modification.
9. A RTS system (102) for regression test selection comprising:
a processor (112);
a CFG generation module (118), coupled to the processor (112), configured to
generate an original control flow graph (OCFG) and a modified control flow graph
(MCFG) associated with an original software system and a modified software system,
respectively, wherein the OCFG and the MCFG are based on an original business process
model notation (OBPMN) of the original software system and a modified business
process model notation of (MBPMN) of the modified software system, respectively;
a CFA module (120), coupled to the processor (112), configured to identify a set
of primary impacted elements (PIE) and a set of other impacted elements (OIE), based on
a control flow analysis utilizing the OCFG and the MCFG, wherein the set of PIE signify
differences between the OCFG and the MCFG based on data modification, and wherein
the set of OIE signify differences between the OCFG and the MCFG based on other
modification;
22
a DFA module (122), coupled to the processor (112), configured to obtain a set of
secondary impacted elements (SIE) based on a data flow analysis utilizing the MCFG,
wherein the data flow analysis develops reaching definitions to obtain the set of SIE; and
a RTS module (124), coupled to the processor (112), configured to:
generate a set of data impacted elements (DIE) based on the identified PIE
and the obtained SIE, wherein the set of DIE are indicative of data modifications
done to the original software system; and
compute a set of impacted elements (IE), for selecting regression tests,
based on the generated DIE and the identified OIE, wherein the IE are indicative
of modifications done to the original software system.
10. The RTS system (102) as claimed in claim 9, wherein the RTS module (124) is further
configured to select a set of regression tests based on the set of IE and a traceability matrix, and
wherein the traceability matrix comprises a mapping among elements of the original software
system and the modified software system; and test cases for regression testing of the original
software system and the modified software system.
11. The RTS system (102) as claimed in claim 10, wherein the selected set of regression tests
are utilized in black-box testing of the original software system and the modified software
system.
12. The RTS system (102) as claimed in claim 9, wherein the RTS module (124) is
configured to generate the set of DIE based on intersection process utilizing the PIE and the SIE,
wherein elements common among the PIE and the SIE are chosen to identify the IE in the
intersection process.
13. The RTS system (102) as claimed in claim 9, wherein the RTS module (124) is further
configured to compute the set of IE is based on combination of the OIE and the DIE.
14. The RTS system (102) as claimed in claim 9, wherein the CFG generation module (118)
is further configured to obtained the OBPMN and MBPN based on a business process and, a test
case of the original software system and the modified software system, and wherein the business
process is indicative of a function provided by the original software system and the modified
software system.
15. A non-transitory computer-readable medium having embodied thereon a computer
readable program code for executing a method, the method comprising::
23
generating an original control flow graph (OCFG) and a modified control flow
graph (MCFG) associated with an original software system and a modified software
system, respectively, wherein the OCFG and MCFG are based on an original business
process model notation (OBPMN) and a modified business model notation of (MBPMN)
the original software system and the modified software system respectively;
identifying a set of primary impacted elements (PIE) and a set of other impacted
elements (OIE), for selecting regression tests, based on a control flow analysis utilizing
the OCFG and the MCFG, wherein the set of PIE signify differences between the OCFG
and the MCFG based on data modification, and wherein the set of OIE signify
differences between the OCFG and the MCFG based on other modification;
obtaining a set of secondary impacted elements (SIE) based on a data flow
analysis of the MCFG, wherein the data flow analysis develops reaching definitions to
obtain the set of SIE;
generating a set of data impacted elements (DIE) based on the identified PIE and
the obtained SIE, wherein the DIE are indicative of data modifications done to the
original software system; and
computing a set of impacted elements (IE) based on the generated DIE and the
identified OIE, wherein the IE are indicative of modifications done to the original
software system.
16. The non-transitory computer-readable medium as claimed in claim 15, the method further
comprising selecting a set of regression test based on the set of IE and a traceability matrix, and
wherein the traceability matrix comprises a mapping among elements of the original software
system and the modified software system; and test cases for regression testing of the original
software system and the modified software system.