JP5745464B2 - Access history storage and retrieval apparatus and method - Google Patents

Description

  The present invention relates to an access history storage and retrieval apparatus and method, and more particularly, to an access history storage and retrieval apparatus and method for creating an access history that holds which destination accessed which destination by using fewer resources. .

  In network operation, it is important to record user access history. For example, by recording an access history, it is possible to know when and which user has accessed which access destination. For example, when a malicious site such as phishing is discovered, it is possible to grasp the user who has accessed the site, understand the range of influence, and warn the accessing user. It is desirable to record the access history for a long period of time because discovery of such malicious sites may be delayed.

  The simplest method of recording the access history is to save all sets of transmission sources and communication destinations (destinations). However, in a large-scale network, the number of source-destination combinations is enormous, and a large amount of resources are required for storage. For this reason, it is difficult to record the access history for a long period of time by a simple method.

There is a Bloom filter as a data structure for efficiently storing a large amount of elements (for example, see Non-Patent Document 1), and it is used in various network applications (for example, see Non-Patent Document 2).
Access history can be recorded and searched by checking all elements that can be inserted using the Bloom filter. Specifically, first, a source-destination pair is inserted into the Bloom filter as an element. When you want to enumerate the senders that have accessed a certain destination, you can create a sender-destination pair for all the senders (all users in the network) that can access it, and search whether they have been inserted in the Bloom filter. .

B. Bloom, "Space / Time Tradeoffs in Hash Coding with Allowable Errors," Communications of the ACM, 1970. A. Broder and M. Mitzenmacher, "Network Applications of Bloom Filters: A Survey," Internet Mathematics, 2005.

  However, the Bloom filter may be erroneously detected as being present even if no element is inserted due to its characteristics. Depending on the parameters of the Bloom filter, a large number of senders that are not actually accessed may appear. Since the occurrence probability of erroneous detection depends on the number of elements to be inserted, the data size of the Bloom filter, and the like, the data size may be increased sufficiently to reduce the occurrence probability of erroneous detection. However, depending on the number of elements to be inserted, a large amount of resources are required for storage even if a Bloom filter is used.

  The present invention has been made in view of the above points, and it is an object of the present invention to provide an access history storage and retrieval apparatus and method capable of storing a huge access history with a small number of resources and performing a search with high accuracy. And

To solve the above problems, the present invention (Claim 1) is an access history storage and retrieval device for storing and retrieving the access history is represented by a combination of source and destination,
When the collected source set S and destination set D are given, the S and the D are respectively stored in the storage means, and the combination of the S and the D that is observed to be actually accessed is stored. Is inserted into the Bloom filter as an element, and the access history recording means for storing in the storage means,
Search means for searching the storage means based on a certain input destination and outputting the accessed transmission source, or searching for the storage means based on a certain transmission source and outputting the accessed destination and, the possess,
The access history recording means includes
When storing the access history using the Bloom filter in the storage means,
An element including a destination with a smaller number of accessed sources increases the number k of hash functions at the time of insertion into the Bloom filter, or an element including a source with a smaller number of accessed destinations at the time of insertion into the Bloom filter. Optimization means for increasing the number k of hash functions is included .

Further, the present invention (Claim 2 ) provides the optimization means,
The number k of the hash functions is
The bit number of the Bloom filter is m,
The total number of elements to be inserted into the Bloom filter is n,
P _i (1 <= i <= n) for the false detection rate for each element,
When K is a vector having k _i (1 <= i <= n) as the number of hash functions for each element,

を用いて決定する手段を含む。

Means for determining using.

Further, the present invention (Claim 3 ) provides the retrieval means,
Means for searching the Bloom filter for all combinations of the destination d and the source S when a destination d is input, and outputting the source that accessed the destination d;
Means for searching the Bloom filter for all combinations of the transmission source s and the destination D and outputting the destination accessed by the transmission source s when a transmission source s is input.

  As described above, according to the present invention, by using a Bloom filter, a huge access history can be held for a long time with a small number of resources. Further, the accuracy of the search result can be improved by determining the number of hash functions for each insertion element of the Bloom filter.

