Delayed and controlled failures in tamper-resistant systems

Tamper-ResistantSoftware

GangTan1,YuqunChen2,andMariuszH.Jakubowski2

1

ComputerScienceDepartment,BostonCollege.gtan@cs.bc.edu2

MicrosoftCorporation.{yuqunc,mariuszj}@microsoft.com

Abstract.Tamper-resistantsoftware(TRS)consistsoftwofunctionalcomponents:tamperdetectionandtamperresponse.AlthoughbothareequallycriticaltotheeffectivenessofaTRSsystem,pastresearchhasfocusedprimarilyontheformer,whilegivinglittlethoughttothelat-ter.Notsurprisingly,manysuccessfulbreaksofcommercialTRSsystemsfoundtheirfirstbreachesattherelativelyna¨ıvetamper-responsemod-ules.Inthispaper,wedescribeanoveltamper-responsesystemthatevadeshackerdetectionbyintroducingdelayed,probabilisticfailuresinaprogram.Thisisaccomplishedbycorruptingtheprogram’sinternalstateatwell-chosenlocations.Ourtamper-responsesystemsmoothlyblendsinwiththeprogramandleavesnonoticeabletracesbehind,mak-ingitverydifficultforahackertodetectitsexistence.Thepaperalsopresentsempiricalresultstodemonstratetheefficacyofoursystem.

1Introduction

Softwaretamperingcontinuestobeamajorthreattosoftwarevendorsandcon-sumers:Billionsofdollarsarelosteveryyeartopiracy3;tamperedsoftware,appearinglegitimatetountrainedconsumers,alsothreatenstheirfinancialsecu-rityandprivacy.Asthemaincountermeasure,thesoftwareindustryhasinvestedheavilyinTamper-ResistantSoftware(TRS)withvaryingdegreeofsuccess.Thispaperfocusesonaneglectedaspectoftamperresistance,namelyhowtheTRSshouldrespondtotampering.

Softwaretamperingisoftenconductedonamalicioushostthatisunderahacker’scompletecontrol:thehackerisfreetomonitorthehardware,aswellasmodifyandobservethesystemsoftware(i.e.,OS).OncurrentPCplatform,with-outdedicatedhardwaresupportsuchasprovidedbyNGSCB[6,17],TRSmustrelyonsoftwareobfuscationtoevadedetectionanddefeathackingattempts[8–11,19].Stealth,ortheartofhidingcodeinthehostprogram,isthefirstandtheprimarydefensethatmostTRSsystemsdeployagainsthackers.Ideally,thecodepertainingtotamperresistanceshouldbeseamlesslyintertwinedwiththehostprogram’scode,sothatahackercannotdiscoveritslocation(s)byeitherinspectingtheprogram’scodeormonitoringitsruntimebehavior[7].

3

Accordingtostudies[1]byBusinessSoftwareAlliance(BSA)andInternationalDataCorporation(IDC),theretailvalueofpiratedsoftwaregloballyis29billions,33billions,and34billions,in2003,2004,and2005,respectively.

ATRSsystemconsistsoftwofunctionalcomponents:tamperdetectionandtamperresponse;eachcanbemadeofmultipledistinctmodules.Bothcompo-nentsareequallyimportanttotheeffectivenessofaTRSsystem.Inpractice,however,mostR&Dworkhasgoneintohidingthetamper-detectioncode,whichverifiesthehostprogram’sintegrity[5,7,13];surprisinglylittlehasbeendonetoimprovethestealthofthetamper-responsecomponent.SincehackerstendtolookfortheweakestlinktocrackthedefenseperimeterofaTRSsystem,inadequatetamper-responsemechanismshaveoftenbecometheAchilles’heelofcommercialTRSsystems[4].

WhilesomeTRSsystemscanbeeffectiveifproperlyapplied,softwareau-thorshaveoftenusedonlysimpleordefaultTRSfeatures.Forexample,certaindongle-andCD-basedcopyprotectionsperformjustoneorafewbooleanchecks,whichmaybeeasilypatchedout[14].Thus,itishighlyusefultoautomatetheprocessofseparatingchecksfromresponses.

Inthispaper,wedescribeanoveltamper-responsesystemthatevadeshackerdetectionbyintroducingdelayed,probabilisticfailuresinaprogram.Themaintechniqueistocorruptcertainpartsofthehostprogram’sinternalstateatwell-chosenlocationssothattheprogrameitherfailsorexhibitsdegradedperfor-mance.Onecanalsoplugotherfailure-inducingtechniquesintoourframework;someofthemcanbefoundinSection6.Ourtamper-responsesystemsmoothlyblendsinwiththeprogramandleavesnonoticeabletracesbehind,makingitverydifficultforahackertodetectitsexistence.

Therestofthispaperisorganizedasfollows.WedescribesomepriorartandrelatedworkinSection2.InSection3,weintroduceprinciplesforeffectivetamper-resistantsoftware.Wedescribeourtamper-responsesysteminSection4.ImplementationdetailsandsystemevaluationarepresentedinSection5.WediscussinterestingextensionsinSection6,andconcludeinSection7.

2Relatedwork

