CN100461091C - Method and system for content detection with reconfigurable hardware - Google Patents

Abstract

The method and system according to the present invention are used to identify duplicate content in a data stream. A hash function is calculated for at least one of a plurality of portions of the data stream. Benign characters are removed from the at least one portion of the data stream to prevent benign strings from being identified as duplicate content. At least one of a plurality of counters is incremented in response to the calculated hash function result. Each counter corresponds to a corresponding calculated hash function result. The duplicate content is identified when at least one of the plurality of counters exceeds a count value. The identified duplicate content is verified to be not a benign string.

Description

Method and system for content detection with reconfigurable hardware

Cross References to Related Applications

This application claims the filing date and priority of U.S. Provisional Application Serial No. 60/604,372, filed August 24, 2004, entitled "METHODS AND SYSTEMS FOR CONTENT DETECTION IN A RECONFIGURABLE HARDWARE," the contents of which are hereby incorporated as permitted by law Levels are cited for reference.

technical field

The present invention relates generally to the field of network communications, and more particularly to methods and systems for detecting content in data transferred over a network.

Background technique

Internet worms work by exploiting vulnerabilities in the operating system and other software running on the system. Attacks can compromise security and degrade network performance. Their impact includes significant financial losses for businesses due to system downtime and workers not being able to work. It is expected that in the future the systems used to protect networks from malicious code will become part of the critical Internet infrastructure. Currently, these systems, known as Intrusion Detection and Prevention Systems (IDPS), typically only filter previously identified worms, so they are of limited use.

Contents of the invention

The method and system according to the present invention detect frequently occurring content in network communication traffic, such as worm signatures. Content detection is implemented in hardware, which provides higher throughput compared to conventional software-based approaches. Data sent via data streams in the network is scanned to identify patterns of similar content. Frequently occurring data patterns are identified and reported as likely worm signatures or other types of signatures. Data can be scanned in parallel to provide high throughput. Throughput is maintained by parallel hashing of several windows of bytes of data to on-chip block memories, where each on-chip block memory can be updated in parallel. The identified content may be compared to known signatures stored in off-chip memory to determine if there are false positives. Because the methods and systems according to the present invention can identify frequently occurring patterns, they are not limited to identifying known signatures.

According to the method according to the invention, there is provided a method in a data processing system for identifying duplicate content in a data stream. The method includes the steps of: computing a hash function for at least one of a plurality of portions of the data stream; and incrementing the value of at least one of a plurality of counters in response to the computed hash function result, each The counters correspond to corresponding calculated hash function results; identifying the duplicate content when a value of at least one of the plurality of counters exceeds a predetermined threshold; and verifying that the identified duplicate content is not a benign string.

According to the system according to the invention, a system for identifying duplicate content in a data stream is provided. The system includes: a hash function calculation circuit for calculating a hash function for at least one of the plurality of portions of the data stream; a plurality of counters responsive to the calculated hash function results to cause the plurality of counters to The value of at least one counter in the plurality of counters is increased, each counter corresponding to the hash function result of the corresponding calculation; the duplicate content identifier is used to identify when the value of at least one counter in the plurality of counters exceeds a predetermined count value. duplicate content; and a validator to verify that the identified duplicate content is not a benign string.

According to the system according to the invention, a system for identifying duplicate content in a data stream is provided. The system includes: means for calculating a hash function for at least one of the plurality of portions of the data stream; and for causing at least one of the plurality of counters to be activated in response to the calculated result of the hash function. means for incrementing a value, each counter corresponding to a corresponding calculated hash function result; means for identifying said duplicate content when the value of at least one of said plurality of counters exceeds a predetermined count value; and means for verifying The identified duplicate content is not a benign string device.

Other features of the present invention will become more apparent to those skilled in the art when examining the following drawings and detailed descriptions. It is intended that all such additional systems, methods, features and advantages be included within this description, be within the scope of the invention, and be protected by the following claims.

Description of drawings

The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate the implementation of the invention and together with the description serve to explain the advantages and principles of the invention: In the accompanying drawings,

Figure 1A is a block diagram of a system for performing content detection in accordance with the present invention;

Fig. 1B is a functional block diagram showing how a signature detection device processes a data stream according to the present invention;

Fig. 2 is a block diagram according to the feature code detecting device of the present invention;

Figure 3 is a block diagram of a counting processor according to the present invention;

Figure 4 is a block diagram of a character filter according to the present invention;

Figure 5 is a block diagram of a byte shifter according to the present invention;

Figure 6 is a block diagram of a control packet containing benign character strings in accordance with the present invention;

Figure 7 is a block diagram of a large count vector according to the present invention;

Figure 8 is a more detailed block diagram of the large count vector of Figure 7;

Figure 9 is a block diagram of a pipeline according to the present invention;

Figure 10 is a functional block diagram for depicting parallel processing of bytes of a data stream;

Figure 11 shows an example of how a priority encoder handles data without conflicts;

Figure 12 shows an example of how a priority encoder handles data in the event of a conflict;

Figure 13 is a block diagram of an analyzer according to the present invention;

Figure 14 is a state diagram of analyzer states according to the present invention; and

Fig. 15 is a block diagram of control packets sent from the alarm generator according to the present invention.

Corresponding figure identifiers refer to corresponding parts throughout the several figures.

Detailed ways

