  Intrusion detection system (IDS) is an important part of enterprise security
system architecture. In particular, anomaly-based IDS has been widely applied
to detect abnormal process behaviors that deviate from the majority. However,
such abnormal behavior usually consists of a series of low-level heterogeneous
events. The gap between the low-level events and the high-level abnormal
behaviors makes it hard to infer which single events are related to the real
abnormal activities, especially considering that there are massive "noisy"
low-level events happening in between. Hence, the existing work that focus on
detecting single entities/events can hardly achieve high detection accuracy.
Different from previous work, we design and implement GID, an efficient
graph-based intrusion detection technique that can identify abnormal event
sequences from a massive heterogeneous process traces with high accuracy. GID
first builds a compact graph structure to capture the interactions between
different system entities. The suspiciousness or anomaly score of process paths
is then measured by leveraging random walk technique to the constructed acyclic
directed graph. To eliminate the score bias from the path length, the Box-Cox
power transformation based approach is introduced to normalize the anomaly
scores so that the scores of paths of different lengths have the same
distribution. The efficiency of suspicious path discovery is further improved
by the proposed optimization scheme. We fully implement our GID algorithm and
deploy it into a real enterprise security system, and it greatly helps detect
the advanced threats, and optimize the incident response. Executing GID on
system monitoring datasets showing that GID is efficient (about 2 million
records per minute) and accurate (higher than 80% in terms of detection rate).
