US 6,959,297 B2Granted

System and process for searching within a data stream using a pointer matrix and a trap matrix

AssigneeWinnow Technology, LLC

InventorsJintae Oh, Ilsup Kim, Hojae Lee

Life of this patent

Estimating the term…

Loading patent…

Abstract

A trap matrix searches the entire contents of a data stream for a pattern that matches the pattern for a search term. In those circumstances where there is a match between patterns of the data stream and the search term, the method and system can proceed to an exact match operation. In particular, a pointer matrix and a corresponding active control matrix are generated according to a set of terms in a rule table. Data is sequenced through the trap matrix according to the hierarchy of its trap elements. The trap elements perform a pattern match check between the sequenced data stream and any search term in the set of terms in the rule table. Results from a positive pattern match are preferably communicated from the matching trap element to an exact match lookup.

Claims39

Dependent claims

A process for electronically searching a data stream, comprising the steps of:

(a) defining a pointer matrix based on a set of terms, said terms comprising a plurality of term characters having a plurality of character lengths and a plurality of character combinations and said pointer matrix comprising a set of one-to-one pointers uniquely corresponding with said set of terms, wherein said one-to-one pointers are stored in said pointer matrix at row and column coordinates defined according to said character lengths and according to a set of patterns defined by said character combinations, and wherein said set of terms includes at least one term and said set of patterns includes at least one pattern corresponding with said at least one term;
(b) receiving the data stream at an input device during a time period, the data stream comprising a set of data characters having a data length and a data combination and said time period comprising a plurality of clock cycles,
(c) sequencing the data stream through a trap matrix during said time period, said trap matrix comprising a set of trap elements and a set of delay elements, wherein said trap elements are in multiplexed communication with said input device and wherein said trap elements have a hierarchy according to said set of delay elements, wherein an increasing series of said delay elements between each of said trap elements and said input device defines an increasing order in said hierarchy of said trap elements, said sequenced data stream comprising a set of data lengths according to said hierarchy of said trap elements, said sequenced data stream further comprising a set of data combinations, said set of data combinations corresponding with said set of data lengths according to said hierarchy of said trap elements;
and
(d) performing a pattern match check between said set of patterns and said set of data combinations in each of said trap elements according to said hierarchy of said trap elements.

2 more elements

A process for searching a data stream, comprising the steps of:

(a) defining a set of terms, said terms comprising a plurality of term characters having a plurality of character lengths and a plurality of character combinations associated with said character lengths, wherein said set of terms includes at least one term having a character length and a character combination;
(b) storing said set of terms in a rule table according to a set of table addresses;
(c) correlating said stored set of terms with said set of table addresses according to a pointer matrix, said pointer matrix comprising a set of one-to-one pointers and a set of row and column coordinates, said set of one-to-one pointers defined according to said set of table addresses and said row and column coordinates defined according to said character lengths and according to a set of patterns corresponding with said set of terms, wherein said set of patterns uniquely corresponds with said character combinations, and wherein said set of patterns includes at least one pattern corresponding with said at least one term;
(d) receiving the data stream at an input during a time period, the data stream comprising a set of data characters having a data length and a data combination and said time period comprising a plurality of clock cycles,
(e) sequencing said received data stream through a trap matrix during said time period, said trap matrix comprising a set of trap elements and a set of delay elements, wherein said trap elements are in multiplexed communication with said input and wherein said trap elements have a hierarchy according to said set of delay elements, wherein an increasing series of said delay elements between each of said trap elements and said input results in an increasing order in said hierarchy of said trap elements, said sequenced data stream having a set of data lengths according to said hierarchy of said trap elements and corresponding with said character lengths of said set of terms, and wherein said sequencing step further comprises the steps of:
(i) reading in parallel a current character from said input for each of said trap elements,
(ii) combining in parallel said current character with a set of previously combined set of characters according to said hierarchy of said trap elements, wherein said combined character set is associated with said clock cycles according to said hierarchy of said trap elements, and
(iii) shifting said combined character set through said set of delay elements and said set of trap elements according to said hierarchy, wherein said combined character set is shifted in said increasing order through said hierarchy of said trap elements;
(f) simultaneously checking said combined character set with said pattern of said character combinations for each of said data lengths, wherein said comparing step further comprises the steps of:
(i) defining said character lengths according to said hierarchy of said trap elements for each of said trap elements, respectively, and
(ii) determining whether said combined character set in any one of said trap elements matches a corresponding one of said patterns of said character combinations;
and
(g) checking a portion of said received data stream with an exact term from said set of terms for an exact match therebetween when any combined character set matches said corresponding pattern of said character combinations, wherein said portion of said data stream corresponds with said clock cycles associated with said combined character set and wherein said exact term is stored at a table address according to a unique one-to-one pointer from said pointer matrix, said unique one-to-one pointer having a row and a column coordinate equal to said hierarchy of said one matching trap element and to said corresponding pattern of said character combinations.