Reference will now be made in detail to implementations in accordance with methods, systems and articles of manufacture in accordance with the invention as illustrated in the accompanying drawings.

Methods and systems according to the present invention detect frequently occurring content in data streams, such as worm signatures, while resisting polymorphic techniques, such as those used by worm authors. In order to realize content detection at high speed, the system is realized with hardware.

FIG. 1A is a block diagram of an illustrative data processing system 100 suitable for use with methods and systems in accordance with the present invention. As shown, multiple hosts are connected to multiple subnets. That is, hosts 102 , 104 , and 106 are connected to subnetwork 108 ; hosts 110 and 112 are connected to subnetwork 114 ; and hosts 116 and 118 are connected to subnetwork 120 . Communication traffic between respective subnetworks and between the subnetworks and a larger network 128 , such as the Internet, passes through router 126 . Virtual local area network (VLAN) concentrator 122 concentrates network communication traffic entering router 126 . By placing the signature detection device 124 between the router and the VLAN concentrator 122, the traffic flow between the sub-networks can be scanned for content.

In the illustrative example of FIG. 1A , signature detection device 124 is a field-programmable port extender (FPX) platform. The FPX platform allows high-speed network flows to be processed by using a large field programmable gate array (FPGA) 130, such as a Xilinx XCV2000E FPGA. The signature detection circuitry described below can be downloaded into FPGA 130 to process network flows at communication traffic rates up to 2.5 Gigabits per second. Network communication traffic is clocked into FPGA 130 using 32-bit wide data words. Those skilled in the art will understand that the methods and systems according to the present invention may be implemented using hardware and software components other than those described herein. For example, other devices other than the FPX platform may be used to implement the signature detection device.

In the illustrative examples described herein, reference is made to detecting worm signatures, although methods and systems according to the present invention are not limited thereto. Methods and systems according to the present invention can identify duplicate content in a data stream. Duplicate content can be, but is not limited to: worms; viruses; the presence of large numbers of people visiting a website; the existence of a large number of similar emails being sent to multiple recipients, such as spam; content repeatedly exchanged via peer-to-peer networks, Duplicate content such as music or video; and other formats.

FIG. 1B is a functional block diagram illustrating how signature detection device 124 processes a data stream in accordance with the present invention. In the illustrative example, FPGA 130 includes character filter 150, hash processor 152, count vector 154, time averaging processor 156, threshold analyzer 158, off-chip memory analyzer 160, and A functional component of the alarm generator 162 . These functional components provide an illustrative high-level functional view of field programmable gate array 130 . The field programmable gate array 130 and its function are described in more detail below with reference to FIGS. 3-15.

As shown in the illustrative example, character filter 150 samples data from data stream 170 and filters out characters that are unlikely to be part of the binary data, thereby providing N-byte data string 172 . As will be described in more detail below, worms typically consist of binary data. In this way, character filter 150 filters out characters that are less likely to exhibit characteristics of a worm signature. Hash processor 152 computes a k-bit hash on N-byte string 172 and hashes the resulting signature to count vector 154 . As will be described in more detail below, count vector 154 may include multiple count vectors. When the signature is hashed to count vector 154, the value of the counter specified by the hash is incremented. At periodic intervals, referred to herein as measurement intervals, the count value in each count vector is reduced by an amount equal to or greater than the average reached due to normal traffic flow, as determined by time averaging processor 156 . When count vector 154 reaches a predetermined threshold, as determined by threshold analyzer 158 , off-chip memory analyzer 160 hashes the offending string to a table in off-chip memory 212 . The next time the same string occurs, a hash is done at the same location in off-chip memory 212 to compare the two strings. If the two strings are the same, an alarm is generated. If the two strings are different, then the string in off-chip memory 212 is overwritten with the new string. Thus, off-chip memory analyzer 160 can reduce the number of alerts by reducing alerts due to semi-frequently occurring strings. When an alarm message is received, the alarm generator 162 sends a control packet including an offending signature to an external machine for further analysis.

FIG. 2 is a block diagram illustrating the signature detection device 124 in more detail. In the illustrative example, circuitry for detecting signals on the network is implemented in field programmable gate array 130 as application 202 called worm_app. The worm_app 202 fits within the framework of a layered protocol wrapper 204 . As will be described in more detail below, the count processor 206 receives a wrapped signal from the layered protocol wrapper 204, parses the wrapped signal into a byte stream, hashes the byte stream into a count vector, and makes the value of the counter Increase. The count processor 206 further counts and averages the number of detected worm signatures and processes benign strings. The count processor 206 outputs the signal count_match which is asserted high for signatures exceeding the threshold and corresponding 10 byte long worm offending_signature. Additionally, count processor 206 may output signals to layered protocol wrapper 204 .

Implement the worm_app circuit such that it provides high throughput and low latency. To achieve this performance, the worm_app circuit can be pipelined. In the illustrative example, the pipeline length is 27 clock cycles and can be broken down as follows:

-FIFO latency: 3 clock cycles

- Count processor latency: 11 clock cycles

- Analyzer latency: 13 clock cycles

