There are two basic components to the detection framework Morgoth employs.
- A Lossy Counting strategy for finding anomlous behavior.
- 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.
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:
- There are no false negatives. The frequency of an item cannot be over estimated.
- False positives are guaranteed to have a frequency of at least
Nis the number of items processed,
mis the minimum support and
eis the error tolerance.
- The frequency of an item can be underestimated by at most
- The space requirements of the algorithm are
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
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.
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
The anomaly is a false positive because its true frequency is greater then the
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.
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.
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:
Minimum Support-- The minimum frequency a fingerprint must have in order to be considered normal.
Error Tolerance-- Controls the maximum error that will be tolerated while counting fingerprints. Controls the resource usage of the algorithm.
Consensus-- The percentage of fingerprinters that must agree in order to mark a window as anomalous. If the consensus is
-1then the average support model is used.
Fingerprinters-- List of fingerprinters to be used by the detector.