WORM DETECTION BY TRENDING FAN OUT

Field of the invention

[001] The invention is directed to communication networks and in particular to worm detection by assessing the trend of the fan-out traffic at a node.

Background of the Invention

[002] The reliability and security of an IP network is essential in a world where computer networks are a key element in intra-entity and inter-entity communications and transactions. While the current network security systems have been around for years, to date none have been able to deliver on the final goal of providing full protection against all malicious attacks with little associated cost and annoyance.

[003] Providing a security solution requires an understanding of possible threat scenarios and their related requirements. There are many types of security concerns that must be considered in a network, among which, the network worms are regarded as a growing threat. Lately, large scale worms spread all over the Web, producing serious damages both to the network/service providers and users. Attacks on network security increased tenfold between 1993 and 2003, from 1 ,334 to 137,529 {CERT Coordination Center). Furthermore, 20-40 new or variant virus threats were reported daily to TrendMicro in 2003. The number of attacks between January and June, 2003 exceeded 70,000, which is the double of those of the previous year (Reuters). Viruses cost businesses around the world $55 billion in 2003, up from $13 billion in 2001 {TrendMicro).

[004] A worm is a self propagating program that resides in the memory of the attacked system and duplicates itself, without altering the resident applications and files, but using parts of the operating system. It is common for worms to be noticed only when their uncontrolled replication consumes system resources,

slowing or halting other applications. By hijacking trusted applications such as web servers, mail transfer agents and log-in servers, which typically run with elevated privileges, worms can gain full access to system resources, and cause a complete system compromise. Even though the impact of a single worm on any given piece of network equipment can be benign, the cumulative effects of tens of thousands of infected network devices spreading the malware to other devices connected to the network can be disastrous.

[005] Network security is one of the biggest challenges of the Internet, due to Internet's unrestricted connectivity, openness, and widespread software homogeneity. Infected hosts with high bandwidth network connections can initiate thousands of connections requests /second, each of which has the potential to spread the infection. Worm detection must be performed quickly to recognize and identify the attacker. Also, antivirus systems are of little use if they fail to be triggered quickly after a host is infected.

[006] Furthermore, many security experts believe that the newer communications channels, such as instant messaging (IM) and VoIP, pose a very serious threat to networks. According to Gartner Group research, 58% of network security managers stated that instant messaging poses the most dangerous security risk to their enterprise. Symantec Security Response predicts that the next major worm exploit will be IM-based. It is assumed that IM exploit could spread to half a million computers in just 30 seconds. One implication is that "signature based" techniques cannot prevent the initial outbreak; a "behavior based" approach is needed.

[007] Stealth worms, or slow-spreading worms, are worms that make infection attempts at a rate significantly below the rate of the normal traffic. Also, worms that escape notice without being specifically designed to do so are sometimes also described as stealth viruses/worms. A stealth worm has various

mechanisms designed to avoid detection by antivirus software. Typically, when an antivirus software runs, the stealth worm hides itself in the memory, and uses various tricks to also hide changes it has made to any host software and data. For example, a stealth worm may maintain a copy of the original, uninfected data in a certain area of the host memory and monitor the host activity. When the antivirus software attempts to find if data has been altered, the worm redirects it to the storage area that maintains the original, uninfected data, so that the antivirus software is tricked into believing that the host is healthy.

[008] While the techniques used by the stealth worms limit the infection rate, these worms merely require a little more time to achieve the same growth as the fast worms, while being significantly harder to catch as they blend in with the normal traffic. The purpose of worms is also changing: with the new emphasis on crime and monetary profits, stealth worms are being used to target particular companies or customer to steal passwords, credit card information and so on. This means that many stealth worms are designed to stay-under-the-radar by purposely not infecting many machines so as to remain undetected. The implication is that stealth worms have a very different behavior than the flash worms and require different detection techniques.

