Application of the PageRank Algorithm to Alarm Graphs (Extended Abstract)
- Ammann, P., Wijesekera, D., Kaushik, S.: Scalable, Graph-Based Network Vulnerability Analysis. In: Proceedings of the 9th ACM Conference On Computer and Communications Security. New York: ACM Press. (2002) pages 217-224.
- http://www.covert.io/research-papers/security/Application%20of%20the%20PageRank%20Algorithm%20to%20Alarm%20Graphs.pdf
In the class, we discuss an interesting approach to solve the web search problems – PageRank algorithm. I am really interested in this topic. After doing some research, I find out PageRank algorithm is widely applied in many field. Moreover, one of the recent applications, which is using the PageRank to build Alarm Graphs, studied by James J. Treinen and Ramakrishna Thurimella, is innovative and useful.
As we known, the task of separating genuine attacks from false alarms in large intrusion detection infrastructures is extremely difficult. The number of alarms received in such environments can easily enter into the millions of alerts per day. The overwhelming noise created by these alarms can cause genuine attacks to go unnoticed. As means of highlighting these attacks, they introduce a host ranking technique utilizing Alarm Graphs. Rather than enumerate all potential attack paths as in Attack Graphs, they build and analyze graphs based on the alarms generated by the intrusion detection sensors (IDS) installed on a network.
In the paper, they use PageRank algorithm and by elevating the rank of known attackers and victims they are able to observe the effect that these hosts have on the other nodes in the Alarm Graph.
In detail, they extend the concept of ranking web graphs to ranking Alarm Graphs in the following manner. Each alarm in the alarm set has the potential to represent a genuine attack. For the purposes of their analysis, they think of an attack as a state transition from the node representing the attacker to a successful compromise of the target IP of the alarm. Following this logic, each path in the Alarm Graph represents a potential path of compromise by an attacker through the monitored network.
Using Alarm Graphs, they model the potential paths that an attacker could take through the network, as detected by the intrusion detection sensors (IDS), in lieu of the web graph which is proposed in the original PageRank discussion. Using this model, they then analyze which nodes in the graph have the highest probability of being visited by an attacker, given random entry into the Alarm Graph.
Ideally, when using this approach they would produce rankings in which nodes undergoing genuine attacks receive the highest ranks, and as the level of risk for a host decreases, so does its corresponding rank. They produce visualizations that highlight nodes of highest risk like Figure 1.
Figure 1: Colored Alarm Graph from production network, including auxiliary nodes and attack signatures
This graph shows a subgraph of an Alarm Graph generated from production IDS data. The full Alarm Graph is too large to display in a readable manner in print. This figure illustrates two known attacks. The nodes are colored so that the darker the color of the vertex, the higher its rank. The darkest vertices in the graph are those hosts, which are known to be involved in attacks, and are shown with the corresponding auxiliary nodes added. Those vertices which are a lighter shade of gray have inherited high rankings, and will appear on the watch list generated at the end of the ranking routine. Additional gray nodes exist in the form of hosts, which have received IDS alarms from multiple sources. These atypical patterns are caught by the ranking algorithm, and these hosts will appear on the watch list as well. The visual representation of the colored Alarm Graphs provides a compact model that can be used by a human analyst to quickly triage the monitored network, providing visual cues as to which systems require immediate attention.