The goal of this project is to make graph-based security analytics practical and robust. General-purpose graph algorithms and graph-based machine learning methods have had some success when applied to a number of security problems ranging from detecting malicious websites and compromised devices in computer networks to detecting compromised or inauthentic accounts in social networks. However, because the existing methods are designed for generic contexts rather than for specific security problems, there is room to improve their performance in detecting bad actors in networks. Further, in security contexts, there is often a determined adversary trying to evade detection that general-purpose algorithms are not designed to consider, which makes them vulnerable to attack. This project will develop novel graph inference algorithms that consider unique characteristics of security problems, analyze the spectrum of possible attacks on such algorithms, define measures of their robustness against attack, and develop methods to improve their robustness. The project team will create and share datasets related to graph-based security analytics along with software that implements their algorithms and robustness measures with both industrial practitioners and other researchers. They will also mentor undergraduate and graduate students in the research, using the problems and data to support new college courses and Science, Technology, Engineering, and Mathematics (STEM) outreach activities for K-12 students. The work focuses on collective classification algorithms that simultaneously label all nodes in a network as malicious or benign. The first main research thrust involves advancing analytic techniques that combine random walk and loopy belief propagation-based algorithms through local rules that model the joint probabilities of a given node and its neighbors being malicious. To do this, the team will develop versions of the algorithms that relax assumptions that neighboring nodes have strong homophily, developing characterizations of neighboring nodes' relationships and creating novel Markov Random Field formulations that leverage these characterizations. The second research thrust will model the attack surface of collective classification algorithms, characterizing the goals and capabilities of attackers, the cost of evasive moves such as creating nodes or edges and generating network activity, and the effect of different goals, capabilities, and levels of evasion on the algorithms' performance. The third thrust will be to develop methods to identify such evasion by developing attacker-resistant link prediction algorithms and similarity metrics, then mitigate evasion efforts through developing local rule-based techniques that add noise to graphs in ways that confound attacks. The team will evaluate the metrics and algorithms on datasets from a number of domains, including malicious users in social networks, malicious URLs in the web graph, malicious domains embedded in domain name service redirects, and malicious orders in an e-commerce marketplace. These problems, and the associated datasets, will be integrated into an existing course on data-driven security and a new graduate seminar course on collective classification. Results from all activities will be used as cases and materials in both existing and new courses, as well as a K-12 summer program and cybersecurity competition organized around detecting malicious actors in networks.
CAREER: Graph-Based Security Analytics: New Algorithms, Robustness under Adversarial Settings, and Robustness Enhancements