Publications by Mr Gerald Tripp

This paper describes an optimised finite state automata based hardware design for implementing high speed regular expression matching. Automata based implementations of regular expression matching can become quite complex and if table driven can use large amounts of memory this can be a problem for hardware based implementations, as the amount of memory available within standard Field Programmable Gate Array (FPGA) components can be quite small as compared with the amount of resources we expect to find within a software environment. This work uses an existing packed array style of table based automata implementation, but then adds a form of input compression to group together characters that are treated identically by the automata. A hardware design for such a system has been created for use within a Xilinx Field Programmable Gate Array and tested by simulation. The design operates at a fixed scan rate of 2.0 Gbps independent of the regular expression used or the input data being scanned. The regular expression rules are first compiled by software and then loaded into the design at run time and may be updated dynamically without modification to the design.

This paper describes a finite state machine approach to string matching for an intrusion detection system. To obtain high performance, we typically need to be able to operate on input data that is several bytes wide. However, finite state machine designs become more complex when operating on large input data words, partly because of needing to match the starts and ends of a string that may occur part way through an input data word. Here we use finite state machines that each operate on only a single byte wide data input. We then provide a separate finite state machine for each byte wide data path from a multi-byte wide input data word. By splitting the search strings into multiple interleaved substrings and by combining the outputs from the individual finite state machines in an appropriate way we can perform string matching in parallel across multiple finite state machines. A hardware design for a parallel string matching engine has been generated, built for implementation in a Xilinx Field Programmable Gate Array and tested by simulation. The design is capable of operating at a search rate of 4.7 Gbps with a 32-bit input word size.

This paper describes the design of an asynchronous transfer mode (ATM) network interface with additional facilities to allow it also to act as both a traffic monitor and traffic source. High resolution timing is provided to enable all received cells to be time stamped on arrival and the information passed back to the user. For transmission, a cell has an associated target transmission time and the transmit hardware will block the head of the transmit queue until the target time is reached.

A new algorithm is proposed to minimise the distortions that accumulate in the process of subjecting images to multiple JPEG compressions.

This paper describes a finite state machine approach for string matching within high-speed network intrusion detection systems. This method uses a standard table based finite state machine implementation, but this is preceded by a preliminary stage that compresses multi-byte network input data into a series of tokens. Each string is matched using a separate finite state machine, each of which has an individually customised token stream. The finite state machines thus created need only a small amount of hardware resources and the overall system is designed to consume network input data at a rate of one word per clock cycle, independent of the search strings and the input data being searched. This technique has been tested using a high-level simulation in Java, with an architecture consisting of two Ternary Content Addressable Memory (TCAM) components followed by a tree structure of lookup tables that generate a separate token stream for each finite state machine. The results of the simulation show that the technique is effective for an input word size of up to 64-bits. It is possible to build the lookup tables and the finite state machine tables with relatively small blocks of memory, such as those provided within a Field Programmable Gate Array the TCAM can be implemented as external components. Most of the complexity in this system is within the software that compiles the string matching rules into the contents for the various lookup tables; the hardware resources required are mainly the various interconnected lookup tables that need initialising each time we change the rule set.

An RPC implementation is described which uses a small network of Transputers as a parallel front end processor to reduce communications delays. Parallel processing allows different aspects of the protocol support and parameter marshalling to be overlapped. Particular attention is paid to issues which affect the performance of the system. Some comparisons are drawn with the ANSAware distributed systems platform.

This paper describes a method for the implementation of regular expression matching based on the use of a form of associative (or content addressable) memory. The regular expression matching is performed by converting the regular expression into a Deterministic Finite Automata, but then using associative memory to hold the state transition information. Rather than try to simplify the resulting automata, this approach starts from the point of view of each next state in the automata being arrived at from some particular area of state-input space. We implement our automata by defining a number of orthogonal regions of state-input space, each of which is compared against our current state and input data. The highest priority region that produces a match will identify a corresponding next state for the automata. This work differs from previous work in that the associative memory used performs a full set membership test, and is hence more selective than systems based on Ternary Content Addressable Memory. This report describes work in progress, which to date has produced the rule processing software and outline designs for the hardware.

