Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Detecting superpoints through a reversible counting Bloom filter

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

Internet attacks such as distributed denial-of-service (DDoS) attacks and worm attacks are increasing in severity. Identifying realtime attack detection and mitigation of Internet traffic is an important and challenging problem. For example, a compromised host doing fast scanning for worm propagation often makes an unusually high number of connections to distinct destinations within a short time. We call such a host a superpoint, which are sources that connect to a large number of distinct destinations. Detecting superpoints is very important in developing effective and efficient traffic engineering schemes. We propose two novel schemes for detecting superpoints and prove guarantees on their accuracy and memory requirements. These schemes are implemented by introducing a reversible counting Bloom filter (RCBF), a special counting Bloom filter. The RCBF consists of 4 hash functions which projectively select some consecutive bits from original strings as function values. We obtain the information of superpoints using the overlapping of hash bit strings of the RCBF. The theoretical analysis and experiment results show that our schemes can precisely and efficiently detect superpoints.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. El-Atawy A, Al-Shaer E, Tran T, Boutaba R (2009) Adaptive early packet filtering for protecting firewalls against DoS attacks. In: IEEE INFOCOM 2009, April, pp 2437–2445

    Google Scholar 

  2. Moore D, Paxson V, Savage S, Shannon C, Staniford S, Weaver N (2003) Inside the slammer worm. Secur Privacy Mag 2(4):33–39

    Article  Google Scholar 

  3. Goodrich MT (2008) Probabilistic packet marking for large-scale IP traceback. IEEE/ACM Trans Netw 16(1):15–24

    Article  Google Scholar 

  4. Xiang Y, Zhou W, Guo M (2009) Flexible deterministic packet marking: an IP traceback system to find the real source of attacks. IEEE Trans Parallel Distrib Syst 20(4):567–580. doi:10.1109/TPDS.2008.132

    Article  Google Scholar 

  5. Roesch M (1999) Snort-lightweight intrusion detection for network. In: Proc USENIX systems administration conference, pp 228–238

    Google Scholar 

  6. Plonka D (2000) Flowscan: a network traffic flow reporting and visualization tool. In: USENIX LISA, pp 305–318

  7. Venkataraman S, Song D, Gibbons P, Blum A (2005) New streaming algorithms for fast detection of superspreaders. In: Proc NDSS, pp 149–166

    Google Scholar 

  8. Zhao Q, Kumar A, Jun X (2005) Joint data streaming and sampling techniques for detection of super sources and destinations. In: IMC 2005, pp 77–90

    Google Scholar 

  9. Kamiyama N, Mori T, Kawahara R (2007) Simple and adaptive identification of superspreaders by flow sampling. In: INFOCOM 2007, pp 2481–2485

    Google Scholar 

  10. Cheng G, Gong J, Ding W, Wu H, Qiang SQ (2008) Detecting superpoint algorithm based on adaptive samling. Sci China, E-Inf Sci 38(10):1679–1696

    Google Scholar 

  11. Guan X, Pinghui W, Qin T (2009) A new data streaming method for locating hosts with large connection degree. In: IEEE Globecom 2009, November, pp 1–6

    Google Scholar 

  12. Cao J, Jin Y, Chen A, Bu T, Zhang Z-L (2009) Identifying high cardinality internet hosts. In: IEEE INFOCOM 2009, April, pp 810–818

    Google Scholar 

  13. Claffy KC, Braun HW, Polyzos GC (1995) A parameterizable methodology for Internet traffic flow profiling. IEEE J Sel Areas Commun 13:1481–1494

    Article  Google Scholar 

  14. Jain R, Routhier SA (1986) Packet trains-measurements and a new model for computer network traffic. IEEE J Sel Areas Commun 4:986–995

    Article  Google Scholar 

  15. Kumar A, Sung M, Xu J, Wang J (2004) Data streaming algorithms for efficient and accurate estimation of flow size distribution. In: Proc ACM SIGMETRICS, pp 177–188

    Google Scholar 

  16. Cypress Semiconductor Corporation (2010). http://www.cypress.com/

  17. Cohen S, Matias Y (2003) Spectral Bloom filters. In: Proceedings of the ACM SIGMOD 2003, San Diego, CA, USA, pp 241–252

    Chapter  Google Scholar 

  18. WIDE (2010) http://tracer.csl.sony.co.jp/mawi/samplepoint-F/20090330/200903300000.html

  19. Ramakrishna MV (1989) Practical performance of Bloom filters and parallel free-text searching. Commun ACM 32(10):1237–1239

    Article  Google Scholar 

  20. JSLAB (2010) http://ntds.njnet.edu.cn/data/index.php

  21. NLANR (2010) ftp://wits.cs.waikato.ac.nz/pma/long/ipls/3/

Download references

Author information

Authors and Affiliations

  1. School of Information Science and Technology, Dalian Maritime University, Dalian, Liaoing, 116026, China

    Weijiang Liu, Wenyu Qu, Xiaona He & Zhaobin Liu

Authors
  1. Weijiang Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wenyu Qu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xiaona He
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Zhaobin Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wenyu Qu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Liu, W., Qu, W., He, X. et al. Detecting superpoints through a reversible counting Bloom filter. J Supercomput 63, 218–234 (2013). https://doi.org/10.1007/s11227-010-0511-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-010-0511-2

Keywords

Search

Navigation