Bitwise sketch for lightweight reverse IP reconstruction in network anomaly detection

Sketch is commonly used in network anomaly detection. However, its irreversibility seriously obstacle for identification of origin of traffic anomaly, such as attack flows. In this paper, we design a novel sketch structure, called Bitwise Sketch, with the ability of fast and lightweight reverse deduction. Bitwisebased hash function, which distributes keys (IPs) is Sketch, is adopted in bitwise sketch, instead of traditional universal hash function. We propose an IP reconstruction algorithm that can reversely infer anomalous keys (IP) from a set of anomalous buckets, with very low overhead. Simulation result shows the effectiveness of the algorithm¿s results in filtering attack traffic. Through theoretical analysis, we compare our approach with three resultant approaches, and our approach outperforms both in memory requirement and computational cost.