Host Attack Graph for Botnet Propagation

arXiv:2610.11640 · cs.CR, cs.GT, cs.NI · Submitted 2026-10-08 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: I'm Nadia, and with me are Elias and Priya, guest researcher.

Elias: Today's paper: "Host Attack Graph for Botnet Propagation".

Nadia: The Host Attack Graph model and two botnet propagation strategies are introduced to study how network topology and target selection affect botnet spread effectiveness over time.

Elias: First, who's behind it and why it matters.

Title and authors: Nadia: So we're looking at this paper now called "Host Attack Graph for Botnet Propagation," and it really tries to model how those botnets actually spread over time, you know, not just how fast they grow randomly.

Elias: Right, and the authors are Andrei Neagu, Mara-Cristina Sterian, and Paul Irofti from the University of Bucharest; they're the ones who put this Host Attack Graph model together.

Nadia: What is this Host Attack Graph model doing for us in simple terms? It seems like it's a way to figure out which hosts are most likely to get compromised by looking at their vulnerabilities and how they connect to others.

Priya: From what I can see, the paper uses a Bayesian Attack Graph framework defined at the individual machine level, which lets them assign a specific probability of compromise for each host based on its vulnerabilities and those goals it has.

Nadia: And they pair that with this Susceptible Infected Protected model to track how the network changes over time as the attack progresses, which is pretty cool for seeing the dynamics.

Elias: They also introduce two specific strategies for choosing which hosts to target and how to spread the infection, which moves beyond just picking random nodes.

Priya: I'm curious about what this means for measurement; they are using three types of graphs, like Erd˝os–Rényi random graphs, Barab´asi-Albert scale-free models, and Watts-Strogatz small-world graphs to see how the structure of the network affects things.

Nadia: And they test target selection based on centrality measures like degree, closeness, betweenness, eigenvector centrality, and percolation based centralities to see which ones work best.

Elias: They introduce two strategies here: the sticky strategy and the weighted strategy for target selection and propagation that they compare against random versions of those.

Priya: What's the actual finding on those strategies? The paper does a Spearman analysis across different graph topologies and centralities, which suggests that network topology and target selection shouldn't be ignored.

Nadia: Exactly, because in their study with graphs of one thousand twenty-four nodes, they found that degree, closeness, betweenness, and eigenvector centrality all had Spearman correlations larger than zero point nine.

Elias: That means the paper suggests that those structural measures are actually really good indicators for characterizing how malware propagates through a network.

Priya: They also noted that the average fraction of network owned by the attacker was about as comparable to their random counterpart, with percolation being the only constant difference when using the weighted strategy.

Nadia: So, what does this mean for someone just listening to this show? It means we can’t just look at a random network structure and assume it doesn't matter; we need to consider how those key structural points—the high-degree or high-betweenness nodes—are picked as targets.

Title and authors: Elias: And on the bigger picture, the Host Attack Graph model is positioned to help us move toward using AI systems to compute root compromise probabilities for individual hosts by modeling vulnerabilities chain and calculating the PPIE to determine user compromise probability.

Nadia: That would let us potentially use this information for targeted vulnerability patching or prioritizing threats in a way that's much more specific than just treating the whole network as one thing.

Priya: Modeling the propagation with those two strategies, like sticky and weighted, allows AI systems to simulate how spread happens under different attacker budgets, which could help us design defenses against specific attack scaling scenarios.

Elias: And by using that Susceptible Infected Protected model dynamically across time intervals during a simulation, we can get a real-time assessment of network vulnerability and propagation dynamics as the attack unfolds.

Nadia: So, to wrap up the Host Attack Graph for Botnet Propagation paper, we see that modeling the spread isn't just about the botnet size or the strategy chosen; it’s fundamentally about understanding how those specific network topologies and target selections interact over time.

Priya: I just want to say that while this is a solid model for characterizing propagation behavior, a limitation they mention is that their current methods might only provide modest improvements over the baseline regardless of the network topology they use.

Nadia: That's fair, it's not claiming perfection across every single scenario, but it definitely gives us a much better starting point than just assuming everything is random.

Elias: And for future work, they suggest focusing more on centrality-based selection because current methods are still showing modest gains even when you change the network structure.

