PageRank in Cybersecurity
Do you remember the Sony PlayStation Breach of 2011? Or the cyber attacks on Nasa in 1999? Most of you will probably remember the former and are curious as to how such large, pivotal companies could face severe security breaches such as these. A group of researchers at Carnegie Mellon University (CMU) were interested in preventing similar breaches and exploitations in computer systems by modeling all possible security vulnerabilities in what is considered an attack graph. The purpose of an attack graph is to not only model security vulnerabilities but also do so in a manner in which relevant portions of the graph are held at utmost importance i.e. what part of a computer system is a hacker most likely to target? In doing so, the attack graph allows a system administrator to “concentrate on relevant subgraphs to figure out how to start deploying security measures.”
You may be thinking “Well, why don’t they fix these vulnerabilities and all would be dandy?” Well, as it turns out, it’s not that simple when it comes to realizing the faults within a large, complex system. As stated in the publication,
[…] It is not feasible for a system administrator to try and remove each and every vulnerability present in these systems. Therefore, the recent focus in security of such systems is on analyzing the system globally, finding attacks which are more likely and severe, and directing resources efficiently to increase confidence in the system. (128)
One of the more interesting things about the implementation of this graph is its utilization of Google’s PageRank algorithm to rank states of an attack graph. Similar to probabilistic trees in CS 2800, the attack graph assigns a probability to each possible event. From there, they compute the ranks of all states with their own modification of PageRank. Just as we demonstrated in class the implementation of PageRank in ranking valued web pages and links so the researchers apply the algorithm to rank states in order of importance “based on factors such as the probability of an intruder reaching the state.” To read more about this ingenious approach of tackling security vulnerabilities, click here.
http://www.cs.cmu.edu/~cbartzis/papers/rankattack.pdf