Abstract Secure checkpointing

Securecheckpointing

HyochangNama,JongKima,SungJeHonga,SungguLee

ab,*DepartmentofComputerScienceandEngineering,PohangUniversityofScienceandTechnology,San31HyojaDong,

Pohang790-784,SouthKorea

bDepartmentofElectricalEngineering,PohangUniversityofScienceandTechnology,San31HyojaDong,

Pohang790-784,SouthKorea

Abstract

Fault-tolerantcomputersystemsareincreasinglybeingusedinsuchapplicationsase-commerce,banking,andstocktrading,whereprivacyandintegrityofdataareasimportantastheuninterruptedoperationoftheserviceprovided.WhilemuchattentionhasbeenpaidtotheprotectionofdataexplicitlycommunicatedovertheInternet,therearealsoothersourcesofinformationleakagethatmustbeaddressed.Thispaperaddressesonesuchsourceofinformationleakagecausedbycheckpointing,whichisacommonmethodusedtoprovidecontinuedoperationinthepresenceoffaults.

Checkpointingrequiresthecommunicationofmemorystateinformation,whichmaycontainsensitivedata,overthenetworktoareliablebackingstore.Althoughthemethodofencryptingallofthismemorystateinformationcanprotectthedata,suchasimplisticmethodisanoverkillthatcanresultinasignificantslowdownofthetargetapplication.Amuchmoreefficientmethodistouseincrementalcheckpointing(IC),inwhichonlythemodifiedmemorydataissavedinstablestorage.ThispaperexamineswaystocombinetheoperationsrequiredtoperformICwiththoserequiredtoencryptthismemorystatedata.Ouranalysisshowthattheproposedsecurecheckpointingschemesincreasetheoverheadby1.57whencompredtoconventionalcheckpointingschemes,whichshowstheproposedschemesarefea-sible.

Ó2002ElsevierScienceB.V.Allrightsreserved.

Keywords:Checkpointing;Faulttolerance;Evaluation;Security;Cryptography

1.Introduction

Checkpointingisanimportantmethodofpro-vidingfault-toleranceingeneral-purposecomput-ingenvironments[8,14,22].Checkpointing,in

Correspondingauthor.Tel.:+82--279-2257;fax:+82--279-2299.

E-mailaddresses:hnam@secui.com(H.Nam),jkim@postech.ac.kr(J.Kim).

*whichthestateofaprocessisperiodicallysavedinstablestorage,isnormallyusedtopermitfastre-coverybyminimizingtheamountofcomputationthatmustberepeated,whenafaultoccurs.

Checkpointingisusefulfromtheperspectiveofcomputersecuritybecauseitpreventsthelossofimportantinformation,sincememorydataispe-riodicallycopiedtostablestorage.However,checkpointdatacanalsobeaserioussourceofinformationleakage.Mostcheckpointingsystemsdumptherawmemorydataofaprocessandsave

1383-7621/03/$-seefrontmatterÓ2002ElsevierScienceB.V.Allrightsreserved.doi:10.1016/S1383-7621(02)00137-6

238H.Nametal./JournalofSystemsArchitecture48(2003)237–2

itontheremotestablestorage[13,15].Thestoragelocationisnormallyremotesinceitisnecessarytoprotectthedataagainstthepossibilityofalocalnodefailure.Iftheprocesshasbeenprocessingprivate(orcritical)informationwhichshouldnotbeexposedtounauthorizedusers,itispossibleformalicioususerstoreadsomeofthisdataby‘‘sniffing’’dataasitcrossesthenetworkorsome-howgainingaccesstotheremotestablestorage.Theleakageofasingleprivatekeycanresultincatastrophicconsequencesforthepeopleusingthatkey.Withtheincreasinguseofcomputersinapplicationssuchaselectroniccommerce,bank-ing,andstocktrading,thesecurityofthedatabeingprocessedisascriticalastheassuranceofaconstantlevelofcomputersystemavailability.Theriskofinformationleakagefromstoreddataordatathatisbeingprocessedhasbeenre-portedelsewhereintheliterature[1,16,17,19,24,29].Cryptographicfilesystems(orencryptedfilesystems)havebeenproposedtoprotectlocallystoredfiles[1,24,29].Thepacketvaultprovidescryptographicallysecurelong-termstoragefornetworkpackets[16].Encryptedvirtualmemoryhasbeenproposedtoprovideconfidentialityforswapped-outdatainthememorybackingstore[17].Thesecurelogsystemgeneratesanencryptedsystemlogtopreventunauthorizedusersfromreadingthesystemlog[19].However,noneofthepreviousresearchreportedintheliteraturehasaddressedtheprotectionofinformationleakedfromcheckpointdata.

Thispaperaddressesproblemsintheexistingcheckpointingsystemwithrespecttosecurity,andproposesasecurecheckpointingsystemasamethodforprovidingcheckpointingcapabilitywhilesi-multaneouslypreventinginformationleakagethroughthecheckpointingdata.Intheproposedsystem,cryptographicmethodsareusedtoensurethatonlythecheckpointandrecoverynodesrec-ognizethecontentsofthecheckpointdata.Inter-estinglyenough,wefoundthattheoperationsusedforcheckpointingandtheoperationsusedtopro-tectthesecurityofcheckpointingsystemscanbecombined,therebyachievingsecurecheckpointingwithanoverheadlowerthanasimplesequentialapplicationofbothtypesofoperations.Thepro-posedsystemisparticularlysuitableforBatchRSA

[3]orBatchDiffie–Hellmankeyagreementsystems[23],whichrunforlongperiodsoftimeandma-nipulatecriticalprivatekeys.

Twoimportantissuesinrealizingsecurecheckpointingarecryptographickeymanagementandthebasecheckpointingscheme.Wepresentseveralmodelsrelatedtothesetwoissues.First,wepresentandcomparetwokeymanagementmodelscalledthekeydistributionmodelandthekeyagreementmodel,whichareusedtoaddresstheproblemofmanagingthesharedsecretkey.Next,wepresenttwocheckpointingschemeswithen-cryptionofthecheckpointdata.Oneisreferredtoassecureincrementalcheckpointing(SIC)andtheotherassecureprobabilisticcheckpointing(SPC).Basedonanevaluationoftheabovekeyman-agementmodelsandcheckpointschemes,these-curecheckpointingsystemisproposedasacombinationofthekeyagreementmodelandSPC.Finally,theperformanceofallthesecurecheck-pointingschemesconsideredisanalyzedusingbothanalyticmodelsandexperimentalresults.Theremainderofthispaperisorganizedasfollows.Section2describesthemajorpointstobeconsideredinthisresearch.Section3presentsseveralsystemmodelswhichtaketheseconsider-ationsintoaccount.InSection4,weproposeamodelforsecurecheckpointing.Section5analyzesthecheckpointoverheadoftheproposedcheck-pointingschemeandmeasurestheperformanceofsecurecheckpointinginrealenvironments.Finally,wepresentourconclusionsinSection6.2.Researchissues

Inthissection,wediscusstwomainissuestobeconsideredinbuildingasecurecheckpointingsystem.Oneistheissueofmakingthecheck-pointingsystemsecureandtheotheristheissueofminimizingthecheckpointingoverheadwhense-curityfunctionsareincluded.Thefollowingtwosubsectionsbrieydescribeeachsubjectandtherelatedresearchissues.2.1.Security

Thissubsectionpresentssecurityproblemsingeneralcheckpointingsystemsanddescribessolu-

H.Nametal./JournalofSystemsArchitecture48(2003)237–2239

tionapproachesbasedonvariousexistingsecurityenhancementmethods.Then,securityproblemsconsideredinourresearcharepresented.2.1.1.SecuritythreatsincheckpointingsystemsUsuallyacheckpointingsystemconsistsofcheckpointinghostsandtheremotestablestorage,whichisimplementedwitharemotefileserverconnectedtoanetwork.Acheckpointinghostrunsapplicationsandtakescheckpointsperiodi-cally(oraperiodicallyinsomesituations).Binarycodesofcheckpointingapplicationsaremainlyplacedonalocaldisk.Whenanapplicationischeckpointed,thecheckpointdataistransferredfromthelocalhosttotheremotestablestorageviaanetworkconnection.

