基于并行Bloom过滤器组的深度数据包检测算法

针对基于软件、硬件的深度数据包检测存在处理速度慢或规则集更新困难等方面的局限性,提出一种在多核平台上基于并行Bloom过滤器组的深度数据包检测算法。算法中首先将规则集按规则的长度分组,构造一个并行Bloom过滤器组,组中每个计数式 Bloom过滤器表示特定规则长度的规则集。为了减少执行过程中的冲突概率和计算量,构造了高性能的哈希函数,然后基于多核平台的并行处理能力使用并行编程实现了该算法。理论分析和实验结果表明该算法是一种时空高效的算法。     

基于正则表达式的深度包检测算法

在深入分析了DFA状态数对算法性能影响的基础上,提出了一种新的基于正则表达式的深度包检测算法,该算法保证在任意有限的系统资源下算法的时间复杂度空间复杂度最小。在Linux下实现了该算法,并对基于L7-filter模式集合的网络数据包进行了大量检测实验。结果表明,与已有的正则表达式算法比较,该算法的时间复杂度和空降复杂度最小。     

双布鲁姆过滤器法查询集合成员

探讨双布鲁姆过滤器查询法查询集合并集、交集、补集、差集或对称差成员的性能问题。理论分析和实验结果表明,双布鲁姆过滤器查询法能够较好地支持集合并集、交集、补集、差集及对称差的成员查询问题,其中双布鲁姆过滤器并集及交集查询不会产生假阴性,仅有少量假阳性的存在,而双布鲁姆过滤器补集、差集及对称差查询则除存在少量假阳性外,还存在少量假阴性。     

Fast and deterministic hash table lookup using discriminative bloom filters

Hash tables are widely used in network applications, as they can achieve O(1) query, insert, and delete operations at moderate loads. However, at high loads, collisions are prevalent in the table, which increases the access time and induces non-deterministic performance. Slow rates and non-determinism can considerably hurt the performance and scalability of hash tables in the multi-threaded parallel systems such as ASIC/FPGA and multi-core. So it is critical to keep the hash operations faster and more deterministic.This paper presents a novel fast collision-free hashing scheme using Discriminative Bloom Filters (DBFs) to achieve fast and deterministic hash table lookup. DBF is a compact summary stored in on-chip memory. It is composed of an array of parallel Bloom filters organized by the discriminator. Each element lookup performs parallel membership checks on the on-chip DBF to produce a possible discriminator value. Then, the element plus the discriminator value is hashed to a possible bucket in an off-chip hash table for validating the match. This DBF-based scheme requires one off-chip memory access per lookup as well as less off-chip memory usage. Experiments show that our scheme achieves up to 8.5-fold reduction in the number of off-chip memory accesses per lookup than previous schemes.     

Deep packet inspection tools and techniques in commodity platforms: Challenges and trends

Deep packet inspection (DPI) helps Internet service providers in efforts to profile networked applications. By relying on DPI systems, Internet service providers may apply different charging policies, traffic shaping, or offer quality of service (QoS) guarantees to selected users or applications. As critical network services rely on the precise characterization of network flows, building agile and efficient DPI systems has recently become an important research topic. In this paper, we present a comprehensive literature review on the tools and techniques necessary to develop modern DPI systems. We provide the essential technical background material and examine the current body of research in DPI engines’ optimization for commodity platforms. Then we discuss current research challenges and present guidelines for building high performance DPI systems.     

一种改进的XFA在深度包检测中的应用

提出了一种应用于深度包检测的改进XFA。该算法在XFA的分支迁移边上添加判断指令,消除XFA存在冗余迁移边的问题;采用并行检测机制,将匹配线程升级为两个并行的线程,预统计线程和状态机匹配线程,加快匹配速度。实验验证该算法有更快的运行速度和稳定性,适合多核计算环境。     

并行分组交换研究综述

随着链路速率和存储器速率发展差距的日益增大,并行分组交换逐渐成为构建高速交换系统的一种流行方案.在给出了并行分组交换的基本结构和相关定义的基础上,对近年来国内外并行分组交换的研究方法和技术进行了阐述,包括高速率大容量并行分组交换研究、支持服务质量保证的并行分组交换研究和支持组播的并行分组交换研究.通过分析对比各种已有研究的优缺点,对并行分组交换的下一步研究方向进行了展望.     

