Tuesday, November 24, 2009

Not-a-Bot: Improving Service Availability in the Face of Botnet Attacks

R. Gummadi, H. Balakrishnan, P. Maniatis, S. Ratnasamy, "Not-a-Bot: Improving Service Availability in the Face of Botnet Attacks," NSDI'09, (April 2009).
This paper talks about identifying the traffic that is sent from compromised machines that form botnets. It aims at separating human generated  traffic from that generated by botnets by observing a fact that human generated traffic is generally accompanied by keyboard or mouse inputs. The authors designed a system called NAB ("Not-A-Bot") to approximately identify human generated activity. It uses a trusted software component called 'attester' which runs on the client machine with an untrusted OS. The authors implemented their version of the attester in the Xen hypervisor but claimed that other implementations such as building the attester in the trusted hardware or running it in software without virtualization is also possible. (The last option actually looks very promising and I wonder as to why it was not done).


Design

The authors used TPM and built the attester on top of it. A TPM provides many security services, among which the ability to measure and attest to the integrity of trusted software running on the computer boot time. The attester relies on two key primitives provided by TPMs called the direct anonymous attester (DAA) and the sealed storage. The basis of the design is that whenever an application send a message, it has to obtain an attestation from the attester. The attestation has the hash of the message, a nonce and range values signed by the attester's public key as well as its certificate. The attestation is given if the request is generated within some range (delta-m and delta-k) of the keyboard and mouse activity (with certain exceptions such as scripted mails which uses PID). On the other end, there is a verifier, which can now implement various policies based on the attestation. It can all together drop non attested packet, but practically, the authors talk about giving low priority to non-attested packets or rather making sure that the attested packets always pass through. Based on this, the paper contained implementation of effective spam solutions, DDoS prevention and click-fraud mitigation.

Comments

Overall, this was an excellent paper. It tackled a very practical problem and came up with a partially practical solution too. However, I have certain comments on the effectiveness of the protocol:

  1. It can very well be possible to have adaptive botnets that can adapt to sending data whenever there is a mouse or key stroke. This can in the worst case result in sending botnet data in bursts and may result in throttling the sender.
  2. Current design an implementations involve modifying applications and protocols (to accommodate attester data). This raises concerns about its deployability.
  3. Although, the authors mention that they donot intend to 'punish' those applications who donot use attesters, I somehow felt that giving priority to attested traffic is against this very goal.
  4. The evaluations showed that 0.08% of human generated mail was still misclassified as spam. Shouldn't it be ideally zero now? Given that they already tackled script generated mails, what could be the cause of these emails? 
  5. It was a bit of a surprise for  me when the authors mentioned that 600 GB of disk overhead for storing nonces is not much for an ISP. Is that scalable?

Thursday, November 12, 2009

X-Trace: A Pervasive Network Tracing Framework

R. Fonseca, G. Porter, R. H. Katz, S. Shenker, I. Stoica, "X-Trace: A Pervasive Network Tracing Framework," NSDI'07, (April 2007).
This paper presents X-Trace, a pervasive Network Tracing Framework. The idea is that different applications spanning multiple administrative domains working over different contexts make it extremely difficult to have a comprehensive view of the system. Though various diagnosis tools do exist but mostly they are either layer specific or application specific. X-Trace aims to be pervasive and generic in its approach (at the cost of requiring agreements from ADs to support it).

The idea is that the user invokes X-Trace when initiating an application task by inserting X-Trace metadata in the resulting request consisting of flags (specifying which component of metadata is placed in it), a unique TaskID, TreeInfo field (consisting of ParentID, OpID and EdgeType tuple), Destination Info (optional field to indicate the N/W adress to send reports to) and an Options field to accomodate future extensions. This metadata propagates through the network using pushDown() and pushNext() calls. pushDown() pushes metadata down the logical layer while pushNext() pushes metadata at the same level on the next components. Each node is responsible to store its X-Trace metadata which is then sent back to the report server and aids in the construction of a trace tree. This tree will help the report server to see the entire trace of how packets traveled into the network and based on incomplete/broken traces, can help the administrator to judge possible network problems.

Further the authors talked about additional uses of X-trace in tunneling, ISP connectivity troubleshooting and link layer tracing mechanisms. They evaluated the system by deploying 3 scenarios: DNS resolution, a three-tiered photo-hosting website and a service accessed through i3 overlay network.

