cerpunkbuster

AccountableVirtualMachinesAndreasHaeberlenPaarijaatAdityaRodrigoRodriguesPeterDruschelUniversityofPennsylvaniaMaxPlanckInstituteforSoftwareSystems(MPI-SWS)AbstractInthispaper,weintroduceaccountablevirtualma-chines(AVMs).
Likeordinaryvirtualmachines,AVMscanexecutebinarysoftwareimagesinavirtualizedcopyofacomputersystem;inaddition,theycanrecordnon-repudiableinformationthatallowsauditorstosub-sequentlycheckwhetherthesoftwarebehavedasin-tended.
AVMsprovidestrongaccountability,whichisimportant,forinstance,indistributedsystemswheredif-ferenthostsandorganizationsdonotnecessarilytrusteachother,orwheresoftwareishostedonthird-partyoperatedplatforms.
AVMscanprovideaccountabilityforunmodiedbinaryimagesanddonotrequiretrustedhardware.
TodemonstratethatAVMsarepractical,wehavedesignedandimplementedaprototypeAVMmon-itorbasedonVMwareWorkstation,andusedittodetectseveralexistingcheatsinCounterstrike,apopularonlinemulti-playergame.
1IntroductionAnaccountablevirtualmachine(AVM)providesuserswiththecapabilitytoaudittheexecutionofasoftwaresystembyobtainingalogoftheexecution,andcompar-ingittoaknown-goodexecution.
Thiscapabilityispar-ticularlyusefulwhenusersrelyonsoftwareandservicesrunningonmachinesownedoroperatedbythirdpar-ties.
AuditingworksforanybinaryimagethatexecutesinsidetheAVManddoesnotrequirethattheusertrusteitherthehardwareortheaccountablevirtualmachinemonitoronwhichtheimageexecutes.
SeveralclassesofsystemsexemplifyscenarioswhereAVMsareuseful:inacompetitivesystem,suchasanonlinegameoranauction,usersmaywishtoverifythatotherplayersdonotcheat,andthattheprovideroftheserviceimplementsthestatedrulesfaithfully;nodesinpeer-to-peerandfederatedsystemsmaywishtoverifythatothersfollowtheprotocolandcontributetheirfairshareofresources;cloudcomputingcustomersmaywishtoverifythattheproviderexecutestheircodeasintended.
Inthesescenarios,softwareandhardwarefaults,mis-congurations,break-ins,anddeliberatemanipulationcanleadtoanabnormalexecution,whichcanbecostlytousersandoperators,andmaybedifculttodetect.
Whensuchamalfunctionoccurs,itisdifculttoestab-lishwhoisresponsiblefortheproblem,andevenmorechallengingtoproduceevidencethatprovesaparty'sinnocenceorguilt.
Forexample,inacloudcomputingenvironment,failurescanbecausedbothbybugsinthecustomer'ssoftwareandbyfaultsormiscongurationoftheprovider'splatform.
Ifthefailurewastheresultofabug,theproviderwouldliketobeabletoprovehisowninnocence,andiftheproviderwasatfault,thecustomerwouldliketoobtainproofofthatfact.
AVMsaddresstheseproblemsbyprovidinguserswiththecapabilitytodetectfaults,toidentifythefaultynode,andtoproduceevidencethatconnectsthefaulttothemachinethatcausedit.
Thesepropertiesareachievedbyrunningsystemsinsideavirtualmachinethat1)maintainsalogwithenoughinformationtore-producetheentireexecutionofthesystem,andthat2)associateseachoutgoingmessagewithacryptographicrecordthatlinksthatactiontothelogoftheexecutionthatproducedit.
Thelogenablesuserstodetectfaultsbyreplayingsegmentsoftheexecutionusingaknown-goodcopyofthesystem,andbycross-checkingtheex-ternallyvisiblebehaviorofthatcopywiththepreviouslyobservedbehavior.
AVMscanprovidethiscapabilityforanyblack-boxbinaryimagethatcanberuninsideaVM.
AVMsdetectintegrityviolationsofanexecutionwithoutrequiringtheauditedmachinetorunhardwareorsoftwarecomponentsthataretrustedbytheauditor.
Whensuchtrustedcomponentsareavailable,AVMscanbeextendedtodetectsomecondentialityviolationsaswell,suchasprivatedataleakingoutoftheAVM.
Thispapermakesthreecontributions:1)itintroducestheconceptofAVMs,2)itpresentsthedesignofanaccountablevirtualmachinemonitor(AVMM),and3)itdemonstratesthatAVMsarepracticalforaspecicapplication,namelythedetectionofcheatinginmulti-playergames.
Cheatdetectionisaninterestingexampleapplicationbecauseitisaseriousandwell-understoodproblemforwhichAVMsareeffective:theycandetect1alargeandgeneralclassofcheats.
Outof26existingcheatswedownloadedfromtheInternet,AVMscande-tecteverysingleone—withoutpriorknowledgeofthecheat'snatureorimplementation.
WehavebuiltaprototypeAVMMbasedonVMwareWorkstation,andusedittodetectrealcheatsinCoun-terstrike,apopularmulti-playergame.
Ourevaluationshowsthatthecostsofaccountabilityinthiscontextaremoderate:theframeratedropsby13%,from158fpsonbarehardwareto137fpsonourprototype,thepingtimeincreasesbyabout5ms,andeachplayermuststoreortransmitalogthatgrowsbyabout148MBperhouraf-tercompression.
Mostofthisoverheadiscausedbylog-gingtheexecution;theadditionalcostforaccountabil-ityiscomparativelysmall.
Thelogcanbetransferredtootherplayersandreplayedthereduringthegame(on-line)orafterthegamehasnished(ofine).
Whileourevaluationinthispaperfocusesongamesasanexampleapplication,AVMsareusefulinothercontexts,e.
g.
,inp2pandfederatedsystems,ortoverifythatacloudplatformisprovidingitsservicescorrectlyandisallocatingthepromisedresources[18].
Ourpro-totypeAVMMalreadysupportstechniquessuchaspar-tialauditsthatwouldbeusefulforsuchapplications,butafullevaluationisbeyondthescopeofthispaper.
Therestofthispaperisstructuredasfollows.
Sec-tion2discussesrelatedwork,Section3explainstheAVMapproach,andSection4presentsthedesignofourprototypeAVMM.
Sections5and6describeourimple-mentationandreportevaluationresultsinthecontextofgames.
Section7describesotherapplicationsandpos-sibleextensions,andSection8concludesthispaper.
2RelatedworkDeterministicreplay:OurprototypeAVMMreliesontheabilitytoreplaytheexecutionofavirtualmachine.
Replaytechniqueshavebeenstudiedformorethantwodecades,usuallyinthecontextofdebugging,andma-turesolutionsareavailable[6,15,16,39].
However,replaybyitselfisnotsufcienttodetectfaultsonare-motemachine,sincethemachinecouldrecordincorrectinformationinsuchawaythatthereplaylookscorrect,orprovideinconsistentinformationtodifferentauditors.
Improvingtheefciencyofreplayisanactivere-searcharea.
Remus[11]contributesahighlyefcientsnapshottingmechanism,andmanycurrenteffortsseektoimprovetheefciencyofloggingandreplayformulti-coresystems[13,16,28,29].
AVMMscandi-rectlybenetfromtheseinnovations.
Accountability:Accountabilityindistributedsystemshasbeensuggestedasameanstoachievepracticalse-curity[26],tocreateanincentiveforcooperativebe-havior[14],tofosterinnovationandcompetitionintheInternet[4,27],andevenasageneraldesigngoalfordependablenetworkedsystems[43].
Severalpriorsys-temsprovideaccountabilityforspecicapplications,in-cludingnetworkstorageservices[44],peer-to-peercon-tentdistributionnetworks[31],andinterdomainrout-ing[2,20].
Unlikethesesystems,AVMsareapplicationindependent.
PeerReview[21]providesaccountabilityforgeneraldistributedsystems.
However,PeerReviewmustbecloselyintegratedwiththeapplication,whichrequiressourcecodemodicationsandadetailedunder-standingoftheapplicationlogic.
Itwouldbeimpracti-caltoapplyPeerReviewtoanentireVMimagewithdozensofapplicationsandwithoutaccesstothesourcecodeofeach.
AVMsdonothavetheselimitations;theycanmakesoftwareaccountable'outofthebox'.
Remotefaultdetection:GridCop[42]isacompiler-basedtechniquethatcanbeusedtomonitortheprogressandexecutionofaremotelyexecutingprogrambyin-spectingperiodicbeaconpackets.
GridCopisdesignedforalesshostileenvironmentthanAVMs:itassumesatrustedplatformandself-interestedhosts.
Also,Grid-Copdoesnotworkforunmodiedbinaries,anditcan-notproduceevidencethatwouldconvinceathirdpartythatafaultdidordidnothappen.
Atrustedcomputingplatformcanbeusedtodetectifanodeisrunningmodiedsoftware[17,30].
Theap-proachrequirestrustedhardware,atrustedOSkernel,andasoftwareandhardwarecerticationinfrastructure.
Pioneer[36]candetectsuchmodicationsusingonlysoftware,butitreliesonrecognizingsub-milliseconddelayvariations,whichrestrictsitsusetosmallnet-works.
AVMsdonotrequireanytrustedhardwareandcanbeusedinwide-areanetworks.
Cheatdetection:Cheatinginonlinegamesisanimpor-tantproblemthataffectsgameplayersandgameoper-atorsalike[24].
Severalcheatdetectiontechniquesareavailable,suchasscanningforknownhacks[23,35]ordefensesagainstspecicformsofcheating[7,32].
Incontrasttothese,AVMsaregeneric;thatis,theyareef-fectiveagainstanentireclassofcheats.
Chambersetal.
[9]describeanothertechniquetodetectifplayerslieabouttheirgamestate.
Thesystemreliesonaformoftamper-evidentlogs;however,thelogmustbeinte-gratedwiththegame,whileAVMsworkforunmodiedgames.
3AccountableVirtualMachines3.
1GoalsFigure1depictsthebasicscenarioweareconcernedwithinthispaper.
AliceisrelyingonBobtorunsomesoftwareSonamachineM,whichisunderBob'scon-trol.
However,AlicecannotobserveMdirectly,shecanonlycommunicatewithitoverthenetwork.
OurgoalistoenableAlicetocheckwhetherMbehavesasex-2NetworkAliceBobSoftwareSMachineMFigure1:Basicscenario.
AliceisrelyingonsoftwareS,whichisrunningonamachinethatisunderBob'scontrol.
Alicewouldliketoverifythatthemachineisworkingproperly,andthatBobhasnotmodiedS.
pected,withouthavingtotrustBob,M,oranysoftwarerunningonM.
TodenethebehaviorAliceexpectsMtohave,weassumethatAlicehassomereferenceimplementationofMcalledMR,whichrunsS.
WesaythatMiscorrectiffMRcanproducethesamenetworkoutputasMwhenitisstartedinthesameinitialstateandgivenpreciselythesamenetworkinputs.
IfMisnotcorrect,wesaythatitisfaulty.
ThiscanhappenifMdiffersfromMR,orBobhasinstalledsoftwareotherthanS.
Ourgoalistoprovidethefollowingproperties:Detection:IfMisfaulty,Alicecandetectthis.
Evidence:WhenAlicedetectsafaultonM,shecanobtainevidencethatwouldconvinceathirdpartythatMisfaulty,withoutrequiringthatthispartytrustAliceorBob.
WeareparticularlyinterestedinsolutionsthatworkforanysoftwareSthatcanexecuteonMandMR.
Forexample,Scouldbeaprogrambinarythatwascom-piledbysomeoneotherthanAlice,itcouldbeacomplexapplicationwhosedetailsneitherAlicenorBobunder-stand,oritcouldbeanentireoperatingsystemimagerunningacommodityOSlikeLinuxorWindows.
Intherestofthispaper,wewillomitexplicitrefer-encestoSwhenitisclearfromthecontextwhichsoft-wareMisexpectedtorun.
3.
2ApproachTodetectfaultsonM,Alicemustbeabletoanswertwoquestions:1)whichexactsequenceofnetworkmes-sagesdidMsendandreceive,and2)isthereacorrectexecutionofMRthatisconsistentwiththissequenceofmessagesAnsweringtheformerisnottrivialbecauseafaultyM—oramaliciousBob—couldtrytofalsifytheanswer.
Answeringthelatterisdifcultbecausethenumberofpossibleexecutionsforanynontrivialsoft-wareislarge.
Alicecansolvethisproblembycombiningtwoseem-inglyunrelatedtechnologies:tamper-evidentlogsandvirtualmachines.
Atamper-evidentlog[21]requireseachnodetorecordallthemessagesithassentorre-ceived.
Wheneveramessageistransmitted,thesenderandthereceivermustprovetoeachotherthattheyhaveaddedthemessagetotheirlogs,andtheymustcommittothecontentsoftheirlogsbyexchanginganauthenti-cator–essentially,asignedhashofthelog.
Theauthen-ticatorsprovidenonrepudiation,andtheycanbeusedtodetectwhenanodetamperswithitslog,e.
g.
,byforging,omitting,ormodifyingmessages,orbyforkingthelog.
OnceAlicehasdeterminedthatM'smessagelogisgenuine,shemusteitherndacorrectexecutionofMRthatmatchesthislog,orestablishthatthereisn'tone.
TohelpAlicewiththistask,McanberequiredtorecordadditionalinformationaboutnondeterministiceventsintheexecutionofS.
Giventhisinformation,Alicecanusedeterministicreplay[8,15]tondthecorrectexe-cutiononMR,providedthatoneexists.
RecordingtherelevantnondeterministiceventsseemsdifcultatrstbecausewehaveassumedthatneitherAlicenorBobhavetheexpertisetomakemodicationstoS;however,Bobcanavoidthisbyusingavirtualmachinemonitor(VMM)tomonitortheexecutionofSandtocaptureinputsandnondeterministiceventsinageneric,application-independentway.
3.
3AVMmonitorsTheabovebuildingblockscanbecombinedtocon-structanaccountablevirtualmachinemonitor(AVMM),whichimplementsAVMs.
AliceandBobcanuseanAVMMtoachievethegoalsfromSection3.
1asfollows:1.
BobinstallsanAVMMonhiscomputerandrunsthesoftwareSinsideanAVM.
(Fromthispointforward,MreferstotheentirestackconsistingofBob'scomputer,theAVMMrunningonBob'scomputer,andAlice'svirtualmachineimageS,whichrunsontheAVMM.
)2.
TheAVMMmaintainsatamper-evidentlogofthemessagesMsendsorreceives,anditalsorecordsanynondeterministiceventsthataffectS.
3.
WhenAlicereceivesamessagefromM,shede-tachestheauthenticatorandsavesitforlater.
4.
AliceperiodicallyauditsMasfollows:sheaskstheAVMMforitslog,veriesitagainsttheau-thenticatorsshehascollected,andthenusesdeter-ministicreplaytocheckthelogforfaults.
5.
Ifreplayfailsorthelogcannotbeveriedagainstoneoftheauthenticators,AlicecangiveMR,S,thelog,andtheauthenticatorstoathirdparty,whocanrepeatAlice'schecksandindependentlyverifythatafaulthasoccurred.
Thisgenericmethodologymeetsourpreviouslystatedgoals:AlicecandetectfaultsonM,shecanobtainevi-dence,andathirdpartycanchecktheevidencewithouthavingtotrusteitherAliceorBob.
3AliceBobCharlieSASBSCAliceBobUsersSoftwareS(a)Symmetricmulti-partyscenario(onlinegame)(b)Asymmetricmulti-partyscenario(webservice)Figure2:Multi-partyscenarios.
Thescenarioontheleftrepresentsamulti-playergame;eachplayerisrunningthegameclientonhislocalmachineandwantstoknowwhetheranyotherplayersarecheating.
Thescenarioontherightrepresentsahostedwebservice:Alice'ssoftwareisrunningonBob'smachine,butthesoftwaretypicallyinteractswithusersotherthanAlice,suchasAlice'scustomers.
3.
4DoestheAVMMhavetobetrustedAperhapssurprisingconsequenceofthisapproachisthattheAVMMdoesnothavetobetrustedbyAlice.
SupposeBobismaliciousandsecretlytamperswithAl-ice'ssoftwareand/ortheAVMM,causingMtobecomefaulty.
BobcannotpreventAlicefromdetectingthis:ifhetamperswithM'slog,Alicecantellbecausethelogwillnotmatchtheauthenticators;ifhedoesnot,AliceobtainstheexactsequenceofobservablemessagesMhassentandreceived,andsincebyourdenitionofafaultthereisnocorrectexecutionofMRthatisconsis-tentwiththissequence,deterministicreplayinevitablyfails,nomatterwhattheAVMMrecorded.
3.
5MustAlicechecktheentirelogFormanyapplications,includingthegameweconsiderinthispaper,itisperfectlyfeasibleforAlicetoauditM'sentirelog.
However,forlong-running,compute-intensiveapplications,Alicemaywanttosavetimebydoingspotchecksonafewlogsegmentsinstead.
TheAVMMcanenablehertodothisbyperiodicallytakingasnapshotoftheAVM'sstate.
Thus,Alicecaninde-pendentlyinspectanysegmentthatbeginsandendsatasnapshot.
Spotcheckingsacricesthecompletenessoffaultde-tectionforefciency.
IfAlicechoosestodospotchecks,shecanonlydetectfaultsthatmanifestasincorrectstatetransitionsinthesegmentssheinspects.
Anincorrectstatetransitioninanuncheckedsegment,ontheotherhand,couldpermanentlymodifyM'sstateinawaythatisnotdetectablebycheckingsubsequentsegments.
Therefore,Alicemustbecarefulwhenchoosinganap-propriatepolicy.
Alicecouldinspectarandomsampleofsegmentsplusanysegmentsinwhichafaultcouldmostlikelyhavealong-termeffectontheAVM'sstate(e.
g.
,duringinitial-ization,authentication,keygeneration).
Or,shecouldinspectsegmentswhensheobservessuspiciousresults,startingwiththemostrecentsegmentandworkingback-wardsinreversechronologicalorder.
Spot-checkingismosteffectiveinapplicationswherethefaultsofinterestlikelyoccurrepeatedlyandasingleinstancecauseslim-itedharm,wheretheapplicationstateisfrequentlyre-initialized(preventinglong-termeffectsofasingleun-detectedfaultonthestate),orwherethethreatofprob-abilisticdetectionisstrongenoughtodeterattackers.
3.
6DoAVMsworkwithmultiplepartiesSofar,wehavefocusedonasimpletwo-partyscenario;however,AVMscanbeusedinmorecomplexscenar-ios.
Figure2showstwoexamples.
Inthescenarioontheleft,theplayersinanonlinemulti-playergameareusingAVMstodetectwhethersomeoneischeating.
Un-likethebasicscenarioinFigure1,thisscenarioissym-metricinthesensethateachplayerisbothrunningsoft-wareandisinterestedinthecorrectnessofthesoftwareonalltheothermachines.
Thus,therolesofauditorandauditeecanbeplayedbydifferentpartiesatdiffer-enttimes.
Thescenarioontherightrepresentsahostedwebservice:thesoftwareiscontrolledandauditedbyAlice,butthesoftwaretypicallyinteractswithpartiesotherthanAlice,suchasAlice'scustomers.
Forclarity,wewillexplainoursystemmostlyintermsofthesimpletwo-partyscenarioinFigure1.
InSection4.
6,wewilldescribedifferencesforthemulti-partycase.
4AVMMdesignTodemonstratethatAVMsarepractical,wenowpresentthedesignofaspecicAVMM.
44.
1AssumptionsOurdesignreliesonthefollowingassumptions:1.
Alltransmittedmessagesareeventuallyreceived,ifretransmittedsufcientlyoften.
2.
Allparties(machinesandusers)haveaccesstoahashfunctionthatispre-imageresistant,secondpre-imageresistant,andcollisionresistant.
3.
Eachpartyhasacertiedkeypair,whichcanbeusedtosignmessages.
Neithersignaturesnorcer-ticatescanbeforged.
4.
Ifauserneedstoauditthelogofamachine,theuserhasaccesstoareferencecopyoftheVMim-agethatthemachineisexpectedtouse.
Thersttwoarecommonassumptionsmadeaboutprac-ticaldistributedsystems.
Inparticular,therstassump-tionisrequiredforliveness,otherwiseitcouldbeim-possibletoevercompleteanaudit.
Thethirdassump-tioncouldbesatisedbyprovidingeachmachinewithakeypairthatissignedbytheadministrator;itisneededtopreventfaultymachinesfromcreatingfakeidentities.
Thefourthassumptionisrequiredsothattheauditorknowswhichbehaviorsarecorrect.
4.
2RoadmapOurdesigninstantiateseachofthebuildingblockswehavedescribedinSection3.
2:aVMM,atamper-evidentlog,andanauditingmechanism.
Here,wegiveabriefoverview;therestofthissectiondescribeseachbuildingblockinmoredetail.
Forthetamper-evidentlog(Section4.
3),weadaptatechniquefromPeerReview[21],whichalreadycomeswithaproofofcorrectness[22].
WeextendthislogtoalsoincludetheVMM'sexecutiontrace.
TheVMMweuseinthisdesign(Section4.
4)virtual-izesastandardcommodityPC.
Thisplatformisattrac-tivebecauseofthevastamountofexistingsoftwarethatcanrunonit;however,forhistoricalreasons,itishardertovirtualizethanamoremodernplatformsuchasJavaor.
NET.
Inaddition,interactionsbetweenthesoftwareandthevirtual'hardware'aremuchmorefrequentthan,e.
g.
,inJava,resultinginapotentiallyhigheroverhead.
Forauditing(Section4.
5),weprovideatoolthatau-thenticatesthelog,thenchecksitfortampering,andnallyusesdeterministicreplaytodeterminewhetherthecontentsofthelogcorrespondtoacorrectexecu-tionofMR.
Ifthetoolndsanydiscrepancybetweentheeventsinthelogandtheeventsthatoccurduringreplay,thisindicatesafault.
Notethat,whileeventssuchasthreadschedulingmayappearnondeterminis-tictoanapplication,theyareinfactdeterministicfromtheVMM'sperspective.
Therefore,aslongasallex-ternalevents(e.
g.
timerinterrupts)arerecordedinthelog,evenraceconditionsarereproducedexactlyduringreplayandcannotresultinfalsepositives.
14.
3Tamper-evidentlogThetamper-evidentlogisstructuredasahashchain;eachlogentryisoftheformei:=(si,ti,ci,hi),wheresiisamonotonicallyincreasingsequencenumber,tiatype,andcidataofthespeciedtype.
hiisahashvaluethatmustbelinkedtoallthepreviousentriesinthelog,andyetefcienttocreate.
Hence,wecomputeitashi=H(hi1||si||ti||H(ci))whereh0:=0,Hisahashfunction,and||standsforconcatenation.
TodetectwhenBob'smachineMforgesincomingmessages,Alicesignseachofhermessageswithherownprivatekey.
TheAVMMlogsthesignaturesto-getherwiththemessages,sothattheycanbeveriedduringanaudit,butitremovesthembeforepassingthemessagesontotheAVM.
Thus,thisprocessistranspar-enttothesoftwarerunninginsidetheAVM.
Toensurenonrepudiation,theAVMMattachesanauthenticatortoeachoutgoingmessagem.
Theau-thenticatorforanentryeiisai:=(si,hi,σ(si||hi)),wheretheσ(·)operatordenotesacryptographicsig-naturewiththemachine'sprivatekey.
Malsoin-cludeshi1,sothatAlicecanrecalculatehi=H(hi1||si||SEND||H(m))andthusverifythattheentryeiisinfactSEND(m).
TodetectwhenMdropsincomingoroutgoingmes-sages,bothAliceandtheAVMMsendanacknowledg-mentforeachmessagemtheyreceive.
Analogoustotheabove,M'sauthenticatorintheacknowledgmentcon-tainsenoughinformationfortherecipienttoverifythatthecorrespondingentryisRECV(m).
Alice'sownac-knowledgmentcontainsjustasignedhashofthecor-respondingmessage,whichtheAVMMlogsforAlice.
Whenanacknowledgmentisnotreceived,theoriginalmessageisretransmittedafewtimes.
IfAlicestopsre-ceivingmessagesfromMaltogether,shecanonlysus-pectthatMhasfailed.
WhenAlicewantstoauditM,sheretrievesapairofauthenticators(e.
g.
,theoneswiththelowestandhighestsequencenumbers)andchallengesMtoproducethelogsegmentthatconnectsthem.
Shethenveriesthatthehashchainisintact.
Becausethehashfunctionissecondpre-imageresistant,itiscomputationallyinfeasibletomodifythelogwithoutbreakingthehashchain.
Thus,ifMhasreorderedortamperedwithalogentryinthatsegment,orifithasforkeditslog,M'shashchainwillnolongermatchitspreviouslyissuedauthenticators,andAlicecandetectthisusingthischeck.
1Ensuringdeterministicreplayonmultiprocessormachinesismoredifcult.
WewilldiscussthisinSection7.
4.
54.
4VirtualmachinemonitorInadditiontorecordingallincomingandoutgoingmes-sagestothetamper-evidentlog,theAVMMlogsenoughinformationabouttheexecutionofthesoftwaretoen-abledeterministicreplay.
Recordingnondeterministicinputs:TheAVMMmustrecordalloftheAVM'snondeterministicinputs[8].
Ifaninputisasynchronous,theprecisetimingwithintheexecutionmustberecorded,sothattheinputcanbere-injectedattheexactsamepointduringreplay.
Hardwareinterrupts,forexample,fallintothiscategory.
Notethatwall-clocktimeisnotsufcientlyprecisetodescribethetimingofsuchinputs,sincetheinstructiontimingcanvaryonmostmodernCPUs.
Instead,theAVMMusesacombinationofinstructionpointer,branchcounter,and,wherenecessary,additionalregisters[15].
Notallinputsarenondeterministic.
Forexample,thevaluesreturnedbyaccessestotheAVM'svirtualhard-diskneednotberecorded.
Aliceknowsthesystemim-agethatthemachineisexpectedtouse,andcanthusreconstructthecorrectinputsduringreplay.
Alsomanyinputssuchassoftwareinterruptsaresynchronous,thatis,theyareexplicitlyrequestedbytheAVM.
Here,thetimingneednotberecordedbecausetherequestswillbeissuedagainduringreplay.
Detectinginconsistencies:Thetamper-evidentlognowcontainstwoparallelstreamsofinformation:Messageexchangesandnondeterministicinputs.
Incomingmes-sagesappearinbothstreams:rstasmessages,andthen,astheAVMreadsthebytesinthemessage,asasequenceofinputs.
IfBobismalicious,hemighttrytoexploitthisbyforgingmessagesorbydroppingormod-ifyingamessagethatwasreceivedonMbeforeitisinjectedintotheAVM.
Todetectthis,theAVMMcross-referencesmessagesandinputsinsuchawaythatanydiscrepanciescaneasilybedetectedduringreplay.
Snapshots:Toenablespotcheckingandincrementalaudits(Section3.
5),theAVMMperiodicallytakesasnapshotoftheAVM'scurrentstate.
Tosavespace,snapshotsareincremental,thatis,theyonlycontainthestatethathaschangedsincethelastsnapshot.
TheAVMMalsomaintainsahashtreeoverthestate;af-tereachsnapshot,itupdatesthetreeandthenrecordsthetop-levelvalueinthelog.
WhenAliceauditsalogsegment,shecaneitherdownloadanentiresnapshotorincrementallyrequestthepartsofthestatethatareac-cessedduringreplay.
Ineithercase,shecanusethehashtreetoauthenticatethestateshehasdownloaded.
TakingfrequentsnapshotsenablesAlicetoperformne-grainaudits,butitalsoincreasestheoverhead.
However,snapshottingtechniqueshavebecomeveryef-cient;recentworkonVMreplicationhasshownthatincrementalsnapshotscanbetakenupto40timespersecond[11]andwithonlybriefinterruptionsoftheVM,ontheorderofafewmilliseconds.
Accountabilityre-quiresonlyinfrequentsnapshots(onceeveryfewmin-utesorhours),sotheoverheadshouldbelow.
4.
5AuditingandreplayWhenAlicewantstoauditamachineM,sheperformsthefollowingthreesteps.
First,AliceobtainsasegmentofM'slogandtheauthenticatorsthatMproduceddur-ingtheexecution,sothatthelog'sintegritycanbever-ied.
Second,shedownloadsasnapshotoftheAVMatthebeginningofthesegment.
Finally,shereplaystheentiresegment,startingfromthesnapshot,tocheckwhethertheeventsinthelogcorrespondtoacorrectex-ecutionofthereferencesoftware.
Verifyingthelog:WhenAlicewantstoauditalogsegmentei.
.
.
ej,sheretrievestheauthenticatorsshehasreceivedfromMwithsequencenumbersin[si,sj].
Next,AlicedownloadsthecorrespondinglogsegmentLijfromM,startingwiththemostrecentsnapshotbe-foreeiandendingatej;thensheveriesthesegmentagainsttheauthenticatorstocheckfortampering.
Ifthisstepsucceeds,Aliceisconvincedthatthelogsegmentisgenuine;thus,sheisleftwithhavingtoestablishthattheexecutiondescribedbythesegmentiscorrect.
IfMisfaulty,AlicemaynotbeabletodownloadLijatall,orMcouldreturnacorruptedlogsegmentthatcausesvericationtofail.
Ineithercase,Alicecanusethemostrecentauthenticatorajasevidencetocon-vinceathirdpartyofthefault.
Sincetheauthenticatorissigned,thethirdpartycanuseajtoverifythatlogentrieswithsequencenumbersuptosjmustexist;thenitcanrepeatAlice'saudit.
Ifnoreplyisobtained,AlicewillsuspectBob.
Verifyingthesnapshot:Next,AlicemustobtainasnapshotoftheAVM'sstateatthebeginningofthelogsegmentLij.
IfAliceisauditingtheentireexecution,shecansimplyusetheoriginalsoftwareimageS.
Oth-erwiseshedownloadsasnapshotfromMandrecom-putesthehashtreetoauthenticateitagainstthehashvalueinLij.
Verifyingtheexecution:Forthenalstep,Aliceneedsthreeinputs:ThelogsegmentLij,theVMsnapshot,andthepublickeysofMandanyuserswhocommuni-catedwithM.
TheaudittoolperformstwochecksonLij,asyntacticcheckandasemanticcheck.
Thesyn-tacticcheckdetermineswhetherthelogitselfiswell-formed,whereasthesemanticcheckdetermineswhethertheinformationinthelogcorrespondstoacorrectexe-cutionofMR.
Forthesyntacticcheck,theaudittoolcheckswhetheralllogentrieshavetheproperformat,veriesthecryp-tographicsignaturesineachmessageandacknowledg-ment,checkswhethereachmessagewasacknowledged,andcheckswhetherthesequenceofsentandreceived6messagescorrespondstothesequenceofmessagesthatenterandexittheAVM.
Ifanyofthesetestsfail,thetoolreportsafault.
Forthesemanticcheck,thetoollocallyinstantiatesavirtualmachinethatimplementsMR,anditinitializesthemachinewiththesnapshot,ifany,orS.
Next,itreadsLijfrombeginningtoend,replayingtheinputs,checkingtheoutputsagainsttheoutputsinLij,andver-ifyinganysnapshothashesinLijagainstsnapshotsofthereplayedexecution(tobesurethatthesnapshotattheendofLijisalsocorrect).
Ifthereisanydiscrep-ancywhatsoever(forexample,ifthevirtualmachineproducesoutputsthatarenotinthelog,orifitrequeststhesynchronousinputsinadifferentorder),replayter-minatesandreportsafault.
Inthiscase,AlicecanuseLijandtheauthenticatorsasevidencetoconvinceBob,oranyotherinterestedparty,thatMisfaulty.
IfthelogsegmentLijpassesalloftheabovechecks,thetoolreportssuccessandthenterminates.
Auditingcanbeperformedofine(aftertheexecutionofagivenlogsegmentisnished)oronline(whiletheexecutionisinprogress).
4.
6Multi-partyscenarioSofar,wehavedescribedtheAVMMintermsofthesimpletwo-partyscenario.
Amulti-partyscenariore-quiresthreechanges.
First,whensomeuserwantstoauditamachineM,heneedstocollectauthenticatorsfromotherusersthatmayhavecommunicatedwithM.
InthegamingscenarioinFigure2(a),Alicecoulddown-loadauthenticatorsfromCharliebeforeauditingBob.
Intheweb-servicescenarioinFigure2(b),theuserscouldforwardanyauthenticatorstheyreceivetoAlice.
Second,withmorethantwoparties,networkprob-lemscouldmakethesamenodeappearunresponsivetosomenodesandalivetoothers.
Bobcouldexploitthis,forinstance,toavoidrespondingtoAlice'srequestforanincriminatinglogsegment,whilecontinuingtoworkwithothernodes.
Topreventthistypeofattack,Al-iceforwardsthemessagethatMdoesnotanswerasachallengeforMtotheothernodes.
Allnodesstopcom-municatingwithMuntilitrespondstothechallenge.
IfMiscorrectbutthereisanetworkproblembetweenMandAlice,orMwastemporarilyunresponsive,itcananswerthechallengeanditsresponseisforwardedtoAlice.
Third,whenoneuserobtainsevidenceofafault,hemayneedtodistributethatevidencetootherinterestedparties.
Forexample,inthegamingscenario,ifAlicedetectsthatBobischeating,shecansendtheevidencetoCharlie,whocanverifyitindependently;thenbothcandecidenevertoplaywithBobagain.
4.
7GuaranteesGivenourassumptionsfromSection4.
1andthefaultdenitionfromSection3.
1,theAVMMoffersthefol-lowingtwoguarantees:Completeness:IfthemachineMisfaulty,afullauditofMwillreportafaultandproduceevidenceagainstMthatcanbeveriedbyathirdparty.
Accuracy:IfthemachineMisnotfaulty,noauditofMwillreportafault,andtherecannotexistanyvalidevidenceagainstM.
IfAliceperformsspotchecksonanumberoflogseg-mentss1,skratherthanafullaudit,accuracystillholds.
However,ifMisfaulty,herauditwillonlyre-portthefaultandproduceevidenceifthereexistsatleastonelogsegmentsiinwhichthefaultmanifests.
TheseguaranteesareindependentofthesoftwareS,andtheyholdforanyfaultthatmanifestsasadeviationfromMR,evenifAlice,Bob,and/orotherusersaremalicious.
Aproofofthesepropertiesispresentedinaseparatetech-nicalreport[19].
Sinceourdesignisbasedonthetamper-evidentlogfromPeerReview[21],theresultingAVMMinheritsapowerfulpropertyfromPeerReview:inadistributedsystemwithmultiplenodes,itispossibletoaudittheexecutionoftheentiresystembyauditingeachnodein-dividually.
Formoredetails,pleasereferto[21].
4.
8LimitationsWenotetwolimitationsimpliedbytheAVMM'sguar-antees.
First,AVMscannotdetectbugsorvulnerabili-tiesinthesoftwareS,becausetheexpectedbehaviorofMisdenedbyMRandthusS.
IfShasabugandthebugisexercisedduringanexecution,anauditwillsuc-ceed.
Forinstance,ifSallowsunauthorizedsoftwaremodications,BobcouldusethisfeaturetochangeorreplaceS.
AlicemustthereforemakesurethatSdoesnothavevulnerabilitiesthatBobcouldexploit.
Second,anybehaviorthatcanbeachievedbypro-vidingappropriateinputstoMRisconsideredcorrect.
Whensuchinputscomefromsourcesotherthanthenet-work,theycannotbeveriedduringanaudit.
Insomeapplications,Bobmaybeabletoexploitthisfactbyrecordinglocal(non-network)inputsinthelogthatelicitsomebehaviorinMRhedesires.
5Application:CheatdetectioningamesAVMsandAVMMsareapplication-independent,butforourevaluation,wefocusononespecicapplication,namelycheatdetection.
WebeginbycharacterizingtheclassofcheatsthatAVMscandetect,andwediscusshowAVMscomparetotheanti-cheatsystemsthatareinusetoday.
75.
1HowarecheatsdetectedtodayToday,manyonlinegamesuseanti-cheatingsystemslikePunkBuster[35],theWarden[23]orValveAnti-Cheat(VAC)[38].
Thesesystemsworkbyscanningtheuser'smachineforknowncheats[23,24,35];someal-lowthegameadminstorequestscreenshotsortoper-formmemoryscans.
Inadditiontoprivacyconcerns,thisapproachhasledtoanarmsracebetweencheatersandgamemaintainers,inwhichtheformerconstantlyreleasenewcheatsorvariationsofexistingones,andthelattermuststruggletokeeptheirdatabasesuptodate.
5.
2HowcanAVMsbeusedwithgamesRecallthatAVMsrunentireVMimagesratherthanin-dividualprograms.
Hence,theplayersrstneedtoagreeonaVMimagethattheywilluse.
Forexample,oneofthemcouldinstallanoperatingsystemandthegameit-selfinaVM,createasnapshotoftheVM,andthendistributethesnapshottotheotherplayers.
EachplayertheninitializeshisAVMwiththeagreed-uponsnapshotandplayswhilerecordingalog.
Ifaplayerwishestoreassurehimselfthatotherplayershavenotcheated,hecanrequesttheirlogs(duringorafterthegame),checkthemfortampering,andreplaythemusinghisown,trustedcopyoftheagreed-uponVMimage.
Sincemanycheatsinvolveinstallingadditionalpro-gramsormodifyingexistingones,itisimportanttodis-ablesoftwareinstallationinthesnapshotthatisusedduringthegame,e.
g.
,byrevokingthenecessaryprivi-legesfromallaccountsthatareaccessibletotheplayers.
Otherwise,downloadingandinstallingacheatwouldsimplybere-executedduringreplaywithoutcausinganydiscrepancies.
However,notethatthisrestrictionisonlyrequiredduringthegame;itdoesnotpreventthemain-taineroftheoriginalVMimagefrominstallingupgradesorpatches.
5.
3HowdoplayerscheatingamesPlayerscancheatinmanydifferentways–arecenttax-onomy[41]identiednolessthanfteendifferenttypesofcheats,includingcollusion,denialofservice,timingcheats,andsocialengineering.
InSection5.
4,wedis-cusswhichofthesecheatsAVMsareeffectiveagainst,andweillustrateourdiscussionwiththreeconcreteex-amplesofcheatsthatareusedinCounterstrike.
Sincethereadermaynotbefamiliarwiththesecheats,wede-scribethemhererst.
Therstcheatisanaimbot.
Itspurposetohelpthecheaterwithtargetacquisition.
Whentheaimbotisac-tive,thecheateronlyneedstopointhisweaponintheapproximatedirectionofanopponent;theaimbotthenautomaticallyaimstheweaponexactlyatthatopponent.
Anaimbotisanexampleofacheatthatworks,atleastconceptually,byfeedingthegamewithforgedinputs.
Thesecondcheatisawallhack.
Itspurposeistoal-lowthecheatertoseethroughopaqueobjects,suchaswalls.
Wallhacksworkbecausethegameusuallyren-dersamuchlargerpartofthescenerythanisactuallyvisibleonscreen.
Thus,ifthetexturesonopaqueob-jectsaremadetransparentorremovedentirely,e.
g.
,byaspecialgraphicsdriver[37],theobjectsbehindthembecomevisible.
Awallhackisanexampleofacheatthatviolatessecrecy;itrevealsinformationthatisavail-abletothegamebutisnotmeanttobedisplayed.
Thethirdcheatisunlimitedammunition.
Thevari-antweusedidentiesthememorylocationintheCoun-terstrikeprocessthatholdsthecheater'scurrentamountofammunition,andthenperiodicallywritesaconstantvaluetothatlocation.
Thus,evenifthecheatercon-stantlyreshisweapon,heneverrunsout(similarcheatsexistforotherresources,e.
g.
,unlimitedhealth).
Thischeatchangesthenetwork-visiblebehaviorofthecheater'smachine.
Itisrepresentativeofalargerclassofcheatsthatrelyonmodifyinglocalin-memorystate;otherexamplesincludeteleportation,whichchangesthevariablethatholdstheplayer'scurrentposition,orun-limitedhealth.
5.
4WhichcheatscanAVMsdetectAVMsareeffectiveagainsttwospecic,broadclassesofcheats,namely1.
cheatsthatneedtobeinstalledalongwiththegameinsomeway,e.
g.
,asloadablemodules,patches,orcompanionprograms;and2.
cheatsthatmakethenetwork-visiblebehaviorofthecheater'smachineinconsistentwithanycorrectexecution.
Bothtypesofcheatscausereplaytofailwhenthecheater'smachineisaudited.
Intherstcase,thereasonisthatreplaycanonlysucceediftheVMimagesusedduringrecordingandreplayproducethesamesequenceofeventsrecordedinthelog.
Ifdifferentcodeisexe-cutedordifferentdataisreadatanytime,replayalmostcertainlydivergessoonafterward.
Inthesecondcase,replayfailsbydenitionbecausethereexistsnocorrectexecutionthatisconsistentwiththenetworktrafcthecheater'smachinehasproduced.
Ifacheatisintherstclassbutnotinthesecond,itmaybepossibletore-engineerittoavoiddetection.
Commonexamplesincludecheatsthatviolatesecrecy,suchaswallhacks,andcheatsthatrelyonforgedinputs,suchasaimbots.
Forinstance,acheatermightimple-mentanaimbotasaseparateprogramthatrunsoutside8Totalnumberofcheatsexamined26CheatsdetectablewithAVMs26.
.
.
inthisspecicimplementationofthecheat22.
.
.
nomatterhowthecheatisimplemented4CheatsnotdetectablewithAVMs0Table1:DetectabilityofCounterstrikecheatsfrompop-ularCounterstrikediscussionforumsoftheAVMandaimstheplayer'sweaponbyfeedingfakeinputstotheAVM'sUSBport.
Aparticularlytech-savvycheatermightevensetupasecondmachinethatusesacameratocapturethegamestatefromtherstmachine'sscreenandarobotarmtotypecommandsontherstmachine'skeyboard.
Whilesuchcheatsarebynomeansimpossible,theydorequiresubstantiallymoreeffortandexpertisethanasimplepatchormodulethatmanipulatesthegamestatedirectly.
Thus,AVMsraisethebarsignicantlyforsuchcheats.
Incontrast,cheatsinthesecondclasscanbedetectedbyAVMsinanyimplementation.
Examplesofsuchcheatsincludeunlimitedammunition,unlimitedhealth,orteleportation.
Forinstance,ifaplayerhaskroundsofammunitionandusesacheatofanytypetoremorethankshots,replayinevitablyfailsbecausethereisnocorrectexecutionofthegamesoftwareinwhichaplayercanreafterhavingrunoutofammunition.
AVMsareeffectiveagainstanycurrentorfuturecheatsthatfallintothiscategory.
Wehypothesizethattherstclassincludesalmostallcheatsthatareinusetoday.
Totestthishypothe-sis,wedownloadedandexamined26realCounterstrikecheatsfrompopulardiscussionforumsontheInternet(Table1).
WefoundthateverysingleoneofthemhadtobeinstalledinthegameAVMtobeeffective,andwouldthereforebedetected.
Wealsofoundthatatleast4ofthe26cheatsadditionallybelongedtothesecondclassandcouldthereforebedetectednotonlyintheircurrentform,butalsoinanyfutureimplementation.
5.
5SummaryEventhoughwedidnotspecicallydesignAVMsforcheatdetection,theydoofferthreeimportantadvan-tagesovercurrentanti-cheatingsolutionslikeVACorPunkBuster.
First,theyprotectplayers'privacybysep-aratingauditablecomputation(thegameintheAVM)fromnon-auditablecomputation(e.
g.
,browserorbank-ingsoftwarerunningoutsidetheAVM).
Second,theyareeffectiveagainstvirtuallyallcurrentcheats,includ-ingnovel,rare,orunknowncheats.
Third,theyareguar-anteedtodetectallpossiblecheatsofacertaintype,nomatterhowtheyareimplemented.
6EvaluationInthissection,wedescribeourAVMMprototype,andwereporthowweusedittodetectcheatinginCoun-terstrike,apopularmulti-playergame.
Ourgoalistoanswerthefollowingthreequestions:1.
DoestheAVMMworkwithstate-of-the-artgames2.
AreAVMseffectiveagainstrealcheats3.
Istheoverheadlowenoughtobepractical6.
1PrototypeimplementationOurprototypeAVMMimplementationisbasedonVMwareWorkstation6.
5.
1,astate-of-the-artvirtualmachinemonitorwhosesourcecodeweobtainedthroughVMware'sAcademicProgram.
VMwareWork-stationsupportsawiderangeofguestoperatingsys-tems,includingLinuxandMicrosoftWindows,anditsVMMalreadysupportsmanyfeaturesthatareusefulforAVMs,suchasdeterministicreplayandincremen-talsnapshots.
WeextendedtheVMMtorecordex-trainformationaboutincomingandoutgoingnetworkpackets,andweaddedsupportfortamper-evidentlog-ging,forwhichweadaptedcodefromPeerReview[21].
SinceVMwareWorkstationonlysupportsuniprocessorreplay,ourprototypeislimitedtoAVMswithasinglevirtualcore(seeSection7.
4foradiscussionofmulti-processorreplay).
However,mostoftheloggingfunc-tionalityisimplementedinaseparatedaemonprocessthatcommunicateswiththeVMMthroughkernel-levelpipes,sotheAVMMcantakeadvantageofmulti-coreCPUsbyusingoneofthecoresforlogging,crypto-graphicoperationsandauditing,whilerunningAVMsontheothercoresatfullspeed.
Ouraudittoolimplementsatwo-stepprocess:Play-ersrstperformthesyntacticcheckusingaseparatetoolandthenrunthesemanticcheckbyreplayingtheloginalocalAVM,usingacopyoftheVMimagetheytrust.
Ifatleastoneofthetwostagesfails,theycangivethelogandtheauthenticatorsasevidencetofellowplayers—or,indeed,anythirdparty.
Allstepsaredeterministic,sotheotherpartywillobtainthesameresult.
6.
2ExperimentalsetupForourevaluation,weusedtheAVMMprototypetode-tectcheatinginCounterstrike.
Therearetworeasonsforthischoice.
First,Counterstrikeisplayedinavarietyofonlineleagues,aswellasinworldwidechampionshipssuchastheWorldCyberGames,whichmakescheat-ingamatterofseriousconcern.
Second,thereisalargeanddiverseecosystemofreadilyavailableCounterstrikecheats,whichwecanuseforourexperiments.
OurexperimentsaredesignedtomodelaCounter-strikegameasitwouldbeplayedatacompetitionor905010015020025030035005101520253035Logsize(MB)Time(minutes)AVMMlogEquivalentVMwarelogFigure3:GrowthoftheAVMMlog,andanequivalentVMwarelog,whileplayingCounterstrike.
ataLANparty.
WeusedthreeDellPrecisionT1500workstations,oneforeachplayer,with8GBofmem-oryand2.
8GHzIntelCorei7860CPUs.
EachCPUhasfourcoresandtwohyperthreadspercore.
Thema-chineswereconnectedtothesameswitchvia1GbpsEthernetlinks,andtheywererunningLinux2.
6.
32(De-bian5.
0.
4)asthehostoperatingsystem.
Oneachma-chine,weinstalledanAVMMbinarythatwasbasedonaVMwareWorkstation6.
5.
1releasebuild.
Eachplayerhadaccesstoan'ofcial'VMsnapshot,whichcon-tainedWindowsXPSP3astheguestoperatingsystem,aswellasCounterstrike1.
6atpatchversion1.
1.
2.
5.
SoundandvoiceweredisabledinthegameandinVMware.
AsdiscussedinSection5.
2,weconguredthesnapshottodisallowsoftwareinstallation.
Inthesnapshot,theOSwasalreadybooted,andtheplayerwasloggedinwithoutadministratorprivileges.
Allplayerswereusing768-bitRSAkeys.
Thesekeysarenotstrongenoughtoprovidelong-termsecurity,butinourscenariothesignaturesonlyneedtolastuntilanycheatershavebeenidentied,i.
e.
,atmostafewdaysorweeksbeyondtheendofthegame.
InDecember2009,factoringa768-bitnumbertookalmost2,000Opteron-CPUyears[3],sothiskeylengthshouldbesafeforgam-ingpurposesforsometimetocome.
ToquantifythecostsofvariousaspectsofAVMs,weranexperimentsinvedifferentcongurations.
bare-hwisourbaselinecongurationinwhichthegamerunsdirectlyonthehardware,withoutvirtualization.
vmware-norecaddsthevirtualmachinemonitorwith-outourmodications,andvmware-recaddstheloggingfordeterministicreplay.
avmm-nosigusesourAVMMimplementationwithoutsignatures,andavmm-rsa768isthefullsystemasdescribed.
Weremovedthedefaultframeratecapof72fps,sothatCounterstrikerenderedframesasquicklyastheavailableCPUresourcesallowandwecanusetheachievedframerateasaperformancemetric.
InSec-tion6.
5weconsideracongurationwiththedefault024681012VMwareAVMM(RSA-768)Averageloggrowth(MB/minute)Tamper-evidentloggingVMwareotherVMwareMAClayerVMwareTimeTrackerTotalaftercompressionFigure4:AverageloggrowthforCounterstrikebycon-tent.
Thebarsinfrontshowthesizeaftercompression.
frameratecap.
Tomakesuretheperformanceofbare-hwandvirtualizedcongurationscanbecompared,weconguredthegametorunwithoutOpenGL,whichisnotsupportedinourversionofVMwareWorkstation,andweranthegameinwindowratherthanfull-screenmode.
Weplayedeachgameforatleastthirtyminutes.
6.
3FunctionalitycheckRecallfromSection5.
4thatAVMscandetectbydesignallofthe26cheatsweexamined.
Asasanitychecktovalidateourimplementation,wetriedfourCounterstrikecheatsinourcollectionthatdonotdependonOpenGL.
Foreachcheat,wecreatedamodiedVMimagethathadthecheatpreinstalled,andwerananexperimentintheavmm-rsa768congurationwhereoneoftheplay-ersusedthespecialVMimageandactivatedthecheat.
Wethenauditedeachplayer;asexpected,theauditsofthehonestplayersallsucceeded,whiletheauditsofthecheaterfailedduetoadivergenceduringreplay.
6.
4LogsizeandcontentsTheAVMMrecordsalogoftheAVM'sexecutiondur-inggameplay.
Todeterminehowfastthisloggrows,weplayedthegameintheavmm-rsa768conguration,andwemeasuredthelogsizeovertime.
Figure3showstheresults.
Theloggrowsslowlywhileplayersarejoin-ingthegame(untilabout3minutesintotheexperiment)andthencontinuestogrowsteadilyduringgameplay,byabout8MBperminute.
Forcomparison,wealsoshowthesizeofanequivalentVMwarelog;thediffer-enceisduetotheextrainformationthatisrequiredtomakethelogtamper-evident.
Figure4showstheaverageloggrowthrateaboutthecontent.
Morethan70%oftheAVMMlogconsistofinformationneededforreplay;tamper-evidentloggingisresponsiblefortherest.
Thereplayinformationcon-sistsmainlyofTimeTrackerentries(59%),whichareusedbytheVMMtorecordtheexacttimingofevents,andMAC-layerentries(14%),suchasincom-10ingoroutgoingnetworkpackets;otherentrytypesac-countfortheremaining27%.
ThecompositionoftheVMwarelogdiffersslightlybecausethepacketpayloadsarestoredintheMAC-layerentriesratherthaninthetamper-evidentloggingentries.
Wealsoshowresultsaf-terapplyingbzip2andalossless,VMM-specic(butapplication-independent)compressionalgorithmwede-veloped.
Thisbringstheaverageloggrowthrateto2.
47MBperminute.
Fromtheseresults,wecanestimatethataone-hourgamesessionwouldresultina480MBlog,or148MBaftercompression.
Thus,giventhatcurrentharddiskcapacitiesaremeasuredinterabytes,storageshouldnotbeaproblem,evenforverylonggames.
Also,whenaplayerisaudited,hemustuploadhislogtohisfellowplayers.
IfthegameisplayedovertheInternet,upload-ingaone-hourlogwouldtakeabout21minutesovera1Mbpsupstreamlink.
IfthegameisplayedoveraLAN,e.
g.
,atacompetition,theuploadwouldcompleteinafewseconds.
Toavoiddetectiondelays,ourpro-totypecanalsoperformauditingconcurrentlywiththegame;weevaluatethisfeatureinSection6.
11.
6.
5LowgrowthwiththeframeratecapRecallthatCounterstrikewasconguredwithoutaframeratecapinourexperiments,sothatthemea-suredframeratecanbeusedasaperformancemet-ric.
Wediscoveredthatwhentheframeratecapisen-abled,Counterstrikeappearstoimplementinter-framedelaysbybusy-waitinginatightloop,readingthesys-temclock.
SincetheAVMMhastologeveryclockac-cessasanondeterministicinput,thisincreasestheloggrowthconsiderably—byafactorof18whenthedefaultcapof72fpsisused.
Toreducetheloggrowthforapplicationsthatexhibitthisbehavior,weexperimentedwiththefollowingopti-mization.
WhenevertheAVMMobservesconsecutiveclockreadsfromthesameAVMwithin5μsofeachother,itdelaysthen.
thconsecutivereadby2n250μs,startingwiththesecondreadanduptoalimitof5ms.
Theexponentialprogressionofdelayslimitsthenumberofclockreadsduringlongwaits,butdoesnotundulyaf-fecttimingaccuracyduringshortwaits.
Thisoptimizationisveryeffective:loggrowthisac-tually2%lowerthanreportedinSection6.
4,withorwithouttheframe-ratecap.
Moreover,theuncappedframerateisonly3%lowerthantheratewithouttheop-timization,whichshowsthattheoptimizationhasonlyamildimpactongameperformance.
6.
6SyntacticandsemanticcheckAlicecanauditanotherplayerBobbycheckingBob'slogagainsthisauthenticators(syntacticcheck)andbyreplayingBob'slogusingatrustedcopyoftheVMim-0246810BarehardwareVMwareVMware(recording)AVMM(nosig)AVMM(RSA-768)Pinground-triptime(ms)BaselineWithVMMWithAVMMFigure5:Medianpinground-triptimes.
Theerrorbarsshowthe5thandthe95thpercentile.
age(semanticcheck).
Weexpectthesyntacticchecktoberelativelyfast,sinceitisessentiallyamatterofverifyingsignatures,whereasthereplayinvolvesrepeat-ingallthecomputationsthatwereperformedduringtheoriginalgameandshouldthereforetakeaboutaslongasthegameitself.
Ourexperimentswiththelogoftheservermachinefromtheavmm-rsa768conguration(whichcovers2,216secondswith1,987secondsofac-tualgameplay)conrmthis.
Weneeded34.
7secondstocompressthelog,13.
2secondstodecompressit,6.
9secondsforthesyntacticcheck,and1,977secondsforthesemanticcheck(2,031secondstotal).
ReplaywasactuallyabitfasterbecausetheAVMMskipsanytimeperiodsintherecordingduringwhichtheCPUwasidle,e.
g.
,beforethegamewasstarted.
Unliketheperformanceoftheactualgame,thespeedofauditingisnotcriticalbecauseitcanbeperformedatleisure,e.
g.
,inthebackgroundwhilethemachineisusedforsomethingelse.
6.
7NetworktrafcTheAVMMincreasestheamountofnetworktrafcfortworeasons:First,itaddsacryptographicsignaturetoeachpacket,andsecond,itencapsulatesallpacketsinaTCPconnection.
Toquantifythisoverhead,wemeasuredtheraw,IP-levelnetworktrafcinthebare-hwcongurationandintheavmm-rsa768conguration.
Onaverage,themachinehostingthegamesent22kbpsinbare-hwand215.
5kbpsinavmm-rsa768.
ThishighrelativeincreaseispartlyduetothefactthatCounterstrikeclientssendextremelysmallpacketsof50–60byteseach,at26packets/sec,sotheAVMM'sxedper-packetoverhead(whichincludesonecrypto-graphicsignatureforeachpacketandoneforeachac-knowledgment)hasamuchhigherimpactthanitwouldforpacketsofaverageInternetpacketsize.
However,inabsoluteterms,thetrafcisstillquitelowandwellwithinthecapabilitiesofevenaslowbroadbandup-stream.
110%20%40%60%80%100%BarehardwareVMwareVMware(recording)AVMM(nosig)AVMM(RSA-768)AverageutilizationHyperthreadsAverage(entireCPU)12.
5%Figure6:AverageCPUutilizationinCounterstrikeforeachoftheeighthyperthreads,andfortheentireCPU.
6.
8LatencyTheAVMMaddssomelatencytopackettransmissionsbecauseoftheloggingandprocessingofauthenticators.
Toquantifythis,werananAVMinvedifferentcon-gurationsandmeasuredtheround-triptime(RTT)of100ICMPEchoRequestpackets.
Figure5showsthemedianRTT,aswellasthe5thandthe95thpercentile.
Sinceourmachinesareconnectedtothesameswitch,theRTTonbarehardwareisonly192μs;addingvir-tualizationincreasesitto525μs,VMwarerecordingto621μs,andthedaemontoabove2ms.
Enabling768-bitRSAsignaturesbringsthetotalRTTtoabout5ms.
Re-callthatboththepingandthepongareacknowledged,sofoursignaturesneedtobegeneratedandveried.
Sincethecriticalthresholdforinteractiveapplicationsiswellabove100ms[12],5msseemtolerableforgames.
Theoverheadcouldbereducedbyusingasigningal-gorithmsuchasESIGN[34],whichcangenerateandverifya2046-bitsignatureinlessthan125μs.
6.
9CPUutilizationComparedtoaCounterstrikegameonbarehardware,theAVMMrequiresadditionalCPUpowerforvirtual-izationandforthetamper-evidentlog.
Toquantifythisoverhead,wemeasuredtheCPUutilizationinvecon-gurations,rangingfrombare-hwtoavmm-rsa768.
Toisolatethecontributionfromthetamper-evidentlog,wepinnedthedaemonprocesstohyperthread0(HT0)intheAVMMexperimentsandrestrictedthegametotheotherhyperthreadsexceptforHT0'shypertwin,HT4,whichsharesacorewithHT0.
2OneofthemachinesinourexperimentsrunstheCounterstrikeserverinad-ditiontoservingaplayer.
Tobeconservative,wereportnumbersforthismachine,asithasthehighestload.
Figure6showstheaverageutilizationforeachHT,aswellastheaverageacrosstheentireCPU.
Theuti-lizationofHT0(below8%)intheAVMexperiments2Nevertheless,theloadonHT4isnotexactlyzerobecauseLinuxperformskernel-levelIRQhandlingonlightly-loadedhyperthreads.
050100150200BarehardwareVMwareVMware(recording)AVMM(nosig)AVMM(RSA768)AverageframerateBaselineWithVMMWithAVMMFigure7:FramerateinCounterstrikeforeachofthethreemachines.
Theleftmachinewashostingthegame.
showsthattheoverheadfromthetamper-evidentlogislow.
Thegameisconstantlybusyrenderingframes,butbecausetheCounterstrikerenderingengineissingle-threaded,itcannotrunonmorethanoneHTatatime.
TheOS/VMMwillsometimesscheduleitononeHTandsometimesonanother,thusweexpectanaverageutilizationovertheeightHTsof12.
5%,whichourre-sultsconrm.
6.
10FramerateSincethegameisrenderingframesasfastastheavail-ableCPUcyclesallow,ameaningfulmetricfortheCPUoverheadistheachievedframerate,whichweconsidernext.
Tomeasuretheframerate,wewroteanAMXModX[1]scriptthatincrementsacountereverytimeaframeisrendered.
Wereadoutthiscounteratthebe-ginningandattheendofeachgame,andwedividedthedifferencebytheelapsedtime.
Figure7showsourresultsforeachofthethreemachines.
Theresultsvaryovertimeandamongplayers,becausetheframeratede-pendsonthecomplexityofthescenebeingrendered,andthusonthepathtakenbyeachplayer.
TheframerateontheAVMMisabout13%lowerthanonbarehardware.
ThebiggestoverheadseemstocomefromenablingrecordinginVMwareWorkstation,whichcausestheaverageframeratetodropbyabout11%.
Inabsoluteterms,theresultingframerate(137fps)isstillveryhigh;postsinCounterstrikeforumsgenerallyrec-ommendconguringthegameforabout60–80fps.
ToquantifytheadvantageofrunningsomeoftheAVMMlogiconadifferentHT,werananadditionalex-perimentwithbothCounterstrikeandallAVMMthreadspinnedtothesamehyperthread.
Thisreducedtheaver-ageframeratebyanother11fps.
6.
11OnlineauditingIfagamesessionislongorthestakesareparticularlyhigh,playersmaywishtodetectcheaterswellbeforetheendofthegame.
Insuchcases,playerscanincre-120%20%40%60%80%100%120%0%20%40%60%80%100%Timetospot-checkthechunk(comparedtoafullaudit)Numberofconsecutivesegmentscoveredbythechunk(k)Spot-checktimeLinear(forcomparison)0%20%40%60%80%100%120%0%20%40%60%80%100%Totaldatatransferred(comparedtoafullaudit)Numberofconsecutivesegmentscoveredbythechunk(k)DatatransferredLinear(forcomparison)Figure9:Efciencyofspotchecking.
Thecostofaspotcheckisroughlyproportionaltothesizeofthecheckedchunk,butthereisaxedcostperchunkfortransferringthememoryanddisksnapshotsandfordatadecompression.
050100150200NoonlineauditingOneauditperplayerTwoauditsperplayerAverageframerateOfflineauditingOnlineauditingFigure8:Framerateforeachofthethreemachineswithzero,one,ortwoonlineauditspermachine.
mentallyauditotherplayers'logswhilethegameisstillinprogress.
Inthisconguration,whichwerefertoasonlineauditing,cheatingcouldbedetectedassoonastheexternallyvisiblebehaviorofthecheater'smachinedeviatesfromthatofthereferencemachine.
Ifaplayerusesthesamemachinetoconcurrentlyplaythegameandauditotherplayers,thehigherresourceconsumptioncanaffectgameperformance.
Toquantifythiseffect,weplayedthegameintheavmm-rsa768con-gurationwitheachplayerauditingzero,one,ortwootherplayersonthesamemachine.
Asbefore,wemea-suredtheaverageframerateexperiencedbyeachplayer.
Figure8showsourresults.
Withanincreasingnum-berofplayersaudited,theframeratedropssomewhat,from137fpswithnoauditsto104fpswithtwoaudits.
However,thedropislesspronouncedthanexpectedbe-causetheauditscanleveragetheunusedcores.
Ifthenumberofauditsaisincreasedfurther,weexpectthegameperformancetoeventuallydegradewith1/a.
Sincereplayisslightlyslowerthantheoriginalexe-cution,auditingfallsbehindthegamebyaboutfoursec-ondsperminuteofplay,evenwhentheauditexecutesonanotherwiseunloadedmachine.
Toensurequickdetec-tionevenduringverylonggamesessions,wecancom-pensatebyarticiallyslowingdowntheoriginalexecu-tion.
Wefoundthata5%slowdownwassufcienttoallowtheauditortokeepup;thisreducedtheframeratebyupto7fps.
Notethatacertainlagcanactuallybeusefultopreventplayersfromlearningeachother'scur-rentpositionsorstrategiesthroughanaudit.
Inpractice,playersmaywanttodisallowauditsofthecurrentroundand/orthemostrecentmomentsofgameplay.
6.
12SpotcheckingOnlinegamesarenotaveryinterestingusecaseforspotcheckingbecausecompleteauditsarefeasible.
There-fore,wesetupasimpleadditionalexperimentthatmod-elsaclient/serversystem–specically,aMySQL5.
0.
51serverinoneAVMandaclientrunningMySQL'ssql-benchbenchmarkinanother.
Weranthisex-perimentfor75minutesintheavmm-rsa768congura-tion,andwerecordedasnapshoteveryveminutes.
Wefoundthat,onaverage,ourprototypetakes5secondstorecordasnapshot.
Theincrementaldisksnapshotsarebetween1.
9MBand91MB,whileeachmemorysnap-shotoccupiesabout530MB.
ThereasonforthelatteristhatVMwareWorkstationcreatesafulldumpoftheAVM'smainmemory(512MB)foreachsnapshot.
Thiscouldprobablybeoptimizedconsiderably,e.
g.
,usingtechniquesfromRemus[11].
Inthefollowing,werefertothepartofthelogbe-tweentwoconsecutivesnapshotsasasegment,andtokconsecutivesegmentsasak-chunk.
Toquantifythecostsofspotchecking,weauditedallpossiblek-chunksinourlogfork∈{1,3,5,9,12},andmeasuredtheamountofdatathatmustbetransferredoverthenet-work,aswellasthetimeittakestoreplaythechunk.
However,weexcludedk-chunksthatstartatthebegin-ningofthelog;theseareatypicalbecausea)theyaretheonlychunksforwhichnomemoryordisksnapshotshavetobetransferred,andb)theyhavelessactivitybe-causetheMySQLserverisnotyetrunningatthebegin-ning.
Wereportaveragesbecausetheresultsforchunkswiththesamevalueofknevervariedbymorethan10%.
13Figure9showstheresults,normalizedtothecostofafullaudit.
Asexpected,thecostgrowswiththechunksizek;however,thereisanadditionalxedcostperchunkfortransferringthecorrespondingmemoryanddisksnapshots.
6.
13SummaryHavingreportedourresults,wenowrevisitourthreeini-tialquestions.
WehavedemonstratedthatourAVMMworksout-of-the-boxwithCounterstrike,astate-of-the-artgame,andwehaveshownthatitiseffectiveagainstrealcheatswedownloadedfromCounterstrikeforumsontheInternet.
AVMsarenotfree;theyaffectvariousmetricssuchaslatency,trafc,orCPUutilization,andtheyreducetheframeratebyabout13%,comparedtotherateachievedonbarehardware.
Inreturnforthisoverhead,playersgaintheabilitytoauditotherplayers.
Auditingtakestime,insomecasesasmuchasthegameitself,butitseemstimewellspentbecauseiteitherex-posesacheaterorclearsaninnocentplayerofsuspicion.
AVMsprovidethisnovelcapabilitybycombiningtwoseeminglyunrelatedtechnologies,tamper-evidentlogsandvirtualization.
7Discussion7.
1OtherapplicationsAVMsareapplication-independentandcanbeusedinapplicationsotherthangames.
Distributedsystems:AVMscanbeusedtomakeanydistributedsystemaccountable,simplybyexecutingthesoftwareoneachnodewithinanAVM.
Thenodesoft-warecanbearbitrarilycomplexandavailableonlyasabinarysystemimage.
Accountabilityisusefulindis-tributedsystemswhereprincipalshaveaninterestinmonitoringthebehaviorofotherprincipals'nodes,andwherepostfactumdetectionissufcient.
Suchsystemsincludefederatedsystemswherenosingleentityhascompletecontrolorvisibilityoftheentiresystem,wheredifferentpartiescompete(e.
g.
,inanonlinegame,anauction,orafederatedsystemliketheInternet)orwherepartiesareexpectedtocooperatebutlackadequatein-centivestodoso(e.
g.
,inapeer-to-peersystem).
Networktrafcaccountability:AVMscouldalsobeusefulindetectingadvancedformsofmalwarethatcouldescapeonlinedetectionmechanisms.
AnAVM,combinedwithatrafcmonitorthatrecordsamachine'snetworkcommunication,cancapturethenetwork-observablebehaviorofamachine,andreplayitlaterwithexpensiveintrusiondetection(e.
g.
,tainttrack-ing)inplace.
Cloudcomputing:AnotherpotentialapplicationofAVMsiscloudcomputing.
AVMscanenablecloudcus-tomerstoverifythattheirsoftwareexecutesinthecloudasexpected.
AVMareaperfectmatchforinfrastructure-as-a-service(IaaS)cloudsthatoffercustomersavir-tualmachine.
However,AVMsinthecloudfaceaddi-tionalchallenges:auditorscannoteasilyreplaytheen-tireexecutionforlackofresources;accountableservicesmustbeabletointeractwithnon-accountableclients;and,itmaynotbepracticaltosigneverysinglepacket.
Therstchallengecanbeaddressedwithspotchecking(Section3.
5).
Weplantoaddresstheremainingchal-lengesinfuturework.
7.
2UsingtrusttogetstrongerguaranteesOneofthestrengthsofAVMsisthattheycanverifytheintegrityofaremotenode'sexecutionwithoutrelyingontrustedcomponents.
However,iftrustedcomponentsareavailable,wecanobtainadditionalguarantees.
Wesketchtwopossibleextensionsbelow.
Securelocalinput:AVMscannotdetectthehypothet-icalre-engineeredaimbotfromSection5.
4becauseex-istinghardwaredoesnotauthenticateeventsfromlocalinputdevices,suchaskeyboardsormice.
Thus,acom-promisedAVMMcanforgeorsuppresslocalinputs,andevenacorrectAVMMcannotknowwhetheragivenkeystrokewasgeneratedbytheuserorsynthesizedbyanotherprogram,oranothermachine.
Thislimitationcanbeovercomebyaddingcryptosupporttotheinputdevices.
Forexample,keyboardscouldsignkeystrokeeventsbeforereportingthemtotheOS,andanauditorcouldverifythatthekeystrokesaregenuineusingthekeyboard'spublickey.
Sincemostperipheralsgener-ateinputatrelativelylowrates,thenecessaryhardwareshouldnotbeexpensivetobuild.
TrustedAVMM:IfwecantrusttheAVMMthatisrun-ningonaremotenode,wecandetectadditionalclassesofcheatsandattacks,includingcertainattacksoncon-dentiality.
Forexample,atrustedAVMMcouldestab-lishasecurechannelbetweentheAVMandAlice(evenifthesoftwareintheAVMdoesnotsupportencryption)andthuspreventBob'smachinefromleakinginforma-tionbysecretlycommunicatingwithothermachines.
AtrustedAVMMcouldalsopreventwallhacks(seeSec-tion5.
3)bycontrollingoutsideaccesstothemachine'sgraphicscard.
Iftrustedhardware,suchasmemoryen-cryption[40]isavailableonBob'smachine,theAVMMcouldevenpreventBobfromreadinginformationdi-rectlyfrommemory.
RemoteattestationcouldbeusedtomakesurethatatrustedAVMMisindeedrunningonaremotecomputer,e.
g.
,usingasystemlikeTerra[17].
7.
3AccountabilityversusprivacyIdeally,anaccountabilitysystemshoulddisclosetoanauditoronlytheinformationstrictlyrequiredtodeter-minethattheauditeehasmethisobligations.
Bythisstandard,AVMlogsareratherverbose:anAVMrecords14enoughinformationtoreplaytheexecutionofthesoft-wareitisrunning.
Thisisapricewepayforthegen-eralityofAVMs—theycandetectalargeclassoffaultsincomplexsoftwareavailableonlyinbinaryform.
Inpractice,theamountofextrainformationreleasedcanbecontrolled.
LetusconsiderhowtheextrainformationcapturedintheAVMlogsaffectAliceandBob'sprivacy.
ThelogrevealsinformationaboutactionsofBob'smachine,butonlyabouttheexecutioninsideagivenAVM,andonlytoapprovedauditors.
Inthewebservicescenario(Figure2b),AliceispresumablypayingBobforrun-ninghersoftwareinanAVM,soshehaseveryrighttoknowabouttheexecutionofthesoftware.
Similarly,itisnotunreasonabletoexpectplayersinagametoshareinformationabouttheirgameexecution.
Ineithercase,theauditorcannotobserveexecutionstheauditeemayberunningoutsidetheauditedAVM.
AliceandBob'sprivacymaybeaffectedwhensheusespartofthelogasevidencetodemonstrateafaultonBob'smachinetoathirdparty.
Theevidencerevealsad-ditionalinformationabouttheAVM,includingasnap-shot,tothatparty.
Therefore,Aliceshouldreleaseevi-denceonlytothirdpartiesthathavealegitimateneedtoknowaboutfaultsonBob'smachine.
Tolimittheextrainformationreleasedtothirdparties,Alicecanusethehashtree(Section4.
4)toremoveanypartofthesnap-shotthatisnotnecessarytoreplaytherelevantsegment.
7.
4ReplayformultiprocessorsOurprototypeAVMMcanassignonlyasingleCPUcoreforeachAVM,becauseVMware'sdeterministicre-playislimitedtouniprocessors.
SMP-ReVirt[16]hasrecentlydemonstratedthatdeterministicreplayisalsopossibleformultiprocessors,butitscostissubstantiallyhigherthanthecostofuniprocessorreplay.
Becausereplayisabuildingblockformanyimportantapplica-tions,suchasforensics[15],replication[11],andde-bugging[25],thereisconsiderableinterestindevelop-ingmoreefcienttechniques[5,13,16,28,29].
Asmoreefcienttechniquesbecomeavailable,AVMMscandirectlybenetfromthem.
7.
5BugdetectionRecallthatAVMsdenefaultsasdeviationsfromthebehaviorofareferenceimplementation.
Ifthereferenceimplementationhasabugandthisbugistriggereddur-inganexecution,itwillbehaveidenticallyduringthereplay,andthusitwillnotbeclassiedasafault.
Ifabuginthereferenceimplementationpermitsunautho-rizedsoftwaremodication(e.
g.
,abufferoverowbug),thenneitherthemodicationitselfnorthebehaviorofthemodiedsoftwarewillbereportedasafault.
DetectingbugsinthereferenceimplementationisoutsidethefaultmodelAVMsweredesignedtodetect.
However,deterministicexecutionreplayprovidesanop-portunitytousesophisticatedruntimeanalysistoolsdur-ingauditing[10].
Inparticular,techniqueswhoserun-timecostsaretoohighfordeploymentinalivesystemcouldbeusedduringanoff-linereplay.
Tainttrack-ing,forinstance,canreliablydetecttheunsafeuseofdatathatwerereceivedfromanuntrustedsource[33],thusdetectingbufferoverwriteattacksandotherformsofunauthorizedsoftwareinstallation.
Moregenerally,sophisticatedruntimetechniquescanbeusedduringre-playtodetectbugs,vulnerabilitiesandattacksaspartofanormalaudit.
8ConclusionAccountablevirtualmachines(AVM)allowuserstoau-ditsoftwareexecutingonremotemachines.
AnAVMcandetectalargeandgeneralclassoffaults,anditpro-ducesevidencethatcanbeveriedindependentlybyathirdparty.
Atthesametime,anAVMallowstheop-eratoroftheremotemachinetoprovewhetherhisma-chineiscorrect.
TodemonstratethatAVMsarefeasi-ble,wehavedesignedandimplementedanAVMmon-itorbasedonVMwareWorkstationandusedittode-tectrealcheatsinCounterstrike,apopularonlinemulti-playergame.
Playerscanrecordtheirgameexecutioninatamper-evidentmanneratamodestcostinframerate.
Otherplayerscanaudittheexecutiontodetectcheats,eitherafterthegamehasnishedorconcurrentlywiththegame.
Thesystemisabletodetectallof26existingcheatsweexamined.
AcknowledgmentsWeappreciatethedetailedandhelpfulfeedbackfromJonHowell,theanonymousOSDIreviewers,andourshepherd,MendelRosenblum.
WewouldliketothankVMwareformakingthesourcecodeofVMwareWork-stationavailabletousundertheVMwareAcademicPro-gram,andourtechnicalcontact,JimChow,whohasbeenextremelyhelpful.
Finally,wewouldliketothankourmanyenthusiasticCounterstrikevolunteers.
References[1]AMXModXproject.
http://www.
amxmodx.
org/.
[2]D.
Andersen,H.
Balakrishnan,N.
Feamster,T.
Koponen,D.
Moon,andS.
Shenker.
AccountableInternetprotocol(AIP).
InProceedingsoftheACMSIGCOMMConference(SIG-COMM),Aug.
2008.
[3]K.
Aoki,J.
Franke,A.
K.
Lenstra,E.
Thome,J.
W.
Bos,P.
Gaudry,A.
Kruppa,P.
L.
Montgomery,D.
A.
Osvik,H.
teRiele,A.
Timofeev,andP.
Zimmerman.
Factorizationofa768-bitRSAmodulus.
http://eprint.
iacr.
org/2010/006.
pdf.
[4]K.
Argyraki,P.
Maniatis,O.
Irzak,andS.
Shenker.
Anaccount-abilityinterfacefortheInternet.
InProceedingsoftheIEEE15InternationalConferenceonNetworkProtocols(ICNP),Oct.
2007.
[5]A.
Aviram,S.
-C.
Weng,S.
Hu,andB.
Ford.
Efcientsystem-enforceddeterministicparallelism.
InProceedingsoftheUSENIXSymposiumonOperatingSystemDesignandImple-mentation(OSDI),Oct.
2010.
[6]P.
Barham,B.
Dragovic,K.
Fraser,S.
Hand,T.
Harris,A.
Ho,R.
Neugebauer,I.
Pratt,andA.
Wareld.
Xenandtheartofvir-tualization.
InProceedingsoftheACMSymposiumonOperatingSystemsPrinciples(SOSP),Oct.
2003.
[7]N.
E.
Baughman,M.
Liberatore,andB.
N.
Levine.
Cheat-proofplayoutforcentralizedandpeer-to-peergaming.
IEEE/ACMTransactionsonNetworking(ToN),15(1):1–13,Feb.
2007.
[8]T.
C.
BressoudandF.
B.
Schneider.
Hypervisor-basedfaulttolerance.
ACMTransactionsonComputerSystems(TOCS),14(1):80–107,1996.
[9]C.
Chambers,W.
Feng,W.
Feng,andD.
Saha.
Mitigatinginfor-mationexposuretocheatersinreal-timestrategygames.
InPro-ceedingsoftheACMInternationalWorkshoponNetworkandoperatingsystemssupportfordigitalaudioandvideo(NOSS-DAV),June2005.
[10]J.
Chow,T.
Garnkel,andP.
M.
Chen.
Decouplingdynamicprogramanalysisfromexecutioninvirtualenvironments.
InProceedingsoftheUSENIXAnnualTechnicalConference,June2008.
[11]B.
Cully,G.
Lefebvre,D.
Meyer,M.
Feeley,N.
Hutchinson,andA.
Wareld.
Remus:Highavailabilityviaasynchronousvirtualmachinereplication.
InProceedingsoftheUSENIXSymposiumonNetworkedSystemsDesignandImplementation(NSDI),Apr.
2008.
[12]J.
DabrowskiandE.
V.
Munson.
Is100millisecondstoofastInProceedingsoftheACMSIGCHIConferenceonHumanFactorsinComputingSystems(CHI),Apr.
2001.
[13]J.
Devietti,B.
Lucia,L.
Ceze,andM.
Oskin.
DMP:Determinis-ticsharedmemorymultiprocessing.
InProceedingsoftheACMInternationalConferenceonArchitecturalSupportforProgram-mingLanguagesandOperatingSystems(ASPLOS),Mar.
2009.
[14]R.
Dingledine,M.
J.
Freedman,andD.
Molnar.
Peer-to-Peer:HarnessingthePowerofDisruptiveTechnologies,chapterAc-countability.
O'ReillyandAssociates,2001.
[15]G.
W.
Dunlap,S.
T.
King,S.
Cinar,M.
Basrai,andP.
M.
Chen.
ReVirt:Enablingintrusionanalysisthroughvirtual-machineloggingandreplay.
InProceedingsoftheUSENIXSymposiumonOperatingSystemDesignandImplementation(OSDI),Dec.
2002.
[16]G.
W.
Dunlap,D.
Lucchetti,P.
M.
Chen,andM.
Fetterman.
Ex-ecutionreplayformultiprocessorvirtualmachines.
InProceed-ingsoftheACM/USENIXInternationalConferenceonVirtualExecutionEnvironments(VEE),Mar.
2008.
[17]T.
Garnkel,B.
Pfaff,J.
Chow,M.
Rosenblum,andD.
Boneh.
Terra:Avirtualmachine-basedplatformfortrustedcomputing.
InProceedingsoftheACMSymposiumonOperatingSystemsPrinciples(SOSP),Oct.
2003.
[18]A.
Haeberlen.
Acasefortheaccountablecloud.
InProceedingsoftheACMSIGOPSInternationalWorkshoponLarge-ScaleDistributedSystemsandMiddleware(LADIS),Oct.
2009.
[19]A.
Haeberlen,P.
Aditya,R.
Rodrigues,andP.
Druschel.
Ac-countablevirtualmachines.
TechnicalReport2010-3,MaxPlanckInstituteforSoftwareSystems,Sept.
2010.
[20]A.
Haeberlen,I.
Avramopoulos,J.
Rexford,andP.
Druschel.
Ne-tReview:Detectingwheninterdomainroutinggoeswrong.
InProceedingsoftheUSENIXSymposiumonNetworkedSystemsDesignandImplementation(NSDI),Apr.
2009.
[21]A.
Haeberlen,P.
Kuznetsov,andP.
Druschel.
PeerReview:Prac-ticalaccountabilityfordistributedsystems.
InProceedingsoftheACMSymposiumonOperatingSystemsPrinciples(SOSP),Oct.
2007.
[22]A.
Haeberlen,P.
Kuznetsov,andP.
Druschel.
PeerReview:Prac-ticalaccountabilityfordistributedsystems.
TechnicalReport2007-3,MaxPlanckInstituteforSoftwareSystems,Oct.
2007.
[23]G.
Hoglund.
4.
5millioncopiesofEULA-compliantspyware.
http://www.
rootkit.
com/blog.
phpnewsid=358.
[24]G.
HoglundandG.
McGraw.
ExploitingOnlineGames:Cheat-ingMassivelyDistributedSystems.
Addison-Wesley,2007.
[25]S.
T.
King,G.
W.
Dunlap,andP.
M.
Chen.
Debuggingoperatingsystemswithtime-travelingvirtualmachines.
InProceedingsoftheUSENIXAnnualTechnicalConference,Apr.
2005.
[26]B.
W.
Lampson.
Computersecurityintherealworld.
InPro-ceedingsoftheAnnualComputerSecurityApplicationsConfer-ence(ACSAC),Dec.
2000.
[27]P.
LaskowskiandJ.
Chuang.
Networkmonitorsandcontract-ingsystems:competitionandinnovation.
InProceedingsoftheACMSIGCOMMConference(SIGCOMM),Sept.
2006.
[28]D.
Lee,M.
Said,S.
Narayanasamy,Z.
Yang,andC.
Pereira.
Ofinesymbolicanalysisformulti-processorexecutionreplay.
InProceedingsoftheIEEE/ACMInternationalSymposiumonMicroarchitecture(MICRO),Dec.
2009.
[29]D.
Lee,B.
Wester,K.
Veeraraghavan,S.
Narayanasamy,P.
M.
Chen,andJ.
Flinn.
Respec:Efcientonlinemultiprocessorre-playviaspeculationandexternaldeterminism.
InProceedingsoftheACMInternationalConferenceonArchitecturalSupportforProgrammingLanguagesandOperatingSystems(ASPLOS),Mar.
2010.
[30]D.
Levin,J.
R.
Douceur,J.
R.
Lorch,andT.
Moscibroda.
TrInc:Smalltrustedhardwareforlargedistributedsystems.
InPro-ceedingsoftheUSENIXSymposiumonNetworkedSystemsDe-signandImplementation(NSDI),Apr.
2009.
[31]N.
Michalakis,R.
Soule,andR.
Grimm.
Ensuringcontentin-tegrityforuntrustedpeer-to-peercontentdistributionnetworks.
InProceedingsoftheUSENIXSymposiumonNetworkedSys-temsDesignandImplementation(NSDI),Apr.
2007.
[32]C.
M¨onch,G.
Grimen,andR.
Midtstraum.
Protectingonlinegamesagainstcheating.
InProceedingsoftheWorkshoponNet-workandSystemsSupportforGames(NetGames),Oct.
2006.
[33]J.
NewsomeandD.
Song.
Dynamictaintanalysisforautomaticdetection,analysis,andsignaturegenerationofexploitsoncom-moditysoftware.
InProceedingsoftheAnnualNetworkandDistributedSystemsSecuritySymposium(NDSS),Feb.
2005.
[34]T.
Okamoto.
Afastsignatureschemebasedoncongruentialpolynomialoperations.
IEEETransactionsonInformationThe-ory,36(1):47–53,1990.
[35]PunkBusterwebsite.
http://www.
evenbalance.
com/.
[36]A.
Seshadri,M.
Luk,E.
Shi,A.
Perrig,L.
vanDoorn,andP.
Khosla.
Pioneer:Verifyingcodeintegrityandenforcingun-tamperedcodeexecutiononlegacysystems.
InProceedingsoftheACMSymposiumonOperatingSystemsPrinciples(SOSP),Oct.
2005.
[37]A.
Smith.
ASUSreleasesgamescheatdrivers.
http://www.
theregister.
co.
uk/2001/05/10/asusreleasesgamescheatdrivers/,May2001.
[38]ValveCorporation.
Valveanti-cheatsystem(VAC).
https://support.
steampowered.
com/kbarticle.
phpref=7849-RADZ-6869.
[39]M.
Xu,V.
Malyugin,J.
Sheldon,G.
Venkitachalam,andB.
Weissman.
ReTrace:Collectingexecutiontracewithvir-tualmachinedeterministicreplay.
InProceedingsoftheAnnualWorkshoponModeling,Benchmarking,andSimulation(MoBS),June2007.
[40]C.
Yan,D.
Englender,M.
Prvulovic,B.
Rogers,andY.
Solihin.
Improvingcost,performance,andsecurityofmemoryencryp-tionandauthentication.
ACMSIGARCHComputerArchitectureNews,34(2):179–190,2006.
[41]J.
YanandB.
Randell.
Asystematicclassicationofcheatinginonlinegames.
InProceedingsoftheWorkshoponNetworkandSystemsSupportforGames(NetGames),Oct.
2005.
[42]S.
Yang,A.
R.
Butt,Y.
C.
Hu,andS.
P.
Midkiff.
Trustbutverify:Monitoringremotelyexecutingprogramsforprogressandcorrectness.
InProceedingsoftheACMSIGPLANAnnualSymposiumonPrinciplesandPracticeofParallelProgramming(PPoPP),June2005.
[43]A.
R.
YumerefendiandJ.
S.
Chase.
Trustbutverify:Account-abilityforInternetservices.
InProceedingsoftheACMSIGOPSEuropeanWorkshop,Sep2004.
[44]A.
R.
YumerefendiandJ.
S.
Chase.
Strongaccountabilityfornetworkstorage.
ACMTransactionsonStorage(TOS),3(3):11,Oct.
2007.
16