Hewlett-packard Company

3com Corporation

Hewlett-packard Development Company, L.p.

Peter Furlong

David J Law

Kevin Loughran

Eoghan Stack

Eugene O'Neill

Daniel M O'Keeffe

Gareth Edward Allwright

Jerome Nolan

Neil J Clifford

Eoin O'Brien

Andrew Davy

Hana Hailichova

An apparatus including logic to receive a data packet comprising a string of characters, said apparatus having a plurality of states and at least one state for every character position in the string of characters; logic to examine the string of characters for matches with a plurality of predefined values, beginning with an initial character; and logic to execute forward exit transitions from any of the plurality of states based upon the examination of the characters, wherein a current state of the apparatus represents a count of a number of characters from the initial character of the string of characters.

Positionally dependent pattern checking in character strings using deterministic finite automata

A deterministic finite state machine organised for the detection of positionally significant matches of characters in a string of characters examines each character in turn to determine a exit transition for a current state of the machine to another state The machine responds to an examination of the string of characters by executing in response to a first character at the commencement of the string a transition from an initial state to another state. The machine has at least one state for every character position, includes a exit transition from each state for each character to another state; and possesses only forward exit transitions each from any of the states whereby the current state of the machine unambiguously represents a count of the number of characters from the commencement of the string. The machine may include at least one match state which indicates that all character matches in the string required by at least one respective rule have been detected. Some but not all the states in the multiplicity of states each have a single exit transition for any value of a respective character in the string. At least some of the states in the multiplicity of states each define an exit transition to a state indicating 'no match'. The machine may be disposed to cease its examination of the character string on attaining a 'no match'state.

A method of detecting signatures in message segments comprises employing a state machine for the detection of character strings in the message segments. The state machine executes for each input character a transition determined by a current state of the machine and a current input character. The message segments conform to TCP or other ordering transport protocol. The order of arrival of the message segments is monitored. In the event that an intermediate message segment is missing between a processed segment and an immediately subsequent message segment, the current state of said state machine at the end of the said processed segment is stored. The machine is restarted from its null or datum state for the examination of the immediately subsequent message segment, which is then temporarily stored. When the missing segment eventually arrives, it and the stored segment are successively examined for signatures by means of the state machine, beginning at the stored state. The invention allows for examination of overlapping signatures without requiring re-assembly of the segments or substantial buffering.

Detection of signatures in disordered message segments

The deciphering of fragmented enciphered IP packets is performed without requiring reassembly of the fragments. fragmented packets. When a first frame is deciphered a characteristic poly-tuple is saved against the state of the cipher, particularly an output vector. When the next frame comes in, the cipher would continue on from that previously saved state after a look-up of the poly-tuple. Each frame would then be sent on, deciphered, but still representing a fragment of the original packet. The poly-tuple employed for the look-up includes the identity and protocol fields from the IP header and at least one of the source IP address and the destination IP address. The deciphering process may commence with the combination of input data with an initializing vector and proceed by combining input data with a vector fed back from the output of the deciphering engine. The saved cipher state is employed as the initializing vector for the next frame.

Deciphering of fragmented enciphered data packets

Detection of a signature in a data packet comprises performing a pre-classification of the packet, using header information and particularly a 5-tuple access control list, into one of a multiplicity of flows and directing the payload of the packet to a respective one of a multiplicity of deterministic finite state machines each of which stores a plurality of signatures as a sequence of states and acts only on the respective flow.

Reduction of false positive detection of signature matches in intrusion detection systems

A deterministic finite state machine is operated to detect any one of a plurality of digital signatures each corresponding to a succession of characters and each defined by a sequence of states in the state machine. The machine is organized such that for each state after the first in any sequence there are not more than two allowed exit transitions of which one is to a default state. Input characters are examined to determine a transition from a current state of the machine to a next state. When the machine responds to an input character to perform a transition to the default state, the input character is re-examined to determine the next state of the state machine. The reduction in transitions saves considerable space in memory.

Pattern matching using deterministic finite automata and organization of such automata

In a stack of multi-port network communication units each unit has a forwarding database, the units are connected by way of a cascade, and at least some of the units are connected to links constituting a trunk. When a unicast data packet is received at a first of said units and the unicast data packet has a destination address which is not the subject of an entry in the forwarding database of the first unit, the unicast data packet is sent by way of the cascade to the other units in the stack, accompanied by a flag. When a second unit has in its forwarding database an entry, associating the destination address with forwarding data, it sends a management packet indicating said destination address and the identity of said second unit, so that the database of the first unit can be immediately updated.

Growing community of inventors

Dublin, Ireland

Peter Furlong