Comments
Another well written paper. Talks about a very real problem and proposes a very generic solution. However a few questions arise over the effectiveness and ease of deployment of the protocol:
  1. Requires modifications in clients, servers and network devices to support X-Trace metadata. This limits its quick deployment.
  2. Though the authors claim that partial deployment of X-Trace can help in finding faults at some granularity, it remains an open question as to how useful will be these partial graphs.
  3. Loss of reports back to the reporting servers may be assumed as failures. 
  4. Though I donot understand this quite well, but the authors admitted that tree structure doesn't capture all possible network actions. They talked about quorum protocols or a controller that sends jobs to many working nodes and waits for all to complete.
Overall, I guess it would also be interesting to discuss how X-Trace can be extended on the lines of NetMedic to automatically detect network failures or misconfiguration errors too. 

Tuesday, November 10, 2009

NetFPGA: A Tool for Network Research and Education

G. Watson, N. McKeown, and M. Casado. NetFPGA: A Tool for Network Research and Education. In 2nd workshop on Architectural Research using FPGA Platforms (WARFP), 2006.
This paper talks about NetFPGA, a platform developed at Stanford which helps users to build real networking hardware using design tools such as Verilog that can be deployed and debugged in an operational network. FPGAs or Field-Programmable Gate Arrays are designed to be configured by the users after they are manufactured using standard hardware definition languages. It consists of various logic blocks that can be programmed to be wired together to perform complex functions. NetFPGA project leverages this technology to design Network specific FPGAs that can be used to build an Ethernet Switch or an Internet router (and probably other middleboxes too?). The NetFPGA project has released 2 versions at the time the paper was written:

NetFPGA-v1
This consisted of:
  • 3 Altera EP20K400 APEX devices
  • An 8 port Ethernet controller
  • 3 1MB SRAMs
  • Ancillary Logic
- Synthesis and Design tool: Synopsys
- Place and route tool: Altera Quartus

Further, a locally developed tool, Virtual Network System was used to map the NETFPGA-v1 ports onto the campus internet. The policy used was that of simulating first and debugging last. Due to the absence of a CPU on chip, the vendor's analysis tool couldn't be used which led the authors to develop there own simple logic analyzer. However, version 1 had various limitations. The PCB board format required an obscure rack that was difficult to obtain and required self-assembly, the rate was limited to 10Mb/s, there was no on-board CPU and finally the development environment was only limited to Linux and Solaris. These shortcomings led the authors to work on version 2 NetFPGA.


NetFPGA-v2
The main changes in v2 were:
  1. PCI Format was incorporated.This provided a familiar format to most users and also provided greater bandwidth benefits.
  2. Further tools were provided to enable development in Linux, Solaris and Windows XP
- Synthesis and Design tool: Synopsys VCS (under Linux), Mentor's ModelSim (Linux and XP)
- Place and route tool: Xilinx ISE tool (Linux or XP)

Using a CPU within the Virtex devices are still being explored. Further the authors have developed 18 NetFPGA-v2 boards and also have a bus-master DMA driver for 4-port Ethernet port. At the time of writing this paper, The authors were also in the process of implementing RCP (Rate Control Procedure) using NetFPGA-v2.

Comments

NetFPGA is definitely a great technology. It will definitely help researchers to actually implement a system and test how does it work in a real environment taking into account the hardware issues which the software routers are unable to simulate. I have a few questions in mind though and it would be great to discuss them in class:
  1. As I see it, there are 3 class of network components, Software routers, FPGAs and ASICs. NetFPGAs are definitely better than software routers. It would be interesting to discuss how close are they to application specific ICs (ASICs).
  2. Aren't software routers sufficient to test the 'correctness' of a protocol? If that is the case, why are NetFPGAs an exciting tool for researchers as well?

A Policy-aware Switching Layer for Data Centers

