Cascade-based attack vulnerability on the US power grid

SafetySciencejournalhomepage:www.elsevier.com/locate/ssciCascade-basedattackvulnerabilityontheUSpowergrid

Jian-WeiWang*,Li-LiRong

InstituteofSystemEngineering,DalianUniversityofTechnology,2LingGongRd.,Dalian116024,Liaoning,PRChinaarticleinfoabstract

Thevulnerabilityofreal-lifenetworkssubjecttointentionalattackshasbeenoneoftheoutstandingchal-lengesinthestudyofthenetworksafety.ApplyingtherealdataoftheUSpowergrid,wecomparetheeffectsoftwodifferentattacksforthenetworkrobustnessagainstcascadingfailures,i.e.,removalbyeitherthedescendingorascendingordersoftheloads.AdoptingtheinitialloadofanodejtobeLj¼½kjðRm2CjkmÞ󰀂awithkjandCjbeingthedegreeofthenodejandthesetofitsneighboringnodes,respectively,whereaisatunableparameterandgovernsthestrengthoftheinitialloadofanode,weinvestigatetheresponseoftheUSpowergridundertwoattacksduringthecascadingpropagation.Inthecaseofa<0:7,ourinvestigationbythenumericalsimulationsleadstoacounterintuitivefindingontheUSpowergridthattheattackonthenodeswiththelowestloadsismoreharmfulthantheattackontheoneswiththehighestloads.Inaddition,thealmostsameeffectoftwoattacksinthecaseofa¼0:7maybeusefulinfurtheringstudiesonthecontrolanddefenseofcascadingfailuresintheUSpowergrid.Ó2009ElsevierLtd.Allrightsreserved.Articlehistory:Received20November2008Receivedinrevisedform15January2009Accepted5February2009Keywords:CascadingfailureAttackUSpowergridCriticalthresholdTunableparameter1.IntroductionRecently,theresilienceofreal-worldnetworks(Albertetal.,2000;AlbertandBarabási,2002;Holmeetal.,2002;Strogatz,2001;Newman,2003;Gohetal.,2002)subjecttorandomorinten-tionalattackshasbeenoneofthemostcentraltopicsinnetworksafety.Manyreal-worldnetworkssuchastheInternet,theelectri-calpowergrid,thetransportationnetworks,andsoon,arerobusttorandomattacksbutvulnerabletointentionalattacks.Evidencehasdemonstratedthatinsuchnetworks,eventhoughintentionalattacksandrandomfailuresemergeverylocally,theentirenet-workcanbelargelyaffected,evenresultinginglobalcollapse.Typ-icalexamplesincludeseveralblackoutsinsomecountries,e.g.,thelargestblackoutinUShistorytookplaceon14August2003andtheWesternNorthAmericanblackoutsinJulyandAugust1996,andtheInternetcollapsecausedbycongestion,e.g.,atypicalexampleisrecentInternetcollapsecausedbythesubmarineearth-quakenearTaiwaninDecember2006.Thesesevereincidentshavebeenattributedtocascadingbehaviors,andhavebeenextensivelyexplored.Wuetal.(2008)studiedtheonsetandspreadingofcascadingfailureonweightedheterogeneousnetworksbyadoptingalocalweightedflowredistributionrule,wheretheweightandtolerancehhofanodewascorrelatedwithitslinkdegreekaskandCk,respec-tively.Lietal.(2008)proposedanovelcapacitymodelforcomplexnetworksagainstcascadingfailure,ofwhichverticeswithbothhigherloadsandlargerdegreeswerepaidmoreextracapacities,*Correspondingauthor.Tel.:+81181258693.E-mailaddress:wdut@yahoo.cn(J.-W.Wang).0925-7535/$-seefrontmatterÓ2009ElsevierLtd.Allrightsreserved.doi:10.1016/j.ssci.2009.02.002i.e.,theallocationofextracapacityonvertexiwouldbepropor-ctionaltoki,wherekiwasthedegreeofvertexiandc>0wasafreeparameter.MotterandLai(2002)proposedanewmodelforover-loadorcongestionbreakdownintheprocessofdatapackettrans-portoncomplexnetworksbyassigningthecapacityonanode.Holmeetal.(2002)discussedoverloadbreakdowninanevolvingwayandproposedamethodtoavoidsuchavalanchesbyusingaglobalanddynamicalsearchingalgorithm.Crucittietal.(2004)studiedcascadingfailuresbyintroducingefficiencydynamics.Simonsenetal.(2008)studiedcascadingfailuresinnetworksusingadynamicalflowmodelbasedonsimpleconservationanddistri-butionlaws.Itwasfoundthatconsideringtheflowdynamicsmightimplyreducednetworkrobustnesscomparedtopreviousstaticoverloadfailuremodels.Baoetal.(2008)introducedthecon-ceptofloadentropy,andtheninvestigatedthedynamicsofloadentropyduringthefailurepropagationusinganewcascadingfail-uresloadmodel.WangandChen(2008)investigateduniversalrobustnesscharacteristicofweightednetworksagainstcascadingfailurebyadoptingalocalweightedflowredistributionrule,wherehtheweightofanedgeisðkikjÞwithkiandkjbeingthedegreesofthenodesconnectedbytheedge.Inaddition,anumberofaspectsofcascadingfailureshavebeendiscussedinsomeliteratures,includingthecascadecontrolanddefensestrategy(ZhaoandGao,2007;Sunetal.,2008;Motter,2004;WangandKim,2007;AshandNewth,2007),themodelfordescribingcascadephenom-ena(Baoetal.,2008;WangandXu,2004;Wuetal.,2007),theana-lyticalcalculationofcapacityparameter(Wangetal.,2008;WangandRong,2008;Zhaoetal.,2004,2005),andsoon.Inallcitedstudiesabove,onehavefocusedonlyonthedynamicpropertiesofthenetworkshowingthattheremovalofagroupofnodesJ.-W.Wang,L.-L.Rong/SafetyScience47(2009)1332–13361333Fig.1.Theschemeillustratesthecorrelationbetweentheinitialloadofanodeianditsneighboringnodes,i.e.,nodesi1;i2;i3,andi4.altogethercanhaveimportantconsequences.However,therearefewworks(MotterandLai,2002)abouttheeffectsofdifferentat-tackstrategiesfortherobustnessagainstcascadingfailuresonreal-lifenetworks.Inviewoftheimportanceofthestudyofattacksonreal-lifenetworks,whichcanbeusedeitherforprotectioninmanyinfra-structurenetworks,e.g.,inanelectricalpowergrid,orfordestruc-tioninthespreadofrumorsandthecontrolofepidemicdiseases,wecomparetheeffectsoftwoattacksforthenetworkrobustnessagainstcascadingfailures,i.e.,theattacksofthenodeswiththehighestloadsandthelowestloads,respectively.AdoptingthefamousUSpowergrid,wenumericallyinvestigatetheuniversalcascadingphenomenon.Comparedwiththekeyroleofthehubnodesofnetworksinmanypreviouscascadingstudies,someinter-estingandcounterintuitiveresultsarefound.Itisexpectedthatourfindingswillbehelpfulforreal-lifenetworkstoprotectthekeynodesselectedeffectivelyandavoidcascading-failure-induceddisasters.2.ThemodelInallstudiescitedabove,theloadonanode(oranedge)wasgenerallyestimatedbyitsdegreeorbetweenness1andtheredistri-butionloadwereusuallyforwardedfollowingtheshortestpath.However,bothloadestimationandredistributionruleshavetheirowndrawbacks.Specially,theprinciplebasedonbetweennessisreasonableonlyforsmallormedium-sizednetworksduetotherequirementofstructuralinformationofthewholenetworks;whiletheprinciplebasedonnodedegreeoutweighsbyitssimplicity,butisinferiorowingtoitsonlyconsiderationofsinglenodedegree,whichlosesmuchinformationtherebyrestrictingmanyactualappli-cations.Therefore,howtobalancethecomplexityandtheinforma-tionquantityisasignificanttopic.

