Method of cyberthreat detection by learning first-order rules on large-scale social media

Inventors

Rao, Praveen • KAMHOUA, CHARLES • KWIAT, KEVIN • NJILLA, LAURENT

Assignees

United States Department of the Air Force

Abstract

A cyberthreat detection method and system includes a distributed file system and a commodity cluster. The commodity cluster has a plurality of servers. A data array of key-value pairs related to social media is received; it stores a plurality of predetermined ground predicates. A ground predicate graph is constructed for each user then partitioned into balanced portions Pi each corresponding to a server and the ground predicates stored on that server. In parallel on each server, a plurality of leaned rules are determined for the files stored on that server. From a union of the plurality of learned rules, the system determines a respective weight for each of the learned rules. The plurality of rules are ranked in order of accuracy by the plurality of weights.

Core Innovation

The invention provides a cyberthreat detection system and method that operates on large-scale social media data, specifically focusing on Twitter® posts. It employs first-order logic, probability theory, and graph theory, particularly using a commodity cluster with multiple servers and a distributed file system. Central to the innovation is the automatic learning of first-order rules from massive datasets by constructing ground predicate graphs for users, forming a user-centric graph with weighted vertices and edges representing relationships between users, partitioning this graph into balanced portions corresponding to servers, and then performing parallel rule learning on each partition. The learned rules from all partitions are combined, weighted, and ranked to identify the most relevant rules indicative of cyberthreats.

The problem addressed arises from the social and economic damage caused by cyber threats on social media platforms like Twitter®, including malicious postings, misinformation, and malware spread through malicious links. Prior approaches used handcrafted first-order logic rules in knowledge bases and probabilistic inference to detect suspicious users and malicious content. However, malicious users adapt and change behavior, and the volume of tweets grows exceedingly large, resulting in evolving and emerging new rules. Modeling and reasoning about the veracity of social media posts faces challenges due to the complex, noisy, and diverse tweet attributes and relationships among users. This necessitates a scalable automated method that can learn relevant first-order rules efficiently across large datasets and adapt to dynamic social media environments.

To solve these issues, the invention employs a divide-and-conquer strategy using a distributed commodity cluster. It constructs a user-centric graph that clusters ground predicates around users, defines edges based on social interactions such as mentions, friendships, follows, and retweets, and assigns weights to vertices and edges to capture social relationships. Parallel graph partitioning is applied to minimize cut edges and balance the partitions, enabling efficient distribution of data and processing across servers. On each partition, Markov Logic Network (MLN) structure learning algorithms identify probabilistic first-order logic rules, then MLN weight learning assigns weights to these rules. The method finally combines and ranks these rules through an objective function that multiplies and sums weights across partitions, enabling selection of the most relevant rules for cyberthreat detection. This approach drastically reduces processing time while maintaining accuracy in identifying suspicion and malicious behavior on large-scale social media data.

Claims Coverage

The patent contains three independent claims covering a system, a method, and a system for detecting suspicious social media activity, each incorporating a distributed file system, a commodity cluster, ground predicate construction, user-centric graph formation, partitioning, parallel learned rule generation, weight determination, and rule ranking.

The independent claims collectively disclose a distributed system and method that partition a user-centric graph derived from social media ground predicates, perform parallel learning of weighted first-order logic rules using MLN techniques, and rank these rules to detect cyberthreats on social media efficiently and accurately.

Stated Advantages

Documented Applications