— A Graph-Theoretic Approach with Python
Network security is never just about having the right tools — it’s about placing them in the right spots. An Intrusion Detection System (IDS) or Intrusion Prevention System (IPS) sitting in the wrong segment of your network might miss 60% of malicious traffic while a thoughtfully placed sensor catches nearly everything. Today, we’ll model this as a combinatorial optimization problem and solve it with Python.
Problem Setup
Imagine a corporate network modeled as a directed graph:
- Nodes = network segments (DMZ, internal LAN, data center, IoT zone, etc.)
- Edges = traffic flows between segments
- Each edge has a traffic volume (how much data flows) and an attack probability (how likely an attack is to traverse it)
We want to place $k$ IDS/IPS sensors on edges (links) to maximize the expected detection coverage, defined as:
$$\text{Coverage} = \frac{\sum_{e \in S} w_e \cdot p_e}{\sum_{e \in E} w_e \cdot p_e}$$
Where:
- $E$ = all edges in the network
- $S \subseteq E$ = the set of monitored edges (sensor placement)
- $w_e$ = traffic volume on edge $e$
- $p_e$ = attack probability on edge $e$
- $|S| \leq k$ = sensor budget constraint
This is a budgeted maximum coverage problem. The optimal solution is NP-hard in general, so we compare three strategies:
- Greedy — pick the top-$k$ edges by risk score $w_e \cdot p_e$
- Simulated Annealing (SA) — stochastic global optimizer
- Integer Linear Programming (ILP) — exact solver via PuLP
We also evaluate detection across attack path scenarios, simulating how likely an attacker traversing a known path gets caught.
The Math Behind It
Risk score per edge:
$$r_e = w_e \cdot p_e$$
Objective (maximize):
$$\max_{S \subseteq E,, |S| \leq k} \sum_{e \in S} r_e$$
Attack path detection probability (at least one sensor on the path):
$$P(\text{detect} \mid \text{path } \pi) = 1 - \prod_{e \in \pi} (1 - \mathbf{1}[e \in S])$$
In other words, detection fails only if every edge on the attack path is unmonitored.
Simulated Annealing acceptance criterion:
$$P(\text{accept worse}) = \exp!\left(\frac{\Delta f}{T}\right), \quad T_t = T_0 \cdot \alpha^t$$
Full Python Code
1 | # ============================================================ |
Code Walkthrough
Section 1 — Network Definition
The network is a directed graph with 10 nodes and 15 edges. Each edge carries two properties:
volume— how much traffic flows (proxy for how much an attacker would blend in)attack_prob— estimated probability that malicious traffic traverses this link
Five realistic attack paths are pre-defined, from a naive web-to-database intrusion all the way to a stealthy slow-exfiltration scenario.
Section 2 — Optimization Methods
Greedy is the simplest: sort all edges by $r_e = w_e \cdot p_e$ and pick the top $k$. It’s $O(E \log E)$ and guaranteed to find the exact optimum here because the objective is a modular (additive) function over edges — no submodularity gap exists for pure edge coverage.
Simulated Annealing explores the solution space stochastically. At each iteration it proposes swapping one sensor to a different edge and accepts the move with probability:
$$P = \begin{cases} 1 & \text{if } \Delta f > 0 \ e^{\Delta f / T} & \text{otherwise} \end{cases}$$
Temperature decays as $T_t = T_0 \cdot \alpha^t$ with $\alpha = 0.995$, giving 8,000 iterations a good exploration-exploitation balance.
ILP with PuLP/CBC casts the problem as:
$$\max \sum_i r_i x_i \quad \text{s.t.} \quad \sum_i x_i \leq k, \quad x_i \in {0,1}$$
This is a 0-1 Knapsack problem — CBC solves it exactly in milliseconds at this scale.
Section 3 — Budget Sweep
We run all three methods for every possible $k$ from 1 to 15. This produces the coverage and path-detection-rate curves plotted in Panels 1 and 2.
Section 4 — Demo at k = 5
With five sensors, ILP confirms which edges are mathematically optimal. The output prints each sensor’s placement with its risk score for easy auditability.
Graph-by-Graph Explanation
Panel 1 — Coverage vs Budget: All three methods converge quickly — by $k=7$ or so, you’ve covered 90%+ of the weighted risk. The yellow dashed line marks our $k=5$ demo. Notice ILP and Greedy are nearly identical: this confirms the greedy strategy is near-optimal for this additive objective.
Panel 2 — Attack Path Detection vs Budget: Path detection is a step function — it jumps whenever a new sensor covers a previously unmonitored path. SA can sometimes outperform Greedy here because it explores non-obvious edge combinations that happen to intersect multiple paths.
Panel 3 — Edge Risk Scores: Orange bars are the ILP-selected edges at $k=5$. The highest-risk links (Internet→Firewall, DB Server→Backup, App→DB) are grabbed first.
Panel 4 — Network Graph: Orange edges carry IDS sensors. You can visually trace each attack path and see which steps are now monitored.
Panel 5 — Detection Heatmap: Green = attack path detected, Red = missed. With $k=1$ only the most traversed path is covered; by $k=4$ all five paths are detected. This is the key operational insight: 4 sensors suffice to catch every modeled attack scenario.
Panel 6 — Marginal Gain: The diminishing-returns curve of security investment. The first sensor buys ~20% coverage; the fifth buys only ~5%. This informs budget decisions: beyond a certain $k$, additional sensors offer little marginal value.
Panel 7 — 3D Surface (Budget × Probability Threshold × Coverage): We filter edges by a minimum attack-probability threshold and compute coverage within that filtered set. At low thresholds (all edges included), coverage is diluted. At high thresholds (only high-risk edges), even $k=1$ achieves 100% within-filter coverage. This surface helps security teams decide where to focus given intelligence about likely attack vectors.
Panel 8 — 3D Surface (Budget × Path × Detection): Each attack path “lights up” (Z=1) once a sensor is placed on one of its edges. The cliff-step pattern shows exactly which budget increment covers each additional path.
Panel 9 — Method Comparison at k=5: The grouped bars confirm that at this scale, Greedy matches ILP on risk coverage. SA performs competitively and would shine more in problems where the objective is non-additive (e.g., overlapping coverage zones or correlated sensors).
Execution Result
Network: 10 nodes, 15 edges Total risk score: 1564.5 Sensor budget range: 1 to 15 Sweep complete. === k=5 Sensor Placement === Greedy: Edge 0: Internet→Firewall vol=1000 p=0.3 risk=300.0 Edge 3: DMZ→Web Server vol=700 p=0.35 risk=245.0 Edge 1: Firewall→DMZ vol=800 p=0.25 risk=200.0 Edge 4: DMZ→App Server vol=500 p=0.28 risk=140.0 Edge 6: App Server→DB Server vol=350 p=0.4 risk=140.0 Coverage=0.6552 PathDetect=1.0000 SA: Edge 4: DMZ→App Server vol=500 p=0.28 risk=140.0 Edge 1: Firewall→DMZ vol=800 p=0.25 risk=200.0 Edge 6: App Server→DB Server vol=350 p=0.4 risk=140.0 Edge 0: Internet→Firewall vol=1000 p=0.3 risk=300.0 Edge 3: DMZ→Web Server vol=700 p=0.35 risk=245.0 Coverage=0.6552 PathDetect=1.0000 ILP: Edge 0: Internet→Firewall vol=1000 p=0.3 risk=300.0 Edge 1: Firewall→DMZ vol=800 p=0.25 risk=200.0 Edge 3: DMZ→Web Server vol=700 p=0.35 risk=245.0 Edge 4: DMZ→App Server vol=500 p=0.28 risk=140.0 Edge 6: App Server→DB Server vol=350 p=0.4 risk=140.0 Coverage=0.6552 PathDetect=1.0000
Figure saved.
Key Takeaways
| Finding | Implication |
|---|---|
| 4 sensors cover all 5 attack paths | Minimum viable sensor count for this topology |
| Greedy ≈ ILP for additive objectives | Greedy is safe for pure edge-coverage problems |
| SA adds value for non-additive variants | Use SA/GA when sensors have overlapping or joint effects |
| Marginal gain drops sharply after k=6 | Budget beyond 6 sensors has diminishing returns |
| High-prob threshold + small k = focused defense | Prioritize sensors near high-probability attack vectors |
The framework scales: swap in your real network topology, real traffic logs for volume estimates, and threat-intel scores for attack probabilities, and the same optimizer will tell you exactly where your next IDS sensor should go.