WIXLIB

Switchs1PacketManagerDevice Event ListenerHostProviderPacket ProcessorHost h1(v1)MAC h 1IP nullaclHost Event ListenerPacket In p2Packet ProcessorHost h1(v2)MAC h 1IP 10.0.0.1Agencyp1MAC src h 1 , MAC dst h 2IP src 10.0.0.1switch:port s2 :1fwdPacket ProcessorPacket Out p3MAC src h 1 , MAC dst h 2IP src 10.0.0.1switch:port s1 :2s1 :port 1f1Flow Rule f2match all trafficaction send to controllerswitch s2Packet In p4MAC src h 1 , MAC dst h 2IP src 10.0.0.1switch:port s1 :1HostProviderPMPacketManagerFlow Rule f1MAC src h 1 , MAC dst h 2IP src 255.255.255.255switch:port s1 :1s2Device Event Listenermatch all trafficaction send to controllerswitch s1Packet In p1s1Switchs2Agencyp2HPfwdPMp3f2fwdPacket Processorh1(v1)Flow Rule f3match {MAC src h 1 , MAC dst h 2IP src 10.0.0.1}action s2 :2switch s2aclHost Event ListenerFlow rule installedfrom h1 to h2HPIdentiferEvolutionacls2 :port 1Data PlaneModelAgencyh1(v2)p4aclfwdNo action takenNo action taken(IP not matched) (Event type not handled)f3(a) Relevant provenance for the CVE-2018-12691 attack based on techniques from F OREN G UARD [55]. The activities from switches s1 and s2 appear to be independent of each other,masking the derivation of a root cause of s2 ’s flow rule f3 from host h1 ’s activities on switchs1 .(b) Relevant provenance generated by P I CO SDN for the same scenario as (a). Thisincludes a data plane model, network identifiers, and precise responsibility (agency).Figure 2: Provenance of the CVE-2018-12691 attack. Ellipses represent SDN control plane objects, rectangles represent SDNprocesses, and pentagons represent the SDN components responsible for each process or object (i.e., the agency). The text of thelabels in (b) are abbreviations from the text of the labels found in (a).from h1 to h2 based on its IP address. The malicious host h1emits into the data plane a spoofed ICMP packet, p1 , with aninvalid IP address. The controller creates a data structure, thehost representation object, for h1 with a valid MAC addressbut no IP address. The data plane access control application,acl, checks to see if it needs to insert new flow rules based onthe data plane access control policy. As the controller doesnot associate h1 with an IP address, no flow rules are installed.Some time later, h1 sends to h2 a packet, p2 , with a validsource IP address. ONOS updates the host object for h1 withh1 ’s actual IP address. Unfortunately, at this point, a bugstops the data plane access control application from handlingevents in which a host object is updated. Thus, the updatenever triggers the application to install flow deny rules thatprevent h1 from sending traffic to h2 . The result is that thereactive forwarding application forwards the packet out (p3 ).Environment In a typical enterprise environment, a varietyof system- and network-layer monitoring tools are usuallydeployed [1,17,23,45]). These services are largely reactive innature, triggering threat alerts when a suspicious event occurs.After an alert is raised, it is then the responsibility of a networkpractitioner or security analyst to manually investigate thealert, determine its veracity, and determine an appropriateincident reponse. Threat investigation routines are carried outthrough the use of a variety of log analysis software, oftenreferred to as Security Indicator & Event Management (SIEM)systems, (e.g., Splunk). Timely investigation of these alertsis critical, as failing to respond promptly can increase theattackers’ dwell time and, therefore, the damage inflicted.USENIX AssociationInvestigation Some time later, a network practitioner isalerted to a suspicious event within the network—the intrusion detection system (IDS) has detected a large data transmission from from host h1 to a known malicious domain.Unbeknownst to the practitioner, this flow represents an exfiltration of sensitive data from host h2 to the open network viah1 , violating the intended data plane access control policy. Asthe practitioner begins to investigate the alert, they notice thata new flow rule was recently added between h1 and h2 , but itisn’t clear how or why this network reconfiguration occurred.To understand the context of this change to the controlplane, the practitioner attempts to perform causal analysisusing a provenance graph over the control plane’s past state,which is depicted in Figure 2a. As the practitioner now knowsthat a flow rule from h1 and h2 seems to have coincidedwith the security incident, they use this as an initial piece ofevidence: a flow rule ( f3 ) was installed that allowed trafficfrom h1 to h2 on switch s2 . The practitioner then issues aquery and identifies a set of possible root causes related to thelineage of that flow rule.2.2Existing Tool LimitationsHowever, the practitioner runs into several challenges whenusing existing tools to generate a graph such as the one in Figure 2a. Although linking h1 ’s packets to s1 ’s default flow rule(i.e., f1 ) does capture past causality, the practitioner is easilyoverwhelmed when all packets over all time from any of s1 ’sports are also linked to that default flow rule. The practitioneralso finds that switches s1 and s2 as principal agents become30th USENIX Security Symposium3185