D. Joseph, A. Tavakoli, I. Stoica, "A Policy-aware Switching Layer for Data Centers," ACM SIGCOMM Conference, (August 2008).
To protect, manage and improve performance of datacenter applications, data centers deploy a large variety of middleboxes including firewalls, load balancers, SSL offloaders, web caches and intrusion prevention boxes. However, as of now, the procedure of deploying various middleboxes involves manually placing them in the physical path and then tweaking traffic by overloading layer 2 mechanisms  to explicitly pass through them. This paper on the other hand proposes a policy aware switching layer based approach which allows switches to specify various policies for the packets passes through them to traverse certain 'out of the way' middleboxes. This system is designed keeping the following 3 points in mind:
  1. Correctness: Traffic should maintain proper sequence of order in traversing the middleboxes.
  2. Flexibility: The sequence should be easily reconfigurable.
  3. Efficiency: Traffic should not traverse unnecessary middleboxes.
Keeping these goals in mind, the authors propose PLayer  which was built around 2 principles:
  • Separating policy from reachability: This is done by incorporating policies in switches comprising of tuples. This policies match the packet's MAC addresses and route it to a  particular middlebox. Further these policies are sent as updates to individual switches by a single policy manager and care must be taken to ensure that 2 adjacent PLayer switches have the same policy version running on it to avoid loops/ bypassing critical middleboxes.
  • Takings middleboxes off the physical network path: The middleboxes are no longer in the physical path and are connected via various interfaces to the Pswitch. There is no need of modifying middleboxes by introducing SRCMACREWRITER in between the middlebox and the regular Ethernet switch.
Comments

I found this paper extremely well written and relevant. It tackles a real problem in a pretty generalized manner. However there are some rough edges which need to tackled out:
  1. 15-byte frame encapsulation overhead may increase frame size beyond 1500 byte MTU.
  2. MAC address and VLAN spoofing attacks can render the protocol ineffective.
  3. Stateful PSwitches may not always be good for scalability.

Internet Indirection Infrastructure

I. Stoica, D. Adkins, S. Zhuang, S. Shenker, S. Surana, "Internet Indirection Infrastructure," ACM SIGCOMM Conference, (August 2002).
 This paper attempts to generalize the Internet's point to point communication system. Traditionally, Internet has always been based on a push model, wherein the sender pushes the packet to the given receiver by explicitly addressing the packet to it. i3 on the other hand, proposes what we can think of as a push-pull model where the sender pushes a packet in the network and it is the responsibility of the receiver to pull it towards it.

Broadly, the idea is that each packet is associated with an identifier which is used by the receiver to obtain delivery of the packet. The sender sends the packets as (id, data) where id is an m-bit identifier and data is the payload. This packet is directed to one of the many i3 servers. The receiver on the other hand, use triggers of the form (id, addr) to indicate their interest in a packet. It is the job of the i3 servers which form a part of the overlay network to match the identifiers and forward the packet to the given addr. The authors also proposed a second generalization of i3 which consisted of sender sending (id_stack, data) and the trigger comprising of (id, id_stack) and the intermediate i3 servers implemented in a chord structure wherein the packets get hashed according to the prefix function of the first k bits of their m-bit identifiers.

Based on this, the authors showed that a variety of services can be implemented efficiently. Primarily applications that involve mobile receivers can now be implemented with ease as the receivers can update the i3 servers on the fly whenever they move to new locations by creating new triggers. Further multicast and anycast can be implemented similarly without the sender being concerned about the individual addresses of receivers. The authors also showed that strong applications such as service composition can be implemented with the help of indirection servers in the middle without the knowledge of the sender, which I feel was the main strength of the paper.

Comments

Overall, the paper builds on a definitely great idea! The whole push-pull model was nicely explained and make total intuitive sense. However, some issues that come to mind are:
  1. I3 like all other overlay networks suffers from latency stretch. That is, every packet is routed to i3 servers instead being directly sent to the receivers. Though the authors have proposed a number of steps that could really localize the nearby i3 server where the packet is stored, it would always suffer from higher latencies as compared to sending directly to the receiver.
  2. I felt that the challenge based protocol to prevent DDoS attacks which consisted of sending a nonce that is expected to be returned by the receiver was too simplistic and can easily be broken.
  3. The authors donot really talk much about the time they should store the packet on each server, the trigger validity period etc. These values are crucial if i3 aims to be deployed on a large scale.

Thursday, November 5, 2009

DNS Performance and the Effectiveness of Caching

