BPF+: exploiting global data-flow optimization in a generalized packet filter architecture
BPF+: exploiting global data-flow optimization in a generalized packet filter architecture
复制标题
DOI：
10.1145/316188.316214
复制
发表时间：
1999-08
期刊：
影响因子：
--
通讯作者：
Andrew Begel;S. McCanne;S. Graham
中科院分区：
文献类型：
--
作者：
Andrew Begel;S. McCanne;S. Graham
分组过滤器是用于以通用的、可重用的方式从分组流中分类或选择分组的可编程选择标准。以前的工作包过滤器福尔斯大致分为两类，即那些努力调查灵活和可扩展的过滤器抽象，但牺牲性能，和那些专注于低层次，优化过滤表示，但牺牲灵活性。然而，像网络监控和入侵检测这样的应用程序需要高级别的表现力和原始性能。在本文中，我们提出了一个完全通用的包过滤器框架，提供了高度的灵活性和良好的性能。在我们的框架中，一个包过滤器表示在一个高层次的语言，编译成一个高效的本地实现。编译器的优化阶段使用称为边缘支配者的流图集合关系和我们称为“冗余谓词消除”的优化技术的新应用，在该优化技术中，我们交错部分冗余消除、谓词断言传播和流图边缘消除来进行过滤器谓词优化。我们得到的包过滤框架，我们称之为BPF+，来自BSD包过滤器（BPF），并包括一个过滤程序翻译器，一个字节码优化器，一个字节码安全验证器，以允许代码迁移跨越保护边界，和一个即时汇编转换字节码高效的本地代码。尽管我们的广义框架提供了高度的灵活性，我们的性能测量表明，我们的系统实现的性能与最先进的包过滤器架构，比手工编写的C语言编写的过滤器。
A packet filter is a programmable selection criterion for classifying or selecting packets from a packet stream in a generic, reusable fashion. Previous work on packet filters falls roughly into two categories, namely those efforts that investigate flexible and extensible filter abstractions but sacrifice performance, and those that focus on low-level, optimized filtering representations but sacrifice flexibility. Applications like network monitoring and intrusion detection, however, require both high-level expressiveness and raw performance. In this paper, we propose a fully general packet filter framework that affords both a high degree of flexibility and good performance. In our framework, a packet filter is expressed in a high-level language that is compiled into a highly efficient native implementation. The optimization phase of the compiler uses a flowgraph set relation called edge dominators and the novel application of an optimization technique that we call "redundant predicate elimination," in which we interleave partial redundancy elimination, predicate assertion propagation, and flowgraph edge elimination to carry out the filter predicate optimization. Our resulting packet-filtering framework, which we call BPF+, derives from the BSD packet filter (BPF), and includes a filter program translator, a byte code optimizer, a byte code safety verifier to allow code to migrate across protection boundaries, and a just-in-time assembler to convert byte codes to efficient native code. Despite the high degree of flexibility afforded by our generalized framework, our performance measurements show that our system achieves performance comparable to state-of-the-art packet filter architectures and better than hand-coded filters written in C.