JP2011171995A - Device, method, and program for discriminating data - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To attain data discrimination with a small storage capacity, where a Bloom filter without the necessity of high frequency decrement is used. <P>SOLUTION: A data discrimination device discriminates whether input data belongs to a prescribed data aggregation or not by comparing the set of hash values to be obtained by applying a plurality of hash functions to the input data with the value of a corresponding element in the Bloom filter. Each element of the Bloom filter has a plurality of bits. When the Bloom filter is updated by adding new data to the prescribed data aggregation, the value of each element in the Bloom filter corresponding to the set of the hash values to be obtained by applying the plurality of hash functions to the added data is incremented by a prescribed probability which is larger than zero and smaller than one. <P>COPYRIGHT: (C)2011,JPO&INPIT

Description

  The present invention belongs to a technique for determining whether or not data such as a packet transferred on a network belongs to a predetermined data set.

  Conventionally, as a technique for discriminating a packet, for example, there is a technique called “Deep Packet Inspection” in which application layer data of a packet is handled and a discrimination process or the like is performed. This is a technique that can determine a character string pattern at high speed by using an automaton or the like. Further, as a method for detecting a pattern having a variable length at a high speed, there is a method using a Bloom filter (hereinafter also referred to as “BF”) (see Non-Patent Document 1).

  In BF, a plurality of sample data is classified into a positive example (data to be correct) and a negative example (data to be incorrect), and for example, the correct example is stored in a buffer by applying a plurality of hash functions. This makes it possible to determine whether or not new data is included in the positive example.

  Specifically, when BF is realized, for example, a bit array (M Bloom filter in the initial state) of length M bits that is initially initialized to “0 (zero)” and k different hash functions f1, f2,..., fk and a plurality of sample data are used. For example, FIG. 10A shows a 7-bit Bloom filter in the initial state.

  Then, for a certain sample data, first hash values hf1, hf2,..., Hfk are obtained by the k hash functions. Then, a second hash value (remainder) obtained by dividing these first hash values by M is obtained, and a process is performed in which each bit on the bit array corresponding to each obtained second hash value is set to “1”. These are performed for each sample data. That is, many “1” s are arranged in the bit array.

  For example, in FIG. 10B, for two sample data, a 7-bit bit array ((b1) and (b2)) in which the value of the element (determination target part) corresponding to the second hash value is “1”. Represents. Then, a process of reflecting the bit “1” in the bit array (b1) and the bit array (b2) is performed on the Bloom filter in the initial state shown in FIG. Then, the Bloom filter shown in FIG.

  Next, for the new discrimination target data, first hash values hf1, hf2,..., Hfk are obtained by the k hash functions, and the first hash values are divided by M. 2 Hash value (remainder) is obtained. Then, each bit value on the bit array corresponding to each of the obtained second hash values is referred to and it is determined whether or not all of them are “1”. If all of these are “1”, it is determined that the determination target data is included in the sample data set. On the other hand, if any one is not “1”, it is determined that the determination target data is not included in the sample data set.

  For example, the new discrimination target data is one of the two sample data described above, and here, the bit arrangement based on the second hash value for the data is shown in (d1) (same as (b1)) Suppose that Then, it is the first element, the fourth element, and the fifth element that have the bit “1” in the bit array (d1). Since the values of the first element, the fourth element, and the fifth element in the Bloom filter shown in FIG. 10C are all “1”, the determination target data is included in the sample data set. judge. This judgment result is correct.

  On the other hand, for example, it is assumed that new discrimination target data is NG data (data other than sample data), and the bit arrangement based on the second hash value for the data is as shown in (d2). Then, it is the second element, the third element, and the seventh element that have the bit “1” in the bit array (d2). In the Bloom filter shown in FIG. 10C, the values of the second element and the seventh element are “1”, but the value of the third element is “0” and not “1”. Therefore, it is determined that the determination target data is not included in the sample data set. This judgment result is correct.

  However, the BF of Non-Patent Document 1 has a property that false positives increase every time sample data is added to a positive example. That is, as the number of “1” bits on the Bloom filter increases, the value of each corresponding element in the Bloom filter is also “1” for NG data, and is included in the sample data set. It may be judged.

  For example, it is assumed that new discrimination target data is NG data, and the bit arrangement based on the second hash value for the data is as shown in (d3) of FIG. Then, it is the first element, the second element, and the seventh element that have the bit “1” in the bit array (d3). Since the values of the first element, the second element, and the seventh element in the Bloom filter shown in FIG. 10C are all “1”, the determination target data is included in the sample data set. judge. However, this determination result is incorrect.

  In order to solve this, there is a method of using a plurality of bits for one element of a Bloom filter, for example, called a count Bloom filter (hereinafter referred to as “CBF”) (see Non-Patent Document 2). . For example, FIG. 10E shows a CBF that uses 3 bits for one element of a Bloom filter.

  Specifically, in the technique of Non-Patent Document 2, by using the fact that there is a plurality of bits in one element of the Bloom filter, there is an addition of sample data to the positive example and there is an overlap of the value of the second hash value. The value of the element corresponding to is incremented. Further, the values of all elements are decremented when a predetermined time elapses. Thereby, it becomes a positive example with high possibility of leaving the new and high frequency sample data, and it becomes possible to suppress the increase in false positives.