textinPacket()t 1DefaultInboundPacketfwdt 1wasAssociatedWithFlowObjectiveServiceforward()t 4wasGeneratedByDefaultForwardingObjectivet 4t 3wasAssociatedWithwasAssociated usedWithFlowObjectiveServiceforward()t 2PacketContextinPacket()t 3wasGeneratedByDefaultForwardingObjectivet 2Figure 3: API-based provenance, based on techniques fromP ROV SDN [52], produces dependency explosion. When anapp’s event listener (fwd) is modeled as one long-runningprocess, all API calls are considered as possible dependencies.For instance, the API call at time t 4 may incorrectly appearto be dependent on all API calls from t [1, 3].too coarse-grained to enable pinpointing of attribution. Sinceexisting tools do not account for the data plane as a causalinfluence, the result in Figure 2a is a set of two disconnectedsubgraphs. That disconnection prevents the practitioner fromperforming a meaningful backward trace. Finally, backwardtracing alone would not provide the practitioner with detailsabout the attack’s other effects. We generalize those challenges and consider them in depth below.Limitation (L1): Dependency explosion Provenancemodeling suffers from the dependency explosion problem inwhich long-running processes or widely-used data structureswithin a system can create false dependencies. For instance,P ROV SDN [52] uses an API-centric model. Figure 3 showsthe provenance generated from two different calls to fwd’sevent handler, which results in four API calls in total. It is notobvious that an API call to forward() was initiated by one (andonly one) API call to inPacket(). As a result, the API-centricmodel would create many false dependencies because an APIcall would be falsely dependent on all previous API calls.F OREN G UARD’s event-centric model uses execution partitioning, but if we apply it as shown in Figure 2a, we see that acontroller that installs default flow rules (i.e., f1 ) will cause allunmatched packets (i.e., p1 and p2 ) to become dependent onit. As a result, F OREN G UARD’s modeling approach can sufferfrom data partitioning challenges when too many unrelatedeffects of a root cause must also be analyzed.Limitation (L2): Coarse-grained responsibility and falseattribution A similar challenge exists in the assignment ofresponsibility (or agency) in the data plane. In Figure 2a, theagency traces back to a switch, either s1 or s2 . Although thiscorrectly implies that one of the root causes of the attack is s1or s2 , it is not a particularly useful insight because all otheractivities have one of these root causes, too. Instead, shouldthe responsibility be assigned to a notion of a host? Given thatnetwork identifiers (e.g., MAC addresses) are easily spoofable,318630th USENIX Security Symposiumassigning agency to hosts would not solve the problem either;malicious hosts would simply induce false dependencies inthe provenance graph.Limitation (L3): Incomplete dependencies In contrast tofalse dependencies, incomplete dependencies occur when theprovenance model does not capture enough information tolink causally related activities. For SDN attacks, that occurswhen the data plane’s effects on the control plane are not captured by an implicit data plane model. In our attack scenarioin § 2.1, the reactive forwarding application reacts to activitiesfrom switch s1 before forwarding the packet (i.e., p3 ) out toother ports. On the other end of one of s1 ’s ports, switch s2receives that incoming packet (i.e., p4 ) and further processesit. Figure 2a’s disconnected subgraphs appear to show thatswitch s1 ’s history of events is independent of switch s2 ’shistory of events. Thus, if a practitioner were starting theirinvestigation from a flow rule on switch s2 , they would notbe able to see that the root cause occurred because of earlierevents related to switch s1 and the malicious host h1 ’s spoofedpackets. P ROV SDN and F OREN G UARD do not account forthis kind of data plane model and would thus suffer from incomplete dependencies. Other tools [11, 57, 59, 61] model theimplicit data plane, but are applicable only in the declarativenetworking paradigm. Most of the popular SDN controllerssuch as Floodlight, ONOS, and OpenDaylight, in contrast,use an operating-system-like imperative paradigm.Limitation (L4): Interpretation and analysis Even if thedependency-related challenges previously described were mitigated, it can still be challenge to interpret provenance graphs.For instance, if the practitioner in our attack scenario from§ 2.1 wanted to understand how network identifier bindings(e.g., the network’s bindings between a host’s MAC addressand its location in the data plane) changed over time, theprovenance graph in Figure 2a would not support that; it doesnot directly link the host objects because their generation werenot causally related.P ROV SDN and F OREN G UARD use backward tracing tostart with a piece of evidence and find its information flowancestors or set of root causes, respectively. However, if thepractitioner wanted to know the other effects of the spoofedpacket generated by h1 , that analysis would require forwardtracing techniques that start at a cause and find its progenyto determine what other data and processes were affected.As neither P ROV SDN nor F OREN G UARD performs forwardtracing, the practitioner would not be able to discover otherrelevant unexpected artifacts of the attack, such as acl’s failureto generate flow deny rules.The practitioner ultimately wants to answer network connectivity questions of the form “Which packet(s) causedwhich flow rule(s) to be (or not to be) installed?” However,the SDN controller’s event-based architecture can be itselfcomplex [53]. Although the complexity must be recorded toUSENIX Association

