IM security: virus throttling in scale-free networks


Scientists have been studying the spread of biological disease for over a hundred years. The aim is to predict and thus avoid damaging epidemics, thus the name “epidemiology.” In recent years, some researchers have started applying the tools of epidemiology to help understand another form of common disease: computer viruses and worms.

One thing that sets computer 'diseases' apart from their biological counterparts is that worms and viruses mostly spread on networks. When epidemiologists talk about networks, they don't mean Ethernet or TCP/IP, they mean the network of 'contacts' that each machine has. For computers this contact network depends on how the worm finds the addresses of machines to infect. For example, an email worm spreads using email addresses found on the infected machine. How those addresses link to other machines, and so on, creates the contact network for the worm.

As you can probably imagine, the 'shape' of the network determines how fast and far a virus will spread. Generally speaking, a virus will spread more quickly over a network that is densely connected than one that is very sparse.

However, there is a class of network where the average connectivity is very sparse, but viruses can find it easy to spread. These networks, called 'scale-free' networks, are ones where the vast majority of the nodes have low-to-medium connectivity (small numbers of links in or out), but there is a significant proportion which are very highly connected. These highly connected nodes act as hubs, making the average distance between any two nodes small.

Scale-free networks are actually pretty common – they are found in a variety of social networks (some people have lots of friends, most of us have a few), sexual contacts (some people ...), and also in technological networks: the internet routing backbone, the hyperlinks on the World Wide Web, etc. The upside of this type of network is that information can travel very quickly, and the downside is that disease can too!

In fact, there are theoretical results to show that in a mathematical sense, scale-free networks are the easiest to spread on. On the other hand, there are also results that suggest that these networks might be relatively easy to defend. If you can find the highly connected nodes and protect them, you can have a large effect on the virus transmission: the virus uses these nodes to spread effectively, so if you remove them, you are left with a sparse topology which is more difficult to spread on.

There has been a lot of hype and excitement about scale-free networks, but it is important to bear in mind that they do not apply well to important classes of computer network. For example, the IP address space used by worms, such as Blaster, is pretty much fully connected, and does not have a scale-free property.

One area where scale-free topologies do seem to be common is in the Instant Messaging (IM) world. IM is a technology that is rapidly growing in adoption in enterprises, and is already very common in the consumer world. A typical IM client allows users to chat in real time, but often supports other features such as video conferencing. From a security point of view, IM is troublesome because the clients are likely to have bugs (or features) that can be exploited by malicious code, and also because IM can relatively easily traverse firewalls, exposing the inside of an enterprise to attack. While IM worms are still rare, there have been examples spreading in the wild, e.g Choke, Hello, Jitux.A, and Bizex.

The topology over which an IM worm would spread is created from the 'buddy lists' that IM clients use to store a user's contacts. Various researchers have studied this topology and found that it is indeed scale-free. This means that an IM worm could be very damaging – spread far and wide, at high speed. And current technologies to deal with worms (patching and signature-based anti-virus) are not at their best when targeting such high speed attacks.

There are some ideas that are currently in research labs that do address this problem. One idea is to contain or throttle the virus outbreak, by looking at the difference between a normal user's use of IM and a worm using IM to spread.

It turns out that users tend to chat with a small and slowly varying subset of the contacts on their buddy list, and that the size of this subset is pretty much independent of the size of the buddy list. This makes sense: you IM with some people frequently, some only occasionally, but you rarely (if ever) act as a worm would, sending a message to every contact on your buddy list in a short period of time.

Throttling takes advantages of this, by keeping track of whom each user has IM'd with recently, and blocking messages when a user attempts to chat with more than a few 'new' contacts not in their subset, over some period of time. Sample parameter settings would be a subset size of five, and the time period one day, thus allowing users to chat with two users not in their subset over the period of a day. The exact parameters are chosen so that for the vast majority of users this would have little impact; for the few that are blocked, their parameter settings can be updated.

Then if a worm tries to spread, it will not know the contents of the subset for the infected user and it will likely choose new recipients, and trigger the throttle. The overall result is that the virus will not spread as far and the number of viral messages processed by the IM server will be reduced, hence reducing the overall impact of the attack.

This countermeasure even has a neat topological explanation – it restricts the connectivity of nodes in time (only allowing the slowly varying subset), as opposed to the spatial connectivity of the buddy lists. In fact, the larger the buddy list, the more likely it is that the worm will trigger the throttle. By limiting all the users, the throttle automatically reduces the effective connectivity of the highly connected nodes, making the overall topology sparse and more difficult for the worm to spread.

In summary, the topology over which a worm propagates can make a great deal of difference as to how far and fast it spreads. However, restricting propagation by using throttling mechanisms will work independent of the topology, and while it cannot stop the virus, it can slow and contain it until slower, more definite mechanisms such as virus signatures can be deployed.

Dr. Matthew Williamson is Senior Research Scientist at Sana Security

Get daily email updates

SC Media's daily must-read of the most current and pressing daily news

By clicking the Subscribe button below, you agree to SC Media Terms and Conditions and Privacy Policy.