Identifying Abnormal Hosts in Data Streams Using Reversible Sketch

ABSTRACT Significant cardinality change is an important sign of the beginning of network attacks. Hosts associated with significant cardinality changes usually exhibit abnormal behavior. Identifying abnormal hosts is meaningful for many applications such as anomaly detection. High‐speed data streams remain a great challenge to accurately estimate cardinality changes and detect abnormal hosts in real‐time. Sketches are a type of probability data structure, which are widely used to compress high‐rate data streams and estimate their statistics. However, most existing studies cannot simultaneously measure two kinds of cardinality changes in a distributed manner and efficiently reconstruct addresses of abnormal hosts in a centralized manner because of high calculation and memory overhead. In this paper, we propose reversible sketch‐based abnormal host identification. It constructs a reversible data structure and estimates cardinality changes using a probabilistic counting approach, so that abnormal sources and destinations are simultaneously identified based on their cardinality changes between consecutive measurement periods. Moreover, addresses of abnormal hosts can be reconstructed by only simple inverse calculation to find out attackers and victims. The experimental results illustrate that the proposed approach obtains superior performance for cardinality change estimation and addresses of abnormal host reconstruction in accuracy and performance compared with the existing approaches.