Securitythreatsinalocalcheckpointinghostexistinoneofthefollowingthreeplaces:compu-tationcontentinthevolatilememory,computa-tioncontentintheswaparea,orbinaryprogramsinthelocaldisk.Datainthevolatilememorycanbesniffedormodifiedtosetaninformationortoexploitahole.Dataintheswapareacanbere-tainedaftertheprocessisterminated.ThesedatacanbeasourceofinformationleakageaspointedoutbyHarkinsetal.[17].Binaryprogramsinthelocaldiskmayalsocontaincryptographickeysorothersecuritysensitivedata,aspointedoutbyShamiretal.[20].Moreover,backdoors,whicharepiecesofcodethatgiveahackeraccesstothesystemwithoutnormalmethodsofaccessau-thentication,canbeinsertedintotheoriginalbi-naryprogrambythehacker.

Thenetworkisoneofthecommonplaceswheresecuritythreatsexist.Checkpointingdataistransferredfromalocalhosttotheremotestablestoragewhenacheckpointoccurs,andfromtheremotestablestoragetoarecoveryhostwhenarecoveryisstarted.Checkpointdatacanbesniffedormodifiedonthenetworkduringthisprocess.Packetsniffingisoneofthecommonattacksusedtoreaddatasentoveranetwork[28]andthe‘‘maninthemiddleattack’’[9]isanothercommonattackmethodwhichmodifiesnetworkdata.

Theremotestablestorageincheckpointingsystemsisacommonsharedstorageareawhichmaybeaccessedbyanyoneinthelocalsystem.Forthisreason,thestoreddatainthesharedstorageis

easiertosniff,modify,ordeletecomparedtodatainotherareas.Evendeleteddatainamagneticdiskcanberecovered[4]andaccessedbyanat-tacker.Oneexampleofastoreddatamodificationattackinanincrementalcheckpointing(IC)sys-temisreplacingnewcheckpointdatawithanoldone.

2.1.2.Relatedresearchesandresearchgoals

Manyindependentdataprotectionmethodshavebeenproposedfortheabovetypesofsecuritythreats.Wereviewthemethodsproposedineachareaandtheapproachofcombiningthemethodsforcheckpointdataprotection.Thenwepresentoursecuritytargetsinthispaper.

Toexploitaprocessinthelocalsystem,theprivilegeoftheowneroftheprocessorahigherlevelofprivilegemustbeachieved.Buttheseareprotectedbymonitoringthebehaviorofprocessesorusersinthelocalsystem,whichissupportedbyintrusiondetectionsystemssuchasInternetSecu-ritySystems(ISS)providedbyRealSecure[25].Theproblemintheswapareaisaddressedwiththeswapencryptionproposedin[17].Tosolveproblemsofbinaryprogramsinthelocaldisk,encryptedfilesystems,whichensuretheconfi-dentialityofstoreddata,orsystemintegritytoolssuchasTripwirecanbeadopted[6].

Toprotectattacksonnetworkdata,VirtualPrivateNetwork(VPN)systemssuchasTLS[30]orIPSec[26]canbeemployedoncommunicationchannels.DeletednetworkdatacanberecoveredbynetworkprotocolslikeTCP,whichprovidessequencenumbercheckingandretransmission.Topreventproblemsonstoreddatainremotedisks,onlyacryptographicfilesystem[24,29],whichprovidesconfidentialityofstoredfilesthroughencryption[1,24],andTripwire[6],whichprovidesdataintegrityofstoredfileswithdatahash,canbedeployed.

Allofthemethodsmentionedabovecanbecombinedtomakeacheckpointingsystemsecure,butitwillhavemanyredundantoperations.Whenaprocessischeckpointed,checkpointdataaretransferredthroughthenetworkandstoredintheremotestablestorage.IfTLSforlinkencryptionandacryptographicfilesystemforsecuringtheremotestablestorageareusedtomakea

240H.Nametal./JournalofSystemsArchitecture48(2003)237–2

checkpointingsystemsecure,twoencryptionandonedecryptionstepsforthesamedataareneededforasingledatatransferofcheckpointeddata––andtheseareredundantoperations.Eventhesamehashoperationcanbeappliedtwicefordatain-tegritycheckingintheaboveapproach.

Ourresearchgoalistoprovideanefficientse-curecheckpointingsystembyfocusingonthefol-lowingresearchtargets:(1)protectinginformationleakagebynetworksniffing,(2)detectingalterationofnetworkdata,(3)protectinginformationleak-agefromstoredcheckpointdata,(4)detectingal-terationofstoredcheckpointdata,(5)detectinginformationdestructiononstoredcheckpointdata.2.1.3.Functionsrequiredbysecuritysystems

Thebasicfunctionalitiesrequiredtocoverbasicsecuritytargetsaddressedintheprevioussubsec-tionareconfidentialityandintegrity.Confidenti-alityreferstothedifficultyofgettingaccesstosensitiveinformationwithoutvalidauthorization.Checkpointdatashouldbestoredinstableandsecurestoragetoblockanyunauthorizedaccess.Also,thecontentsofcheckpointdatashouldnotberevealedtoanyunauthorizedparty,evenwhenthedataisleakedtothembysomemeans.Integ-rityreferstohowmuchwecantrusttheinfor-mationstoredinthedata.Thecontentsofcheckpointdatacanbealteredbyanunauthorizedpartyifthesecuritysystemiscompromised.Withoutknowingwhetherthestoredcheckpointdataisgenuine,itisriskytorecoverfromafaultbyusingthecheckpointdata.Cryptographicmethodssuchasdataencryptionandmessageauthenticationcodescanprovidebothoftheserequiredfunctionalities.Cryptographicmethodssuchasencryptionarecommonlyusedtoprovideconfidentialityforstoredfiles.However,crypto-graphicfilesystemsareunsuitableforsecurecheckpointingsystembecauseoftheirinsufficientkeymanagementfunctions[12].Theremustbeamethodformanagingthecryptographickeysse-curelyforboththecheckpointandrecoverynodes,whichmeansthatasecurekeymanagementmechanismmustbeprovidedtoenableautomatedandsecurerecoveryonacheckpointingsystem.Ifamalicioususermodifiescheckpointdata,recoverybyusingthecorruptedcheckpointdata

canleadtoanothersystemfailureorintroduceinformationalterationandbackdoorsthatcanbecomesubsequentsecurityholes.Therefore,dataintegrityshouldalsobeprovidedtomakeacheckpointingsystemsecure.AsimplemethodofverifyingdataintegrityistocalculateasignaturekeyforagivensetofdatausinghashfunctionslikeMD5orSHA1[9]beforeitisstoredandafteritisretrieved(forrecovery).Butusingonlydatahashingcannotdetectthere-placementofanewcheckpointwithanoldone,oneoftheinformationalterationattacksusedonstoredcheckpointdata.Tocoversuchanattack,thesignaturekeyiscreatedwithaMAC(MessageAuthenticationCode)1function,notwithasimplehashfunction,anddifferentkeysforMACsareappliedtoeverycheckpoint.2.2.Checkpointing

Whencryptographicoperationsareaddedtoacheckpointingsystem,thetotaloverheadofthecheckpointingitselfincreases.Tomakethesecurecheckpointingsystempractical,itisimportanttominimizethischeckpointingoverhead.Whentherearealternativewaystochoosefrom,itismoredesirabletofocusonreducingthecheckpointingoverheadforthefault-freesituation,sincethiswillbethecommoncase.2Inordertocreateasecurecheckpointingschemewithlowoverhead,wefirstselectedthecheckpointingschemewhichrequiresalowover-head.Manycheckpointingschemestoreducetheoverheadinthefault-freesituationhavebeenproposed[10,13,15].Amongthoseschemes,ICbasedonmemorypageprotectionhasbeenoneofthemostsuccessfulschemesinreducingtheover-headofsavingcheckpointstostablestorage[15].

1Sometimes,MACfunctionsarereferredtoaskeyedhashfunctions,becauseawellknownmethodofconstructingMACfunctionsistouseahashfunctionasabaseoperationandauthenticationkeysasinputs.Forexample,HMAC-SHA1isimplementedwithSHA1andHMAC-MD5isimplementedwithMD5[7].2Sincecheckpointingismerelyanoverheadinafault-freesituation,weusetheterm‘‘overhead’’insteadof‘‘executioncost’’or‘‘checkpointcost.’’

H.Nametal./JournalofSystemsArchitecture48(2003)237–2241