1 is a system configuration diagram according to an embodiment of the present invention. It is a block diagram of the access history recording / retrieval part in one embodiment of this invention. It is a data structure of Bloom filter in one embodiment of the present invention. It is the insertion procedure of the element in the Bloom filter in one embodiment of this invention. It is the element insertion determination procedure of the element in the Bloom filter in one embodiment of the present invention. It is an example of inserting the access history into the Bloom filter in one embodiment of the present invention. It is an example of the search in one embodiment of this invention. It is a figure which shows the deviation of the access number in one embodiment of this invention. It is an example of the optimization of the number of hash functions for every insertion element in one embodiment of this invention.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings.

  The present invention uses a Bloom filter that is used as a data structure for efficiently storing a large number of elements, and among the combinations of a source and a destination, a pair that is observed to be actually accessed is used as an element in the Bloom filter. By inserting and storing, an enormous access history is retained for a long time with few resources.

  FIG. 1 shows a system configuration according to an embodiment of the present invention.

  The system shown in FIG. 1 includes an access history storage / retrieval device 100, an operator device 1, a transmission source device 2, a communication destination server 3, a router, or a proxy server 4.

  The access history storage / retrieval device 100 uses a data collection unit 110 that collects access information from a transmission source device 2 to a destination communication destination server 3 from a router or proxy server 4, and acquires access information and uses a Bloom filter. It has an access history recording / retrieval unit 120 that records and retrieves an access history in response to a search request from the operator device 1. As shown in FIG. 2, the access history recording / search unit 120 includes an access history recording unit 121, an access history storage unit 122, and a search unit 123.

  First, the Bloom filter used in the access history recording / retrieval unit 120 will be described.

  Bloom Filter is a probabilistic data structure that allows insertion and determination (search) of arbitrary elements. As shown in FIG. 3, the Bloom Filter structure is represented by a bit string that takes a value of 0 or 1. When an element is inserted, the access history recording unit 121 sets 1 to the bit corresponding to that element. When the search unit 123 searches for an element, the value of the bit corresponding to the element to be searched is checked, and when the bit is 1, it is determined that the element exists. In order to determine the corresponding bit, a hash function for converting an arbitrary element into a numerical value is used. A feature of Bloom Filter is that the space required for the elements to be inserted is very small. However, in the Bloom Filter search operation, even if a certain element is not inserted, a false detection that determines that the element exists is generated.

  The details of Bloom Filter insertion, search operation, and false detection will be described below.

[Bloom filter parameters]
Hereinafter, the Bloom Filter is B, the bit length of the Bloom Filter is m, and the value of the i-th bit (1 ≦ i ≦ m) of B is B [i]. Also, the elements to be inserted are x ₁ , x ₂ ,..., X _n , and the hash functions are H _1, H _{2 ,.} Here, k hash functions output values from 1 to m, and the values output by the respective functions are different.

[Insert element into Bloom filter]
The procedure for inserting elements into the Bloom Filter in the access history recording unit 121 is shown in FIG.

(1) First, the element x _i to be inserted is applied to k hash functions.

(2) Next, the bit at the position of the output value is set to 1. Specifically, B [H ₁ ] = 1,..., B [H _k ] = 1.

[Find elements in Bloom filter]
FIG. 5 shows a procedure for determining whether or not an element having the search unit 123 is inserted into the Bloom Filter.

(1) First, an element x _j to be searched is applied to k hash functions.

  (2) Next, the bit at the position of the output value is examined. If all k bits are 1, the element is present (true), and if at least one bit is 0, the element is not present ( FALSE)

[Probability of false detection]
Bloom Filter is excellent in space efficiency, but there is a false detection that determines that it exists for an element that it wants to exist at the time of search. This is because all the retrieved bits may be 1 due to the hash function collision. The probability of occurrence of false detection of the Bloom filter is calculated from the bit length m of the Bloom filter, the number n of elements to be inserted, and the number k of hash functions. The number of false detections decreases as the ratio of the number of bits of 1 to the bit length m of the Bloom filter decreases. That is, if it is desired to reduce the probability of erroneous detection, m should be increased. Further, when m and n are determined, k that minimizes the probability of erroneous detection can be calculated.

