JP4980396B2 - Traffic characteristic measuring method and apparatus - Google Patents

Description

  The present invention relates to a traffic characteristic measurement method and apparatus using hierarchical aggregated entropy, and more particularly to a technique for characterizing traffic having a hierarchical structure according to the structure and detecting an abnormality based on the characteristic amount.

As a technique for detecting abnormal traffic due to scans by worms, mass traffic denial of service (DoS) attacks and failures, there is a technique that uses the entropy indicating traffic variation as a characteristic quantity and detects anomalies by deviation from the normal value of the characteristic quantity. Proposed. (See Non-Patent Documents 1, 2, and 3 below)
A set of destination is D, the proportion of the traffic volume of traffic is overall to a certain destination d∈D and p _d. At this time, the traffic entropy H (D) relating to the destination is given by the following equation (1).

For example, many worms send scan packets while changing the destination IP address to scan terminals with other vulnerabilities. When such scan traffic occurs, traffic to a wide range of destinations As it occurs, the variability with respect to the traffic destination increases, and thus the entropy H (D) increases.
On the other hand, in the case of a DoS attack, the traffic concentration to a single or a small number of victims occurs, so the variability with respect to the traffic destination is reduced, and thus the entropy H (D) is reduced.
In addition, a method has been proposed in which entropy is calculated for DNS traffic to detect the occurrence of a DNS query by a worm (see Non-Patent Document 4 below).

A. Lakhina, M. Crovella, and C. Diot, “Mining anomalies using traffic feature distributions”, in Proc. ACM SIGCOMM 2005, Philadelphia, PA, USA, August 2005.

Y. Gu, A. McCallum, and D. Towsley, “Detecting anomalies in network traffic using maximum entropy estimation”, in Proc. ACM IMC 2005, Berkeley, CA, USA, October 2005.

G. Nychis, V. Sekar, D. G. Anderson, H. Kim, and H. Zhang, “An empirical evaluation of entropy-based traffic anomaly detection,” in Proc. ACM IMC 2008, Vouliagmeni, Greece, October 2008.

D. Arturo, L. Roma, and Y. Musashi, “Entropy based analysis of DNS query traffic in the campus network,” in Proc. CTISA2007, Orlando, FL USA, 2007.

WK Ehrlich, K. Futamura, and D. Liu, “An enyropy based method to detect spoofed denial of service (Dos) attacks,” Telecommunicaions Modeling, Policy and Technology (Operations Research / Computer Science Interfaces) Vol. 44, Springer, 2008 .

However, the traffic characteristic measurement by entropy has a problem that the hierarchical structure of traffic cannot be reflected. As can be seen from the equation (1), used in the calculation of the entropy is traffic ratio p _d to the destination d, destination d does not consider whether the position where the destination set D.
For example, many worms are known to scan a neighboring address space that includes their own IP address when scanning a destination IPv4 address. The entropy of such a scan is large when observed in address units, but when observing traffic aggregated in units of neighboring address space, the entropy decreases because the aggregated traffic is concentrated in a single space. I think that.
However, the entropy expressed by the above-described equation (1) is the entropy observed in units of addresses, and information on whether or not the information is concentrated when observed in units of such address spaces cannot be obtained.
When the traffic has a hierarchical structure, it is expected that detailed traffic characteristics as described above can be obtained by calculating entropy for the traffic aggregated according to the hierarchical structure.