Asinformaladvice,theideaofseparatingtamperdetectionfromresponsehaslongbeenfamiliartoprogrammersofsoftware-protectionschemes[4].Thecon-ceptof“gracefuldegradation”,orslowdecayofaprogram’sfunctionalityaf-tertamperdetection,isacloselyrelatedtechnique,whichhasbeenwidelyre-portedtobeusedcommercially[16].Softwareauthorstypicallyhavenotre-vealedhowspecificimplementationsachievetheseeffects;ingeneral,manualandapplication-specifictechniqueshavebeenused.Ourworkprovidessystematic,automatedmethodsofseparatingdetectionfromresponseingeneralprograms.Commercialcopyprotection,licensing,andDRMsystemshaveemployedmanyunpublishedtechniques,whichhavebeendescribedbyhackersonalargenumberofInternetsitesanddiscussionboards.Suchmethodshaveoftenreliedon“securitybyobscurity,”whichmaybeavalidtacticwhenonlylimitedpro-tectionstrengthisdesiredorexpected,asinthecaseofcertaincopyprotections.Thisworkbelongstothegeneralcategoryoftamper-resistance,softwareob-fuscation,andsoftwarewatermarking.Representativeexamplesinthiscategory

includeruntimecodeencryptionanddecryptionbasedonavisibilityschedule[2];taxonomiesofgenericobfuscatingtransformationsandopaquepredicates[9–11];complicationofpointer-aliasingandcontrol-flowanalysis[8,19];andintegrityverificationofbothstaticprogramcode[5,13]anddynamicexecutiontraces[7].

Theoreticaltreatmentofobfuscation[3]hasrevealedthatageneralobfusca-torcannotexistforarbitrarysoftwareunderaspecificmodel.Thisshowsonlytheexistenceofcertaincontrivedprogramsthatcannotbeobfuscatedagainstapolynomial-timeadversary,andthusdoesnotnecessarilyblockpracticalsolu-tions.Furthermore,someformsofsecrethiding,whichincludeUnix-stylepass-wordhashing,havebeenprovensecureeveninthisframework[15,20].Anearlier,somewhatdifferentmodel[12]showedthatobfuscationispossibleinthesenseofrandomizingmemoryaccessesofcertainprograms,albeitataperformancecostimpracticalfortypicalapplications.

3Tamper-resistantsoftwaremodelandprinciples

Beforedescribingoursystem,wefirstdefineasimplemodeloftamper-resistantsoftwareandlayoutasetofprinciplestowhichaneffectiveTRSsystemmustadhere.Inthefollowingdiscussion,weconsiderathreatmodelwiththesepartici-pants:softwarevendors,legitimateusers,andsoftwarepirates.Softwarevendorsproducesoftware,havethesourcecode,andsellsoftwareintheformofexe-cutablecode.Legitimateusersandsoftwarepiratesbuysoftware(intheformofexecutablecode)fromthevendors.Softwarepiratestrytotamperwiththesoftwaretobypassitscopyright-protectionsystem.

Initssimplestincarnation,atamper-resistantsoftwaremoduleresidesinandprotectsanothersoftwaremodule.Themodulebeingprotected(orthehostmodule)canbeanapplicationprogram,alibrary(eitherstaticallylinkedordynamicallyloaded),anoperatingsystemoradevicedriver.Inpractice,multipleTRSmodulesarespreadamongstseveralmodulestocreateacomplexwebofdefenses;inthispaper,however,weconcentrateonthesimplifiedcaseofasinglehostmodule.Thisistosimplifythediscussionwithoutlossofgenerality.

TheTRSmodulecanbefunctionallydecomposedintotwocomponents:tam-perdetectionandtamperresponse.Asthenamesimply,theformerisresponsiblefordetectingwhetherthehostmodule,includingtheTRSmoduleitself,hasbeen(orisbeing)tamperedwith;thelattergeneratesanappropriateresponsetoei-therthwartsuchtamperingorrenderthetamperedhostmoduleunusable.Morespecifically,

Detection.Weassumeoneormoredetection-codeinstancesexistinthehost

module.Theycommunicatewiththeresponsecodeviacovertflags:upondetectingtampering,thedetectioncodesetsoneormoreflagstoinformtheresponsemoduleasopposedtocallingthelatterdirectly.Acovertflagneednot(andshouldnot)beanormalbooleanvariable.Itcantaketheformofacomplexdatastructure,suchasadvocatedbyCollbergetal.[9–11].

Researchershavebeenputtingafairamountofeffortintobuildingdetectionsystems.Astaticchecksumbasedoneitherthestaticprogramcode[5,13]or

dynamicexecutiontraces[7]ofthecodeiscomputedandstoredinasecretplace.Thedetectionsystemcomputesthenewchecksumwhenprogramsarerunninginmalicioushosts,andcheckwhetherthenewchecksumisidenticaltotheoldone.

Response.Whentamperingisdetected,anunusualeventmusthappentoei-therstoptheprogramfromfunctioning(inthecaseofstandaloneapplica-tions)orinformingtheappropriateauthority(inthecaseofnetwork-centricapplications).Inthiswork,werestrictourattentiontostandaloneappli-cationsinwhichaprogramfailureisoftenadesirableeventposttamper-detection.

