asergrp

Projects‎ > ‎

eXpress: Guided Path Exploration for Regression Test

b e c


PROJECT SUMMARY

Regression test generation aims at generating a test suite that can detect behavioral differences between the original and the new ver sions of a program. Regression test generation can be automated by using Dynamic Symbolic Execution (DSE), a state-of-the-art test generation technique, to generate a test suite achieving high struc tural coverage. DSE explores paths in the program to achieve high structural coverage but exploration of all these paths can often be expensive. However, if our aim is to detect behavioral differences between two versions of a program, we do not need to explore all these paths in the program since not all these paths are relevant for detecting behavioral differences. In this paper, we propose an approach on guided path exploration that avoids exploring irrel evant paths in terms of detecting behavioral differences. Hence, behavioral differences are more likely to be detected earlier in path exploration. In addition, our approach leverages the existing test suite (if available) for the original version to efficiently execute the changed regions of the program and infect program state. Experi mental results on 72 versions (in total) of four programs show that our approach requires about 53% fewer runs (i.e., explored paths) on average to cause the execution of a changed region and 44% fewer to cause program-state differences after its execution than exploration without using our approach. In addition, our approach requires 71% fewer runs to cover all the changed regions by exploiting an existing test suite than exploration without using the test suite.

PEOPLE 

Faculty
     Tao Xie (Principal Investigator)

Students
     Kunal Taneja (PhD Student)

Collaborators
    Nikolai TillmannJonathan de Halleux, and Wolfram Schulte (Microsoft Research)


EVALUATIONS

We conducted experiments on four programs and their 72 versions (in total) collected from three different sources. In our experiments, we try to address the following research questions:
RQ1. How much fewer DSE runs does Pex require to execute the changed regions between the two versions of a program with the assistance of eXpress?
RQ2. How much fewer DSE runs does Pex require to infect the program states with the assistance of eXpress?
RQ3.
 How much more tests does Pex, with the assistance of eXpress, generate that execute changed regions between the two versions of a program?
RQ4. How much more tests does Pex, with the assistance of eXpress, generate that infect the program states?
RQ5. How much fewer DSE runs does Pex require to cover the changed regions when the program exploation is seeded with the existing test suite?

SUBJECTS USED

1. Replace: 32 versions
2. Siena : 17 versions
3. Silverlight String-To-PathGeometry Converter (STPG): 2 versions
4. Structorian : 21 versions

EXPERIMENTAL SETUP

For replace and siena, we conduct regression test generation between the original version and each version v2 synthesized from the available faults in the SIR. We use eXpress and the default search strategy in Pex to conduct regression test generation. In addition to the versions synthesized by seeding faults, we also conduct regression test generation between each successive versions of siena (versions 1.8 through 1.15) available in SIR, using eXpress and the default search strategy in Pex. For STPG and structorian, we conduct regression test generation between two successive pairs of versions that we collected.

To address RQ1, we compare the number of runs of DSE required by the default search strategy in Pex (in short as Pex) with the number of runs required by Pex enhanced with eXpress (in short as Pex+eXpress) to execute a changed region. To address RQ2, we compare the number of runs required by Pex with the number of runs required by Pex+eXpress to infect the program states. To address RQ3, we compare the number of tests that cover a changed region generated by Pex with the number of such tests generated by Pex+eXpress. If more tests are generated that cover a changed region, it is easier for developers (or testers) to debug the program under test (if the changes are faulty) and gives more confidence to developers that the changes they made do not introduce any unintended side effects. To address RQ4, we compare the number of tests that infect the program state after the execution of changed region generated by Pex with the number of such tests generated by Pex+eXpress. To address RQ5, we compare the number of DSE runs required by Pex (and Pex+eXpress) to cover all the blocks in all the changed regions with and without seeding the program exploration (with the existing test suite). Our experimental results for the four subjects are shown below.

Experimental Results for Replace and STPG