Further, in the above-mentioned Non-Patent Document 5, a method for detecting an abnormality from a time series of entropy by traffic aggregated in units of upper 16 bits of an IP address has been proposed, but what can be measured by this method is aggregated at a fixed 16 bits. This is the traffic entropy, and the traffic entropy observed at other granularities cannot be measured.
In addition, it is also common to use IP address as a target, divide the address into several blocks, calculate the frequency of occurrence for each address block, and use entropy between the address blocks to determine whether the communication is unauthorized. It is. However, this method is entropy for each block, and it is not possible to measure a traffic characteristic amount considering a hierarchical structure.
By evaluating the variation as the traffic characteristic in each layer of the hierarchical structure, it becomes clear in which layer the variation is increasing, and as a result, the cause of the occurrence of the traffic characteristic is clarified.
The present invention has been made to solve the problems of the prior art, and an object of the present invention is to use hierarchical aggregated entropy reflecting the hierarchical structure of traffic in a traffic characteristic measuring method and apparatus. Accordingly, it is an object of the present invention to provide a technique capable of extracting more detailed information and improving abnormality detection accuracy based on the characteristic amount.
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) A traffic characteristic measurement method, in which traffic is acquired in Step 1, Step 2 for extracting measurement target traffic, Step 3 in which traffic is aggregated according to the hierarchical structure of measurement target traffic, A step 4 for calculating the entropy of the aggregated traffic, and a step 5 for characterizing the traffic using the entropy for each layer. In step 3, the traffic is aggregated in the N layers, and D traffic where the _N aggregated at the highest layer, the traffic that aggregates the D _N-1 in the hierarchy of the one step lower, when the traffic in front of the lowest hierarchy aggregating D _0, in step 4, the D _N the entropy _{H (D N), D N} -1 of entropy _{H (D N-1),} ..., entropy H _{(D 0)} a total of _{D 0} And, in step 5, using a _{D N} entropy _H (D _{N), D N-1} of entropy _{H (D N-1),} ..., entropy H _{(D 0)} of _{D 0,} characterization of the traffic I do.

(2) A traffic characteristic measurement method, in which traffic is acquired in Step 1, Step 2 for extracting traffic to be measured, Step 3 in which traffic is aggregated according to the hierarchical structure of the traffic to be measured, A step 4 for calculating the entropy of the aggregated traffic, and a step 5 for characterizing the traffic using the entropy for each layer. In step 3, the traffic is aggregated in the N layers, and D traffic where the _N aggregated at the highest layer, the traffic that aggregates the D _N-1 in the hierarchy of the one step lower, when the traffic in front of the lowest hierarchy aggregating D _0, in step 4, the D _N Entropy H (D _N ), D _{N -1} entropy H (D _N-1 | D _N ), D _N-1 conditioned by DN _D conditioned with _N-2 entropy _{H (D N-2 | D} N-1), ..., entropy _H of the _{D 0} which are conditioned by _{D 1} | calculates the _(D 0 _{D 1),} the step 5 in, _D entropy _H (D N) of the _{N, D} conditioned in _{N D N-1} of entropy _{H (D N-1 | D} N), D D conditioned by _{N-1 N-2} entropy H Using the entropy H (D ₀ | D ₁ ) of D ₀ conditioned by (D _N−2 | D _N−1 ),..., D ₁ , the traffic is characterized.

(3) In (1) or (2), in step 4, the entropy for each layer is normalized by the maximum value, and in step 5, the normalized entropy for each layer is used to determine the traffic characteristics. To do.
(4) In any one of (1) to (3), in step 5, a time series of traffic entropy aggregated hierarchically is generated, and a traffic abnormality is detected based on the fluctuation of the time series.
(5) In any one of (1) to (3), the traffic to be measured is traffic in units of hosts, and the measured traffic characteristics in units of hosts are used for classification of host abnormalities / normalities.
(6) Moreover, this invention is a traffic characteristic measuring device which performs the above-mentioned traffic characteristic measuring method.

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, it is possible to extract more detailed information by using the hierarchical aggregate entropy reflecting the hierarchical structure of traffic, and improve the abnormality detection accuracy based on the characteristic amount.

It is a block diagram which shows schematic structure of the traffic characteristic measuring apparatus of the Example of this invention. It is a figure which shows the entropy of the aggregate traffic in the DNS traffic with a hierarchical structure. It is a flowchart which shows an example of the process sequence of the traffic characteristic measuring device of the Example of this invention.

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 schematic configuration of a traffic characteristic measuring apparatus according to an embodiment of the present invention. In FIG. 1, 10 is a traffic acquisition unit, 11 is a measurement target traffic extraction unit, 12 is a hierarchical traffic aggregation unit, 13 is an entropy calculation unit, and 14 is a traffic characteristic calculation unit.
The traffic acquisition unit 10 acquires communication traffic that is communication data transferred between two or more terminals of an IP network for a certain period.
The acquisition method may be a method of acquiring traffic flowing in the link of the IP network by a tapping device, acquisition by mirroring in a node such as a switch / router in the communication network, or acquisition of traffic flow information output by the node Alternatively, it may be acquisition of a communication log or the like in the terminal.
The acquired traffic data is a set of individual traffic. The individual traffic differs depending on the acquisition method, and in the case of tapping and mirroring, it is an IP packet. In the case of flow information, generally {transmit / receive IP address, This is a flow in which the values of five sets of identifiers of transmission / reception port number and protocol} are the same, and in the case of a communication log, it is individual access information.