WeexpecttheTRSmoduletohavemultipleresponsecodeinstancesinplace.Ideallytheyshouldbemutuallyindependentsothatuncoveringofonedoesnoteasilyleadtouncoveringofothers.Intheory,theresponsesshouldbesocraftedthatthehackercannoteasilylocatethecodeanddis-ableit,norbacktracktothedetectioncodefromit.However,inpracticethedetectionmechanismcanoftenbelocatedbyinspectingthecodestaticallyorback-tracingfromtheresponsethatthetamper-resistantcodegenerates.Wenotethatourworkisaboutseparatingtamperresponsefromdetection,butnotaboutchoosingthedetectionsitesinthefirstplace.Weassumethatsomelistofdetectionlocationsisprovidedtoouralgorithm.Forexample,apro-grammermaychoosesuchlocationsmanually;alternately,atoolmaygeneratealistofsitessemi-randomly,possiblyinfluencedbyperformanceandsecurityrequirements,aswellasbystaticanddynamicanalysis.Relatedtothecheckingmechanismsthemselves,suchmethodsarebeyondthescopeofthispaper.3.1

Principlesofeffectivetamper-responsemechanisms

Letusfirstlookatana¨ıveresponsesystem(anexamplealsousedbyCollbergandThomborson[10])andseewhatkindofattacksadversariescanapply:

iftampered_with()theni=1/0

Upondetectingtampering,theaboveresponsecodecausesadivide-by-zeroerrorandthentheprogramstops.Sincetheprogramfailsrightattheplacewheredetectionhappens,anadversary,withtheabilitytolocatethefailurepoint4,cantriviallytracebacktothedetectioncodeandremoveit.Alternatively,sincedivide-by-zeroisanunusualoperation,anadversarycanstaticallyscantheprogramtolocatethedetectioncodefragmentsandthenremoveit.

Thena¨ıveresponserevealsmanyinformationoftheTRSmoduletoanad-versary.Anidealresponsesystem,incontrast,shouldnotrevealinformationoftheTRSmodule.Basedonthisguideline,wenextproposeasetofprinciples5foreffectivetamper-responsemechanisms.

45

Adebuggerissufficient.

Theprincipleofspatial/temporalseparationhasalsobeenbrieflydiscussedbyColl-bergandThomborson[10].

Spatialseparation.Tamperresponsesandthecorrespondingfailuresshould

bewidelyseparatedinspace:Whiletheresponseisperformedinonepartoftheprogram,itseffect(failure)becomesonlyapparentinotherparts.Thisway,evenanadversarycanidentifythefailurepoint,hecannottracebacktotheresponsepoint.

Onequestionisthatwhatisagoodmetricforspatialseparation.Onemetricisthenumberoffunctioncallsinvokedbetweentamperresponsesandpro-gramfailures.Byincreasingthenumberoffunctioncalls,wehopethatlittletracehasbeenleftforanadversarytoperformanyanalysis.Inaddition,thefunctionwheretheresponsecoderesidesisbetternotinthecurrentcallstackwhenthefailurehappens,becausedebuggerscangiveadversariestheinformationofthecurrentcallstack.Temporalseparation.Ifaresponsesystemcancauseenoughamountofdelay

beforefailure,itcaneffectivelythwarttheprocessoftampering.Imagineanattackwherebyanadversarytriesanumberoftamperingoptions.Theadversarytriesoneoptionandstartstoobservetheprogram’sbehaviortoseeifthetamperingworks.Supposeourresponsesystemwillnotfailtheprogramuntilafteralargeamountoftime,sayoneday.Thenonlyafteroneday,thepooradversarywilldiscoverthathistrickisnotworkingandheneedstospendanothernighttotryanotheroption.Thisispsychologicallyfrustratingfortheadversaryandwillcertainlyslowdownthetamperingprocess.Thestrategyofdelayedfailureisanalogoustoinjectingextradelaybetweentwoconsecutivepasswordtriesinapasswordprotectionsystem.Themetricfortemporalseparationisobviouslythetimeorthenumberofinstructionsexecutedbetweenresponseandfailure.Stealth.Thecodeinatamper-responsesystemshouldblendinwiththepro-grambeingprotectedsothatanautomaticscanningtoolwillnotidentifythetamper-responsecodeeasily.Aresponsesysteminvolvingdivision-by-zeroisdefinitelynotagoodidea.

Stealthisahighlycontext-sensitivequality.Responsecodethatisstealthyinoneprogrammaynotbesoinanother.Anymetricforstealthhastobewithrespecttothecontext,ortheprogram.Onepossiblemetricisthestatisticalsimilarity6betweentheprogrambeingprotectedandtheresponsecode.Predictability.Aprogramthathasbeentamperedwithshouldeventuallyfail,

withhighprobability.Wealsowanttocontrolwhenandwherethefailure(damage)canhappen.Afailurethathappensduringsensitiveoperationsisprobablyundesirable.Inaddition,anyavailableobfuscationshouldbeusedtoprotectthetamper-detectionandresponsecode.Ideally,neitherobservationnortamperingshould

6

E.g.,thepercentageofeachkindofmachineinstructions.

easilyrevealpatternsusefulfordeterminingwheredetectionandresponseoccur.Inpractice,bothgenericandapplication-specificobfuscationmethodsshouldbedevisedtomaximizeanattacker’sworkload.

4Systemdescription

