C. Kanich, C. Kreibich, K. Levchenko, B. Enright, G. M. Voelker, V. Paxson, S. Savage, “Spamalytics: An Empirical Analysis of Spam Marketing Conversion”, ACM Conference on Computer and Communications Security, 2008

Direct marketing is a form of marketing that has been used since way before the Internet era. The appeal of such a technique is that it is very simple to calculate the return on investment: it is simply the product of the net profit times the response rate, divided by the total cost. When talking about e-mail based direct marketing, the cost per recipient is very low, therefore taking this formula to an extreme.

Really, in their most essential form, spam economics are just about these three quantities. One of the most spectacular quantities is of course the cost of sending e-mails, which is laughable. This is why spam seems to be economically profitable, despite a very low response rate. The study presented in this paper provides the first quantitative analysis of spam response rate, and very interesting insights into spam operations.

Before talking about the results, it is worth to take a look at the methodology, which is in itself pretty spectacular. The authors infiltrated the Storm botnet, by running 8 unmodified bots in “proxy mode” behind a proxy server which modifies the C&C instructions on the fly. It exploits an architectural weakness which places some bots higher in the command hierarchy, in a man-in-the-middle position. These 8 proxy bots relayed instrumented spam templates to other bots for up to what is estimated to be 1.5% of the total spam sent by the Storm botnet.

Two spam campaigns were instrumented; one was a self-propagation campaign, advertising a program containing the malware, and the second was a “classical” pharmaceutical campaign. The quantitative results are interesting. They show that, overall, the major webmail’s spam filter do a fair job in eliminating this spam. Then, they show that response rate (i.e. the ratio of sent mail vs. completed orders / installations of the program) is low: less than one in ten millions for the pharma campaign, and less than 4 in a million for the self-propagation campaign.

In my opinion, this study offered great insights into real-world spam operations. Even if the authors argue that their work is ethical, I think this remains a question to be further discussed. For example, from their data set, they can nominally say which e-mail would have completed a purchase on a pharmaceutical website.

C. Y. Cho, J. Caballero, C. Grier, V. Paxson, D. Song, “Insights from the Inside: A View of Botnet Management from Infiltration”, LEET ’10, April 2010

MegaD is a large botnet used for spamming purposes, having been responsible for up to a third of the volume of spam at its peak. This measurement and analysis paper looks at MegaD from the inside, by constructing software that acts like a bot from the perspective of the MegaD botmasters, but actually extracts as much information as possible. The measurements span a period of four months.

Generally speaking, botnets are organized in a hierarchy. Infected PCs – or bots – sit at the bottom of the hierarchy. They take order from one or several botmasters, and might communicate with other servers too, as it is the case with MegaD. One of the contribution of this paper is to try to characterize the chain of control and the topology of this hierarchy – although it is probably not exhaustive.

Two new techniques are introduced. The first one is called “Google Hacking”. The authors observed that the control communications transit over HTTP, and that a standard HTTP request to a botmaster over a web browser gives a specific output, distinguishable from other web server responses. They could craft a special Google query, and leverage Google’s index to find more botmasters. The second one, coined “milking” consists of building a mock bot which appears like a bot to the botmaster, but is actually used to extract as much information as possible from the the various components of the botnet.

A big contribution of this paper, in my opinion, is the longitudinal view, i.e. the evolution over time, of the botnet. This includes a takedown attempt, which was unsuccesful, and the evolution of spam campaigns. The authors also argue that there are more than one management behind the botnet.

The key idea of this paper, for me, is the crafting of mocked bots not only to learn about the protocols and modus operandi of the botnet, but to extract a live feed of the botnet’s state and evolution. The longitudinal component is also very interesting.

A. Yaar, A. Perrig, D. Song, “SIFF: A Stateless Internet Flow Filter to Mitigate DDoS Flooding Attacks”, 2004 IEEE Symposium on Security and Privacy, May 2004

Denial of Service attacks are an important class of problems in today’s internet. They are arguably a negative side-effect of the end-to-end principle, because the intelligence is in the end-host, where it is already too late to prevent malicious traffic. Some solutions have already been proposed, but they require drastic changes or a stateful network.

This paper introduces a new defense mechanism against flooding attacks, called Stateless Internet Flow Filter (SIFF), which is, on the opposite, fairly lightweight and doesn’t require state in the routers. It doesn’t require any protocol change at the network layer (which would be a huge pushback for deployment), and doesn’t need to be deployed overnight – although it is arguable whether the benefits are worth it when deployed over a small portion of the network.