The measurement target traffic extraction unit 11 extracts the measurement target traffic from the acquired traffic. The measurement target traffic is, for example, the entire IP traffic, DNS traffic, or VoIP traffic.
In addition, the measurement target traffic extraction unit 11 may sort the traffic into units of hosts. In this case, the abnormality / normality of the host can be classified based on the measured traffic characteristics of the host unit described later.
The hierarchical traffic aggregating unit 12 aggregates the extracted traffic according to the hierarchical structure of the measurement target traffic. Aggregation here refers to ignoring a part of identifiers that distinguish individual traffic, so that other identifiers are the same, identify one or more individual traffic as new individual traffic, This indicates that the traffic amount such as the number of bytes accompanying the individual traffic is used as the sum of the traffic amounts of the individual traffic identified.
Hierarchical aggregation indicates that the part of the identifier that is ignored is inclusive from the lowest layer to the highest layer.

Hereinafter, an aggregation method in the hierarchical traffic aggregation unit 12 will be described.
(1) If the traffic to be measured is IP traffic, the first single or multiple bits of the IP address are the highest hierarchy, the longer bit string is the lower hierarchy, and the lowest hierarchy is the IP address. The traffic is aggregated according to the hierarchical structure
(2) When the traffic to be measured is IP traffic, the Autonomous System (autonomous system; hereinafter referred to as AS) of the measurement location is the highest hierarchy, and the lowest hierarchy, up to the AS to which the IP address belongs. Traffic is aggregated according to the hierarchical structure represented by the via AS path.
(3) When the traffic to be measured is Domain Name System (DNS) traffic, the top-level domain is the highest hierarchy, and traffic is aggregated according to the same hierarchical structure as the domain tree structure.
In this case, the highest hierarchy is a top level domain (TLD) such as (.com), (.net), (.jp).
FIG. 2 shows the entropy of aggregate traffic in DNS traffic having a hierarchical structure. The left half of FIG. 2 shows the DNS domain tree. Each ellipse is a domain, and the upper domain is an aggregate domain. The higher the hierarchy, the less the number of aggregate domains. The right half shows the traffic volume distribution between these aggregate domains.

(4) When the traffic to be measured is DNS traffic, the domain in which the user can register the name is set as the highest hierarchy, and the traffic is aggregated according to the same hierarchical structure as the domain tree structure.
This is because there are both gTLDs in which the top level domain is registered with the user's domain name (.com) directly below it and ccTLDs that are not directly under the user's domain name (.jp). Therefore, in order to unify the level of the hierarchical structure, a domain called a “public suffix” in which a user can register a name immediately below is set as the highest hierarchy.
(5) When the traffic to be measured is a reverse query that inquires the domain name for the IP address of DNS traffic, the traffic is hierarchically transmitted to the inquired IP address by the method (1) or (2) described above. Summarize.

(6) When the traffic to be measured is a reverse query that inquires the domain name for the IP address of the DNS traffic, the traffic is hierarchically applied to the domain name of the response to the query by the above method (3) or (4) Aggregate.
(7) When the traffic to be measured is Voice over IP (VoIP) telephone traffic, the telephone number is E.E. Since a hierarchical structure called 164 number is defined, traffic is aggregated using this hierarchical structure.
(8) When the traffic to be measured is World Wide Web (WWW) traffic, the traffic is aggregated according to the hierarchical structure of Uniform Resource Identifier (URI). That is, when the measurement target is World Wide Web (WWW) traffic, since the WWW has a hierarchical structure delimited by “/”, traffic is aggregated using this hierarchical structure.

