DISco:aDistributedInformationStorefornetworkChallengesandtheir Outcome 2 ∗ 1 SylvainMartin a, LaurentChiarelloa GuyLeduca 0 aResearchUnitinNetworking,InstitutMontefiore,4000Liège,Belgium 2 n a J Abstract 5 1WepresentDISco,astorageandcommunicationmiddlewaredesignedtoenabledistributedandtask-centricautonomiccontrolofnetworks. DIScoisdesignedtoenablemulti-agentidentificationofanomaloussituations–so-called“challenges”–andassistcoordinatedremediation ]that maintains degraded – but acceptable – service level, while keeping a track of the challenge evolution in order to enable human-assisted I Ndiagnosisofflawsinthenetwork.Weproposetousestate-of-artpeer-to-peerpublish/subscribeanddistributedstorageascorebuildingblocks fortheDIScoservice. . s c [ 1. Introduction operation of the network and therefore threatens the quality, 1 v availability of the services it delivers. This definition includes 3 Networkmonitoringmostlyfollowalocation-centric,hierar- maliciousattacks,mis-configurations,accidentalfaultsandop- 7chical processing [1] of information where most decisions are erationaloverloads. 0ultimatelymadebyhumanoperators.Wearguethatthismodel Appropriateautonomicresponsetonetworkchallengesstems 3 .sufferthreemajorlimitations.First,thereactionofhumanop- forreal-timeonsetdetectionthatactsasabackgroundtask,and 1eratorsislimited,especiallywhenproblemsmostlybecomeas triggers on-demand more sophisticated mechanisms involved 0 complexasnowadaysbotnet-drivendenialofserviceorworm inroot-causeandimpact analysis.Thistwo-phaseapproachis 2 1propagation.Second,thehierarchicalapproachallowssomelo- crucialforsavingresourcesofthenetworkoperator,asthe(rel- :cal manager to automate some “reflex” reaction based on lo- atively) computationally expensive tasks can be focused both v cal information. Any decision that requires knowledge – even intimeandintheamountoftraffictheyconsider. i Xsummarised – regarding a larger area has to be deferred to a We argue that this multi-stage processing of monitoring in- rhigherlevelinthehierarchy.Asaresult,thetopofthemonitor- formation to ultimately provide a high-level understanding of a ing hierarchy becomes a strategic target to intentional attacks: a situation is similar to the process of hand-script recognition iftakenofflineoroverloaded,defenceofthenetworkbecomes in architectural sketches [4] and could therefore benefit from severely compromised. Finally, although the causes of service a multi-agent approach, where each agent is specialised (task- degradation are numerous, the analysis of a challenging situa- centric) into one kind of challenge and can identify it with a tion is performed by a single program (e.g. an IDS) that must certain confidence level. Translating this approach to network takeintoaccountalltheirpossiblevariations. control, however, requires a distributed middleware that can InlinewiththeResilinet/R2D2+DRstrategy[2],weargue efficiently relay information and self-document its decision to that the role Internet now plays in our society and the evolu- allowhuman-drivenrevisionofthepolicies. tionofchallengingeventsstemsforageneralisedabilityforthe This paper collects the requirements for such a middleware network to self-defend by activating remediation mechanisms (section 2), propose a service model (sections 3) – the Dis- (trafficfiltering,rerouting,...)thatwillsustainserviceinade- tributed Information Store for Challenge and their Outcome – graded, but acceptable state. The need for a more resilient In- that fulfil these requirements and review the available compo- ternetsuggestsdecisionsalwaysoriginatefromalocalsystem, nents it could be built on (section 4). We further validate the possibly even defining areas of the network as Self-Managed conceptonaDDoSdetectionscenario(section5)andevaluate Cells[3].Achallenge,inthiscontext,isaneventthatimpairs thefeasibilityofusingScribe–aDHT-basedpublish/subscribe service–asthecorebuildingblock(section6). ∗ correspondingauthor. Emailaddress:[email protected](Sylvain Martin). PreprintsubmittedtoElsevier 17January2012 resilience onset identification success estimator detector engine assessor DISCO observation investigation observation investigation progress publishes report background on-demand remediation probes probes mechanism subscribes to report Fig.1.Overviewoftheprocessingchainindetectionandremediationofachallenge 2. ProblemStatement we can afford to relay on the network. Because we expect thatmultiplealgorithmswillbedeployed,eachoperatingas We base our work on the findings of [5] regarding the de- anautonomousagenttoidentifyaspecifickindofchallenge, tection of challenging situations in a network, that is, beyond we want the sensors to remain unaware of the number and onset challenge detection, which is usually achieved through identityoftheirlisteners.Moreover,therelativenetworklo- anomaly or signature-based detection, additional steps are re- cationofdetectionalgorithmsandsensorsimpactstheaccu- quiredtoclassifythechallengeandunderstanditsimpactonthe racyweneedontheinformationwereceive. network and on ongoing communications. The ultimate goal – Detection, remediation and diagnostic actions are delayed of the challenge identification process is to activate and de- from sensing activities, yet they may require detailed infor- ploy a specific remediation mechanism, providing it with all mationonpasteventsthatprecededatrigger.Therefore,the the required configuration parameters to handle the challenge required lifetime of individual events is hard to predict, but and restore the service to a degraded, but acceptable level. If it requires careful management given the potential amount weconsiderdefenceagainstDDoSattacksasanexample,on- ofgeneratedinformation. setdetectioncouldconsistoflinkandqueuesmonitoring.On- – Newcomponentswillbedeployedovertime,tobetteriden- demandidentificationinvolvesavolumeanomalydetectionthat tifyandremediateunforeseenandforeseenchallenges.They pin-pointthevictimoftheattack,andremediationmechanism will likely alter the coupling between data by introducing wouldbearatelimiterforafirewall. new relationships and attributes. While this is an essential Figure1illustratesthecommunicationchaininvolvedinde- featuretoguaranteesuccessfulevolutionofmachine-learning tection,identificationandremediationofchallengesthroughre- algorithmsbeyondtheirinitialprogramming,italsoimplies portspublishedintoDISco.Probespresentinforwardingplane that no database schema can be established in advance. Yet componentsmayvaryincomplexity,fromsingle-variablemon- thedynamicsofinformationmakesidentifier-basedsolutions itoring(e.g.numberofpendingTCPconnections)tomoreso- suchasIF-MAP[6]notapplicable“asis”. phisticated entropy-based systems. These reports are gathered Toaddresstheseproblems,theDistributedInformationStore by onset detection agents and identification engines, usually forChallengesandtheirOutcome(DISco)providesthefollow- frommultiplesources,whichinturnproduceinvestigationre- ingfeatures: portswhentheriseordecayofachallengehappens. – aaggregation-capablepublish/subscribefunctionthatrelays Notificationofchallengestriggertheactivationofmitigation informationbetweensensors,detectors,andmitigators. componentswhichwilltakeactionstoremediatethechallenge. – an annotation system, coupled with more conventional Because these decision are taken automatically and require a database-like lookups that allows detectors and mitigators responsetimethatnohumanoperatorcanoffer,itisimportant tofurtherclassifysensorsinformationandadjustitslifetime to record the progress of the challenge as a whole (triggering accordingly. conditions, evolution of the impact, side-effects) so that the – a distributed (peer-to-peer) storage system that provides fitnessoftheautomatedsolutioncanbeanalysedlatertoadjust system-widelonger-termpersistencefordatathathavebeen responsethresholdsandparameters. “electedfordiagnostic”takingintoaccounttheexistenceof Weidentifiedthreekeyproblemsthathinderthedevelopment “natural”storagespacesuchasroutingtables. and deployment of efficient detection and remediation tech- niques,andwesuggestthatacommoninformationdispatching andstoragesystemistheproperabstractiontoaddressthem: – Theremaybemanysensors,reportingmoreinformationthan 2 3. DesignPrinciples Thefollowingdesignprinciplessteeredusfromtheproblem Publishers Any Client descriptiontothearchitectureproposedinsection4. EvolvingSystem : We expect that the monitored system will Publish Look up evolve by addition of new probes and agents over time. As Subscribe a result, new type of information and new information pro- Subscribers Deliver APgugbrleisghSa yt&iso tSneu mCbaspcaribblee LPoorokxuyp Look up LSetograecsy cessorswillappearandmustintegratetheprotectednetwork Reply without requiring to reprogram, reconfigure or reboot other Store Look up components. Retention Multi-attribute, range queriable Peer-to-PeerDistributedSystem : Distributed monitoring Manager distributed database infrastructures typically follow a strongly hierarchical ap- Distributed Store proach where a device in a low level of the hierarchy DISco Core Functions receives and process an important amount of information aboutasmallareaandreportitsconclusionstothelevelim- Manage ment Overlay mediately above, up to a central device that has coarse and complete view of the network and take decisions that are Fig.2.GeneralarchitectureofDISco. forwarded and enforced down the hierarchy. We argue that, althoughofferinginterestinglocalityproperties,suchanap- sible collection of terms that are hierarchically organised proach lacks scalability by the fact it excessively decouples by a “IS-A” relationship. We would, for instance, express data-plane monitoring and enforcement from decisions that that bandwidth is a connection-related metric by plac- aredelegatedtothemanagementplane. ing it under the connection node of the vocabulary tree Advancesinstructuredpeer-to-peerhashtablesandmes- rootedatmetrics.Aswithontologies,VSTsallowtodis- saging(especiallypub/sub)systemswouldcomparativelyal- tinguishconcepts:metrics.connection.bandwidth low any number of devices to cooperate so that the control isdifferentfromresources.link.bandwidth,which plane of a device can obtain network-wide context it lacks expresshowfastrawdatacanbesentoveralink.Eachcon- tolocallyprocessfine-grainedeventsdescribingitsownbe- cept is thus a node in a tree and can be refined by adding haviour,decidetherequiredchangesandinformpeersofits childrenconceptstoit. decisiontoavoidinconsistentglobalbehaviours. KeepingManagementApart : Tasks occurring in the man- Multi-ResolutionInformation : When an agent receives an agementplanetypicallyoccuratadifferentpaceandwitha observation report, it is essential that it can gather addi- levelofabstractionthatdiffersfromcontrolanddataplanes. tional information that was not explicitly included in that Therefore,ourproposaldoesn’tincludeanymechanismfor, report. Through the coupling between the pub-sub system e.g., (human-readable) self-description of exchanged infor- and the distributed database, agents are allowed to “zoom” mation. Assignment of numerical identifiers to event and intoaneventbycollectingadditionalinformationwithspec- attributes, for instance, can be synchronised independently ified scope in time, location and layers. This is a principle withassignmentofotherdevicesatinitialisation.Numerical we share with [7], although the rest of our approach differs IDsaresuitedtorun-timeprocessing,whiletheirconnection fromthatproposal. toconceptsintheVSTallowsextensiontoaricherdatabase, Learning-ReadyDataModel :InformationrelayedbyDISco e.g., by linking reports to metrics as “challenge.X – must ultimately be useful as input to machine learning al- impairs→ metrics.Y”. This database can be stored in a gorithms, that will provide configuration parameter of the separaterelationtableavailabletohuman-assisted,orsolver- adaptiveprobesandremediationmechanism,butalsotoau- based,diagnosticandrefinementtasks. tomatetheidentificationofmeaningfulsymptomsforagiven problem among a huge amount of measurable parameters. 4. ArchitectureandMainComponents Tothatregard,wepreferredmachine-orientedrepresentation (tuples of numbers) over log entries. Alarms, reports, noti- fication are mapped to such tuples where a special member AswewantDIScotoservebothfordisseminationandstor- servesthepurposeofidentifyingthenatureoftheevent(the age of information (more specifically, events reports), it will eventidentifier)andtherestconsistsofanarbitraryamount indeed consist of a peer-to-peer publish & subscribe function, ofattributes. combined to a distributed storage to provide data persistence Identifiers for events and attributes relayed through the atshortandlonger-term.Ageneralviewofthisarchitectureis DISconeedtohaveacommonlyagreedsemanticforallcom- depictedonFigure2. ponentsinthesystem.Weproposetoreuseforthispurpose We collectively name clients the software components (or the concept of Vocabulary Specification Trees (VSTs) de- “blocks”)thatmakeuseoftheDIScoAPI,bothfordeliveryof scribed in the monitoring framework of the European ANA events or searches through the storage facility. Publisher and project[8].Vocabulariesprovideeasy-to-manageandexten- subscribers are merely roles, and it is frequent that a single componentplaybothfordifferentlevelsofevent.Everyclient 3 –detectors,identifiers,remediatorsandoff-linediagnostictool Itisimportanttounderlinethattheonlyroleofaggregation – has access to data archived in the store through the lookup istomergesimilarevents,thecombinationofwhichisanevent interface, which enables among other things on-demand reso- of the same type (attributes are altered, though). This must lution“zooming”.Thecontentofthisstorecanbeconceptually not be confused with correlation, which extracts information extended to legacy storage that could provide useful context, fromseveraleventsinordertodeduceoneofanewtype.This suchasroutingtables,asdescribedinSection4.5. correlation is not performed by the DISco itself, but in clients suchasidentificationengines. Whenspecifyingaggregation,thesystemhastobetoldhow 4.1. Publish&SubscribeSystem and how much to aggregate. Although it could be imagined to let full freedom in this specification, through, for instance, The Publish & Subscribe mechanism is used for near real- programmableaggregators,thiswouldraisehugeimplementa- timenotificationofevents,andisthustheprivilegedpathforin- tion (and even maybe security) problems. Instead, predefined formationexchangebetweendetectionandremediationagents. aggregatorswillbeselectable,dependingonthetypeofevent, Whiledetectionagentsarequitenaturallyassociatedtopublish- andfollowingthesubscribers’needs. ers, and remediation agents to subscribers, it is also expected Consideringthegranularitylevel,twokindsofspecification thatseveralidentificationengineswillbeusingtheinformation can be provided. On one hand, the event rate has to be con- extracted from various sources they subscribed to, in order to trolledstrictly,andtheaggregatordeliversaperiodicsummary, publishsomehigher-levelevents. containing more or less base events, depending on the num- Besidethesetwoactions(publish,subscribe),DIScowillbe ber of generated events during the interval considered. On the providingareplymechanism,thatcanbeusedtoannotatethe other hand, we may require that a single aggregated event al- data. A subscriber can then tell the notifier that the published ways contain the same number of base events. In this case, summary of some data is of importance and that the detailed trafficwillnotbeuniformovertime,allowingtobettercapture data should be kept for a longer duration. The annotation tags criticalsituations. canprovidelinkbetweenlow-levelandhigh-level(correlated) events, trigger the storage of these related events in the dis- 4.3. DistributedStorageSystem tributed store, and might also guide the auto-configuration of aggregators. The published events are kept in a distributed store across participatingnodesforfurtheranalysis.Thisincludesbothde- tection algorithms requesting recent events (short-term stor- 4.2. FilteringandAggregation age),anddelayedprocessesrunningdiagnosisonalargerscale (long-termstorage). DIScoisintendedtobedeployedinlargesystems,withpos- Manydistributedstoresarebasedondistributedhash-tables siblyhugevolumeofinformationtoprocess.Whilethereisno (DHT),basicallyusingahashofanelementidentifiertodeter- a priori limitations to the amount of published data and gran- minethenodeonwhichithastobestored.Whilethisapproach ularity of events, a practical solution has to keep bandwidth is used by many peer-to-peer systems which need to search and storage usage as low as possible. This leads to two possi- singleelementsbasedontheiridentifiers,DIScoisrequiredto blesolutions:eitherpublishersareresponsibleforlimitingthe handle more evolved lookups, supporting range-based queries amount of events they generate, or the subscribers specify to onseveralattributes(suchasIPrange,timeintervals,thresholds thesystemthegranularityleveltheyareinterestedin.However, onvalues,andsoon),whileconsideringothersaswild-cards. only the second approach will succeed in efficiently reducing Other structures have been developed to handle this kind of the data volume without losing essential information, mainly queries, but we identified only two of them being of interest fortworeasons.First,publishershaveno(oronlyfew)knowl- and supporting multi-attribute range queries: Mercury [9] and edgeofthelevelofinterestintheirpublications,possiblylead- SkipTree[10].Thelatterhasbeenselectedforimplementation ingthemtolargelyunder-(orover-)estimatetheoptimalgran- anduseinDISco,sinceithastwomajoradvantagesoverMer- ularity.Second,subscriberswillbeabletodynamicallyrecon- cury:localitypropertiesandlowerspaceusage. figure(e.g.,throughanewsubscription)thedesiredgranularity inordertotellpublisherstobemoreverbosewhentheydetect suspiciousevents.Thisallowstomaintainrelativelylowman- 4.4. InformationRetention agement overhead during normal operations, while gathering more precise data during challenges, enabling better detection Ideally, element removal will be something that is handled and/ordiagnosis. in an autonomous way by DISco itself through the Retention When subscribing to a particular event, the subscriber can Manager.Itwilluseinformationsuchasnumberofsubscribers, specify limitations to the amount of published notifications pastlookups,andannotationsashintsthataspecificdataentry through needs to be “promoted” to a longer storage (typically, for the – Filters,discardingnonrelevanteventsand/orattributes,and diagnosis phase). Static and manual configuration should be – Aggregators, gathering several events to produce a single, used only to define defaults and characterise retention length coarser-grainednotification. dependingonthehintsmentionedabove. 4 4.5. HeterogeneousStorage WhileDIScoprovides,fromalogicalpointofview,asingle store (even if physically distributed) for all published events, wesuggesttoorganisestoragefacilitiesinthreedistinctclasses. Local Temporary Storage (LTS) is co-located with sensors andstoresforashortamountoftimeacopyofeverypublished event, regardless of its potential value and the existence of subscribers.ThepersistenceofLTSisusuallylimitedtoasmall Fig.3.NetworkunderDDoSchallenge,Lbeingistheoverloadedbottleneck multipleofedge-to-edgedomainlatencyasitissolelyintended link,R−T −V thepathtothevictimthroughthenetwork togivesubscribertheopportunitytoreplytoanevent. Distributed Working Storage (DWS) is the main storage fa- afewhopsafterL1 inordertofurtherevadedetectionbysys- cility, based on SkipTree (or a similar alternative), that holds tems in V’s network. This, however, makes their traffic look and organises pertinent published information from onset de- singularinthenetworkcontainingL. tectiontooff-linediagnostic. Routers in this example monitor the amount of IP pack- Finally,LegacyStorage(LS)consistsofpre-existing,“natu- ets that are rejected by the forwarding process, including ral”storesofinformation(suchasBGProutingtables)thatare those who have their time to live exhausted. They report madeaccessiblethroughanadditionaltranslationdaemonrun- this through event.network.drops.forwarding.- ningontheirhost.Thecontentofthoselegacystorescouldin- rfc791-ttl-exceeded which contains (as attributes) deedbeavaluablesourceofcontextformanyalgorithms,and flowidentification(madeofsource/destinationaddresses,ports wecouldbenefitonhavingaunifiedwaytoreachthem.Instead and transport protocol, in the case of IPv4), location of the ofduplicatinglegacyinformationdirectlyintheDWS,onlylo- reporting router and timestamp of occurrence. These events cationhintswouldbekept,relyingonthelookupproxytofol- are published by V and U in the distributed store. Similarly, low indirections transparently. This daemon-indirection-proxy an important amount of “queue full” events occurring at R chainofcomponentsshouldbesufficientforfurtherextension willtriggertheexecutionofDoS-detectionalgorithmslocalto needs.ContextpresentintheLScanbeselectivelytransferred R such as identifying destinations of largest flows. A further totheDWSwithareplyonthelookupresultinordertocapture analysisprocessAthatwasdormantinasystemclosetoRpre- relevantdataforlaterdiagnostic. viously subscribed to “any heavy-flow report event” from R, andpossiblyotherroutersinthesamepointofpresence(PoP). 4.6. ConnectivityLayer Upon reception of heavy flows reports from R, A will ad- ditionally subscribe to events reporting network-related errors downstreamfromR,enablingcollectionofreportsfromT,V Forproperoperation,DISconeedsaresilientcommunication andU.WeassumeherethatAisan“expert”softwareagentthat infrastructurethatcanbeprovisionedwithlimited,butguaran- looksforandidentifiesthespecifickindofDDoSattackwede- teed bandwidth (i.e., defended against volume-based attacks), scribed above. The publish/subscribe mechanism fully allows andpossiblyusingsecurechannels(i.e.,encryptedcommunica- multiple similar systems to execute concurrently and perform tionsandknownpartners).ItsgoalistodecoupleDISco-related theirownanalysisusingthesameinitialevents. traffic(i.e.,managementtraffic)fromthemonitoredtraffic.We The following features of DISco are highlighted in this ex- also assume that it provides peers authentication and integrity ample: of the DISco-internal traffic so that neither forgery nor falsifi- Localholdingofdata: informationaboutpacketsdroppedat cationofreportscouldoccur.Achievingthislevelofresilience V and U are put under the control of DISco, but not yet is beyond the scope of this paper. We will simply assume that transferred to a remote system until interest in such infor- appropriate“detourtunnels”exists,thatpreventscommonchal- mation is expressed through a subscribe call. Yet, it is lengesfromimpairingconnectivityofDISconodes. important that such data can be looked up a posteriori, for instancewhenprocessAtriesandgathersrecentpaststatis- 5. ConceptValidation:DDoSDetection tics to figure out the dynamics of the challenge. Temporal aggregationcanstillbeappliedtoreducetheavailablegran- 5.1. Network-NetworkInteraction ularityofinformationovertime. Selectivesubscription: whileAneedsextrainformationfrom T, U and V, it is only interested in information related to To illustrate the way DISco works, let us use the following a fraction of the traffic those routers forward. For instance, denialofserviceattemptonthenetworkdepictedinFig.3.At- if it identified 4.2.0.0/16 to be the destination of heavy tackerstargetlinkLthatisrequiredtoreachavictimattached hitters, we will add a constraint on attributes stating that to V. They additionally identified that traffic towards destina- tionsattachedtoU alsousesthislinkand,thus,usesaddresses Ui as well to dilute the signature of their attack. We also as- 1 by means of their Time To Live field or any similar hop count limiting sumethatattackersdecidedtohavetheirattacktrafficdropped technique 5 attribute.flow.rfc791-destination-address between“challengedetected”and“endofchallengedetected”. mustmatchthatrange. Thecorrelationbetweentheexpectedstate(notchallenged,de- Compoundvalues: note that while A describes filtering on tection in progress, remediation applied, ...) with the number “destination address”, V and U put flow identification to- of“overload”reportsisusedtoassertthesuitabilityofthede- gether in a compound value. The schema of this compound tectionprocess. needstobeknownbyDIScopeerssothatfiltering/aggrega- tion components are able to extract and compare the desti- nationaddresses. 6. Aggregation-CapablePub/SuboverScribe Aggregatingeventsfrommultiplesources: A typically makes no difference between reports coming from U and This section focuses on the choices we made to implement V as long as they match the filter. This highlights the need the aggregation-capable pub/sub system required by DISco. for describing a region of the network through an attribute Theideawastorelyonthealready-availableimplementationof constraint. Scribe [12] for the OMNET++ simulator2, included in Over- Flexibility: A could broaden its monitoring criterion by sub- sim3 [13].Wethenneededtoadaptitsmechanismsinorderto scribingtoevent.network.drops*,andreceivenotifi- integrateaggregationandfilteringinitsmessagedeliverypro- cationofpacketlossesinthenetworkregardlessofwhether cess. However, as explained with more details in Section 6.5, they are due to TTL issues, congestion (queue full or early the mechanisms used by Scribe (and, to an extent, Key-based notifications), broken link, unknown destination, etc. This routing systems using DHTs) to deliver messages do not sup- relieves A from knowing the actual network protocol stack port the full range of features we require for our aggregation- details (as a ICMP snooping agent would have to) and al- capablesystem. lows monitoring of events originated by different layers as As described in the following text, Scribe proved to be a needed. non-optimalchoiceforourpurpose,thesamewayDHTwasn’t ideal for the store itself. In parallel to the development of an alternative based on SkipTree, we decided to pursue the im- 5.2. Network-ServerInteraction plementation of aggregation/filtering features over Scribe as a referencepoint. Wethenconsideramore“classical”DDoSattack,wherethe victim server S is really receiving application-level requests through transport-level connections. S locally observes those 6.1. AddingAggregationtoScribe request patterns and their effect on system resources such as CPU and memory load, or access to internal databases. Devi- Scribe uses Pastry [14], a DHT system capable of routing ation from sustainable behaviours are reported as events de- messages to the node whose numeric ID is the closest to the riving from event.server.overload.* and include at messagekey.Usingthisproperty,eachtopicofthepublish/sub- leastflowidentificationofthe“faulty”connection. scribesystemwillbehashedtoobtainatopicID,andthenode When the agent A coaching a router like R observes ab- with the closest node ID will act as a rendez-vous point. Dur- normal traffic share towards S’s prefix, it may subscribe to ing the subscription process, the message from the subscriber “serveroverload”eventstohelpdecidingwhetherthecurrently willberoutedtotherendez-vouspoint.Eachnodeonthepath observed challenge is a DDoS attempt. This, assuming that a will subscribe to that topic and become a forwarder, until the DDoS is more likely to use resource-intensive requests while, messagereachesanodebeingalreadyaforwarderforthattopic during a flash crowd, time and resources needed to serve the (ortherendez-vouspointultimately).Thisendsupwithamul- requests do not deviate from normal behaviour and only the ticast tree rooted at the rendez-vous point. Other mechanisms amountofrequestsperunitoftimegetswild. are used to maintain only active nodes in the tree (refresh), or Similarly,resilienceagentco-hostedwithSwouldsubscribe even to change the root node in case of failure, but these will to “challenge detection reports” and “remediation action re- notbedescribedhere. ports”producedbynetworksdeliveringtraffictoS.Ifneeded, Forouraggregation-capablesystem,eachsubscription the DISco peers that receive this subscription can ensure that specifies aggregators in addition to the topic ID. The mes- theagentonlysubscribetoinformationitisentitledtoreceive sageisthenroutedtowardstherendez-vouspointasintheclas- (thatis,checkthepresenceofanIP-destinationfilter). sical Scribe implementation. When a forwarding node in the Thisapproachisespeciallyattractiveincontentdeliverynet- multicast tree has children with different aggregation require- works(CDNs)[11],whereasingleeconomicentityownsboth ments, its own subscription is aligned onto the finest-grained the access network/routers and server farms. It can still be of one.Thenecessaryadditionalaggregationisperformedonsub- high interest as a way to train learning-capable detectors. In sequentpublicationstoservechildrenwithcoarser-grainedre- thatalternative,detectionandremediationalgorithmsdonotdi- quirements. rectlyuse“serveroverload”events,butinsteaduseinformation comingfrommultiplesymptomstoidentifysymptomscombi- nation that reveal a DDoS challenge. In a refinement step, di- 2 http://www.omnetpp.org/ agnosticagentslookupforoverloadeventsinthetimeinterval 3 http://www.oversim.org/ 6 6.2. DataModel,TemplatesandDiscardedAttributes Since DISco is designed to be used by many devices and networkcomponents,itisessentialtobeabletomakeitevolve dynamically by adding new events and/or attributes progres- sively and smoothly. Moreover, since the vocabulary may be huge and not known by every DISco client, we need a mech- anism that guarantees easy and consistent data formatting be- tweenclients.Forthispurpose,DIScousesanapproachsimilar toIPFIX(IPFlowInformationExport [15]). The format of the published events is described in specific Templatemessages.ThesecontainanID(uniquetotheissuer) andtheformatdescription(attributeIDsandtypes)ofthefol- lowingevents.Consequently,eachpublishedeventwillcontain the ID of the corresponding template. It is worth noting that, duetoaggregationanddiscardingofattributes,thetemplateis likelytobedifferentfromnodetonodeinthemulticasttree. When a subscriber receives a template for a particular sub- scription,itwillbeabletoreadalltheattributesoftheevents, Fig.4.ActivitydiagramofeventaggregationanddeliverybyaDISconode. butmaynotbeinterestedinallofthem.Inordertoreduceband- width usage, DISco allows a subscriber to explicitly discard a toatopicwithnosubscriberswillbereportedbytherootnode listofattributes,preventingthemfrombeingsentsubsequently. through a specific notification. This allows sources to regulate their publishing rate when there is no interest in their events. 6.3. GenericAggregators A list of early publishers is kept in order to notify them when subscribersareready. After this initial step, the event is filtered and aggregated Basedonthesubscriptiondetails,nodesinthemulticasttree following the specification of subscribers. The state of filters will have to aggregate events and thus need functions to com- and aggregators for each direct children in the multicast tree bine them. As already mentioned in Section 4.2, DISco does has to be maintained separately (since they may have diverse not provide fully programmable aggregation but instead, lets requirements). thesubscriberselecttheaggregatoramongstpredefinedones. Since the level of aggregation can be specified through a The aggregation is applied on attributes individually. Each maximum number of aggregated events and through a maxi- attributereceivesanidentifierthroughthevocabulary.Subscrip- mum period length, several situations have to be dealt with. tion defines the operation type to be applied, while event con- The new event may be added to a pending aggregate, if any, tentdefinestheattributetype(thisinformationisextractedfrom or a new aggregate will be created. In the first case, we want the template, preventing routers to cache knowledge of every tocheckifthemaximumnumberofeventsisachievedand,in attributeID→attributetyperelation).ItisrequiredthatDISco suchacase,forwardtheaggregate.Inthesecondcase,weneed has an aggregation function for each possible < operator > to ensure that the maximum period is not already exceeded x < attrtype > pair. Core operators and attribute types are (meaning that the aggregate will be forwarded with only one available, but new ones may be added to the system later on, eventaggregated).Afterthecreationofthenewaggregate,we providedappropriateaggregationfunctionaredeployedtoo. alsoneedtostartatimerthatwilltriggertheforwardingatthe endofthemaximumperiod. 6.4. BasicNodeOperations A local circular buffer is used for short-term storage of for- warded events. This buffer is used in case of replies to match Severaloperationshavetobeaccomplishedbyeachnodein the source events and further process them. The pending ag- the multicast tree in order to perform aggregation. Moreover, gregateisthendiscardedandanyassociatedtimercancelled. somestateisrequiredtomaintainthelistofchildrennodes,as- sociatedwiththeirfilteringandaggregationspecification.This state is built up or updated as nodes subscribe to a particular 6.5. ScribeInadequacy topic. A published event goes through the chain of operations illustratedonFigure4. 6.5.1. Multicastinpresenceofsinglepublishers. A DISco node maintains a list of each multicast group it When a specific topic is filled by only one publisher, the belongs to, either being a subscriber (leaf node) or an internal multicasttreeshouldberootedatthepublishingnodetoavoid nodeofthemulticasttree.Whenitreceivesanevent,thenode unnecessary traffic between the publishing node and the root must first of all find at which multicast group it is aimed. If of the multicast tree. But, since the rendez-vous point is cho- no group is found, then the event was published before any senfollowingthetopicID(ahashvalue),alltherootnodesare subscription. It is worth noting that, unlike Scribe, publishing pseudo-randomly distributed over all the nodes in the overlay. 7 This is indeed a key point for load balancing in generic ap- As we raise towards the application-layer challenge detec- plications using Scribe. But, in our case, topics with only one tion and remediation, however, there is an increased need for publisherwilltypicallycorrespondtoprecise,low-levelevents, inter-domaininformationexchanges.Decisionsinautonomous whosesubscribersarereasonablysomelocalmanagerslocated domain A may then be depending on (or influenced by) re- quite near the publisher. Having to forward every single event ports generated by probes in other autonomous domains. The throughapossiblydistantrendez-vouspointwouldclearlyin- major point to address is then to ensure that integrating those crease the amount of traffic and impact on the minimal level reports in our detection mechanism does not open the door to of aggregation required to limit the overhead of management newattacks. traffic. Additionally, DISco relies on a shared vocabulary between running components, but doesn’t require the vocabulary to be commonamongeveryautonomoussystem.Inter-domainoper- 6.5.2. Topicaggregationthroughvocabulary. ationthusrequiresthateithersessionsfirstnegotiateavocabu- Itisexpectedtohaveremediationagentssubscribingbothto larymapping,orthateveryexchangedmessageusesthetextual specific events (e.g., report.intrusion.protocol-- representation of event and attribute identifiers, with implied exploits.rfc792.cve-1999-128),becausetheyknow overhead. what they can remediate exactly, but admittedly a generic manager should be able to subscribe more largely (e.g., report.intrusion.*). Also, a remediation agent might 7.1. Import/Export wanttobeabitlessspecificandsubscribeto.protocol-- exploits.rfc792.*. The DISco service model allows A conservative approach consists of programming explicit this to be addressed through the vocabulary, that is, ensure importers and exporters at the border of a DISco domain. An that all items under report.intrusion.* will be given exporter subscribes to reports of its own domain, applies ad- IDs that match a common prefix, e.g. CA:FE/16, while ditional filtering and aggregation as defined by domain man- alarm.failure.* would be DE:AD/16, much like IP agers’confidentialitypoliciesandrelaysresultingmessagesto addressesblocks. theimporterofaremotedomainoverasecurechannel.Theim- Unfortunately,whenusingDHT-basedroutingfortopics,the porterinitiallygatherinformationaboutexporters’capabilities topichierarchyiscompletelylostduringthehashingoperation, (such as IP ranges they report about) and informs the pub-sub and topics can no longer be grouped. To work this limitation system that it can potentially publish reports for the identified around, we use in our simulations an “oracle” to determine ranges. It also perform sanity filtering on received reports to whichtopicsneedstobeaggregated.Publishersandsubscribers avoid source spoofing of DISco message (i.e. it has to ensure obtainthetopicIDthroughthisoracleinsteadofdirectlyhash- thatmessagecomingfromdomainDactuallygiveinformation ingthetopicname.Asinglemulticasttreewillthusbebuiltfor aboutdomainD). severalrelatedtopics,andinternalnodeswillberesponsiblefor This import/export mechanism is well-suited when trust re- filteringouttheeventstobeforwardeddownwardinthetree. lationshipsexistamongdomains,suchasimportingprovider’s reportsintoclient’sdomain,orexchangingreportsbetweenar- bitrary,peer-trustingdomains(suchasuniversitiescampuses). 6.5.3. Geographicalaggregation. Athirdwayofperformingaggregationistoaggregatemul- tiple sources based, typically, on their IP range. It would also 7.2. RemoteEnquiries be interesting to be able to aggregate events along a specified path, or in the vicinity of a particular device (both "path" and Thenumberofimport/exportchannelsthataDIScodomain "vicinity"havingtobedefined).Asforthepreviousdrawback, can maintain is necessarily limited, and since trust is not nec- thereisnoclearwayofimplementingthesefunctionalitywhen essarilytransitive,itmakeslittlesensetoprovidemechanisms usingkey-basedroutingonaDHT,whichpurposelydistribute to relay reports of domain P to domain S through domain D. similarkeysinapseudo-randommanner. However, when an analyser in domain S investigates suspi- cioustraffic,informationaboutthedestinationdomainaremore likelytobeusefulthanknowingoddshappeninginthesecond 7. ExtendingOperationtoMulti-domainDetection orthirdrelayerdownstreamS. An option to achieve this is to encapsulate lookup requests Initially, DISco is designed to federate information of mul- forremoteinformationandtorelaythemtoaDISco-compatible tiple sources of event and made it available to entities that system responsible of the intended domain. This mode of op- supervise network operation with both time and space multi- eration is heavily inspired and can be supported by the “pull resolution.Althoughitcanbeappliedatdifferentscales(from mode” of i4 [16], an information-exchange proposal between campusnetworktoe.g.theGéantresearchnetworkoroverlays), intrusiondetectionsystems.Sharedkeystoestablishthesecure it assumes that all participants (probes, analysers, mitigators, connectionforthelookuprequestaregeneratediterativelyand resilience managers, ...) share a common interest for network piggy-backedonBGPprefixadvertisement4. resilience (and in most cases, a common administration), and thattheycanestablishsecurecommunicationwitheachother. 4 ThemajoradvantageofBGP-basedkeydistributionisthatkeygeneration 8 Again,thesupportforremoteenquiriescanbetransparently ysers subscribe to such events in addition to reports generated addedtoaDIScosystemthroughtheuseofindirectstoresand byin-networkprobes,especiallygiventhatX-Trace-augmented LOOKUPcommands:abordersystemwithintheASwillscan packetscarryatokenthatuniquelyidentifiestheuser-level“ac- BGP exchanges and install lookup indirections in the DISco tivity”thatisunderinvestigationbytheend-system.Whenac- storecapturingthecorrespondingIPaddresses,thereforeplay- cessing a webmail, for instance, that very same token will ap- ing the role of a DISco proxy. When a lookup request hits pearinDNSrequests,TCPconnectionestablishments,andide- theproxy,ituses internallystoredcorrespondencebetweenIP ally, even internal web-to-IMAP requests5, providing precise blocks,ASpathtowardsthatblockandthecorrespondingcom- correlationhints. municationkey. However, in the absence of an additional authentication of Becausethereisnoimpliedtrustinthismodel–onlyauthen- the emitter of the token and trust relationships between the ticated connection – lookups should only enquiry about sub- emitter and the network resilience manager of a specific AS, jects for which D can establish that motivation of the request it would be easy for a malevolent end-user to forge tokens in isvalid.Flowsoriginatingfromorcarriedbytherequester,for ordertomisguidetheresiliencemechanismofavictimnetwork. example, are good candidate subject, as the target system can Members of a DDoS botnet, for instance, could collectively easily verify involvement of the requester. Issuing generic re- usethesametoken,forcingthedefencesystemtobelievethat quests about the load of routers or servers within the domain, somethingcausedanunusualrateofretransmissions.Similarly, however,wouldbedenied. anintrudercouldintroduceartificiallydifferenttokenstoevade anydetectionbasedontokencorrelation. 7.3. ActivityTracing 8. IntegrationwithExistingToolsandProtocols With increasingly complex network technologies and ever rising use of near-real-time multimedia over best effort net- 8.1. CorrelationEngines works,evenend-to-endcontrolloopsmayneedaclearerreport ofwhathappenswithinthenetworktooptimisetheirbehaviour Correlatingeventstodrawconclusionsisakeyfeatureofthe andimproveserviceavailabilityfortheend-user. challenge detection process. We have specifically investigated Two recent proposals, X-Trace [17] and NetReplay [18] the possibilities offered by ISS and Chronicles, two engines investigate the opportunities of collecting network-generated developedbyprojectspartnersandnowpresenthowtheycanbe monitoring at inter-domain scale and exploiting it to fine-tune integratedwithDISco.Moretechniquescertainlyexist,anditis the behaviour of end-to-end protocols, providing integration notintendedtobeexhaustivehere,asdifferentchallengemight between service-level and network-level resilience. Similarly, suitdifferentcorrelationmechanisms.Thisspeaksinfavourof as suggested in the Knowledge Plane [19], suspicions of fail- havingcorrelationtaskskeptoutofDIScoandimplementedas ure from end-systems can be incentive for the network-level partoftheDISco“clients”. resilience system to further investigate the current behaviour. Information Sensing and Sharing framework (ISS [20]) has We will focus on X-Trace in the remaining, as NetReplay is beendevelopedatLancasteraspartofthefunctionalcomposi- a problem-specific solution and that the knowledge plane is tionframeworkoftheANAproject6.Whileitwouldn’treally merelyaconceptualproposalsofar. beusedinsideDISco,itisagoodwaytobuildcorrelatorsand UponreceptionofapacketcarryinganX-Tracemarker,pro- moresophisticatedsensorsonnodes.DISco’spublishandsub- tocolentitiescapturerelevantpartoftheirstateandgeneratea scribesystemnaturallyextendsthepoint-to-pointdatadelivery reportthatishandledtoaper-domaincollector andwilleven- thatisalreadypresentinISS. tually be logged in a report server using the identity is men- Chronicles recognition is a mechanism for temporal events tionedintheX-Tracepayload.Thismechanismisgenericand correlationthathasbeensuccessfullyappliedtonetworkintru- primarily aimed at debugging by human experts. Yet, we can sion detection at Orange Labs [21]. It features its own inter- extenditintoacross-layerandcross-domainquerymechanism connectionmechanismstobuildhierarchicallyorganiseddistri- byhavingDIScolookupsperformedattheprotocolentityand butionofdetectionandefforts,whichagaincouldbenefitfrom atthecollector.Themajorlimitingfactoristhelackofashared DISco’speer-to-peernaturetoimprovescalabilityanddepend- vocabularybetweentherequesterandthereplyingsystemhere, ability. Its strong dependency on time-related aspects puts an andtheoverheadduetosystematicexportpolicychecks. interestingconstraintonhowDIScocouldperformaggregation Itcouldalsobetemptingtoimporte.g.thepresenceofanX- andfiltering. TracemarkerinapacketintoDIScoandhavesomeoftheanal- effort is limited and, compared to public key infrastructures, do not require 8.2. StandardNetworkMonitoringProtocols a central certification authority. A domain X that receives key KD for a given destination AS D builds a derived key KDY = hash(KD,Y) for Out of the existing network monitoring protocols, we have every neighbour AS Y it forwards the prefix advertisement. It should be specifically investigated NetFlow, SNMP and syslog for inter- notedthatotherBGPsystemsbetweentheenquirerandtheenquiredsystems can impersonate the enquirer. This approach is thus better suited to ISP-to- remote-clientenquiriesthantosupporte.g.membersofanoverlayorpartners 5 providedthatend-systemsandproxiesareX-Trace-enabled ofagridcomputing. 6 http://www.ana-project.org/ 9 operability with DISco. Both serve different purposes and are meet constraints of real-time challenge detection – is still to widelydeployedinexistingproducts.Theytypicallyfitasensor be demonstrated. Our hope in that regards is that the addi- componentofFig.2,but,aswithexternaldatastoresdiscussed tional path stretch caused by our peer-to-peer approach will inSection4.5,theyneedanadditionaltranslationfunctionthat becompensatedbylighterprocessingloadonaggregatingand convertstheirreportsintoDIScoeventreports. analysingsystems(asopposedtoastrictlyhierarchicalsetup). Thistranslationtypicallyincludestheidentificationofevent labelaswellasattributesextractionandconversionbymatch- 10. Acknowledgements ingtheexternalnotificationagainstknownpatterns.Inthecase of NetFlow, the mapping can be pretty straightforward, espe- This work has been partially funded by EU project Re- ciallythankstotheavailabilityofcompoundvaluessupportin sumeNet,FP7-224619.SylvainMartinacknowledgesthefinan- DISco.Ontheotherhand,syslogentrieswouldrequireadeep cialsupportoftheBelgianNationalFundofScientificResearch knowledge of the applications that generated them to proceed (FRS-FNRS). withmatchingandextraction,and,toalargeextent,itwouldbe preferabletoaltertheapplicationssothattheynativelysupport DISco pub/sub interfaces and have an external exporter trans- References lating DISco events into human-readable syslog events rather thantheotherwayround. [1] D.Durham,“RFC2748thecommonopenpolicyserviceprotocol,”Jan Finally, the SNMP protocol provides much more than the 2000.[Online].Available:http://tools.ietf.org/html/rfc2748 functionality we propose in DISco, and its trap mechanism [2] J. P. Sterbenz, D. Hutchison, E. K. Çetinkaya, A. Jabbar, J. P. Rohrer, (usedtoreportnotificationsasynchronously)isthemostinter- M.Schöller,andP.Smith,“Resilienceandsurvivabilityincommunication esting feature for our real-time approach. It should be noted, networks: Strategies, principles, and survey of disciplines,” Computer however,thatdespiteanSNMPtrapislinkedtoanobjectwhich Networks, vol. 54, no. 8, pp. 1245 – 1265, 2010, <ce:title>Resilient valuecanbelaterlookedup,SNMPdaemonstypicallydonot and Survivable networks</ce:title>. [Online]. Available: http://www. sciencedirect.com/science/article/pii/S1389128610000824 keeptrackofindividualdataevolution,anditwouldn’tbepos- [3] A. Schaeffer-Filho, P. Smith, A. Mauthe, D. Hutchison, Y. Yu, and sibletolookintomoredetailsatareportedsituationunlessthe M.Fry,“Aframeworkforthedesignandevaluationofnetworkresilience aggregation happened after the translation step. Again, thus, management,”in13thIEEE/IFIPNetworkOperationsandManagement publishingtranslatedSNMPtrapsintoDIScoshouldbeseenas Symposium(NOMS2012),April2012. acheap,transitionalalternativetothenativesupportofDISco [4] J.R.,leclercqP.,andA.S.,“Amulti-agentsystemfortheinterpretationof architecturalsketches,”SpecialIssueofComputersandGraphicsJournal, inthenetworkstack. vol.29,no.5,2006. [5] M. Fry, M. Fischer, M. Karaliopoulos, P. Smith, and D. Hutchison, “Challenge identification for network resilience,” in Next Generation 9. ConclusionandFutureWorks Internet(NGI),20106thEURO-NFConf.,June2010,pp.1–8. [6] “Trusted Computing Group (TNC) IF-MAP binding for SOAP specification version 1.1,” In this paper, we have presented the design of an integrated http://www.trustedcomputinggroup.org/files/resource_files/51F74E9B- event dissemination and storage system that meets the need 1D09-3519-AD2DAE1472A3A846/TNC_IFMAP_v1_1_r5.pdf, May of challenge detection system both in terms of real-time and 2009. bandwidth-limited notification and context lookups with vari- [7] Y.Xiao,“Flow-netmethodologyforaccountabilityinwirelessnetworks,” able granularity. The use of dynamic aggregation and filtering IEEENetwork,vol.23,no.5,pp.30–37,September/October2009. [8] V. Goebel, B. Gueye, T. Hossmann, G. Leduc, S. Martin, C. Mertz, as events are forwarded is a fundamental feature of our solu- E. Munthe-Kaas, T. Plagemann, M. Siekkinen, and D. Witaszek, tion,forwhichweproposeanOMNet++implementationbased “Integratedmonitoringsupportinana(v1),”SixthFrameworkProgramme ontheOverSimpackage. -SituatedandAutonomicCommunications(SAC),Tech.Rep.FP6-IST- We conceptually illustrated the use of DISco abstractions 27489,D.3.7v1,February2009. (pub/sub,vocabulariesandaggregation)onthescenarioofiden- [9] A. R. Bharambe, M. Agrawal, and S. Seshan, “Mercury: supporting scalable multi-attribute range queries,” in Proc. ACM SIGCOMM’ 04, tifying and tackling DDoS attacks and proposed guidelines to 2004,pp.353–366. interconnectthedistributedstoreofanautonomoussystemwith [10]S. Alaei, M. Ghodsi, and M. Toossi, “Skiptree: A new scalable external publishers and subscribers in order to assist service- distributed data structure on multidimensional data supporting range- levelresiliencemanagers. queries,”Comput.Commun.,vol.33,no.1,pp.73–82,2010. The adaptive storage that we coupled with notification for- [11]R.Krishnan,H.V.Madhyastha,S.Srinivasan,S.Jain,A.Krishnamurthy, warding is intended to provide the necessary information for T. E. Anderson, and J. Gao, “Moving beyond end-to-end path information to optimize cdn performance.” in Internet Measurement challengediagnosticandremediationrefinement.Themostin- Conference,A.FeldmannandL.Mathy,Eds. ACM,2009,pp.190–201. terestingresearchquestioninthatregardsincludethestrategies [Online]. Available: http://dblp.uni-trier.de/db/conf/imc/imc2009.html# used by the retention manager to adjust information lifetime, KrishnanMSJKAG09 the ranking of remediation strategies and the identification a- [12]A. Rowstron, A.-M. Kermarrec, M. Castro, and P. Druschel, “Scribe: posterioriofcontextinformationthatshouldguidetheselection Thedesignofalarge-scaleeventnotificationinfrastructure,”Networked Group Communication, pp. 30–43, 2001. [Online]. Available: http: ofweightsforremediationmechanismactivation. //dx.doi.org/10.1007/3-540-45546-9_3 Despite its desirable features, the performance of DISco – [13]I. Baumgart, B. Heep, and S. Krause, “OverSim: A Flexible Overlay and especially the ability of the event delivery subsystem to Network Simulation Framework,” in Proceedings of 10th IEEE Global 10