Abstrakt. Tänk på följande spel mellan en mask och en alert 3 över ett nätverk av n noder. Inledningsvis är inga noder infekterade eller larmade och varje nod i nätverket är en speciell detektornod oberoende med liten men konstant sannolikhet. Spelet börjar med en enda nod som blir infekterad. I varje omgång därefter skickar varje infekterad nod ut ett konstant antal maskar till andra noder i befolkningen, och varje larmad nod skickar ut ett konstant antal varningar. Noder i nätverket ändrar tillstånd enligt följande fyra regler: 1) Om en mask tas emot av en nod som inte är en detektor och inte är varnad, att nod blir infekterad; 2) Om en mask tas emot av en nod som är en detektor, att nod blir varnad; 3) Om en varning tas emot av en nod som inte är infekterad, att nod blir varnad; 4) Om en mask eller en varning tas emot av en nod som redan är infekterad eller redan varnad, då finns det ingen förändring i tillståndet för den noden. Vi gör två antaganden om det här spelet. För det första, att en infekterad nod kan skicka mask meddelanden till någon annan nod i nätverket, men i motsats, en larmad nod kan skicka varningsmeddelanden endast genom en tidigare bestämd, konstant grad overlay nätverk. För det andra antar vi att de infekterade noderna är intelligenta, samordnade och i huvudsak allvetande. Med andra ord vet de infekterade noderna allt utom vilka noder som är detektorer och de larmade nodernas slumpmässiga myntflips d.v.s. De känner till topologin för det overlay-nätverk som används av larmen, vilka noder som larmas och som är infekterade när som helst, var varningar och maskar skickas, den övergripande strategi som används av de larmade noderna, etc. De larmade noderna antas inte veta något om vilka andra noder som är infekterade eller larmade, där varningar eller maskar skickas, eller den strategi som används av de infekterade noderna. Finns det en strategi för de larmade noderna som bara säkerställer en försvinnande liten del av noderna blir infekterade, oavsett vilken strategi som används av de infekterade noderna? Förvånansvärt nog är svaret ja. I synnerhet visar vi att en enkel strategi uppnår detta resultat med sannolikhet närmar sig 1 förutsatt att overlay nätverket har bra nod expansion. Specifikt, Detta resultat håller om d ≥ α och, Där α och 3 Specifikt, Vi anser självcertifierande varningar [6], som innehåller korta bevis på att en säkerhetsbrist finns och därmed eliminera falska varningar. β representerar hastigheten för spridningen av larmet respektive masken; γ är sannolikheten för att en nod är en detektornod; d är graden av överlagringsnätet; och c är nodexpansion av överlagringsnätet. Därefter ger vi empiriska resultat som tyder på att våra algoritmer för larmet kan vara användbara i nuvarande storskaliga nätverk. Slutligen visar vi att om overlay-nätverket har dålig expansion, särskilt om (1 − γ)β > d, då masken sannolikt infekterar nästan alla noder som inte är detektorer.
I REF, Aspnes et al. visa att det finns en enkel strategi för att förhindra alla utom en liten bråkdel av noder från att bli infekterade och, om nätverket har dålig expansion, masken kommer att infektera nästan alla noder.
Worm Versus Alert: Who Wins in a Battle for Control of a Large-Scale Network?
{'venue': 'OPODIS', 'journal': None, 'mag_field_of_study': ['Computer Science']}