However,oneproblemwithincrementalcheckingisthatthegranularityofmodifieddatacanonlybedeterminedtowithinapagesize,whichcanresultinstorageofalotofunnecessary(unmodified)data[10].ToovercomethisprobleminIC,theauthorspreviouslyproposedamethodreferredtoasprobabilisticcheckpointing(PC),whichusesamemoryblocksignaturefordetectionofmodi-fieddata[10].Inthenextsection,IC3andPCareinvestigatedaspossiblebasecheckpointingschemesforasecurecheckpointingsystem.

3.Systemmodels

Inthissection,systemmodelsforkeymanage-mentandcheckpointingareinvestigated.3.1.Keymanagementmodels

Weconsidertwomodelsforkeymanagement:thekeydistributionmodelandthekeyagreementmodel.Fig.1showsthekeydistributionmodel,inwhichthekeyserverprovidesanencryptionkeyandaMACkeyfordataintegritytothecheck-pointnodewhenacheckpointingapplicationisinitiated.Usingthesekeys,thecheckpointnodeencryptscheckpointdataandgeneratesMACs,thensavesthemtotheremotestablestorage.Whenafaultoccursinthecheckpointnode,thekeyservertransmitsthekeystotherecoverynodetoenableittodecryptthecheckpointsforthere-coveryandverifytheintegrityofcheckpointdata.Inthekeyagreementmodel,showninFig.2,secretkeysaresharedbythecheckpointnodeandtherecoverynodeusingakeyagreementproto-col4beforeanewcheckpointingapplicationisinitiated.Withthesharedsecretkeys,thecheck-pointingnodeencryptscheckpointdataandgen-eratesMACs.Alsowiththekeystherecovery

3Inconventionalusage,‘‘IC’’means‘‘memorypageprotec-tionbasedIC.’’4Therearevariouskeyagreementprotocolsintheliterature,e.g.keyagreementbasedonsymmetrictechniques,includingBlomÕssymmetrickeypre-distributionsystem,keyagreementbasedonasymmetrictechniques,includingDiffie–Hellmankeyagreement,ElGamelkeyagreement,etc.[9].

Encryption KeyKeyServerDecryption KeyCheckpointingRecoveryNodeNodeEncryptedFileEncryptedCheckpointServerCheckpointDataDataStableStorageFig.1.Thekeydistributionmodel.CheckpointingKey NegotiationRecoveryNodeNodeEncryptedFileCheckpointServerEncryptedCheckpointDataDataStableStorageFig.2.Thekeyagreementmodel.nodeverifiestheintegrityofcheckpointdatabygeneratingMACsanddecryptstheencryptedcheckpointdatatoactivatearecoverywhenafaultoccursinthecheckpointnode.

Thetwomodelsabovearecomparedwithrespecttofiveaspects,andtheresultsofthecomparisonaresummarizedinTable1.Whencomparingtheadditionalcostrequiredatthecheckpointsetuptime,thekeydistributionmodelrequireskeysetupbetweenthekeyserverandthecheckpointnode,whilethekeyagreementmodelrequireskeyagreementbetweenthecheckpointnodeandtherecoverynode.Thus,bothmodelshavesimilaroverheadswithrespecttothecheck-pointsetuptime.

Whencomparingtheadditionalcostatthere-coverytime,thekeydistributionmodelrequirestimetotransmitkeysfromthekeyservertotherecoverynode.Thekeyagreementmodel,how-ever,doesnotrequireanyadditionalcostatre-coverytime,sincetherecoverynodereceivesthe

242H.Nametal./JournalofSystemsArchitecture48(2003)237–2

Table1

Comparisonofkeymanagementmodels

Keydistributionmodel

AdditionalcostatcheckpointsetupAdditionalcostatrecoveryAdditionalfaultHardwareoverheadSecuritytightness

Keysetupcostbetweenakeyserverandacheckpointnode

Keytransmissioncostfromthekeyservertotherecoverynode

FaultonthekeyserverKeyservernodeAttherecoverytime

Keyagreementmodel

KeyagreementcostbetweenacheckpointnodeandarecoverynodeNone

FaultontherecoverynodeNone

Attheinitialsetuptime

secretkeysattheinitialcheckpointsetuptime.Thus,withrespecttotherecoverytime,thekeyagreementmodelrequireslesstimeandsimplerexecutionstepsthanthekeydistributionmodel.Forfaulttolerance,thekeydistributionmodelhastoovercomefaultsonakeyserverbecause,ifthekeyserverbecomesfaulty,therecoveryofprocessesrelyingonthefailedkeyservercannotbetrusted,andanewapplicationtobecheckpointedcannotbereliablysetup.Thesetupofanewap-plicationtobecheckpointedcanonlybedoneafteranewnon-faultykeyserverhasbeenas-signed.Ifthekeyserverisre-assigned,newkeysmustalsobetransmittedtothecurrentlyrunningcheckpointedapplications.Thisrequirestheinitialkeysetupproceduretobere-executed.Ontheotherhand,thekeyagreementmodelhastoovercomefaultsontherecoverynode.Ifthere-coverynodebecomesfaultywhilethecheck-pointedapplicationisexecuting,anotherrecoverynodemustbeassignedandthekeyagreementstepsmustbeexecutedagain.

Whenconsideringthehardwareoverhead,thekeydistributionmodelneedsadedicatedkeyser-ver,whilethekeyagreementmodeldoesnot.Ontheotherhand,thekeyagreementmodelassignsarecoverynodewhenanapplicationtobecheck-pointedisinitiallystarted,whilethekeydistribu-tionmodelassignsarecoverynodeonlywhenthereisafaultonthenodeexecutingacheck-pointedapplication.Thus,thekeydistributionmodelhasmoreflexibilityinchoosingrecoverynodesthanthekeyagreementmodel.

Thefinalissueisthesecuritytightnessofthetwomodels.Forexample,attherecoverytime,afakenodemaypretendthatitistherecoverynodeandrequestakeyservertotransmitthekeyinthe

keydistributionmodel.Topreventsuchdeception,thekeyservershouldhaveamechanismtorec-ognizelegitimaterecoverynodes.Similarly,thekeyagreementmodelshouldalsohaveamecha-nismtorecognizealegitimaterecoverynodewhennegotiatingkeysattheinitialkeysetuptime.Thedifferencebetweenthetwoschemesisthetimewhentheoverheadofauthenticatingalegitimaterecoverynodeisincurred.

Overall,intheauthorsÕopinion,thekeyagree-mentmodelispreferabletothekeydistributionmodelsincetheformerdoesnotrequireaseparatekeyserverandhasaloweroverheadatrecoverytime.

3.2.Checkpointingschemes

Inthissubsection,weconstructandexaminetwocheckpointingschemes,referredtoasSICandSPC,thatcombinetheexistingcheckpointingschemeswithcryptographicoperations.

3.2.1.Secureincrementalcheckpointing

ICisaschemethatusesthepageprotectionmechanisminoperatingsystemtodetectadirtypageandsavesonlythememorypagesthathavebeenmodifiedsincethelastcheckpoint.Attheveryfirstcheckpoint,theentiresetofmemorystateofaprocessissavedintheremotestablestorage.Atalllatercheckpoints,onlythedirtymemorypagesaresavedtotheremotestablestorage[15].

SICsimplyincorporatesasecuritymethodtothecheckpointdatatobesavedinthestablestorage.Attheveryfirstcheckpoint,aMACoftheentiresetofmemoryareaiscalculatedfordataintegrity,andtheentiresetofmemorypagesare

H.Nametal./JournalofSystemsArchitecture48(2003)237–2243

encryptedandsavedforconfidentiality.Atalllatercheckpoints,aMACofdirtypagesarecalculatedandonlythedirtymemorypagesareencryptedandsaved.TherearetwochoicesingeneratingMACsfordataintegrity:

Choice1:generateithMACofdirtypagesatthe

ithcheckpoint;

Choice2:regenerateaMACoftheentiresetof

memorypagesattheithcheckpoint.Choice1isfasterthanChoice2inthefault-freesituationsinceChoice1onlygeneratesaMACofthedirtypagesafterthefirstcheckpoint.However,Choice1requiresmorespacethanChoice2sinceMACsmustbesavedateachcheckpointinChoice1.Moreover,Choice2ismuchfasterthanChoice1atrecoverytimesinceChoice2needstoverifyonlythelastMACfordataintegrity,whileChoice1hastoverifyallMACsaccruedfromtheinitialcheckpoint.

