Abstract:
Described is a system and method for receiving first data corresponding to usage of a network, receiving second data corresponding to usage of the network, comparing the first data to the second data and providing an indication of a network event when the second data varies from the second data greater than a predetermined threshold.

Description:
BACKGROUND 
     Computer networks, such as those utilizing the Internet Protocol (“IP”) are subject to security violations. These security violations can include activities such as reconnaissance, exploits, denial of service (“DoS”), and misuse of the network. In the case of exploits, DoS attacks, and misuse, the security violations are often only detected after the security violations have begun. By the time the security violations are detected, damage (e.g., slowed traffic, corrupted data, stolen data, etc.) may have already occurred. 
     It is desirable, therefore, to detect security violations as early as possible. One method of doing this is to detect reconnaissance (i.e., scanning) attacks, which are often a precursor to the other types of security violations. By detecting the scanning attacks, the other types of security violations are anticipated, and preventative measures may be taken. Accordingly, there is a need for a method of detecting the scanning attacks reliably and accurately. 
     SUMMARY OF THE INVENTION 
     A method for receiving first data corresponding to usage of a network, receiving second data corresponding to usage of the network, comparing the first data to the second data and providing an indication of a network event when the second data varies from the second data greater than a predetermined threshold. 
     A system having a data collection module to receive first data corresponding to usage of a network, a data collection module to receive second data corresponding to usage of the network, a comparison module to compare the first data and the second data and an output module to provide an indication of a network event when the second data varies from the first data greater than a predetermined threshold. 
     A computer system comprising a memory for storing a set of instructions and a processor for executing the set of instructions. The set of instructions being operable to receive first data corresponding to usage of a network, receive second data corresponding to usage of the network, compare the first data and the second data and provide an indication of a network event when the second data varies from the first data greater than a predetermined threshold. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         FIG. 1  shows an exemplary embodiment of a grid corresponding to a network graph according to the present invention. 
         FIG. 2  shows an exemplary embodiment of an IP address usage graph according to the present invention. 
         FIG. 3  shows an exemplary embodiment of another IP address usage graph according to the present invention. 
         FIG. 4A  shows an exemplary embodiment of an IP address usage graph before scanning activity is recorded according to the present invention. 
         FIG. 4B  shows an exemplary embodiment of the IP address usage graph of  FIG. 4A  after scanning activity is recorded according to the present invention. 
         FIG. 5  shows an exemplary embodiment of a method according to the present invention. 
         FIG. 6  shows an exemplary embodiment of a graph of a first statistic, which shows potential scanning activity according to the present invention. 
         FIG. 7  shows an exemplary embodiment of a graph of a second statistic, which shows potential scanning activity according to the present invention. 
         FIG. 8  shows an exemplary embodiment of a graph of the first statistic, which does not show scanning activity according to the present invention. 
         FIG. 9  shows an exemplary embodiment of a graph of the second statistic, which does not show scanning activity according to the present invention. 
         FIG. 10  shows an exemplary embodiment of another method according to the present invention. 
         FIG. 11  shows an exemplary embodiment of a graph of a third statistic, which shows potential scanning activity according to the present invention. 
         FIG. 12  shows an exemplary embodiment of a graph of a fourth statistic, which shows potential scanning activity according to the present invention. 
         FIG. 13  shows an exemplary embodiment of a graph of the third statistic, which does not show scanning activity according to the present invention. 
         FIG. 14  shows an exemplary embodiment of yet another method according to the present invention. 
         FIG. 15  shows an exemplary embodiment of a data record according to the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     The present invention may be further understood with reference to the following description and the appended drawings, wherein like elements are referred to with the same reference numerals. The exemplary embodiment of the present invention describes a method for monitoring network activity and detecting scanning activity within a network. A method for visualizing network activity will be described below, followed by a discussion of exemplary methods for detecting scanning activity. 
     The methods described herein may be performed, either partially or entirely on one or more computing devices. The computing device(s) may include components such as a processor (e.g., a microprocessor, an application-specific integrated circuit (“ASIC”), etc.) for executing instructions, a memory (e.g., a hard drive, a random-access memory (‘RAM”), etc.) for storing the instructions and data, an input device (e.g., a keyboard, a mouse, etc.), an output device (e.g., a monitor), and a network communications arrangement (e.g., a network interface card, a wireless adapter, etc.). 
     In the exemplary embodiment, a method for visualizing network activity utilizes NetFlow data. However, those skilled in the art will understand that other types of data may also be utilized for visualizing network activity. NetFlow refers to a technology and applications utilizing this technology, which are available from Cisco Systems, Inc. NetFlow allows measurements to be made for applications such as network traffic accounting and network monitoring. As would be known to one skilled in the art, scanning activities are often used by would-be assailants of the network to identify network topology, operating systems, and/or network services running on potential target systems residing in the network. By observing Netflow data traversing the routers in the network, it is possible to detect scanning activity and thus anticipate other security violations. It is also possible to detect Internet Protocol (“IP”) address spoofing using NetFlow data. 
     After Netflow data has been acquired, it is necessary to organize the NetFlow data in a manner that is conducive to the detection of scanning activity. One method of organizing the NetFlow data is to use IP Graph. IP Graph is software developed by AT&amp;T Corp. (“AT&amp;T”) to graphically represent IP addresses. IP Graph utilizes a two-dimensional grid  100  of coordinate values corresponding to a network graph, as illustrated in an exemplary embodiment shown in  FIG. 1 . In the exemplary embodiment, the grid  100  is a 16 by 16 square formed by blocks numbered from 0 to 255. Each block may be used to represent part or all of an IP address whose 32 bits are denoted as A.B.C.D. Because there are 256 blocks, it is possible to represent the first 8 bits of the IP address (denoted by the letter, “A”) by marking the block whose number matches the numerical value of the first 8 bits. For example, if the first 8 bits of the IP address are 11111111 (255 in base ten) the block number 255 may be marked (e.g., colored or highlighted) to indicate this. The next 8 bits of the IP address (denoted by the letter, “B”) may also be represented by dividing each of the 256 A blocks into 256 smaller B blocks. For example, if B is 11111111, then A.B may be represented by marking a B block number 255, which is located in the lower right-hand corner of the A block number 255. 
     In the exemplary embodiment of the grid  100 , only the first 16 bits of the IP address (i.e., A.B) are represented. However, in other embodiments, additional bits of the IP address may be represented through further subdivision of the grid  100 , changing the dimensions of the grid  100 , etc. In addition, the grid  100  may be used to display other information. For example, a third dimension may be used to represent traffic volume (e.g., the number of flows, packets, bytes, etc.) for each IP address. The number and size of the dimensions of the grid  100  may therefore be customized to a user&#39;s specification as well as for compatibility with hardware on which IP Graph is run (e.g., sizing the grid  100  so that the total number of blocks is less than or equal to a maximum number of pixels a video monitor is capable of displaying). 
       FIG. 2  shows an exemplary embodiment of an IP address usage graph  200 , which illustrates the number of unique 16-bit portions of destination IP addresses observed from NetFlow data during a predetermined time interval (e.g., 10 minutes). By examining changes to network graphs over various time intervals, scanning activity can be detected. For example, if a subsequent network graph were to show a significant increase in the number of destination IP addresses, this may indicate that scanning activity has occurred. Exemplary methods of detecting scanning activity using network graphs will be described in detail below. 
       FIG. 3  shows an exemplary embodiment of a network graph  300 , which illustrates the number of unique 16-bit portions of destination IP addresses announced by AT&amp;T&#39;s Internet Gateway Routers (“IGRs”) belonging to the network. As would be known to one skilled in the art, the destination IP addresses depicted in the network graph  300  include addresses that are owned and/or managed by an owner of the network. For example, the network graph  300  shows several blocks  310 ,  320 ,  330 ,  340  and  350 , which are substantially filled-in, indicating that the blocks  310 - 350  represent large blocks of destination IP addresses owned or managed by AT&amp;T. It will be appreciated that with this ownership information, the task of monitoring the network may be greatly simplified by focusing only on those areas of the network graph  300  which are owned and/or managed by the network provider. Thus, in analyzing network graphs generated from NetFlow data, it may be preferable to ignore blocks that do not belong to the owner. In addition to simplifying network monitoring, the network graph  300  also defines disallowed space. That is, destination IP addresses outside of the ones represented in the network graph  300  may indicate routing and/or security problems. 
       FIG. 4A  shows an exemplary embodiment of a network graph  400  before scanning activity is recorded. The network graph  400  may represent the network at any point in time. If additional network graphs were recorded prior to the network graph  400 , a comparison between the network graph  400  and the previous network graphs may be made using a method according to the present invention (which will be described below) to confirm that no scanning activity has occurred. 
       FIG. 4B  shows an exemplary embodiment of a network graph  410  after scanning activity is recorded. The network graph  410  was recorded during a time interval following that of the network graph  400 . For example, the network graph  410  may have been recorded ten minutes after the network graph  400 . Thus, in the ten minutes that elapsed between the graphs  400 ,  410 , scanning activity occurred over the network. The scanning activity is represented by a block  444 , which is substantially filled-in, indicating that most of the destination IP addresses of the block  444  have been targeted. Referring to  FIG. 1 , it may be seen that the block  444  corresponds to the A block number 32 (00100000 in base two). Therefore, most of the destination IP addresses with A equal to 00100000 were targeted. 
     From the example discussed above with reference to  FIGS. 4A-B , it has been demonstrated that visual inspection of the network graphs  400 ,  410  may be sufficient to identify scanning activity. However, visual inspection may not always be feasible. For example, in a large network with hundreds of routers and thousands of links, visual inspection of even a single network graph is tedious and difficult. The task of visual inspection is made even more onerous when a system administrator or other user must compare multiple network graphs across different time intervals. Accordingly, the present invention is directed towards providing a method of detecting scanning activity without requiring visual inspection. Two such exemplary methods will now be described in conjunction with  FIGS. 5-13 . 
       FIG. 5  shows an exemplary embodiment of a method  500  for detecting scanning activity using the Kolmogorov-Smirnov (“K-S”) test. As known to those skilled in the art of statistics, the K-S test may be used to determine if two datasets differ significantly. For example, the K-S test may be used to perform a goodness-of-fit test between an empirical distribution function, F(x) and a hypothesized distribution function, F 0 (x). A null hypothesis, H 0  is selected such that F(x)=F 0 (x) for all x against an alternative hypothesis, H 1  such that F(x)≠F 0 (x) for some x. In step  510 , empirical and hypothesized distribution functions, {circumflex over (F)} n (k) and {circumflex over (F)} n-1 (k) are determined from data recorded during an nth and an (n−1)th time interval, respectively. The (n−1)th time interval may correspond to that of an earlier network graph (e.g., network graph  400 ), while the nth time interval may correspond to a later network graph (e.g., network graph  410 ). Accordingly, the null hypothesis, H 0  is {circumflex over (F)} n (k)={circumflex over (F)} n-1 (k) for all k, and the alternative hypothesis, H 1  is {circumflex over (F)} n (k)≠{circumflex over (F)} n-1 (k) for some k. The distribution functions {circumflex over (F)} n (k) and {circumflex over (F)} n-1 (k) may be determined according to the formula 
                   F   ^     ⁡     (   k   )       =         ∑     j   =   0     k     ⁢     I   j           ∑     j   =   0     255     ⁢     I   j           ,     0   ≤   k   ≤     255.   ⁢           ⁢     I   j               
