A large amount of data now being transferred through networks has made deep packet inspection (DPI) an essential part of security activities. Several DPI systems are developed based on Bloom filters to defend against malicious worm attacks through the Internet. These approaches have achieved significant performance. However, they do not permit deletion of items from the set of target patterns. This study proposes two multiple pattern matching schemes for DPI to exploit high parallelism capacity of graphics processing units (GPUs). Firstly, a GPU-based Cuckoo filter scheme is proposed by adopting a new approximate set membership, called Cuckoo filter, for parallel multiple pattern matching. The Cuckoo filter has many advantages over the Bloom filter such as higher insert performance, higher lookup throughput, less memory consumption, less false positive rate, and delete operation support. Secondly, an implementation of the GPU-based Cuckoo filter, called GPUshared-based Cuckoo filter is proposed. This scheme can efficiently distribute input string and pre-processing data in the hierarchical memory of GPUs to optimise the performance of the GPU-based Cuckoo filter scheme. Experiments show that the proposed schemes offer better performance than the previous approaches based on the Bloom filter.

References

1. 1)
  - 33. DEFCON: Available at: https://media.defcon.org, accessed 28 May 2017.
2. 2)
  - 23. Lin, C.-H., Liu, C.-H., Chien, L.-S., et al: ‘Accelerating pattern matching using a novel parallel algorithm on GPUs’, IEEE Trans. Comput., 2013, 62, (10), pp. 1906–1916.
3. 3)
  - 38. Ho, T., Oh, S.-R., Kim, H.: ‘New algorithms for fixed-length approximate string matching and approximate circular string matching under the hamming distance’, J. Supercomput., 2017, https://doi.org/10.1007/s11227-017-2192-6.
4. 4)
  - 14. Yun, S.K.: ‘An efficient TCAM-based implementation of multipattern matching using covered state encoding’, IEEE Trans. Comput., 2012, 61, (2), pp. 213–221.
5. 5)
  - 1. Bijone, M.: ‘A survey on secure network: intrusion detection & prevention approaches’, Am. J. Inf. Syst., 2016, 4, (3), pp. 69–88.
6. 6)
  - 27. Peng, J., Chen, H., Shi, S.: ‘The GPU-based string matching system in advanced AC algorithm’. Proc. 10th IEEE Int. Conf. on Computer and Information Technology (CIT), 2010, pp. 1158–1163.
7. 7)
  - 22. Zha, X., Sahni, S.: ‘Multipattern string matching on a GPU’. Proc. IEEE Symp. on Computers and Communications (ISCC), 2011, pp. 277–282.
8. 8)
  - 8. Antonatos, S., Anagnostakis, K.G., Markatos, E.P.: ‘Generating realistic workloads for network intrusion detection systems’, ACM SIGSOFT Softw. Eng. Notes, 2004, 29, pp. 207–215.
9. 9)
  - 7. Hung, C.-L., Lin, C.-Y., Wang, H.-H.: ‘An efficient parallel-network packet pattern-matching approach using GPUs’, J. Syst. Archit., 2014, 60, (5), pp. 431–439.
10. 10)
  - 15. Dharmapurikar, S., Attig, M., Lockwood, J.: ‘Design and implementation of a string matching system for network intrusion detection using FPGA-based bloom filters’, 2004.
11. 11)
  - 41. Jenkins, B.: ‘A new hash function for hash table lookup’, http://www.burtleburtle.net/bob/hash/doobs.html, accessed 28th May 2017.
12. 12)
  - 21. Vasiliadis, G., Antonatos, S., Polychronakis, M., et al: ‘Gnort: high performance network intrusion detection using graphics processors’. Int. Workshop on Recent Advances in Intrusion Detection, 2008, pp. 116–134.
13. 13)
  - 18. Kim, H., Choi, K.-I.: ‘A pipelined non-deterministic finite automaton-based string matching scheme using merged state transitions in an FPGA’, PLoS One, 2016, 11, (10), p. e0163535.
14. 14)
  - 10. Boyer, R.S., Strother Moore, J.: ‘A fast string searching algorithm’, Commun. ACM, 1977, 20, (10), pp. 762–772.
15. 15)
  - 32. Al-hisnawi, M., Ahmadi, M.: ‘Deep packet inspection using cuckoo filter’. 2017 Annual Conf. on New Trends in Information & Communications Technology Applications (NTICT), 2017, pp. 197–202.
16. 16)
  - 17. Kim, H., Lee, S.-W.: ‘A hardware-based string matching using state transition compression for deep packet inspection’, ETRI J., 2013, 35, (1), pp. 154–157.
17. 17)
  - 28. Tran, N.-P., Lee, M., Hong, S., et al: ‘Memory efficient parallelization for Aho–Corasick algorithm on a GPU’. Proc. 14th IEEE Int. Conf. on Embedded Software and Systems (HPCC-ICESS)E, 2012, pp. 432–438.
18. 18)
  - 3. Martin, R.: ‘Snort: lightweight intrusion detection for networks’. Proc. 13th Large Installation System Administration Conf. (LISA), 1999, vol. 99, pp. 229–238.
19. 19)
  - 12. Alicherry, M., Muthuprasanna, M., Kumar, V.: ‘High speed pattern matching for network IDS/IPS’. Proc. 14th IEEE Int. Conf. on Network Protocols, 2006. ICNP'06., 2006, pp. 187–196.
20. 20)
  - 37. Pagh, R., Rodler, F.F.: ‘Cuckoo hashing’, J. Algorithms, 2004, 51, (2), pp. 122–144.