Sarang Dharmapurikar, et al., “Deep Packet Inspection using Parallel Bloom Filters”, IEEE Micro, IEEE Computer Society, January / February 2004, Volume24, Issue 1, p.52-61 Gianni Antichi, et al., “Counting Bloom Filters for Pattern Matching and Anti-Evasion at the Wire Speed”, IEEE Network Magagine, IEEE Computer Society, January / February 2009, Volume23, Issue 1, p.30-35

  However, since the CBF of Non-Patent Document 2 uses a plurality of bits for each element, it is possible to count the value of a certain amount of elements. There was a disadvantage that it reached the point, and it was necessary to decrement frequently. If it does so, even if it was a short period, there was a problem that the unreachable data in that period would be deleted from the CBF by decrement.

  In addition, in order to avoid this problem, there is a method in which many bits are assigned to each element of the Bloom filter so that the value of the element corresponding to a large amount of data does not reach the upper limit immediately. However, in that case, there is a problem that the storage capacity required for the CBF increases, which is not preferable.

  Therefore, the present invention has been made in view of the above-described problems, and an object thereof is to realize data discrimination using a Bloom filter that does not require high-frequency decrement with a small storage capacity.

  In order to solve the above problem, the present invention compares a set of hash values obtained by applying a plurality of hash functions to input data with the value of a corresponding element in a Bloom filter, and A data discriminating apparatus for discriminating that input data belongs to a predetermined data set if there is no zero in an element value in a Bloom filter corresponding to a set, wherein the Bloom filter has elements each having a plurality of bits When updating a Bloom filter stored in the storage unit by adding new data to a predetermined data set and a storage unit stored as a hash value obtained by applying a plurality of hash functions to the added data The value of each element in the Bloom filter corresponding to the set of is incremented with a predetermined probability greater than 0 and less than 1. Characterized in that it comprises a processing unit for cement, the.

  According to this invention, when new data is added to a predetermined data set to update the Bloom filter, the Bloom filter corresponding to a set of hash values obtained by applying the plurality of hash functions to the added data. By incrementing the value of each element at a predetermined probability greater than 0 and less than 1, the possibility that the value of each element reaches the upper limit value can be reduced, and a Bloom filter that does not require frequent decrement Can be realized with a small storage capacity.

  In addition, the present invention is characterized in that, when the value of each element in the Bloom filter is incremented with a predetermined probability, the processing unit increments the value of the element with a lower probability as the element value is larger.

  According to this invention, when the value of each element in the Bloom filter is incremented with a predetermined probability, the value of each element reaches the upper limit value by incrementing the value of the element with a lower probability as the element value increases. The possibility can be further reduced, and when the value of the element is small, it is incremented with a high probability, so that the discrimination accuracy of the Bloom filter can be further increased.

  Further, the present invention is characterized in that the processing unit decrements the values of all elements every predetermined time.

  According to such an invention, by decrementing every predetermined time, a number that can be substantially counted by each element while avoiding a situation in which a long time elapses after the value of each element reaches the upper limit with a light processing load. Can be increased.

  The present invention is also characterized in that the processing unit decrements all element values when any of the element values in the Bloom filter reaches an upper limit value.

  According to this invention, when any of the element values in the Bloom filter reaches the upper limit value, the value of each element can be decremented at an appropriate timing, and the value of each element becomes the upper limit value. It is possible to increase the number that can be substantially counted by each element while more reliably avoiding a situation in which a long time has passed since reaching the value.

  In the present invention, the storage unit stores a Bloom filter corresponding to each predetermined IP address, and when the processing unit accepts input data, the Bloom filter corresponding to the destination IP address of the input data is stored. And performing the discrimination.

  According to this invention, it is possible to further reduce the possibility that the value of each element of the Bloom filter reaches the upper limit value by using a separate Bloom filter for each destination IP address of the input data.

  The present invention is also a program for operating a computer as a data discrimination device. According to this invention, a computer in which this program is installed can be operated as a data discrimination device.

  According to the present invention, data discrimination using a Bloom filter that does not require frequent decrementing can be realized with a small storage capacity.

