Graph-Based Network Anomaly Detection

• Activity Number: 494
• Type: Invited
• Date/Time: Wednesday, August 4, 2010 : 10:30 AM to 12:20 PM
• Sponsor: Section on Statistics in Defense and National Security
• Author(s): Joshua Charles Neil*+ and Mike Fisk and Curtis Storlie and Alexander Brugh
• Companies: Los Alamos National Laboratory and Los Alamos National Laboratory and University of New Mexico and Los Alamos National Laboratory
• Keywords: Anomaly Detection ; Computer Networks ; Cyber Security ; Graph ; Stochastic Models ; Scan Statistics

Abstract

Network anomaly detection is a vital aspect of modern computer security. To this end, engineers at Los Alamos National Laboratory have installed sensors on the network to collect an enormous amount of data on usage. A key aspect of this type of data is that it can be described using graphs. To accomplish anomaly detection, first we use stochastic processes to model the edges of the graph. Next, we use methods borrowed from scan statistics to combine anomaly scores from edges in a neighborhood. We then use this technique to locate neighborhoods and paths in the network which are least likely to occur under normal conditions. This results in a more robust system than host-based detection, where the connections between hosts are ignored. In addition, it more accurately reflects the behavior of attackers, who tend to explore local areas in the graph, producing anomalous neighborhoods.