WenowdescribearesponsemechanismwehavebuiltfollowingtheprinciplesinSection3.1.Ourstartinginsightisthatbycorruptingaprogram’sinternalstate,aresponsesystemcancausetheprogramtofail.Ifwecarefullychoosewhichpartofstatetocorruptandwhentocorrupt,wemayachievetheaforementionedspa-tialandtemporalseparation.Thisdeliberateinjectionof“programmingbugs”alsosatisfiesourstealthprinciplebecausethesebugslookjustlikenormalpro-grammingbugsandarethushardtopickoutbystaticscanning.7Bugsduetoprogrammingerrorsarehardtolocate.Someofthesebugscausedelayedfailure.Asanexample,anearlysystemcalledHUW[18]appearedtorunsuccessfully,butcrashedafteraboutonehour.Thiswasduetoanelusivebuginitsstringhandlingmodule,whichcorruptedthesystem’sglobalbuffer.Thedatastruc-turesinsidethecorruptedbuffer,however,werenotuseduntilaboutanhourlater.Therefore,thesystemranOKuntilthecorrupteddatastructureswereaccessed.

Aswecanseefromthisexample,corruptingprograms’internalstatemightproducetheeffectofdelayedfailure.Forclarity,weassumetherearethreekindsofsites:detectionsites(wheretamperdetectionhappens),responsesites(wherecorruptingtheinternalstatehappens),andfailuresites(wherefailurehappens).Responsesitesarealsocalledcorruptionsitesinoursystem.Intherestofthispaper,forsimplicity,wewillidentifydetectionsiteswithcorruptionsites.Inpractice,detectionsitesandcorruptionsitesshouldbeseparated(andcommunicateviacovertflags),andthetechniquesandimplementationthatwewillintroduceappliesaswell.

Therearemanywaystocorruptaprogram’sinternalstate.Oursystemchoosesthestraightforwardway:corrupttheprogram’ownvariables.Byde-liberatelycorruptingtheprogram’variables,wehopetoachievethefollowingresults:

–Predictablefailureoftheprogram,duetothecorruptionoftheprogram’sinternalstate.

–Stealthyresponsecode,sincetheresponsecodeisjustanordinaryvariableassignment.

–Spatialandtemporalseparation,ifwecarefullychoosewhenandwheretocorruptthevariables.Notallvariablesaregoodcandidates.Supposethevalueofanintegervariablerangesbetween3and10.Thenwhatwouldbethebehavioroftheprogramwhen

7

Ifthereisregularityinthetypeofbugsweintroduce,anattackermaybeabletoemploystaticanalysistoincreasehis/herlikelihoodoflocatingthem.

thevariableischangedto100?Wouldtheprogramfail?Whereandwhenwoulditfail?Wehavetoanswerthesequestionstoachievesomepredictabilityinourresponsesystem.Wesuspectthatforanarbitraryprogramvariable,theresultofanyanalysisishighlyimprecise.However,oneobservationcanbemadeaboutpointervariables,whichareubiquitousinC-styleprograms.IfapointeriscorruptedbysettingittoaNULLpointeroravalueoutoftheprogram’saddressspace,dereferenceofthispointerdefinitelycrashestheprogram.Moreover,ifthenextdereferencehappensonlyaftersometime,weachievetheeffectofdelayedfailure.

Corruptionoflocalpointers(declaredinafunctionbody)isunlikelytoachievemuchdelay.Thecorruptionoflocalpointershastohappenlocally,be-causetheirstorageisintherun-timestack,Theirvaluesarealsousedlocally,whichmeansthecorruptionandusagewouldbeverycloseifwehadchosentocorruptalocalpointer.

int * pModule CModule AModule BFig.1.Globalpointers.

Forglobalpointers,thescenarioisdifferentandoneexampleisdepictedinFigure1.SupposethereisaglobalpointerpwhichisusedbymodulesBandC,butnottouchedbymoduleA.IfwechoosetocorruptthispointerinmoduleA,thentheprogramwillkeeprunninguntilmoduleAhasfinishedandtheprogramswitchestomoduleBorC.Basedonthisexample,intuitionistherethatdelayedfailurecanbeachievedbycorruptingaglobalpointer.

Butwhatiftheprogramhasnotmanyglobalpointers?Oursolutionistoperformtransformationsontheprogramtocreatenewglobalpointers.Onewaytoachievethisistoaddalevelofindirectiontotheexistingglobalvariables.TheideaisillustratedbytheexampleinFigure2.

OntheleftofFigure2istheoriginalprogram;thecodeaftertransformationisontheright.Fortheglobalvariablea,wecreateanewpointervariablepa,whosevalueisinitializedtotheaddressofa.Thenwereplacealluses,orsomeuses,ofvariableabythedereferenceofthenewlycreatedpointervariablepa.

Belowarethebenefitsoftheextralevelofindirectiontoglobalvariables:–Anyglobalvariablescanbeusedtocreatenewpointers,alleviatingthepossibleshortageofglobalpointers.

–Thefailurebehaviorofthenewprogramiseasilypredictable.Afterpaiscorrupted,anysubsequentuseofthevariable,pa,wouldbeafailuresite.

inta;

voidf(){a=3;}

voidmain(){f();

printf(‘‘a=%i\\n’’,a);}

inta;

int*p_a=&a;voidf(){*p_a=3;}

voidmain(){f();

printf(‘‘a=%i\\n’’,*p_a);}

Fig.2.Example:Creatingalayerofindirectiontoglobalpointers.