It is a figure which shows the connection relation of the data discrimination | determination apparatus in this embodiment, and another apparatus. It is a functional block diagram of a data discrimination device. It is a sequence diagram of operation | movement of a terminal and a data discrimination device. It is explanatory drawing of the data addition to the buffer for positive / negative examples. It is explanatory drawing of the increment probability at the time of adding data to the buffer for positive / negative examples. It is explanatory drawing of the decrement in the buffer for positive / negative examples. It is a flowchart which shows the operation | movement which adds data to the buffer for positive / negative examples. It is explanatory drawing of the example of application of a data discrimination device. It is explanatory drawing of the example of application of a data discrimination device. It is explanatory drawing of a Bloom filter.

  DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, modes for carrying out the present invention (hereinafter referred to as “embodiments”) will be described in detail with reference to the drawings (refer to drawings other than the referenced drawings as appropriate).

  As shown in FIG. 1, the terminals 2a (2) and 2b (2) access the server 3 by transmitting and receiving request and response packets via the network 4, and the data discriminating apparatus on the path. 1 is arranged.

  As shown in FIG. 2, the data discriminating apparatus 1 which is a computer apparatus includes a packet receiving unit 11, a packet assembling unit 12, a data hash unit 13 (processing unit), a filter DB (Data Base) 14 (storage unit), and a filter check. Unit 15 (processing unit), redirect generation unit 16, packet transfer unit 17, and authentication unit 18, which are CPU (Central Processing Unit), RAM (Random Access Memory), ROM (Read Only Memory), HDD (Hard Disk) Drive) and various interfaces. The operation of each part will be described later with reference to FIG.

  In FIG. 2, the packet reception unit 11 receives the packet from the terminal 2 and transmits the packet from the packet transfer unit 17 to the server 3, but conversely, the packet reception from the server 3 is received. Similar processing is performed when the packet is received by the unit 11 and transmitted from the packet transfer unit 17 to the terminal 2.

  Next, with reference to FIG. 3, the sequence of the operation | movement which adds sample data to a positive example in the data discrimination device 1 is demonstrated.

<(A) Processing when conditions are not met>
As shown in FIG. 3, the packet (stream) transmitted from the terminal 2 is received by the packet receiving unit 11 and passed to the packet assembling unit 12 (step S11). The packet assembling unit 12 constructs the received plurality of packets into data at the L (layer) 3 or L4 level (step S12), and passes the constructed data to the next data hash unit 13 (step S13).

  In the data hash part 13, a hash function is applied using the specific location of the constructed | assembled data, a bit sequence is produced | generated, and it passes to the filter test | inspection part 15 (step S14). The filter checking unit 15 makes a request to the filter DB 14 (step S15) while referring to the positive / negative example buffers (positive example buffer and negative example buffer) (step S16), and whether or not this bit string corresponds to the positive example. Determine whether. In step S16, it may be determined whether or not this bit string corresponds to the positive example with reference to only the positive example buffer.

  When the filter checking unit 15 does not determine that this bit string is a positive example (it is incompatible with the conditions) (step S17), the filter checking unit 15 discards the packet before construction and recognizes the redirect packet generated by the redirect generation unit 16 as an authentication unit. 18 (step S18).