Priya: It’s interesting how they pointed toward the frontier of susceptible hosts at time t, S(t) = s i in I(t), h in V not s.t. (s, h) in E, as a special interest for future study in this area.

Nadia: Exactly, so we're seeing the path forward isn't just tweaking the current methods but really digging into how those frontier sets behave under attack pressure.

Elias: We have covered the basics of this Host Attack Graph for Botnet Propagation paper, looking at how they model spread with those two strategies and what the Spearman analysis on centrality measures actually showed us about network structure.

Priya: I think the real implication for us is getting a more principled way to quantify risk in these complex networks, moving beyond just counting connections.

Nadia: Indeed, we’ll be keeping an eye on how this framework helps us prioritize defenses when dealing with those large botnets out there.

Elias: That wraps up our look at the Host Attack Graph for Botnet Propagation paper; we've got a lot of modeling to think about as we move on to the next one.

The paper's summary: Nadia: So, to recap this whole paper, they’ve put together this Host Attack Graph model alongside two different ways bots can spread, all to figure out how much of a network a botnet can take over over time.

Elias: They use this Host Attack Graph thing which is built on Bayesian Attack Graphs at the individual machine level to figure out those root compromise probabilities.

Priya: And they layer that on top of the Susceptible Infected Protected model, which tracks how the network changes as time moves forward during an attack simulation.

Nadia: The core idea is looking at how network topology and which targets you pick really matters when you're trying to stop a botnet from spreading effectively.

Elias: They test two specific propagation strategies, the sticky strategy and the weighted strategy, to see how target selection impacts that spread.

Priya: The experimental findings show that you can't just ignore the network structure; measures like degree and betweenness centrality are actually very correlated with how effective those propagation strategies are.

Nadia: They found strong correlations, like over zero point nine for things like eigenvector centrality across different graph types, which suggests these structural points are really important indicators.

Elias: And they also observed that the average network fraction owned by the attacker stays pretty consistent whether they use a random approach or one of their structured ones, with just a small difference when using the weighted strategy.

Priya: So what this means for us is that we need to think about how those key structural measures actually influence which hosts get compromised and how fast the infection moves through the network.

Nadia: It shifts the focus from just looking at a static map of connections to understanding dynamic choices made by an attacker as they scale up their operation.

Elias: And for me, this model gives us a way to think about how we might integrate this into AI systems to calculate those root compromise probabilities for individual hosts by modeling vulnerabilities chain and calculating the PPIE.

Priya: If we can use that, it could lead to real-time threat prioritization or maybe even targeted vulnerability patching based on what the simulation predicts is most likely.

Nadia: Exactly, it moves us toward a more proactive stance where we're not just reacting to an infection but trying to predict and mitigate the most dangerous paths.

Elias: And simulating those propagation strategies under different attacker budgets lets us test how our defenses would hold up against specific scaling scenarios during the simulation.

Priya: It gives us a way to measure the effectiveness of different defense hypotheses by seeing how they play out against these modeled attack dynamics.

Nadia: So, we’re looking at a framework that combines network structure, time evolution, and attacker strategy to build better models for botnet spread.

Elias: The next thing we need to consider is how we can practically use these probabilities and strategies inside an AI system to make real decisions about defense.

The paper's improvements: Nadia: So, looking at what the authors suggest for moving this research forward, they aren't just stopping at their current results, they want to see how we can really integrate this into practical systems.

Elias: Right, they point toward using those centrality measures—degree, closeness, betweenness—as a more structured way to select targets as the attacker budget gets bigger.

Priya: They say that current methods are just starting to show modest gains no matter what kind of network topology you use, so focusing on how we select victims based on those metrics is where the real progress lies.

Nadia: That means for us, it’s not enough to just model the spread; we need better ways to choose *where* the attack should focus within that network structure.

Elias: They are also really interested in taking these models and putting them into AI systems to compute root compromise probabilities for individual hosts by modeling those vulnerability chains directly.

Priya: If they can link that up with calculating the PPIE, it could give us a way to figure out the actual probability of user compromise or root compromise for any single machine.

Nadia: That would let us do much more targeted work, like prioritizing vulnerability patching based on what the model predicts is most likely to get hit.

Elias: And by implementing those sticky and weighted strategies we discussed earlier, they want AI systems to simulate how spread happens under different attacker budgets during an attack.

