JP4311682B2 - Optimal memory allocation method - Google Patents

Description

  The present invention relates to an optimal memory allocation method, and more particularly to an optimal memory allocation method for specifying a mass flow generation host in which the number of flows generated per unit time exceeds a threshold using data obtained from flow measurement. .

In recent years, there has been a problem that abnormal traffic caused by worms, viruses, DDoS (Distributed Denial of Service), etc. causes serious damage to networks and servers.
A host that has been used as a platform for DDoS or a host that is infected with a worm or virus has a feature that a large number of flows are generated in a short time although the individual flow size is small. For this reason, it is important to quickly identify a host that generates a large number of flows in a short time, call attention to the identified host, and take measures such as disconnecting from the network.
On the other hand, as a technique for collecting various statistical values of a flow such as a flow size and a flow time, packet sampling for extracting a packet from a packet stream at a constant period or at random is in the day.
As the line capacity of the link increases to 2.5 Gbps and 10 Gbps, it becomes difficult to manage all the flow states. Therefore, only some flow states are managed by packet sampling, and various flow statistics are obtained. Is very useful in practice.
Therefore, a method for identifying a high-rate flow in which the number of packets transmitted within a measurement period is equal to or higher than a threshold value from information obtained by packet sampling has been studied.
However, since the size of individual flows generated by the mass flow generation host is small, such a host cannot be effectively specified by the high-rate flow identification method.

In order to specify a large number of flow generation hosts, it is effective to perform sampling for each flow, not for each packet, and total the number of generated flows for each host.
From such a point of view, a method of identifying a host on which Y or more flows are sampled as a mass flow generation host has been studied.
When specifying a mass flow generation host, it is practically important to be able to design a threshold m ^{* of the} number of flows defined as a mass flow and its specific probability H ^* . Furthermore, the probability that a flow with the number m of flows m <m ^* is specified incorrectly (FPR: False Positive Ratio) and the probability that a flow with m ≧ m ^* is not specified incorrectly (FNR: False Negative Ratio) are clarified. It is important to clarify the specific accuracy.
For that purpose, it is necessary to clarify the specific probability H (specific curve) for an arbitrary m given m ^* and H ^* .

A flow is defined as a set of packets having a common outgoing / incoming IP address and outgoing / incoming port number. Then, an arbitrary measurement period Φ having a length of φ (s) is defined, and the total number of flows arriving at the link of interest within the measurement period Φ is defined as M.
Then, when the number of flows arriving at the link of interest within the measurement period Φ for each host is m, a host with m ≧ m ^* is defined as a mass flow generation host with respect to an arbitrarily defined threshold m ^* . Consider that the mass flow generation host is specified within the measurement period Φ at the link of interest.
Now, focus on the host whose flow number is m in the measurement period Φ.
The probability fd that d flows are sampled from m flows of the host of interest within the measurement period Φ is expressed by the following equation (1) using r as the flow sample rate.
[Equation 1]
f _d = _m C _d r ^d (l−r) ^m−d (1)
Therefore, when a host whose sample flow number is Y or more is specified, the probability H that this host is specified can be obtained by the following equation (2).

Moreover, when m ^* and H ^* are given by numerically solving the following equation (3) obtained by substituting m = m ^* into equation (2), an arbitrary Y or r It is possible to set the other parameter corresponding to one set.

For each packet arriving at the link of interest, when v is the value of s bits obtained through a hash function prepared in advance using a total of 96 bits of the arrival and departure IP addresses and the arrival and departure port numbers as keys, v <v ^* Only when there is a new flow determination device. However, v ^* is a threshold for flow sampling, and r = v ^* / 2 ^s , where r is a flow sampling probability. Since flows belonging to the same flow have the same key, all flows are sampled with a probability r regardless of the flow size.
When v <v ^* , it is determined whether or not the flow to which the next arrival packet belongs has already been counted.
The most intuitive method is to manage all sampled flows in the flow table and determine whether there is an entry for the flow in the flow table, but it is necessary to check all the entries at the maximum. As a result, the processing time increases.