<(B) Authentication process>
The authentication unit 18 causes the terminal 2 to display an authentication screen including a pop-up or the like, and inquires whether or not to additionally register the data that does not meet the conditions in step S17 as sample data in the positive example buffer (step S21). . When a reply from the terminal 2 is received by the user's operation (step S22), the authentication unit 18 adds a bit string corresponding to the data (created by the data hash unit 13, details will be described later) to the positive example buffer. (Step S23). Further, the authentication unit 18 transmits a redirect packet to the terminal 2 (step S24).

<(C) Processing when conditions are met>
The terminal 2 that has received the redirect packet transmits the same packet (stream) again (step S31). Since the process of steps S32 to S36 is the same as the process of steps S12 to S16, the description thereof is omitted.

  After step S36, the filter checking unit 15 determines whether or not the received bit string corresponds to the positive example, but unlike the case of step S17, the bit string corresponding to the data is additionally registered in the positive example buffer. Therefore, the received bit string conforms to the positive example buffer (condition) (step S37).

  The filter inspection unit 15 passes the data to the packet transfer unit 17 (step S38), and the packet transfer unit 17 transfers the data to the original destination server 3 (step S39).

  If there is a reply of No in step S22, a bit string corresponding to the data may be additionally registered in the negative example buffer in step S23.

  Next, the processing image of step S23 in the sequence of FIG. 3 will be described with reference to FIG. As shown in FIG. 4, first, the bit string generated by the data hash unit 13 (hereinafter also referred to as “generated bit string”) is 7 elements, 3 bits / element, and the hash function for BF is 4 An example will be described.

  Since there are four hash functions for BF, the value of four elements among the seven elements in the generated bit string is “001”. In addition, the “set of hash values” in the claims refers to a set of elements that are “001” in the generated bit string (the set of second hash values described above).

  When the reply content in step S22 is Yes, the generated bit string is added to the positive example buffer. If the reply content in step S22 is No, the generated bit string may be added to the negative example buffer.

  Next, referring to FIG. 5, the increment probability in each element when data is added to the positive / negative example buffer (positive example buffer or negative example buffer; hereinafter also simply referred to as “buffer”). explain. As shown in FIG. 5, when the generated bit string is added to the positive / negative example buffer, the addition is performed for each element, and the increment probability is calculated independently for each element.

The increment probability for each element is calculated based on the value of the element currently contained in each element of the buffer. Here, a case where the increment probability is proportional to the value power of an element of a predetermined base (m: 0 <m <1) will be described as an example. For example, as shown in FIG. 5, in the first element, since the value of the element is “011 (“ 3 ”in decimal number)”, “m ³ ” is the increment probability. When the element value is “111” and the upper limit (maximum value) as in the fifth element, the increment probability is exceptionally set to “0”.

  In this way, since the increment probability decreases as the element value increases, the probability that the element value reaches the upper limit value can be kept low. That is, the frequency of decrementing the values of all elements can be greatly reduced.

  Next, decrement in the positive / negative example buffer will be described. As shown in FIG. 6, when several bits are added to the positive / negative example buffer after a while and then the positive / negative example buffer is decremented, the values of all elements are uniformly “1”. "Is subtracted. However, elements that are already “0” are set to “0” as they are.

  As a result, the same effect as that obtained by multiplying the upper limit of the number of storage in each element by 1 / m times (or twice if m is 1/2) can be obtained. That is, it is possible to leave a new bit string reflected in the buffer without changing the relative ratio of the values of the elements.

  Next, the operation of adding data to the positive / negative example buffer (corresponding to step S23 in FIG. 3) will be described. As shown in FIG. 7, the data hash unit 13 generates a bit string by applying a hash function to the data constructed from the packet (step S101), and performs the processes of steps S103 and S104 for each element in the bit string ( Steps S102 to S105).

  The data hash unit 13 determines whether or not a bit of the bit string is raised (“1”) for a certain element (step S103). If Yes, the process proceeds to step S104, and if No, step S104 is performed. Is skipped and the process proceeds to the next element process (next step S103).

  As described with reference to FIG. 5, the data hash unit 13 increments the value of the element with an increment probability corresponding to the value of the element (step S <b> 104), and proceeds to processing of the next element (next step S <b> 103). move on.

  Thus, according to the data discrimination device 1 of the present embodiment, in the data discrimination using the Bloom filter, the value of each element is incremented with a predetermined increment probability, so that the Bloom filter that does not require frequent decrement is required. Can be realized with a small storage capacity.

  That is, for example, when each element of a buffer (Bloom filter) is 3 bits, in the conventional technique, when seven bit strings with bits are applied to a certain element, the value of that element in the buffer is an upper limit value (binary number). To "111"). On the other hand, in the data discriminating apparatus 1 according to the present embodiment, when the base m is “1/2” under the same conditions, one bit string is used even though the element value is changed from “000” to “001”. , The average value of the bit string is 2 for the element value from “001” to “010”, the average of the bit string is 4 for the element value from “010” to “011”, and so on. In order to increase one, the average of 8, the average of 16, the average of 32, and the average of 64, that is, a total of 127 bit strings are required until the value of the element in the buffer reaches the upper limit value.