3.2.2.Secureprobabilisticcheckpointing

PCisanICschemewhichusesblocksignaturestodetectdirtymemoryareas[10].Inthischeck-pointingscheme,aprocessÕsmemoryareaisdi-videdintoblockswhicharelargerthanamemorywordbutsmallerthanamemorypage.Attheveryfirstcheckpoint,theentirememorystateofaprocessissavedintheremotestablestorage,andsignaturekeysaregeneratedforeachmemoryblock.Atalllatercheckpoints,signaturekeysaregeneratedforeachblock.Thenewlygeneratedsignaturekeysarecomparedwiththecorre-spondingsignaturekeysgeneratedinthepreviouscheckpoint.Ifthekeysdiffer,itmeansthatthememoryblockhaschanged,andthusmustbesavedinstablestorage.

SPCisa‘‘secure’’versionofPC.InSPC,theentiresetofmemoryblocksareencryptedandsavedatthefirstcheckpoint.InsteadofgeneratingaMACoftheentirememoryspaceordirtyarea,aMACofeachblockisgeneratedforthefollowingpurposes:

•BycomparinganewMACtoanoldMACofthesamememoryblock,itcanbedeterminedwhethertheblockisdirtyornot.

•Whenrecoveryhastobeperformed,thedataintegrityofcheckpointdataisexaminedbycomparinganewlygeneratedMACofasavedmemoryblockincheckpointdatatotheprevi-ouslysavedMACofthesameblock.NotethatMACsaregeneratedforeverymemoryblockandthatthegeneratedMACsareusedforbothdetectionofadirtymemoryblockandtocheckthedataintegrityofeachblock.Thus,anadditionalsignaturegenerationfunctionisnolongerneeded.

Atalllatercheckpoints,thecheckpointingmechanismisthesameastheoriginalPCmethodexceptthatthesignaturegenerationfunctionisreplacedwithaMACfunctionfordataintegrity.OnemajorpotentialproblemwithPCisalias-ing[10].However,thechecksumsizeofaMACfunctionislarger––128bitsforMD5and160bitsforSHA1[9]––thanthatofthesignaturekey––bits[10]––usedintheoriginalPCscheme.ThismeansthatthealiasingrateofSPCismuchlowerthanthatoftheoriginalPCmethodduetotheuseofaMACfunctionasitssignaturegenerationfunction(e.g.,a10À20aliasingrateforMD5and10À24forSHA1[9]).Whencomparingtheseali-asingrateswiththatofPC,whichusesabitsignature(withaliasingrate1:58Â10À7),theali-asingratesoftheseMACfunctionsarenegligible.Infact,whenaMACfunctionisusedasthesig-naturegenerationfunction,thealiasingproblemcaneffectivelybeignoredduetoitsunlikelyprobabilityofoccurrence.

4.Theproposedmodel:asecurecheckpointingsystem

Basedonthefindingsintheprevioussection,wesuggestamodelforasecurecheckpointingsystemwhichcombinesthekeyagreementmodelwiththeSPCscheme.

4.1.Systemmodelandoperations

4.1.1.Proposedsystemmodel

Thebasicdescriptionoftheproposedsystemmodelisasfollows:

244H.Nametal./JournalofSystemsArchitecture48(2003)237–2

•Allnodesinthesystemaredividedintotwogroups:checkpointnodesandrecoverynodes.Mostnodesarecheckpointnodesandexecutecheckpointingapplications.Thenumberofre-coverynodesissmall(e.g.,afewsparenodes,asin[11]),andareonlyusedforsystemrecov-erywhenacheckpointnodebecomesfaulty.•Bothcheckpointandrecoverynodesshouldhaveamechanism,suchastheonepresentedin[21,27],toauthenticateeachother.Afakenodemaypretendthatitistherecoverynodeandattempttointerceptasecretkey.Topre-ventsuchdeception,amechanismtorecognizelegitimaterecoverynodesisnecessary.

•BothcheckpointandrecoverynodesshouldhaveakeynegotiationmechanismsuchasIn-ternetKeyExchange(IKE)[5].Asharedsecretkeycanbeestablishedbetweenacheckpointandarecoverynodebyusingthenegotiationmechanismatanytime.

4.1.2.Pre-executionsteps

Beforeanapplicationtobecheckpointedisexecutedonacheckpointnode,thefollowingtwostepsareexecuted:(1)recoverynodeselectionand(2)keynegotiation.Atstep(1),oneoftherecoverynodesisselected.Ifthepossibilityofonlyasinglefaultisconsideredatanygiventime,arecoverynodecanbeusedtocoverseveralcheckpointnodesatthesametime.Ifweconsideramorecomplexfaultmodel,morecomplicatedrecoverynodeselection(orallocation)mechanismsshouldbedevised,whichisbeyondthescopeofthispaper.Weassumethatasimplemethod,suchasroundrobin,isadoptedforthenodeselectional-gorithm.Atstep(2),sharedsecretkeysarees-tablishedbetweenthecheckpointnodeandtheselectedrecoverynode.5Withthissharedsecretkey,thecheckpointnodewillencryptcheckpointdataandgenerateMACs,andtherecoverynodewilldecryptthecheckpointdataandverifythe

5Inourcurrentmodel,wedonotconsiderfaultsinthekeyestablishmentprotocol.Buildingafail-safekeyestablishmentprotocolisaseparatecomplexresearchtopicwhichwearecurrentlyinvestigating.

integrityofcheckpointdatabycomparingMACswhenafaultoccursinthecheckpointnode.4.1.3.In-executionsteps

Fortheactualcheckpointingandrecovery,thesecurecheckpointingsystemwilluseSPC.Atthefirstcheckpointing,theentiresetofmemoryblocksareencryptedusingthesharedsecretkeyandsavedinstablestorage.Also,aMACofeachmemoryblockisgeneratedandsavedinbothlocalmemoryspaceandstablestorage.TheMACssavedinstablestorageisalsoencryptedusingasharedsecretkeyforprotection.

Atalllatercheckpoints,MACsaregeneratedforeachblock.ThenewlygeneratedMACsarecomparedwiththecorrespondingMACsgener-atedinthelocalmemoryspaceatthepreviouscheckpoint.IftheMACsdiffer,itmeansthatthememoryblockhaschanged,andthusthememoryblockmustbesavedinstablestorage.Hence,thesechangedmemoryblocksareencryptedandsavedinstablestorage.AlsothecorrespondingMACsareupdatedinthelocalmemoryandsavedinstablestorageafterencryption.

4.1.4.Recoverysteps

Whenafaultoccursinacheckpointnode,thecorrespondingrecoverynodeexecutesthefollow-ingsteps:(1)checkcheckpointdataalterationand(2)recovermemorydataandprocessstateusingcheckpointdata.Atstep(1),MACforeachcheckpointblockisgeneratedandcomparedwiththecorrespondingMACsaveduntilthelastcheckpoint.Thisstepisrequiredtopreventthealterationofcheckpointdatabysomeoneelse.Weconsiderthatprotectionofstablestorageandre-coveryofalteredcheckpointdataisthebeyondthescopeofthispaperandthusisnotconsideredinthispaper.Hence,ifoneofthemdiffers,reportthefactandstoptherecovery.Otherwise,executestep(2)asanormalrecovery.

Whenthereisafaultintherecoverynode,anewrecoverynodeisselected.Theexecutionofpro-cessesatcheckpointnodeistemporarilyblocked.Afterthenewrecoverynodeisselectedandasharedsecretkeyisnegotiated,theexecutionofprocesseswhichhavebeenblockedbecauseofthefaultisresumed.Attheresumption,allprocesses

H.Nametal./JournalofSystemsArchitecture48(2003)237–2245

dothefirstcheckpointingstepagainandsavetheentirememoryblocksandMACsencryptedusinganewsharedsecretkeyinstablestorage.4.2.Securityoftheproposedsystem

Inthisresearch,wesetfivesecuritygoalsforcheckpointingsystem:(1)protectionofinforma-tionleakagebynetworksniffing,(2)detectionofalterationofnetworkdata,(3)protectinginfor-mationleakagefromstoredcheckpointdata,(4)detectingalterationofstoredcheckpointdata,and(5)detectinginformationdestructiononstoredcheckpointdata.Wewilldescribehowthesegoalsachievedintheproposedsystem.