–Wecanalsocontrolwheretheprogramfails.Forexample,ifwedonotwanttheprogramtofailinsidethemainfunction,wejustdonotreplaceawithpainmain.Notethattheextralevelofindirectiontoglobalvariablesdoesslowdowntheprogrambecauseofthecostofextradereferences.Ontheotherhand,thisperformancehitiscontrollablesincewecancontrolhowmanyusesofglobalvariablesarereplacedbytheirpointercounterparts.

4.1Choosingcorruptionsites

Aswehaveexplained,globalpointervariablesarethetargetstocorruptinoursystem.Theremainingquestioniswheretocorruptthosepointers?Sincewecouldcorruptaglobalpointeranywhereintheprogram,thesearchspaceisthewholeprogram.

Tomakeoursearchalgorithmscalableforlargeprograms,weusefunctionsasthebasicsearchunitsinsteadof,say,statements.Basedonthis,westatethesearchingproblemmorerigorously.Corruptionofglobalpointervariablescanhappeninsideanyfunctionbody;thusafunctionbodyisapossiblecorruptionsite.Afailuresiteisafunctionwheretheprogramfailswhentheprogramreachesthefunctionafterpointercorruption.Inoursetting,failuresitescorrespondtothoseplaceswherecorruptedpointersaredereferenced.Tofindgoodcorruptionsites,wewanttosearchforfunctionstoembedpointercorruptions,toachievewidespatialandtemporalseparationbetweencorruptionandfailure.

First,weshouldmakesurethefunctionwherecorruptionhappensisnotinthecurrentcallstackwhentheprogramfails.Otherwise,attackercoulduseadebuggertoback-tracefromthefailuresitetothecorruptionsite.Toavoidsuchattacks,weuseastatic-analysistoolcalledcallgraphs.Belowisanexampleprogramanditscallgraph.

inta;

int*p_a=&a;voidg1();voidg2();voidh();voidf(){g1();g2();*p_a=3;}

voidmain(){f();h();}

mainfg1g2hIntheexample,themainfunctioncallstheffunction;thusthereisadirectededgefrommaintofinitscallgraph.Similarly,sincefcallsg1andg2,thecallgraphhasthedirectededgesfromftog1,andfromftog2.

Intheexampleprogram,supposeoursystemdecidestocorruptthepointervariablepa.Thenthefunctionfisafailuresitesinceitdereferencespa.Obvi-ously,thecorruptionshouldnothappeninsidefbecauseotherwisetheprogramwouldfailinthefunctionwherethecorruptionhappened.Furthermore,themainfunctionshouldnotbethecorruptionsitesinceotherwisethemainfunctionwouldbeinthecurrentcallstackwhentheprogramfailsinthefunctionf.Ingeneral,oursystemexcludesallfunctionswherethecorruptedpointervariableisdereferenced;furthermore,itexcludesallfunctionswhointhecallgraphareancestorsofthosefunctionswherefailurecanhappen.Thisheuristicguaranteesthatwhentheprogramfailsthecorruptionsiteisnotinthecallstack.

Additionally,wewanttoachievewidespatialandtemporalseparationbe-tweencorruptionandfailure.Wefirstpresentsomeexperimentalnumbers,whichshowthespectrumofspatialandtemporalseparation.Weconductedtheexper-imentonaCprogramcalledWinboard.Wepicked800functionsinWinboard,plantedthecorruptionofaselectedpointervariableintoeachfunction,andrecordedthetemporalandspatialseparationbetweencorruptionandfailure.Figure3showsthetemporalseparation,andFigure4showsthespatialsepara-tion.Inbothfigures,thehorizontalaxisisthefunctionIDwherethecorruptionhappens.InFigure3,theverticalaxisistheelapsingtimebetweencorruptionandfailureinmicroseconds.IntheFigure4,theverticalaxisisthenumberoffunctioncallshappenedbetweencorruptionandfailure.

Aswecanseefromthefigures,thespreadisoverseveralordersofmagnitude.Thefunctionsintheupperportionaretheoneswewanttosearchfor.However,astaticheuristicmaybehardtosucceedbecauseessentiallyanestimateoftimebetweentwofunctioncallsisneeded;wearenotawareofanystatic-analysistechniquesthatcangiveusthisinformation.

Oursolutionistomeasuretheaveragedistancebetweentwofunctioncallsinadynamicfunction-callandtimetrace.Thisinformationestimateshowfarafunctionisfromthenearestfailuresites(functionsthatdereferencesthepointer)intermsofboththenumberoffunctioncallsandtime.Onlyfunctionsthatarefarfromfailuresiteswillbeselectedascorruptionsites.Weexperimentedthis

Fig.3.Temporalseparationbetweencorruptionandfailure.Thehorizontalaxisrepre-sentsfunctionIDs,andtheverticalaxisrepresentstheelapsingtimebetweencorruptionandfailureinmicroseconds.

heuristicontheWinboardprogramandtheresultsshowedthatthosefunctionsintheupperportionofFigure3and4aremostlikelytobeselected.Theshortcomingofthisapproachisthatitdependsondynamictraces,whichmaybecorrelatedtouserinputsandotherrandomevents.

Tomakeitmoreprecise,weoutlineouralgorithmforselectinggoodcorrup-tionsitesinFigure5.Forasimplepresentation,thealgorithmprocessesasingleCfile,calledexample.c(Ourimplementationcanprocessmultiplefilesatonce).