Analyzer 208 receives input signals from counting processor 206 and interfaces with hash table 210 stored in off-chip memory 212, such as static random access memory (SRAM). If count_match is asserted high, off-chip memory 212 is accessed by analyzer 208 . If the offending_signature is identified in the hash table 210 of the off-chip memory 212, the analyzer 208 outputs a signal analyzer_match that is asserted high. Alarm generator 214 receives the analyzer_match signal from analyzer 208 and passes the wrapper signal it receives from count processor 206 to layered protocol wrapper 204 . When the analyzer_match signal is asserted high, the alarm generator 214 sends out a control packet containing the offending_signature.

A component-level view of an illustrative count processor 206 is shown in FIG. 3 . Count processor 206 includes packet buffer 302 . As will be described below, the packet buffer 302 buffers packets during count averaging periods when the block RAM is occupied and the counters within the block RAM cannot be incremented. Outside of the count averaging period, the packet buffer 302 is delivered via traffic. Character filter 304 determines which bytes are to be included in the worm signature. Byte shifter 306 assembles a countable input string from the output of character filter 304 . The large count vector 308 hashes the string received from the byte shifter 306, increments the corresponding counter value and generates an alarm as needed. Each functional component of the counting processor is described in more detail below.

Character filter 304 is shown in more detail in the block diagram of FIG. 4 . Character filter 304 may cause selected characters to be excluded from hash calculations. Since worms typically consist of binary data, the signature detection device can ignore some characters in the data stream that are very unlikely to be part of the binary data. These characters include, for example, blanks, newlines, newlines, and spaces in the data stream. Text documents for example contain a lot of spaces and empty lines for padding. Another reason to avoid these characters is that blank lines or strings of spaces do not have to exhibit the properties of a good signature to identify a worm. It is preferable to use strings that do not appear in the document. Methods and systems according to the present invention are not limited to heuristics for avoiding harmful signatures. Other ways this can be done include, but are not limited to: identifying and ignoring text in email messages, preprocessing entire strings, or stream editing to search for regular expressions and replace them with strings.

The character filter 304 receives a 32-bit data word data_in and a signal data_en as input, and the signal data_en is used to identify whether the data in data_in is valid. Character filter 304 splits the 32-bit word into 4 individual bytes (byte1 to byte4) and outputs a corresponding signal to indicate whether the byte contains valid data (byte1valid to byte4valid). If it is one of the characters that character filter 304 is looking for, it is considered invalid. If, for example, the 4-byte string a, newline, b, null is received as input by character filter 304, and assuming character filter 304 is configured to ignore newline and null characters, then the corresponding output signal of character filter 304 may will be:

Byte1: a, Byte1 valid: high

Byte2: newline, Byte2 effective: low

Byte3: b, Byte3 valid: high

Byte4: null, Byte4 valid: low

FIG. 5 is a block diagram of an illustrative byte shifter 306 . Byte shifter 306 reads in values from character filter 304 and outputs a byte-shifted version of the signature, possibly hashed by large count vector 308 . The byte shifter 306 also outputs the number of bytes that need to be hashed (num_hash) and a signal to tell the large count vector 308 when to start counting averages. Byte shifter 306 accepts data output from character filter 304 . In the illustrative example, the output signatures are 13 bytes long, and each signature contains four overlapping strings of 10 bytes.

The following illustrative example describes the functionality of the byte shifter. If the input was "NIMDAADMIN123" followed by the strings a, newline, b, null from the previous example, then the byte-shifted version of the string would be "MDAADMIN123ab" and num_hash would be 2. The num_hash value is used by the large count vector 308 as described below.

To maintain a running average of the number of detected signatures, the count of detected signatures is periodically decremented. In the illustrative example, this occurs at packet boundaries after a fixed number of bytes, such as 2.5 megabytes, have been processed. Byte shifter 306 keeps track of the number of bytes that have been hashed to large count vector 308 . When the total number of bytes processed exceeds a threshold, then byte shifter 306 goes through the following steps:

1. The byte shifter 308 waits for the last word of the current packet to be read from the packet buffer 302 and then stops reading from the packet buffer 302 . From this point on, the communication traffic entering the counting processor 206 is temporarily buffered in the packet buffer 302 . This is done because the bytes cannot be hashed and counted when doing count averaging.

2. When the last word of the current packet has been processed by the large count vector 308, the byte shifter 306 asserts the subtract_now signal high. This signal is used by the large count vector 308 to start count averaging.

When the start of payload signal from the wrapper is asserted high, the byte shifter 306 asserts the count_now signal high. count_now is asserted low when the end of frame signal from the wrapper is asserted high. From this, bytes including only the payload can be counted.

Byte shifter 306 may also determine whether there are benign strings in the data stream. A benign string, such as a code segment from Microsoft Update, can be identified by being programmed into the byte shifter 306 as a set of strings that, while commonly appearing on the web, are not worms. The benign strings are loaded into the large count vector 308 by receiving the benign string packets at the byte shifter 306 via the data stream. For example, when a packet is sent on port 1200 to a destination address of 192.168.200.2, byte shifter 306 assumes that the packet contains a 13-bit hash value of a benign string. The upper 5 bits of the hash value are used to reference one of the 32 block RAMs and the lower 8 bits are used to reference one of the 256 counters within each block RAM. A diagram of an illustrative control packet 602 containing benign strings is shown in FIG. 6 . The lower 13 bits of the first word of the payload are output as benign_string and benign_valid is asserted high. count_now is asserted low because the control packet contains benign strings that do not have to be counted. The benign_valid and count_string signals are used by the large count vector 308 to avoid counting benign strings, as explained below.

