Assigning Maliciousness to Tweets
Group Members: Joseph Stamenkovich, Afsayh Saquib, Peter Tsongalis
Project Overview and Motivation
With social media influence becoming more prevalent in the modern age, the danger for terrorist and malicious propaganda spreading through these mediums worsens. Using techniques in machine learning it is possible to train a model to detect malicious tweets, be they threats or simply propaganda, to aid in the networking of terrorists as well as to prevent threats from becoming a reality. Undirected graphical models that are essentially Markov Random Fields, and graph theory as a whole can also help visualize how these suspicious words relate to each other and can provide some insight behind the algorithms.
Approach to a Solution
To begin to solve the problem of identifying malicious tweets, we first needed to establish a database of non-malicious tweets and malicious text strings to combine to make a training data set. Once we mined tweets from Twitter and generated malicious strings from terrorist propaganda using Markov Chains, we were able to train models using two machine learning algorithms: Naive Bayes and Multi-Layered Perceptron Classifiers. With these models trained, a test set of malicious and non-malicious tweets was applied and the results quantified by a percentage accuracy for each method.
How adept are humans at noticing maliciousness?
Even without knowing the context or author of the tweet, from the words used one can assign different levels of suspicion. In cases such as above, the contrast can be stark, and in others it can be very difficult to tell sincerity from sarcasm. With the hypothesis that there could be something inherent in lingual data that can help determine suspiciousness and/or maliciousness, we attempted to use machine learning algorithms to train models which perform this human task on large data sets.
Data Mining and Malicious Text Generation
Using the python-twitter library, it was easy to mine tweets from different locations across the United States. These tweets were then manually checked to ensure they were not malicious and would not interfere with the training in that way. Next, using writings from a well known terrorist¹, we were able to generate our own malicious text strings using a simple Markov Chain. Combining these two sets of data, the result was our training data set with both malicious and non-malicious text strings.
Training Data
DataMatrix: (# of tweets) by (# of words (sorted alphabetically)) matrix showing which words are in which tweets
MaliciousnessMatrix: vector of size (# of tweets) showing which tweets are classified as malicious
WordSet.txt: set of all words in the data matrix in alphabetical order (can be used to generate test data vectors)
DataMatrix.csv.gzMaliciousnessMatrix.csv.gzWordSet.txtGraphical Models
By generating our suspicious tweets using Markov Chains, we may not have always had grammatically correct sentences, but we were primarily examining these tweets on a word choice basis. Having these probabilistic based tweets allowed for, among other computations, the generation of undirected graphical models reflecting the dependencies between certain words for being suspicious, essentially Markov Random Fields. Google's Fusion tables provided a easy tool to create these once the data was in order. To organize the data in the correct format, we needed to list every word that appeared in the suspicious tweets against every other word that appeared in the tweets. We then counted the number of times both words appeared in the same tweet. Filtering and weighting by this count, as well as the particular words of interests, allowed for clear results.
The network graph to the left shows the most common words used across all of the suspicious tweets and how they depend on each other to be considered suspicious. Each ink means that the those two words were used in a suspicious tweet, and the larger the node, the more often it was used. Various cliques are apparent, demonstrating groups of words that were repeatedly flagged as suspicious when used together.
Lets look at another example application of the graphical models. Say you wanted to see what suspicious persons are associating America or Americans as enemies without actually saying that. In fact, the graph on the right shows that "enemy" and "America" aren't directly connected at all, meaning that in our data set America and enemy were not used in the same tweet in anything generated as suspicious. In other words, because of our probabilistic approach to generating these tweets, it is not as likely that this terrorist organization will outright call America the enemy as some may have thought. However, we can see that by hovering over "money" or "God" that enemy is connected to both America and American's. We can use this information to be suspicious of an individual's intentions towards America tweeting about American's and their money and also tweeting about people with lots of money as the enemy. It is also apparent from this graph that this terrorist group associates a great many things as the enemy. We could also run a Node Importance algorithm for a more precise computation. This can be simulated by limiting the amount of nodes you have selected. Try it on our "America-Enemy" graph by changing the amount of nodes to 10. Not only do our main nodes with the most connections remain, but also the ones linking these important ones together.
Naive Bayes
This classifier is simple (naive) and assumes independence between all features. In the case of our application, this naivety diminishes the effectiveness of the algorithm because it assumes that seeing malicious or threatening words in a tweet are not related to one another. For this method to classify a tweet as malicious it must see a correlation between the words in that tweet and another malicious tweet that it has seen before.
While the Naive Bayes classifier performed well on our test suite, registering a 75% correct classification rate, it sometimes misclassified some text strings that would seem obvious to the naked eye.
Multi-Layered Perceptron
This classifier uses more advanced techniques than the Naive Bayes Classifier to determine the class of a string of text. Using a technique called backpropagation through supervised learning, the MLP Classifier can be used to distinguish between data that is not linearly separable which is often the case for malicious versus non-malicious text strings (i.e. "That movie was the bomb" and "I will make a bomb" use similar phrasing but have different meanings).
With this more advanced method, correct classification rate increased to 84% and while this is still not perfect, it represents a marked improvement over the naive approach of the first method.
Solution Drawbacks
While both the Naive Bayes Classifier and the Multi-Layered Perceptron Classifier have produced decent results, there are several drawbacks to the solution as a whole mostly dealing with the data that we gathered. First, having tweets that originated only in the United States narrows the usefulness of our solution as the only language present is English. Second, with only one piece of terrorist literature to train on, many possibly malicious phrases and statements are left out of the training set. While we added some blatant malicious terms to test their detection, it was not possible to test on the full scope of malicious tweets. By only having access to one piece of terrorist literature, we can certainly see the bias of these groups in the graphs, and inevitable the algorithms determining whats suspicious. The religious extremist nature of this propaganda could lead our algorithm to have an unfair suspicion of people tweeting about God for example. Ambiguity in words without much context can also be problematic in general. We would need a much more expansive data set to train to have more reliable, practical, and unbiased results.
Previous Work and Other References
Cooperative Game Theoretic Centrality Analysis of Terrorist Networks: The cases of Jermaah Islamiyah and Al Qaeda. Lindelauf, Hamers, Husslage
The above paper details very similar work with network graphs except with the alleged terrorists themselves instead of what unknown persons were saying. Having individual to individual connections allowed for importance and significance calculations to determine leaders and specialized groups within the larger operations. This type of analysis requires significant sensitive data we did not have access to.
Visualizing criminal networks reconstructed from mobile phone records. Ferrara, De Meo, Fiumara, Catanese
The second listed paper also did similar work as the first, but they also used the geographical location information usually associated with social network postings to locate groups of criminal activity and therefor where to focus police investigations. Having access to geographical locations with suspected criminals is sensitive data we also did not have access to.
Helping Intelligence Analyst make Connections. Hossian, Andrews, Ramakrishnan, North
Virginia Tech's department of Computer Science published the above paper where they explained how they tried to make connections between seemingly unconnected documents, words, or phases, to compile evidence fragments to construct a story to help intelligence agencies solve and prevent crimes.
Additional References
2. http://www.latimes.com/opinion/op-ed/la-oe-0417-gerges-islamic-state-theorists-20160417-story.html
Conclusion
Even with the drawbacks listed above, our results show that it is possible to detect malicious phrases in tweets. This technique could be applied to larger data sets and to all manner of social media using even more advanced techniques than the ones here, possibly employing online learning methods to streams of tweets so real-time threat detection could be employed. Relationships between words and phases identified has suspicious can be represented graphically to show and find relationships among them that may not have been obvious otherwise.