Generally speaking, when each element of a buffer (bloom filter) is i bits, according to the prior art, when (2 ⁱ −1) bit strings having a bit are applied to an element, The value reaches the upper limit. On the other hand, in the data discriminating apparatus 1 of the present embodiment, when {(1 / m) ^ (2 ⁱ −1) −1} bit strings are applied in the case of the base m under the same conditions, the buffer The value of that element in reaches the upper limit. Thus, according to the Bloom filter in the data discriminating apparatus 1 of the present embodiment, even if the number of bits of each element is the same, the number that can be substantially counted by each element can be dramatically increased as compared with the prior art. There is an effect.

  The base m may be set as appropriate as long as the administrator of the data discrimination device 1 satisfies “0 <m <1”. Specifically, if importance is placed on reducing the probability that an element value will reach the upper limit value, m may be set to a small value, and if importance is placed on reducing the possibility of information loss due to decrement. What is necessary is just to set m to a large value. In the claims, “the value of each element in the Bloom filter is incremented with a predetermined probability larger than 0 and smaller than 1”, but this is 1 when the value of the element is 0. It is not excluded that it is incremented by probability or not incremented when the value of the element is the upper limit value.

  The decrement timing may be, for example, every predetermined time or when any of the element values in the Bloom filter reaches the upper limit value. For example, when decrementing every predetermined time, the processing load can be reduced. Further, when decrementing when any of the element values in the Bloom filter reaches the upper limit value, it is possible to more reliably avoid a situation where a long time elapses after the value of each element reaches the upper limit value.

  If a program for causing the data discriminating apparatus 1 to be executed is created and installed in the data discriminating apparatus 1, the data discriminating apparatus 1 can realize each function based on the program.

(Application example)
Next, an application example of the data discrimination device 1 according to the present embodiment will be described. FIG. 8 shows a case where the data discriminating apparatus 1 is applied to a system that discriminates users related to a NAT (Network Address Translation) apparatus 5 and a proxy apparatus 6 on the network 4.

  There are many NAT devices 5 and proxy devices 6 on the network 4, and the total number of users is enormous. Therefore, even in the data discriminating apparatus 1 of the present embodiment, the number of positive / negative example buffers can be increased rather than constructing a single positive / negative example buffer for all NAT apparatuses 5 and proxy apparatuses 6. Dividing into crab can reduce false positives more.

  Therefore, a positive / negative example buffer is provided for each IP address of the NAT device 5 or the proxy device 6. For example, in the data discriminating apparatus 1, separate positive / negative example buffers (positive example buffer and negative example) are used for the NAT device 5 whose IP address is “A” and for the proxy device 6 whose IP address is “B”. Have a buffer).

  In addition, a cookie (part of the HTTP body) included in an HTTP (Hyper Text Transfer Protocol) request is assumed as a target to which the hash function is applied in the data hash unit 13. This is because, basically, the same cookie is often assigned to destinations in the same domain, so that users can be distinguished.

  FIG. 9 shows a service example using the data discrimination device 1. In the example of FIG. 9A, the data discrimination device 1 cooperates with the firewall device 7 on the network 4 (NW), distinguishes the user of the NAT device 5, and the firewall device 7 in the case of access from a specific user. Block communication (“×”).

  Further, in FIG. 9B, the data discrimination device 1 cooperates with a DPI (Deep Packet Inspection) device 8 and an advertisement server 9 existing on the network 4 to perform an appropriate advertisement according to the user of the proxy device 6. Represents the service to be inserted. The DPI device 8 is a network device that can rewrite the contents of the transferred packet. Realizing advertisement distribution on the network side by notifying the user information identified by the data discriminating apparatus 1 to the DPI apparatus 8 and modifying the packet so that the advertisement server 9 inserts advertisement data corresponding thereto. Is possible.