21. 21)
  - 29. Fan, B., Andersen, D.G., Kaminsky, M., et al: ‘Practically better than bloom’. Proc. 10th ACM Int. Conf. on Emerging Networking Experiments and Technologies, 2014, pp. 75–88.
22. 22)
  - 11. Aho, A.V., Corasick, M.J.: ‘Efficient string matching: an aid to bibliographic search’, Commun. ACM, 1975, 18, (6), pp. 333–340.
23. 23)
  - 5. Ho, T., Oh, S.-R., Kim, H.: ‘PAC-k: a parallel Aho–Corasick string matching approach on graphic processing units using non-overlapped threads’, IEICE Trans. Commun., 2016, 99, (7), pp. 1523–1531.
24. 24)
  - 16. Irwin, S.G., Venkat, A.A., Winberg, S.L., et al: ‘FPGA-based string matching’. 2011 Int. Conf. on Energy, Automation, and Signal (ICEAS), 2011, pp. 1–4.
25. 25)
  - 36. Attig, M., Dharmapurikar, S., Lockwood, J.: ‘Implementation results of bloom filters for string matching’. 12th Annual IEEE Symp. on Field-Programmable Custom Computing Machines, 2004 (FCCM 2004), 2004, pp. 322–323.
26. 26)
  - 13. Kim, J., Choi, S.-i.: ‘High speed pattern matching for deep packet inspection’. 9th Int. Symp. on Communications and Information Technology, 2009. ISCIT 2009., 2009, pp. 1310–1315.
27. 27)
  - 39. Ramakrishna, M.V., Zobel, J.: ‘Performance in practice of string hashing functions’. Database Systems for Advanced Applications (DASFAA), 1997, pp. 215–224.
28. 28)
  - 4. Paxson, V.: ‘Bro: a system for detecting network intruders in real-time’, Comput. Netw., 1999, 31, (23), pp. 2435–2463.
29. 29)
  - 6. Al-Hisnawi, M., Ahmadi, M.: ‘Deep packet inspection using quotient filter’, IEEE Commun. Lett., 2016, 20, (11), pp. 2217–2220.
30. 30)
  - 30. Gupta, V., Breitinger, F.: ‘How cuckoo filter can improve existing approximate matching techniques’. Int. Conf. on Digital Forensics and Cyber Crime, 2015, pp. 39–52.
31. 31)
  - 34. Bloom, B.H.: ‘Space/time trade-offs in hash coding with allowable errors’, Commun. ACM, 1970, 13, (7), pp. 422–426.
32. 32)
  - 26. Ho, T., Oh, S.-R., Kim, H.: ‘A parallel approximate string matching under Levenshtein distance on graphics processing units using warp-shuffle operations’, PLoS One, 2017, 12, (10), p. e0186251.
33. 33)
  - 35. Dharmapurikar, S., Krishnamurthy, P., Sproull, T., et al: ‘Deep packet inspection using parallel bloom filters’. Proc. 11th IEEE Symp. on High Performance Interconnects, 2003, 2003, pp. 44–51.
34. 34)
  - 19. Yu, J., Li, J.: ‘A parallel NIDS pattern matching engine and its implementation on network processor’. Security and Management, 2005, pp. 375–384.
35. 35)
  - 40. Enbody, R.J., Du, H.C.: ‘Dynamic hashing schemes’, ACM Comput. Surv., 1988, 20, (2), pp. 85–113.
36. 36)
  - 25. Kouzinopoulos, C.S., Assael, J.-A.M., Pyrgiotis, T.K., et al: ‘A hybrid parallel implementation of the Aho–Corasick and Wu–Manber algorithms using NVIDIA CUDA and MPI evaluated on a biological sequence database’, Int. J. Artif. Intell. Tools, 2015, 24, (01), p. 1540001.
37. 37)
  - 20. Arudchutha, S., Nishanthy, T., Ragel, R.G.: ‘String matching with multi-core CPUs: performing better with the Aho–Corasick algorithm’. 2013 8th IEEE Int. Conf. on Industrial and Information Systems (ICIIS), 2013, pp. 231–236.
38. 38)
  - 42. NVIDIA. GeForce GTX 660: Available at: http://www.geforce.com/hardware/desktop-gpus/geforce-gtx-660, accessed 28 May 2017.
39. 39)
  - 43. Intel. Xeon CPU E31270: Available at: http://ark.intel.com/products/52276/Intel-Xeon-Processor-E3-1270-8M-Cache-3_40-GHz, accessed 28 May 2017.
40. 40)
  - 24. Soroushnia, S., Daneshtalab, M., Plosila, J., et al: ‘Heterogeneous parallelization of Aho–Corasick algorithm’. Proc. 8th Int. Conf. on Practical Applications of Computational Biology & Bioinformatics (PACBB 2014), 2014, pp. 153–160.
41. 41)
  - 2. Hung, C.-L., Lin, C.-Y., Wu, P.-C.: ‘An efficient GPU-based multiple pattern matching algorithm for packet filtering’, J. Signal Process. Syst., 2017, 86, (2-3), pp. 347–358.
42. 42)
  - 9. Knuth, D.E., Morris, J.H., Pratt, V.R.: ‘Fast pattern matching in strings’, SIAM J. Comput., 1977, 6, (2), pp. 323–350.
43. 43)
  - 31. Eppstein, D.: ‘Cuckoo filter: simplification and analysis’. 15th Scandinavian Symp. and Workshops on Algorithm Theory, 2016, p. 1.

Parallel multiple pattern matching schemes based on cuckoo filter for deep packet inspection on graphics processing units

References

Related content