Protectionofinformationleakagebynetworksniffing:Weassumethatthekeynegotiationpro-cedureissecurefromnetworksniffingsothatthesharedkeybetweencheckpointandrecoverynodesissecure.InformationtransferredthroughthenetworkischeckpointdataandMACs.Alltheinformationtransferredisencryptedusingthesharedkeytoprotectfromnetworksniffing.Hence,theproposedsystemissecurefrominfor-mationleakagebynetworksniffing.Whenthereisafaultinrecoverynode,newrecoverynodeisse-lectedandsharingsecurekeyandtransferringencrypteddataisrepeated.

Detectionofalterationofnetworkdata:Asim-plemethodofverifyingdataintegritylikeMD5orSHA1isusedtodetectthealterationofnetworkdata.However,theproposedsystemhasmorein-tegritycheckingmechanisms.MACisalsousedforintegritychecking,althoughtheintegritycheckisperformedwhenrecoveryisrequired.

Protectinginformationleakagefromstoredcheckpointdata:Theprotectionofstoredcheck-pointdatamainlydependsonthesecuritylevelofstablestorage.However,intheproposedsystem,storeddataistheencrypteddatareceivedfromthecheckpointnode.Thesharedkeyusedforen-cryptionisonlyknowntothecheckpointandtherecoverynodes.Anyonewhocanaccessthestoreddatainstablestorageneedsthesharedkeytoknowthecontentincheckpointdata.

Detectingalterationofstoredcheckpointdata:Thedatastoredinstablestoragecanbemodifiedmeaningfullybytheintruderwhoknowstheshared

key.Toincreasethesecuritylevel,weuseseparatesharedkeysforencryptingcheckpointdataandMACs.Tomodifythecheckpointdatameaning-fully,itshouldalsomodifytheMACforthecor-respondingcheckpointdata.Todothat,theintrudermustknowtwoseparatesharedkeys.Weconsiderthatitisveryhardtoknowtwoseparatekeysatthesametime.Aslongasonlynotmorethanonesharedkeyisleaked,thealterationofcheckpointdataorMACscanbefoundbycheck-ingtheintegritywhentherecoveryisrequired.Detectinginformationdestructiononstoredcheckpointdata:Storedcheckpointdataisaccessedonlywhenrecoveryisrequired.Thedestructiononstoredcheckpointdataiseasilydetectedbytheintegritycheckperformedbytherecoverynode.5.Performanceanalysis

Inthissection,weanalyzeandcomparetheoverheadofthecheckpointingschemesdescribedintheprevioussection:page-basedIC,PC,SIC,andSPC.Toanalyzethenecessarycheckpointingoverhead,simplifiedanalyticmodelsarederivedforeachscheme.Also,measurementsaretakenonanactualsystemtodeterminerealisticvaluesfortheparametersderived,andtocalculateandmeasuretheactualcheckpointingoverheadsforeachscheme.

5.1.Performanceoverheadmodel

5.1.1.Notation/symbols

Theperformanceoverheadofthefouralgo-rithmsconsideredareevaluatedusingthenota-tion/symbolsshowninTable2.

5.1.2.Analysismodels

SincethefourschemesconsideredarebasedonIC,thefirstcheckpointisafullcheckpointthatstoresallofthedatainthememoryspaceofatargetprocess.Table3showsthecostofthefirstcheckpointforeachscheme.66IthasalreadybeenmentionedthattherearetwochoicesforthegenerationofMACsinSIC.Inthisanalysis,Choice2isusedforsimplicity.

246H.Nametal./JournalofSystemsArchitecture48(2003)237–2

Table2

Notation/symbolsusedintheanalysisNotationTpwTprTpcTpeTpfTpsTsigTmacTinTpnTsinTspnNpNmNbNpeNseRpRb

Description

DiskwritetimeperpageDiskreadtimeperpagePerpagecomparisontimePerpageencryptiontimePage-faulthandlingtime

Timetosetupapageintoread-onlyGeneratingasignatureforapageinPCGeneratingaMACforapagenthcheckpointingtimeusingICnthcheckpointingtimeusingPCnthcheckpointingtimeusingSICnthcheckpointingtimeusingSPCNumberofbytespermemorypage

Numberofbytesinthevirtualmemoryofacheckpointingprocess

Numberofbytesperblock

NumberofbytesofasignaturekeyinPCNumberofbytesofasignaturekeyinSPCDirtyprobabilityofamemorypageDirtyprobabilityofamemoryblock

checkpointingscheme.Thus,onlytheFii,Fpi,Fsii,andFspivaluesaremeasuredandcompared.Thesearereferredtoasthenormalizedcheckpointingoverhead.

5.2.1.Experimentalenvironmentsandparametervalues

Overheadmodelsforcheckpointinganalyzedintheprevioussubsectionusemanysystem-depen-dentparameters.Thevaluesoftheseparametershavebeendeterminedbyexperimentsforourevaluation.Thesystemenvironmentusedintheevaluationisasfollows:(1)ThecheckpointinghostisaSUNSPARC-station10runningSUN-OS4.1.3.(2)Theremotestablestorageiscon-nectedby10MbpsEthernet.(3)EachhostisequippedwithMBphysicalmemoryandapagesizeof4096bytes.

Tpr,Tpw,Tpf,andTpsareparametersdependentonlyonsystemcharacteristics.Table5showsthemeasuredvaluesforthesystemdependentpa-rametersdescribedabove.

CheckpointingschemedependentparametersareTpe,Tsig,andTmac.IntheoriginalPCmethod,a1-bitShift-RotateXORfunctionwasusedasthesignaturegenerationfunction,andthesizeofeachsignaturewasassumedtobebits.InthesecurecheckpointingschemesSICandSPC,HMACwithMD5,whichgeneratesa128-bitmessageauthen-ticationcode,isusedastheMACfunction,andDESisusedastheencryptionalgorithm.Table6

Asubsequentcheckpointsavesonlythedirtyarea.Thesizeofasubsequentcheckpointisveryimportantforapplicationshavingalonglifetime.Thecostoftheith(iP2)checkpointisshowninTable4.

5.2.Performanceevaluation

EachequationinTables3and4isoftheformTx¼ðNm=NpÞFx,wherexrepresentsaparticular

Table3

CostofthefirstcheckpointTimeTi1Tp1

Description

¼Timetosetallmemorypagestoreadonlyþtimetowriteallmemorypagestodisk

¼Timetogeneratesignaturesforeachmemoryblockþtimetowriteallmemoryblockstodiskþtimetowritesignaturestodisk¼TimetosetallmemorypagestoreadonlyþtimetoencryptallmemorypagesþtimetogenerateaMACforallmemory

pageþtimetowriteaMACtodiskþtimetowriteallmemorypagestodisk

¼TimetogenerateMACsforeachmemoryblockþtimetowriteMACstoadiskþtimetoencryptallmemorypagesþtimetowriteallmemoryblockstodisk

Equation

¼ðNm=NpÞTpsþðNm=NpÞTpw¼ðNm=NpÞðTpsþTpwÞ

¼ðNm=NpÞTsigþðNm=NpÞTpw

þðNm=NbÞNpeð1=NpÞTpw

¼ðNm=NpÞðTsigþTpwþðNpe=NbÞTpwÞ

¼ðNm=NpÞTpsþðNm=NpÞTpeþðNm=NpÞTmac

þðNse=NpÞTpwþðNm=NpÞTpw¼ðNm=NpÞðTpsþTpeþTmac

þðNse=NmÞTpwþTpwÞ

¼ðNm=NpÞTmacþðNm=NbÞNseð1=NpÞTpw

þðNm=NpÞTpeþðNm=NpÞTpw

¼ðNm=NpÞðTmacþðNse=NbÞTpwþTpeþTpwÞ

Tsi1

Tsp1

H.Nametal./JournalofSystemsArchitecture48(2003)237–2

Table4

CostofthesubsequentcheckpointTimeTii

Description

¼Timetohandlepagefaultþtimetosetdirtypagestoreadonlyþtimetowritedirtypagestodisk

