Detection Framework

There are two basic components to the detection framework Morgoth employs.

  1. A Lossy Counting strategy for finding anomlous behavior.
  2. A fingerprinting mechanism to summarize/fingerprint behaviors.

At a high level Morgoth fingerprints each window of data it sees and keeps track of which fingerprints it has seen before and marks new/infrequent fingerprints as anomalous. The power of the framework is in which fingerprinting algorithms are used and in the simplicity of configuring how to count frequent fingerprints.

Lossy Counting

The Lossy Counting algorithm is a way of counting frequent items efficiently. The algorithm is lossy since it will drop infrequent items but does so in such a way that it can guarantee certain behaviors:

  1. There are no false negatives. The frequency of an item cannot be over estimated.
  2. False positives are guaranteed to have a frequency of at least mN-eN, where N is the number of items processed, m is the minimum support and e is the error tolerance.
  3. The frequency of an item can be underestimated by at most eN.
  4. The space requirements of the algorithm are 1/e log(eN).

These constraints allow the user to have intuitive control over what is considered an anomaly. For example #3 states that items can be underestimated by at most eN. What this means given an e = 0.10, items that are less than 10% frequent could be underestimated to have 0% frequency as a worst case. As result these items would get dropped from the algorithm and when they occur again will be marked as anomalies. By settings the error tolerance and minimum support one can control how lossy the counting alogorithm is for a given use case.

Notice that m > e, this is so that we reduce the number of false positives. For example say we set e = 5% and m = 5%. If a normal behavior X, has a true frequency of 6% than based on variations in the true frequency, X might fall below 5% for a small interval and be dropped. This will cause X's frequency to be underestimated, which will cause it to be flagged as an anomaly, since its estimated frequency falls below the minimum support. The anomaly is a false positive because its true frequency is greater then the minimum support. By setting e < m we have a buffer to help mitigate creating false positives.

What is considered anomalous?

The answer is simple; every time the Lossy Counting algorithm is given an fingerprint is checks to see how many times it has seen that fingerprint. If the fingerprint has a frequency less than the minimum support than it is considered anomalous.

Multiple Fingerprinters

A detector instance can have more than one fingerprinting algorithm. In this case an anomaly is determined via a consensus model or using the average support.

Consensus Model

Using a consensus model each fingerprinter votes for whether it thinks the window is ananomalous by comparing its support to the minimum support threshold. If the percentage of anomalous votes is greater than a specified consensus threshold than the window is considered anomalous.

Average Support Model

Alternatively the average support from each of the fingerprinters is compared against the minimum support threshold. If the average support is less than or equal to the minimum support than the window is considered anomalous. By using the average support of the fingerprinters you essentially get a weighted voting system where each fingerprinter instead of voting yes or no gets to vote with a value between 0-1. The average of the votes is then compared to the threshold.

Putting it all together

Each detector instance has five parameters:

  1. Minimum Support -- The minimum frequency a fingerprint must have in order to be considered normal.
  2. Error Tolerance -- Controls the maximum error that will be tolerated while counting fingerprints. Controls the resource usage of the algorithm.
  3. Consensus -- The percentage of fingerprinters that must agree in order to mark a window as anomalous. If the consensus is -1 then the average support model is used.
  4. Fingerprinters -- List of fingerprinters to be used by the detector.