The entropy calculation unit 13 calculates entropy for each layer from the traffic ratio of the aggregation unit for the traffic aggregated for each layer by the hierarchical traffic aggregation unit 12.
In the case of unconditional entropy, a set of destinations aggregated in the k-th (k = 0 to N) hierarchy is defined as D _k, and the traffic amount to a certain destination d _k εD _k occupies the total traffic amount. Let p _dk be the ratio. At this time, the traffic entropy H (D _k ) related to the destination is calculated by the following equation (2).

また、条件付きエントロピーの場合は、最上位階層Ｎで集約されたトラヒックＤ_Ｎのエントロピーは、前述の（２）式で計算し、Ｄ_Ｎで条件付けられた階層Ｎ−１のトラヒックのエントロピーＨ（Ｄ_Ｎ−１｜Ｄ_Ｎ）、を、下記（３）式で計算する。

In the case of conditional entropy, entropy of traffic D _N aggregated at the highest layer N is calculated by the aforementioned equation (2), the hierarchy conditioned by D _N N-1 traffic entropy H ( D _N-1 | D _N ) is calculated by the following equation (3).

ここで、ｄ’_Ｎ∈Ｄ_Ｎは、Ｎ−１階層の宛先ｄ∈Ｄ_Ｎ−１が属するＮ階層の宛先である。
以下、同様に、Ｈ（Ｄ_Ｎ−２｜Ｄ_Ｎ−１）,...,Ｈ（Ｄ_０｜Ｄ_１）を計算する。

Here, d ′ _N εD _N is the N-layer destination to which the N−1-layer destination dεD _N-1 belongs.
Hereinafter, similarly, H (D _N−2 | D _N−1 ),..., H (D ₀ | D ₁ ) is calculated.

一般的に、前述の（４）式が成り立つため、階層的に集約したトラヒック毎に条件付きエントロピーを計算することで、集約前のエントロピーＨ（Ｄ_０）に含まれるトラヒック特性量を全て含み、かつ階層構造に起因するトラヒック特性も計測することができる。
この場合に、エントロピーは集合Ｄ_ｋの要素数に依存し、Ｄ_ｋの要素数が大きくなるにつれてエントロピーも増大するため、集合Ｄ_ｋの要素数に依存しないようにその最大値で正規化する。例えば、条件付きでないエントロピーの場合は最大値がｌｏｇ（Ｄ_ｋ）であるため、その数で除する。条件付きエントロピーの場合は、最大値は下記（５）式で与えられるので、この数で除算する。

In general, since the above-described equation (4) holds, calculating the conditional entropy for each hierarchically aggregated traffic includes all the traffic characteristic amounts included in the entropy H (D ₀ ) before aggregation, In addition, traffic characteristics resulting from the hierarchical structure can also be measured.
In this case, the entropy depends on the number of elements of the set _Dk , and the entropy increases as the number of elements of _Dk increases. Therefore, normalization is performed with the maximum value so as not to depend on the number of elements of the set _Dk . For example, in the case of unconditional entropy, since the maximum value is log (D _k ), it is divided by the number. In the case of conditional entropy, since the maximum value is given by the following equation (5), it is divided by this number.

The traffic characteristic calculation unit 14 performs traffic characteristic assignment using the entropy calculated by the entropy calculation unit 13.
The traffic characteristic calculation unit 14 determines normality / abnormality of traffic in a certain period from a time series of entropy for each certain period, which is sequentially calculated from the traffic data acquired every certain period. Here, for normality / abnormality determination from time-series data, a probability distribution of a set of entropy values for a certain period is generated, and an outlier above the threshold value such as 1% point, 99% point, etc. May be determined as above.
Alternatively, traffic data for a certain period is divided for each transmission host, and normal / abnormal determination of the host is performed from the entropy value calculated for each host. Here, for normality / abnormality determination from the entropy value for each host, a probability distribution of a set of entropy values for each host is generated, and the outliers are less than or equal to a threshold such as 1% point and 99% point of the distribution. The period may be determined as above.
As described above, according to the present embodiment, in the traffic characterization using entropy, the hierarchical structure of the traffic can be taken into account, and the accuracy can be improved in the abnormality detection using the characteristic amount. It becomes.