is a numerical value corresponding to the number of unique Bs in a recorded sample where A equals j. (A and B represent the first and second set of eight bits, respectively, in a 32-bit IP address). Thus, the distribution functions {circumflex over (F)} n (k) and {circumflex over (F)} n-1 (k) represent the sum of the number of unique Bs for each A up to j as a fraction of the total number of unique Bs for all As.
 
     In step  520 , two statistics, D n  and D′ are determined according to the formulas 
               D   n     =         max     k   ∈     (     0   ,   255     )         ⁢                  F   ^     n     ⁡     (   k   )       -         F   ^       n   -   1       ⁡     (   k   )              ⁢           ⁢   and   ⁢           ⁢     D   ′         =       ∑     k   =   0     255     ⁢                F   ^     k     -       G   ^     k            .               
represents the maximum difference between the distribution functions {circumflex over (F)} n (k) and {circumflex over (F)} n-1 (k) at corresponding values of k, and D′ represents the sum of the absolute differences between the two distribution functions {circumflex over (F)} n (k) and {circumflex over (F)} n-1 (k). D n  may be used to identify increases in the number of prefixes within a given A block and is effective in detecting scans which target individual A blocks, whereas D′ is useful for detecting scans which target multiple A blocks. It should be noted that the distribution functions shown for D n  and D′ are the same, even though the notation is shown differently.
 
     In step  530 , D n  and D′ are compared to threshold values in order to detect scanning activity. The threshold values may be determined based on empirical data. For example, the threshold values may be a moving average values of D n  and D′ observed under normal conditions for some interval, plus some standard deviations. If the threshold values are exceeded, this may indicate that scanning activity has occurred. Referring to  FIG. 6 , an exemplary data graph  600  shows D n  plotted over various time intervals. A threshold value  610  is shown as a line and is determined from empirical data. For example, the threshold value  610  may be determined by adding 3.5 times the standard deviation to an average D′ value, which is calculated from a set of time intervals that are relatively free of scanning activity. A majority of the data points are below the threshold value  610 , however there are also a substantial number of data points above the threshold value  610 . These latter data points are referred to as outliers, and indicate that scanning activity may have occurred. 
     Similarly, an exemplary data graph  700  is shown in  FIG. 7 , which plots D′ over various time intervals and includes a threshold value  710 . The threshold value  710  may be determined in a manner similar to that of the threshold  710 . As evidenced by the appearance of outliers, the data graph  700  corroborates the results of the data graph  600 .  FIGS. 8 and 9  show exemplary embodiments of data graphs  800  and  900 , which plot D n  and D′, respectively, when excluding the block that was scanned. In contrast to the data graphs  600  and  700 , few or no data points are above the threshold values  610 ,  710 . 
     In the exemplary embodiment of the method  500 , only the A.B portion of the destination IP address was used. However, in other embodiments it may be possible to perform the method  500  using additional portions of the destination IP address. How much of the destination IP address is used may depend on, among other things, the size/dimensions of the grid  100 . In addition, it may also be possible to perform the method  500  multiple times on different portions of the destination IP address. For example, the user may initially wish to use only the A.B portion. If potential scanning activity was detected after doing so, the user may then wish to repeat the method  500  using the A.B.C portion in order to analyze the potential scanning activity in more detail and determine if specific prefixes within a C block are being targeted. 
       FIG. 10  shows an exemplary embodiment of a method  1000  for detecting scanning activity using an entropy test. Unlike the K-S test using the D n  and D′ statistics, the entropy test is not based on a cumulative distribution, and is therefore effective in detecting sudden increases in the number of prefixes over a time interval. However, one drawback to the entropy test is that it does not provide any information regarding which blocks are being targeted. Therefore, it may be desirable, but not required, to use both the methods  500 ,  1000  to detect scanning activity. As with the method  500 , the method  1000  will be described with reference to the A.B portion of the destination IP address. However, other embodiments may use other portions of the destination IP address. In step  1010 , four entropy factors, N 00 , N 01 , N 10  and N 11  are determined. Given two sets of destination IP addresses, where the second of the two sets is recorded after the first set, such as in the network graphs  400 , 410 , N 00  is the number of unique A.Bs that appear in both sets, N 01  is the number of unique A.Bs in the first set, but not the second, N 10  is the number of unique A.Bs that appear in the second set, but not the first, and N 11  is the number of unique A.Bs that do not appear in either set. 
     In step  1020 , an entropy, H is determined where 
                   H   =       ⁢     -             ln   (         (       N   00         N   00     +     N   01         )       N   00       ⁢       (       N   01         N   00     +     N   01         )       N   01                           (       N   10         N   10     +     N   11         )       N   01       ⁢       (       N   11         N   10     +     N   11         )       N   11         )               N   00     +     N   01     +     N   10     +     N   11                       =       ⁢     -                   N   00     ⁢   ln   ⁢       N   00         N   00     +     N   01           ⁢           +       N   01     ⁢   ln   ⁢       N   01         N   00     +     N   01           ⁢           +                     N   10     ⁢   ln   ⁢       N   10         N   10     +     N   11           ⁢           +       N   11     ⁢   ln   ⁢       N   11         N   10     +     N   11             ⁢                       N   00     +     N   01     +     N   10     +     N   11         .                   
