[ Pobierz całość w formacie PDF ]
FastDetectionofScanningWormInfections
StuartE.Schechter
1
,JaeyeonJung
2
,andArthurW.Berger
2
1
HarvardDEAS,
33OxfordStreet,CambridgeMA02138,USA,
stuart@eecs.harvard.edu
2
MITCSAIL,
32VassarStreet,CambridgeMA02139,USA,
f
jyjung,awberger
g
@csail.mit.edu
Abstract.Wormdetectionandresponsesystemsmustactquicklyto
identifyandquarantinescanningworms,aswhenleftuncheckedsuch
wormshavebeenabletoinfectthemajorityofvulnerablehostsonthe
Internetinamatterofminutes[9].Wepresentahybridapproachtode-
tectingscanningwormsthatintegratessignificantimprovementswehave
madetotwoexistingtechniques:sequentialhypothesistestingandcon-
nectionratelimiting.Ourresultsshowthatthistwo-prongedapproach
successfullyrestrictsthenumberofscansthatawormcancomplete,is
highlye®ective,andhasalowfalsealarmrate.
1Introduction
Humanreactiontimesareinadequatefordetectingandrespondingtofastscan-
ningworms,suchas
Slammer
,whichcaninfectthemajorityofvulnerablesys-
temsinamatterofminutes[18,9].Thus,today’swormresponseproposalsfocus
on
automated
responsestoworms,suchasquarantininginfectedmachines[10],
automaticgenerationandinstallationofpatches[14,15],andreducingtherateat
whichwormscanissueconnectionrequestssothatamorecarefullyconstructed
responsecanbecrafted[22,27].
Evenanautomatedresponsewillbeoflittleuseifitfailstobetriggered
quicklyafterahostisinfected.Infectedhostswithhigh-bandwidthnetworkcon-
nectionscaninitiatethousandsofconnectionrequestspersecond,eachofwhich
hasthepotentialtospreadtheinfection.Ontheotherhand,anautomated
responsethattriggerstooeasilywillerroneouslyidentifyhostsasinfected,in-
terferingwiththesehosts’reliableperformanceandcausingsignificantdamage.
Manyscandetectionmechanismsrelyupontheobservationthatonlyasmall
fractionofaddressesarelikelytorespondtoaconnectionrequestatanygiven
port.ManyIPv4addressesaredeadendsastheyarenotassignedtoactivehosts.
Othersareassignedtohostsbehindfirewallsthatblocktheportaddressedbythe
scanner.Whenconnectionrequestsdoreachactivehosts,manywillberejected
asnotallhostswillberunningthetargetedservice.Thus,scannersarelikelyto
havealowrateofsuccessfulconnections,whereasbenignhosts,whichonlyissue
connectionrequestswhenthereisreasontobelievethataddresseeswillrespond,
willhaveamuchgreaterrateofsuccess.
Existingmethodsfordetectingscanningwormswithinalocalnetworkuse
fixedthresholdsforthenumberofallowablefailedconnectionsoveratimepe-
riod[16]orlimittherateatwhichahostcaninitiatecontactwithadditional
hosts[27].However,thesethresholdbasedapproachesmayfailtodetectlow-rate
scanning.Theymayalsorequireanexcessivenumberofconnectionobservations
todetectaninfectionorleadtoanunnecessarynumberoffalsealarms.
Todetectinboundscansinitiatedbyhostsoutsidethelocalnetwork,pre-
viousworkonwhichwecollaborated[7]usedanapproachbasedonsequential
hypothesistesting.Thisapproachautomaticallyadjuststhenumberofobserva-
tionsrequiredtodetectascanwiththestrengthoftheevidencesupportingthe
hypothesisthattheobservedhostis,infact,scanning.Theadvantageofthis
approachisthatitcanreducethenumberofconnectionrequeststhatmustbe
observedtodetectthataremotehostisscanningwhilemaintaininganaccept-
ablefalsealarmrate.
Whilethisapproachshowspromiseforquicklydetectingscanningbyhosts
insidealocalnetworksoonaftertheyhavebeeninfectedbyaworm,there
aresignificanthurdlestoovercome.Forone,todeterminewhetherarequestto
connecttoaremotehostwillfail,onemustoftenwaittoseewhetherasuccessful
connectionresponsewillbereturned.Untilenoughconnectionrequestscanbe
establishedtobefailures,asequentialhypothesistestwilllacktheobservations
requiredtoconcludethatthesystemisinfected.Bythetimethedecisionto
quarantinethehostismade,awormwithahighscanratemayhavealready
targetedthousandsofotherhosts.
Thisearlierworkusedasinglesequentialhypothesistestperhostanddid
notre-evaluatebenignhostsovertime.Unlikeanintrusiondetectionsystemob-
servingremotehosts,awormdetectionsystemislikelytoobservebenigntra±c
originatingfromaninfectedhostbeforeitisinfected.Itisthereforenecessary
toadaptthismethodtocontinuouslymonitorhostsforindicationsofscanning.
WDS
Fig.1.AWormDetectionSystem(WDS)islocatedtomonitoralocalnetwork
WeintroduceaninnovativeapproachthatenablesaWormDetectionSystem
(WDS)tocontinuouslymonitorasetof
local
hostsforinfection,requiringasmall
numberofobservationstobecollectedafteraninfectiontodetectthatthehost
isscanning(Figure1).
Todetectinfectedhosts,theWDSneedonlyprocessasmallfractionof
networkevents;asubsetofconnectionrequestobservationsthatwecall
first-
contactconnection
requestsandtheresponsestotheserequeststhatcomplete
theconnections.Afirst-contactconnectionrequestisapacket(TCPorUDP)
addressedtoahostwithwhichthesenderhasnotpreviouslycommunicated.
Theseeventsaremonitoredbecausescansaremostlycomposedoffirst-contact
connectionrequests.
InSection2,weintroduceascandetectionalgorithmthatwecallareverse
sequentialhypothesistest(
á¡
HT
),andshowhowitcanreducethenumberoffirst-
contactconnectionsthatmustbeobservedtodetectscanning
3
.Unlikeprevious
methods,thenumberofobservations
á¡
HT
requirestodetecthosts’scanning
behaviorisnota®ectedbythepresenceofbenignnetworkactivitythatmaybe
observedbeforescanningbegins.
InSection3,weintroduceanewcredit-basedalgorithmforlimitingthe
rateatwhichahostmayissuethefirst-contactconnectionsthatareindica-
tiveofscanningactivity.Thiscredit-basedconnectionratelimiting(CBCRL)
algorithmresultsinsignificantlyfewerfalsepositives(unnecessaryratelimiting)
thanexistingapproaches.
Whencombined,thistwo-prongedapproachise®ectivebecausethesetwo
algorithmsarecomplementary.Withoutcredit-basedconnectionratelimiting,a
wormcouldrapidlyissuethousandsofconnectionrequestsbeforeenoughcon-
nectionfailureshavebeenobservedbyReverseSequentialHypothesisTestingso
thatitcanreporttheworm’spresence.BecauseReverseSequentialHypothesis
Testingprocessesconnectionsuccessandfailureeventsintheorderthatcon-
nectionrequestsareissued,falsealarmsarelesslikelytooccurthanifweused
anapproachpurelybasedoncredit-basedconnectionratelimiting,forwhich
first-contactconnectionsattemptsareassumedtofailuntiltheevidenceproves
otherwise.
Wedemonstratetheutilityofthesecombinedalgorithmswithtrace-driven
simulations,describedinSection4,withresultspresentedinSection5.The
limitationsofourapproach,includingstrategiesthatwormscouldattemptto
avoiddetection,arepresentedinSection6.Wediscussrelatedwork,including
previousapproachestothescanningwormdetectionproblem,inSection7.Our
plansforfutureworkarepresentedinSection8,andweconcludeinSection9.
2DetectingScanningWormsbyUsing
ReverseSequentialHypothesisTesting
Awormisaformofmalwarethatspreadsfromhosttohostwithouthuman
intervention.Ascanningwormlocatesvulnerablehostsbygeneratingalistof
addressestoprobeandthencontactingthem.Thisaddresslistmaybegener-
atedsequentiallyorpseudo-randomly.Localaddressesareoftenpreferentially
3
Thelettersinthisabbreviation,
á¡
HT
,standforHypothesisTestingandthearrow
indicatesthereversesequentialorderinwhichobservationsareprocessed.
selected[25]ascommunicationbetweenneighboringhostswilllikelyencounter
fewerdefenses.ScansmaytaketheformofTCPconnectionrequests(SYNpack-
ets)orUDPpackets.InthecaseoftheconnectionlessUDPprotocol,itispossible
forthescanningpackettoalsocontainthebodyofthewormaswasthecase
withthe
Slammer
worm[9].
Inthissection,wepresentanon-linealgorithmfordetectingthepresenceof
scannerswithinalocalnetworkbyobservingnetworktra±c.Weuseasequential
hypothesistestforitsabilitytoadjustthenumberofobservationsrequiredto
makeadecisiontomatchthestrengthoftheevidenceitispresentedwith.
2.1SequentialHypothesisTesting
Aswithexistingapproachestoscandetection[7,17,22,27],werelyuponthe
observationthatonlyasmallfractionofaddressesarelikelytorespondtoa
connectionrequestatanygivenport.Benignhosts,whichonlycontactsystems
whentheyhavereasontobelievethatthisconnectionrequestwillbeaccepted,
aremorelikelytoreceivearesponsetoaconnectionrequest.
Recallthatafirst-contactconnectionrequestisapacket(TCPorUDP)
addressedtoahostwithwhichthesenderhasnotpreviouslycommunicated.
Whenalocalhost
l
initiatesafirst-contactconnectionrequesttoadestination
address,
d
,weclassifytheoutcomeaseithera“success”ora“failure”.Ifthe
requestwasaTCPSYNpacket,theconnectionissaidtosucceedifaSYN-ACK
isreceivedfrom
d
beforeatimeoutexpires.IftherequestisaUDPpacket,
anyUDPpacketfrom
d
receivedbeforethetimeoutwilldo.Welet
Y
i
bea
random(indicator)variablethatrepresentstheoutcomeofthe
i
th
first-contact
connectionrequestby
l
,where
½
0iftheconnectionsucceeds
1iftheconnectionfails
Y
i
=
Detectingscanningbylocalhostsisaproblemthatiswellsuitedforthe
methodof
sequentialhypothesistesting
firstdevelopedbyWald[24],andused
inourearlierworktodetectremotescanners[7].
Wecall
H
1
thehypothesisthathost
l
isengagedinscanning(indicating
infectionbyaworm)and
H
0
thenullhypothesisthatthehostisnotscanning.We
assumethat,conditionalonthehypothesis
H
j
,therandomvariables
Y
i
jH
j
i
=
1
;
2
;:::
areindependentandidenticallydistributed(i.i.d.).Thatis,conditional
onthehypothesis,anytwoconnectionattemptswillhavethesamelikelihood
ofsucceeding,andtheirchancesofsuccessareunrelatedtoeachother.Wecan
expressthedistributionoftheBernoullirandomvariable
Y
i
as:
Pr[
Y
i
=0
jH
0
]=
µ
0
;
Pr[
Y
i
=1
jH
0
]=1
¡µ
0
Pr[
Y
i
=0
jH
1
]=
µ
1
;
Pr[
Y
i
=1
jH
1
]=1
¡µ
1
Giventhatconnectionsoriginatingatbenignhostsaremorelikelytosucceed
thanthoseinitiatedbyascanner,
µ
0
>µ
1
.
Sequentialhypothesistestingchoosesbetweentwohypothesesbycomparing
thelikelihoodsthatthemodelwouldgeneratetheobservedsequenceofevents,
Y
n
´
(
Y
1
;:::;Y
n
),undereachhypothesis.Itdoesthisbymaintainingtheratio
¤
(Y
n
),thenumeratorofwhichisthelikelihoodthatthemodelwouldgenerate
thesequenceofeventsY
n
underhypothesis
H
1
,andthedenominatorunder
hypothesis
H
0
.
¤
(Y
n
)
´
Pr[Y
n
jH
1
]
Pr[Y
n
jH
0
]
(1)
Thei.i.d.assumptioninthemodelenablesustostatethisratiointermsof
thelikelihoodsoftheindividualevents.
n
Y
Pr[
Y
i
jH
1
]
Pr[
Y
i
jH
0
]
¤
(Y
n
)
´
(2)
i
=1
Wecanwritethechangeto
¤
(Y
n
)asaresultofthe
i
th
observationas
Á
(
Y
i
):
8
<
µ
1
µ
0
if
Y
i
=0(success)
Á
(
Y
i
)
´
Pr[
Y
i
jH
1
]
Pr[
Y
i
jH
0
]
=
:
1
¡µ
1
1
¡µ
0
if
Y
i
=1(failure)
Thisenablesustorewrite
¤
(Y
n
)inductively,suchthat
¤
(Y
0
)=1,and
¤
(Y
n
)maybecalculatediterativelyaseachobservationarrives.
n
Y
¤
(Y
n
)=
Á
(
Y
i
)=
¤
(Y
n¡
1
)
Á
(
Y
n
)
i
=1
Onecomparesthelikelihoodratio
¤
(Y
n
)toanupperthreshold,
´
1
,above
whichweaccepthypothesis
H
1
,andalowerthreshold,
´
0
,belowwhichweaccept
hypothesis
H
0
.If
´
0
<¤
(Y
n
)
<´
1
thentheresultwillremaininconclusiveuntil
moreeventsinthesequencecanbeevaluated.ThisisillustratedinFigure2.
h
1
0
1
0
1
0
1
h
0
Y
1
Y
2
Y
3
Y
4
Y
5
Fig.2.Alogscalegraphof
¤
(Y)aseachobservation,
Y
i
,isaddedtothesequence.
Eachsuccess(0)observationdecreases
¤
(Y),movingitclosertothebenignconclusion
threshold
´
0
,whereaseachfailure(1)observationincreases
¤
(Y),movingitcloserto
theinfectionconclusionthreshold
´
1
Writingtheprobabilityofcorrectlyreportingdetection(declaringhostis
infectedwhenindeeditis)as
P
D
andtheprobabilityofafalsepositive(declaring
[ Pobierz całość w formacie PDF ]