Priya: That simulation power means we can test potential defense strategies against specific scaling scenarios before we even deploy them in the real world.

Nadia: So the authors are pushing us to move from just characterizing propagation behavior to actually using those models to drive proactive defense simulations and prioritization decisions.

Elias: And they flag that current methods still show modest improvements regardless of topology, so future work should really focus on making sure the centrality-based selection is robust across all kinds of networks.

Priya: They also highlighted the frontier of susceptible hosts at time t, which they see as a special area for future study because that set is where the action actually happens during an ongoing attack.

Nadia: It sounds like the next big step is moving beyond just knowing how fast things spread to building tools that tell us exactly what to do when we know *how* they are trying to spread.

Conclusion: Tom: So we're wrapping up this look at the Host Attack Graph for Botnet Propagation model and what it means for understanding botnet spread over time.

Nadia: To recap, they introduced this Host Attack Graph model with two propagation strategies to study how network structure and target selection affect botnet spread effectiveness.

Elias: They showed that using centrality measures like degree or betweenness isn't just random; those structural points matter a lot when you decide which hosts to target.

Priya: The data really shows that network topology and how targets are picked are important factors, and they found strong correlations across different types of graphs.

Nadia: So what this means for the world is that we need better ways to characterize malware behavior beyond just seeing a list of connections; we have to consider the strategic choices an attacker makes.

Elias: And this model could be really useful if we can get it into AI systems to compute root compromise probabilities for individual hosts by looking at vulnerabilities chain and calculating the PPIE.

Priya: If that works, it opens up a path for targeted vulnerability patching or prioritizing threats based on what the simulation predicts is most likely to get hit.

Nadia: Exactly, we move from just reacting to an infection to actually predicting and mitigating the most dangerous paths in those complex networks.

Elias: They also showed that by modeling those sticky and weighted strategies, AI can simulate how spread happens under different attacker budgets during an attack scenario.

Priya: That gives us a way to test potential defense strategies against specific scaling scenarios before we even deploy them in the real world.

Nadia: The authors flag that their current methods still show modest improvements regardless of the network topology they use, so future work should focus on making sure that centrality-based selection is robust across all kinds of networks.

Elias: They also pointed toward the frontier of susceptible hosts at time t as a special area for future study because that set is where the action actually happens during an ongoing attack.

Priya: I just want to say that while this is a solid model for characterizing propagation behavior, they admit their current methods might only provide modest improvements over the baseline regardless of the network topology they use.

Nadia: That’s fair, it’s not claiming perfection across every single scenario, but it definitely gives us a much better starting point than just assuming everything is random.

Elias: And for me, this framework sets up a solid foundation for how we might integrate those probabilities and strategies into an AI system to make real decisions about defense.

Priya: I think the main thing here is getting a more principled way to quantify risk in these complex networks, moving beyond just counting connections.

Nadia: Indeed, we’ll be keeping an eye on how this Host Attack Graph for Botnet Propagation model helps us prioritize defenses when dealing with those large botnets out there.

Elias: That wraps up our look at the Host Attack Graph for Botnet Propagation paper; we've got a lot of modeling to think about as we move on to the next one.

Andrei Neagu, Mara-Cristina Sterian, Paul Irofti

Department of Computer Science, Faculty of Mathematics and Computer Science, and Interdisciplinary School for Doctoral Studies, University of Bucharest

cs.CR, cs.GT, cs.NI

Submitted: 2026-10-08

Updated: 2026-10-08

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

The gist: The Host Attack Graph model and two botnet propagation strategies are introduced to study how network topology and target selection affect botnet spread effectiveness over time.

Key concepts

Host Attack Graph (HAG): A novel method used to calculate the probability that a machine will be compromised by an attacker. It combines Bayesian Attack Graphs with a Susceptible, Infected, Protected (SIP) model to track how infection spreads across the network over time.
Susceptible, Infected, Protected (SIP) Model: A mathematical framework used to simulate how a virus or botnet evolves in a network. Hosts are categorized as susceptible (can be infected), infected (already compromised), or protected (immune), allowing researchers to model the spread dynamics.
Centrality Measures: Metrics like degree, closeness, and betweenness are used to measure the importance of different nodes within a network. These measures help determine which hosts are most influential in spreading an infection or being targeted by an attacker.
Sticky Strategy: An attack strategy that selects the top-k susceptible hosts with the highest centrality scores at each time step and attempts to compromise them. This strategy prioritizes targeting the most important nodes first.