A parallel computational approach for similarity search using Bloom filters

Finding similar items in a large and unstructured dataset is a challenging task in many applications of data science, such as searching, indexing, and retrieval. With the increasing data volume and demand for real time responses, similarity search has gained much consideration. In this paper, a parallel computational approach for similarity search using Bloom filters (PCASSB) has been proposed, which uses Bloom filter for the representation of features of document and comparison with user's query. Query features are stored in integer query array (^IQ_A), an array of integer. The PCASSB, an approximate similarity search technique, has been implemented on graphics processing unit with compute unified device architecture as the programming platform. To compute the similarity score between query and reference dataset, Dice coefficient has been used as a baseline method. The accuracy of the results generated by PCASSB is compared with the baseline method and other state‐of‐the‐art methods. The experimental results show that the proposed technique is quite effective in processing large number of text documents as it takes less computational time.     

Power efficient packet classification using cascaded bloom filter and off-the-shelf ternary CAM for WDM networks

In wavelength division multiplexing (WDM) networks, tens or hundreds of wavelengths can be transmitted over a single fiber. As transmission line speed goes to 10 Gb/s and beyond, ternary CAM (TCAM) is usually employed for wire speed packet classification. To the best of authors’ knowledge, this is the first paper that addresses the impact of WDM transmission on the power consumption of packet classification. We show that as the number of wavelengths increases in the WDM networks, the power consumption of TCAMs can become the limiting factor for WDM network expansion. For example, the power consumption of IPv4 and IPv6 packet classification with merely 32 channels at 40 Gb/s can be as high as 700 and 1400 W, respectively, while technology wise it is feasible to transmit over 500 channels over a single fiber. Existing power efficient TCAM designs require special modification to TCAM cell structures, which makes the adoption of the technology difficult. This paper proposes a novel approach which cascades bloom filter with off-the-shelf TCAM to greatly reduce the power consumption of packet classification. In particular, the proposed solution takes advantage of the fact that bloom filters may give false positive alarms but never give false negative alarms. By eliminating majority of non-matching packets before passing the packets to the TCAM, the TCAM is only activated to exam packets with a high potential of matching in the filter set. The proposed scheme greatly reduces the activation frequency of the TCAM, thus achieving great power savings.     

基于多维布隆过滤器的模式匹配引擎

针对传统的模式匹配引擎不具备完整报文检测功能的问题和出现的速度瓶颈,提出了基于FPGA实现的多维布隆过滤器解决方案,设计了能够同时检测报头和有效负载的多模式匹配引擎。引擎使用多维布隆过滤器过滤出可疑报文,由位拆分状态机进行精确匹配。分析和试验结果表明：与传统方法相比,基于多维布隆过滤器的模式匹配引擎可以并行检测报头和报文内容,在降低过滤器误判率的同时,有效提高了引擎的吞吐量。     

Preserving privacy in association rule mining with bloom filters

Privacy preserving association rule mining has been an active research area since recently. To this problem, there have been two different approaches—perturbation based and secure multiparty computation based. One drawback of the perturbation based approach is that it cannot always fully preserve individual’s privacy while achieving precision of mining results. The secure multiparty computation based approach works only for distributed environment and needs sophisticated protocols, which constrains its practical usage. In this paper, we propose a new approach for preserving privacy in association rule mining. The main idea is to use keyed Bloom filters to represent transactions as well as data items. The proposed approach can fully preserve privacy while maintaining the precision of mining results. The tradeoff between mining precision and storage requirement is investigated. We also propose δ-folding technique to further reduce the storage requirement without sacrificing mining precision and running time.     

一种面向深度包检测的DFA压缩算法

DFA (确定性有限自动机)对于实现深度包检测（deep packet inspection, DPI）技术具有重要作用。随着深度包检测规则的不断增多,DFA所需的存储空间急剧增大。为此,本文提出了一种基于字符替换的DFA压缩算法,利用状态转换表中每个状态通常只有少数几个不同跳转的特点,我们将状态转换表分解为剩余表和字符替换表,减少了存储空间。此外,通过使相似的状态可以共享相同的字符替换表以进一步压缩存储空间。最后,本文给出了复杂度为O(n2)的压缩算法,n为DFA的状态数。实验结果表明,该算法在L7-filter和Snort规则集上具有较稳定的压缩率,压缩率都在5%以下。     