The system works roughly as follows, assuming every router in the network implements SIFF. Two classes of traffic are differentiated: privileged traffic, which is granted after a handshake, can be implicitly revoked by the destination, and has always higher priority; and normal traffic (including legacy traffic). Every router marks a normal packet it sees passing by, and the final marking (consisting of the concatenation of each router’s marking) is a token that the destination can send to the sender to grant privileged traffic. On subsequent communications, the sender includes the token, which then can get verified by each router. The router markings change after a small amount of time, giving the possibility to the destination to revoke the privilege implicitly by not sending the new token back.

The protection against flooding attacks is done as follows: packets with a incorrect token are dropped at the first router which doesn’t match it to its marking – with high probability, it won’t get near the destination. Therefore, it is impossible to flood the destination with privileged packets. Packets with a correct token don’t suffer from the congestion because they are given priority. The only difficult step is to go through the congestion to complete the handshake and to get a token, but the authors show that the number of attempts needed is logarithmic in the packet dropping probability.

SIFF relies on two big assumption that are not self-evident at all. First it relies on the fact that servers can distinguish malicious traffic, which might be difficult in the case of DDoS caused, for example, by a large botnet. It relies also on the fact that internet paths are relatively static. It would have been interesting to test the performance impact of route flapping in a realistic internet scenario.

D. A Joseph, A. Tavakoli, I. Stoica, “A Policy-aware Switching Layer for Data Centers”, ACM SIGCOMM Computer Communication Review, Vol. 38, No. 4, October 2008, pp 51-62

This Berkeley paper is, just like for VL2, written in the context of data centers – although the solution proposed is not limited to that particular environment. It describes a system to allow the easier deployment and management of middleboxes in a large, dynamic network.

As we have already seen with previous papers (such as the DOA proposal), the current networking stack lacks the possibility to explicitly address middleboxes. Therefore, a middlebox has to be on the physical path of the packets. In the context of data centers, this has a lot of issues, and the authors categorize them into three general problems. First of all, paths have to be manipulated to include the middlebox, which is error prone, and as there might be many paths, it is difficult to guarantee that the packet is effectively going through the middle box. Second, changes in the deployment of middleboxes are hard because of all the extra configuration that is required everywhere else in the network. Third, it is inefficient, in the sense that load balancing between middleboxes is rarely achievable in practice, and a lot of traffic which doesn’t have to go through it still does (because it is on the path).

The proposed solution, called PLayer, is very interesting, because it requires no change in the end hosts and middleboxes, and minimal changes to the switches. These enhanced L2 switches are called pswitches (policy-aware switches). The network administrator dictates the middlebox policies on a central policy server. These policies get translated into per-switch rules, and are disseminated to the pswitches. One of the key improvements is that network path computation is orthogonal to which middleboxes need to be visited.

Pswitches work roughly as follow: when they encounter a packet that matches a rule which indicates it has to go through a middlebox, they encapsulate it into a new ethernet frame and send it to the middlebox. While this is the basic idea, many subtleties need to be taken care of, concerning the identification of which packets have gone through which middlebox, for example.

Some very interesting properties are achieved by the system. First of all, it allows the placement of middleboxes off the path – in fact, it creates a level of indirection, much like DOA. It also guarantees correctness, even under conditions of multiple failures. On a personal note, I think that this system is a perfect example where Software-Defined Networking (SDF) would shine, allowing an easy implementation of PLayer.

A. Greenberg, J. R. Hamilton, N. Jain, S. Kandula, C. Kim, P. Lahiri, D. A. Maltz, P. Patel, S. Sengupta, “VL2: A Scalable and Flexible Data Center Network”, ACM SIGCOMM Computer Communication Review, Vol. 39, No. 4, October 2009, pp 51-62

Data centers have seen a tremendous development over the last decade, with the rising trend of a data and service centric Internet. One might argue that the most critical part of a data center is the network, and it does indeed present some hard challenges. The environment is very particular, and characterized by low latency and high bandwidth. The authors of this paper argue that while data center allow economies of scale, they need to achieve high utilization to be profitable, and flexibility is therefore a requirement.

VL2 is a novel network architecture for the data center. It tries to meet several objectives; one of them is uniform high capacity between any two servers in the data center. Another one is performance isolation: when multiple services run in the data center, bandwidth allocation has to be fair.

A data center like this achieves this highly coveted property of flexibility – or agility: the servers are all equal peers, and the physical topology has no influence, therefore any server can be assigned to any service without negative impact. In my opinion, this is the key idea of this paper: how to design a network which, independently of the assignment of the servers over the services and their position in the topology, can use every link to its maximum and avoid the creation of hotspots.

