asergrp

23days until
FSE Deadline

26days until
ASE Deadline

43days until
SPLASH Deadline

Projects‎ > ‎

eXpress: Guided Path Exploration for Regression Test

       

PROJECT SUMMARY

Regression test generation aims at generating a test suite that can detect behavioral differences between the original and the new versions of a program. Regression test generation can be automated by using Dynamic Symbolic Execution (DSE), a state-of-the-art test generation technique. DSE explores all feasible paths in the program 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 irrelevant 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 states. Experimental results on 67 versions (in total) of four programs show that our approach requires about 36% fewer amount of time (on average) to detect behavioral differences than exploration without using our approach. In addition, our approach detects 6 behavioral difference that could not be detected by exploration without using our approach (within a time bound). Furthermore, our approach requires 67% fewer amount of time to find behavioral differences 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 67 versions (in total) collected from three different sources. In our experiments, we try to address the following research questions:

RQ1. How many 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 many fewer DSE runs does Pex require to infect the program states with the assistance of eXpress?

RQ3. How many fewer DSE runs and how much fewer amount of time does Pex require to find behavioral differences with the assistance of  eXpress?|

RQ4. How many fewer DSE runs and how much fewer amount of time does Pex require to find behavior differences when the program exploration 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.

To find behavioral differences between two versions, we execute the tests generated for a new version on the original version. Behavioral differences are detected by a test if an assertion in the test fails.

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.

 

The results of our seeding technique are as follows:

CVPexPex+SeedingeXpresseXpress+seeding
SP2-510000/1hr*10000/1hr*2381/35min181/17min
SP37-393699/26m60/1m851/22m47/11m
SP39-4010000/1hr*304/2m10000/1hr*251/12m
SP45-4710000/1hr*10000/1hr*10000/1hr*10000/1hr*
SP47-5010000/1hr*81/1m10000/1hr*64/10m
SP62-12410000/1hr*59/1m7228/58m41/10m
SL169-174478/1m324/1m34/1m18/1m
SL150-169299/1m37/1m52/1m29/1m
SL9-1392988/2m69/1m1002/1m52/1m
Total64476/6.5hr20934/2hr8m41568/5hr9m10683/2hr3m


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