The entropy H indicates the difference between the two sets. When the sets are identical, H equals zero. As the difference between the two sets increases (indicating possible scanning activity), the entropy H correspondingly increases.
 
     It may also be desirable to determine whether the sets are different using a steady-state entropy in addition to, or instead of, the entropy H. Accordingly, two transition probabilities, a and β are determined along with a steady-state entropy, H′. α represents the probability of remaining in the second set during the next time interval, and β represents the probability of remaining out of the second set during the next time interval. These transition probabilities are determined according to the formulas 
               α   =       N   00         N   00     +     N   01           ,     β   =         N   11         N   10     +     N   11         .             
The steady-state entropy H′ is a function of α and β, and is determined according to the formula
 
                 H   ′     ⁡     (     α   ,   β     )       =     -                   (     1   -   β     )     ⁢     (       α   ⁢           ⁢   ln   ⁢           ⁢   α     +       (     1   -   α     )     ⁢     ln   ⁡     (     1   -   α     )           )       +                 (     1   -   α     )     ⁢     (       β   ⁢           ⁢   ln   ⁢           ⁢   β     ⁢           +       (     1   -   β     )     ⁢           ⁢     ln   ⁡     (     1   -   β     )           )               2   -   α   -   β       .             
In order to simplify computations, the steady-state entropy H′ may be approximated using smoothed values of α and β, which are obtained after applying exponential smoothing with a smoothing constant, w where 0&lt;w&lt;1. The smoothed values, which are denoted by the symbols {circumflex over (α)} n ,{circumflex over (β)} n , correspond to α and β when evaluated at an nth time interval and may be determined according to the formulas {circumflex over (α)} n =wα n-1 +(1+w){circumflex over (α)} n-1 , {circumflex over (β)} n =wβ n-1 +(1−w){circumflex over (β)} n-1  where
 
                 α     n   -   1       =       N   00     n   -   1           N   00     n   -   1       +     N   01     n   -   1             ,       β     n   -   1       =         N   11     n   -   1           N   10     n   -   1       +     N   11     n   -   1           .             