Hereinafter, an example of a processing procedure of the traffic characteristic measuring apparatus according to the present embodiment will be described with reference to FIG. This FIG. 3 uses traffic in units of hosts as the traffic to be measured, uses the above-described method (3) for the aggregation method in the hierarchical traffic aggregation unit 12, and further, the entropy calculation unit 13 performs conditional entropy. It is a flowchart which shows the process sequence in the case of calculating.
(1) Step 101
The traffic of the link constituting the IP network is observed, and the traffic acquisition unit 10 acquires the traffic transferred packet. The output in this step is a group of packets that have passed through the link for a certain period.
(2) Step 102
The measurement target traffic extraction unit 11 extracts only the DNS inquiry packet with the destination port number 53, and generates a packet set for each transmission host i. The output at this step is the DNS inquiry packet group D _i (i = 1,..., N) of the transmission host i (i = 1,..., N).

(3) Step 103
In the hierarchical traffic aggregation unit 12, the domain name hierarchy k (k = 1) from the DNS inquiry packet group D _i (i = 1,..., N) of the transmission host i (i = 1,..., N). , ..., M) generate aggregate traffic. Here, the hierarchy M is the highest hierarchy and the hierarchy 1 is the lowest hierarchy. The output in this step is the aggregate DNS inquiry packet group D _i ^(k) (i =) for each transmission host i (i = 1,..., N) and layer k (k = 1,..., M). 1, ..., N), (k = 1, ..., M).
(4) Step 104
In the entropy calculation unit _13, ^{D i (k)} with respect to the conditional entropy ^{_{H (D i (k-1}} ) | D i (k)) (k = 1, ..., M), and H _{(D i} ^(K) ) is calculated. The outputs at this step are H (D _i ^(k−1) | D _i ^(k) ) (k = 1,..., M) and H (D _i ^(k) ).
(5) Step 105
In the traffic characteristic calculation unit 14, H (D _i ^(k−1) | D _i ^(k) ) (k = 1,..., M) and H (D _i ^{(k )} The distribution of) is calculated, and the transmission host i that is out of the distribution is specified. The output in this step is an abnormal traffic transmission host group.
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.

DESCRIPTION OF SYMBOLS 10 Traffic acquisition part 11 Measurement object traffic extraction part 12 Hierarchical traffic aggregation part 13 Entropy calculation part 14 Traffic characteristic calculation part

Claims (9)