Thealgorithmtakesthreeinputs.Thefirstisthesourcefile.Thesecondisafunction-distancematrixT,whichtellsdistancesbetweenfunctions.ThevalueT[f1,f2]isthedistancebetweenfunctionsf1andf2.Inoursystem,thematrixiscomputedfromatypicaldynamictraceoftheprogram.Thelastinputisathresholdparameterδtodictatetheminimaldistancebetweencorruptionsitesandfailuresites.

Foreachglobalvariablegi,thealgorithmfirstidentifiesthosefunctionsthatusethevalueofgi(line4).Afunctionfinthissetisafailuresiteforgi,becauseifwehadcreatedanindirectpointertogi,saypgi,andreplacedtheuseofgiinfby∗(pgi),thentheprogramwouldfailinsidefafterpgihadbeencorrupted.Thealgorithmthenproceedstoruleoutallfunctionsthatareancestorsofthefailuresitesinthecallgraph(line6),sothatwhenprogramfails,thefunctionwherecorruptionhappenswillnotbeinthecallstack.Finally,thealgorithmrulesoutthosefunctionsthataretooclosetofailuresites(line8and9).

Fig.4.Spatialseparationbetweencorruptionandfailure.Thehorizontalaxisrepre-sentsfunctionIDs,andtheverticalaxisrepresentsthenumberoffunctioncallsbetweencorruptionandfailure.

5Implementationandevaluation

Wehavebuiltaprototypesystem,whichtakesCprogramsasinputsandauto-maticallyinsertstamper-responsecode.Thesystemidentifiesgoodglobalvari-ablesastargetvariablestocorruptwhentamperingisdetected;italsoselectsgoodcorruptionsitesaccordingtotheheuristicsweexplainedinsection4.

TheflowofourimplementedsystemisdepictedinFigure6.Inthefigureandalsointhefollowingparagraphs,weusetheWinboardprogramastheexampleapplicationtoexplainoursystem.WinboardisachessprogramwritteninC.Ithastotally27,000linesofCcode,andcontains297globalvariables,whicharepotentialtargetvariablestocorrupt.

WinboardconsistsofabunchofCfiles:winboard.c,backend.c,etc.Inoursystem,thesefilesarefirstfedintoavarusagemodule.Foreachsourcefile,thevarusagemoduleproducesa.usefile,whichidentifiesplacesthatglobalvariablesareused.Separate.usefilesarelinkedbytheuselinkmoduletoproducetheglobal.usefile.SourceCfilesarealsofedintothecallgraphmodule,whichproduces.cgfiles,orcallgraphfiles.Separate.cgfilesarelinkedtogetherbythecglinktoproduceaglobalcallgraph.

Wealsorunprofilingtoolsontheprogramtoproduceadynamictrace.Thetracerecordstheorderofenteringandexitingfunctionsandalsothecorrespond-ingtimestamps.Thistraceistheinputtothetrmatrixmodule.Themodule

Input:a)example.c,withglobalvariablesg1,g2,...,gn;

b)Function-distancematrixT;

c)δ:Thresholdforthedistancebetweencorruptionandfailuresites.

Output:ThesetofgoodcorruptionsitesCi,foreachgi.

1:ComputethecallgraphGofexample.c2:foreachglobalvariablegi,1≤i≤ndo3:Ci←thesetofallfunctionsinexample.c4:Identifythesetoffunctionswherethevalueofgiisused,say{fi1,...,fim}5:foreachfij,1≤j≤mdo6:RemovefromCialltheancestorsoffijinthecallgraphG.7:foreachfremaininginCido8:ifT[f,fij]<δthen9:removeffromCi10:endif11:endfor12:endfor13:OutputCifortheglobalvariablegi14:endfor

Fig.5.Algorithmforselectinggoodcorruptionsites

measurestheaveragedistancebetweentwofunctionsintermsofbothelapsingtimeandthenumberoffunctioncalls,recordstheinformationintoamatrix,andwritesthematrixintoa.trfile.

Atthispoint,wehavewinboard.use(recordingwhereglobalvariablesareused),winboard.cg(theglobalcallgraph),andwinboard.tr(thetracematrix).Thesefilesareinputstothedelayedfailuremodule.Themodulefirstcomputesthesetofgoodcorruptionsitesforeachglobalvariable,followingthealgorithminFigure5,andthenrandomlyselectssomeglobalvariablesandgoodcorruptionsites.Finally,thecorruptmoduleperformssource-to-sourcetransformationtofirstcreatealayerofindirectiontoselectedglobalvariables,andthenplantthecorruptionofthenewly-createdpointersintoselectedcorruptionsites(ontheconditionthattamperingisdetected).5.1

Systemevaluation/threatanalysis

Overall,oursystemprotectssoftwarebymakingthemexhibittheeffectofde-layedfailureaftertamperingisdetected.Toremoveourtamper-responsecode,theattackerhastotracebackfromthecrashsitetoanalyzewhatiscorruptedandwherethecorruptionhappens.Sincewecorruptpointervariables,theat-tackeressentiallyhastodebugprogramswithelusivepointer-relatedbugs,whichmanyprogrammersknowcanbeextremelyhard;thesituationisactuallyworsefortheattacker,becausehehasnosourcecode.Next,weevaluateoursysteminmoredetailintermsoftheprincipleswelaidoutinsection3.1.