ExecutionInfection
Subject E-PexE-eXpressReduction (%)Ne-PexNe-eXpresIncrement (%)I-PexI-eXpressReduction (%)Ni-PexNi-eXpressIncrement (%)
replace177010715343161412.5213252.4
replace277010715343796517.7192742.1
replace32828050132164----- 
replace4282805013216413313301430114.3
replace524015037.51225108.324015834.2512140
replace63178273.81018803178373.8770
replace7603246.7111863.61285854.74775
replace8603246.7111863.613213204650
replace91313041213419.5243102581131181.8
replace101313041213419.5152111271332146.1
replace111313041213419.522413838.4152460
replace14---   ---- -
replace1544091211131.94409110515.4
replace16603246.7111863.61261232.448100
replace17202004545015150423475
replace18------------
replace20151503712266.7151503712266.7
replace2266012815118------
replace23660128151186601011032
replace246601281511815150273944.4
replace254259577.62725046513271.613200
replace264259577.62725046913371.613200
replace27----------- 
replace28603246.7111863.618212332.42330
replace29603246.7111863.618212332.426833.3
replace30603246.7111863.6603246.74525
replace31------------
replace32131305195-------
Total 194678959.411832249903203171646.435857962
STPG114112511.321251917812728.77928.6
STPG220012537.5172335.3200128363433.3
Total34125026.1384826.337825532.4101330

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Experimental Results for Siena

ExecutionInfection
Versions
(Revions)
E-PexE-eXpressReduction (%)Ne-PexNe-eXpresIncrement (%)I-PexI-eXpressReduction (%)Ni-PexNi-eXpress

Increment
(%)

v1-v25501943111.1302710121850
v2-v3NRNRNRNRNRNRNRNRNRNRNRNR
v3-v4(d)501276121316161.2501276115292153.9
v3-v4(e)3303698172.23302888214.3
v4-v58801131162.7NRNR----
v5-v6231726.12581224332427.3122391.67
v6-v7------------
v7-v821385.71345246.221385.71345246.2
v0-v9603541.7310233603541.7310233
v0-v10332718.2111863.6NANA----
v0-v11NRNRNRNRNRNRNRNRNRNRNRNR
v0-v12207655860207655560
v0-v138801131162.658801131162.65
v0-v141717056605.321199.5202525
v0-v1588030300880330
v0-v16NRNRNRNRNRNRNRNRNRNRNRNR
v0-v17302613.3102832730302613.3102832730
Total286166425491214121.128417239.4336908170.2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Experimental Results for Structorian


ExecutionInfection
ClassVersions
(Revions)
E-PexE-eXpressReduction (%)Ne-PexNe-eXpresIncrement (%)I-PexI-eXpressReduction (%)Ni-PexNi-eXpressIncrement (%)
StructLexer2-91027526.5243858.31027526.5243858.3
StructLexer9-1391027526.5243858.315210729.681137.5
StructLexer139-1501027526.5243858.31027526.5131838.5
StructLexer150-169534613.2202525534613.2202525
StructLexer169-174554812.732341121.4554812.723028122.2
StructLexer174-1751027526.5243858.3------
StructLexer175-184191521.1414817.121210131730.8
Total5353962648063624.548537223.330839026.6
BaseLexer45-17422099999903302432659.1
BaseLexer174-17522099999903302432659.1
StructParser2-5-1866-----2587----
StructParser5-6-2614-----2614----
StructParser9-13-1866-----1866----
StructParser37-3966012816528.9-851--5-
StructParser39-4022015016711.3------
StructParser50-626188105382.9---6188105382.9--
StructParser45-47220435323.3220435323.3
StructParser47-50220435323.3220435323.3
StructParser62-124220435323.3220435323.3
StructParser124-125220435323.3220435323.3
StructParser125-166-7452-----7452---
StructParser40-45-8214-----8276----

E-Pex: The total number of DSE runs required Pex for satisfying E (i.e., execution of a changed region)
E-eXpress: The total number of DSE runs required by Pex+eXpress for satisfying E.
Ne-Pex: The total number of tests that execute a changed region, generated by Pex
Ne-eXpres: The total number of tests that execute a changed region, generated by eXpress
I-Pex: The total number of DSE runs required by Pex for satisfying I (i.e., Program State Infection)
I-eXpress: The total number of DSE runs required by Pex+eXpress for satisfying I.
N-Pex: The total number of tests generated by Pex that infect the program state.
Ne-eXpress: The total number of tests generated by Pex+eXpress, that infect the program state.

 


PUBLICATIONS

  1. Kunal Taneja, Tao Xie, Nikolai Tillmann, Jonathan de Halleux, and Wolfram Schulte. Guided Path Exploration for Regression Test Generation.  In Companion Proceedings of the 31st International Conference on Software Engineering  (ICSE 2009), New Ideas and Emerging Results, Vancouver, Canada, pp. 311-314, May 2009.
    Download: [PDF]
  2. Kunal Taneja, Tao Xie, Nikolai Tillmann, Jonathan de Halleux, and Wolfram Schulte. eXpress: Guided Path Exploration for Regression Test Generation. Submitted for publication.

SPONSORS

d g ss