VL2 stands for Virtual Layer 2, and its name indicates it is built at the link layer. Every server of a particular service sees a virtual L2 network containing all the other servers of the service. The actual path taken is randomized (at the flow level) with the Valiant Load Balancing algorithm, allowing for uniformity and fairness. This is just one part of the system; there are several other clever tricks and mechanisms that allow high scalability and resilience to failure.

An notable fact about that a VL2 data center doesn’t use any new technology, and can be built with commodity hardware available today. This paper is one year old, and therefore it is difficult to say to what extent it is going to be applied in practice, but I think data centers are an area with huge potential for pioneering networking systems.

B. Pfaff, J. Pettit, T. Koponen, K. Amidon, M. Casado, S. Shenker, “Extending Networking into the Virtualization Layer”, HotNets, October 2009

This paper anchors itself in the rising trend of virtualized computing. It makes the argument that there is a lot of improvement potential for virtual switching over the status quo. Today, most virtual switches mirror their physical counterparts, in the sense that they implement just standard L2 or L3 forwarding. The key idea of this paper is to take advantage of the information one can easily get from a hypervisor to provide better networking at the virtual layer.

The motivation is that, in virtualized environments, the requirements are much tighter than in a traditional physical environment for several properties, such as mobility, scaling and isolation. But on the other hand, and unlike in the physical world, it is easy to have access to e.g. host events. For example, it is possible to know when a host gets powered on or off, or changes its network parameters.

The outcome is Open vSwitch, a virtual switch, which provides much more control over all its internals. The key advantage is its flexibility, which can be leveraged to meet the difficult requirements we talked about above. The authors provide various examples of applications, e.g. virtual private networks in the cloud. The implementation has two components, which correspond to different levels: a fast path which just forwards packets, and a slow patch containing all the control and decision logic.

At the end of the paper, the authors discuss about the complexity vs. flexibility tradeoff in networking, and say that lately flexibility has been favored. They envision a completely virtualized networking environment, where the underlying physical network is kept very simple, and all the complexity is pushed to the virtual layer, where it is easier to manage.

T. Koponen, M. Casado, N. Gude, J. Stribling, L. Poutievski, M. Zhu, R. Ramanathan, Y. Iwata, H. Inoue, T. Hama, S. Shenker, “Onix: A Distributed Control Platform for Large-scale Production Networks”, Proceedings OSDI, October 2010

Onix is in the continuation of the line of research behind NOX, the network operating system, which we read about last week. In a sense, Onix could be described as “NOX on steroids”: it is a system which has the same philosophy, i.e to provide a uniform, higher-level abstraction on top the networking infrastructure to allow simplified management and control. But the interesting aspect of Onix is that it is targeted – and used – on real production networks of considerable size.

In my opinion, the key difference between NOX and Onix is that the latter abandons the idea of providing a completely centralized and consistent abstraction, and relies on the application developer to choose which modules (with different service levels) to use in which part of the application. This is far more scalable, but of course adds quite a bit of complexity.

Applications built on Onix work on a big, distributed data structure called the Network Information Base (NIB). It is a graph describing the entire network, and includes every component, up to the port and link level. I think the key idea of Onix is this data structure, and how it can be updated in a large distributed system. The hard part is really how to distribute and maintain this state across multiple controllers.

All in all, Onix does not present a radically new feature. It relies on many well-known, traditional systems components, such as DHTs, coordination mechanisms, standard protocols, etc. But it is a great display of the possibilities of software defined networking, and shows that the idea scales to large production networks.

D. Moon, J. Naous, J. Liu, K. Zarifis, M. Casado, T. Koponen, S. Shenker, L. Breslau, “Bridging the Software/Hardware Forwarding Divide”, 2010

Routers and switches have to evolve very rapidly over time to remain competitive. They are expected to perform better for lower prices, and at the same time to be able to deliver new functionalities and accomodate new requirements. Embedding forwarding logic in the cardboards achieves very high performance for low cost, at the expense of flexibility. On the other hand, software switches allow much flexibility, but at a poor performance/cost ratio. Given the context, the paper tries to bridge these two extremes and provide a interesting tradeoff between flexibility and performance.

The key idea of the proposal, called SDF (Software-Defined Forwarding) is, intuitively, to have “hardware accelerated” software forwarding decisions. The forwarding algorithm is implemented entirely in software, and once a decision is made, subsequent packets matching the decision are forwarded directly by the hardware. Although this looks a lot like caching, it is conceptually different: in SDF, software and hardware work hand in hand to store and accelerate a forwarding decision, whereas caching works at the flow level, in a transparent way.