Toreducethecomplexityofthebetweennessandimprovethepracticabilityofthedegree,wepresentanewmeasuretoassigntheinitialloadofanode(seeFig.1).AssumethattheinitialloadLjofanodejinthenetworkisafunctionoftheproductofitsde-greekjandthesummationRm2Cjkmofthedegreesofitsneighbor-ingnodes,andisdefinedas:Laj¼½kjðRm2CjkmÞ󰀂,whereCj1Thebetweennessofanodecanbeobtainedbycountingthenumberofgeodesicsgoingit.Moreprecisely,thebetweennessbiofanodei,sometimesreferredload,isdefinedas:bi¼P

toalsoas

j;k2N;j–knjkðiÞ=njk,wherenjkisthenumberofshortestpathsconnectingjandk,whilenjkðiÞisthenumberofshortestpathsconnectingjandkandpassingthroughi.

Fig.2.Theschemeillustratestheloadredistributiontriggeredbyannode-basedattack.Nodeiisremovedandtheloadonitisredistributedtotheneighboringnodesconnectingtonodei.Amongtheseneighboringnodes,theonewiththehigherloadwillreceivethehighersharedloadfromthebrokennode.representsthesetofallneighboringnodesofthenodejandaisatunableparameter,whichcontrolsthestrengthoftheinitialloadofanode.Afteranodeiisattacked,itsloadwillberedistributedtoitsneighboringnodes(seeFig.2).TheadditionalloadDLjireceivedbythenodejisproportionaltoitsinitialload,i.e.,hiaDkLjRm2Cjkmji¼LLjiP¼Lin2CPiLn½kð1Þn2CinRf2Cnkf󰀂aThecapacityofanodeisthemaximumloadthatthenodecanhan-dle.Inman-madenetworks,thecapacityisseverelylimitedbycost.Thus,itisnaturaltoassumethatthecapacityCjofanodejispro-portionaltoitsinitialload(Wuetal.,2008;MotterandLai,2002;Crucittietal.,2004;WangandChen,2008;ZhaoandGao,2007;Sunetal.,2008;Motter,2004;Wangetal.,2008;WangandRong,2008;Zhaoetal.,2004,2005),i.e.,Cj¼TLj;j¼1;2;3;...;N,wheretheconstantTðP1Þisatoleranceparameter2,andNisthenumberofnodesinthenetwork.IfLjþDLji>Cj,thenthenodejwillbebro-kenandinducefurtherredistributionofflowLjþDLjiandpotentiallyfurtherbreakingofothernodes.Afterthecascadingprocessisover,wewillcalculatethenumberofbrokennodes.Tothisend,weuseCFitodenotetheavalanchesizeinducedbyremovingnodei.Itisevidentthat06CFi6NÀ1.Toquantifytheattack-basedrobust-nessofthewholenetwork,weadoptthenormalizedavalanchesize,i.e.,