Spatialseparation.Oursystemcanguaranteewidespatialseparationbe-tweenthecorruptionsiteandthefailuresite.Weachievedtheseparation

winboard.cbackend.c...varusage.usevarusage.usecallgraph.cgcallgraph.cga typicaltracetrmatrixwinboard.truselinkwinboard.usecglinkwinboard.cgdelayedfailureselected vars & functionswinboard.c,backend.c, ...corruptwinboard.exeFig.6.SystemImplementation.

ontheorderof104functionscallsinourexperiment.Withthehelpofcallgraphs,itcanfurtherguaranteethatthecorruptionsitewillnotbeinthecallstackwhenfailurehappens.

Temporalseparation.Usingthedynamic-traceapproach,weachievedsec-ondsofdelayinourexperiment,whichismuchbetterthanimmediatefail-ure.Furtherdelaycanbeachievedwiththefollowingtechniques.First,ourexperimentswereconductedbysettingthepointervariabletoNULL.Oursystemcanbeeasilyconfiguredsothatpointercorruptionmeansaddingrandomoffsetstothepointer.Inthiscase,thecumulativeeffectofseveralconsecutivecorruptionswillmostlikelycrashtheprogram,andthedelaywillbeboostedbythistechnique.Second,sincewewantedautomatictestinginourexperiment,weavoidedthosefunctionswhichneedhumaninteractiontoinvoke,e.g.,thefunctionsthatwillbeinvokedonlyifcertainbuttonsareclicked.User-behaviormodelscaninformusofthosefunctionsthatarecalledoccasionally.Forexample,ifweknowthatacertainfunctioniscalledonlyonceinanhour,thenwecanplantthecorruptionintothatfunctiontoachievelongdelay.

Stealth.Sinceourresponsesystemonlymanipulatespointers,itshouldbe

fairlystealthyinprogramsthathavelotsofpointermanipulations.Forpro-gramsinwhichpointersarescarce,onepossibleattackforanadversaryistotrackthepointersofaprogramdynamically,identifytheinstructionsthatmakepointersnonsensical,andthenremovethoseinstructions.

Tocounterthisattack,oursystemshouldbecombinedwithvarioustypesofobfuscationandintegritychecks.Forexample,dynamiccomputationofglobal-variablepointers,includingtechniquessuchastemporarypointercor-ruptionandruntimerelocationofglobaldata,shouldcomplicateattacksthattrackpointerusageviabreakpointsortraces.Wealsoembedmulti-plepointercorruptions,sothatevenonehasbeenremoved,otherscanstillwork.Finally,weareexperimentingwiththeideaofcorruptingdatastruc-turesthroughpointers.Inthesekindsofcorruption,pointervaluesalwaysstaymeaningful;onlycertaininvariantsofthedatastructurearedestroyed.Predictability.Ourresponsesystemispredictableandcontrollable.Pointer

dereferencesafteritscorruptionwillsurelyfailtheprogram.Anydereferencebecomesafailuresiteandwecancontrolwherefailurehappens.

6Extensions

Safelanguages.Insafe,stronglytypedlanguagessuchasC#andJava,pointersandglobalvariablesmaybeeitherunavailableorlimitedtoatypicalusage.Whileourpointer-corruptionmethoddoesnothaveanimmediateanalogueinsafecode,variousothertechniquescanachievesimilarresults.Ingeneral,themainideaofseparatingtamperresponsefromdetectionappliesjustaswelltosafelanguagesastoC/C++.

Belowaresomeexamplesofdelayedcorruptionpossibleviaasafelanguage:–Arrayout-of-boundserrors:Setupanarrayindextofallbeyondthearray’slimits.