¼Timetoreadsignaturekeysfromdiskþtimetogeneratesignaturesandcompareentirememoryblocksþtimetowriteencodekeystodiskþtimetowritedirtyblockstodisk¼TimetohandlepagefaultþtimetosetdirtypagestoreadonlyþtimetoencryptdirtypagesþtimetowriteencryptedpagestodiskþtimetogenerateaMACforallmemorypageþtimetowriteaMACtodisk

¼TimetoreadMACsfromdiskþtimetogenerateMACsandcompareentirememoryblocksþtimetowriteMACstodiskþtimetoencryptdirtyblocksþtimetowriteencryptedblockstodisk

Equation

247

Tpi

Tsii

Tspi

¼ðNm=NpÞTpfRpþðNm=NpÞTpsRp

þðNm=NpÞTpwRp

¼ðNm=NpÞðTpfþTpsþTpwÞRp

¼ðNm=NpÞðNpe=NbÞTprþðNm=NpÞTsig

þðNm=NpÞðNpe=NbÞTpwþðNm=NpÞRbTpw¼ðNm=NpÞððNpe=NbÞTprþTsigþðNpe=NbÞTpw

þTpwRbÞ

¼ðNm=NpÞTpfRp

þðNm=NpÞTpeRpþðNm=NpÞTpwRpþðNm=NpÞTmacþðNse=NpÞTpw

¼ðNm=NpÞðTpfRpþTpsRpþTpwRpþTmac

þðNse=NmÞTpwÞ

¼ðNm=NpÞðNse=NbÞTprþðNm=NpÞTmac

þðNm=NpÞðNse=NbÞTpwþðNm=NpÞRbTpeþðNm=NpÞRbTpw

¼ðNm=NpÞððNse=NbÞTprþTmacþðNse=NbÞTpw

þTpeRbþTpwRbÞ

Table5

Valueofsystemdependentparameters(inms)Tpr4.135

Tpw10.491

Tpf0.45

Tps0.00057

Table6

Valueofcheckpointingschemedependentparameters(inms)Tpe6.71

Tsig0.24

Tmac0.96

showsthemeasuredvaluesforthecheckpointingschemedependentparameterslistedabove.

ByapplyingeachparametervalueinTables5and6,wederivedmoresimplifiedformsofana-lyticmodelsasinTable7.RpandRbintheequationsofTable7areapplicationdependentparameters.WeusedtheRpandRbvaluesmea-suredin[10].Table8showstheexperimentalval-uesforeachapplication.Thefourapplications7listedinTable8areasfollows:

Table7

SimplifiedFxvaluesNtsnFi1Fp1Fsi1Fsp1FinFpnFsinFspn

Simplified

10:39157

10:731þ83:928ð1=NbÞ18:32

18:08þ167:856ð1=NbÞ10:94157Rp

0:24þ150:088ð1=NbÞþ10:491Rb0:96þ17:651Rp

0:96þ234:016ð1=NbÞþ17:201Rb

ThethreeapplicationsexceptBRSAarenot,bythemselves,typicalsecurityapplications.However,theyarebasicapplica-tionsandmayusedasapartofasecurityapplication.Thesefourapplicationswerechosen,thoughthreeofthemarefarfromrealsecurityapplications,becauseoftheirdiversechar-acteristicsforthedirtyratesofmemoryblocks,whichhasasignificantinfluenceontheperformanceofthefourcheck-pointingschemesbeingevaluated.

7•Matmulisa1600Â1600matrixmultiplicationprogram;

•BRSAisaprogramtocompute512-bitRSAdecryptionoperationsatacomputationalcostapproachingthatofonenormaldecryption;•Lufcatisaprogramthatfactorsa2048Â2048matrixusingLU-decomposition;

•Cell30isaprogramthatexecutesa4096Â4096gridofcellularautomataforfiftygenerationswithaseedof30%.

248H.Nametal./JournalofSystemsArchitecture48(2003)237–2

Table8

RpandRbvaluesforvariousapplicationsApplication

Rb32

MatmulBRSALufactCell30

0.02990.05620.15240.3423

0.02990.05840.15560.5218

1280.02990.06130.16530.7148

2560.02990.06290.17820.8296

5120.03000.08870.20430.8553

10240.03000.120.250.8563

20480.03020.17530.35610.8565

Rp40960.03040.28220.57300.8687

5.2.2.Measuredfirstcheckpointingoverhead:Fx1

EachoftheequationsintheleftcolumnofTable7correspondstothefirstcheckpointforeachscheme.OnlyNbaffectsthecheckpoint-ingoverhead;thatis,theoverheadofthefirstcheckpointisapplicationindependent.Fig.3showsFx1valuesforvariousblocksizes.Inthisfigure,Fsp=FpandFsi=Fiareabout1.7,whichmeansthatsecurecheckpointingincreasesthecheckpointingoverheadbyafactorof1.7atthefirstcheckpoint.However,ifweassumethattheapplicationisalongrunningprocess,theoverheadofthefirstcheckpointhaslittleeffectonthetotalcheckpointingoverhead.FiishigherthanFpinallcases.AlthoughFspismuchworsethanFsiforsmallblocksizes,FspbecomesbetterthanFsiforblocksizeslargerthanabout700bytes.5.2.3.Measuredsubsequentcheckpointingover-head:Fxn,ðnP2Þ

ByapplyingthemeasuredvaluesinTable8totheequationsintherightcolumnofTable7,wederivedthecheckpointingoverheadsofeachap-plicationanalytically.Fig.4showsFxn,ðnP2Þvalues,thenormalizedoverheadofcheckpointing,foreachapplication.Inthisfigure,securecheck-pointing(SICandSPC)increasesthecheckpoint-ingoverheadcomparedtotheexistingnon-securecheckpointingmethods(ICorPC).AlsoSPCre-quireslessoverheadthanSICexceptforMatmul,whichmeansthattheperformanceofthePCschemeisnotgoodwhenthedirtypageandthedirtyblockratearelow(butthedifferenceissmall).Formostcases,SPCoutperformsSIC.Thus,PCisagoodcandidateasthebaseschemeforthesecurecheckpointingsystem.InFig.4,

2422checkpoint overhead(ms)201816141210\"F_i\"\"F_p\"\"F_si\"\"F_sp\"050010001500200025003000block size(bytes)350040004500Fig.3.Analyticoverheadatthefirstcheckpointforeachscheme.H.Nametal./JournalofSystemsArchitecture48(2003)237–2249

checkpoint overhead(ms)98763210050010001500200025003000350040004500block size(Bytes)Matmulcheckpoint overhead(ms)109876321050010001500200025003000350040004500block size(bytes)BRSAcheckpoint overhead(ms)121110987632checkpoint overhead(ms)1716151413121110980050010001500200025003000350040004500Lufact\"F_i\"block size(Bytes)\"F_p\"50010001500200025003000350040004500block size(Bytes)Cell30\"F_si\"\"F_sp\"Fig.4.Measuredoverheadafterthefirstcheckpointingforeachapplication.boththeFpandFspcurveshaveaminimumpoint

whenmedium-sizedblocksareused,i.e.,256or512bytes,whichissimilartotheresultsobtainedin[10].Whenthedirtyblockrateismuchsmallerthanthedirtypagerate,i.e.,BRSAandLufactcases,FsptakeslesstimethanFiatmediumblocksizes.ThismeansthatSPCrequireslessoverheadthantheexistingICschemeinthebestcase.5.2.4.Checkpointingoverheadwithvarioussecurityalgorithms

WealsoappliedvariousencryptionandMACalgorithmstoourmodels.Blockencryptionalgo-rithmsusedinthisevaluationareasfollows:(1)DES(DESencryptionalgorithm),(2)3DES(tripleDESalgorithm,abitblockcipher),(3)BF(Blowfishalgorithm,abitblockcipher[18]),and(4)RJ(Rijndaelalgorithm,a128bitblock

Table9

Encryptiontime(inms)DES9.59

3DES22.08

BF5.09

RJ7.2

cipher[2]).Table9showsmeasuredTpevaluesforeachblockcipheralgorithm.

MACalgorithmsusedinthisevaluationareHMACwithMD5(representedasH_MD5inthispaper)andHMACwithSHA1(representedasH_SHA1inthispaper).Table10showsthemeasuredTmacvalueforeachalgorithm.ThesizeoftheMACisdifferentforeachalgorithm.H_MD5generatesa128-bitcode,butH_SHA1generatesa160-bitcode.Thus,Nsechangesasthealgorithmchanges,i.e.,16forH_MD5,and20forH_SHA1.