J. Jung, E. Sit, H. Balakrishnan, "DNS Performance and the Effectiveness of Caching," IEEE/ACM Transactions on Networking, V. 10, N. 5, (October 2002).
This paper presented a detailed analysis of traces of DNS and its associated traffic at 2 locations -- MIT LCS and KAIST. This analysis resulted in insights into how various clients interact with the DNS, effects of caching and the performance perceived by the clients. It was widely believed that 2 factors contributed to scalability of DNS:
  • Hierarchical Design around administratively delegated namespaces.
  • Aggressive use of caching.
Caching was effective only when the TTLs were high as otherwise the cache will return stale values. However, low TTLs is not a very desirable thing to have in say for example mobile servers. This led the authors to delve deeper into estimating the effectiveness of DNS caching by observing the amound of DNS traffic in the wide area traffic. The following were some of the interesting things that were uncovered during these experiments:

  1.  Low TTLs on A records (IP-hostname) mappings doesn't really affect performance due to the fact that network bandwidth is not really affected by it in practice. Further, caching at NS-record level results in substantial increase in DNS performance.
  2. The major cause of latency observed by the client is due to recursive referrals. For lookups involving 2 or more referrals, more than 95% took more than 100ms and 50% take more than 1 second to resolve.
  3. Almost half of the lookups were not associated with a TCP connection as was assumed initially.

Development of the Domain Name System

P. Mockapetris, K. Dunlap, "Development of the Domain Name System," ACM SIGCOMM Conference, 1988.
This paper examined the ideas and issues behind the initial design of DNS (Domain Name System) in 1983 exploring it in terms of the improvement it brought over existing systems, its successes and shortcomings and other performance characteristics.

Broadly speaking, the job of a DNS server is to provide a mapping between an IP and a hostname. Queries are mainly made over a hostname to determine its corresponding IP address, however the reverse is also pretty much possible. Prior to the design of DNS, there were mainly 2 popular existing designs that the authors discussed:
  • HOSTS.TXT file: This was a single file maintained by SRI-NIC consisting of all hostname-IP mappings. This simple soultion worked quite well when the number of nodes were limited but gradually had obvious scalability issues.
  • XEROX Grapevine:  This was pretty sophisticated and had a heavy use of replication, light use of caching and fixed number of hierarchy levels. Fixed number of hierarchy levels meant that it was suited for particular protocol architectures and importing its design would have meant importing elements of its protocol architecture. This limitations led to the development of a new design.
DNS Architecture

The architecture had to deal with many tradeoffs before coming up with a design. Ideally, such a system should have been a system that behaves like a perfect 'dynamic database' and incorporates related atomicity, voting and backup etc, however, it was believed that these things would make it a bit too complex to be adopted readily. The active components of the system are of 2 major types -- name servers and resolvers.  Name servers contained repositories of information while resolvers interfaced the client programs and contains algorithms to find the name servers. Further, DNS internal name space is a variable-depth tree where each node in the tree had an associated label. These subnodes of the tree can be managed by different organizations and are free to assign labels accordingly. For instance berkeley.edu is a subtree of the .edu node and is free to manage its own subtrees (which can be further managed by different administrative units eg. cs.berkeley.edu, me.berkeley.edu etc.). Third important concept was that the data for each name in the DNS was organized as a set of resource records (RRs) which were < type, class > tuples. Types represent abstract resources (eg. host address, mailbox etc.)  while the class represents the protocol family.

Further, the authors talk a bit about the importance of caching in DNS and its dependence on TTL. Lower value of TTL tend to make caching ineffective. One important observation was that even though root servers take less than 100ms to process vast majority of requests, the clients see a typical response time of 500ms to 5s. This may well be possible due to recursive nature of zone checking and other network latency issues.

Comments

It was nice to read this paper to get a historical perspective on the design decisions that led to the development of DNS. However, in present context, few questions come into mind:
  1. Given that essentially DNS is all about finding   mapping, how about designing it in terms of the DHTs?. Such a system would help in solving the ever increasing scalability issues. Specially, as the world is moving towards URIs (Universal Resource identifiers) and the namespace size is going to increase exponentially, it makes total sense to have such a system in place.
  2. Nothing much was done about security of DNS at that time. It made some sense back then when the networks were mostly trusted but it would be interesting to know how existing systems deal with this security problem.