Improved deep packet inspection in data stream detection

The Journal of Supercomputing - Finite state automata are widely used in firewalls, data detection and content audit systems to match complex sets of regular expressions in network packets....     

An index-split Bloom filter for deep packet inspection

Deep packet inspection(DPI)scans both packet headers and payloads to search for predefined signatures.As link rates and traffc volumes of Internet are constantly growing,DPI is facing the high performance challenge of how to achieve line-speed packet processing with limited embedded memory.The recent trie bitmap content analyzer(TriBiCa)suffers from high update overhead and many false positive memory accesses,while the shared-node fast hash table(SFHT)suffers from high update overhead and large memory requi...     

A parallel decomposition for Kalman filters

A decomposition is given for the implementation of the Kalman filter as a collection of parallel processors. This decomposition is based on the representation of the system as a direct sum of observability subspaces     

深度报文检测中基于GPU的正则表达式匹配引擎*

提出了一种基于GPU的正则表达式匹配引擎来加速深度报文检测中的模式匹配过程。该引擎基于DFA模型,在匹配时每一个GPU线程处理一个报文,通过大量的并行线程来提高引擎的吞吐量。基于NVIDIA GeForce 9800GT GPU的实验表明,该引擎处理实际网络报文时的吞吐量达到了7.91 Gbps。     

Scheduling parallel Kalman filters with quantized deadlines

In this paper we explore the problem of scheduling parallel processes of Kalman filters to meet individual estimation error requirements. It is assumed that at each time-step measurements of only one process are received. We define real-time deadlines of transmissions and convert the problem into arranging sequence of tasks with corresponding deadlines. To reduce computations, cycles of transmissions are calculated and virtual processes are introduced into scheduling. A sliding window method is then designed to adjust the processes against real-time disturbances in applications. Compared with algorithms proposed in Lin and Wang (2013), the proposed algorithm is able to schedule a feasible sequence adaptively within a short scheduling window and requires little computation.     

香烟小包装嵌入式视觉在线检测系统

针对烟草企业对小包烟包装质量精密检测的需要,提出基于嵌入式视觉在线检测的关键技术。本系统以TI公司的数字多媒体处理器TMS320DM642为核心,设计实现小包烟包装质量精密在线检测的软、硬件平台。通过DM642对视频图像进行采集并结合相应的智能图像处理与模式识别算法,使系统不仅适应在线快速包装质量检测,而且能准确的判断缺陷类型。实验证明,嵌入式视觉系统的扩展和适用性强,应用前景广泛。     

一种用于深度报文检测的DFA状态表压缩方法

基于正则表达式进行深度报文检测在IDS/IPS、应用层协议识别等网络应用中具有重要作用。然而,采用DFA实现正则表达式需要大量的存储空间,限制了它的实际应用。将DFA状态转换表拆分成3个表,使用run-length编码进行压缩,并对压缩方法进行了优化。采用l7-filter中几个常用应用程序的正则表达式进行测试,结果表明该方法压缩效果一般在90%以上。     

Utilizing bloom filters for detecting flooding attacks against SIP based services

Any application or service utilizing the Internet is exposed to both general Internet attacks and other specific ones. Most of the times the latter are exploiting a vulnerability or misconfiguration in the provided service and/or in the utilized protocol itself. Consequently, the employment of critical services, like Voice over IP (VoIP) services, over the Internet is vulnerable to such attacks and, on top of that, they offer a field for new attacks or variations of existing ones. Among the various threats–attacks that a service provider should consider are the flooding attacks, at the signaling level, which are very similar to those against TCP servers but have emerged at the application level of the Internet architecture. This paper examines flooding attacks against VoIP architectures that employ the Session Initiation Protocol (SIP) as their signaling protocol. The focus is on the design and implementation of the appropriate detection method. Specifically, a bloom filter based monitor is presented and a new metric, named session distance, is introduced in order to provide an effective protection scheme against flooding attacks. The proposed scheme is evaluated through experimental test bed architecture under different scenarios. The results of the evaluation demonstrate that the required time to detect such an attack is negligible and also that the number of false alarms is close to zero.