pletecuteftp

AutomaticallyComplementingProtocolSpecicationsFromNetworkTracesJooAntunesandNunoNevesLASIGE,DepartamentodeInformática,FaculdadedeCiênciasdaUniversidadedeLisboa,Portugal{jantunes,nuno}@di.
fc.
ul.
ptABSTRACTNetworkserverscanbetestedforcorrectnessbyresortingtoaspecicationoftheimplementedprotocol.
However,producingaprotocolspecicationcanbeatimeconsumingtask.
Inaddition,protocolsareconstantlyevolvingwithnewfunctionalityandmessageformatsthatrendertheprevi-ouslydenedspecicationsincompleteordeprecated.
Thispaperpresentsamethodologytoautomaticallycomplementanexistingspecicationwithextensionstotheprotocolbyanalyzingthecontentsofthemessagesinnetworktraces.
Theapproachcanbeusedontopofexistingprotocolre-verseengineeringtechniquesallowingittobeappliedtobothopenandclosedprotocols.
Thisapproachalsohasthead-vantageofcapturingunpublishedorundocumentedfeaturesautomatically,thusobtainingamorecompleteandrealisticspecicationoftheimplementedprotocol.
Theproposedso-lutionwasevaluatedwithaprototypetoolthatwasabletocomplementanIETFprotocol(FTP)specicationwithsev-eralextensionsextractedfromtracdatacollectedin320publicservers.
CategoriesandSubjectDescriptorsC.
2.
2[ComputerSystemsOrganization]:Computer-CommunicationNetworks—NetworkProtocols;C.
2.
4[ComputerSystemsOrganization]:Computer-CommunicationNetworks—PerformanceofSystems1.
INTRODUCTIONNetworkserversrelyonprotocolstooerservicestotheirclients.
Protocolsprescribehowinterconnectedcomponentsshouldcommunicatebydeningtherulesandmessagefor-matsthatmustbeemployedwhileexchangingdata.
Asanexample,theInternetEngineeringTaskForce(IETF)hasbeenstandardizingprotocolsforvariousapplications,suchascomputerbootstrapinanetworkedenvironment[11],dis-tributednameresolution[16]orremoteemailaccess[17].
Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprotorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationontherstpage.
Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspecicpermissionand/orafee.
EWDC'11,May11-12,2011,Pisa,ItalyCopyrightc2011ACM978-1-4503-0284-5/11/05.
.
.
$10.
00Translatingahuman-readablespecication(e.
g.
,aRFCdoc-ument)intoamachine-readableformatcanbeacumber-someanderror-pronetask.
Therefore,intherecentyears,afewapproacheshavebeendevisedtoautomaticallyinferanapproximateprotocolspecicationfromnetworktraces[7,23,2]orfromtheexecutionofexistingimplementations[5,14,9,24].
Thesemachine-readablespecicationscanthenbeemployedinseveralareas,inparticularintestingandse-curity.
Forinstance,thespecicationscansupportthegen-erationoftestcasestoevaluateifaparticularserverimple-mentsaprotocolinacorrectandsecureway[1,7].
Alterna-tively,theycanbeincorporatedinltersofanapplication-levelrewall,whichrejectsmessagesthatviolatethepro-tocol[20]ortheycanbeemployedbyintrusiondetectionsystemstobuildsignaturesthatareabletodiscovermisbe-havingcomponents[18].
However,protocolsareconstantlyevolving,asnewfunc-tionalityanddierentmessageformatsareadded,render-ingthepreviouslydenedspecicationsincompleteordep-recated.
Oldspecicationsmustthereforebeupdatedwiththenewextensions,whichtypicallyrequiresacarefulanal-ysistoidentifywheretheoldspecicationwaschangedandhowitshouldbeupdated.
Sometimesdevelopersmustevenincorporatemultiplechangesfrommorethanoneextension,makingitanevenmorechallengingtask.
Currently,theexistingsolutionsaimedatobtainingprotocolspecicationsinanautomatedwaydonotmakeuseoftheolderversionsofthespecication,creatingthespecicationscompletelyfromscratch.
Thismeansthattocomplementanexistingspecication,onemustnotonlygetdatatracesthatcoverthenewfeatures,butalsore-createtheolddatatracesinordertoconservethepreviouscoverageofthepro-tocol.
Additionally,sincetheseapproachesignoretheoldspecication,onecannoteasilyidentifythenewpartofthespecicationthatpertainstotheextensions,whichmightbeuseful,forinstance,toprioritizethetestingofthenewfeatures.
Oursolutionisbasedonprotocolreverseengineering,butittakesadvantageoftheolderversionofthespecication.
Hence,thedatatracesitusesareonlyrequiredtoincludeinformationconcerningthenewextensions(althoughtheycanalsohavedatapertainingtotheoldspecication).
Atthismoment,wearefocusingonapplication-levelclear-textprotocolsdescribedbytheIETF,widelyusedbymanynet-workservers,forexample,FTP[19],IMAP[8],POP[17],orSMTP[12].
Themethodologycanbeappliedtobothopenandclosedprotocols1.
Infact,closedprotocolsareaveryinterestingtargetforsecuritypurposesbecause,asopposedtoopenprotocols,theyarenotsubjecttothepub-licscrutinyandtesting.
Nevertheless,thisapproachcanshedsomelightonthespecicationofclosedprotocolsandontheirlatestchanges.
Evenwithoutapubliclyavailabledescription,existingreverseengineeringtechniquescanin-feranapproximatespecicationfromnetworkorexecutiontraces,whichcanthenbeincrementallycomplementedusingourmethodologyasnewertracesarecaptured.
Weimplementedaprototypetoolandevaluatedourmethod-ologywiththecurrentspecicationoftheFileTransferPro-tocol(FTP,RFC959[19])andwithtracdatacollectedfrom320publicFTPserverscontainingseveralextensionstotheprotocol.
Wefoundthatthetoolcorrectlycomple-mentedthespecicationwithcommandsdescribedinvedierentRFCextensions.
Thecomplementedspecicationalsocapturedtwonon-standardprotocolcommandsthatwerebeingusedbyafewFTPclients.
Thismorecompletespecicationismuchclosertotherealutilizationofthepro-tocolthantheoriginaldocument-basedspecication.
Itcanprovidevaluableinformationasanunifyingspecication,whichweintendtouseinthefuturefortestingandsecu-ritypurposes.
Featuresnotpresentinformerversionsofthespecicationshouldbegivenhigherpriorityintesting.
Inparticular,non-standardorundocumentedextensionsmustbegivenspecialattention,sincemoreobscurefeaturesareusuallylesstested.
2.
METHODOLOGYThissectionpresentsthemethodologyforcomplementingaprotocolspecicationwithnewfeaturesorextensions.
Wefocusonclear-textprotocols,whichareoftenusedbynet-workservers,suchasmanyofthestandardprotocolspub-lishedbytheIETF.
Itisassumedthatanolderversionofthespecicationalreadyexistsandthattherearenetworktraceswithmessagescoveringthenewfeatures(orthatsomeimplementationisavailablefromwhichthenetworktracescanbeproduced).
Althoughinthispaperweareusingopenprotocolsasanexample,oursolutioncanalsobeappliedtoclosedprotocols.
Thelackofapublicprotocoldescriptionwouldrequireanapproximatespecicationtobeinferredinsteadofbeingmanuallytranslatedfromthedocumenta-tion,forinstance,byreverseengineeringtheexecutionofaserver[14,9,24]orthenetworktraces[7,23,2].
Inthesolution,theoriginalprotocolspecicationismodeledasanite-statemachine(FSM)thatdescribestherulesofcommunicationbetweentheclientsandtheservers.
Theau-tomatonmustcaptureboththelanguage(i.
e.
,theformatsofthemessages)andthestatemachine(i.
e.
,therelationbetweenthedierenttypesofmessages)oftheprotocol.
Separatespecicationsaredevisedfortheclientandserverdialects,i.
e.
,oneFSMdenesthemessagesrecognizedbytheclientsandtheirrespectivestates,whereasthespeci-cationpertainingtheserverisdenedbyanother.
1Closedprotocolsareprotocolsforwhichthereisincom-pleteornodocumentationtodescribetheirbehavior(e.
g.
,messageformats,states,transitionsbetweenstates).
Openprotocolscorrespondtotheoppositecase,wherethisdocu-mentationisavailable.
1FunctionextendSpecication2Input:A:Automatonwiththeoriginalspecicationoftheprotocol3NetworkTraces:Messagesoftheprotocol4T1:Minimumratioofuniqueinstances5T2:Minimumnumberoftransitions6Output:A←Automatonwiththeextendedspecicationoftheprotocol78//Phase1:ProtocolLanguage9L←emptyautomatonforthemessageformats10Formats←listofmessageformats(regularexpressions)takenfromtransitionsofA11foreachFormatf∈Formatsdo12Seqf←sequenceoftexttokensfromf13AddanewpathtoLtoacceptSeqf14foreachMessagem∈NetworkTracesdo15Seqm←sequenceoftexttokensfromm16Ifneeded,addnewpathtoLtoacceptSeqm17LabelnewlycreatedtransitionswithNew18Updatefrequencylabelofvisitedstates1920generalize←True21whilegeneralize=Truedo22generalize←False23foreachStateq∈L24ifalltransitionsinqarelabeledasNewthen25transq←numberoftransitionsdenedinstateq26freqq←frequencylabelofq27iftransq/freqq>T1ortransq>T228mergealltransitionsinstateq29generalize←True30ConvertLtodeterministicautomaton31MinimizeL3233//Phase2:ProtocolStateMachine34A←automatonAtobeextended35foreachSessions∈NetworkTracesdo36Seqs←SequenceofmessageformatsfromLthatacceptsthesequenceofmessagesofsessions37Ifneeded,addnewpathtoAtoacceptSeqs3839foreachpairofStatesq1,q2∈Ado40mergestatesq1andq2iftheyaredestinationstatesofanytwotransitionsinAwiththesamemessageformat41reduce←True42whilereduce=Truedo43reduce←False44foreachpairofStatesq1,q2∈Ado45ifthereisatransitionfromq1→q2,butnotq2→q1then46pairq1,q2←NonEquivalent47ifthereisnotransitionbetweenq1andq2ornocommontransitiondenedinq1andq2then48pairq1,q2←NonEquivalent49ifpairq1,q2=NonEquivalentthen50mergestatesq1andq251reduce←True52MinimizeA5354returnAAlgorithm1:Methodologyforcomplementinganexistingspecicationfromnetworktraces.
Ourapproachconsistsintwodistinctphases,onededicatedtothelanguageoftheprotocolandanotherphaseaddress-ingitsstatemachine.
Algorithm1depictsthelogicalstepsofthemethodologytoextendagivenspecicationfromnet-worktraces.
Noticethattheclientandserverspecicationsaretreatedseparately,sothemethodologyhastobeappliedtobothspecications.
Forthisreasonweuseindiscrim-inatelythetermsspecication,FSM,orautomatonwhilereferringtoeithertheclientorserverspecications.
2.
1Phase1:ProtocolLanguageOneofthethingsthatmightchangewithamorerecentversionofaprotocolisthesetofmessagesthatareaccepted,i.
e.
,thelanguageitrecognizes.
Novelmessagesorformatsmightbeintroduced,andtherefore,therststepconsistsincomplementingtheprotocollanguagewiththemessagesinthenetworktraces.
First,weextractalistofthemessageformatsthatareal-readydenedintheoriginalspecication(line10,andalsoseeFigure1foranexamplespecication).
Sinceweareaddressingtext-basedprotocols,messageformatsaremod-eledasregularexpressions.
Forexample,messagesUSERjantunesandUSERnnevescanbemodeledastheregularexpressionUSER.
*.
Thelistofextractedmessageformatsisacomprehensiveaccountofthelanguagerecognizedbytheprotocol,i.
e.
,anyprotocolmessagemustbeacceptedbyatleastoneoftheregularexpressions,unlessthemes-sagefollowssomeextensionyettobespecied.
WeusethelistofextractedmessageformatstobuildaFSMLfortheoriginalprotocollanguage(lines9–13).
Eachmes-sageformat(regularexpression)oftheextractedlististo-kenizedinwordsandwordseparators(e.
g.
,spaces,punc-tuationandanyotherspecialcharacters)(line12).
Hence,everymessageformatcorrespondstoasequenceoftokens,andwhenaddedtoLitwillcausethecreationofanewpathofstatesandtransitions(line13).
Forexample,ames-sageREST[0-9]+wouldbedividedintokensREST,thespacecharacter,and[0-9]+,andthepathwouldthereforebe:stateS1isconnectedtoS2bytransitionREST,S2isconnectedtostateS3byatransitionacceptingthespacecharacter,andnallyS3isconnectedtoS4bytransition[0-9]+.
Attheendofthisprocess,aFSMthatcanrec-ognizeallmessagesisproduced,withtheexceptionoftheextensions.
Thenextstepconsistsinidentifyingandaddingnewmes-sageformatsnotpresentintheoriginallanguageofthepro-tocol(lines14–18).
Thenetworktracesareparsed,andeachmessageistokenizedintoasequenceofwordsandwordsep-arators(line15)andgiventotheautomatonL.
Whenevertheautomatonfailstorecognizeanewsymbol(i.
e.
,awordorawordseparator)inaparticularstate,anewtransitionanddestinationstateiscreatedtoacceptit(line16).
Thefrequencythateachstateisvisitedduringtheconstructionofthenewpathsisrecorded,andeverynewtransitionislabeledforlateranalysis(lines17and18).
ThisresultsinaFSMthatacceptsboththepreviouslydenedmessagefor-matsandthenewmessagespresentinthenetworktraces.
However,noticethatthenewlycreatedpathsarenotgenericenoughtoacceptdierentinstancesofthesametypesofmessages(e.
g.
,ifapathwascreatedinLtoacceptthenewmessageSIZExg,itwouldnotacceptsimilarrequestswithdierentparameterslikeSIZEnewle).
Therefore,thenewpathsofstatesandtransitionsdonotyetrepresentamessageformat,whichmustdescribethecompositionandarrangementofeldsofagiventypeofmessage.
Inourapproach,afewadditionalstepsmustbefollowedinordertoidentifymessagesrelatedtosimilarrequestsandtoproducearegularexpressionthatcapturestheircommonformat.
Inanotherwords,wemustidentifytransitionsinLthatareassociatedwithpredenedvalues(e.
g.
,commandnames),whichshouldbeexplicitlydenedinthenewspecication,andtransitionsconcerningundeneddata(e.
g.
,parametersofcommands).
Toachievethisobjective,weapplytechniquessimilartoReverX[2]wheretransitionswithdatathatshouldbeab-stracted,suchasspecicparametersandothervariabledata,areidentiedandgeneralized(lines20–31).
Noticethatonlythetransitionscreatedforthenewmessages(inline16)canbegeneralizedandmergedtogether.
Theothertransitionscorrespondtothedenitionofmessageformatsthatwereex-tractedfromtheoriginalspecication,andareconsequentlyalreadygeneralized.
Hence,weonlyanalyzestatesinwhichalltransitionsarelabeledas"New"(line24).
Messageeldsassociatedwithpredenedvaluesshouldap-pearofteninthenetworktraces(e.
g.
,commandSIZE),asopposedtothevariableandlessrecurrentnatureofthere-spectiveparameters(e.
g.
,pathnamestoseveraldierentlessuchasxgor/libpcap.
tar.
Z,justtonameafew).
Pa-rameterdatacanthereforeberecognizedinstatesoftheau-tomatonthatacceptawiderangeofdierentvalues(eachoneisaparticularinstanceofthatparametereld),andtherefore,thathavealargenumberofoutgoingtransitions.
However,onecannotrelysolelyontheindividualfrequencyofeachtransition,orelsecommandsthatappearrarelyinthetracescouldbemisidentiedasparameters.
Therefore,weselectstatesofthelanguageFSMforgeneralizationifatleastoneoftheseconditionsaremet(line27):theratioofthenumberoftransitionsleavingfromastateoverthetotalfrequencyofthatstateisabovesomethreshold,T1;thetotalnumberoftransitionsislargerthansomepre-denedvalue,T2.
Transitionsoftheselectedstatesarethenmerged,i.
e.
,aregularexpressionisproducedtoacceptallvalues,andanewdestinationstateiscreatedbymergingtheformerdes-tinationstatesofthetransitions.
Afterallstateshavebeenanalyzed,theprocessisrepeatediftheFSMwasmodiedbyatleastonegeneralization(lines21and29).
Theresultingautomatonthusrecognizesthenewlanguageoftheproto-col,whereeachpath,composedasasequenceoftokensthatformaregularexpression,correspondstoadierentprotocolmessageformat.
2.
2Phase2:ProtocolStateMachineInthesecondphaseofthemethodology,weprocessindivid-ualapplicationsessionsfromthenetworktracestocomple-mentthestatemachineoftheprotocolwiththenewmessageformatsandcorrespondingprotocolstates.
Individualsessionsareextractedfromthetracesinordertoascertainthelogicalsequenceoftypesofmessagesthatwereexchangedbetweentheclientsandtheservers(line35).
DierentsessionscanbedistinguishedbytheclientIPaddressesandportsusedintheconnection,TCPse-quencenumbers,temporalgapsbetweenmessages,orsimplybyknowingwhichmessagesareusedintheinitialprotocolsetupasdenedintheoriginalspecication.
Sincethetraceswerealreadyusedtoinfertheprotocollan-guage,insteadoftheactualnetworkmessages,weusetherespectivemessageformatsthatwerederived(i.
e.
,thepathintheautomatonLthatacceptsthemessage).
Thus,everyapplicationsession,whichisasequenceofmessages,iscon-vertedintoasequenceofmessageformats(line36).
EachsequenceisfedtotheFSMoftheoriginalspecicationandnewstatesandtransitionsareaddedwhenevertheautoma-tonfailstoacceptthecompletesession(line37).
Forexam-ple,asessioncomposedofmessagesUSERjantunes,PASSxyz,andREST10isrstconvertedintothecorrespond-ingmessageformatsUSER.
*,PASS.
*,andREST[0-9]+;then,itisfedtotheoriginalspecication,andallmessagesareaccepted(seeFigure1).
IfthesessionincludedanovelmessagetypesuchasLPTR,thenanewtransitionwouldbecreatedintheautomationsothatitcouldbeaccepted.
However,sincewearedealingwithpotentiallyincompletedatasets(thenetworktracesareasampleoftheprotocolutilization),theautomatononlycapturesthesequenceofmessagesexactlyastheyappearinthetraces.
Cyclesandequivalentstatesmustthereforebeinferred.
Inthiswork,weuseasimilartechniquetoReverXtoidentifyandmergepotentiallyequivalentstatesandcycles.
First,weidentifystatesthatarereachedundersimilarcondi-tions,i.
e.
,fromthesamemessageformat,becausetheyprob-ablyrepresentthesameprotocolstate.
Hence,wemergeanydestinationstateoftransitionsthatdenethesamemes-sageformat(line40).
However,evensomestatesthatarereachedfromdierentmessagetypesmaycorrespondtothesameprotocolstate.
Forinstance,afterloggingin,ausermaycreate,edit,ordeleteles,allseeminglyinterchange-ableprotocolcommands(i.
e.
,thesameprotocolstatewithacycletoitself).
Withrespecttotheprotocolstatemachine,theorderofthesemessagesisirrelevantaftertheuserlogsin,andtheycanbeexecutedfromaprotocolstatethatacceptsanyofthem.
Todeduceacompleteprotocolstatemachine,inspiteoftheincompletenessofthenetworktraces,weneedtomakeafewassumptionsabouttheequivalenceofsomestates.
First,ifthereisatransitionfromonestatetoan-other,butnotviceversa,thisestablishesanexplicitcausalrelationandthustheyaredeemedasnon-equivalent(line45-46).
Second,protocolstateswithoutanyexplicitcausalrela-tion(i.
e.
,withoutanytransitionbetweenthemorwithtran-sitionsconnectingthestatesinbothdirections)andwithnocommontransitions(i.
e.
,statesacceptcompletelydierentmessageformats),arealsoconsideredasnon-equivalent(line47–48).
Consequently,anytwostatesthatwerenotlabeledasnon-equivalentareconsideredasequivalentandarethere-foremerged(lines49–50).
TheautomatonisthenminimizedFigure1:FSMfortheFTPprotocol(RFC959).
(whichwillproduceeventualcyclesbetweeninterchangeablestatesandtransitions)andthisentirereductionprocedureisrepeateduntilnomorestatescanbemerged(lines42and51).
Theresultingautomataisthenewcomplementedspec-icationoftheprotocolstatemachine.
Thenewlylabeledtransitionsalsorevealmoreclearlythechangesbroughtbythenetworktraces,whichcanhelpdevelopersandtesterstofocusonthenewpartofthespecication.
3.
EVALUATIONForthepurposeofevaluation,weappliedthemethodol-ogytocomplementaspecicationofawell-knownprotocol,withpubliclyavailablenetworktracesthatcontainedmes-sagetypesintroducedinsubsequentextensions.
WechosetheFileTransferProtocol(FTP)toillustratetheresultsbe-causeitiswidelyknownandutilized.
Inaddition,theFTPlanguageandstatemachineareeasilyperceivedfromtheexamples,whichmakesitaninterestingcasestudytoshowthepotentialresultsthatcanbeobtainedwiththemethod-ology.
Sincetheserverpartofthespecicationisrelativelysimple—itmostlydenesreplycodesandimplementation-specicresponsestrings—,weoptedtouseandcomplementonlytheFTPspecicationrelatedtothemessagestrans-mittedbytheclients.
Therefore,allautomataandnetworktracesconcerntheclient-sideoftheprotocolspecication.
AclientspecicationwasmanuallyproducedfortheoriginalFTPprotocolstandardpresentedinRFC959[19].
Figure1showstheFSMfortheoriginalclientFTP.
Itdeneseightstates,andthetransitionsarerelatedtothevariouscom-mandsthatcanbeexecutedineachstate.
Forexample,thersttwostates(S1andS2)correspondtotheinitialauthenticationprocesswheretheclientstartsbyindicatingtheusernamewithcommandUSERandthenprovidestheassociatedpasswordwithcommandPASS.
Thenetworktraceswereobtainedfrom320publicFTPserverslocatedattheLawrenceBerkeleyNationalLaboratory2.
Thetracesspanaperiodoftendaysandcontainover3.
2millionpack-etsfrom5832clients.
AprototypetoolwaswritteninJavatoimplementthemethodology.
ThetoolusesasinputtheFSMoftheorigi-nalprotocolspecicationandtheFTPclientrequests(i.
e.
,TCPmessagesfromthetracestransmittedtoport21).
Thetoolfollowsthemethodologyasdescribedintheprevious2http://ee.
lbl.
gov/anonymized-traces.
htmlTable1:DiscoveredmessageformatsandrespectiveRFCextensions.
MessageTypesIntroducedinXCWD,XPWDRFC775LPRTRFC1639FEAT,OPTSRFC1839EPSV,EPRTRFC2428SIZE,MDTM,MLSDRFC3659MACB,CLNTnon-standard169illegalrequestsN/Asection.
First,itproducesaFSMrecognizingtheknownlanguageoftheprotocol,whichisthenextendedwiththenewmessagesthatwerenotrecognized(phase1).
Then,thetoolcomplementstheprotocolspecicationusingthelanguageinferredpreviously,placingthenewmessagefor-matsinthecorrespondingprotocolstates,asdeterminedbythecausalrelationsobservedintheapplicationsessionsinthetraces(phase2).
Table1showsthenewtypesofmessagesthatthetoolfoundintheFTPtracesandtherespectiveRFCdocumentwheretheywerepublished.
Atotaloftwelvenewmessagetypeswereextractedandtheirformatinferred.
Additionally,thetooldetected169malformedprotocolrequeststhatconsistedmainlyofmisspelledcommandnames.
Toseparatetheseer-roneousmessagesfromtherest,wejustignoredcommandnamesthatappearedonlyonceinthetraces,eectivelypre-ventingthesemessagesfrombeingfurtherusedintheex-periments3.
Amongthetwelvecommands,thetooldiscoveredtwocom-mands(MACBandCLNT)thatwereneverpublishedordocumentedbyanyRFCextension.
MACBcommandissometimesusedbyFTPclientsrunningintheMacintoshOperatingSystems(e.
g.
,CuteFTPorWebTen)totransferlesinMacBinarymode,whileCLNTreferstoanobscurefeatureofaparticularFTPclient(NcFTP)apparentlyusedtoidentifyitandtoaccessshellutilities.
Littlemoreinfor-mationisavailableforthesetwonon-standardcommands,astheyarenotspeciedbyanyRFCorotherocialdocument.
Afteridentifyingthenewmessages,thetoolcomplementedtheoriginalspecicationwiththeobservedextensions(Fig-ure2showsthecomplementedspecicationwithchangesinbold).
Byanalyzingthetraces,thetoolwasabletodiscoverthecorrectstateoftheprotocolwherethemessageformatswerespeciedasextensions,i.
e.
,theprotocolstateaftertheuserloggedin(stateS4).
Naturally,thequalityofthederivedspecicationfortheprotocollanguageandstatemachinedependsontheval-uesofthegeneralizationparameters(T1andT2)4andonthecomprehensivenessofthenetworktraces,whichshouldcovertheprotocolextensionsonewishestoinfer.
Accord-ingly,anymessagetypemissingfromthetracescannotbe3Noticethatanyapproachthatusesdatatracestoinferortolearnsomemodelmustassumethecorrectnessofitstrainingdata,soitisacceptabletoignoretheseerroneousmessagesfromtheevaluation.
4Forastudyabouttheimpactofthegeneralizationparam-etervalues,T1andT2,wereferthereadertothetechnicalreport[2].
Figure2:FSMfortheFTPprotocol,complementedwithmessagetypesandprotocolstatesfromsubse-quentextensionstotheprotocol(indarker).
extracted,andthereforecannotbeusedtocomplementtheoriginalspecication.
Thisproblemcanbeaddressedifonehasaccesstoaclientandserverimplementationthatsup-portsthenewfeatures.
Inthiscase,thenewfunctionalityoftheclientcanbeexercised,thusproducinganetworktracethatcoverstheentireprotocolextensions,allowingthecre-ationofafullprotocolspecication.
4.
RELATEDWORKOurworkaimsatcomplementingexistingspecicationswithnewmessageformatsandprotocolstates.
Tothebestofourknowledgethereisnoworkdonewithafocusonautomat-icallycomplementingexistingprotocolspecicationsfromnetworktraces.
Thereis,however,asubstantialbodyofworkdedicatedtoprotocolspecications,suchasinconfor-mancetestingorinferringautomata.
Conformancetestingemergedfromtheneedtoensurethecomplianceofagivenimplementationwithapredenedspec-ication[13].
Itusuallyresortstonite-statemachinestoderivespecictestsequencesthattraversealltransitionstoverifytheconformanceofanimplementation.
Testse-quencesconsistofsetsofinputandexpectedoutputob-tainedfromthespecication,withthepurposeofcheckingiftheinput/outputtransitionsarecorrectlyexecutedbytheimplementation.
Otherapproachesusepassivetestingtoextractasetofinvariantsfromthespecication,andthencheckthemagainstthetracesproducedbyanimplementa-tion[6,3,25].
Automatainferenceisusedtoderiveapproximateprotocolspecicationswhenthereisnoformalspecicationavail-able.
Theproblemofinferringautomatafromincompletedatatraceshasbeentackledindierentresearchareasinthepast,fromnaturallanguagestobiologyandtosoftwarecomponentbehavior[10,4,21].
Typically,aprextreeac-ceptorisrstbuiltfromthetrainingset,acceptingallevents.
Then,similarstatesaremergedaccordingtotheirlocalbe-havior(e.
g.
,stateswiththesametransitionsorstatesthatacceptthesamekconsecutiveevents)[4,15].
Afewworkshavealsobeenfocusingontheinferenceofpro-tocolstatemachinespecications.
Prospexemploystaintanalysistoobtainexecutiontracesofaprogramforeachses-sion,whicharethenusedtobuildanacceptormachine[7].
PEXTutilizesnetworktracestoinferanapproximatestatemachinebyclusteringmessagesofthesametype,basedonadistancemetric,andbyanalyzingthesimilaritiesbetweendierentsequencesoftypesofmessagespresentobservedinthetraces[22].
Triloetal.
describesaprotocolreverseen-gineeringsolutionthatresortstothestatisticalanalysisofnetworktraces[23].
5.
CONCLUSIONSThispaperpresentsamethodologytocomplementexistingprotocolspecicationsfromnetworktraces.
Oursolutionhastheadvantageofnotcreatingacompletespecicationfromscratch,butbytakingadvantageofthepreviouslyde-ned(openprotocols)orinferred(closedprotocols)spec-icationsandfromnetworktracestocapturenewproto-colinteractionsbetweentheclientsandtheservers.
ThemethodologywasimplementedinaprototypetoolandwasevaluatedbycomplementingthestandardFTPspecica-tion(RFC959)withatracecollectedfrom320publicFTPservers.
Severalprotocolextensionsandtwonon-standardFTPtypesofrequestswerediscoveredandintegratedintheFTPspecication.
Theproposedapproachalsohastheadvantageofobtain-ingamorecompleteandrealisticspecicationbecauseitintegratestherulesandmessageformatsfrommultipleanddierentextensionsintoasinglespecication.
Thisuniedspecicationcapturestherealisticutilizationoftheprotocol,includingunpublishedorundocumentedfeaturespresentinthetraces.
Inthefuture,weintendtoextendthisworktosupporttheidenticationandsubsequentremovalofpoten-tiallyobsoletepartsofthespecication,suchasdeprecatedmessagetypes.
6.
ACKNOWLEDGMENTSThisworkwaspartiallysupportedbytheECthroughprojectFP7-257475(MASSIF)andbytheFCTthroughtheMulti-annualandtheCMU-PortugalProgrammes,andtheprojectPTDC/EIA-EIA/100894/2008(DIVERSE).
7.
REFERENCES[1]J.
Antunes,N.
Neves,M.
Correia,P.
Verissimo,andR.
Neves.
Vulnerabilityremovalwithattackinjection.
IEEETrans.
onSoftwareEngineering,36:357–370,2010.
[2]J.
Antunes,N.
Neves,andP.
Verissimo.
ReverX:Reverseengineeringofprotocols.
TechnicalReportTR-2011-01,FaculdadedeCienciasdaUniversidadedeLisboa,Jan.
2011.
[3]E.
Bayse,A.
Cavalli,M.
Nunez,andF.
Za¨di.
Apassivetestingapproachbasedoninvariants:ApplicationtotheWAP.
ComputerNetworks,48(2):247–266,2005.
[4]A.
BiermannandJ.
Feldman.
Onthesynthesisofnite-statemachinesfromsamplesoftheirbehavior.
IEEETrans.
onComputers,21(6):592–597,1972.
[5]J.
Caballero,H.
Yin,Z.
Liang,andD.
Song.
Polyglot:Automaticextractionofprotocolmessageformatusingdynamicbinaryanalysis.
InProc.
oftheConf.
onComputerandCommunicationsSecurity,2007.
[6]A.
Cavalli,C.
Gervy,andS.
Prokopenko.
Newapproachesforpassivetestingusinganextendednitestatemachinespecication.
InformationandSoftwareTechnology,45(12):837–852,2003.
[7]P.
M.
Comparetti,G.
Wondracek,C.
Kruegel,andE.
Kirda.
Prospex:Protocolspecicationextraction.
InIEEESecurityandPrivacy,2009.
[8]M.
Crispin.
InternetMessageAccessProtocol–Version4rev1(IMAP).
RFC3501(ProposedStandard),Mar.
2003.
[9]W.
Cui,M.
Peinado,K.
Chen,H.
Wang,andL.
Irun-Briz.
Tupni:Automaticreverseengineeringofinputformats.
InProc.
oftheConf.
onComputerandCommunicationsSecurity,2008.
[10]C.
delaHiguera.
GrammaticalInference:LearningAutomataandGrammars.
CambridgeUniversityPress,2010.
[11]R.
Droms.
DynamicHostCongurationProtocol(DHCP).
RFC2131(DraftStandard),Mar.
1997.
[12]J.
Klensin.
SimpleMailTransferProtocol(SMTP).
RFC5321(DraftStandard),2008.
[13]R.
Lai.
Asurveyofcommunicationprotocoltesting.
JournalofSystemsandSoftware,62(1):21–46,2002.
[14]Z.
Lin,X.
Jiang,D.
Xu,andX.
Zhang.
Automaticprotocolformatreverseengineeringthroughcontext-awaremonitoredexecution.
InProc.
oftheNetworkandDistributedSystemSecuritySymposium,2008.
[15]D.
Lo,L.
Mariani,andM.
Pezz`e.
Automaticsteeringofbehavioralmodelinference.
InProc.
ofthe7thjointmeetingoftheEuropeanSoftwareEngineeringConf.
andtheACMSIGSOFTInt.
Symp.
onFoundationsofSoftwareEngineering,pages345–354,2009.
[16]P.
Mockapetris.
Domainnames-implementationandspecication.
RFC1035(Standard),Nov.
1987.
[17]J.
MyersandM.
Rose.
PostOceProtocol–Version3(POP).
RFC1939(Standard),May1996.
[18]V.
Paxson.
Brointrusiondetectionsystem.
http://www.
bro-ids.
org/,accessedin2011.
[19]J.
PostelandJ.
Reynolds.
Filetransferprotocol(ftp).
RFC959,1985.
[20]R.
Russell.
Iptables.
http://www.
netfilter.
org/,rstreleasein1998.
[21]Y.
Sakakibara.
Grammaticalinferenceinbioinformatics.
IEEETrans.
onPatternAnalysisandMachineIntelligence,27(7):1051–1062,2005.
[22]M.
ShevertalovandS.
Mancoridis.
Areverseengineeringtoolforextractingprotocolsofnetworkedapplications.
InProc.
oftheWorkingConf.
onReverseEngineering,2007.
[23]A.
Tril`o,S.
Burschka,andE.
Biersack.
Tractoprotocolreverseengineering.
InProc.
oftheInt.
Conf.
onComputationalIntelligenceforSecurityandDefenseApplications,2009.
[24]G.
Wondracek,P.
Comparetti,C.
Kruegel,E.
Kirda,andS.
Anna.
Automaticnetworkprotocolanalysis.
InProc.
oftheNetworkandDistributedSystemSecuritySymp.
,2008.
[25]F.
Zaidi,E.
Bayse,andA.
Cavalli.
Networkprotocolinteroperabilitytestingbasedoncontextualsignaturesandpassivetesting.
InProc.
oftheACMSymp.
onAppliedComputing,2009.