摘要： BSD包过滤器(BSD Packet Filter，BPF)是BSD Unix操作系统提供的网络数据包捕获及过滤机制的内核组件。该文描述了BPF的组成及工作过程，分析了BPF采用的无环控制流图过滤模式，介绍了此模式基于虚拟机的实现。为了提高过滤器性能，必须解决BPF虚拟机指令生成器处理多个过滤条件组合时存在的指令冗余问题，通过引入静态单赋值(SSA)，结合冗余谓词消除和窥孔优化等技术，可以有效缩短CFG图的平均路径长度，从而实现对过滤器性能的优化。

关键词: BPF, 无环控制流图, 过滤器虚拟机, BPF+, 静态单赋值, 冗余谓词消除

Abstract: A packet filter is a programmable selection criterion for classifying or selecting packets from a packet stream. The BSD packet filter(BPF) is a kernel facility in BSD Unix that gives the user-level programs access to raw or unprocessed network traffic. This paper describes the architecture of BPF, analysis the filter model based on directed acyclic control flow graph。The problem of redundant instructions is a crucial problem in pseudo-machine’s code generator which affects the filter’s performance greatly. To solve this problem, the SSA form, combined with redundant predicate elimination and peephole optimization technology, is used to minimize the average path length in the control flow graph. This results in efficient performance improvement.

Key words: BSD packet filter(BPF), CFG, Filter Pseudo-machine, BPF+, SSA, Redundant predicate elimination

中图分类号: 

• TP393.08