An SDF switch has 3 layers. At the top sits the forwarding algorithm, written in a high-level language, and using the SDF API. The so-called System Software is just below, providing a clean interface to the higher layer and taking care of the low-level details. The lowest layer consists of the hardware, which is basically a large Ternary CAM, against which arriving packets are matched. The delicate part of the system is to annotate what was used by the software to take the forwarding decision, and how the packet was modified. The authors argue that this is hard to infer automatically, and therefore require the forwarding application to explicitly signal state and header dependencies.

The authors provide different types of examples. They show how this naturally fits virtualization (i.e. multiple forwarding algorithms). One of the interesting part of the paper, in my opinion, is the ease with which they can implement novel routing schemes such as SEATTLE, i3, etc. One of the limitations, though, is that it can only take decisions based on packet headers (limited by the width of the TCAM).

Personally, there is one point that bugs me a little: IP forwarding using longest prefix matching is very hard to implement in this system, and has, overall, poor performance in my opinion. This shows that there is a class of “reasonable” algorithms that doesn’t fit well into the model. But, as a conclusion, and as the author say, although the use of something like this in production networks is questionable, I think it is a clever technique that has potential for experimental networks.

N. Gude, T. Koponen, J. Pettit, B. Pfaff, M. Casado, N. McKeown, S. Shenker, “NOX: Towards an Operating System for Networks”, ACM SIGCOMM Computer Communication Review, Vol. 38, No. 3, July 2008, pp 105-110

The solution presented in this paper is motivated by the fact that today, large networks are difficult to manage. This is due to the distributed nature of the problem, and the absence of any abstractions over the various network components. NOX, a so-called network operating system, aims at solving these issues. The key idea, which explains the operating system analogy, is to provide a high level abstraction for accessing resources in a uniform, centralized way. This way, a central application can observe and control the network.

The main issue of a centralized system like NOX is scalability; and indeed there is a fundamental tradeoff between scalability and flexibility. At the extreme, every packet has to go through NOX, which obviously doesn’t scale at all. NOX therefore has to choose a granularity level at which it provides control, and it does so by choosing the flow-level. The authors argue that flows can then be distributed across several controller instances, and that the only state that has to remain consistent at all times is the network view, upon which the forwarding decisions are taken.

At lower levels, NOX works with OpenFlow switches, which provides a simple API to manipulate the flow table. At a higher level, NOX provides an event-based API, where applications register callbacks for certains events, such as a switch join for example. Names are kept at high level too – e.g. host names instead of IP or MAC addresses, providing the advantage of topology independence.

As an example, the authors talk about Ethane, which is a network access control mechanism. It has been implemented both in a standalone way, and then on top of NOX. The NOX implementation, written in Python, shows some of the benefits we can expect: use of a very high-level language, and much fewer lines of codes.

L. Popa, A. Ghodsi, I. Stoica, “HTTP as the Narrow Waist of the Future Internet”, HotNets-IX, October 2010

After reading several papers about novel, clean-slate internet architectures, this recently presented paper gives a fresh perspective. It looks at a widely used application protocol, HTTP, and shows that it achieves several good properties. The authors show that HTTP is becoming the predominant protocol on the Internet, getting used even for video streaming. Given that video is thought to represent 90% of the volume of Internet traffic in a few years, the trend doesn’t seem to be going downwards. HTTP infrastructure is widely deployed, and penetrates through corporate firewalls.

Therefore, network proposals should be evaluated with respect to HTTP, i.e. how they compare and how it impacts it. The authors show that HTTP achieves good properties, such as being content centric (anycast through DNS round-robin), providing support through middleboxes (through forward / reverse proxies), and allowing mobility (again, through the use of DNS). However, several other aspects don’t do as well, the best example being support for low-latency applications.

The contributions of this paper, in my opinion, are twofold. The main contribution, which is also the key idea of this paper, is the high-level observation that HTTP is becoming the narrow waist of the Internet, with more and more different services running on top of it. More than just noticing that fact, the authors provide an evaluation of HTTP as such – i.e. a discussion of what it does / does not provide.

The second contribution is technical; a new request method for http is proposed, entitled S-GET (S for Subscribe), which is supposed to provide a datagram service on top of HTTP. It works following a publish / subscribe pattern: if A wants to communicate with B, B sends an S-GET to an intermediary server S, and every time A does a PUT request on S, the data is forwarded to B. Note that this is nothing fundamentally new; current web applications use the same idea under the name “hanging GET”.

Personally, I am not convinced by S-GET. I think the overhead is too large for applications such as VoIP. Also, this breaks some of the HTTP functionalities; for example, HTTPS wouldn’t work as an end-to-end authentication and encryption tool anymore. I am way more convinced by the first part of the paper. Today, HTTP is often a practical intermediary layer for many services, and it should be recognized and evaluated as such.