Detecting malicious logins as graph anomalies

Authenticated lateral movement via compromised accounts is a common adversarial maneuver that is challenging to discover with signature- or rules-based intrusion detection systems. In this work a behavior-based approach to detecting malicious logins to novel systems indicative of lateral movement is presented, in which a user's historical login activity is used to build a model of putative "normal" behavior. This historical login activity is represented as a collection of daily login graphs, which encode authentications among accessed systems. Each system, or graph vertex, is described by a set of graph centrality measures that characterize it and the local topology of its login graph. The unsupervised technique of non-negative matrix factorization is then applied to this set of features to assign each vertex to a role that summarizes how the system participates in logins. The reconstruction error quantifying how well each vertex fits into its role is then computed, and the statistics of this error can be used to identify outlier vertices that correspond to systems involved in unusual logins. We test this technique with a small cohort of privileged accounts using real login data from an operational enterprise network. The ability of the method to identify malicious logins among normal activity is tested with simulated graphs of login activity representative of adversarial lateral movement. We find that the method is generally successful at detecting a broad range of lateral movement for each user, with false positive rates significantly lower than those resulting from alerts based solely on login novelty.