pwrite卡巴斯基授权文件

AllFileSystemsAreNotCreatedEqual:OntheComplexityofCraftingCrash-ConsistentApplicationsThanumalayanSankaranarayanaPillai,VijayChidambaram,RamnatthanAlagappan,SamerAl-Kiswany,AndreaC.
Arpaci-Dusseau,RemziH.
Arpaci-DusseauAllFileSystemsAreNotCreatedEqual:OntheComplexityofCraftingCrash-ConsistentApplicationsThanumalayanSankaranarayanaPillai,VijayChidambaram,RamnatthanAlagappan,SamerAl-Kiswany,AndreaC.
Arpaci-Dusseau,RemziH.
Arpaci-DusseauCrashConsistencyMaintainingdatainvariantsacrossasystemcrash‐Example:DatabasetransactionsshouldbeatomicCrashConsistencyMaintainingdatainvariantsacrossasystemcrash‐Example:DatabasetransactionsshouldbeatomicImportantinsystems‐FileSystems‐RelationalDatabases‐Key-ValueStoresCrashConsistencyMaintainingdatainvariantsacrossasystemcrash‐Example:DatabasetransactionsshouldbeatomicImportantinsystems‐FileSystems‐RelationalDatabases‐Key-ValueStoresHardtogetright:ARIESinventedonlyin1992‐ProvingARIEStook5moreyears(1997)Lotsofworkinfilesystemcrashconsistency‐Journaling,copy-on-write,softupdates.
.
.
File-SystemCrashConsistencyLotsofworkinfilesystemcrashconsistency‐Journaling,copy-on-write,softupdates.
.
.
FSconsistencyfocusesoninternalmetadata‐DodirectoriesonlycontainvaliddirectoryentriesFile-SystemCrashConsistencyLotsofworkinfilesystemcrashconsistency‐Journaling,copy-on-write,softupdates.
.
.
FSconsistencyfocusesoninternalmetadata‐DodirectoriesonlycontainvaliddirectoryentriesWhataboutuser-leveldataFile-SystemCrashConsistencyWhatguaranteesdofilesystemsgiveapplications‐Thatcanbeusedforconsistencyofuser-leveldataThisworkstudies.
.
.
Whatguaranteesdofilesystemsgiveapplications‐Thatcanbeusedforconsistencyofuser-leveldataDoapplicationsmaintainconsistencycorrectly‐Importantapplicationsrequireuser-levelconsistency‐Databases,key-valuestores,distributedsystems.
.
.
Thisworkstudies.
.
.
Filesystemguaranteesvarywidely‐Studied16configsofext2,ext3,ext4,btrfs,xfs,reiserfs‐Guaranteesvaryamongconfigsofsamefilesystem‐Guaranteesoftenside-effectsofFSimplementation‐POSIXstandardsofguarantees,ifany,aredebatedWefind.
.
.
Filesystemguaranteesvarywidely‐Studied16configsofext2,ext3,ext4,btrfs,xfs,reiserfs‐Guaranteesvaryamongconfigsofsamefilesystem‐Guaranteesoftenside-effectsofFSimplementation‐POSIXstandardsofguarantees,ifany,aredebatedApplicationsdependonguaranteesinsubtleways‐Studied11applications:Databases,Distributedsystems,Virtualizationsoftware,Key-valuestores,VCS‐60vulnerabilitiesunderaweakfilesystemmodel‐Morethan30vulnerabilitiesunderext3,ext4,btrfsWefind.
.
.
IntroductionAnExampleBOB:ExaminingFileSystemBehaviorALICE:ExaminingApplicationsConclusionOutlineIntroductionAnExampleBOB:ExaminingFileSystemBehaviorALICE:ExaminingApplicationsConclusionOutlineAfileinitiallycontainsthestring"afoo"‐Assumeeachcharacterin"afoo"isablockofdataTask:Atomicallychangethecontentsto"abar"‐Onapowerloss,wemustretrieveeither"afoo"or"abar"ToyExample:OverviewToyExample:SimpleOverwriteInitialstate/x/f1"afoo"Finalstate/x/f1"abar"Modificationpwrite(/x/f1,2,"bar")IntermediatestatespossibleoncrashToyExample:SimpleOverwriteInitialstate/x/f1"afoo"Modificationpwrite(/x/f1,2,"bar")Finalstate/x/f1"abar"Intermediatestate1/x/f1"aboo"Intermediatestate2/x/f1"afar"Intermediatestates3,4,5.
.
.
.
WhatifcrashatomicityisneededUseapplication-levellogging(a.
k.
a.
undologging/rollbackjournaling)a.
Makeacopyofolddatain"log"fileb.
Modifyactualfilec.
Deletelogfiled.
Onacrash,datacanberecoveredfromthelogToyExample:MaintainingConsistencyWhatifcrashatomicityisneededUpdateProtocolcreat(/x/log1);write(/x/log1,"2,3,foo");pwrite(/x/f1,2,"bar");unlink(/x/log1);WritetologActualmodificationDeletelogToyExample:Protocol#1Worksinext3(data-journal)!
UpdateProtocolcreat(/x/log1);write(/x/log1,"2,3,foo");pwrite(/x/f1,2,"bar");unlink(/x/log1);ToyExample:Protocol#1Somepossibleintermediatestates/x/f1"afoo"/x/log1""/x/f1"afoo"/x/log1"2,3,f"/x/f1"aboo"/x/log1"2,3,foo"1.
2.
3.
Worksinext3(data-journal)!
UpdateProtocolcreat(/x/log1);write(/x/log1,"2,3,foo");pwrite(/x/f1,2,"bar");unlink(/x/log1);Somepossibleintermediatestates/x/f1"afoo"/x/log1""/x/f1"afoo"/x/log1"2,3,f"/x/f1"aboo"/x/log1"2,3,foo"1.
2.
3.
ToyExample:Protocol#1SimplydeletelogfileduringrecoveryWorksinext3(data-journal)!
UpdateProtocolcreat(/x/log1);write(/x/log1,"2,3,foo");pwrite(/x/f1,2,"bar");unlink(/x/log1);Somepossibleintermediatestates/x/f1"afoo"/x/log1""/x/f1"afoo"/x/log1"2,3,f"/x/f1"aboo"/x/log1"2,3,foo"1.
2.
3.
ToyExample:Protocol#1RecoverfromlogfileduringrecoveryWorksinext3(data-journal)!
Doesn'tworkinext3(data-ordered)UpdateProtocolcreat(/x/log1);write(/x/log1,"2,3,foo");pwrite(/x/f1,2,"bar");unlink(/x/log1);ToyExample:Protocol#1Worksinext3(data-journal)!
Doesn'tworkinext3(data-ordered)UpdateProtocolcreat(/x/log1);write(/x/log1,"2,3,foo");pwrite(/x/f1,2,"bar");unlink(/x/log1);ext3(ordered)canre-orderthesetworequests,sendingpwrite(f1)todiskfirst,beforewrite(log1)ToyExample:Protocol#1Worksinext3(data-journal)!
Doesn'tworkinext3(data-ordered)UpdateProtocolcreat(/x/log1);write(/x/log1,"2,3,foo");pwrite(/x/f1,2,"bar");unlink(/x/log1);Apossibleintermediatestate/x/f1"aboo"/x/log1""Recoverynotpossible!
ToyExample:Protocol#1Worksinext3(data-journal),(data-ordered)!
UpdateProtocolcreat(/x/log1);write(/x/log1,"2,3,foo");fsync(/x/log1);pwrite(/x/f1,2,"bar");fsync(/x/f1);unlink(/x/log1);ToyExample:Protocol#2Worksinext3(data-journal),(data-ordered)!
Doesn'tworkinext3(writeback)UpdateProtocolcreat(/x/log1);write(/x/log1,"2,3,foo");fsync(/x/log1);pwrite(/x/f1,2,"bar");fsync(/x/f1);unlink(/x/log1);Apossibleintermediatestates/x/f1"afoo"/x/log1"2,3,#!
@"Filesizealoneincreasesforlog1,andgarbageoccurs.
Recoverycannotdifferentiatebetweengarbageanddata!
CrashhereToyExample:Protocol#2Worksinext3(data-journal),(data-ordered),(writeback)UpdateProtocolcreat(/x/log1);write(/x/log1,"2,3,checksum,foo");fsync(/x/log1);pwrite(/x/f1,2,"bar");fsync(/x/f1);unlink(/x/log1);ToyExample:Protocol#3Worksinext3(data-journal),(data-ordered),(writeback)Notenough,accordingtoLinuxmanpagesUpdateProtocolcreat(/x/log1);write(/x/log1,"2,3,checksum,foo");fsync(/x/log1);pwrite(/x/f1,2,"bar");fsync(/x/f1);unlink(/x/log1);Apossibleintermediatestates/x/f1"aboo"Thelogfile'sdirectoryentrymightneverbecreatedToyExample:Protocol#3WorksinallfilesystemsUpdateProtocolcreat(/x/log1);write(/x/log1,"2,3,checksum,foo");fsync(/x/log1);fsync(/x);pwrite(/x/f1,2,"bar");fsync(/x/f1);unlink(/x/log1);ToyExample:Protocol#4Worksinallfilesystems(Additionalfsync()requiredfordurabilityinallFS)UpdateProtocolcreat(/x/log1);write(/x/log1,"2,3,checksum,foo");fsync(/x/log1);fsync(/x);pwrite(/x/f1,2,"bar");fsync(/x/f1);unlink(/x/log1);fsync(/x);ToyExample:Protocol#5Filesystemsvaryincrash-relatedbehavior‐ext3(ordered)re-orders,whileext3(journaled)doesnotApplicationsusuallydependonsomebehavior‐Dependonordering:Somefsync()callscanbeomittedExample:SummaryIntroductionAnExampleBOB:ExaminingFileSystemBehaviorALICE:ExaminingApplicationsConclusionOutlineTwoclassesofproperties:atomicityandordering‐Atomicityexample:Isawrite()callatomicintheFS‐Orderingexample:Arewrite()callssenttodiskin-orderStudiedext2,ext3,ext4,btrfs,xfs,reiserfs‐Westudied16configurationsofthesixfilesystemsFSBehavior:PersistenceProperties1.
Runuser-levelworkloadsstressingtheproperty‐Example:write(8KB)fortestingatomicityofwrite()callsMethodology:TheBlock-OrderBreaker(BOB)1.
Runuser-levelworkloadsstressingtheproperty‐Example:write(8KB)fortestingatomicityofwrite()calls2.
Recordblock-leveltraceoftheworkloadMethodology:TheBlock-OrderBreaker(BOB)1.
Runuser-levelworkloadsstressingtheproperty‐Example:write(8KB)fortestingatomicityofwrite()calls2.
Recordblock-leveltraceoftheworkload3.
Reconstructdisk-statespossibleonapower-loss‐Allstatespossibleifdisk-cachedoesnotre-order‐Afewstateswheredisk-cachere-ordersMethodology:TheBlock-OrderBreaker(BOB)1.
Runuser-levelworkloadsstressingtheproperty‐Example:write(8KB)fortestingatomicityofwrite()calls2.
Recordblock-leveltraceoftheworkload3.
Reconstructdisk-statespossibleonapower-loss‐Allstatespossibleifdisk-cachedoesnotre-order‐Afewstateswheredisk-cachere-orders4.
RunFSrecovery,verifypropertyoneachdisk-state‐Example:Isall8KBwrittenatomicallyMethodology:TheBlock-OrderBreaker(BOB)FileSystemStudy:ResultsFilesystemconfigurationAtomicityOrderingOnesectoroverwriteAppendcontentManysectoroverwriteDirectoryoperationOverwrite→AnyopAppend→AnyopDir-op→AnyopAppend→Renameext2asyncsyncext3writebackordereddata-journalext4writebackorderedno-delallocdata-journalbtrfsxfsdefaultwsyncFileSystemStudy:ResultsFilesystemconfigurationAtomicityOrderingOnesectoroverwriteAppendcontentManysectoroverwriteDirectoryoperationOverwrite→AnyopAppend→AnyopDir-op→AnyopAppend→Renameext2asyncsyncext3writebackordereddata-journalext4writebackorderedno-delallocdata-journalbtrfsxfsdefaultwsyncFileSystemDifferentConfigurationsofFileSystemFileSystemStudy:ResultsFilesystemconfigurationAtomicityOrderingOnesectoroverwriteAppendcontentManysectoroverwriteDirectoryoperationOverwrite→AnyopAppend→AnyopDir-op→AnyopAppend→Renameext2asyncsyncext3writebackordereddata-journalext4writebackorderedno-delallocdata-journalbtrfsxfsdefaultwsyncPersistencePropertiesconsideredFileSystemStudy:ResultsFilesystemconfigurationAtomicityOrderingOnesectoroverwriteAppendcontentManysectoroverwriteDirectoryoperationOverwrite→AnyopAppend→AnyopDir-op→AnyopAppend→Renameext2asyncsyncext3writebackordereddata-journalext4writebackorderedno-delallocdata-journalbtrfsxfsdefaultwsyncIsadirectoryoperation,likerename(),atomiconasystemcrashFileSystemStudy:ResultsFilesystemconfigurationAtomicityOrderingOnesectoroverwriteAppendcontentManysectoroverwriteDirectoryoperationOverwrite→AnyopAppend→AnyopDir-op→AnyopAppend→Renameext2asyncsyncext3writebackordereddata-journalext4writebackorderedno-delallocdata-journalbtrfsxfsdefaultwsyncPropertycertainlynotobeyedWedidnotseeaviolationFileSystemStudy:ResultsFilesystemconfigurationAtomicityOrderingOnesectoroverwriteAppendcontentManysectoroverwriteDirectoryoperationOverwrite→AnyopAppend→AnyopDir-op→AnyopAppend→Renameext2asyncsyncext3writebackordereddata-journalext4writebackorderedno-delallocdata-journalbtrfsxfsdefaultwsyncMainresult:FilesystemsvaryintheirpersistencepropertiesApplicationsshouldnotrelyonpersistencepropertiesTestingapplicationsonaspecificFSisnotenough‐ext3(data-journal):Re-orderingvulnerabilitiesarehiddenFileSystemStudy:ConclusionIntroductionAnExampleBOB:ExaminingFileSystemBehaviorALICE:ExaminingApplicationsConclusionOutlineALICE:Goal"Application-LevelIntelligentCrashExplorer"Goal:Tooltofindcrashvulnerabilitiesofanapplication‐Findvulnerabilitiesacrossallfilesystems‐Relatevulnerabilitiestospecificsourcelines‐RelatevulnerabilitiestofilesystembehaviorALICE:TechniqueUser-suppliedApplicationWorkloadALICEUsersuppliesALICEwithanapplicationworkload–Example:AdatabasetransactionALICE:TechniqueSystem-callTraceALICErunsworkloadandrecordssystem-calltraceALICEUser-suppliedApplicationWorkloadALICE:TechniqueSystem-callTraceAPM:AbstractPersistenceModelAPMmodelsallcrashstatesthatcanoccuronanFS–Default,weakAPMallowsmanypossiblestates–CustomAPMscanbeconfiguredbyuserforaspecificfilesystem–Eg:ext3(ordered)APMallowsstateswithoverwritesre-ordered;ext3(data-journal)APMdoesnotALICEUser-suppliedApplicationWorkloadALICE:TechniqueSystem-callTraceExplorerAPM:AbstractPersistenceModelExplorerreconstructssomestatesusingtheAPMALICEUser-suppliedApplicationWorkloadALICE:TechniqueSystem-callTraceExplorer.
.
.
ALICEAPM:AbstractPersistenceModelCrashstate#1(Violatesatomicityofsyscall-1)Crashstate#2(Violatesorderingofsyscall-1and2)Explorertargetsspecificstates–Relatingtoatomicityandre-orderingofeachsyscallUser-suppliedApplicationWorkloadTheapplicationisrunoneachreconstructedstate–Usersuppliesapplicationchecker–Example:WasACIDpreservedALICE:TechniqueSystem-callTraceExplorer.
.
.
User-suppliedApplicationCheckerALICEAPM:AbstractPersistenceModelCrashstate#1(Violatesatomicityofsyscall-1)Crashstate#2(Violatesorderingofsyscall-1and2)User-suppliedApplicationWorkloadCheckershowswhichstatesarerecoveredfromcorrectlyALICE:TechniqueSystem-callTraceExplorer.
.
.
ALICEAPM:AbstractPersistenceModelCrashstate#1(Violatesatomicityofsyscall-1)Crashstate#2(Violatesorderingofsyscall-1and2)CorrectIncorrectUser-suppliedApplicationWorkloadUser-suppliedApplicationCheckerFromcheckeroutputs,wedeterminevulnerabilitiesALICE:TechniqueSystem-callTraceExplorer.
.
.
Crashvulnerability:Re-orderingsyscall-1and2ALICEAPM:AbstractPersistenceModelCrashstate#1(Violatesatomicityofsyscall-1)Crashstate#2(Violatesorderingofsyscall-1and2)CorrectIncorrectUser-suppliedApplicationWorkloadUser-suppliedApplicationCheckerHDFSZooKeeperVMWarePlayerLMDBGDBMLevelDBPostgresHSQLDBSQLiteMercurialGitVulnerabilityStudy:ApplicationsNon-relationalDatabasesRelationalDatabasesVersionControlSystemsVirtualizationSoftwareDistributedServicesExample:Gitcreat(index.
lock)mkdir(o/x)creat(o/x/tmp_y)append(o/x/tmp_y)fsync(o/x/tmp_y)link(o/x/tmp_y,o/x/y)unlink(o/x/tmp_y)append(index.
lock)rename(index.
lock,index)stdout(finishedadd)Readthefullpapertocorrectlyinterpretresults!
creat(index.
lock)mkdir(o/x)creat(o/x/tmp_y)append(o/x/tmp_y)fsync(o/x/tmp_y)link(o/x/tmp_y,o/x/y)unlink(o/x/tmp_y)append(index.
lock)rename(index.
lock,index)stdout(finishedadd)Example:GitAtomicityvulnerabilityWhichsystemcallsneedtobeatomicReadthefullpapertocorrectlyinterpretresults!
creat(index.
lock)mkdir(o/x)creat(o/x/tmp_y)append(o/x/tmp_y)fsync(o/x/tmp_y)link(o/x/tmp_y,o/x/y)unlink(o/x/tmp_y)append(index.
lock)rename(index.
lock,index)stdout(finishedadd)Example:GitAtomicityvulnerabilityOrderingvulnerabilityWhichsystem-callre-orderingscauseincorrectnessReadthefullpapertocorrectlyinterpretresults!
VulnerabilityStudy:Default(Weak)APMReadthefullpapertocorrectlyinterpretresults!
VulnerabilityStudy:Default(Weak)APM60VulnerabilitiesManyresultinsilentdataloss,inaccessibleapplicationsReadthefullpapertocorrectlyinterpretresults!
VulnerabilityStudy:BtrfsAPMReadthefullpapertocorrectlyinterpretresults!
VulnerabilityStudy:BtrfsAPM31VulnerabilitiesReadthefullpapertocorrectlyinterpretresults!
Garbageduringfile-appends‐Affects3applications‐But,partialappendswithactualdata:0vulnerabilitiesFSsafetyheuristicsseeminglydon'thelpmuch‐Only2foundvulnerabilitiesby"Flushdatabeforerename"‐HeuristicsmighthelpothertypesofapplicationsNon-synchronousdirectoryoperations‐Affectsdurabilityof6applicationsWhatFSbehavioraffectsapplicationsIn-depth:WhatFSbehaviorsaffectapplicationsVulnerabilitiesunderotherAPMsInteractionswithapplicationdevelopersHownottointerpretourresultsAnefficientFSdesignwithsafetyvalidatedbyALICEInthepaper.
.
.
FSvaryinbehavioraffectingapplicationconsistency‐ext2,ext3,ext4,btrfs,xfs,reiserfsvaryevenamongtheirdifferentconfigurations‐SubtleimplementationdetailsaffectbehaviorApplicationprotocolsarecomplex,vulnerable‐60vulnerabilitiesunderweakAPM‐Morethanhalfexposedunderext3,ext4,btrfs‐Depend(bydesignorunwittingly)onFSimplementationSummaryApartingnote.
.
.
.
ExperiencedApp-Developer:POSIXdoesn'tletFSesdothatCanyoupointustotheexactPOSIXdocumentationDeveloper:Ican'tfindit,butIremembersomeonesayingsoApartingnote.
.
.
.
ExperiencedApp-Developer:POSIXdoesn'tletFSesdothatCanyoupointustotheexactPOSIXdocumentationDeveloper:Ican'tfindit,butIremembersomeonesayingsoExperiencedAcademic:Realfilesystemsdon'tdothatButdoesjustthatAcademic:Mystudentswouldflunkclassiftheybuiltafilesystemthatway.
.
.
Apartingnote.
.
.
.
ExperiencedApp-Developer:POSIXdoesn'tletFSesdothatCanyoupointustotheexactPOSIXdocumentationDeveloper:Ican'tfindit,butIremembersomeonesayingsoExperiencedAcademic:Realfilesystemsdon'tdothatButdoesjustthatAcademic:Mystudentswouldflunkclassiftheybuiltafilesystemthatway.
.
.
Thankyou!
Downloadtools:http://research.
cs.
wisc.
edu/adsl/Software/alice