display pdf in mvc : Batch pdf to jpg converter SDK software service wpf windows web page dnn fulltext0-part1637

Pex–WhiteBoxTestGenerationfor.NET
NikolaiTillmannandJonathandeHalleux
MicrosoftResearch
OneMicrosoft Way,RedmondWA98052,USA
{nikolait,jhalleux}@microsoft.com
Abstract. Pexautomaticallyproducesasmalltestsuitewithhighcode
coverage for a.NET program.Tothis end,Pexperforms a systematic
program analysis (using dynamic symbolic execution,similar r topath-
bounded model-checking) to o determine e test t inputs for Parameterized
Unit Tests. Pex learns s the e programbehavior by monitoringexecution
traces. Pex uses a constraint solver toproducenew test inputs which
exercisedifferentprogrambehavior.Theresultisanautomaticallygen-
erated smalltest suitewhich oftenachieveshighcodecoverage. In one
case study,we applied Pextoa core component of the .NET runtime
whichhadalreadybeenextensivelytestedoverseveralyears.Pexfound
errors,includingaseriousissue.
1 Overview
Pex[24]isanautomaticwhite-boxtestgenerationtoolfor.NET.Startingfrom
amethodthat takesparameters,Pex performs path-boundedmodel-checking
byrepeatedly executingtheprogramandsolvingconstraintsystemstoobtain
inputsthatwillsteertheprogramalongdifferentexecutionpaths,followingthe
idea of f dynamic c symbolic execution n [12,6]. Pex uses s the theorem m prover r and
constraintsolverZ3[3]toreasonaboutthefeasibilityofexecutionpaths,and
toobtaingroundmodelsforconstraintsystems.
Whiletheconceptofdynamicsymbolicexecutionisnotnew,Pexextendsthe
previousworkinseveralways:
– Pexcanbuildfaithfulsymbolicrepresentationsofconstraints s thatcharac-
terizeexecutionpathsofsafe.NETprograms.Inotherwords,Pexcontains
acompletesymbolicinterpreterforsafeprogramsthatruninthe.NETvir-
tualmachine.(AndtheconstraintsolverZ3comeswithdecisionprocedures
formostsuchconstraints.)
– Pex can reasonabout t a a commonly usedset t of unsafe e features s of f .NET.
(Unsafe meansunverifiablememoryaccessesinvolvingpointerarithmetic.)
– Pexemploysasetofsearchstrategieswiththegoaltoachievehighstatement
coverageinashortamountoftime.
WehaveintegratedPexintoVisualStudioasanadd-in.Pexcangeneratetest-
cases that can n be integrated with various s unit testing g frameworks, , including
NUnit [20] and d MSTest [22]. Pex x is anextensible dynamic program analysis
B. Beckertand R.H¨ahnle(Eds.):TAP2008,LNCS 4966, pp. 134–153, 2008.
c Springer-VerlagBerlinHeidelberg2008
Batch pdf to jpg converter - Convert PDF to JPEG images in C#.net, ASP.NET MVC, WinForms, WPF project
How to convert PDF to JPEG using C#.NET PDF to JPEG conversion / converter library control SDK
convert pdf image to jpg online; convert online pdf to jpg
Batch pdf to jpg converter - VB.NET PDF Convert to Jpeg SDK: Convert PDF to JPEG images in vb.net, ASP.NET MVC, WinForms, WPF project
Online Tutorial for PDF to JPEG (JPG) Conversion in VB.NET Image Application
reader pdf to jpeg; convert pdf file to jpg format
Pex–WhiteBoxTestGenerationfor.NET
135
platform;one recentplug-inis DySy [7],aninvariantinferencetool basedon
dynamicsymbolicexecution.Weareworkingtowardsmakingthesymbolicex-
ecutionanalysiscompositional[1].
WehaveconductedacasestudyinwhichweappliedPextoacorecomponent
ofthe .NET architecture whichhadalreadybeenextensivelytestedover five
yearsbyapproximately40testers.Thecomponentisthebasisforotherlibraries,
whichareusedbythousandsofdevelopersandmillionsofendusers.Pexfound
errors,including a serious s issue. . Because of f proprietary concerns, , we e cannot
identifythe.NETcomponentonwhichthiscasestudywasbased.Wewillrefer
toitasthe“core.NETcomponent”inthefollowing.
Therestof the paperis structuredas follows: Section2 contains anintro-
ductiontoPex.Section3discusses the implementationofPexinmoredetail.
Section4showsaparticularapplicationofPextounsafe.NETcode.Section5
presentstheresultsofapplyingPextoacore.NETcomponent.Section6com-
paresPexwithotherrelatedtechnologies,andSection7concludes.
2 AnIntroductiontoPex
2.1 ParameterizedUnitTesting
Atitscore,Pexisatestinputgenerator.Atest inputgeneratorisonlyuseful
inpractice
– ifwehaveaprogramtogeneratetestinputsfor,and
– ifwehaveatestoraclethatdecideswhetheraprogramexecutionwassuc-
cessfulforsomegiventestinputs.
ForPex,wehaveadoptedthenotionofparameterizedunittests [28,29]which
meetbothrequirements.Aparameterizedunittestissimplyamethodthattakes
parameters,performsasequenceofmethodcallsthatexercisethecode-under-
test,andassertspropertiesofthecode’sexpectedbehavior.
Forexample,thefollowingparameterizedunittestwritteninC#createsan
array-listwithanon-negativeinitialcapacity,addsanelementtothelist,and
thenassertsthattheaddedelementisindeedpresent.
[PexMethod]
public void AddSpec(
// data
int capacity, , object t element) ) {
// assumptions
PexAssume.IsTrue(capacity >= = 0);
// method sequence
ArrayList a a = new w ArrayList(capacity);
a.Add(element);
// assertions
Assert.IsTrue(a[0] == element);
}
Here,
AddSpec
is decoratedwiththe customattribute
[PexMethod]
, whichPex
usestodistinguishparameterizedunittestsfromordinarymethods.
JPEG to PDF Converter | Convert JPEG to PDF, Convert PDF to JPEG
Open JPEG to PDF Converter first; Load JPG images from local folders in "File" in toolbar Windows Explorer; Select "Batch Conversion" & Choose "PDF" in "Output
convert .pdf to .jpg online; change file from pdf to jpg
JPG to GIF Converter | Convert JPEG to GIF, Convert GIF to JPG
Open JPEG to GIF Converter first; Load JPG images from local folders in "File" in toolbar Windows Explorer; Select "Batch Conversion" & Choose "GIF" in "Output
convert pdf pages to jpg; conversion pdf to jpg
136
N.TillmannandJ.deHalleux
2.2 TheTestingProblem
Startingfromparameterizedunittestsasspecification,weformulatethetesting
problemasfollows.
GivenasequentialprogramP withstatementsS,computeasetofpro-
graminputsI suchthatforallreachablestatementssinSthereexists
aninputiinIsuchthatP(i)executess.
Remarks:
– Bysequentialwemeanthattheprogramissingle-threaded.
– We consider failing an assertion, or r violating g an implicit t contract of the
executionengine(e.g.
NullReferenceException
when
null
isdereferenced)as
specialstatements.
2.3 The e TestingProbleminPractice
Ingeneral,thereachabilityofprogramstatementsisnotdecidable.Therefore,in
practiceweaimforagoodapproximation,e.g.highcoverageofthestatements
of theprogram.Insteadofstatementcoverage,other coveragemetricssuchas
arccoveragecanbeused.
Inasystemwithdynamicclassloadingsuchas.NET,itisnotalwayspossible
todeterminethestatementsoftheprogramsaheadoftime.Intheworstcase,
theonlywaytodetermineallreachablestatementsisanincrementalanalysisof
allpossiblebehaviorsoftheprogram.
Theanalysisofallpossibleprogrambehaviors,i.e.allexecutionpaths,may
takeaninfiniteamountoftime.Inpractice,wehaveonlyalimitedamountof
timeavailable,soweaimforananalysisthatcanproducetestinputsformost
reachablestatementsfast.
Anotherproblemarisesfromthefactthatmostinterestingprogramsinteract
withtheenvironment.Inotherwords,thesemanticsofsomeprogramstatements
maynotbeknownaheadoftime.Moststaticanalysistoolsmakeconservative
assumptionsinsuchcasesandmayproducemanyfalsepositives,e.g.test-cases
thatsupposedlymayexhibitanerror,butinpracticedonot.Fortestgeneration
tools it t is more appropriate to o take into account t environment interactions in
ordertofilteroutfalsepositives.
Inthe remainder of this sectionwedescribethefoundationsonwhichPex
triestoaddressthetestingproblem,andthenextsectiondescribesPex’imple-
mentationinmoredetail,includinghowheuristicsearchstrategiesoftensolve
theproblemofachievinghighcoveragefast.
2.4 SymbolicExecution
Peximplementsawhite boxtestinput generationtechnique thatis basedon
theconceptofsymbolicexecution.Symbolicexecutionworkssimilartoconcrete
JPG to DICOM Converter | Convert JPEG to DICOM, Convert DICOM to
Open JPEG to DICOM Converter first; Load JPG images from local folders in "File" in toolbar Windows Explorer; Select "Batch Conversion" & Choose "DICOM" in
change from pdf to jpg; pdf to jpg
JPG to JBIG2 Converter | Convert JPEG to JBIG2, Convert JBIG2 to
Open JPEG to JBIG2 Converter first; Load JPG images from local folders in "File" in toolbar Windows Explorer; Select "Batch Conversion" & Choose "JBIG2" in
convert pdf file to jpg on; bulk pdf to jpg
Pex–WhiteBoxTestGenerationfor.NET
137
execution,onlythatsymbolicvariablesareusedfortheprograminputsinstead
ofconcretevalues.Whenaprogramvariableisupdatedtoanewvalueduring
programexecution,thenthisnewvaluemaybeanexpressionoverthesymbolic
variables.Whentheprogramexecutesaconditionalbranchstatementwherethe
conditionisanexpressionoverthesymbolicvariables,symbolicexecutionhasto
considertwopossiblecontinuations,sincetheconditionmayevaluatetoeither
true
or
false
,dependingontheprograminputs.Foreachpathexploredbysym-
bolicexecutioninthisway,apathconditionisbuiltoversymbolicvariables.The
pathconditionis theconjunctionoftheexpressionsthat representthebranch
conditionsoftheprogram.Inthismannerallconstraintsarecollectedwhichare
neededtodeducewhatinputscauseanexecutionpathtobetaken.
Aconstraintsolverorautomatictheoremproveris usedtodecidethefeasi-
bilityofindividualexecutionpaths,andtoobtainconcretetestinputsasrepre-
sentativesofindividualexecutionpaths.
2.5 DynamicSymbolicExecution
Pexexploresthereachablestatementsofaparameterizedunittestusingatech-
niquecalleddynamicsymbolicexecution[12,6].Thistechniqueconsistsinexecut-
ingtheprogram,startingwithverysimpleinputs,whileperformingasymbolic
execution inparallelto collect t symbolic constraints s on inputs obtained from
predicatesinbranchstatementsalongtheexecution.ThenPexusesaconstraint
solvertocomputevariationsofthepreviousinputsinordertosteerfuturepro-
gramexecutionsalongdifferentexecutionpaths.Inthisway,allexecutionpaths
willbeexercisedeventually.
Dynamicsymbolicexecutionextendsconventionalstaticsymbolicexecution
[16]withadditionalinformationthat is collectedatruntime,whichmakesthe
analysismoreprecise[12,11].Whileadditionalinformationiscollectedbymoni-
toringconcretetraces,eachofthesetracesisrepresentativeofanexecutionpath,
i.e.theequivalenceclass oftest inputs thatsteertheprogramalongthispar-
ticularexecutionpath.Bytakingintoaccountmoredetails ofstructureofthe
program(e.g.boundariesofbasicblocksorfunctions),evenbiggerequivalences
classescanbeanalyzedatonce[12,1].
Algorithm2.1showsthegeneraldynamicsymbolicexecutionalgorithmimple-
mentedinPex.Thechoiceofthenewprograminputsiineachloopiterationde-
cidesinwhichorderthedifferentexecutionpathsoftheprogramareenumerated.
Pexusesseveralheuristicsthattakeintoaccountthestructureoftheprogram
andthealreadycoveredstatementswhendecidingonthenextprograminputs.
While the ultimategoal of Pexis to discover allreachablestatements,which
is anundecidableproblem,inpracticePexattemptstoachievehighstatement
coveragefast.ThissimplifiestheconfigurationofPexgreatly:theuserjusthas
tosetatimelimitoranotherroughexplorationbound.Otherdynamicsymbolic
executiontools([12,11,12,6])performanexhaustivesearchofalltheexecution
pathsinafixedorder,withinboundsonthesizeandstructureoftheinputgiven
JPG to JPEG2000 Converter | Convert JPEG to JPEG2000, Convert
Open JPEG to JPEG2000 Converter first; ad JPG images from local folders in "File" in toolbar Windows Explorer; Select "Batch Conversion" & Choose "JPEG2000" in
change pdf file to jpg; change pdf into jpg
JPG to Word Converter | Convert JPEG to Word, Convert Word to JPG
Open JPEG to Word Converter first; Load JPG images from local folders in "File" in toolbar Windows Explorer; Select "Batch Conversion" & Choose "Word" in
pdf to jpeg; convert pdf pages to jpg online
138
N.TillmannandJ.deHalleux
by the user. Inthe case of Pex the inputs s areoften richly y structuredobject
graphsforwhichitisadifficultproblemtodefinepracticalandusefulbounds.
Algorithm2.1.Dynamicsymbolicexecution
SetJ:=∅
(intuitively,J isthesetofalready
loop
analyzed programinputs)
Chooseprograminputi/∈J
(stopifnosuchicanbefound)
Outputi
ExecuteP(i);recordpathconditionC (inparticular,C(i)holds)
SetJ :=J∪C
(viewingCastheset{i|C(i)})
endloop
2.6 MoreReasonsfor r Dynamic SymbolicExecution
Symbolicexecution was s originally proposed[16] ] as s a a static programanalysis
technique,i.e.ananalysisthatonlyconsideredthesourcecodeoftheanalyzed
program.Thisapproachworkswellaslongasalldecisionsaboutthefeasibility
of executionpaths canbemadeonbasis of thesourcecodealone.Itbecomes
problematic when n the e program m contains s statements that cannot t be reasoned
abouteasily(e.g.memoryaccessesthrougharbitrarypointers,orfloatingpoint
arithmetic), or r when n parts of f the program are e actually y unknown n (e.g. when
theprogramcommunicateswiththeenvironment,forwhichnosourcecodeis
available,andwhosebehaviorhasnotbeenspecifiedrigorously).
Itisnotuncommonfor.NETprogramstouseunsafe.NETfeatures,i.e.using
pointerarithmetictoaccessmemoryforperformancereasons,andmost .NET
programs interact with h other r unmanaged(i.e. . non-.NET) ) components or r the
WindowsAPIforlegacyreasons.
Whilestaticsymbolicexecutionalgorithmsdonotuseanyinformationabout
theenvironmentintowhichtheprogramisembedded,dynamicsymbolicexecu-
tioncanleveragedynamicinformationthatitobservesduringconcreteprogram
executions,i.e.thememorylocationswhichareactuallyaccessedthroughpoint-
ersandthedatathatispassedaroundbetweentheanalyzedprogramandthe
environment.
Asa result,Pexcanprunethesearchspace.Whentheprogramcommuni-
cates withthe environment,Pexbuilds amodel l oftheenvironment fromthe
actualdatathattheenvironmentreceivesandreturns.Thismodelisanunder-
approximationoftheenvironment,sincePexdoesnotknowtheconditionsunder
whichtheenvironment produces its output.The resultingconstraint systems
thatPexbuildsmaynolongeraccuratelycharacterizetheprogram’sbehavior.
Inpracticethismeansthatforacomputedinputtheprogrammaynottakethe
predictedexecutionpath.SincePexdoesnothaveapreciseabstractionofthe
program’sbehaviorinsuchcases,Pexmaynotdiscoverallreachableexecution
paths,andthusallreachablestatements.
Inanycase,Pexalwaysmaintainsanunder-approximationoftheprogram’s
behavior,whichisappropriatefortesting.
JPG to PNG Converter | Convert JPEG to PNG, Convert PNG to JPG
Open JPEG to PNG Converter first; Load JPG images from local folders in "File" in toolbar Windows Explorer; Select "Batch Conversion" & Choose "PNG" in "Output
convert pdf to jpeg on; best way to convert pdf to jpg
VB.NET Image: PDF to Image Converter, Convert Batch PDF Pages to
RasterEdge .NET Imaging PDF Converter makes it non-professional end users to convert PDF and PDF/A documents commonly in daily life (like tiff, jpg, png, bitmap
.pdf to .jpg online; convert pdf to high quality jpg
Pex–WhiteBoxTestGenerationfor.NET
139
3 PexImplementationDetails
3.1 Instrumentation
Pexmonitorstheexecutionofa.NETprogramthroughcodeinstrumentation.
Pex plugs into the .NET profiling API [21]. It inspects s the e instructions of a
methodintheintermediatelanguage[15]whichall.NETcompilerstarget.Pex
rewritestheinstructionsjustbeforetheyaretranslatedintothemachinecode
atruntime.Theinstrumentedcodedrivesa“shadowinterpreter”inparallelto
theactualprogramexecution.The“shadowinterpreter”
– constructs s symbolicrepresentationsoftheexecutedoperationsoverlogical
variablesinsteadoftheconcreteprograminputs;
– maintainsandevolvesasymbolicrepresentationoftheentireprogram’sstate
atanypointintime;
– recordstheconditionsoverwhichtheprogrambranches.
Pex’“shadowinterpreter”modelsthebehaviorofallverifiable.NETinstruc-
tionsprecisely,andmodelsmostunverifiable(involvingunsafememoryaccesses)
instructionsaswell.
3.2 SymbolicRepresentationofValuesandProgramState
Asymbolicprogramstateisapredicateoverlogicalvariablestogetherwithan
assignmentofexpressionsoverlogicalvariablestolocations,justasaconcrete
programstateisanassignmentofvaluestolocations.ForPex,thelocationsof
astateconsistofstaticfields,instancefields,methodarguments,localvariables,
andpositionsontheoperandstack.
Pex’expressionconstructors includeprimitive constants forallbasic.NET
datatypes (integers,floatingpoint numbers,objectreferences),andfunctions
overthosebasictypesrepresentingparticularmachineinstructions,e.g.addition
andmultiplication.Pex uses tuples torepresent .NETvalue types (“structs”)
aswellas indicesofmulti-dimensionalarrays,andmapstorepresentinstance
fields andarrays,similar tothe heapencodingofESC/Java[10]:Aninstance
fieldofanobjectisrepresentedbyafieldmapwhichassociatesobjectreferences
withfieldvalues.(Foreachdeclaredfieldintheprogram,thereisonelocation
inthestate that holdscurrentfieldmapvalue.) Anarraytypeis represented
byaclasswithtwofields:alengthfield,andafieldthatholdsamappingfrom
integers(ortuplesofintegersformulti-dimensionalarrays)tothearrayelements.
Constraintsover the .NETtype system andvirtual l methoddispatchlookups
areencodedinexpressionsaswell.Predicatesarerepresentedbyboolean-valued
expressions.
Wewillillustratetherepresentationofthestatewiththefollowingclass.
class C C {
int X;
int GetXPlusOne() ) { { return this.X + + 1; }
void SetX(int t newX) { { this.X X = newX; }
}
140
N.TillmannandJ.deHalleux
Symbolically executing the method
c.GetXPlusOne()
withthe receiver object
givenbytheobjectreference
c
willyieldtheexpression
add(select(X_Map,c), 1)
wherethe
select
functionrepresentstheselectionof
c
’s
X
-fieldvaluefromthe
currentfieldmap
X_Map
.Aftersymbolicallyexecuting
c.SetX(42)
,thefinalstate
will assignthe expression
update(X_Map,c,42)
to the location that holds s the
currentfieldmapof
X
.
X_Map
denotesthevalueofthefieldmapof
X
beforethe
executionofthemethod.
Peximplements varioustechniquestoreducetheenormous overheadofthe
symbolicstaterepresentation.Beforebuildinganewexpression,Pexalwaysap-
plies asetofreductionruleswhichcomputeanormalform.Asimpleexample
ofareductionruleisconstantfolding,e.g.1+1isreducedto2.Alllogicalcon-
nectivesaretransformedintoabinarydecisiondiagram(BDD)representation
withif-then-elseexpressions[5].Allexpressionsarehash-consed,i.e. only one
instanceiseverallocatedinmemoryforallstructurallyequivalentexpressions.
Mapupdates, whichare usedextensively torepresent the evolving heapof a
program,arecompactlystoredintries,indexedoveruniqueexpressionindices.
Based onthe e already accumulated d path condition,expressions are e further
simplified.Forexample,ifthepathconditionalready establishedthat x> 0,
thenx<0simplifiesto
false
.
3.3 SymbolicPointers
Pexrepresentspointersas expressions aswell.Pexdistinguishesthefollowing
pointerconstructors.
– Pointertonowhere.Representsaninvalidpointer,orjust
null
.
– Pointertovalue.Representapointertoanimmutablevalue,e.g.apointer
tothefirstcharacterofastring.
– Pointertostaticfield.
– Pointerto instance fieldmap.Represents s apointer tothe mappingof an
instancefieldthatassociatesobjectreferenceswithfieldvalues.
– Pointertomethodargumentorlocalvariable.
– Pointertoelement.Givenapointertoamappingandanindexexpression,
representsapointertotheindexedvalue.
While thepointers insafe,managed.NETprograms are guaranteedtobe
either
null
or pointingtoa a validmemorylocation,unsafe .NETcodethat t is
sufficientlytrustedtobypass.NET’sbytecodeverifierdoesnotcomewithsuch
aguarantee.Thus,when the e user enables Pex’ strict pointer checking mode,
Pexbuilds averificationconditionwheneverthe programis abouttoperform
anindirectmemoryaccessthroughapointer.Inparticular,givenapointerto
anelementofanarray,theconditionstatesthattheindexmustbewithinthe
boundsofthearray.
Inpractice,theverificationconditionscanverifymostuses of unsafepoint-
ers.Forexample,thefollowingcodeshowsacommonuseofpointers,withthe
intentionofsimplyavoidingtheoverheadofrepeatedarray-boundschecking.
Pex–WhiteBoxTestGenerationfor.NET
141
public unsafe bool BuggyContainsZero(byte[] a) ) {
if (a == = null || | a.Length == null) return n false;
fixed (byte* * p = a)
for (int t i = = 0; ; i i <= = a.Length; i++)
if (p[i] ] == = 0) ) return true;
return true;
}
This codecontainsanerror:Theloopconditionshouldbe
i < < a.Length
in-
steadof
i <= a.Length
.Thiserrormightnotbedetectedwithconventionaltest-
ing,sincereadingbeyondtheboundsofanarraywithapointeroftendoesnot
triggeranexception(theallocatedmemoryisusuallyadvancedtoanotherblock
ofallocatedmemory).
Whiletheproblemofbufferoverflowshasbeenwellstudied,e.g.inthecontext
ofC programsthat t arecompiledtomachine code directly,we are not aware
of athoroughchecker r inthe context of managedexecution n environments, in
particular.NET.
Pexcannotonlydetecttheerrorinstrictpointer-checkingmode,Pexwilleven
steertheprogramtowardsobscureprogrambehaviorsbytestinputgeneration
throughdynamicsymbolicexecution.
However,Pex cannot symbolically reasonabout all operations that involve
pointers.Inparticular, Pexdoes s not track when n the e content of amemory is
reinterpreted,e.g.apointertoanarrayofbytesiscasttoapointerofaninteger,
andwhenthememorywasobtainedfromtheenvironment,e.g.throughacall
toaWindowsAPI.
3.4 SearchStrategy
Decidingreachabilityofprogramstatementsisahardproblem.Inasystemwith
dynamicclassloadingandvirtualmethoddispatchtheproblemdoesnotbecome
easier.Asdiscussedearlier,Pex’approachbasedondynamicsymbolicexecution
enumeratesfeasibleexecutionpaths,whereinformationfrompreviouslyexecuted
pathsisusedtocomputetestinputsforthenextexecutionpaths.Mostearlier
approachtodynamicsymbolicexecution[12,27,26,6]infactonlyuseinformation
from the last execution n path to determine e test inputs s that will exercise e the
nextpath.Thisrestrictionforcesthemtouseafixed“depth-first,backtracking”
searchorder,where the e next execution n path wouldalways share e the longest
possibleprefixwiththepreviousexecutionpath.Asaresult,alotoftimemaybe
spentanalyzingsmallpartsoftheprogrambeforemovingon.Theseapproaches
requirewelldefinedboundsontheprograminputstoavoidunfoldingthesame
programloopforever,andtheymaydiscover“easy”tocoverstatementsonly
after anexhaustive search. . (Toavoidgetting stuck in the e depth-first t search,
theseearlierapproachesfrequentlyinjectrandomtestinputstosteerthesearch
towardsotherparts oftheprogram.However,thispreventsanydeepsymbolic
analysis.)
Pexusestheinformationofallpreviouslyexecutedpaths:Duringexploration,
Pexmaintainsarepresentationoftheexploredexecutiontreeofthe program,
142
N.TillmannandJ.deHalleux
whosepathsaretheexploredexecutionpaths.Ineachstepofthetestgeneration
algorithm,Pexpicksanoutgoingunexploredbranchofthetree,i.e.theprefix
ofafeasibleexecutionpathplusanoutgoingbranchthathasnotbeenexercised
yet.Thenexttestinputsarethesolution(ifany)oftheconstraintsystemthat
is builtfrom theconjunctionofthe pathconditionofthefeasiblepathprefix,
andtheconditionoftheunexercisedoutgoingbranch.Iftheconstraintsystem
hasnosolution,oritcannotbecomputedbytheconstraintsolver,thesearch
marksthebranchasinfeasibleandmoveson.
Inearlierexperiments,wetriedwell-knownsearchstrategiestotraversethe
executiontree, suchas s breadth-firstsearch. . While this strategy does s not get
stuckinthesame way as depth-first search,it does nottakeintoaccountthe
structureoftheprogrameither.
Theprogram consists of building blocks suchasmethods andloops,which
maygetinstantiatedandunfoldedmanytimesalongeachexecutionpath,giv-
ingrisetomultiplebranchinstancesintheexecutionpath(andtree).For our
ultimategoal,tocoverallreachablestatements,thenumberofunfoldingsisir-
relevant,althoughacertainnumberofunfoldingsmightberequiredtodiscover
thatastatementisreachable.Howmanyandwhichunfoldings arerequiredis
undecidable.
Inordertoavoidgettingstuckinaparticularareaoftheprogrambyafixed
searchorder,Peximplementsafairchoicebetweenallsuchunexploredbranches
oftheexploredexecutiontree.Pexincludesvariousfairstrategieswhichpartition
allbranchesintoequivalenceclasses,andthenpickarepresentativeoftheleast
oftenchosenclass.Theequivalenceclassesclusterbranchesbymappingthem
– tothebranchstatementintheprogramofwhichtheexecutiontreebranch
isaninstance(eachbranchstatementmaygiverisetomultiplebranchin-
stancesintheexecutiontree,e.g.whenloopsareunfolded),
– tothestacktraceatthetimethebrachwasrecorded,
– totheoverallbranchcoverageatthetimethebranchwasrecorded,
– tothedepthofthebranchintheexecutiontree.
Pex combinesallsuchfairstrategiesintoameta-strategythatperforms afair
choicebetweenthestrategies.
Creatingcomplexobjects. Whenanargumentofaparameterizedunittest
isanobjectthathasnon-publicfields,Pexwillstillcollectconstraintsoverthe
usageofthatfield.Later,newtestinputsmaybecomputedwhichassignpartic-
ularvaluestothosefields.ButthenPexmaynotknowhowtocreateanobject
throughthepubliclyavailableconstructorssuchthattheobject’sprivatefields
areinthedesiredstate.(Ofcourse,Pexcoulduse.NET’sreflectionmechanism
tosetprivatefieldsinarbitraryways,butthenPexmightviolatethe(implicit)
classinvariant.)
Insuchcases,Pexselects aconstructoroftheclass(theusermayconfigure
whichconstructorischosen),andPexincludesthisconstructorintheexploration
of the e parameterized d unit test. As s a a result, Pex will first t try y to o find a non-
exceptionalpaththroughthecontrol-flowoftheconstructor,andthenusethe
Pex–WhiteBoxTestGenerationfor.NET
143
createdobjecttofurtherexploretheparameterizedunittestthatrequiredthe
object.Inotherwords,Pextriestoavoidthebackwardsearchtofindawayto
reachatargetstate;instead,itwillperformaforwardsearchthatiscompatible
withdynamicsymbolicexecution.
Inthis way,directedobject graphscaneasily be created,where arguments
to constructors s canrefer r to earlier r constructed d objects.Cyclic object t graphs
canonlyresultifaconstructorupdates afieldofanargumenttopointtothe
constructedobject.
Asanalternativetoemployingonlyexistingconstructorstoconfigureobjects,
the user may alsoprovidefactorymethods,whichcouldinvokeasequenceof
methodcallstoconstruct andconfigureanewobject,possiblycreatingcyclic
referencesaswell.
3.5 ConstraintSolving
For eachchosenunexploredbranch,Pex builds aformulathat representsthe
conditionunderwhichthis branchmaybereached.Pex performsvariouspre-
processing steps to reduce the size of the formula before handing it over r to
theconstraintsolver,similartoconstraintcaching,andindependentconstraint
optimization[6].
PexemploysZ3asitsconstraintsolver.Pexfaithfullyencodesallconstraints
arisinginsafe.NETprogramssuchthatZ3candecidethemwithits built-in
decisionproceduresforpropositionallogic,fixedsizedbit-vectors,tuples,arrays,
andquantifiers.Arithmeticconstraintsoverfloatingpointnumbersareapprox-
imatedbyatranslationtorationalnumbers.Pexalsoencodes the constraints
ofthe.NET type system andvirtual methoddispatchlookups s as universally
quantifiedformulas.
3.6 Pex x Architecture
Internally,Pexconsistsofseverallibraries:
Microsoft.ExtendedReflection. ExtendedReflection(ER)isalibrarythat
enablesthemonitoringof.NETapplicationsattheinstructionlevel.Ituses
theunmanagedprofilingAPItoinstrumentthemonitored.NETprogram
withcallbackstothemanagedERlibrary.Thecallbacksareusedtodrive
the“shadowinterpreter”mentionedinSection3.1.
Microsoft.Pex.Framework. Thislibraryisservesasafront-endfortheuser
toconfigurePex.Itdefinesanumberof.NETcustomattributes,including
the
PexMethod
attributethatweusedintheearlierexample.
Microsoft.Pex. ThePexengineimplements s thesearchfortestinputs,byre-
peatedlyexecutingtheprogramwhilemonitoringit,andbuildingconstraint
systemstoobtainnewtestinputs.
Microsoft.Z3. [3]istheconstraintsolverthatPexuses.
Documents you may be interested
Documents you may be interested