250

Table10

MACgenerationtime(inms)H_MD50.96

H.Nametal./JournalofSystemsArchitecture48(2003)237–2

H_SHA11.52

Fig.5showscheckpointoverheadsofLufactforvariouscryptographicalgorithms.Inthisfigure,thecombinationofH_MD5andBFshowslessoverheadthanalloftheothercases.

BasedupontheresultsofFig.4,wemeasuredtherelativeslowdownforeachcombinationofalgorithms.Table11showstheresultswhentheblocksizeis256.Inthistable,FsiðXÞ=FivaluesarelowerthanFsiðXÞ=Fpvalues.ThismeansthatSPC,securecheckpointingbasedonPC,islessaffectedbythecryptographicalgorithmsused.

25FromTable11,itcanbeobservedthatSPCwithBF-H_MD5(usingBlowfishfortheencryp-tionalgorithmandH_MD5fortheMACfunc-tion)hasanoverheadincrementonlybyafactorofabout1.57comparedtoPC,whichmeansthatthesecurecheckpointingschemehasanin-creasedoverheadbyonlyaboutafactorof1.57comparedtoanon-securecheckpointingschemeinthebestcase.Moreover,Table12showsthatSPCisfasterthantheexistingICscheme,whichdoesnotevenhavesecurityfeatures.ThespeedupoverICisabout1.27inthebestcase.Compar-ingH_MD5casestoH_SHA1case,H_MD5casesarefasterandgeneratesmallersizeofMACsthanH_SHA1.However,Fsið3DESÀRMD160Þ=Fspð3DESÀRMD160Þshowssimilarratescom-paredtotheothercasesshowninTable13,which

checkpoint overhead(ms)2015\"F_i\"\"F_p\"\"F_si(DES,H_MD5)\"\"F_sp(DES,H_MD5)\"\"F_si(BF,H_MD5)\"\"F_sp(BF,H_MD5)\"\"F_si(RJ,H_MD5)\"\"F_sp(RJ,H_MD5)\"\"F_si(3DES,H_SHA1)\"\"F_sp(3DES,H_SHA1)\"1050050010001500200025003000350040004500block sizeFig.5.Checkpointoverheadofvariousalgorithms(usingLufact).Table11

Relativeslowdown(Nb¼256,Lufact)XFsiðXÞ=FiFspðXÞ=Fp

DES-H_MD52.28011.826825

BF-H_MD52.2315251.571988

RJ-H_MD52.4243681.691478

3DES-H_SHA13.87302.712100

Table12

Relativespeedup(Nb¼256,Lufact)XFi=FspðXÞ

DES-H_MD51.090633

BF-H_MD51.267436

RJ-H_MD51.177902

3DES-H_SHA10.734632

H.Nametal./JournalofSystemsArchitecture48(2003)237–2

Table13

Relativeslowdowncomparedtothetwosecurecheckpointingmethods(Nb¼256,Lufact)X

FsiðXÞ=FspðXÞ

DES-H_MD52.882326

BF-H_MD52.828317

RJ-H_MD53.607177

3DES-H_SHA12.962875

251

impliesthatincreasingthesizeoftheMAChaslittleeffect.

5.3.Experimentalresults

Theproposedschemeswereimplementedonlibckpt,ageneral-purposecheckpointinglibrarydevelopedattheUniversityofTennessee[13].WealsoimplementedBatchRSA[3]andtestedtheperformanceofthesecurecheckpointingwithitasanapplicationprogram.

Thephysicalenvironmentsusedforourexper-imentswerethesameasassumedinSection5.1.512-bitRSAencryptedmessagesandcorrespond-ing512-bitRSAprivatekeyswereusedasinputsoftheBatchRSAprogramandcheckpointsweretakenevery2min.TheaveragedirtyblockratesanddirtypagerateoftheprogramareshownintheTable8.WeusedBlowfishastheblocken-cryptionalgorithmandHMACwithMD5astheintegritycheckingalgorithmforeachcheckpoint-ingscheme.Fig.6showsexecutiontimewhenapplyingeachcheckpointingscheme.Inthefigure,

‘‘FULL’’isthecasewherefullcheckpointingwasappliedwithBlowfishblockencryptionandHMAC-MD5hash,and‘‘NONE’’isthecasewherenocheckpointingschemewasapplied.Ourexperimentsshowresultssimilartotheanalyticaldata.Intheseexperiments,SPCrequireslesstimethanSIC.Inthebestcase,SPCshowsacheck-pointoverheadof6.2%,whichisamuchsmalleroverheadthanthatoffullcheckpointingwithcryptographicfunctionalities(i.e.,22%).

6.Conclusion

Inapplicationssuchase-commerce,banking,andstocktrading,thesecurityoftheinformationbeingprocessedisasimportantas,ifnotmoreimportantthan,theabilitytoscaletolargenum-bersofusersortheabilitytoprovideuninter-ruptedserviceeveninthepresenceoffaults.Asecuresystemshouldaddressallaspectsofthecommunication,storage,andprocessingofsen-sitivedata.Thissuggeststhatnotonlyshould

700680checkpoint overhead(ms)66006206005805600050010001500200025003000\"NONE\"\"FULL\"\"SIC\"\"SPC\"350040004500block size(bytes)Fig.6.ExecutiontimeofBRSAprogramapplyingvariouscheckpointingschemes.252H.Nametal./JournalofSystemsArchitecture48(2003)237–2

explicitnetworkcommunicationbeprotectedbycryptographicmethods,butthatprotectionshouldalsobeprovidedforfilesstoredonharddisk,pagesswappedoutofmainmemory,andanydataprocessingactivitiesinwhichthedataisexposedtoareasoutsideoftheoperatingsystemÕskernelspaceandprivateprocessmemoryspace(theker-nelspaceandprivateprocessmemoryspaceareassumedtobeprotectedbynormaloperatingsystemprotectionmechanisms).

Thispaperaddressedtheinformationleakageincheckpointdataasitissentoutoverthenetworktoremotestablestorage,aspartofcheckpointingoperationsdesignedtoprotectlong-runningap-plicationsfromfaults.Theproposedsolutionmethod,referredtoassecurecheckpointing,com-binestheexistingcheckpointingmethodswithcryptographicfunctionalities.Becausetheencryp-tionnode(checkpointnode)anddecryptionnode(recoverynode)differinsecurecheckpointing,cryptographickeymanagementisanimportantissueforsecurecheckpointing.Forkeymanage-ment,wehavedevelopedtwomodels:thekeydistributionmodelandthekeyagreementmodel.Ofthetwomodels,thekeyagreementmodelhasloweroverheadthanthekeydistributionmodel.However,thekeyagreementmodelrequiresare-coverynodetobedesignatedwhencheckpointingisinitiated.

Anotherimportantissueinourresearchisminimizingthecheckpointoverhead.Twocheck-pointingschemesaredevisedforcheckpointingwithalowoverhead:oneisSICandtheotherisSPC.BecauseSPCcombinesdirtyareadetectionanddataintegrityintooneoperation,theSPCcheckpointingschemeissimplerandfasterthanSIC.Finally,weproposeasecurecheckpointingsystem,whichcombinesthekeyagreementmodelandSPCtosolvetheinformationleakageproblemforacheckpointingsystem.

Performanceanalysisandexperimentationonanactualsystemshowthatsecurecheckpointingincreasestheoverheadbyafactorofabout1.57whencomparedtoconventionalcheckpointingsystems.Althoughthismayseemlikealargeslowdownwhenconsideredbyitself,itshouldbe

notedthatthischeckpointingtimeisstillontheorderofatmostafewtensofseconds(typicallysmaller),whichisinsignificantwhenconsideringthattheoverallexecutiontimeofapplicationstobecheckpointedtypicallyexceedsseveralhours,days,orevenlonger.Also,theobservedslowdowncansimplybeconsideredasthecostthatmustbepaidtoprotectvaluableinformation.Withtheincreasingprocessingspeedsofmodernmicro-processors,itismoreimportanttoensurethatre-quiredfunctionalitiesareprovided(andwithsufficientcapabilities)thantoskipthosefunc-tionalitiesandprovideafasterbutinsecurepro-gram.

Acknowledgements