FIG. 7 is a block diagram of an illustrative large count vector 308 . The output of byte shifter 306 is the input of large count vector 308 . The big count vector 308 contains the logic to hash the input string, resolve conflicts between block RAMs, read from block RAM, increment the value of the counter and write back to block RAM. In the illustrative example, large count vector 308 includes 32 block RAMs each having 256 counters, each counter being 16 bits wide. With an illustrative counter of this size, counts up to 64K can be supported. The functional components of the large count vector 308 will be described in more detail below with reference to FIG. 8 .

The illustrative large count vector 308 computes four hash values per clock cycle for the four 10-byte strings included in the 13-byte signal string. Compute more than one hash value per clock cycle to maintain throughput. Since the tracked signatures may appear at any point in the payload, and they are hashed to the same place regardless of their offset in the packet, the same hash function is used in all cases. Each hash function produces a 13-bit value.

To detect frequently occurring content, the large count vector 308 computes a k-bit hash over a 10-byte (80-bit) window of streaming data. To compute the hash, a set of k x 80 random binary values is generated when the counting processor is configured. Each bit of the hash is computed as an exclusive OR (XOR) on a randomly selected subset of the 80-bit input string. By randomizing the hash function, an adversary cannot determine byte patterns that could cause too many hash collisions. Multiple hash calculations for each payload ensure that simple polymorphic approaches are less effective.

In an illustrative embodiment, a general hash function called _H3 is used. The hash function _H3 is defined as:

$\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="1"\; label="d"\; filenames="C200580033049E00341.png,C200580033049E00401.png"\; state="\{\{state\}\}">d</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; \&CenterDot;</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; \&CirclePlus;</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="2"\; label="d"\; filenames="C200580033049E00371.png"\; state="\{\{state\}\}">d</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; \&CenterDot;</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; \&CirclePlus;</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="3"\; label="d"\; filenames="C200580033049E00331.png,C200580033049E00341.png"\; state="\{\{state\}\}">d</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; \&CenterDot;</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; \&CirclePlus;</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>{<span\; class="notranslate">\; \&CirclePlus;</span>\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; b</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; b</span>}}$

In the above formula, b is the length of the string measured in bits. In the illustrative example, b=80 bits. (d ₁ , d ₂ , d ₃ , . . . d _b ) are k×80 groups of random binary values. Random binary values in the range [0..2m ^+n-1 ] (where n is the size of a single counter in bits and ^2m is the number of block RAMs used). In other words, the d value has the same range as the hash value to be generated. An XOR function performed on the set of random values with respect to the input generates a hash value that has a distribution over the input values.

To compute the hash, for each bit in the string, if the bit is equal to '1', the random value associated with that bit is XORed with the current result to obtain the hash value. For example, given d = (101; 100; 110; 011) and the input string X = 1010, then the corresponding 3-bit hash function is 101 XOR 110 = 011.

Large count vector 308 uses hash values to index into counter vectors contained in count vectors such as count vector 802 . This causes the value of the counter to be incremented by one when a signature hashes to the counter. At periodic intervals, which may be referred to herein as measurement intervals, the count value in each count vector is reduced by an amount equal to or greater than the average number reached due to normal traffic flow. When the value of the counter reaches a predetermined threshold, the analyzer 208 accesses the off-chip memory 212, as will be described below, and the counter is reset. For the illustrative implementation of the circuit on a Xilinx FPGA, the count vector is implemented by configuring a dual-ported on-chip block RAM as an array of memory cells. Each illustrative memory can perform one read operation and one write operation per clock cycle. As shown in Figure 9, a three-stage pipeline is implemented to read, increase and write to the memory in each clock cycle. Since the signature changes every clock cycle and since each occurrence of each signature is counted, high performance is required from the memory subsystem perspective. Dual-ported memory allows writing back occurrences of one signature while an occurrence of another signature is being read.

To mark the end of the measurement interval, the large count vector 308 may reset the counters periodically. After the fixed byte window has elapsed, all counters are reset by writing the value to zero. However, this approach has drawbacks. If the counter value corresponding to a malicious signature is just below the threshold near the end of the measurement interval, resetting the counter makes the signature go undetected. So instead, the illustrative large count vector 308 periodically subtracts the average from all counters. The average is calculated as the expected number of bytes that can be hashed to each counter's value in the interval. As described below, this method requires the use of comparators and subtractors.

To achieve high throughput, multiple strings can be processed per clock cycle. To allow multiple memory operations to be performed in parallel, multiple block RAMs are used in the content detection system 130 as shown in FIG. 10 to segment count vectors into multiple banks. Use the higher bits of the hash value to determine which block of RAM to access. The lower bits are used to determine which counter's value should be incremented within a given block of RAM. More than one string may hash to the same block of RAM. This situation is referred to herein as a "bank conflict." A priority encoder can be used to resolve bank conflicts. Due to the operation of the priority encoder, it may not count between 1 and 3 strings per clock cycle for systems running at OC-48 line rates.

The probability c of conflict can be expressed by the following formula:

$\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; B</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}}\frac{\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}$

In the above formula, N is the number of block RAMs used and B is the number of bytes coming per clock cycle.