[Recording and searching access history using Bloom filter]
a number of source _{S = {s 1, s 2} , ..., s a} and, b number of the destination _{D = {d 1, d 2} , ..., d b} to exist. At this time, the combination of access histories (s _i, d _j ) (1 ≦ i ≦ a, 1 ≦ j ≦ b) is enormous on a large-scale network, and it is difficult to maintain all of them. Therefore, the access history recording unit 121 stores only S and D, and stores the pair (s _i, d _j ) using the Bloom Filter, so that necessary resources can be significantly reduced. The insertion of access history into the Bloom filter is shown in FIG.

When it is desired to know which sender has accessed a certain destination d, the search unit 123 inserts the combination of d and all the senders (s _j , d) (1 ≤ j ≤ b) into the Bloom filter. It is only necessary to search for the transmission source and list the inserted transmission sources. The access history search is shown in FIG.

[Bias of access count and the problem of false detection of Bloom filter]
Here, consider bias in access history and false detection of the Bloom filter.

  Regarding the characteristics of access history in the network, it is known that there are biases that a very large number of sources access a small number of destinations (for example, documents “M. Aida, N. Takahashi, and T. Abe,” See A proposal of Dual Zipfian Model describing HTTP access trends and its application to address cache design.

For example, a destination having a large number of access transmission sources is d _major , a destination having a small number of access transmission sources is d _minor , and the numbers of transmission sources are 100,000 and 100, respectively. Also, a Bloom filter is created so that the total number of transmission sources is 1,000,000 and the false detection rate is 0.1%, and the access history is registered. At this time, when a search is made as to which sender of each of d _major and d _minor has accessed, the number of searches is performed 1,000,000 times, which is the total number of senders, and the number of false detections is 1,000, which is 0.1% of 1,000,000. That is, the in d _major 101,000, the source of 1,100 in d _minor is output as the search result (estimated value).

Considering the accuracy of the search result in this case, the estimated value for d _major is 1.01 times the true value, and for d _minor , the estimated value is 11 times the true value. As in this example, the difference between the estimated value obtained by the access history search and the true value is biased due to the bias of the access tendency. An example of this is shown in FIG.

[Optimization of the number of hash functions for each inserted element]
To solve the above problem, consider a method of leveling the difference between the estimated value and the true value regardless of the bias of the access history. As described above, the false detection of the Bloom filter may be performed by reducing the ratio of bits having a value of 1 to the total number of bits m.

Therefore, a method is proposed in which the number k of hash functions is changed for each element to be inserted. Specifically, in the access history recording unit 121, when inserting an element including a destination having a large number of access transmission sources, the number k of hash functions is reduced, and when inserting an element including a destination having a small number of access transmission sources Increase the number of k. This method is shown in FIG. Here, regarding the method of determining k, the ratio between the estimated value and the true value is set to a constant ratio. For example, if the difference between the estimated value and the true value is allowed up to 10% of the true value, the number of false detections is allowed up to 10,000 for d _major and up to 10 for d _minor . In this way, the difference between the estimated value and the true value can be leveled regardless of the bias in the access tendency.

  In the present invention, the Bloom filter makes the difference (ratio) between the value obtained by the search and the true value constant, not the number of search elements. As a result, it is possible to reduce the number of false detections when searching for a destination with a small number of access transmission sources while keeping the number of erroneous detections when searching for a destination with a large number of access transmission sources within an allowable range.

[Example of determining the number k of hash functions]
Here, an example of a method for determining the value of the number k of hash functions for each element will be described.

In order to determine the number of hash functions, the occurrence probability of false detection is formulated. Here, it is assumed that there is no bias in the output of the hash function. When the number of hash functions for a certain element x _j (1 ≦ j ≦ n) is k _i , the probability that the value of a certain bit is 0 is as follows.

よって、n個の要素を挿入したときあるビットの値が0である確率は式1から

Therefore, the probability that a bit value is 0 when n elements are inserted is

となる。ある要素x_iがBloom filterに挿入されたと判定されるときは、k_i個のハッシュ関数の出力に対応するビットの値が全て1のときであるので、要素x_iに関する誤検出の発生確率p_iは式2を用いて以下のようになる。

It becomes. When it is determined that an element x _i has been inserted into the Bloom filter, since the values of bits corresponding to outputs of k _i hash functions are all 1, the probability of occurrence of false detection p for the element x _{i i} is as follows using Equation 2.

上記によって得られた式3を用いて各要素のハッシュ関数の個数を決定する。

The number of hash functions for each element is determined using Equation 3 obtained as described above.

The present invention determines the occurrence probability of false detection for each element to be inserted, and obtains the number of hash functions. As described above, the probability of false detection is determined so that the ratio between the estimated value and the true value is constant, and for each p _i

を満たすような各k_iを計算する。ここで、mおよびnは与えられているものとする。

Each k _i that satisfies is calculated. Here, m and n are assumed to be given.

  In addition, it is possible to construct the operation of the above-mentioned components of the access history recording / retrieval device as a program and install it on a computer used as the access history recording / retrieval device, or to distribute it via a network. It is.

  The present invention is not limited to the above-described embodiments, and various modifications and applications can be made within the scope of the claims.

DESCRIPTION OF SYMBOLS 1 Operator apparatus 2 Transmission source apparatus 3 Communication destination server 4 Router or proxy server 100 Access history storage / retrieval apparatus 110 Data collection part 120 Access history / record search part 121 Access history record part 122 Access history storage part 123 Search part

Claims (6)

A access history storage and retrieval device for storing and retrieving the access history is represented by a combination of source and destination,
When the collected source set S and destination set D are given, the S and the D are respectively stored in the storage means, and the combination of the S and the D that is observed to be actually accessed is stored. Is inserted into the Bloom filter as an element, and the access history recording means for storing in the storage means,
Search means for searching the storage means based on a certain input destination and outputting the accessed transmission source, or searching for the storage means based on a certain transmission source and outputting the accessed destination and, the possess,
The access history recording means includes
When storing the access history using the Bloom filter in the storage means,
An element including a destination with a smaller number of accessed sources increases the number k of hash functions at the time of insertion into the Bloom filter, or an element including a source with a smaller number of accessed destinations at the time of insertion into the Bloom filter. An access history storage / retrieval device comprising optimization means for increasing the number k of hash functions . The optimization means includes
The number k of the hash functions is
The bit number of the Bloom filter is m,
The total number of elements to be inserted into the Bloom filter is n,
P _i (1 ≤ i ≤ n) for the false detection rate for each element,
When K is a vector having k _i (1 ≤ i ≤ n) as the number of hash functions for each element,

Access history storage and retrieval device of claim 1 further comprising means for determining using. The search means includes
Means for searching the Bloom filter for all combinations of the destination d and the source S when a destination d is input, and outputting the source that accessed the destination d;
Means for searching the Bloom filter for all combinations of the transmission source s and destination D when a transmission source s is input, and outputting the destination accessed by the transmission source s;
The access history storage and retrieval device according to claim 1, comprising: A access history storage and retrieval method for storing and retrieving the access history is represented by a combination of source and destination,
Storage means for storing access history;
Access history recording means;
A device having a search means,
When the access history recording means is given the collected source set S and destination set D, the access history recording means stores the S and the D in the storage means respectively, and the actual combination of the S and the D is actually stored. An access history recording step of inserting the group observed to be accessed into the Bloom filter as an element and storing it in the storage means;
The search means searches the storage means based on the input destination and outputs the accessed transmission source, or searches the storage means based on the input transmission source and accesses the destination have rows and search step, the output of the,
In the access history recording step,
When storing the access history using the Bloom filter in the storage means,
An element including a destination with a smaller number of accessed sources increases the number k of hash functions at the time of insertion into the Bloom filter, or an element including a source with a smaller number of accessed destinations at the time of insertion into the Bloom filter. An access history storage and retrieval method characterized by performing an optimization step of increasing the number k of hash functions . In the optimization step,
The number k of the hash functions is
The bit number of the Bloom filter is m,
The total number of elements to be inserted into the Bloom filter is n,
P _i (1 ≤ i ≤ n) for the false detection rate for each element,
When K is a vector having k _i (1 ≤ i ≤ n) as the number of hash functions for each element,

The access history storage and retrieval method according to claim 4 , wherein the access history storage and retrieval method is determined by using. In the search step,
When a certain destination d is input , the Bloom filter is searched for all combinations of the destination d and the transmission source S, and the transmission source that accessed the destination d is output.
Or
5. The access according to claim 4 , wherein when a transmission source s is inputted, the Bloom filter is searched for all combinations of the transmission source s and the destination D, and the destination accessed by the transmission source s is output. History storage and retrieval method.

Images