Anomaly Detection : A Survey

This post is summary of the “Anomaly Detection : A Survey”. Anomaly detection refers to the problem of finding patterns in data that do not conform to expected behavior. These non-conforming patterns are often referred to as anomalies, outliers, discordant observations, exceptions, aberrations, surprises, peculiarities or contaminants in different application domains.

Anomalies are patterns in data that do not conform to a well defined notion of normal behavior.

Interesting to analyze
Unwanted noise in the data also can be found in there.
Novelty detection which aims at detecting previously unobserved (emergent, novel) patterns in the data

Challenges for Anomaly Detection

Drawing the boundary between normal and anomalous behavior
Availability of labeled data
Noisy data

Type of Anomaly
Anomalies can be classified into following three categories

Point Anomalies - An individual data instance can be considered as anomalous with respect to the rest of data
Contextual Anomalies - A data instance is anomalous in a specific context (but not otherwise), then it is termed as a contextual anomaly (also referred as conditional anomaly). Each data instance is defined using following two sets of attributes

Contextual attributes. The contextual attributes are used to determine the context (or neighborhood) for that instance
eg:
In time- series data, time is a contextual attribute which determines the position of an instance on the entire sequence
Behavioral attributes. The behavioral attributes define the non-contextual characteristics of an instance
eg:
In a spatial data set describing the average rainfall of the entire world, the amount of rainfall at any location is a behavioral attribute

To explain this we will look into "Exchange Rate History For Converting United States Dollar (USD) to Sri Lankan Rupee (LKR)"[1]

Contextual anomaly t2 in a exchange rate time series. Note that the exchange rate at time t1 is same as that at time t2 but occurs in a different context and hence is not considered as an anomaly
3. Collective Anomalies - A collection of related data instances is anomalous with respect to the entire data set

Data Labels
The labels associated with a data instance denote if that instance is normal or anomalous. Depending labels availability, anomaly detection techniques can be operated in one of the following three modes

Supervised anomaly detection - Techniques trained in supervised mode assume the availability of a training data set which has labeled instances for normal as well as anomaly class
Semi-Supervised anomaly detection - Techniques that operate in a semi-supervised mode, assume that the training data has labeled instances for only the normal class. Since they do not require labels for the anomaly class
Unsupervised anomaly detection - Techniques that operate in unsupervised mode do not require training data, and thus are most widely applicable. The techniques implicit assume that normal instances are far more frequent than anomalies in the test data. If this assumption is not true then such techniques suffer from high false alarm rate

Output of Anomaly Detection
Anomaly detection have two types of output techniques

Scores. Scoring techniques assign an anomaly score to each instance in the test data depending on the degree to which that instance is considered an anomaly
Labels. Techniques in this category assign a label (normal or anomalous) to each test instance

Applications of Anomaly Detection
Intrusion detection
Intrusion detection refers to detection of malicious activity. The key challenge for anomaly detection in this domain is the huge volume of data. Thus, semi-supervised and unsupervised anomaly detection techniques are preferred in this domain.Denning[3] classifies intrusion detection systems into host based and net-
work based intrusion detection systems.

Host Based Intrusion Detection Systems - This deals with operating system call traces
Network Intrusion Detection Systems - These systems deal with detecting intrusions in network data. The intrusions typically occur as anomalous patterns (point anomalies) though certain techniques model[4] the data in a sequential fashion and detect anomalous subsequences (collective anomalies). A challenge faced by anomaly detection techniques in this domain is that the nature of anomalies keeps changing over time as the intruders adapt their network attacks to evade the existing intrusion detection solutions.

Fraud Detection

Fraud detection refers to detection of criminal activities occurring in commercial organizations such as banks, credit card companies, insurance agencies, cell phone companies, stock market, etc. The organizations are interested in immediate detection of such frauds to prevent economic losses. Detection techniques used for credit card fraud and network intrusion detection as below.