Having determined the smoothed values {circumflex over (α)} n , {circumflex over (β)} n , it is now possible to approximate H′ according to the formula
 
     
       
         
           
             
               
                 H 
                 ′ 
               
               ⁡ 
               
                 ( 
                 
                   α 
                   , 
                   β 
                 
                 ) 
               
             
             ≈ 
             
               
                 
                   H 
                   ′ 
                 
                 ⁡ 
                 
                   ( 
                   
                     
                       α 
                       ^ 
                     
                     , 
                     
                       β 
                       ^ 
                     
                   
                   ) 
                 
               
               + 
               
                 
                   
                     ∂ 
                     
                       
                         H 
                         ′ 
                       
                       ⁡ 
                       
                         ( 
                         
                           α 
                           , 
                           β 
                         
                         ) 
                       
                     
                   
                   
                     ∂ 
                     α 
                   
                 
                 ⁢ 
                 
                   
                     
                        
                       
                         α 
                         = 
                         
                           α 
                           ^ 
                         
                       
                     
                     ⁢ 
                     
                       
                         ( 
                         
                           α 
                           - 
                           
                             α 
                             ^ 
                           
                         
                         ) 
                       
                       + 
                       
                         
                           ∂ 
                           
                             
                               H 
                               ′ 
                             
                             ⁡ 
                             
                               ( 
                               
                                 α 
                                 , 
                                 β 
                               
                               ) 
                             
                           
                         
                         
                           ∂ 
                           β 
                         
                       
                     
                      
                   
                   
                     β 
                     = 
                     
                       β 
                       ^ 
                     
                   
                 
                 ⁢ 
                 
                   
                     ( 
                     
                       β 
                       - 
                       
                         β 
                         ^ 
                       
                     
                     ) 
                   
                   . 
                 
               
             
           
         
       
     
     In step  1030 , a mean, E and a variance, Var of the entropy H are determined according to the formulas 
     
       
         
           
             
               
                 
                   
                     
                       var 
                       ⁡ 
                       
                         ( 
                         α 
                         ) 
                       
                     
                     = 
                     
                       
                         
                           α 
                           ^ 
                         
                         ⁡ 
                         
                           ( 
                           
                             1 
                             - 
                             
                               α 
                               ^ 
                             
                           
                           ) 
                         
                       
                       
                         
                           N 
                           00 
                         
                         + 
                         
                           N 
                           01 
                         
                       
                     
                   
                   , 
                   
                     
                       var 
                       ⁡ 
                       
                         ( 
                         β 
                         ) 
                       
                     
                     = 
                     
                       
                         
                           β 
                           ^ 
                         
                         ⁡ 
                         
                           ( 
                           
                             1 
                             - 
                             
                               β 
                               ^ 
                             
                           
                           ) 
                         
                       
                       
                         
                           N 
                           10 
                         
                         + 
                         
                           N 
                           11 
                         
                       
                     
                   
                   , 
                   
                     
                       E 
                       ⁡ 
                       
                         ( 
                         
                           
                             H 
                             ′ 
                           
                           ⁡ 
                           
                             ( 
                             
                               α 
                               , 
                               β 
                             
                             ) 
                           
                         
                         ) 
                       
                     
                     ≈ 
                     
                       
                         
                           
                               
                             
                                 
                             
                             ⁢ 
                             
                               
 
                             
                             ⁢ 
                             
                               
                                 
                                   H 
                                   ′ 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       a 
                                       ^ 
                                     
                                     , 
                                     
                                       β 
                                       ^ 
                                     
                                   
                                   ) 
                                 
                               
                               , 
                               
                                 
                                   
                                     ∂ 
                                     
                                       
                                         H 
                                         ′ 
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           α 
                                           , 
                                           β 
                                         
                                         ) 
                                       
                                     
                                   
                                   
                                     ∂ 
                                     α 
                                   
                                 
                                 = 
                                 
                                   
                                     - 
                                     
                                       
                                         
                                           
                                             ( 
                                             
                                               1 
                                               - 
                                               β 
                                             
                                             ) 
                                           
                                           ⁢ 
                                           
                                             ( 
                                             
                                               
                                                 ln 
                                                 ⁢ 
                                                 
                                                     
                                                 
                                                 ⁢ 
                                                 α 
                                               
                                               + 
                                               
                                                 ln 
                                                 ⁡ 
                                                 
                                                   ( 
                                                   
                                                     1 
                                                     - 
                                                     α 
                                                   
                                                   ) 
                                                 
                                               
                                             
                                             ) 
                                           
                                         
                                         - 
                                         
                                           ( 
                                           
                                             
                                               β 
                                               ⁢ 
                                               
                                                   
                                               
                                               ⁢ 
                                               ln 
                                               ⁢ 
                                               
                                                   
                                               
                                               ⁢ 
                                               β 
                                             
                                             + 
                                             
                                               
                                                 ( 
                                                 
                                                   1 
                                                   - 
                                                   β 
                                                 
                                                 ) 
                                               
                                               ⁢ 
                                               
                                                 ln 
                                                 ⁡ 
                                                 
                                                   ( 
                                                   
                                                     1 
                                                     - 
                                                     β 
                                                   
                                                   ) 
                                                 
                                               
                                             
                                           
                                           ) 
                                         
                                       
                                       
                                         2 
                                         - 
                                         α 
                                         - 
                                         β 
                                       
                                     
                                   
                                   - 
                                   
                                     
                                       
                                         
                                           
                                             
                                               
                                                 ( 
                                                 
                                                   1 
                                                   - 
                                                   β 
                                                 
                                                 ) 
                                               
                                               ⁢ 
                                               
                                                 ( 
                                                 
                                                   
                                                     αln 
                                                     ⁢ 
                                                     
                                                         
                                                     
                                                     ⁢ 
                                                     α 
                                                   
                                                   + 
                                                   
                                                     
                                                       ( 
                                                       
                                                         1 
                                                         - 
                                                         α 
                                                       
                                                       ) 
                                                     
                                                     ⁢ 
                                                     
                                                       ln 
                                                       ⁡ 
                                                       
                                                         ( 
                                                         
                                                           1 
                                                           - 
                                                           α 
                                                         
                                                         ) 
                                                       
                                                     
                                                   
                                                 
                                                 ) 
                                               
                                             
                                             + 
                                           
                                         
                                       
                                       
                                         
                                           
                                             
                                               ( 
                                               
                                                 1 
                                                 - 
                                                 α 
                                               
                                               ) 
                                             
                                             ⁢ 
                                             
                                               ( 
                                               
                                                 
                                                   β 
                                                   ⁢ 
                                                   
                                                       
                                                   
                                                   ⁢ 
                                                   ln 
                                                   ⁢ 
                                                   
                                                       
                                                   
                                                   ⁢ 
                                                   β 
                                                 
                                                 + 
                                                 
                                                   
                                                     ( 
                                                     
                                                       1 
                                                       - 
                                                       β 
                                                     
                                                     ) 
                                                   
                                                   ⁢ 
                                                   
                                                     ln 
                                                     ⁡ 
                                                     
                                                       ( 
                                                       
                                                         1 
                                                         - 
                                                         β 
                                                       
                                                       ) 
                                                     
                                                   
                                                 
                                               
                                               ) 
                                             
                                           
                                         
                                       
                                     
                                     
                                       
                                         ( 
                                         
                                           2 
                                           - 
                                           α 
                                           - 
                                           β 
                                         
                                         ) 
                                       
                                       2 
                                     
                                   
                                 
                               
                               , 
                               
                                 
                                   
                                     ∂ 
                                     
                                       
                                         H 
                                         ′ 
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           α 
                                           , 
                                           β 
                                         
                                         ) 
                                       
                                     
                                   
                                   
                                     ∂ 
                                     β 
                                   
                                 
                                 = 
                                 
                                   
                                     - 
                                     
                                       
                                         
                                           
                                             
                                               
                                                 
                                                   ( 
                                                   
                                                     1 
                                                     - 
                                                     α 
                                                   
                                                   ) 
                                                 
                                                 ⁢ 
                                                 
                                                   ( 
                                                   
                                                     
                                                       ln 
                                                       ⁢ 
                                                       
                                                           
                                                       
                                                       ⁢ 
                                                       β 
                                                     
                                                     + 
                                                     
                                                       ln 
                                                       ⁡ 
                                                       
                                                         ( 
                                                         
                                                           1 
                                                           - 
                                                           β 
                                                         
                                                         ) 
                                                       
                                                     
                                                   
                                                   ) 
                                                 
                                               
                                               - 
                                             
                                           
                                         
                                         
                                           
                                             
                                               ( 
                                               
                                                 
                                                   α 
                                                   ⁢ 
                                                   
                                                       
                                                   
                                                   ⁢ 
                                                   ln 
                                                   ⁢ 
                                                   
                                                       
                                                   
                                                   ⁢ 
                                                   α 
                                                 
                                                 + 
                                                 
                                                   
                                                     ( 
                                                     
                                                       1 
                                                       - 
                                                       α 
                                                     
                                                     ) 
                                                   
                                                   ⁢ 
                                                   
                                                     ln 
                                                     ⁡ 
                                                     
                                                       ( 
                                                       
                                                         1 
                                                         - 
                                                         α 
                                                       
                                                       ) 
                                                     
                                                   
                                                 
                                               
                                               ) 
                                             
                                           
                                         
                                       
                                       
                                         2 
                                         - 
                                         α 
                                         - 
                                         β 
                                       
                                     
                                   
                                   - 
                                   
                                     
                                       
                                         
                                           
                                             
                                               
                                                 ( 
                                                 
                                                   1 
                                                   - 
                                                   β 
                                                 
                                                 ) 
                                               
                                               ⁢ 
                                               
                                                 ( 
                                                 
                                                   
                                                     αln 
                                                     ⁢ 
                                                     
                                                         
                                                     
                                                     ⁢ 
                                                     α 
                                                   
                                                   + 
                                                   
                                                     
                                                       ( 
                                                       
                                                         1 
                                                         - 
                                                         α 
                                                       
                                                       ) 
                                                     
                                                     ⁢ 
                                                     
                                                       ln 
                                                       ⁡ 
                                                       
                                                         ( 
                                                         
                                                           1 
                                                           - 
                                                           α 
                                                         
                                                         ) 
                                                       
                                                     
                                                   
                                                 
                                                 ) 
                                               
                                             
                                             + 
                                           
                                         
                                       
                                       
                                         
                                           
                                             
                                               ( 
                                               
                                                 1 
                                                 - 
                                                 α 
                                               
                                               ) 
                                             
                                             ⁢ 
                                             
                                               ( 
                                               
                                                 
                                                   β 
                                                   ⁢ 
                                                   
                                                       
                                                   
                                                   ⁢ 
                                                   ln 
                                                   ⁢ 
                                                   
                                                       
                                                   
                                                   ⁢ 
                                                   β 
                                                 
                                                 + 
                                                 
                                                   
                                                     ( 
                                                     
                                                       1 
                                                       - 
                                                       β 
                                                     
                                                     ) 
                                                   
                                                   ⁢ 
                                                   
                                                     ln 
                                                     ⁡ 
                                                     
                                                       ( 
                                                       
                                                         1 
                                                         - 
                                                         β 
                                                       
                                                       ) 
                                                     
                                                   
                                                 
                                               
                                               ) 
                                             
                                           
                                         
                                       
                                     
                                     
                                       
                                         ( 
                                         
                                           2 
                                           - 
                                           α 
                                           - 
                                           β 
                                         
                                         ) 
                                       
                                       2 
                                     
                                   
                                 
                               
                               , 
                               
                                 
                                   and 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     Var 
                                     ( 
                                     
                                       
                                         H 
                                         ′ 
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           α 
                                           , 
                                           β 
                                         
                                         ) 
                                       
                                     
                                     ) 
                                   
                                 
                                 ≈ 
                                 
                                   
                                     ( 
                                     
                                       
                                         ∂ 
                                         
                                           
                                             H 
                                             ′ 
                                           
                                           ⁡ 
                                           
                                             ( 
                                             
                                               α 
                                               , 
                                               β 
                                             
                                             ) 
                                           
                                         
                                       
                                       
                                         ∂ 
                                         α 
                                       
                                     
                                      
                                   
                                   
                                     α 
                                     = 
                                     
                                       α 
                                       ^ 
                                     
                                   
                                 
                               
                             
                             ) 
                           
                           2 
                         
                         ⁢ 
                         
                           var 
                           ⁡ 
                           
                             ( 
                             α 
                             ) 
                           
                         
                       
                       + 
                       
                         
                           ( 
                           
                             
                               ∂ 
                               
                                 
                                   H 
                                   ′ 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     α 
                                     , 
                                     β 
                                   
                                   ) 
                                 
                               
                             
                             
                               ∂ 
                               β 
                             
                           
                            
                         
                         
                           β 
                           = 
                           
                             β 
                             ^ 
                           
                         
                       
                     
                   
                 
                 ) 
               
               2 
             
             ⁢ 
             
               
                 var 
                 ⁡ 
                 
                   ( 
                   β 
                   ) 
                 
               
               . 
             
           
         
       
     
     The mean E and the variance Var are used to determine a threshold value for the steady-state entropy H′ at the nth time interval. The threshold value for the steady-state entropy H′ is determined according to the formula 
               E   ⁡     (       H   ′     ⁡     (     α   ,   β     )       )       +     3.5   ⁢         var   ⁡     (       H   ′     ⁡     (     α   ,   β     )       )         .             