Step 1 to get traffic,
Step 2 for extracting traffic to be measured;
Step 3 for aggregating traffic according to the hierarchical structure of the traffic to be measured;
Step 4 for calculating the entropy of aggregate traffic at each hierarchy;
And step 5 for characterizing the traffic using the entropy for each hierarchy,
In step 3, the traffic is aggregated in N layers,
D _N traffic that aggregates at the highest layer, the traffic that aggregates the D _N-1 in the hierarchy of the one step lower, when the traffic in front of the lowest hierarchy aggregating D _0, in step 4, D _N Entropy H (D _N ), D _n−1 entropy H (D _N−1 ),..., D ₀ entropy H (D ₀ ),
In Step 5, _{D N} entropy _{H (D N), D N} -1 of entropy _{H (D N-1),} ..., using the entropy H _{(D 0)} of _{D 0,} performing the characterization of the traffic A traffic characteristic measuring method characterized by the above. Step 1 to get traffic,
Step 2 for extracting traffic to be measured;
Step 3 for aggregating traffic according to the hierarchical structure of the traffic to be measured;
Step 4 for calculating the entropy of aggregate traffic at each hierarchy;
And step 5 for characterizing the traffic using the entropy for each hierarchy,
In step 3, the traffic is aggregated in N layers,
D _N traffic that aggregates at the highest layer, the traffic that aggregates the D _N-1 in the hierarchy of the one step lower, when the traffic in front of the lowest hierarchy aggregating D _0, in step 4, D _N entropy _{H (D} N), D D conditioned in _{N N-1} of entropy _{H (D N-1 | D} N), D N-1 in conditioned and _{D N-2} entropy H _{(D N- 2} | computes the _{D 1), | D N-} 1), ..., entropy _H of the _{D 0} which are conditioned by _{D 1 (D} 0
In step 5, the entropy _H (D N) of _{D N, D} conditioned in _{N D N-1} of entropy _{H (D N-1 | D} N), D N-2 , which is conditioned by the _{D N-1} entropy _{H (D N-2 | D} N-1), ..., entropy _H of the _{D 0} which are conditioned by _{D 1} | using _(D 0 D _1), and performs characterization of the traffic Traffic characteristic measurement method. In step 4, the entropy for each layer is normalized by its maximum value,
3. The traffic characteristic measuring method according to claim 1, wherein in step 5, the traffic is characterized using the normalized entropy for each layer.   4. The traffic entropy time series aggregated hierarchically is generated in the step 5, and a traffic abnormality is detected based on the time series fluctuation. 5. Traffic characteristics measurement method. The traffic to be measured is host-based traffic,
4. The traffic characteristic measuring method according to claim 1, wherein the measured traffic characteristic of each host is used for abnormal / normal classification of the host. A traffic acquisition unit for acquiring traffic;
A measurement target traffic extraction unit for extracting measurement target traffic;
A hierarchical traffic aggregation unit that aggregates traffic according to the hierarchical structure of the traffic to be measured;
An entropy calculator that calculates the entropy of aggregate traffic at each hierarchy;
A traffic characteristic measurement device having a traffic characteristic calculation unit for characterizing the traffic using entropy for each layer,
The hierarchical traffic aggregation unit aggregates traffic in N layers,
D _N traffic that aggregates at the highest layer, traffic aggregated at D _N-1 a stage lower layer thereof, when the traffic in front of the lowest hierarchy aggregating D _0, the entropy calculator, D _N entropy H (D _N ), D _N−1 entropy H (D _N−1 ),..., D ₀ entropy H (D ₀ ),
The traffic characteristic calculation unit, _{D N} entropy _{H (D N), D N} -1 of entropy _{H (D N-1),} ..., using the entropy H _{(D 0)} of _{D 0,} characterization of the traffic A traffic characteristic measuring apparatus characterized by A traffic acquisition unit for acquiring traffic;
A measurement target traffic extraction unit for extracting measurement target traffic;
A hierarchical traffic aggregation unit that aggregates traffic according to the hierarchical structure of the traffic to be measured;
An entropy calculator that calculates the entropy of aggregate traffic at each hierarchy;
A traffic characteristic measurement device having a traffic characteristic calculation unit for characterizing the traffic using entropy for each layer,
The hierarchical traffic aggregation unit aggregates traffic in N layers,
D _N traffic that aggregates at the highest layer, traffic aggregated at D _N-1 a stage lower layer thereof, when the traffic in front of the lowest hierarchy aggregating D _0, the entropy calculator, D _N entropy _{H (D} N), D conditioned in _{N D N-1} of entropy _{H (D N-1 | D} N), D D conditioned by _{N-1 N-2} entropy H _{(D N -2} | computes the _{D 1), | D N-} 1), ..., entropy _H of the _{D 0} which are conditioned by _{D 1 (D} 0
The traffic characteristic calculation unit includes an entropy _H (D N) of _{D N, D D} conditioned in _{N N-1} of entropy _{H (D N-1 | D} N), D conditioned by _{D N-1 N −2} entropy H (D _N−2 | D _N−1 ),..., D ₁ , D ₀ entropy H (D ₀ | D ₁ ) is used to characterize the traffic. Traffic characteristic measuring device. The entropy calculation unit normalizes the entropy for each layer by its maximum value,
8. The traffic characteristic measuring apparatus according to claim 6, wherein the traffic characteristic calculation unit performs traffic characteristic using the normalized entropy for each layer.   9. The traffic characteristic calculation unit generates a time series of traffic entropy aggregated in a hierarchical manner, and detects an abnormality in traffic based on a change in the time series. The traffic characteristic measurement method described in 1.

Images