Terminology

Host Attack Graph — 41× in this paper
Nadia — 28× in this paper · explained in 2 episodes
Elias — 25× in this paper · explained in 2 episodes
Susceptible Infected Protected — 4× in this paper
Benchmark — 2× in this paper · explained in 2 episodes
Core — 2× in this paper · explained in 2 episodes
Robustness — 2× in this paper · explained in 5 episodes
Actor — 1× in this paper · explained in 3 episodes
Clustering — 1× in this paper · explained in 2 episodes
Consistency — 1× in this paper · explained in 3 episodes
Principal Component Analysis (PCA) — 1× in this paper · explained in 4 episodes
World Model — 1× in this paper · explained in 7 episodes

Summary

The Host Attack Graph model and two botnet propagation strategies are introduced to study how network topology and target selection affect botnet spread effectiveness over time. This research matters because it provides insights into characterizing malware propagation behavior and designing targeted defensive strategies against botnets

Botnet Modeling

The Host Attack Graph (HAG) is a novel method for computing root compromise probabilities, coupled with the Susceptible, Infected, Protected (SIP) model for network evolution across time and two new strategies for target selection and propagation The HAG is built on the framework of a Bayesian Attack Graph [16], defined at the individual machine level Host attributes are defined as the set of vulnerability attributes and goal attributes, where vulnerability attributes are denoted as Av(h) = Sv: v ∈ V (h), and goal attributes are G(h) = g1, g2,..., gn such that gi = V (gi(h)) ⊆ V (h)

Network Topology and Centrality

The study utilizes three types of graphs to measure behavioral patterns of propagation: Erd˝os–R´enyi random graphs [6], Barab´asi-Albert scale-free models [1], and Watts-Strogatz small-world graphs [20] Hosts are divided into three types: susceptible (S), infected (I), and protected (P) making this a SIP model The frontier is defined as the set of susceptible hosts at time t, S(t) = s i ∈ I(t), h ∈ V not s.t. (s, h) ∈ E Target selection is based on centrality measures such as degree, closeness, betweenness, eigenvector and percolation based centralities

Propagation Strategies

The paper introduces two attack strategies that can be paired with each centrality measure: the sticky strategy and the weighted strategy The sticky strategy selects the top-k (arg maxk) susceptible hosts with the highest centrality and tries to compromise them at each time t, denoted as sticky(t)k = arg maxk(c, S(t)) The weighted strategy selects k susceptible hosts at random, weighted by their given centrality score, at each interval t These strategies are compared against baselines like random sticky and random weighted, and an ideal attacker is also included as a reference point

Experimental Findings

Spearman analysis across different graph topologies, node centralities and propagation strategies was conducted The results show that network topology and target selection should not be easily discarded For example, in Figure 5, the Spearman correlation study for graphs of 1024 nodes shows that degree, closeness, betweenness and eigenvector have values larger than 0.9 Furthermore, the average fraction of network owned by the attacker is comparable to their random counterpart and we identify the only constant difference for percolation when utilising the weighted strategy

Conclusions and Future Directions

The study introduces a Host Attack Graph model for estimating compromise probabilities of a given computer network and proposes two botnet propagation strategies The simulations show the effectiveness of our two strategies and provide insights regarding the impact of the network topology on the botnet propagation Future research should focus on centrality-based selection as current methods provide modest improvements over the baseline regardless of network topology The authors consider frontier P r(U(h))’s to be of special interest here The paper makes available the source code and datasets used to compare botnet propagation algorithms including probability computations, centrality and scenario generation

The gist

The Host Attack Graph model and two botnet propagation strategies are introduced to study how network topology and target selection affect botnet spread effectiveness over time.

Botnet Modeling

The Host Attack Graph (HAG) is a novel method for computing root compromise probabilities, coupled with the Susceptible, Infected, Protected (SIP) model for network evolution across time and two new strategies for target selection and propagation The HAG is built on the framework of a Bayesian Attack Graph [16], defined at the individual machine level Host attributes are defined as Av(h) = Sv: v ∈ V (h), and goal attributes are G(h) = g1, g2,..., gn such that gi = V (gi(h)) ⊆ V (h)