Statistical Profiling using Histograms
Parametric Statistical Modeling
Non-parametric Statistical Modeling Bayesian Networks
Neural Networks
Support Vector Machines
Rule-based
Clustering Based
Nearest Neighbor based
Spectral
Information Theoretic

Here are some domain in fraud detections

Credit Card Fraud Detection
Mobile Phone Fraud Detection
Insurance Claim Fraud Detection
Insider Trading Detection

Medical and Public Health Anomaly Detection
Anomaly detection in the medical and public health domains typically work with pa- tient records. The data can have anomalies due to several reasons such as abnormal patient condition or instrumentation errors or recording errors. Thus the anomaly detection is a very critical problem in this domain and requires high degree of accuracy.
Industrial Damage Detection
Such damages need to be detected early to prevent further escalation and losses.
Fault Detection in Mechanical Units
Structural Defect Detection
Image Processing
Anomaly detection techniques dealing with images are either interested in any changes in an image over time (motion detection) or in regions which appear ab- normal on the static image. This domain includes satellite imagery.
Anomaly Detection in Text Data
Anomaly detection techniques in this domain primarily detect novel topics or events or news stories in a collection of documents or news articles. The anomalies are caused due to a new interesting event or an anomalous topic.
Sensor Networks
Since the sensor data collected from various wireless sensors has several unique characteristics.

References
[1] http://themoneyconverter.com/USD/LKR.aspx
[2] Varun Chandola, Arindam Banerjee, and Vipin Kumar. 2009. Anomaly detection: A survey. ACM Comput. Surv. 41, 3, Article 15 (July 2009), 58 pages. DOI=10.1145/1541880.1541882 http://doi.acm.org/10.1145/1541880.1541882
[3] Denning, D. E. 1987. An intrusion detection model. IEEE Transactions of Software Engineer-ing 13, 2, 222–232.
[4]Gwadera, R., Atallah, M. J., and Szpankowski, W. 2004. Detection of significant sets of episodes in event sequences. In Proceedings of the Fourth IEEE International Conference on Data Mining. IEEE Computer Society, Washington, DC, USA, 3–10.

We used have Singleton Design Pattern in our applications whenever it is needed. As we know that in singleton design pattern we can create only one instance and can access in the whole application. But in some cases, it will break the singleton behavior.

There are mainly 3 concepts which can break singleton property of a singleton class in java. In this post, we will discuss how it can break and how to prevent those.

Here is sample Singleton class and SingletonTest class.

Singleton.Java

package demo1;

public final class Singleton {

    private static volatile Singleton instance = null;

    private Singleton() {
    }

    public static Singleton getInstance() {
        if (instance == null) {
            synchronized (Singleton.class) {
                if (instance == null) {
                    instance = new Singleton();
                }
            }
        }
        return instance;
    }
}

SingletonTest.java

package demo1;

public class SingletonTest {
    public static void main(String[] args) {
        Singleton object1 = Singleton.getInstance();
        Singleton object2 = Singleton.getInstance();
        System.out.println("Hashcode of Object 1 - " + object1.hashCode());
        System.out.println("Hashcode of Object 2 - " + object2.hashCode());
    }
}

Here is output, you can see it the same hashcode for objectOne and objectTwo

Hashcode of Object 1 - 1836019240
Hashcode of Object 2 - 1836019240

Now we will break this pattern. First, we will use java reflection.

Reflection

Java Reflection is an API which is used to examine or modify the behavior of methods, classes, interfaces at runtime. Using Reflection API we can create multiple objects in singleton class. Consider the following example.

ReflectionSingleton.java

package demo1;

import java.lang.reflect.Constructor;

public class ReflectionSingleton {
    public static void main(String[] args)  {

        Singleton objOne = Singleton.getInstance();
        Singleton objTwo = null;
        try {
            Constructor constructor = Singleton.class.getDeclaredConstructor();
            constructor.setAccessible(true);
            objTwo = (Singleton) constructor.newInstance();
        } catch (Exception ex) {
            System.out.println(ex);
        }

        System.out.println("Hashcode of Object 1 - "+objOne.hashCode());
        System.out.println("Hashcode of Object 2 - "+objTwo.hashCode());

    }
}