–Infiniteloops:Changeavariableinaloop-conditiontesttoresultinaninfinite(oratleastverytime-consuming)loop.Suchtechniquesrequireimplicitdata-basedlinksbetweenthecodeatcor-ruptionandfailuresites.WhileglobalvariablesinC/C++servetocreatesuchconnections,properobject-orienteddesignstipulatesobjectisolationandtightlycontrolleddataflow.Nonetheless,someobjectfields(e.g.,publicstaticmembersinC#)serveessentiallyasglobalvariables.Someapplicationsalsousededicatednamespacesandclassesthatencapsulateglobaldata,whichcanalsosubstitutefortrueglobalvariables.

Toincreasethenumberofopportunitiesfordelayedresponses,wecanper-formvarioussemantically-equivalentcodetransformationsthatbreakobjectiso-lation,similartohowwecreateglobalpointervariables.Asanexample,wecanconvertaconstantloopendpointorAPI-functionargumenttoapublicstatic

variablethatcanbemodifiedtoeffectatamperresponse.Ifagoodresponselocationcontainsnosuitablecode,wecaninjectnewcodethatreferencessuchvariables(e.g.,anewlooporsystem-APIcall).Randomlygeneratedandtightlyintegrated,suchcodeshouldhavenooperationaleffectsiftamperingisnotde-tected.

Gracefuldegradation.Someoftheabovetechniquesdonotcausefailuresaspredictablyaspointercorruption.However,gracefuldegradationcanbemorestealthyanddifficulttoanalyzethandefinitefailures.Anyparticularresponsemightnotterminatetheprogram,butifoneormorecheckscontinuetofail,thecumulativeeffectshouldeventuallymaketheprogramunusable.Boththechecksandresponsescanalsobemadeprobabilisticintermsofspatial/temporalseparationandresponseaction.

Aprogramruncoulddegradeitsfunctioningviaslowdown,highresourceusage,andarbitraryincorrectoperation(e.g.,filecorruptionorgraphicsdis-tortion).Suchtechniquesmaybegenericandautomated;forexample,wecantransformprogramloopstoincludeconditionsthattakeincreasinglylongertimetosatisfy(e.g.,viagraduallyincrementedcounters).Whileapplication-specifictechniquesrequiremanualdesignandimplementation,thesecouldbequiteef-fective(e.g.,agamewheretheplayer’smovementsandaimbecomeincreasinglyerratic[16]).

7Conclusions

Atamper-resistantsystemconsistsoftamperdetectionandtamperresponse.In-adequatetamperresponsecanbecometheweakestlinkofthewholesystem.Inthispaper,wehaveproposedatamper-responsemechanismthatevadeshackerremovalbyintroducingdelayedandcontrolledfailures,accomplishedbycorrupt-ingtheprogram’sinternalstateatwell-chosenlocations.

Acknowledgment

WethankStephenAdamsandManuvirDasforprovidingsomestatic-analysistools,andMatthewCaryforhelpfulconversations.

References

1.BusinessSoftwareAllianceandInternationalDataCorporation.AnnualBSAandIDCglobalsoftwarepiracystudy.http://www.bsa.org/globalstudy,2004-2006.2.DavidAucsmith.Tamperresistantsoftware:Animplementation.InFirstInfor-mationHidingWorkshop,pages317–333,1996.

3.BoazBarak,OdedGoldreich,RussellImpagliazzo,StevenRudich,AmitSahai,SalilVadhan,andKeYang.Onthe(im)possibilityofobfuscatingprograms.Ad-vancesinCryptology-CRYPTO’01,LectureNotesinComputerScience,2139:1–18,2001.

4.PavolCerven.CrackproofYourSoftware.NoStarchPress,Inc.,2002.

5.HoiChangandMikhailJ.Atallah.Protectingsoftwarecodebyguards.InDigitalRightsManagementWorkshop,pages160–175,2001.

6.YuqunChen,PaulEngland,MarcusPeinado,andBryanWillman.Highassurancecomputingonopenhardwarearchitectures.ResearchReportMSR-TR-2003-20,MicrosoftResearch,MicrosoftCorporation,Redmond,Washington,USA,March2003.

7.YuqunChen,RamarathnamVenkatesan,MatthewCary,RuomingPang,SaurabhSinha,andMariuszH.Jakubowski.Oblivioushashing:Astealthysoftwareintegrityverificationprimitive.InInformationHidingWorkshop,pages400–414,2002.8.StanleyChow,YuanGu,HaroldJohnson,andVladimirA.Zakharov.Anapproachtotheobfuscationofcontrol-flowofsequentialcomputerprograms.InInformationSecurity,4thInternationalConference,pages144–155,2001.

9.ChristianCollberg,ClarkThomborson,andDouglasLow.Ataxonomyofobfus-catingtransformations.TechnicalReport148,DepartmentofComputerScience,UniversityofAuckland,July1997.

10.ChristianS.CollbergandClarkD.Thomborson.Watermarking,tamper-proofing,

andobfuscation-toolsforsoftwareprotection.IEEETrans.SoftwareEng.,28(8):735–746,2002.

11.ChristianS.Collberg,ClarkD.Thomborson,andDouglasLow.Manufacturing

cheap,resilient,andstealthyopaqueconstructs.InACMSymposiumonPrinciplesofProgrammingLanguages(POPL),pages184–196,1998.

12.OdedGoldreichandRafailOstrovsky.Softwareprotectionandsimulationonobliv-iousRAMs.JournaloftheACM,43(3):431–473,1996.

13.BillHorne,LesleyR.Matheson,CaseySheehan,andRobertEndreTarjan.Dy-namicself-checkingtechniquesforimprovedtamperresistance.InDigitalRightsManagementWorkshop,pages141–159,2001.14.http://cdfreaks.com,2006.

15.BenjaminLynn,ManojPrabhakaran,andAmitSahai.Positiveresultsandtech-niquesforobfuscation.InEUROCRYPT2004,pages20–39,2004.16.Macrovision.FADE,SafeDiscandSafeDVDcopyprotection,2002.

17.MarcusPeinado,YuqunChen,PaulEngland,andJohnManferdelli.NGSCB:A

trustedopensystem.InHuaxiongWang,JosefPieprzyk,andVijayVaradharajan,editors,ACISP,volume3108ofLectureNotesinComputerScience,pages86–97.Springer,2004.

18.I.C.Pyle,R.C.F.McLatchie,andB.Grandage.Asecond-orderbugwithdelayed

effect.Software–PracticeandExperience,1(3):231–233,1971.

19.ChenxiWang,JonathanHill,JohnKnight,andJackDavidson.Softwaretamper

resistance:Obstructingstaticanalysisofprograms.TechnicalReportCS-2000-12,UniversityofVirginia,December2000.

20.HoeteckWee.Onobfuscatingpointfunctions.CryptologyePrintArchive,Report

2005/001,2005.http://eprint.iacr.org/.