10 more elements

A process for electronically searching a data stream, comprising the steps of:

(a) storing a set of terms in a term table according to a set of table addresses, wherein each of said terms stored in said term table has a plurality of term characters, wherein said set of terms has a plurality of character lengths;
(b) compressing said set of terms into a set of compressed term values according to a compression operation on said term characters for each of said terms;
(c) correlating said stored set of terms with said set of table addresses according to a set of one-to-one pointers, said set of one-to-one pointers comprising a pointer matrix, said pointer matrix having row and column coordinates according to said character lengths and according to said compressed term values;
(d) receiving the data stream at an input during a time period, the data stream comprising a set of data characters having a plurality of data character lengths, and said time period comprising a plurality of clock cycles;
(e) sequencing said received data stream through a trap matrix during said time period, said trap matrix comprising a set of trap elements and a set of delay elements, wherein said set of trap elements have a hierarchy according to said set of delay elements, said hierarchy of said trap elements having a one-to-one correspondence with said character lengths of said set of terms, and wherein said sequencing step comprises the steps of:
(i) reading in parallel a current character from said input for each of said trap elements,
(ii) compressing in parallel said set of data characters into a set of data values according to said compression operation, wherein said compression operation is simultaneously performed in each of said trap elements, and
(iii) shifting said set of compressed data values through said set of delay elements according to said hierarchy of said delay elements;
(f) simultaneously checking for a value match between a compressed data value in said set of compressed data values and a compressed term value in said set of compressed term values for each of said trap elements and for each of said character lengths, respectively, wherein said set of compressed data values are respectively checked with said set of compressed term values according to said one-to-one correspondence between said hierarchy of said trap elements and said character lengths of said set of terms, wherein a pattern match returns a matching compressed data value from said set of compressed data values and a matching hierarchy from said hierarchy of said trap elements;
and
(g) checking for an exact match between a portion of said received data stream and an exact term from said set of terms when said value match occurs, wherein said exact term is stored at a table address according to a unique one-to-one pointer from said pointer matrix, said unique one-to-one pointer having a row and column coordinate equal to said matching compressed data value and said matching hierarchy.

8 more elements

A process for electronically detecting an attempt to breach security of a computer network, comprising the steps of:

(a) defining a set of security rules, said security rules comprising a plurality of characters in a plurality of character lengths and a plurality of character combinations;
(b) storing said set of security rules in a rule table according to a set of table addresses;
(c) correlating said stored set of security rules with said set of table addresses according to a set of one-to-one pointers, said set of one-to-one pointers comprising a pointer matrix, said pointer matrix having rows and columns according to said character lengths of said set of security rules and according to a set of patterns corresponding with said set of security rules, wherein said set of patterns uniquely corresponds with said set of security rules according to said character combinations in said character lengths for each of said security rules;
(d) receiving a data packet at an input during a time period, said data packet comprising a set of characters having a length and said time period comprising a plurality of clock cycles,
(e) sequencing said received data packet through a trap matrix during said time period, said trap matrix comprising a set of trap elements and a set of delay elements, wherein said trap elements are in multiplexed communication with said input and wherein said trap elements have a hierarchy according to said set of delay elements, wherein an increasing series of said delay elements between each of said trap elements and said input results in an increasing order in said hierarchy of said trap elements, said sequenced data packet having a set of lengths according to said hierarchy of said trap elements and said hierarchy of said trap elements having a one-to-one correspondence with said character lengths of said set of security rules, and wherein said sequencing step further comprises the steps of:
(i) reading in parallel a current character from said input for each of said trap elements,
(ii) combining in parallel said current character with a set of previously combined set of characters according to said hierarchy of said trap elements to produce a combined character set, and
(iii) shifting said combined character set through said set of delay elements and said set of trap elements according to said hierarchy;
(f) simultaneously checking for a pattern match between said combined character set from said received data packet and said set of patterns uniquely corresponding with said set of security rules for each of said trap elements and for each of said character lengths, respectively, wherein said combined character set is respectively checked with said set of patterns according to said one-to-one correspondence between said hierarchy of said trap elements and said character lengths of said set of terms, wherein a pattern match returns a matching combined character set of said combined character set and a matching hierarchy of said trap elements;
and
(g) checking for an exact match between a portion of said data packet and an exact security rule from said set of security rules when said pattern match occurs, wherein said exact security rule is stored in said rule table at a table address according to a unique one-to-one pointer from said pointer matrix, said unique one-to-one pointer having a row and a column equal to said matching combined character set and said matching hierarchy.

8 more elements

A system for searching a data stream, comprising:

a rule table having a set of terms and a set of table addresses, wherein each of said terms in said set of terms is stored in said rule table at a location defined by a table address in said set of table addresses;
wherein said set of terms comprise a plurality of term characters having a plurality of character lengths and a plurality of character combinations associated with said character lengths, and wherein said set of terms includes at least one term having a character length and a character combination;
a set of one-to-one pointers comprising a pointer matrix, said set of one-to-one pointers correlating said table addresses with said set of terms in said rule table, said pointer matrix further comprising row and column coordinates defined according to said character lengths and according to a set of patterns corresponding with said set of terms, wherein said set of patterns uniquely corresponds with said character combinations for any of said terms having equal character lengths, and wherein said set of patterns includes at least one pattern corresponding with said at least one term;
a buffer memory;
an input for receiving the data stream during a time period, the data stream comprising a set of data characters having a data length and a data combination and said time period comprising a plurality of clock cycles, said input further comprising a bypass for communicating the data stream through said buffer memory,
a trap matrix comprising a set of trap elements and a set of delay elements, said trap matrix sequencing said set of said data characters in the data stream from said input through each of said trap elements, wherein said trap elements are in multiplexed communication with said input and wherein said trap elements have a hierarchy according to said set of delay elements, said hierarchy of said trap elements having a one-to-one correspondence with said character lengths of said set of terms, wherein said set of trap elements further comprise a set of memory-comparator pairs according to said hierarchy of said trap elements, said set of data characters entering said memory-comparator pairs as a set of set of sequenced data, wherein said set of memory-comparator pairs checks for a pattern match between said set of sequenced data and said set of patterns, wherein each of said memory-comparator pairs simultaneously checks for said pattern match according to said one-to-one correspondence between said hierarchy of said trap elements and said character lengths of said set of terms, wherein a matching memory-comparator pair defines a row and column coordinate according to said hierarchy of said trap elements and said sequenced data;
an exact match lookup in communication with said buffer, said trap matrix and said rule table, said exact match lookup receiving a portion of the data stream from the buffer and receiving said row and column coordinate from said trap matrix, said row and column coordinate comprising a hierarchy and sequenced data according to said matching memory-comparator pair;
said exact match lookup retrieving an exact term from said rule table according to a table address in said pointer matrix, said table address being defined by a unique one-to-one pointer having said row and column coordinate;
said exact match lookup checking for an exact match between said exact term and said portion of the data stream.

6 more elements

Dependencies are inferred from the claim text.