[009] Ideally, a network operator strives to identify fast an infected machine and quarantine it as soon as possible; otherwise, the infection could well spread before any alarm is raised. However, the price to pay for detecting and preventing security attacks is overwhelming. Today, enterprises deploy a layered defense model, which includes firewalls, anti-virus systems, access management and intrusion detections systems (IDS). Besides being expensive, responsiveness of these defense systems is impacted by the fact that the current solutions are based on multiple components, which may have problems to communicate and coordinate the required counter-measures.

[0010] A methodology for detection of Internet worms is presented in the article "The Monitoring and Early Detection of Internet Worms" (Zou et al.), August 2004. The system proposed in this article uses a Kalman filter to estimate traffic parameters in a known epidemic model. The problem with this approach is twofold: first, the Kalman filters are difficult to implement, and second, assuming that a worm spreads according to a specific class of epidemic models is dangerous, as the malware could be coded in a way so as to avoid this type of behavior.

[0011] Most research on worm detection has focused so far on catching fast spreading worms. For example, the co-pending patent application SN 11/450348 entitled: "Method for Estimating the Fan-In and/or Fan-Out of a Node" (Rabinovitch), filed on 12 June, 2006 and assigned to Alcatel describes a method for detecting anomalies in traffic patterns and a traffic anomalies detector are presented. The method and the detector are based on estimating the fan-in of a node, i.e. the number of distinct sources sending traffic to a node, based on infrequent, periodic sampling. Destinations with an abnormally large fan-in are likely to be the target of an attack, or to be downloading large amounts of material with a P2P application. The method and the anomalies detector are extremely simple to implement and exhibit excellent performance on real network traces.

[0012] Co-pending patent application SN 11/656434 (Chow et al.) fully identified above describes a malware detection and response system based on traffic pattern anomalies detection, whereby packets on each port of a network element (NE) are counted distinctly over a selected period of time, according to their transmission protocol and traffic direction. An attack is declared when an individual count or combination of counts exceeds a threshold. The system can be incorporated into the fast path, that is, the data plane, enabling

communications systems such as switches, routers, and DSLAMs to have built-in security at a very low cost.

[0013] However, as discussed above, detecting a worm that scans fast has its own set of techniques, which cannot apply to slow worms. Little work (if any) has been done on detecting worms that spread at a rate that is so slow that they can not be detected by the above mentioned types of methods. The above described malware detection method will not notice anything unusual in case of worms that only attempt a single probe in each time window, or even a single probe in many time windows.

Summary of the Invention

[0014] It is an object of the invention to provide a system for detecting propagation of stealth worms.

[0015] Accordingly, the invention provides a system for detecting stealth worms at an egress port of a network element (NE) connected in a data network, comprising: a header data processing unit for extracting address data from the header of the PDU; means for establishing a time window; means for storing a benchmark plot AiIk), where A _k is an expected number, and k takes values between 7 and N; means for determining for the source NE, a set of destination NEs to which the source NE has sent PDUs during a current time window; means for determining for each of N successive time windows a current number X _k , which provides the total number of destination NEs in the data network to which the source NE sent PDUs during k successive time windows; and means for identifying a stealth worm attack when the current number X _k is significantly different from the expected number Ak on the benchmark plot.

[0016] The invention also provides a method for detecting stealth worms at an egress port of a network element (NE) connected in a data network, comprising

the steps of: a) examining header data of each PDU seen on the port for identifying address data for the PDU; b) storing a benchmark A _k (k) plot providing the expected number of destination NEs A _k in the data network to which a source NE sends PDUs; c) determining for the source NE, a set of destination NEs to which the source NE has sent PDUs during a current time window; d) determining for each of N successive time windows a current number Xz ₀ which provides the total number of destination NEs in the data network to which the source NE sent PDUs during k successive time windows; and e) identifying a stealth worm attack when the current number X _k is significantly different from the expected value A _k on the benchmark plot.

[0017] Advantageously, the system of the invention is an inexpensive solution that is easy to install, resulting in a low-cost way of detecting stealth worm traffic while minimizing false positives generated by normal traffic. The invention can be implemented in a way that has minimal impact on the datapath of the router, and allows for tracking of sources that are likely to be spreading slow scanning worms.