Example to show how reflection can break the singleton pattern with Java reflect. You will get two hash code as below. It has a break on the singleton pattern.

Hashcode of Object 1 - 1836019240
Hashcode of Object 2 - 325040804

Prevent Singleton pattern from Reflection

There are many ways to prevent Singleton pattern from Reflection API, but one of the best solutions is to throw run time exception in the constructor if the instance already exists. In this, we can not able to create a second instance.

    private Singleton() {
        if( instance != null ) {
           throw new InstantiationError( "Creating of this object is not allowed." );
        }
    }

Deserialization

In serialization, we can save the object of a byte stream into a file or send over a network. Suppose if you serialize the Singleton class and then again de-serialize that object will create a new instance, hence deserialization will break the Singleton pattern.

Below code is to illustrate how the Singleton pattern breaks with deserialization.

Implements Serializable interface for Singleton Class.

DeserializationSingleton.Java

package demo1;

import java.io.*;

public class DeserializationSingleton {

    public static void main(String[] args) throws Exception {

        Singleton instanceOne = Singleton.getInstance();
        ObjectOutput out = new ObjectOutputStream(new FileOutputStream("file.text"));
        out.writeObject(instanceOne);
        out.close();

        ObjectInput in = new ObjectInputStream(new FileInputStream("file.text"));
        Singleton instanceTwo = (Singleton) in.readObject();
        in.close();

        System.out.println("hashCode of instance 1 is - " + instanceOne.hashCode());
        System.out.println("hashCode of instance 2 is - " + instanceTwo.hashCode());
    }

}

The output is below and you can see two hashcodes.

hashCode of instance 1 is - 2125039532
hashCode of instance 2 is - 381259350

Prevent Singleton Pattern from Deserialization

To overcome this issue, we need to override readResolve() method in Singleton class and return same Singleton instance. Update Singleton.java, with below method.

   protected Object readResolve() { 
           return instance; 
     }

Now run above DeserializationDemo class and see the output.

hashCode of instance 1 is - 2125039532
hashCode of instance 2 is - 2125039532

Cloning

Using the "clone" method we can create a copy of original object, samething if we applied clone in singleton pattern, it will create two instances one original and another one cloned object. In this case will break Singleton principle as shown in below code.

Implement the "Cloneable" interface and override the clone method in the above Singleton class.

Singleton.java

    @Override
    protected Object clone() throws CloneNotSupportedException  {
        return super.clone();
    }

Then Test with cloning for breaking the singleton
CloningSingleton.java

public class CloningSingleton {
    public static void main(String[] args) throws CloneNotSupportedException, Exception {
        Singleton instanceOne = Singleton.getInstance();
        Singleton instanceTwo = (Singleton) instanceOne.clone();
        System.out.println("hashCode of instance 1 - " + instanceOne.hashCode());
        System.out.println("hashCode of instance 2 - " + instanceTwo.hashCode());
    }

}

Here is the output

hashCode of instance 1 - 1836019240
hashCode of instance 2 - 325040804

If we see the above output, two instances have different hashcodes means these instances are not the same.

Prevent Singleton Pattern from Cloning

In the above code, breaks the Singleton principle i. e created two instances. To overcome the above issue we need to implement/override clone() method and throw an exception CloneNotSupportedException from clone method. If anyone try to create clone object of Singleton, it will throw an exception as see below code.

    @Override
    protected Object clone() throws CloneNotSupportedException  {
        throw new CloneNotSupportedException();
    }

Now we can run the CloningSingleton class, it will throw CloneNotSupportedException while creating a clone object of Singleton object.

Add a comment

Madhuka

Microservices, Java, DevOps, WSO2, Enterprise Solution, Enterprise Integration, SOA, EDA, Restful, C#, C++ tutorial, Ruby on rails, API Manager, jaggery, javascript, Madhuka

Reflection

Deserialization

Cloning

View comments