A priority encoder, such as priority encoder 804, resolves collisions that may occur when the upper 5 bits of two or more of the four hash values are the same. The priority encoder 804 outputs the address of the block RAM that needs to be increased. As shown in Figure 8, the upper 5 bits of the hash value are used to identify the block RAM to be increased. The lower 8 bits are used to index the counter within the block RAM whose value is to be incremented. bram_num1 to bram_num4 refer to each block of RAM. ctr_addr1 to ctr_addr4 refer to the number of the counter whose value is to be incremented within each block RAM. num1_valid to num4_valid are asserted high when the corresponding block RAM and counter addresses are valid. Since an alert can be generated by any of the 32 block RAMs and the alert can correspond to four possible signatures, the large count vector 308 keeps track of which signature triggered the alert. This is achieved by using the signals sign1 to sign4 corresponding to the bram_num and ctr_addr signals. In an illustrative example, signals sign1 through sign4 can have one of five values: one, two, three, and four corresponding to the first, second, third, and fourth signatures in the 13-byte signal string. A value of eight indicates a benign string.

The value num_hash determines the number of block RAMs in which conflicts need to be resolved. For example, if this signal has a value of two, then this means that the byte shifter 306 has shifted the signature by two bytes. Therefore, only two signatures are counted because two other signatures have already been counted.

An illustrative example of the functionality of the priority encoder in the absence of conflicts is shown in FIG. 11 . In the illustrative example, during the first clock cycle, all four input bytes are considered valid by the character filter. Therefore, all four signatures are hashed, and sign1 through sign4 have valid values along with their corresponding bram_num and ctr_addr signals. During the second clock cycle, only two of the four input bytes are considered valid by the character filter. Therefore, only two signatures are hashed. So only sign1 and sign2 have valid values for signatures 3 and 4.

An illustrative example of the functionality of the priority encoder in the presence of conflicts is shown in FIG. 12 . As shown in the illustrative example, increased block RAM conflicts in two cases. In both cases, one signature is preferred to resolve conflicts. The priority of one signature relative to another is in large count vector 308 .

In an illustrative embodiment, since the native functionality of block RAM does not include support for reset and count averaging, a wrapper is provided around the block RAM to implement this functionality. The functionality of the package is illustratively represented by the illustrative count vector shown in FIG. 8 . Thirty-two copies of this count vector component are instantiated in the large count vector 308, one for each block of RAM being used.

As shown in the illustrative example of the count vector, the count vector has a reset signal. When the reset signal is asserted low, the value of each counter is initialized to 0. Since the block RAMs are initialized in parallel in the illustrative example, this takes 256 clock cycles (the number of counters in each block RAM). hash identifies the address to read in count_vector. dout identifies the data corresponding to the hash in the counter. addr identifies the address where the incremented count is to be written back, as described below. ctr_data identifies the value to be written back to count_vector. set_ctr provides write permission to count_vector. When subtract is asserted high, the large count vector iterates through each counter and subtracts the average from it. As mentioned previously, the average is calculated as the expected number of bytes that might hash to the counter's value in each interval. If the value of the given counter is less than the average value, then it is initialized to zero. If the value of a given counter contains the particular field associated with a benign string, it is not decremented. As with initializing the count vector, parallelism ensures that the subtraction is achieved within 256 clock cycles.

To support benign strings, the counter corresponding to the hash of the benign string is filled with values exceeding the threshold. When the counter has this value, the circuit skips the described steps of incrementing and writing back.

For a limited number of common strings, hash buckets may not be counted, and thus alerts may be avoided. But as the number of benign strings approaches the number of available counters, effectiveness decreases because fewer counters are used to detect signatures. For larger numbers of uncommon strings, false positives can be avoided in downstream software. To reduce false positives being sent to downstream software, strings that are benign but occur less frequently can be processed by the control host.

Referring back to FIG. 8 , the input to the read stage 806 is the output from the priority encoder 804 . The output from the read stage 806 is connected to the address and data buses of the 32 block RAMs (eg, count vector 802). However, only one count vector 802 is shown in FIG. 8 for simplicity. Depending on the value of the read stage 806's bram_num input, the appropriate address and data signals are asserted. Signals sign1 to sign4 entering the read stage 806 are assigned to any of signb1 to sign b32 (hereinafter referred to as the "sign" signal while referring to any one of the block RAMs), except when processing control packets containing benign strings will flow out of the read stage 806 . In this case, the output sign signal is assigned a value of 8 so that the comparison component 808 and the addition component 810 can handle it appropriately.

The output of a count vector, such as count vector 802, is checked by its corresponding compare component 808, and if it is less than a threshold, the compare component's inc signal is asserted high. If it is equal to the threshold, the large count vector 308 sets the count_match signal high to notify the analyzer 208 of potentially frequently occurring signatures. The count_match signal keeps off-chip memory 212 occupied for up to 13 clock cycles (this is because it is the time it takes to start reading a 10-byte string from off-chip memory 212, compare character strings, and write the string back) , the count_match suppress signal ensures that there is an interval of at least 13 clock cycles between two count_match signals.

There are four illustrative functions in the increment and writeback stages, which may be performed in a pipelined manner. In all cases, ctr_data is the value that is written back to the count vector. The four illustrative functions are as follows:

- If the inc signal has been asserted high, then the value of ctr_data is set to one more than the output of count_vector.