Although description of this embodiment is finished above, the aspect of the present invention is not limited to these.
For example, the increment probability may be lower as the element value is larger, as in the above example, but is not limited to this. For example, when each element of the buffer is 3 bits, the increment probability is 2/3 when the element value is “000” to “010”, and the increment probability is 1/3 when “011” to “111”. For example, the increment probability may be set stepwise. In addition, the increment probability may be appropriately set to a predetermined probability by the administrator of the data discrimination device 1.
Further, in the data discriminating apparatus 1, a plurality of Bloom filters and a plurality of parallel processors may be prepared to perform parallel processing regarding data discrimination.

Further, the present invention can be applied to a traffic analysis technique in order to make it possible to grasp a traffic trend of a packet.
Further, the present invention can be applied to the field of machine learning because data identification is performed with a fixed calculation amount.

Further, the present invention can be applied to a stream processing technique because high-speed identification is possible for a large number of packets.
In addition, about a concrete structure, it can change suitably in the range which does not deviate from the main point of this invention.

DESCRIPTION OF SYMBOLS 1 Data discrimination apparatus 2a, 2b, 2 terminal 3 Server 4 Network 5 NAT apparatus 6 Proxy apparatus 7 Firewall apparatus 8 DPI apparatus 9 Advertising server 11 Packet receiving part 12 Packet assembly part 13 Data hash part (processing part)
14 Filter DB (storage unit)
15 Filter inspection unit (processing unit)
16 redirect generation unit 17 packet transfer unit 18 authentication unit

Claims (7)

A set of hash values obtained by applying a plurality of hash functions to input data is compared with the value of the corresponding element in the Bloom filter, and the value of the element in the Bloom filter corresponding to the obtained set of hash values is compared. A data discriminating apparatus that discriminates that the input data belongs to a predetermined data set if there is no zero.
A storage unit for storing the Bloom filter as a configuration in which each of the elements has a plurality of bits;
When updating the Bloom filter stored in the storage unit by adding new data to the predetermined data set, it corresponds to a set of hash values obtained by applying the plurality of hash functions to the added data A processing unit that increments the value of each element in the Bloom filter with a predetermined probability greater than 0 and less than 1;
A data discriminating apparatus comprising: The processor is
The data determination apparatus according to claim 1, wherein when the value of each element in the Bloom filter is incremented with a predetermined probability, the value of the element is incremented with a lower probability as the element value is larger. The processor is
The data discriminating apparatus according to claim 1 or 2, wherein the values of all the elements are decremented every predetermined time. The processor is
The data discriminating apparatus according to claim 1 or 2, wherein when any of the element values in the Bloom filter reaches an upper limit value, the values of all the elements are decremented. The storage unit
The Bloom filter corresponding to each predetermined IP (Internet Protocol) address is stored,
The processor is
The data according to any one of claims 1 to 4, wherein when the input data is received, the determination is performed using the Bloom filter corresponding to a destination IP address of the input data. Discriminator. A set of hash values obtained by applying a plurality of hash functions to input data is compared with the value of the corresponding element in the Bloom filter, and the value of the element in the Bloom filter corresponding to the obtained set of hash values is compared. A data discriminating method by a data discriminating apparatus that discriminates that the input data belongs to a predetermined data set if there is no zero.
The data determination device includes a storage unit that stores the Bloom filter as a configuration in which each of the elements has a plurality of bits, and a processing unit.
The processor is
When updating the Bloom filter stored in the storage unit by adding new data to the predetermined data set, it corresponds to a set of hash values obtained by applying the plurality of hash functions to the added data A value of each element in the Bloom filter is incremented with a predetermined probability greater than 0 and less than 1. A data discrimination method.   A program for causing a computer to operate as the data discriminating apparatus according to any one of claims 1 to 5.

Images