Therefore, a method of determining using a Bloom filter is effective. Bloom filter is a method for determining whether or not a candidate is a member of a certain set, k different hash functions (each returning a b-bit value for the incoming key) and 2 ^b Binary variables (initially all reset to zero) are prepared.
In this case, the value of the binary variable corresponding to the k addresses obtained by using the k-Hatsch function with the 96-bit key of the packet is examined, and if one or more is zero, the flow to which the corresponding packet belongs is a new flow. Is determined. Then, all k corresponding binary variables are set to 1.
When the Bloom filter is used, there is no possibility that a flow that has already been counted is erroneously regarded as a new flow, but there is a possibility that a new flow may be mistakenly missed due to a hash value collision.
For the total flow M that has flowed through the link of interest within the measurement period Φ, the expected value D of the number of flows sampled within the measurement period Φ is D = rM. The optimum value of k is expressed by the following equation (4) using D.

When the 2 ^b (bits) bitmap of the Bloom filter is updated for n different flows, the probability that a bit in the bitmap is 1 is {1- (1-k / 2 ^b ) ⁿ }.
At this time, if the probability of missing a new flow by mistake is η _n , the probability η _n is expressed by the following equation (5).
[Equation 5]
η _n = {1- (1-k / 2 ^b ) ⁿ } ^k (5)
Therefore, the average value η of the probability of missing a new flow can be derived from the following equation (6) in consideration of the equation (4).

From equation (6), when r and M are given, the minimum value of b satisfying the average value η ≦ δ _BF (value arbitrarily given) of the probability of missing a new flow can be obtained. The value of k can be set from the above equation (4).
The host table contains the source IP address and the number of sample flows _cj . When it is determined that the flow is a new flow, it is checked whether or not the source IP address of the corresponding packet has already been entered in the host table (for example, the hash value address is checked using the source IP address as a key). If present, increase the number of sample flows by one.
As a result, when the number of sample flows reaches the specific determination threshold Y, the host is specified as a mass flow generation host and is written in the mass flow generation host list.
On the other hand, if the source IP address is not entered in the host table, a new entry is generated.
When implementing the host table entry update process, it is important to efficiently resolve the address where each entry is accommodated. Here, a method using a generally widely used hash function is assumed. .
For hash value collisions, a solution using a link structure using a pointer exhibits high performance and is widely used, so a form using a link structure is also assumed here.

The host table includes a pointer storage area (hereinafter referred to as a PSA (pointer stored area)) and a host entry storage area (hereinafter referred to as an ESA (entry stored area)).
The ESA is an area where an entry is actually accommodated, and accommodates a host IP address, the number of sample flows c _j , and a pointer to the next entry. The PSA pointer to the first entry accommodating in ESA corresponding to each of the 2 ^beta pieces of hash values is accommodated.
The PSA value corresponding to the hash value h (j) obtained by using the hash function h having a β-bit hash space prepared in advance is checked, and if it is a null value, an entry is created in the empty position of the ESA. The sample flow number c _j is initialized to 1.
On the other hand, if the PSA value is not a null value, the link of the corresponding entry of the ESA is examined in order to check whether the entry of the corresponding host exists, and if there is, the sample flow number c _j of the entry is determined. Increase by one. If it does not exist, a new entry is created.

Consider the processing time required by the mass flow generation host identification method for one incoming packet. For example, since the packet time of the minimum packet (40 bytes) in the OC192 link is as short as 32 ns, there is a great restriction on the processing amount to be completed in one packet time, and it is important to evaluate the upper limit of the required processing time.
Although it is necessary to obtain a hash value in all three processes, ie, flow sampling, new flow determination, host table update, it is assumed here that a universal hash function is used.
This hash function has an excellent feature that it is close to ideal (high in randomness), outputs a hash value, and is suitable for hardware implementation.
Since the calculation of the hash value is performed by parallel processing by hardware implementation, it is not included in the processing time. Since the processing time in the CPU is also shorter than the memory access time, the maximum number of memory accesses is used here as a measure for evaluating the maximum processing time.