maintain the necessary dependencies, most of the complexity can be abstracted away to answer a practitioner’s query.Thus, abstracted summarization is necessary for practitionersto understand attacks easily and quickly.2.3Node classNode meaning and node subclassesEntityA data object within the SDN control plane state, used orgenerated through API service calls or event listenersSubclasses: Host, Packet (subsubclasses: PacketIn, PacketOut), FlowRule, Objective, Intent, Device, Port, Table, Meter, Group, Topology, StatisticOur ApproachMotivated by the attack presented in § 2.1 and the previous tools’ limitations noted in § 2.2, we highlight how P I CO SDN would mitigate the issues. P ICO SDN uses a provenance model that accounts for data and execution partitioningwith precise agency, while also incorporating the implicitdata plane effects on the control plane (§ 3). P ICO SDN alsoprovides techniques to aid in analysis (§ 5).Applying P ICO SDN produces the graph shown in Figure 2b. Rather than rely solely on the default flow rule f1as a cause, the practitioner can see that packets p1 and p2originate at a host on switch s1 ’s port 1 (L1). That also allowsthe practitioner to precisely identify agency at the switch port(rather than switch) level (L2). The previously independentactivities from each switch are linked by the data plane modelthat connects p4 with p3 (L3), which allows the practitionerto backtrace from s2 to s1 (L4). Finally, the practitioner cansee how host h1 ’s network identifier information evolved overtime (L4) and can summarize the past network state (L4).3Table 1: Nodes in the P ICO SDN provenance graph model.P ICO SDN Provenance ModelIn order to reason about past activities and perform causalanalysis, we first define a provenance model that formallyspecifies the relevant data, processes, and principal identitiesinvolved in such data’s generation and use.2 Our unified approach accounts for app, control, and data plane activities,which allows us to reason holistically about SDN attacks.ActivityAgentEach edge (or relation) e E belongs to one of the classeslisted in Table 2; rows that are indented show relations thathave more precise subclasses and meanings from their superclass. Relations form the connections among the control planeobjects, the network activities involved in their generation anduse, and principal identities within the SDN components.A backward trace path, denoted by tb hv0 e0 · · · ei v j i, e0 . . . ei Eclass6 wasRevisionOf , v0 . . . v j V , is a pathof alternating nodes and edges that begins at a node of interestv0 and ends at an ancestry node v j . An ancestry node is apredecessor of a node of interest. Given that G is a DAG,nodes v1 , . . . , v j 1 are also ancestry nodes. A backward tracedoes not include any wasRevisionOf edges because such edgesrepresent non-causal relations.A revision trace path, denoted by tr hv0 e0 · · · ei v j i, e0 . . . ei Eclass wasRevisionOf , v0 . . . v j V , is a pathof edges that begin at a node of interest v0 and show therevisions of that node’s object starting from an earlier revision node v j . These revisions are non-causal and are used toidentify changes to objects over time.3.23.1DefinitionsA provenance graph, denoted by G (V , E ), is a directedacyclic graph (DAG) that represents the lineages of objectscomprising the shared SDN control plane state. Informallystated, the graph shows all of the relevant processes and principal identities (i.e., agents) that were involved in the use orgeneration of such control plane objects. We use the graph toanalyze past activities to determine root causes (i.e., backwardtracing) and use those root causes to determine other relevantcontrol plane activities (i.e., forward tracing).Each node v V belongs to one of three high-level classes:Entity, Activity, and Agent. Each high-level node class is explained with its respective subclasses in Table 1. We detailthe design choices and semantics of these nodes in § 3.2. Anode may also contain a dictionary of key–value pairs.2 Ourmodel is loosely based on the W3C PROV data model [44].USENIX AssociationAn event listener or a packet processor used by an SDNapp or controllerSubclasses: EventListener, PacketProcessorAn SDN app, an SDN controller core service, a switchport, or a switch (i.e., device)Subclasses: App, CoreService, SwitchPort, SwitchModel design choicesGiven the aforementioned definitions, we now discuss thedesign decisions we made in P ICO SDN’s provenance model.We show how these decisions were influenced by the limitations found in previous work and how these decisions help ussolve the challenges outlined in § 2.2.Data and execution partitioning We achieve data partitioning with Entity objects by partitioning the data objectsspecified in the controller’s API. For instance, the ONOS controller’s host core service provides the API call getHosts(),which returns a set of Host objects. Thus, a natural way topartition data is to identify each Host object as a data partition.The Entity subclasses are generalizable to common SDN control plane state objects as found in the representative ONOS,OpenDaylight, and Floodlight SDN controllers.Default flow rules can generate dependency explosionsbecause any incoming packet that does not match other flow30th USENIX Security Symposium3187