PCFattack¼i2ACFiNAðNÀ1Þð2ÞwhereAandNArepresentsthesetandthenumberofnodesat-tacked,respectively.3.AnalysisofattackstrategiesInourcascadingmodel,givenavalueofa,whenthevalueofTissufficientlysmall,wecanimaginethatitiseasyforthe2Ingeneral,themoretheloadofanode,thestrongerthecapacityofthenode.Therefore,consideringthesimplicityofalinearrelationshipandinspiredbymanycascadingmodelscitedabove,weassumethatallthenodeshavethesametoleranceparameterT.However,foranonlinearrelationshipbetweenthecapacityandtheloadofsomerealcomplexnetworks,sinceitisverycomplicatedandmayfurtherincreasethefrequencyofoverloadscomparedwithalinearrelationship,thereisfewworksonexploringtheimpactonthismodel.

1334J.-W.Wang,L.-L.Rong/SafetyScience47(2009)1332–1336wholenetworktofullycollapseinthecaseofanarbitrarynodefailurebecausethecapacityofeachnodeislimited.Ontheotherhand,forsufficientlylargeT,sinceallnodeshavethelargerextracapacitiestohandletheload,nocascadingfailureoccursandthesystemmaintainsitsnormalandefficientfunctioning.Thus,withtheincreaseofT,thereshouldbesomecrossoverbehaviorofthesystemfromlargescalebreakdowntonobreakdown,goingthroughsmallscaleones.Therefore,inspiredbymanypreviousstudies(Wuetal.,2008;WangandChen,2008;Wangetal.,2008;WangandRong,2008),wealsousethecrossoverbehaviortoquantifythenetworkrobustness,i.e.,thecriticalthresholdTc,atwhichaphrasetransitionoccursfromnormalstatetocollapse.WhenT>Tc,thesystemmaintainsitsnormalandefficientfunc-tioning;whilewhenT0:5.

