Graph Theory: Analyzing Social Networks
Reading time: 3 – 4 minutes
Photo: escapedtowisconsin
Social networking applications are among the most popular websites that are used on the Internet. Facebook.com and myspace.com are both in the top 20 most visited pages on the Internet. According to Alexa, 17% of global Internet users visit facebook.com on a daily basis.
How can attackers use the abundant amounts of information that is available on these websites to aid in their attacks?
One method is by analyzing a victims social network using network analysis.
Network analysis is a way to infer information from the social connections that someone makes. An attacker could use a social applications data set to:
- identify positive and negative relationships
- identify their victims mood
- identify individuals that are most influential in a group
By assigning people and organizations to nodes and linking nodes based on relationships, attackers can begin to infer information from these social graphs.
Who is the Most Influential?
It is beneficial for an attacker to know who is the most influential person in their victim’s social network. Constructing a malicious instant message or email that requires user intervention (think Reflective Cross-Site Scripting) will have a higher success rate, if it is sent from the victim’s most influential friend.
In order to analyze the victim’s social network from an influential perspective, the attacker begins by constructing a graph with the victim in the center and each of the victim’s friends as node off of the victim.
In this example, Sam is the attacker’s target. Sam has five friends, Alice, Bart, Charlie, Dave, and Ed. This would create a star graph that would look like this.
The next step is for the attacker to analyze the connections between Sam’s friends. The attacker identifies that Alice communicates with Bart on a regular basis, so a link is made between Alice and Bart.
It is also easier for the attacker to understand who is the most influential by assigning a value to each vertex. Alice and Bart’s vertex would change from 0 to 1, since they know one of Sam’s friends. In this example, we have made the vertex larger and assigned it a number. Once the social network is analyzed the attacker will have a graph similar to this.
Since Ed knows 3 of Sam’s friends, it can be inferred that Ed is the most influential in Sam’s network. If an attacker wanted to send a malicious instant message or email to Sam, the attacker would have the highest rate of success if the malicious message was from Ed.
This is a simple example. In reality, social networks are vastly more complicated. However, with the use of certain API’s an attacker could use network analysis to his benefit.