TheauthorswouldliketothanktheMinistryofEducationofKoreaforitsfinancialsupportto-wardtheElectricalandComputerEngineeringDivisionatPOSTECHthroughitsBK21program.

References

[1]M.Blaze,AcryptographicfilesystemforUnix,in:ProceedingsoftheFirstACMConferenceonComputerandCommunicationsSecurity,November1993,pp.9–16.[2]J.Daemen,V.Rijmen,AESProposal:Rijndael,AESsubmision,http://www.esat.kuleuven.ac.be/rijmen/rijndael,June1998.

[3]A.Fiat,BatchRSA,JournalofCryptology10(1997)75–88.

[4]P.Gutmann,Securedeletionofdatafrommagneticandsolid-statememory,in:TheSixthUSENIXSecuritySymposiumProceedings,July1996.

[5]D.Harkins,D.Carrel,TheInternetKeyExchange(IKE),http://www.ietf.org/rfc/rfc2409.txt,November1998.

[6]G.H.Kim,E.H.Spafford,TheDesignandImplementationofTripwire:AUNIXFileIntegrityChecker,TechnicalReportCSD-TR-93-071,CERIASatPurdueUniversity,1993.

[7]H.Krawczyk,M.Bellare,R.Canetti,HMAC:Keyed-HashingforMessageAuthentication,RFC2104,February1997.

[8]K.Li,J.F.Naughton,J.S.Plank,Low-latencyconcurrentcheck-pointingforparallelprograms,IEEETransactionsonParallelandDistributedSystems5(August)(1994)874–879.

H.Nametal./JournalofSystemsArchitecture48(2003)237–2

253

[9]A.J.Menezes,P.C.vanOorschot,S.A.Vanstone,Hand-BookofAppliedCryptography,CRCPress,1997.

[10]H.Nam,J.Kim,S.J.Hong,S.Lee,Probabilisticcheck-pointing,IEICETransactiononInformationandsystemsE85-D(7)(2002)1093–1104.

[11]H.Nam,J.Kim,S.J.Hong,S.Lee,Reliableprobabilistic

checkpointing,in:1999PacificRimInternationalSympo-siumonDependableComputing,December1999,pp.153–160.

[12]H.Nam,J.Kim,S.J.Hong,S.Lee,Securecheckpointing,

TechnicalReportCS-HPC-01-001,PohangUniversityofScienceandTechnology,2001.

[13]J.S.Plank,M.Beck,G.Kingsley,K.Li,Libckpt:

Transparentcheck-pointingunderunix,in:ConferenceProceedings,UsenixWinter1995TechnicalConference,January1995,pp.213–223.

[14]J.S.Plank,K.Li,FastercheckpointingwithNþ1parity,

in:24thInternationalSymposiumonFault-TolerantComputing,June1994,pp.288–297.

[15]J.S.Plank,J.Xu,R.H.B.Netzer,CompressedDifferences:

AnAlgorithmforFastIncrementalCheckpointing,Tech-nicalReportCS-95-302,UniversityofTennessee,August1995.

[16]N.Provos,Thepacketvault:securestorageofnetwork

data,in:ProceedingsoftheWorkshoponIntrusionDetectionandNetworkMonitoring,April1999.

[17]N.Provos,Encryptingvirtualmemory,in:9thUSENIX

SecuritySymposium,August2000.

[18]B.Schneier,Descriptionofanewvariable-lengthkey,-bitblockcipher(Blowfish),in:FastSoftwareEncryption,CambridgeSecurityWorkshopProceedings,Springer-Verlag,December1993,pp.191–204.

[19]B.Schneier,J.Kelsey,Cryptographicsupportforsecure

logsonuntrustedmachines,in:Proceedingsofthe7thUSENIXSecuritySymposium,January1998.

[20]A.Shamir,N.vanSomeren,Playinghideandseekwith

storedkeys,FinancialCryptographyÕ99(February)(1999)22–25.

[21]J.G.Steiner,B.C.Neuman,J.I.Schiller,Kerberos:an

authenticationserviceforopennetworksystems,in:ProceedingsofUsenixConference,February1988,pp.191–202.

[22]Y.-M.Wang,Y.Huang,K.-P.Vo,P.-Y.Chung,C.

Kintala,Checkpointinganditsapplications,in:25thAnnualInternationalSymposiumonFault-TolerantCom-puting,October1995,pp.22–30.

[23]Y.Yacobi,M.J.Beller,BatchDiffie–Hellmankeyagree-mentsystems,JournalofCryptology10(1997)–96.[24]EncryptingFileSystemforWindows2000,Microsoft

Windows2000WhitePaper,MicrosoftCorp.,http://www.microsoft.com/windows2000/guide/server/features/se-curity.asp,1999.

[25]IntrusionDetection:RealSecureOSSensor,http://

www.iss.net/securing_e-business/security_products/intru-sion_detection/realsecure_ossens-or/index.php.

[26]IPSecurityProtocol(ipsec),http://www.ietf.org/html.char-ters/ipsec-charter.html.

[27]Public-KeyInfrastructure(X.509)(pkix),http://www.

ietf.org/html.charters/pkix-charter.html.

[28]Sniffing(networkwiretap,sniffer)FAQ,http://www.

robertgraham.com/pubs/sniffing-faq.html.

[29]TransparentCryptographicFileSystem,http://tcfs.dia.

unisa.it/.

[30]TransportLayerSecurity(tls),http://www.ietf.org/

html.charters/tls-charter.html.

HyochangMSNamreceivedneeringincomputersciencehisandBSengi-andSciencefromPohangUniversityof1995currentlyandandTechnology,Koreaintheworking1998,respectively.towardthePh.D.Heatissearchsamedistributedinterestsuniversity.includeHisfaultcurrenttolerance,re-security.

computing,andcomputerJongelectronicKimreceivedtheBSUniversityengineeringcomputerin1981,thefromdegreeinMSHanyang-StaterentlyUniversityscienceinfromdegreein1991.PennsylvaniadepartmentanAssociateHeiscur-Engineering,ofComputerProfessorintheScienceKorea.andPohangEngineering,UniversityScienceandPohang,ofwasComputingaresearchPriortofellowthisappointment,inhepartmentofElectricalLaboratorytheEngineeringoftheReal-TimeDe-andMichigansystemfrom1991toComputer1992.ScienceattheUniversityof

Seoul,engineercomputing,Korea.HinFrom1983to1986,hewasaisthemajorKoreaSecuritiesComputerCorporation,computing,andperformancecomputerevaluation,areasofinterestsecurity.

parallelareandfault-tolerantdistributedSunginJeHongreceivedtheBSNationalelectronicsdegreeUniversityengineeringin1973,fromdegreeSeoulStatedegreeUniversityincomputertheMSinsciencefromIowaUniversityincomputer1979,scienceandfromthePhDthepaignfessorin1983.ofIllinois,HeiscurrentlyUrbana-Cham-aPro-ScienceintheUniversityandDepartmentEngineering,ofComputerPohangPohang,wasKorea.ofScienceFromand1983Technology,to19,heElectricsearchastaffandmemberDevelopment,ofCorporateGeneral

Re-hedesignwasCompany,Schenectady,NY,USA.From1975to1976,systemengineer.withOrientalFromComputer1973to1975,Engineering,heservedKorea,thearmyasalogicasaresearchanalystattheArmyFinanceCenter,Korea.Hiscurrenting,andinterestsparallelprocessing.

includeVLSIdesign,CADalgorithms,test-2H.Nametal./JournalofSystemsArchitecture48(2003)237–2

SungguLeereceivedtheBSEEdegreewithhighestdistinctionfromtheUni-versityofKansas,Lawrence,in1985andtheMSEandPhDdegreesfromtheUniversityofMichigan,AnnAr-bor,in1987and1990,respectively.HeiscurrentlyanAssociateProfessorintheDepartmentofElectronicandElectricalEngineeringatthePohang

UniversityofScienceandTechnology(POSTECH),Pohang,Korea.Priortothisappointment,hewasanAssistantProfessorintheDepartmentofElectricalEngineeringattheUniversityofDelawareinNewark,Delaware,USA.FromJune1997toJune1998,hespentoneyearasaVisitingScientistattheIBMT.J.WatsonResearchCenter.Hisresearchinterestsareinparallelcomputingusingclusters,fault-tolerantcomputing,andreal-timecomputing.