Automata based regular expression matching can often require large amounts of memory for its state transition tables, particularly when matching multiple complex regular expressions with the same automata. For systems with limited memory resources it is common to try to compress the state transition tables. One technique called row displacement with state marking does this by identifying default values for the next state and then packing the remaining information into a one dimensional array. Although this compression technique works well when matching multiple strings, it is not as effective when matching multiple complex regular expressions. This paper describes a technique called next state prediction. This performs lossy compression of the current state and input values and uses these to select a likely next state from a prediction table. This is used in conjunction with a standard row displacement with state marking algorithm and leads to an overall reduction in the memory required for the various tables. The algorithms have been tested with a number of different design parameters, and compared with a 'baseline version' where this technique is not used. When testing this system with a set of regular expressions from the Snort intrusion detection system, the memory required was around 46% of that required for the baseline version. The design has been modelled in VHDL for use within an FPGA and tested via simulation and operates at a search rate of 2.0 Gbps irrespective of the regular expressions being searched for or the input data being scanned.

The aim of this work is to investigate the effectiveness of a finite state machine (FSM) based string-matching scheme for the implementation of high-speed network intrusion detection systems. The work uses standard RAM based techniques for the FSM implementation, but provides a per-FSM input stream consisting of symbols representing multi-byte patterns that appear in the input data. Multiple search strings are processed in parallel using multiple FSMs. This pre-FSM classification stage is used to reduce the redundancy in the input data stream (as seen by an individual FSM) and hence allows a FSM to be implemented with relatively small resources that is able to operate on multiple bytes per clock cycle. The benefit of this approach is that in operating on a relatively large number of input data bits per clock cycle, we are able to cope with an increased network throughput. An example architecture is described along with an associated compiler. The compiler takes a set of intrusion detection rules, generates the various tables required for system implementation and also provides a high level simulation against some simple synthesised network data. Resource utilisation is presented for a range of input word sizes.

This paper looks at the design of an embedded processor to be used for network traffic monitoring. This would operate on the stream of data between a network interface and a host computer. Associative processing techniques are used to implement multiple finite state machines that can be used to monitor various network streams or protocol layers. Network packets are selectively captured and passed along with other status information to a host computer for further processing. A first version of such a processor has been designed and modeled in VHDL. The processor design has been simulated and performance figures are presented in this paper along with some sample monitoring programs. This study shows that associative processing appears to be an efficient way to implement fast network monitoring tools.

This paper investigates possible associative processing architectures for use in the implementation of a real time network traffic monitoring system. The proposed solution is a simple associative mono-processor based on a small number of electronic components including state-of-the-art ternary content addressable memory. This would enable a large number of finite state machines to be implemented which could be used to track the activity of multiple data channels at several protocol layers. The system would receive a stream of packets of data from a network and could be programmed to generate output event messages consisting of selectively captured network data or other information.

This paper looks at the problems of real time network traffic monitoring. Some of the existing approaches are reviewed, looking at both simple filtering systems and also systems based on the use of finite state machines that can report specific events or capture data only when in particular states. Finally, some existing implementation techniques are examined and an outline proposal made for the design of a network monitoring system that uses finite state machines implemented using associative processing.

This paper describes an ATM interface with additional facilities to also allow it to act as both a traffic monitor and traffic source. High resolution timing is provided to enable all received cells to be time stamped on arrival and the information passed back to the user. For transmission, a cell has an associated target transmission time and the transmit hardware will block the head of the transmit queue until the target transmit time is reached. This interface is intended to serve two purposes: as a conventional interface for ATM based projects and also as a piece of test equipment to act as a traffic source or monitor (or both) for use in experiments on ATM network performance. As a conventional interface, the control over transmit time for individual cells gives facilities for implementation of traffic shaping schemes. As a piece of test equipment, the control over precise transmit times and the recording of cell receive times allow accurate measurements to be made on network performance which would not be possible with a conventional interface.

This report describes the design and implementation of a simple microprogrammable processor with a fast response time to external events. This processor was designed as a controller for a testbench video system capable of performing a number of functions such as windowing and frame rate conversion.

Two-point ATM Switching System Measurements P.F. Linington and G.E.W. Tripp Abstract The ATM testbed at the University of Kent includes specialized hardware for the generation and measurement of ATM cell streams with a variety of different timing properties. This measurement environment has made possible precise evaluation of the performance of various ATM network configurations, revealing a range of different kinds of behaviour that result from the switch architectures and the way they are combined. Observations of the cell stream taken at different points in the network have been analysed using a number of techniques, exploiting variations on correlation of the times measured and delays experienced by the cell stream. Different processing options produce a family of data representations which show significant features of the system behaviour, and which can be used to identify potential operational problems before they become apparent to users of the network.