- If the sign value is 8, then the value associated with the benign string is designated as ctr_data. In the illustrative example, this value is 0 x FFFF.

- If the output of the count vector is 0 x FFFF, then assign the same value to ctr_data to hold the benign string.

The default value for -ctr_data is 0. If the counter has exceeded the threshold, then the zero value will not change.

A valid signal (eg, bl_valid) is used as an input to the count vector's write enable (eg, set_ctr) when flopped the appropriate number of times.

Some block RAM can be placed in such a way as to suffer large propagation delays during placement and routing. This may cause the circuit to fail timing constraints. This is remedied in the illustrative example by including flip-flops to the inputs and outputs of the block RAM. Additional triggers are not shown in Figure 8 in order to maintain clarity.

When a malicious signature is found, the large count vector 308 outputs count_match and the corresponding signature (sign_num). The count processor 206 inverts the string an appropriate number of times to reflect the latency of the large count vector 308 . When count_match is asserted high, offending_signature is chosen according to the value of sign_num.

FIG. 13 is a block diagram of an illustrative analyzer 208 . Analyzer 208 retains suspicious signatures and estimates how often certain signatures occur. Accordingly, analyzer 208 may reduce the number of alerts sent by alert generator 214 . To do this, the analyzer makes sure that the values of the counters crossing a predetermined threshold are in fact the result of frequent occurrences of strings. When the value of the counter crosses a predetermined threshold, the harmful string is hashed to a table in off-chip memory 212 . Compute a 17-bit hash value for the malicious signature using the method described above. The off-chip memory 212 data bus is 19 bits wide. The hash value maps to the upper 17 bits of the address signal. The lower two bits of the address signal are changed to represent three consecutive words in the memory used to store 10 byte strings. The hash value is used to index into the hash table 210 in off-chip memory. The next time the same string occurs, the analyzer hashes to the same location in off-chip memory 212 and compares the two strings. If the two strings are the same, an alarm is generated. If the two strings are different, analyzer 208 overwrites off-chip memory 212 cells and stores another string. In this case, counter overflow may occur because the hash function hashes several semi-frequently occurring strings to the same value. Since semi-frequently occurring strings are not of interest, analyzer 208 can prevent the overhead of generating alert packets.

The illustrative signals of analyzer 208 are explained below:

count_match: When asserted high by the large count vector 308, a certain signature has caused the counter to reach the threshold.

offending_signature: The signature corresponding to count_match is being asserted high.

analyzer_match; When asserted high, the analyzer has verified that the counter reaching the threshold is not the result of a false positive.

mod1_req: When asserted high, this signal indicates a request to access off-chip memory 212 . This signal remains high while the off-chip memory 212 is being accessed.

mod1_gr: When asserted high, this signal indicates that access to off-chip memory 212 is granted.

mod1_rw: Analyzer 208 reads from off-chip memory 212 when this signal is asserted high and analyzer 208 writes to off-chip memory 212 when this signal is asserted low.

mod1_addr: Indicates the off-chip memory address to read from or write to.

mod1_d_in: Contains the data being read from off-chip memory 212 .

mod1_d_out: Contains the data being written to the off-chip memory 212 .

Analyzer 208 is configured to include a plurality of finite states for off-chip memory 212 access. An illustrative finite state machine for analyzer 208 is shown in FIG. 14 . Each illustrative state depicted in FIG. 14 is explained below.

idle: is the default state of the analyzer 208 . Analyzer 208 transitions out of this state when count_match is asserted high.

prep_for_sram: permission to access off-chip memory 212 is requested in this state. Analyzer 208 transitions out of this state when a license is granted.

send_read_request: As shown in the illustrative example of Figure 14, three send_read_request states are implemented. In all three states where a read request is sent, mod1_rw is asserted high and mod1_addr is set to the value derived from the hash of offending_signature.

wait1: waiting for data to be read from the off-chip memory 212 .

read_data_from_sram: Data from off-chip memory 212 is read into temporary registers on mod1_d_in.

check_match: Temporary registers are concatenated and compared with offending_signature. If these two are equal, analyzer_match is asserted high and analyzer 208 transitions back to idle. If the two are not equal, the parser 208 writes the new string back to memory.

send_write_request: mod1_rw is asserted low, and like read status, mod1_addr is set to the value derived from the hash of offending_signature.

Every transition in analyzer 208 occurs on a clock edge once mod1_gr goes high.

Off-chip memory 212 is used to store the full string (unhashed version), which in the illustrative example is 10 bytes (80 bits) long. Analyzer 208, while hundreds of times faster than software, still requires several additional clock cycles to access off-chip memory 212, which may stall the data processing pipeline. In the illustrative example, accessing a 10-byte string in off-chip memory 212 requires 13 clock cycles.

Circuitry may be implemented that stalls the data processing pipeline whenever a memory read is performed from off-chip memory 212 . However, stalling the pipeline has disadvantages. The purpose of hashing the byte window relative to the entire packet payload is to handle the case of polymorphic worms. But consider the more general case of non-polymorphic worms, where the packet payloads of the worm traffic are nearly identical. In this case, the method and system according to the present invention can generate a series of consecutive matches for the entire packet payload. Stalling the pipeline for each match can then cause severe throughput degradation since each off-chip memory 212 access takes multiple clock cycles. In fact, doing so may benefit the attacker, since the system administrator may be forced to shut down the system. In the illustrative example, the solution is not to stall the pipeline when reading from off-chip memory 212, but to skip further store operations until the previous operation has completed. Therefore, once an alert is generated, the data over the next 13 clock cycles (latency involved in reading and writing back into off-chip memory 212) will not cause further alerts to be generated.