Brief Description of the drawings [0018] The foregoing and other objects, features and advantages of the invention will be apparent from the following more particular description of the preferred embodiments, as illustrated in the appended drawings, where:

Figure 1 illustrates the block diagram of an embodiment of the invention;

Figure 2 shows an example of a collection of nested sets of destinations to which a source has sent packets, which destinations are common to N, N-1 ,... 1 time windows; and

Figure 3 is a graph illustrating the number of destinations that are common to N, N-1....1 windows versus the number of windows.

Detailed Description

[0019] The invention is directed to a system for detecting propagation of stealthy, slow probing worms.

[0020] In this specification, units through which digital data are transmitted from one point to another over a communication path are referred to generically as Protocol Data Units (PDU's). This term includes data units formatted according to various transmission protocols; PDU's can be IP packets, TCP packets, frames, etc. The term "fan-out" is used for the outgoing PDU's. As well, the system of the invention can be installed in any area of the network, with an adequate sizing for the targeted equipment (i.e. more flows implies larger amount of memory, etc.)

[0021] The system of the invention collects for each source, during a predetermined time window (TW), a representation of the set of destinations to which that source has sent packets. While a complete list of the IP addresses of the destinations can be kept for each packet, such a list would consume system resources and as such it would not be scalable. A better way to keep such a list is to use a compact hash table representing the set of destinations, as described in the above-identified parent US Patent Application SN 11/656434. The hash table can then be used for estimating the fan-out of a node (i.e. the number of distinct sources sending traffic to a node), based on periodic sampling.

[0022] Figure 1 shows the block diagram of a system 1 for worm detection by trending fan-out (WDTFO) according to an embodiment of the invention. This figure shows generically a network element (NE) 10 with a port 12; the WDTFO system 1 monitors the PDU's leaving port 12. The monitoring may be performed on selected ports or on all ports of a NE; Figure 1 shows only port 12 by way of example. In this embodiment, system 1 includes a header data processing unit 14, a hash table unit 16, a set collector unit 20, an attack identification unit 22

and a timing unit 18. The system may also include an attack containment block 24.

[0023] Header data processing unit 14 monitors the PDU's seen on the port 12 and examines the data in various fields of the PDU's header with a view to determine the PDU "type" and to identify the source node, with a view to establish which hash table unit 16 should be updated. The header data processing unit 14 also extracts the IP addresses of the far-end hosts (addresses of the destinations for packets transmitted by a respective source), or IP address- port combinations. The technique used for determining the type of PDU's on port 12 and for extracting the source and destination address data from the header is beyond the scope of this invention. It is to be understood that any method for uncovering this information may be used as long as unit 14 does not impact operation of the datapath. The data extracted by the header data processing unit is referred generically as the "address data". The source address (and packet type, etc) is used to identify the appropriate hash table 16, and the destination data is used as seen later, for determining the number of far end hosts.

[0024] To detect and protect a system against slow probing worms, a time window (TW) is selected, as shown by timing unit 18. The duration of the time window is also a design parameter, and can be selected according to the needs of the network operator. A shorter time window will allow for a quicker detection of any anomaly, but it will consume more resources and results will have less confidence. A longer time window will provide more accurate information, at a slower rate. The default for the TW parameter is expected to be in the range of a few minutes.

[0025] Hash table unit 16 is used for identifying the far-end hosts (also referred to as destination NEs) to which the respective source sends packets in each time window. While Figure 1 illustrates a hash table unit 16, system 1 may use

multiple hash table units 16. The number of units 16 is a design parameter, depending on the number of source nodes that the provider wishes to monitor, the types of the traffic to be monitored, the direction of transmission, etc. For example, port 12 may be equipped with a hash table unit 16 for each direction of traffic, and each protocol type. It is to be noted that while it is desirable to maintain distinct hash table units 16 of far-end hosts for each of the PDU categories (types) listed above, it is also possible to combine hash table units for selected protocols. There is a lot of value even in the extreme case of using only a single hash table unit for all incoming and outgoing packets.

[0026] As discussed above, each port or only some ports of interest may be equipped with the system 1 of the invention. An advantage of this invention is that it is not necessary to synchronize the polling for all ports of the network element; spreading out the polling does not impact negatively on worm detection. Depending on the platform, one easy way is to integrate the pooling of the counters with SNMP polls, which means checking the counters of a port as the SNMP packets for that port are processed. Also, realistically, there is no need for high precision in the polling interval so it can be done as a low priority task.

[0027] Obviously, the usual methods of keeping track of destination nodes would run into CPU and memory limitations. Use of the hash table unit 16 results in a much faster way of counting the destination hosts seen on port 12 than keeping address lists, saves processor cycles and savers memory space at the expense of accuracy. Hash table unit 16 comprises a plurality of buckets 17, a bucket selector 15 and a buckets count unit 19. The number of buckets 17 used by unit 16 is a design parameter and is selected based on the intended scope of worm detection at that particular node and port, precision of attack detection required, resources available at the respective node/port, cost, etc. Preferably, the buckets 17 are provided in the form of a memory array of a selected size.

[0028] The idea is to hash the address data from the fields of the header that identify the destination host, as generically shown by bucket selector 15. We refer in the following to the data that is hashed by the bucket selector 15 as "the destination address". As an example, in case of IP packets, the bits that are hashed are the IP destination address bits of the packet, or the IP destination address and port number bits.

[0029] A hash value is obtained by applying the hash function to bits in the respective header fields. The hash value is then used as an index into array 17, for setting the bucket (bit) corresponding to the respective hash value. In this way, each bucket is associated with a certain set of destination host addresses, because the hash function performed over the bits in the same header fields is the same if the bits are the same. Buckets count unit 19 determines which and how many buckets are set in array 17. This set of buckets, denoted with X, indicates how many far-end hosts received/transmitted traffic during a time interval established by the current time window. As indicated above, TW is a design parameter, depending on the protocol of the PDUs monitored, desired accuracy of the result, etc. An attack may be for example detected if the number of far-end hosts is suspiciously high.

[0030] Each bucket could be set repeatedly (once for each applicable PDU) or it could be set only once during the time window, using a very simple algorithm. If bucket selector 15 determines a hash value that identifies one of the buckets Bucket#1 to Bucket#m, let's say, a Bucket#i, and that bucket has already been seen (set), nothing happens. If, on the other hand, if Bucket#i has not been set yet, it is set. The pseudo code for bucket updating is:

Declare seen as Boolean[m]; set m buckets

Bucket = hash(IP, port); hash header data to find bucket number lf (seen[bucket]); bucket already seen, do nothing else; bucket not seen yet count = count + 1;

seen[bucket] = true; endif

[0031] In one experimental embodiment of the invention the buckets were implemented on a bit array of 256 bits (m=256) and the hash function selected reduced this number to 8 bits. Since the IP address space is 32 bits, for an 8-bit hash, there is a choice of 2 ²⁴ combinations in the same bucket. In other words, 2 ²⁴ different addresses data may set the same bucket. This means that an attacker could attempt to avoid detection by talking to hosts/ports that fall into the same bucket in order to keep the number of far-end hosts low.

[0032] Certain countermeasures may be used with a view to address this situation. For example, the hash function used by the bucket selector 15 may be designed so that addresses in the same subnet are likely to use different buckets (this is the "randomize" property that is expected from hash functions). XOR-ing the four address bytes together is another way to differentiate the sub-networks. Or, it is possible to XOR the last byte of the IP address and the lower byte of the port number; this will ensure that neither horizontal scanning (same port number, different IP address) nor vertical scanning (same IP address, different port) will end up in the same bucket. Still another solution is to add a randomizer to the hash function. Thus, a random 32 bit number may be picked at boot time, and added to the IP address before doing the XOR. This preserves the sub-net scattering property above and is difficult for the attacker to stay in the same bucket. In general, selection of the function depends on the complexity of the attack detection desired. All these methods are described and shown in further detail in the above-identified parent patent application.

[0033] A "linear counting" function is preferably used for hashing the address data, as described by K-Y Whang et al. in the paper "A Linear-Time Probabilistic Counting Algorithm for Database Applications", which presents a thorough

mathematical treatment of these counting techniques. This type of function has been selected because it is the most accurate of the whole family of probabilistic counting techniques. Whang et al. derive the best estimate of the actual linear count:

ή = —m * ln(z / m) where m is the array size, z is the number of unset entries in the array, and n is the real count.

[0034] Whang et al. also derive the error estimate for this type of function as:

where t is a load factor determined by the n/m ratio.

[0035] The paper also gives guidelines for obtaining a desired accuracy. If we apply the finding of this paper to the system of the invention, it is noted that the size of array 17 may be reduced significantly from the 256 bits discussed above, without a significant impact on the accuracy of malware detection. A smaller array is desirable in order to make the implementation easier in software. For the system of the invention, if array 17 has four bytes (rather than a 256), the resulting accuracy is 17%. For a two byte array, the accuracy drops to 35%. This means even a very little memory space dedicated to the array still enables comprehensive results.

[0036] As indicated above, the hash table unit 16 does not distinguish between destinations that hash to the same bucket, so the statistics are not exact. While this is currently be the preferred implementation for counting the far-end hosts, any other scheme that provides such a set of destinations can be used as unit

16, thus allowing for tuning of accuracy vs. resource requirements, engineering costs, etc.

[0037] To reiterate, the number X provides the number of destination NEs to which a certain source NE has sent PDUs during the current time window, as determined by the number of buckets that have been set during that time window. The set collector 20 identifies the number of destination addresses that are common over successive sets of destination addresses, from the sets of destination addresses collected including the current set of destinations, X. This number is denoted with X _k . In other words, X _k includes the number of destination NEs common to k sets collected over k successive time windows. Once N sets of destinations (for N successive time windows) have been obtained, the set collector determines the number of destinations that are common to all N, N-1, N- 2, ..., 2, 7 of these windows. The result is a collection of nested sets, with each destination address "seen" being in the ring labeling how many windows the destination address was seen in, as in Figure 2. The term "seen" refers in this specification to the PDUs that are transmitted from port 12 to far-end hosts (outgoing PDU's).

[0038] As seen in Figure 1 , the attack identification block 22 includes a memory 21 for storing a benchmark data set A _k , shown at 5 which is prepared for the respective source based on statistical data collected over time. The graph of data set A _k plots the sets A _k versus the respective number of time windows /c; Figure 3 shows the graph with the number of destinations for a particular source for /c=7,2, ..., N time windows. Generally, A _k should exhibit a stable behavior for each source. This enables modeling the sources by set collector unit 20 using a specific, appropriate distributional form, with a view to minimize the amount of storage required for each source. For example, a source may be modeled using a power law graph, etc.

[0039] Attack identification block 22 further includes a comparator 23 that compares the pooled set of destination Xk collected by the set collector against the corresponding value A _k in the data set. Values of Xk that are significantly different from the modeled graph are declared to be suspicious by an alarm block 25. The term "significantly different" is a relative term with respect to the expected value Ak in the data set, and is defined relatively to the respective benchmark plot. For example, a significantly different value may be considered an Xk more than three standard deviations away from the mean value provided by plot 5 of the data set. Preferably, the anomalous values are also defined taking into account the time of day effects. Further analysis of such anomalous values may be performed by the attack identification block 22. Ideally, attack identification unit 23 should check plot 5 each time a counter is changed. While this mode of operation gives the fastest response time, it requires processing power in the data-path. Preferably, the checks are performed at each time window TW.

[0040] Once the type of attack has been identified, attack containment block 24 triggers a certain defensive action, based on rules provided in a rules set (not shown).