Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1995-01-01

Filename

WUCS-95-21.PDF

DOI:

10.7936/K7BZ648H

Technical Report Number

WUCS-95-21

Abstract

Packet filters are a mechanism for efficiently demultiplexing network packets to application endpoints. There is currently no general, formal specification method for packet filters that allows for easy or efficient composition of specifications. In this paper we present an automatic approach that achieves all of these goals. We approach packet filter specification as a language recognition problem: each filter is represented by a context-free grammar, whose language is the set of packets the filter should accept. Thus, packet filters can be formulated through a general, well defined specification; further, the grammar-based approach simplifies filter composition, which is essential where scalability is important. However packet filters based on standard LR parsing techniques suffer from poor performance they touch every portion of the input, they check input bit by bit, they occupy large amount of space. We present new optimizations to LR parsing that enable our automatic approach to overcome the above problems and achieve performance rivalling hand-crafted approaches. We present results that compare our approach to the BSD packet filter for TCP connections; our approach shows significant improvements when there are multiple filters installed: for 50 TCP connections our approach is 6 times faster.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7BZ648H

Download

Share

COinS