During the measurement interval, the number of observed signatures can be approximately equal to the number of characters processed. The number of characters processed may be lower because a small number of characters are skipped due to bank RAM conflicts. The problem of determining a threshold given the length of the measurement interval can be reduced to determining a bound on the probability that when m elements are hashed to a table with b buckets, the number of elements hashed to the same bucket exceeds probability of i. The bound is given by:

$\mathrm{<span\; class="notranslate">\; b</span>}{<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; em</span>}}{\mathrm{<span\; class="notranslate">\; ib</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; i</span>}}$

In an illustrative example, m signatures are hashed to b counters. In the above expression, i is a threshold. Thus, given the length of the measurement interval, the threshold can be varied such that the upper bound on the probability of the counter exceeding the threshold is acceptably small. This in turn reduces the number of unnecessary off-chip memory 212 accesses. Thus, since the incoming signature randomly hashes to the value of the counter, an irregular signature for a suitably large threshold may cause the value of the counter to exceed said predetermined threshold. The probability that the counter receives exactly i elements can be given by:

$\left(\begin{array}{c}\mathrm{<span\; class="notranslate">\; m</span>}\\ \mathrm{<span\; class="notranslate">\; i</span>}\end{array}\right){<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; b</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; i</span>}}{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; b</span>}}<span\; class="notranslate">\; )</span>}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; \&le;</span>\left(\begin{array}{c}\mathrm{<span\; class="notranslate">\; m</span>}\\ \mathrm{<span\; class="notranslate">\; i</span>}\end{array}\right){<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; b</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&le;</span><span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; me</span>}}{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>{<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; b</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; =</span>{<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; me</span>}}{\mathrm{<span\; class="notranslate">\; bi</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; i</span>}}$

The second inequality is a consequence of the upper bound on the binomial coefficient. The probability that the value of the counter is at least i can be given by:

$\mathrm{<span\; class="notranslate">\; PR</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; \&Greater\; Equal;</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&le;</span>\underset{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; i</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; em</span>}}{\mathrm{<span\; class="notranslate">\; bk</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; \&le;</span>{<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; em</span>}}{\mathrm{<span\; class="notranslate">\; ib</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; +</span><span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; em</span>}}{\mathrm{<span\; class="notranslate">\; ib</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; em</span>}}{\mathrm{<span\; class="notranslate">\; ib</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; em</span>}}{\mathrm{<span\; class="notranslate">\; ib</span>}}<span\; class="notranslate">\; )</span>}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; ]</span>$

The term in square brackets approaches 1 as i increases. Therefore, the probability that the value of the counter is at least i can be bounded by:

$\mathrm{<span\; class="notranslate">\; b</span>}{<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; em</span>}}{\mathrm{<span\; class="notranslate">\; ib</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; i</span>}}$

In the illustrative embodiment, since the measurement interval m is 2.5 megabytes, the number of counters b is 8192, and the predetermined threshold i is 850, the probability of counter overflow for random traffic flow ranges from 1.02 x 10 ⁻⁹ . Accordingly, the probability of counter overflow is as low as desired for the traffic processed during the interval.

Upon receiving an alert message from analyzer 208, alert generator 214 sends a user datagram protocol (UDP) control packet to an external data processing system listening on a known UDP/IP port. The packet may contain the malicious signature (a string of bytes for which to hash). The alarm generator 214 issues this control packet when analyzer_match is asserted high. From this, the most frequently occurring strings can then be marked as suspicious. FIG. 15 is a block diagram of an illustrative control packet 1502 sent from the alert generator 214 .

Therefore, the method and system according to the present invention detect frequently occurring signatures in network communication traffic. By implementing content detection in hardware, high throughput can be achieved. Furthermore, by taking advantage of the parallelism provided by the hardware, larger volumes of traffic can be scanned as compared to typical software-based approaches. Throughput is maintained by parallel hashing of several byte windows to on-chip block memories, where each on-chip block store can be updated in parallel. This differs from traditional software-based approaches, where a hash followed by a counter update may require several instructions to be executed sequentially. Furthermore, using an off-chip memory analyzer provides a low false positive rate. Doing multiple hashes per packet also helps the system hinder simple polymorphic measurements.

Previous network monitoring tools relied on a system administrator's intuition to detect anomalies in network traffic traffic. The method and system according to the present invention automatically detect peaks in network communication traffic corresponding to frequently occurring content.

The foregoing descriptions of implementations of the present invention have been presented for purposes of illustration and description. This is not exhaustive and does not limit the invention to the precise forms disclosed. Modifications and variations are possible in light of the above teachings or may be obtained through practice of the invention. For example, the described implementations include software, but current implementations may be implemented as a combination of hardware and software or by hardware alone. Furthermore, the illustrative processing steps performed by the programs may be performed in an order different from that described above, and may include additional processing steps. The scope of the invention is defined by the claims and their equivalents.