Fig.3illustratesthenormalizedavalanchesizeCFattackaftercas-cadingfailuresofallattackednodes,asafunctionofthetoleranceparameterT,fortheelectricalpowergridofthewesternUnited3Inourstudy,toaccordwiththepositiveproportioncorrelationbetweentheinitialloadofanodejandkjðRm2CjkmÞ,weseta>0.Inaddition,takingtheimpactoftheproductofkjandRm2Cjkm,wesimplychoosetworanges,i.e.,00:5.

1.0 α=0.5(LL) α=0.5(HL)0.8 α=0.4(LL) α=0.4(HL) α=0.3(LL)kc0.6 α=0.3(HL)att α=0.2(LL)aF0.4 α=0.2(HL)CTc α=0.1(LL)0.2 α=0.1(HL)0.01.01.11.21.31.41.51.61.71.8TFig.3.Illustrationoftherelationbetweentwoattackstrategiesinthecaseofa60:5.States.Itisoriginalexpectedthatthepresenceofafewnodeswithlargerloadshasadisturbingsideeffect:theattackonthenodeswiththehighestloadsmaybepronetotriggeracascadeofover-loadfailurescapableofdisablingthenetworkalmostentirelythantheattackontheoneswiththelowestloads.However,asaresult,ourfindingsisonthecontrary,i.e.,thebiggercascadescanbemorelikelytobetriggeredbytheLLthanbytheHLwhena60:5,asshowninFig.3.Wefurthermoretrytoexplainthiscounterintuitivephenome-nonbyadoptingtwosub-graphsofanetwork(seeFig.4).AssumeFig.4tobetwodifferentpartsofanetwork.Whena¼0:2,wecomparethelocaleffectsoftwoattacksonnodeswiththehigherorlowerloadsforthenetworkrobustness.Inordertoavoidthebreakdownoftheneighboringnodes,wefindthatthelowestvalueofthecapacityparameterais1.2872and1.5intwocasesofthefailuresofthenodesiandjinFig.4,respectively.Therefore,inthiscasethenodewiththelowerloadsplaysmoreimportantinnet-worksafetythantheonewiththehigherloads.InFig.3,onecansee:thebiggerthevaluea,thesmallerthedifferenceoftheeffectsoftwoattacks.Inaddition,asthevalueoftheparameteraincreasesfrom0.1to0.5,wecanalsoseetwointerestingphenomenainourcascadingmodel:ontheonehand,thenetworkrobustnesshasanegativecorrelationwithaundertheHL(i.e.,theestimatecriticalthresholdTcispositivecor-relationwitha);whileontheotherhand,thenetworkrobustnesshasapositivecorrelationwithaundertheLL.Ourfindinghasanimportantimplicationthatitcanprovideguidanceinprotectingsomenodesselectedeffectivelytoavoidingcascading-failure-in-duceddisastersaccordingtothedifferentcasesinreal-lifenetworks.Inthecaseofa>0:5,wealsocheckthenetworkrobustnessun-dertwoattacksinFig.5.Itiseasytofindtwospecialpoint,i.e.,a¼0:6anda¼0:7.Inthecaseofa¼0:6,theHLismoreeffectivethantheLLinthebiggeravalanchesizeofthebrokennodesin-ducedbycascadingfailures,whilebasedontheobtainedestimateTcbyCFattack,theresultisonthecontrary.Whena¼0:7,thealmostsameTcoriginatingfromtwoattacksisalsodifferentfrommanypreviousstudiesoncascadingfailures.Inaddition,whena>0:7,theHDisanefficientwaytodestructtheelectricalpowergridofthewesternUnitedStates.WefurtherinvestigatetherelationshipbetweenthecriticalthresholdTcandtheparameteraundertwoattacks.AsshowninFig.6,switchingoftheefficiencyoftwoattacksexistsatthepointofa¼0:7.J.-W.Wang,L.-L.Rong/SafetyScience47(2009)1332–13361335Fig.4.Acomparisonbetweentheeffectsofthebreakdownsoftwonodeswiththehigher(nodei)orlowerloads(nodej)fortheirsneighboringnodes,i1,i2,i3,i4,j1,andj2.Forexample,toavoidthefailuresoftheneighboringnodes,itisfoundwhena¼0:2thatthelowestvaluesofthecapacityparameterTare1.2872and1.5intwocasesoftheremovalsofthenodesiandj,respectively,andtheLLstrategyismorelikelytotriggercascadingfailures;whena¼1:2,thelowestvaluesofthecapacityparameterTare1.5743and1.5,respectively,andtheHLstrategyisharmfultodisrupttheUSpowergridthantheLLone.1.00.80.60.40.20.01.0 α=1(LL)CFattackTc α=1(HL) α=0.9(LL) α=0.9(HL) α=0.8(LL) α=0.8(HL) α=0.7(LL) α=0.7(HL) α=0.6(LL) α=0.6(HL)1.11.21.31.41.51.61.71.8aP0:6.robustnessundertwoattacks.Someinterestingandcounterintui-tiveresultsarefoundinourcascadingmodel,ofwhichaninterest-ingfindingisthattheattackonthenodeswiththelowestloadsisamoreeffectivemaytodestroytheelectricalpowergridofthewes-ternUnitedStatesduetocascadingfailureswhena<0:7.Itisalsofoundthattheeffectsoftwoattacksarealmostidenticalwhena¼0:7.Thestudyofattacksoncomplexnetworksisimportantinordertoidentifytherobustnessandvulnerabilityofreal-lifenetworks,whichcanbeusedeitherforprotectioninmanyinfrastructurenet-works,e.g.,inanelectricalpowergrid,orfordestructioninthespreadofrumorsandthecontrolofepidemicdiseases.Ourworkmayhavepracticalimplicationsforprotectingthekeynodesse-lectedeffectivelyandavoidcascading-failure-induceddisastersintherealworld.AcknowledgementsThisworkwassupportedbytheNationalNaturalScienceFoun-dationofChinaunderGrantNos.70571011and70771016.ReferencesAlbert,R.,Barabási,A.-L.,2002.Statisticalmechanicsofcomplexnetworks.Rev.Mod.Phys.74,47.Albert,R.,Jeong,H.,Barabási,A.-L.,2000.Attackanderrortoleranceincomplexnetworks.Nature406,387.Ash,A.,Newth,D.,2007.Optimizingcomplexnetworksforresilienceagainstcascadingfailure.PhysicaA380,673.Bao,Z.J.,Cao,Y.J.,Ding,L.J.,Han,Z.X.,Wang,G.Z.,2008.Dynamicsofloadentropyduringcascadingfailurepropagationinscale-freenetworks.Phys.Lett.A372,5778.Bao,Z.J.,Gao,Y.J.,Ding,L.J.,Wang,G.Z.,Han,Z.X.,2008.Synergeticbehaviorinthecascadingfailurepropagationofscale-freecoupledmaplattices.PhysicaA387,5922.Crucitti,P.,Latora,V.,Marchiori,M.,2004.Modelforcascadingfailuresincomplexnetworks.Phys.Rev.E69,045104.Goh,K.-I.,Kahng,B.,Kim,D.,2002.Fluctuation-drivendynamicsoftheinternettopology.Phys.Rev.Lett.88,108701.Holme,P.,Kim,B.J.,Yoon,C.N.,Han,S.K.,2002.Attackvulnerabilityofcomplexnetworks.Phys.Rev.E65,056109.Li,P.,Wang,B.H.,Sun,H.,Gao,P.,Zhou,T.,2008.Alimitedresourcemodeloffault-tolerantcapabilityagainstcascadingfailureofcomplexnetwork.Eur.Phys.J.B62,1.Motter,A.E.,2004.Cascadecontrolanddefenseincomplexnetworks.Phys.Rev.Lett.93,098701.Motter,A.E.,Lai,Y.C.,2002.Cascade-basedattacksoncomplexnetworks.Phys.Rev.E66,065102.Newman,M.E.J.,2003.Thestructureandfunctionofcomplexnetworks.SIAMRev.45,167.Simonsen,I.,Buzna,L.,Peters,K.,Bornholdt,S.,Helbing,D.,2008.Transientdynamicsincreasingnetworkvulnerabilitytocascadingfailures.Phys.Rev.Lett.100,218701.Strogatz,S.H.,2001.Exploringcomplexnetworks.Nature(London)410,268.Sun,H.J.,Zhao,H.,Wu,J.J.,2008.Arobustmatchingmodelofcapacitytodefensecascadingfailureoncomplexnetworks.PhysicaA387,31.Wang,W.X.,Chen,G.R.,2008.Universalrobustnesscharacteristicofweightednetworksagainstcascadingfailure.Phys.Rev.E77,026101.TFig.5.Illustrationoftherelationbetweentwoattacksinthecaseof1.91.81.71.6 LL HLTc1.51.41.31.21.10.10.20.30.40.50.60.70.80.91.0αFig.6.RelationbetweenthecriticalthresholdTcandtheparameterattacks.aundertwo4.ConclusionInsummary,adoptingthelocalpreferentialredistributionruleofanoverloadnode,weinvestigatetheeffectsoftwoattackforthenetworkrobustnessagainstcascadingfailuresontheelectricalpowergridofthewesternUnitedStates.AssumingtheinitialloadofanodejtobeLj¼½kjðRm2CjkmÞ󰀂awithkjandCjbeingthedegreeofthenodejandthesetofitsneighboringnodes,respectively,whereaisatunableparameterandgovernsthestrengthofthenodeload,wenumericallyobtaintheestimateforthenetwork1336J.-W.Wang,L.-L.Rong/SafetyScience47(2009)1332–1336Wu,J.J.,Sun,H.J.,Gao,Z.Y.,2007.Cascadingfailuresonweightedurbantrafficequilibriumnetworks.PhysicaA386,407.Wu,Z.X.,Peng,G.,Wang,W.X.,Chan,S.,Wong,E.E.M.,2008.Cascadingfailurespreadingonweightedheterogeneousnetworks.J.Stat.Mech.,P05013.Zhao,H.,Gao,Z.-Y.,2007.Cascadedefensevianavigationinscalefreenetworks.Eur.Phys.J.B57(1),95.Zhao,L.,Park,K.,Lai,Y.C.,2004.Attackvulnerabilityofscale-freenetworksduetocascadingbreakdown.Phys.Rev.E70,035101(R).Zhao,L.,Park,K.,Lai,Y.C.,Ye,N.,2005.Toleranceofscale-freenetworksagainstattack-inducedcascades.Phys.Rev.E72,025104.Wang,B.,Kim,B.J.,2007.Ahigh-robustnessandlow-costmodelforcascadingfailures.Europhys.Lett.78,48001.Wang,J.W.,Rong,L.L.,2008.Effectattackonscale-freenetworksduetocascadingfailures.Chin.Phys.Lett.25,3826.Wang,X.F.,Xu,J.,2004.Cascadingfailuresincoupledmaplattices.Phys.Rev.E70,056113.Wang,J.W.,Rong,L.L.,Zhang,L.,Zhang,Z.Z.,2008.Attackvulnerabilityofscale-freenetworksduetocascadingfailures.PhysicaA387,6671.Watts,D.J.,Strogatz,S.H.,1998.Collectivedynamicsof’small-world’networks.Nature393,440.