A threshold value for the entropy H may also be determined using empirical data.
 
     In step  1040 , the entropy H and/or the steady-state entropy H′ are compared to their respective threshold values. If the respective threshold values are exceeded, this may indicate that scanning activity has occurred. Referring to  FIG. 11 , an exemplary data graph  1100  shows the entropy H plotted over various time intervals. As seen from the outliers above a threshold value  112 , scanning activity may have occurred. The threshold value  112  may be determined in a manner similar to that of the threshold value  610  (e.g., an average value plus 3.5 times a standard deviation). A similar data graph is shown in  FIG. 12 , which shows an exemplary data graph  1200  plotting the steady-state entropy H′. The data graph  1200  shows two threshold lines  122  and  124 , which are calculated using w values of 0.8 and 0.2, respectively. When w is close to 1, as is the case with the threshold line  122 , the threshold line has a tendency to follow the original data. When w is close to 0, as is the case with the threshold line  124 , the threshold line is smoother and does not follow the original data as closely. As can be seen, using the threshold line  122  results in fewer outliers.  FIG. 13  shows an exemplary data graph  1300  which plots the entropy H over various data values. In contrast to the data graph  1100 , few or none of the data points are above the threshold value  112 , indicating that scanning activity has not occurred. 
       FIG. 14  shows an exemplary embodiment of a method  1400  for monitoring network activity. The method  1400  may be performed automatically at scheduled intervals, or at the request of the user. In step  1410 , network data (e.g., NetFlow data) is collected and graphed. The collection and/or graphing of the network data may be performed whenever the method  1400  is initiated, or the network data could be retrieved from a database which is continually updated with new network data. This may be performed using IP graph as discussed above. NetFlow data is retrieved from routers in the network, and destination IP addresses are plotted on a network graph. Although not necessary for the detection of scanning activity, the graphing of the network data allows the user to visualize traffic rather than relying solely on the output of a scanning activity analysis. Graphing the network data also facilitates the detection of trends in and/or substantial changes to the network activity. 
     In step  1420 , the network graph is analyzed for potential scanning activity. Data points on the network graph may be analyzed, for example, using one or both of the methods  500 ,  1000 . For example, the user may choose to monitor for scanning activity using the method  500  and then confirm the results of the method  500  by performing the method  1000  or a visual inspection. Data graphs of the D n  and D′ statistics and/or the entropy H and/or the steady-state entropy H′ may be generated depending on which method(s) are used to analyze the network graph. Accordingly, in step  1430 , a determination is made as to whether potential scanning activity has been detected. 
     In step  1440 , if potential scanning activity was detected, the source(s) of the potential scanning activity are determined. This may be done by first locating the time intervals at which outliers are located. For example, in  FIG. 6 , the k values for each outlier may be used to locate the block(s) targeted by the outlier. This may be done for all the time intervals at once, or the time intervals may be split and evaluated separately. In the exemplary embodiment of the data graph  600 , splitting the time intervals and evaluating only the first 1440 minutes (i.e., one day) yields 7 groups of outliers beginning at the 20 th  10-minute interval and whose k values indicate that the block number 32 was targeted. Each outlier group consists of two outliers, which are followed by a period of normal activity. Having identified the target block, NetFlow data may then be used to reveal additional information.  FIG. 15  shows an exemplary data record  1500 , which lists NetFlow records for the time intervals corresponding to the data graph  600 . For brevity, only the records for the 20 th  10-minute interval are shown. These records indicate that for the first scan, a single Ping packet was sent to every other address in the second (i.e., B) portion of the destination IP addresses with the form 32.x.0.53. The sizes of the Ping packets varied from 66 to 70 bytes, and the average time between scans was approximately 1.5 seconds. For each destination IP address targeted, the source IP address was 209.12.44.46. The scanning source corresponding to the source IP address may then be identified by, for example, performing a reverse Domain Name System (“DNS”) lookup. 
     In step  1450 , a response procedure is performed. For example, the system administrator may be alerted to the potential scanning activity. In certain situations, no further action may be required. Such instances may occur when the scanning source is a server (e.g., DNS, Network Time Protocol (“NTP”), web, mail, Netnews, etc.) which communicates with many clients. In these instances, the potential scanning activity does not ordinarily warrant further investigation. Potential scanning activity from other sources however, would likely raise suspicion and therefore would require investigation. Such investigation may include communicating with system administrators who manage the network on which the scanning source is located. This may enable the scanning source to be further identified (e.g., a particular computer or group of computers). In addition to investigation, the response procedure may also include preventative measures, such as blocking requests from the scanning source. This may be performed automatically (e.g., when a predetermined number of packets and/or Pings have been sent from the scanning source) or performed at the discretion of the system administrator. 
     In the exemplary embodiments described above, a 10-minute time interval was used. However, in other embodiments, time intervals of different durations may be used, either alone or together. If the time interval is substantially longer that the duration of the potential scanning activity, the potential scanning activity is unlikely to be noticed because it is small in duration compared to the duration of normal activities. If the time interval is too short, the potential scanning activity may be hard to distinguish from the normal activities. It may therefore be desirable to perform the methods of the present invention using multiple time intervals of various durations. The number and/or length of these multiple time intervals may be affected by considerations such as the amount of time required to execute the methods using the multiple time intervals. 
     In addition to detecting scanning activity, the methods described above may also be used to detect IP spoofing. By applying the above described methods to source IP addresses rather than destination IP addresses, the user may be able to monitor changes in the number and/or distribution of the source IP addresses. Sudden changes in the number of unique source IP addresses, or changes to the distribution thereof, may indicate that spoofing techniques are being used to impersonate legitimate source IP addresses. Thus, the present invention may be capable of detecting current security violations in addition to anticipating future security violations. 
     There are many modifications of the present invention which will be apparent to those skilled in the art without departing from the teachings of the present invention. The embodiments disclosed herein are for illustrative purposes only and are not intended to describe the bounds of the present invention, which is to be limited only by the scope of the claims appended hereto.