When referring to elements of the invention or its preferred embodiment(s), "a", "an", "the" and "said" mean that there are one or more of that element. The terms "comprising", "comprising" and "having" are meant to be inclusive and mean that there may be additional elements other than the listed elements.

As various changes could be made in the above constructions without departing from the scope of the invention, all matter contained in the above description or shown in the accompanying drawings shall be interpreted as illustrative and not in a restrictive sense.

Claims (33)

1. method that in data handling system, is used for the duplicate contents of identification data stream, described method comprises step:

Be at least one the part compute Hash functions in a plurality of parts of described data stream;

In response to institute's computed hash function result, increase the value of at least one counter in a plurality of counters, each counter is corresponding to respective computed hash function result;

When surpassing predetermined count value, the value of at least one counter in described a plurality of counters identifies described duplicate contents; And

The duplicate contents that checking is identified is not optimum string.

2. the method for claim 1 is wherein calculated a plurality of hash functions of a plurality of part parallels ground calculating that described hash function is included as described data stream.

3. method as claimed in claim 2, wherein said a plurality of counter bit are in a plurality of memory banks.

4. method as claimed in claim 3 also comprises step:

When a plurality of counters that are arranged in same bank will be increased in the identical clock period, determine the priority which counter is increased.

5. the method for claim 1 also comprises step:

Filter at least one part in a plurality of parts of described data stream to remove predetermined data.

6. the method for claim 1 also comprises step:

Usage count on average comes periodically to reduce the value of each counter in described a plurality of counter.

7. the method for claim 1 also comprises step:

Determine whether the duplicate contents that is identified is false sign.

8. method as claimed in claim 7 is wherein by comparing the duplicate contents that is identified to determine whether the duplicate contents that is identified is false sign with the duplicate contents of previous sign.

9. method as claimed in claim 8, the duplicate contents of wherein previous sign are stored in the storer away from local storage, and this local storage comprises the duplicate contents that is identified.

10. the method for claim 1 wherein uses streamline to increase the value of at least one counter in described a plurality of counter.

11. the method for claim 1, wherein said duplicate contents are the worm condition codes.

12. the method for claim 1, wherein the duplicate contents that is identified has non-predefined condition code.

13. the method for claim 1, wherein said duplicate contents is a virus signature.

14. the method for claim 1, wherein said duplicate contents is a Spam signatures.

15. the method for claim 1, wherein said duplicate contents are the contents via the network repeated exchanged.

16. the method for claim 1, wherein said duplicate contents are the user's of a plurality of access websites appearance.

17. a system that is used for identification data stream duplicate contents, described system comprises:

The hash function counting circuit is used at least one the part compute Hash functions in a plurality of parts of described data stream;

A plurality of counters in response to institute's computed hash function result, increase the value of at least one counter in a plurality of counters, and each counter is corresponding to respective computed hash function result;

The duplicate contents concentrator marker is used for identifying described duplicate contents when the value of at least one counter of described a plurality of counters surpasses predetermined count value; With

Validator is used to verify that the duplicate contents that is identified is not optimum string.

18. a plurality of hash functions of a plurality of part parallels ground calculating that described hash function is included as described data stream wherein calculate in system as claimed in claim 17.

19. system as claimed in claim 18, wherein said a plurality of counter bit are in a plurality of memory banks.

20. system as claimed in claim 19 comprises:

Priority encoder is used for determining the priority which counter is increased when a plurality of counters that are positioned at same bank are increased.

21. system as claimed in claim 17 comprises:

Filtrator, at least one part of a plurality of parts that is used for filtering described data stream is to remove predetermined data.

22. system as claimed in claim 17, wherein usage count on average comes periodically to reduce the value of each counter in described a plurality of counter.

23. system as claimed in claim 17 comprises:

Analyzer is used to determine whether the duplicate contents that is identified is false sign.

24. system as claimed in claim 23 is wherein by comparing the duplicate contents that is identified to determine whether the duplicate contents that is identified is false sign with the duplicate contents of previous sign.

25. system as claimed in claim 24, the duplicate contents of wherein previous sign is stored in the storer away from local storage, and this local storage comprises the duplicate contents that is identified.

26. system as claimed in claim 17 wherein uses streamline to increase the value of at least one counter in described a plurality of counter.

27. system as claimed in claim 17, wherein said duplicate contents is the worm condition code.

28. system as claimed in claim 17, wherein the duplicate contents that is identified has non-predefined condition code.

29. system as claimed in claim 17, wherein said duplicate contents is a virus signature.

30. system as claimed in claim 17, wherein said duplicate contents is a Spam signatures.

31. system as claimed in claim 17, wherein said duplicate contents is the content via the network repeated exchanged.

32. system as claimed in claim 17, wherein said duplicate contents is the user's of a plurality of access websites appearance.

33. a system that is used for the duplicate contents of identification data stream, described system comprises:

Be used to the device of at least one the part compute Hash functions in a plurality of parts of described data stream, at least one part of described data stream is therefrom removed optimum character to prevent that optimum string is designated duplicate contents;

Be used for increasing in response to institute's computed hash function result the device of value of at least one counter of a plurality of counters, each counter is corresponding to respective computed hash function result;

Be used for when the value of at least one counter of described a plurality of counters surpasses predetermined count value, identifying the device of described duplicate contents; With

Be used to verify that the duplicate contents that is identified is not the device of optimum string.

Images