# IDSMatch: A Novel Deployment Method for IDS Chains in SDNs +
## 4 IDSMatch: Deploying IDS Chains in SDN  
In this paper, we introduce an innovative extension to the data plane within SDNs, with a specific focus on tackling issues related to anomaly detection and controller overload. Within the network infrastructure, IDS applications are commonly integrated into the control plane layer. However, when the network experiences a substantial influx of incoming traffic, its ability to effectively identify anomalies becomes constrained. Moreover, there exists a limited bandwidth for communication between the data plane and the control plane. Since SDNs rely exclusively on a centralized controller to manage network traffic, a high volume of incoming traffic can overwhelm the controller, potentially leading to network failures. Deploying IDSs on specific data plane switches can relieve the SDN controller's load, and increasing the number of IDSs enhances attack detection chances in specific traffic flows. However, deploying IDS on all switches is impractical due to costs and delays. Our proposal involves strategically placing IDS chains across the data plane and directing flows through specific paths that include these IDS chains. This routing approach increases transmission delay compared to the shortest path. To mitigate this delay, we group incoming flows and route all flows within a group through the same path. A classifier categorizes traffic patterns upon entry into the network to assign the most suitable IDS chain. Grouping is based on the proximity of source and destination flows to the group's centroid. The proposed approach organizes incoming flows by measuring the distance between their source and destination points relative to a central reference point. Flows sharing the same cluster ID are regarded as part of a cohesive cluster and are subjected to identical security protocols. Subsequently, each cluster of flows is allocated a dedicated sequence of IDSs. To direct packet flow within each group through the designated IDS chain, the controller establishes rules. The task of assigning each group to an appropriate IDS chain is known to be NP-hard, and to address this complexity, we propose a modified version of the k-means algorithm as an approximate solution. **Theorem 1**. : _The complexity of the flow grouping problem being NP-hard implies that the likelihood of discovering highly efficient algorithms to achieve optimal solutions is quite low._  
Proof. : The demonstration of this fact has been presented in two notable references, namely, [39], which utilizes Exact Cover by 3-Sets, and [40], where a reduction from Planar 3-SAT is employed. The overall strategy involves clustering flows and defining a set of rules applicable to each cluster. Flow categorization hinges on the proximity of source and destination hosts to the cluster's centroid. Subsequently, the task is to allocate each cluster to an IDS chain, which can be likened to solving a matching problem. Following this, the controller configures flow rules that reroute packets from flows within each cluster through a predetermined sequence of IDSs within the assigned chain. The conventional \(K\)-means algorithm typically relies on assessing the distance between data points and their respective centroids. Nevertheless, in our specific problem, we encounter a distinct challenge that necessitates a different similarity metric than the standard \(K\)-means approach. We must devise a unique grouping strategy and similarity measurement. In our context, the data points represent flows with distinct source (\(s_{j}\)) and destination (\(d_{j}\)) attributes. To adapt the \(K\)-means clustering to our scenario, we apply it to pairs \((s_{j},d_{j})\). The distance measurement employed is \(dis(s_{j},\overline{s}_{k})+dis(d_{j},\overline{d}_{k})\), where \(\overline{s}_{k}\) and \(\overline{d}_{k}\) denote the centroids of a cluster with center \(c\). Here, we present formal definitions for flow grouping, distance measurement, and the process of matching IDS, inspired by the concepts introduced in [4].