Table 2: Edges (relations) in the P ICO SDN provenance graph model.Valid edge (relation) classRelation meaningEntity wasGeneratedBy ActivityCreation of an SDN control plane state objectActivity used EntityEventListener used EntityPacketProcessor used PacketUse of an SDN control plane state objectAn event listener’s use of the SDN control plane state objectA packet processor’s use of a data plane packetEntity wasInvalidatedBy ActivityDeletion of a data object within the SDN control plane stateEntity wasDerivedFrom EntityPacketIn wasDerivedFrom FlowRulePacketIn wasDerivedFrom PacketOutCausal derivation of one SDN control plane state object to another objectCausal derivation of an incoming packet based on a previously-installed flow rule (e.g., default flow rule)Causal derivation of an incoming packet from one switch based on the outgoing packet of another switchEntity wasRevisionOf EntityNon-causal revision (i.e., new version) of an SDN control plane state objectActivity wasAssociatedWith AgentAgency or attribution of an SDN control plane eventPacket wasAttributedTo SwitchPortAgency or attribution of a data plane packet with the respective switch port on which the packet was received(Default) Flow RulewasDerivedFromPacket InMAC src h 1switch:port s1:1xid 1, t 1wasDerivedFromPacket InMAC src h 2switch:port s1:2xid 1, t 2wasDerivedFromPacket InMAC src h 1switch:port s1:1xid 1, t 10wasAssociatedWithwasDerivedFromPacket InMAC src h 3switch:port s1:3xid 1, t 100(a) Data dependency explosion using default flow rules (used inP ROV SDN [52] and F OREN G UARD [55]). All packets from switchs1 that do not match any other flow rules become causally dependenton the default flow rule, which leads to dependency explosion.Switch s1Port 1wasAttributedToPacket InMAC src h 1switch:port s1:1xid 1, t 1(Default) Flow Rulematch all trafficaction send to controllerswitch s 1, xid 1wasAttributedToPacket InMAC src h 1switch:port s1:1xid 1, t 10Switch s1Port 2wasAttributedToPacket InMAC src h 2switch:port s1:2xid 1, t 2Control planeobject o 1App Xmatch all traffic, action send to controllerswitch s 1, xid 1Switch s1Port 3wasAttributedToPacket InMAC src h 3switch:port s1:3xid 1, t 100(b) Data partitioning using packets and switch port agents (usedin P ICO SDN). All packets per switch port are logically groupedtogether.Figure 4: Data partitioning models for flow rules. Ellipsesrepresent Entity nodes, and pentagons represent Agent nodes.rules is sent to the controller for processing. All previouslyunseen packets become causally dependent on a generalizeddefault flow rule, as shown in Figure 4a. To mitigate thatproblem, our model links any such packets to the respectiveedge ports that generated the packets, as shown in Figure 4b.We achieve execution partitioning with Activity objects bypartitioning each execution of recurring event listeners andpacket processors into separate activities. Figure 5 shows thedifferences between API-based modeling and event-basedmodeling. With event-based modeling, we can more clearlyshow which Entity objects were used, generated, or invalidedby a given Activity and mitigate the dependency explosion.NB API calltype WRITEt 10waswasAssociated Associate

Software-defined networking (SDN) has emerged as a flexi-ble network architecture for central and programmatic control. Although SDN can improve network security oversight and policy enforcement, ensuring the security of SDN from so-phisticated attacks is an ongoing challenge for practitioners.