Effects of Pointers on Data Dependences(12)

Data dependences, which relate statements that compute data values to statements that use those values, are useful for automating a variety of program-comprehension-related activities, such as reverse engineering, impact analysis, and debugging. Unfortunat

correspondstoadata-dependencetypeandrepresentsthepercentageofdata-dependencesforthattype.Thedatainthe gureillustratesthatdatadependencesfallpredominantlyintoonlythreetypes.Duatype1,duatype3,andduatype20occurmostfrequently:togetherthesetypesaccountforover98%ofthetotaldatadependences.Oftheremaining21typesofdatadependences,12typesoccurinmarginalnumbersandaccountfortheremaining2%ofthedatadependences.Theremaining9typesofdatadependencesdonotoccurinthesubjects;suchtypesarenotlistedalongthehorizontalaxisinFigure6.

Theresultsofthisstudyarepreliminaryinnature.AlthoughthedatainFigure6showstrendsinthedistributionofdata-dependencetypes,thescarcityofthedatapoints,preventsusfromdrawinganyconclu-sionsaboutthedistribution.Furtherexperimentationwithmoreanddiversesubjectswillhelpdetermineiftrends,suchasthefrequentoccurrenceofduatype20,persist.Thedatainthe gureshowsthatforover30%ofthedatadependences,nopathfromthede nitiontotheusecontainsarede nitionoftherelevantvariable.Thisresultisimportantbecauseitmeansthat,forthesedatadependences,statementcoverageguaranteesthecoverageofthecorrespondentdef-useassociations.

ThelastthreebarsinFigure6showthedistributionofdata-dependencetypesaccordingtoOstrandandWeyuker’sclassi cation[19].Accordingtotheirclassi cation,over88%ofthedatadependencesarestrong,andover11%ofthedatadependencesareveryweak.Theremaining1%ofthedatadependencesareweak;nodatadependenceis rm.

4ApplicationsoftheData-DependenceClassi cation

Theabilitytoclassifydatadependencescanbeexploitedfordi erentapplications.Forexample,datadependencesthatareorderedbasedontheir“strength”canguideadata- owtestingstrategy[9],canbeusedtoperformimpactanalysesfocusedondi erentkindsofdependences,andcanbeanalyzedtoidentifypartsofthecodewherepossiblyunforeseendatadependencesrequirecarefulsoftwareinspections.Inshort,allactivitiesthatdependondata-dependenceinformationcanutilizesuchaclassi cation.Inthispaper,wefocusonanapplicationthatisrelatedtoprogramunderstanding—programslicing.Inthefollowingsection,wede neaslicingtechniquethatletsuscomputeslicesbasedondata-dependencetypes;wealsoillustrateacasestudyinwhichweapplythetechnique.

4.1Programslicing

Traditionalslicingtechniques(e.g.[12,14,27])includeinthesliceallstatementsthata ecttheslicingcriteriathroughdirectortransitivecontrolanddatadependences.Suchtechniquescomputetheslicebycomputingthetransitiveclosureofallcontrolandalldatadependencesstartingattheslicingcriterion.Theclassi cationofdatadependencesintodi erenttypesleadstoanewparadigmforslicing,inwhichthetransitiveclosureisperformedoveronlythespeci edtypesofdatadependences,ratherthanoveralldatadependences.Inthisslicingparadigm,aslicingcriterionisatriple<s,V,T>,wheresisaprogrampoint,Visasetofprogramvariablesreferencedats,andTidenti esoneormoretypesofdatadependences.Thesliceincludesthosestatementsthatmaya ectthevalueofthevariablesinVatsthroughtransitivecontrolorspeci edtypesofdatadependences.

Usingthenewslicingparadigm,wede neaslicingtechniquethatincreasesthescopeofasliceincre-mentallybyincludingdatadependencesofdi erenttypes.Thetechniquestartsbyconsideringthestronger