(I) Flow sampling, (ii) New flow determination, (iii) Host table update and mass flow generation host specific information (starting IP address of incoming packet or flow belonging to it) Since the key) is obtained at the moment when the packet arrives, each process can be started in parallel.
(Ii) is necessary only when the corresponding flow is sampled as a result of (i), and the bitmap update processing of the Bloom filter needs to wait for completion of (i), but the calculation of k hash values is ( It can be performed in parallel with i), and (i) is completed in a short time without memory access, so (i) and (ii) can be parallelized.
In addition, the host table update process (iii) is necessary only when it is determined that the flow is a new flow as a result of (ii), but the address resolution of the corresponding entry (or the necessity of creating a new entry) is (ii). ), And the number of memory accesses required in (ii) is 1, whereas (iii) requires two or more memory accesses for address resolution as described later. Therefore, (ii) and (iii) can also be parallelized.
Therefore, in order to evaluate the processing time, only the maximum memory access number (iii) that requires the most processing time has to be considered.

If there is no upper limit on the number of hosts mapped to the same hash value in the host table, the upper limit on the number of memory accesses cannot be suppressed. In mounting, since it is necessary to suppress the maximum number of memory accesses required within one packet processing time, the upper limit of the number of links is limited to L here.
If L entries are already accommodated in the corresponding hash value at the time of entry creation, this entry is rejected. When a new entry is created with a hash value containing l entries, (l + 1) times of memory access is required until it is determined as a new entry. Furthermore, since it is necessary to create an entry in the ESA space and write the address of the created entry in the pointer of the l-th entry, a total of (l + 3) memory accesses is required at the maximum.
Since l ≦ L−1, the maximum memory access number is (L + 2).

When the hash collision is resolved by a linked list using pointers, it is important to design a parameter β that determines the hash space.
When n entries are accommodated in the host table, the probability that the number of entries accommodated in a hash value is i is _n C _i (1/2 ^β ) ⁱ (1-1 / 2 ^β ) ^{n− i} .
Therefore, when the number of hosts from which one or more flows are sampled within the measurement period Φ is expressed by the following equation (6-1), the average value pi of the probability that the number of accommodated entries of a certain hash value is i is ( 7).

Therefore, when a new entry is created in the host table, the average value Pi of the probability that the number of links of the corresponding hash value is i or less is expressed by the following equation (8).
If the maximum number of links restricted with L, a new entry is rejected with probability P _L. Here, β is designed so that P _L is equal to or less than δ _HT (arbitrarily given value) given arbitrarily.

なお、以上の技術については、下記非特許文献１を参照されたい。

Refer to the following Non-Patent Document 1 for the above technique.

As prior art documents related to the invention of the present application, there are the following.
Kamiyama, Mori, Kawahara, “Identification of Mass Flow Generation Hosts Using Flow Sampling”, IEICE Technical Report 2005/184.

In the conventional mass flow generation host identification method, the measurement period Φ, the specific threshold m ^* , the specific probability H ^* , the specific determination threshold Y, the total number of flows M in the measurement period, and the number of sample hosts N in the measurement period are given. The flow sampling probability r to be set, the parameters b and k of the Bloom filter, the parameter β of the host table, and the required memory size B can be obtained.
However, in general, the memory size is often determined by the implementation, and given the memory size, the specific accuracy is maximized, that is, the probability of erroneously overlooking a mass flow generation host (FNR) is minimized. It is important that various parameters can be set appropriately.
However, in the conventional method, when the total amount of memory is determined by implementation, various parameters are appropriately set so that the specific accuracy is maximized, and the amount of memory is assigned to each of the Bloom filter, PSA, and ESA. Cannot allocate optimally.
The present invention has been made to solve the above-described problems of the prior art, and an object of the present invention is to use the data obtained from flow measurement and the number of flows generated per unit time exceeds a threshold value. An object of the present invention is to provide a technique capable of optimally allocating memory so as to minimize the probability of erroneously overlooking a mass flow generation host in a method for identifying a mass flow generation host.
The above and other objects and novel features of the present invention will become apparent from the description of this specification and the accompanying drawings.

