Over the past few weeks, we have researched Internet security--the more recent threats, as well as countermeasures against the attacks made. The problems we looked at ranged from Botnets to DDoS to DNS attacks to Spam attacks. The solutions included anomaly detection using a variety of approaches, reputation systems, blacklisting and cheating detection.
One of the thoughts I've had is that network security is not so much a problem of bad system design as much as it is a perpetual game between the "bad guy" and security research. Either party is rewarded by staying one step ahead of the other. The "bad guy" always has plenty of incentive to come up with a new security threat, and that gives security a good reason to come up with a countermeasure against the threat. In a sense, the good and bad guys are creating a competitive market for each other.
Also, I was previously unfamiliar with how Botnets worked. It was pretty impressive (albeit quite insidious) that a system can be designed to take command of tens of thousands of computers and use them to perform an arbitrary task. Robust distributed systems are hard to design. (Well, who knows if Botnets are designed robustly?)
We discussed several reputation systems. Collusion seems to be a persistent problem in reputation system design. It is a hard problem because colluding peers can game the system by taking advantage of good peers and rating other colluding peers well, thus damaging the accuracy of the rating system. I have read papers on reputation systems, but none of them has applied the study of evolutionary dynamics and evolutionary stable strategies to them. I read an excellent book this semester that sheds light on design of a robust social structure. It discusses the conditions that allow or prohibit invasion into a society of agents. Translating collusion into the language of the book, if a reputation system can be designed where peers have an evolutionarily stable strategy, the peers will be able to resist invasion by a colluding group of attackers.
Wednesday, December 15, 2010
Kalman: Another Anomaly Detection System
My previous post dealt with ASTUTE, a traffic anomaly detection system that uses the queue volume equilibrium property to detect anomalies of a distributed nature. This post deals with a different anomaly detection system known as KALMAN. The developers of this approach presented their system in the 2005 IMC. It makes use of the Kalman filter to extract normal traffic traces from a network, leaving the rest (known as the residual) for anomaly analysis.
The Kalman filter is a technique that allows for predicting future values based on past measurements that may be mingled with noise, or random variations in measurement. This filter is useful for other things, such as predicting the position of a target, given previous measurements that may be slightly inaccurate.
In the anomaly detection system KALMAN, the Kalman filter compares predictions of traffic state with the actual traffic state (with the more recent measurement data). Then, ROC curves are used to decide the accuracy of the prediction. In short, there is a traffic matrix (showing traffic at each intermediate node) and a path matrix from which origin-destination flows can be constructed. The system identifies the individual flows that are anomalous so that they can be analyzed for what type of anomaly it has.
The Kalman filter is a technique that allows for predicting future values based on past measurements that may be mingled with noise, or random variations in measurement. This filter is useful for other things, such as predicting the position of a target, given previous measurements that may be slightly inaccurate.
In the anomaly detection system KALMAN, the Kalman filter compares predictions of traffic state with the actual traffic state (with the more recent measurement data). Then, ROC curves are used to decide the accuracy of the prediction. In short, there is a traffic matrix (showing traffic at each intermediate node) and a path matrix from which origin-destination flows can be constructed. The system identifies the individual flows that are anomalous so that they can be analyzed for what type of anomaly it has.
A "Wise" Way to Detect Traffic Anomalies
Since the early days of the Internet, its security has been something of growing importance. As it is managed on many different levels (user, ISP, content provider, telephony, etc.), there have been different approaches to minimize threats. For example, users and content providers are primarily concerned with keeping their computers free of malware, to avoid compromise of personal information or resources.
ISPs take a different stance. They are concerned with keeping their clients as a whole free of malware, and free from becoming part of (or the target of) attacks, such as DDoS and spam. That is what traffic anomaly detection is concerned with. Anomaly detection is a challenging task, as there are a variety of anomalies that can occur within an ISP. Consequently there are a variety of systems that have been developed to pinpoint anomalies.
ASTUTE is a fairly recent system. Its detection is based on the assumption that, when router queues are not saturated, the total volume aggregated from different flows does not change much over time. Anomalies are thus detected based on deviations from this equilibrium. ASTUTE does well at finding when groups of flows simultaneously cause an increase of traffic, even when this increase is small. This would make it possible to classify traffic from Botnets. However, it does not do well at classifying large volume increases by one or a few flows. There are other detection methods, such as Wavelet or Kalman, that can do this. In practice, ASTUTE would work well in concert with one of these other detection methods, as each has its own benefits.
ISPs take a different stance. They are concerned with keeping their clients as a whole free of malware, and free from becoming part of (or the target of) attacks, such as DDoS and spam. That is what traffic anomaly detection is concerned with. Anomaly detection is a challenging task, as there are a variety of anomalies that can occur within an ISP. Consequently there are a variety of systems that have been developed to pinpoint anomalies.
ASTUTE is a fairly recent system. Its detection is based on the assumption that, when router queues are not saturated, the total volume aggregated from different flows does not change much over time. Anomalies are thus detected based on deviations from this equilibrium. ASTUTE does well at finding when groups of flows simultaneously cause an increase of traffic, even when this increase is small. This would make it possible to classify traffic from Botnets. However, it does not do well at classifying large volume increases by one or a few flows. There are other detection methods, such as Wavelet or Kalman, that can do this. In practice, ASTUTE would work well in concert with one of these other detection methods, as each has its own benefits.
Looking at Wireless Simulations in OMNeT++
We were curious to know how well OMNeT++ (v4) simulates a wireless setting. There are several out there, such as ns-2, and Opnet. We have done experiments with ns-2 in a wireless setting, but thought it performed significantly below our expectation. Perhaps it is because we hold wireless simulation to a high standard.
The benchmark we use is a 2007 IMC performance study done by Dracos Nicolescu, titled "Interference map for 802.11 networks". A major point in his study is that there are three different ranges in an 802.11 network. Communication range defines the range in which two hosts can communicate with adequate SNR in absence of other wireless communications. Carrier sensing range is the distance at which two hosts can sense whether the other is transmitting, but they don't have the ability to send or receive data from the other. Beyond carrier sensing range is the interfering range, at which one host will transmit while the other is transmitting, yet its signal will be corrupted by the signal of the other.
So, we set out to experiment to see whether simulated 802.11 hosts in fact model those three ranges, and if so, find out at which distances the ranges correspond to. We used two different OMNeT++ packages: the most common networking one (INET), and Mixnet. Mixnet combines the upper stack of INET with a more sophisticated network interface card, which is derived from MiXiM.
Our methodology and results are included in our report. The conclusions are two-fold: First, OMNeT++ wireless simulation provides many of the aspects of the 802.11 host, but isn't entirely faithful to the results of Nicolescu's study. Second, these simulation packages are relatively young; we found adequate need for debugging, development and documentation in both.
The benchmark we use is a 2007 IMC performance study done by Dracos Nicolescu, titled "Interference map for 802.11 networks". A major point in his study is that there are three different ranges in an 802.11 network. Communication range defines the range in which two hosts can communicate with adequate SNR in absence of other wireless communications. Carrier sensing range is the distance at which two hosts can sense whether the other is transmitting, but they don't have the ability to send or receive data from the other. Beyond carrier sensing range is the interfering range, at which one host will transmit while the other is transmitting, yet its signal will be corrupted by the signal of the other.
So, we set out to experiment to see whether simulated 802.11 hosts in fact model those three ranges, and if so, find out at which distances the ranges correspond to. We used two different OMNeT++ packages: the most common networking one (INET), and Mixnet. Mixnet combines the upper stack of INET with a more sophisticated network interface card, which is derived from MiXiM.
Our methodology and results are included in our report. The conclusions are two-fold: First, OMNeT++ wireless simulation provides many of the aspects of the 802.11 host, but isn't entirely faithful to the results of Nicolescu's study. Second, these simulation packages are relatively young; we found adequate need for debugging, development and documentation in both.
Tuesday, November 30, 2010
The Botnet Battle
It wasn't until I did some research on Botnets that I realized what a powerful thing a distributed army of bots can be. Botnets typically consist of thousands of hosts, which are PCs and servers that have been compromised by malware. Each host in a Botnet takes orders from a Command & Control server, where inter-bot communication is encrypted IRC. Further, the malware may accomplish other evil designs, e.g., intercept keystrokes, infect other computers, etc.
Why do Botnets exist? The way I understand it, they are a source of power in the "dark computing underworld." Suppose Joe is administrator of a Botnet with 10,000 computers, and somebody wants an evil deed done (a DDoS attack, stealing credit card numbers, etc.) Then they would pay Joe to use his Botnet to accomplish the deed.
These complex systems pose a significant concern to network security, where Botnets are often hard to identify, and even harder to stop. Botnets often accomplish their purposes through sending spam, where email links point to malware or websites to DoS attack. Addressing the Botnet spam problem, Microsoft Research published a paper discussing how to recognize spam from Botnets. Their publication provides a measurement study which captures important characteristics of a Botnet. It also gives an architecture that discovers these characteristics in spam.
The way I see it, there is a perpetual battle between Botnets and email systems, and any defensive measures on the part of email systems will be opposed by additional offensive measures from the Botnet. In my opinion, the best way to approach the Botnet battle is to expose as much measurement information about Botnets as possible, and hide information about email systems.
Why do Botnets exist? The way I understand it, they are a source of power in the "dark computing underworld." Suppose Joe is administrator of a Botnet with 10,000 computers, and somebody wants an evil deed done (a DDoS attack, stealing credit card numbers, etc.) Then they would pay Joe to use his Botnet to accomplish the deed.
These complex systems pose a significant concern to network security, where Botnets are often hard to identify, and even harder to stop. Botnets often accomplish their purposes through sending spam, where email links point to malware or websites to DoS attack. Addressing the Botnet spam problem, Microsoft Research published a paper discussing how to recognize spam from Botnets. Their publication provides a measurement study which captures important characteristics of a Botnet. It also gives an architecture that discovers these characteristics in spam.
The way I see it, there is a perpetual battle between Botnets and email systems, and any defensive measures on the part of email systems will be opposed by additional offensive measures from the Botnet. In my opinion, the best way to approach the Botnet battle is to expose as much measurement information about Botnets as possible, and hide information about email systems.
Wireless Mesh Networking Summary
As our class has concluded the section on Wireless Mesh Networks, I will summarize what has been discussed and point out a potential area for research. WMNs has attracted significant attention to research groups, because of 1) the challenging nature of networking using a wireless medium for communication and 2) the advantages offered by ad-hoc networks.
Wireless networking poses only a few significant problems, but these problems adversely affect each layer of the network, and many solutions have been suggested at each layer. First, the fact that nodes must share the medium for communication requires that those communicating take turns in order for traffic to flow. Second, because of the hidden node problem, there is inevitably going to be loss due to interference from those outside carrier sensing range. Third, nodes withhold transmission because of the exposed node problem.
At the link layer, we have discussed techniques such as Lagrangian relaxation to allow nodes to have a fair share of bandwidth within their clique of nodes with which they share the medium. We have looked at how network coding can be used to make up for lost packets, such that the receiver is indifferent to which packets it didn't receive. We have also looked at making use of corrupted (partially correct) packets in some cases.
At higher layers, we have discussed how opportunistic routing can be used as a more reliable source of packet transmission, as routes are often broken with traditional routing on a WMN. At the transport layer, adaptive pacing can be used to allow a sender to be silent while its neighbors relay the message.
In short, the nature of wireless networking requires design adaptations from traditional (wired) networking. Many of the aforementioned techniques address the problems caused by 802.11 MAC unfairness and interference due to the hidden node problem. I'm curious to know whether any work has been done to measure the severity of the loss (lack of potential transmission) due to the exposed node problem. And if this loss is significant, I wonder what could be done to remedy it.
Wireless networking poses only a few significant problems, but these problems adversely affect each layer of the network, and many solutions have been suggested at each layer. First, the fact that nodes must share the medium for communication requires that those communicating take turns in order for traffic to flow. Second, because of the hidden node problem, there is inevitably going to be loss due to interference from those outside carrier sensing range. Third, nodes withhold transmission because of the exposed node problem.
At the link layer, we have discussed techniques such as Lagrangian relaxation to allow nodes to have a fair share of bandwidth within their clique of nodes with which they share the medium. We have looked at how network coding can be used to make up for lost packets, such that the receiver is indifferent to which packets it didn't receive. We have also looked at making use of corrupted (partially correct) packets in some cases.
At higher layers, we have discussed how opportunistic routing can be used as a more reliable source of packet transmission, as routes are often broken with traditional routing on a WMN. At the transport layer, adaptive pacing can be used to allow a sender to be silent while its neighbors relay the message.
In short, the nature of wireless networking requires design adaptations from traditional (wired) networking. Many of the aforementioned techniques address the problems caused by 802.11 MAC unfairness and interference due to the hidden node problem. I'm curious to know whether any work has been done to measure the severity of the loss (lack of potential transmission) due to the exposed node problem. And if this loss is significant, I wonder what could be done to remedy it.
Friday, November 19, 2010
EEC: A Brilliant Approach
In a recent SIGCOMM publication on improving wireless communication, someone had a brilliant idea. Usually, when a packet is received by a wireless device, the packet is checked for errors. If the packet has errors that can't be recovered, it is discarded. The whole packet. The paper gives the following graph showing the fraction of bits that are typically corrupted in a wireless mesh network setting:
This shows that 50% of packets have some corruption within 0 to 2%. They claim that corrupted packets have some value, if the fraction of corrupted packets can be estimated. For example, error-tolerant applications, like video streaming could leverage corrupted packets to increase throughput if the error rate is below a threshold. Other applications could measure the error rate to determine setting selection (such as route selection or WiFi rate adaptation).
As a result, they propose a concept known as error estimation codes (EEC). The idea is to introduce a small amount of extra data to a packet used for error estimation. This is similar to error correction codes, which also introduce redundancy, but use the redundancy for error correction. The problem with error correction is that it requires a lot more redundancy to correct a "more corrupted" packet. EEC's additional redundancy guarantees estimation precision, and is the same regardless of the error rate.
This shows that 50% of packets have some corruption within 0 to 2%. They claim that corrupted packets have some value, if the fraction of corrupted packets can be estimated. For example, error-tolerant applications, like video streaming could leverage corrupted packets to increase throughput if the error rate is below a threshold. Other applications could measure the error rate to determine setting selection (such as route selection or WiFi rate adaptation).
As a result, they propose a concept known as error estimation codes (EEC). The idea is to introduce a small amount of extra data to a packet used for error estimation. This is similar to error correction codes, which also introduce redundancy, but use the redundancy for error correction. The problem with error correction is that it requires a lot more redundancy to correct a "more corrupted" packet. EEC's additional redundancy guarantees estimation precision, and is the same regardless of the error rate.
Subscribe to:
Posts (Atom)