Of the inventions disclosed in this application, the outline of typical ones will be briefly described as follows.
(1) Use a host table that stores the number of sample flows for each sampled host and a Bloom filter used to determine new flows, and use only statistical data obtained by flow sampling to identify large-volume flow generation hosts device, Oite the flow Hogs specific method to identify the host that the number of flows is equal to or more than a threshold to generate per unit of time, parameter design device, a memory that is implemented in the optimal memory allocation method for optimally allocating The upper limit H ^C (m ₀ ) of the probability that the specific determination threshold Y is not specified under the condition that a mass flow generation host having an arbitrary number of generated flows m ₀ is entered in the host table. the host derives the upper R (m ₀₎ of the probability of not being an entry in the host table, H _{(M 0) {1-R} (m 0)} + R specific decision threshold Y that minimizes _{(m 0)} was derived as an optimum value, a specific determination threshold Y that the derived, amount of memory B being the mounting Based on the above, all parameters of the Bloom filter and the host table are derived so as to minimize the probability of erroneously overlooking a mass flow generation host.
(2) In (1), as the m _0, a median value of generation number of flows all Flow Hogs.
(3) In (1) or (2), estimate the total number of flows required for parameter calculation and the median number of generated flows of the mass flow generation host using the information obtained in the previous measurement period. .
(4) In (3), in the estimation of the median number of generated flows of the mass flow generation host, in order to remove the influence of the error of the specific host in the previous measurement period, the median is overlooked and the estimated value of the number of mass flow generation hosts And subtract an estimate of the number of non-mass flow generation hosts specified incorrectly.

The effects obtained by the representative ones of the inventions disclosed in the present application will be briefly described as follows.
According to the present invention, in a method for identifying a mass flow generation host in which the number of flows generated per unit time exceeds a threshold using data obtained from flow measurement, the probability of erroneously overlooking the mass flow generation host is minimized. It is possible to optimally allocate the memory so that

Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
In all the drawings for explaining the embodiments, parts having the same functions are given the same reference numerals, and repeated explanation thereof is omitted.
FIG. 1 is a block diagram showing a system configuration to which an optimum memory allocation method of a mass flow generation host specifying method according to an embodiment of the present invention is applied.
In FIG. 1, 101 is a parameter design device, 102 is a flow sampling device, 103 is a new flow determination device, 104 is a host table, 105 is a mass flow generation host specifying device, and 106 is a mass flow generation host list.
From the average number of sample flows of the flow hog specified in the previous measurement period by the parameter design device 101, the estimated value of the total number of flows M shown in the following equation (8-1), the memory size B, the measurement period Φ, and the specific threshold m ^* From the specific probability H ^* , Bloom filter parameters b and k, host table parameter β, specific determination threshold Y, flow sampling rate r, and ESA size E are designed.
During the measurement period, the flow flowing through the link of interest by the flow sampling device 102 is sampled with a certain probability r, and the new flow determination device 103 determines whether or not the sampled flow is a new flow (uncounted), If it is a new flow, the host table 104 is updated. The mass flow generation host specifying device 105 specifies a mass flow generation host from the hosts registered in the host table 104 and outputs it to the mass flow generation host list 106.

Next, the optimum memory allocation method of the mass flow generation host specifying method of this embodiment will be described.
[Optimal memory allocation method]
Consider appropriately setting various parameters used in the measurement period Φ _n at the start point of the n-th measurement period Φ _n .
A total sample number of flows _{D n-1} in the previous measurement period Φ _n-1, the use of the flow sample rate _{r n-1,} the total number of flows before the measurement period can be estimated at _{D n-1 / r n-} 1 is Assuming that the same number of flows are generated in the measurement period Φ _n , the estimated value of the total number of flows shown in the above equation (8-1) is given by the following equation (8-2).
In mounting, it is desirable to consider not only the memory size B but also the maximum value k _max of the number k of Hash functions that can be used for the Bloom filter as a constraint expression. Therefore, five design constraints, B, L, k _max , an arbitrary value δ _BF , and an arbitrary value δ _HT are given.

[Parameter design method when memory size B and specific determination threshold Y are given]
First, constraint parameters _{B, L, kmax,} [delta] _BF, and [delta] _HT, an estimate of the total number of flows M shown in (8-2) equation, the measurement period ^[Phi, m ^{*, H} *, when Y is given How to design the other parameters r, k, b, β, E will be described.
The flow sampling rate r can be obtained by solving the above equation (3).
Further, the following formulas (9) and (10) obtained by replacing the total number of flows M in the formulas (4) and (6) with the estimated values shown in the formula (8-2) are solved. Thus, b and k are obtained. However, k is rounded to the nearest integer value, and when k> k _max is satisfied, k = k _max is set. Also, b is set to the smallest integer that satisfies the above equation.

By the way, the memory amount of B _bf = 2 ^b / 8 = 2 ^b−3 (bytes) is required for the bitmap of the Bloom filter for new flow determination.
Also, if the size of the ESA is E, a memory amount of B _psa = 2 ^β−3 [log ₂ E] (bytes) is required for the PSA. The host entry is an IP address of 32 (bit), [ log ₂ Y] (bits) sample flow number counter (it should be possible to count up to Y at most), and [log ₂ E] (bits) is a pointer to the next entry, so for ESA, B _esa = E A memory amount of (32+ [log ₂ Y] + [log ₂ E]) / 8 (bytes) is required.
Therefore, when the parameters Y, b, β, and E are given, the required memory amount needs to be equal to or less than B. Therefore, the constraint equation shown by the following equation (11) is obtained.
Moreover, the constraint equation determined from the maximum allowable memory access number replaces N with E in the above-described equation (8), whereby the constraint equation of the following equation (12) is obtained.
By deriving the maximum values of β and E that satisfy these conditions, β and E can be designed.

[Influence of Y on specific accuracy and optimum design method of Y]
Since the flow sample rate r increases as the specific determination threshold Y increases, in order to keep the new flow miss rate of the Bloom filter below a certain value δ _BF , b increases from the above equation (11), and the Bloom filter Increases the amount of memory allocated to.
Since the amount of memory that can be used as a whole is constant at B, as the specific determination threshold Y increases, the amount of memory allocated to PSA and ESA constituting the host table decreases, and the size E of β and ESA decreases.
Since the increase in the specific determination threshold Y increases the slope of the specific curve near the specific threshold m ^* , the specific accuracy improves as the specific determination threshold Y increases. Therefore, the FPR improves monotonously as Y increases.
However, on the other hand, increasing the specific decision threshold Y leads to a decrease in ESA size E, thus increasing the probability that sampled mass flow generation host entries will not be accommodated in the host table due to host table ESA overflow. .
As a result, the FNR improves with an increase in the specific determination threshold Y in an area where the specific determination threshold Y is small, but deteriorates as the specific determination threshold Y increases in an area where the specific determination threshold Y is large.
Therefore, in the present invention, the specific determination threshold Y that minimizes the FNR, that is, minimizes the number Z of mass flow generation hosts to be overlooked, is defined as the optimum value of the specific determination threshold Y.
Under the condition that an entry of a mass flow generation host having m = m ₀ (where m ₀ ≧ m ^* ) is generated in the host table, the upper limit of the probability that this host is not specified is defined as H ^c (m ₀ ). Then, H ^c (m ₀ ) is obtained by the following equation (13).
On the other hand, if the upper limit of the probability that this host entry is not accommodated in the host table due to overflow of the host table is R (m ₀ ), R (m ₀ ) is obtained by the following equation.

However, the upper limit of the probability of not entries in this host is generated in the host table is given by _{R (m 0) + δ HT} .
From the viewpoint of specifying a mass flow generation host with m = m _0, the specific determination threshold Y that minimizes ^HC (m ₀ ) {1−R (m ₀ )} + R (m ₀ ) is optimal.
However, the optimum value of the specific determination threshold Y expressed by the following equation (15) calculated in this way differs depending on the value of m ₀ .
When m ₀ is close to m ^* or very large, the influence of the specific determination threshold Y on H ^c (m ₀ ) is reduced, so that the small specific determination threshold Y is selected as the optimum value of the characteristic determination threshold Y. The
In order to suppress the probability of missing all the large flow generation hosts as much as possible, it is desirable to select a value representing m of the large flow generation hosts as m ₀ .
Therefore, the median value of m for all hosts with m ≧ m ^* is set to m ₀ . Actually, during the previous measurement period, the median of the number of sample flows of the identified host (the number of sample flows is equal to or greater than the specific determination threshold Y) shown by the following equation (16-1) is calculated, and the following ( Set according to 16-2).

However, because the identification process in the previous measurement period misses a large flow generation host or misidentifies a non-mass flow generation host, the median number of generated flows estimated from the sample flow number of the specified host is the actual mass This is different from the median number of flows generated by the flow generation host.
Therefore, m ₀ is corrected by the following equation (17).
In the equation (17), N is the number of hosts specified in the previous measurement period, and d is an arbitrary integer value that takes a value in the range of 1 ≦ d ≦ m ^* −1.

As described above, in this embodiment, when the memory size B, the measurement period Φ, the specific threshold value m ^* , the specific probability H ^* , and the total number of flows M in the measurement period are given, the mass flow generation host In addition to the parameters b and k of the Bloom filter and the parameter β of the host table, the specific decision threshold Y, the flow sampling rate r, and the ESA size E are optimally designed so as to minimize the probability of erroneously overlooking (FNR). It becomes possible.
As mentioned above, the invention made by the present inventor has been specifically described based on the above embodiments. However, the present invention is not limited to the above embodiments, and various modifications can be made without departing from the scope of the invention. Of course.

It is a block diagram which shows the system configuration | structure to which the optimal memory allocation method of the mass flow production | generation host identification method of the Example of this invention is applied.

Explanation of symbols

DESCRIPTION OF SYMBOLS 101 Parameter design apparatus 102 Flow sampling apparatus 103 New flow determination apparatus 104 Host table 105 Mass flow generation host specification apparatus 106 Mass flow generation host list

Claims (4)

Using a host table that stores the number of sample flows for each sampled host and a Bloom filter used for determining a new flow, only using statistical data obtained by flow sampling, a mass flow generation host specifying device Oite the flow Hogs particular method for identifying a host number of flows to be generated per unit time is equal to or greater than a threshold, the parameter designing apparatus, a memory mounted a optimal memory allocation method for optimally distributed,
The upper limit H ^C (m ₀ ) of the probability that a large-volume flow generation host having the specific determination threshold Y as a parameter and having an arbitrary number of generated flows m ₀ is entered in the host table, and this host And an upper limit R (m ₀ ) of the probability that is not entered in the host table,
A specific determination threshold Y that minimizes H ^C (m ₀ ) {1−R (m ₀ )} + R (m ₀ ) is derived as an optimum value;
Deriving a certain determination threshold Y that the derived, based on the amount of memory B being the mounting, so as to minimize the probability of missing accidentally Flow Hogs, all parameters of the Bloom filter and the host table An optimal memory allocation method. The optimal memory allocation method according to claim 1 , wherein the m ₀ is a median value of the number of generated flows of all the mass flow generating hosts. And the total number of flows required for parameter calculation, claim 1 or claim and estimates using information and a central value of the generated flow rate, obtained in the preceding measurement period Flow Hogs 2 The optimal memory allocation method described in 1. In the estimation of the median number of generated flows of mass flow generation hosts, in order to remove the influence of the error of the specific host in the previous measurement period, the estimated value of the number of mass flow generation hosts missed was added to the median and further specified incorrectly. The optimal memory allocation method according to claim 3 , wherein an estimated value of the number of non-mass flow generation hosts is subtracted.

Images