Defensive Programming: Using an Annotation Toolkit to Build

DoS-Resistant Software
Xiaohu Qie, Ruoming Pang, and Larry Peterson
Department of Computer Science, Princeton University
{qiexh, rpang, llp}@cs, princeton, edu

Abstract discovered until the system is hit by an attack t h a t ex-

This p a p e r describes a toolkit to help improve the ro- ploits the weakness, t h a t is, after the d a m a g e is done.
bustness of code against DoS attacks. We observe t h a t Instead of reacting to attacks, we propose a new
when developing software, p r o g r a m m e r s primarily fo- approach to DoS protection: defensive programming,
cus on functionality. Protecting code from attacks is by which we mean p r o g r a m m e r s embed general mech-
often considered the responsibility of the 0S, firewalls anisms into their software to provide systematic and
and intrusion detection systems. As a result, m a n y proactive protection against DoS attacks. Ideally, de-
DoS vulnerabilities are not discovered until the system fensive software guarantees availability even under a
is attacked and the d a m a g e is done. Instead of reacting previously unknown DoS attack. An i m p o r t a n t as-
to attacks after the fact, this paper argues t h a t a bet- pect of this approach is t h a t it should be designed to
ter solution is to make software defensive by system- thwart common DoS attack characteristics; program-
atically injecting protection mechanisnls into the code mers should not have to scan their code for a specific
itself. Our toolkit provides an API t h a t p r o g r a m m e r s implementation vulnerabilities and fix them, as they
use to annotate their code. At runtime, these anno- do when writing a software patch.
tations serve as b o t h sensors and actuators: watching Towards this end, this paper describes our experi-
for resource abuse and taking the appropriate action ence developing mechanisms to help p r o g r a m m e r s sys-
should abuse be detected. This paper presents the de- tematically build robust software. T h e key idea is to
sign and implementation of tile toolkit, as well as eval- insert annotations that monitor and control the exe-
uation of its effectiveness with three widely-deployed cution of the program at runtime. These annotations
network services. serve b o t h as sensors t h a t detect anomalies and actu-
ators t h a t change the control flow of a program when
1 Introduction they detect t h a t defensive measures are necessary. The
advantage of annotations is that they allow us to ad-
Denial-of-Service (DOS) attacks are a major source of
just the program's behavior at a very fine granularity,
concern in the Internet. Unlike security break-ins t h a t
thereby making it possible to confine the damage of
obtain privileged access, DoS attacks are designed to
an attack without negatively affecting other aspects of
consume a disproportionate amount of resources on
the program.
the target system by exploiting weakness in the net-
work software. W h e n successful, such attacks make We have developed a toolkit consisting of a set
the system unavailable to well-behaved users. of annotation primitives, a runtime library, and
C o m m o n defenses against DoS attacks include us- a set of compiler extensions. As a means of
ing firewalls and Intrusion Detection Systems (IDS) to specifying a resource management policy, a pro-
monitor network links for offending traffic, as well as grammer inserts annotation primitives into code
applying software patches to fix known vulnerabilities. so that the annotations mark where resources
However, such defensive practices burden the system are acquired/released/consumed, where the program
administrator with making sure all systems have the branches into independent functionalities, and what
up-to-date patches installed and all firewalls are prop- principals are holding resources. The compiler exten-
erly configured. To make matters worse, even after a sions check consistency among annotations by analyz-
new attack is recognized, it is not until the vulnera- ing the control flow graph of the program and gen-
bilities exploited by the attack are determined t h a t a erating necessary code to be executed at annotated
patch can be developed. points. At runtime, appropriate monitor and control
We observe t h a t m a n y DoS vulnerabilities can be functions are invoked as control flow passes through
attributed to the separation of software functionality these annotations.
and protection. W h e n developing software, program- The toolkit helps programmers reason about DoS
mers primarily focus on functionality. Protection from problems in a more structured way. Rather than focus
attacks is often considered the responsibility of the O S, on implementation details, they are asked to identify
firewalls, and IDS, and thus not an immediate concern. the services provided and the resources consumed by
As a result, m a n y vulnerabilities in the code are not their program at a high level. For example, if the pro-

USENIX Association 5th Symposium on Operating Systems Design and Implementation 45

 grammer annotates a certain function as performing In general, however, we found profiling-based detec-
an identifiable service, the toolkit will confine a DoS tion insufficient for the fbllowing reasons. First, pro-
attack on that service to requests of the same service, filing does not cover all the important aspects of a
rather t h a n letting the attack bring down the program program's behavior. The target resource of a DoS at-
as a whole. The flip-side, of course, is that the toolkit tack is not necessarily CPU cycles; sometimes it can
is not a panacea. Like any mechanism, the effective- be application-level objects. Second, getting the aver-
ness of the toolkit depends on whether a good defen- age behavior from profiling data is not enough because
sive policy can be specified, which is ultimately the even perfectly legitimate users can deviate significantly
responsibility of the programmer. from the average without attacking the system, rib in-
The paper makes two contributions. First, it stud- fer the behavior distribution Dom profiling data is a
ies the general question of how to develop defensive hard problem that does ,lot have a good solution for
code that protects itself from DoS attacks. In the pro- the general case.
cess, the paper identifies a class of attacks that exploits In order to collect comprehensive data for analysis
a vulnerability existing in many network servers, but and extract meaningful information from the data, it
t h a t has not received attention in the literature. Sec- is necessary to know what resources a program con-
ond, it describes a specific mechanism--the annotation sumes, as well as where and how they are being used.
toolkit---that evolved from this study. We have imple- Our annotation interface allows a program to provide
mented the toolkit in Linux, and demonstrated how such information.
to annotate widely deployed software, including the In performance assertion checking [11], the original
Linux IP protocol stack, the Flash web server [10], and program is instrumented to generate an execution log,
the Linux NIS servers [8]. Our experience shows that which is then checked offline for performance viola-
we can significantly improve the robustness of software tions. The assertions and logging facilities are the
against DoS attacks with relatively low programming counter parts of our resource sensors. Being inde-
effort. pendent of the original program, assertions can be de-
clared in a more expressive language. In contrast, our
2 Related Work resource sensors and actuators are part of the original
program being annotated, monitoring resource usage
Our approach to writing defensive code draws on pre- and changing the program control flow at runtime.
vious research in several areas. This section explains In addition, our goal is not only detection, but also
how our work fits in this larger design space. protection. Since an appropriate defensive action is
highly dependent on the functionality and architecture
2.1 Intrusion Detection Systems
of the program, the action has to be specified at the
Anomaly detection uses statistics of normal behavior source code level. Watching profiling d a t a can some-
as a baseline, and treats changes in these patterns as times tell us the system is being attacked, but without
an indication of an attack. Researchers have demon- a defense mechanism built into the program, the only
strated t h a t examining the sequence of system-calls available response is to kill the victim process, which
made by an application is a viable approach to de- is a DoS attack i n its own right.
tecting security violations due to bugs in the program
(mainly buffer overflows) [6, 14, 18]. 2.3 Static Code Analysis
However, current anomaly detection techniques have There has recently been much work in automatic de-
difficulty detecting resource-exhausting attacks, be- tection of software errors and security bugs through
cause a DoS attacker can request the same service static code analysis. Recent work by Engler et al.
as a legitimate user. Our approach has the flavor of [4, 5] introduced the technique of rneta-level compi-
anomaly detection, but with a focus on resource usage lation. The idea is that the software must obey cer-
rather t h a n security. Since the target of a DoS attack tain rules for correctness, such as "kernel code cannot
is some resource on the victim system, we instrument call blocking functions with interrupts disabled" and
the program to look for irregularities in resource usage "message handlers must free their buffer before com-
and actively participate in resource management. In a pleting". System programmers specify the rules in a
way, we do not have to distinguish DoS attacks from high-level language, and an extensible compiler then
other activities, the rationale being that as long as re- applies the rules throughout the program source to
sources are properly managed, the damage any DoS check for violations. Meta-level compilation is very
attack can cause is limited. successful in finding errors in OS code, as well as a
wide range of security bugs using rules such as "do
2.2 Performance Monitoring not dereference user pointers without checking valid-
Resource-exhausting DoS attacks often cause perfor- ity". The authors found several DoS possibilities in
mance degradation on the target, making it possible to the kernel code they examined, but the result is lim-
detect such attacks by monitoring the profiling data. ited to a special case in which an attacker controls the

46 5th Symposium on Operating Systems Design and Implementation USENIX Association

 iterations of a kernel loop. also on the stage in which the process is running. From
Static analysis alone is not sufficient for detecting this perspective, our approach is similar to SEDA. On
DoS attacks since such attacks do not necessarily rely the other hand, SEDA is not intended for DoS pro-
on software bugs. It is often the cumulative pressure tection, and does not protect resources t h a t cannot be
on resources t h a t puts a system in peril, even though protected by scheduling.
the software itself is bug-free. Thus, besides exam- Finally, our toolkit is intended to improve the ro-
ining how the software is implemented, we must also bustness of existing software. Annotating code is
watch how it is ezecuted. Such information can be only more programmer-friendly than imposing a new OS
collected at runtime with additional application or OS architecture or abstraction, which often requires re-
support. Previous work in detecting race conditions in architecting code. This is especially true with Scout
concurrent programs [12] seems to support this point and SEDA.
of view. Our approach differs from previous work of
static analysis mainly in t h a t we check for possible
3 DoS Attack Characterization
"rule" violations at runtime, with a focus on resource
usage. Researchers have studied many DoS attacks [13, 7].
What is lacking, however, is an analysis of their com-
2.4 OS Mechanisms mon characteristics: what they attack and how they
There has been an ongoing effort to build new OS attack it. Such a characterization would help us under-
mechanisms and specialized OSs to provide service dif- stand the signature of DoS attacks, and shed light on
ferentiation and guarantees. For example, Resource how to systematically and proaetively write defensive
Containers [3] are an abstraction t h a t takes over the software.
process' role as the p r i m a r y resource principal. It There are several well-known attacks on network
allows multiple cooperating processes to bind to the software, including the ICMP flood attack (send a
same container, as well as a process to change its re- large number of ICMP echo packets at the target),
source and schedule binding dynamically when it ex- TCP SYN attack (flood the target with connection-
ecutes on behalf of another activity. The Scout op- open requests), and Christmas Tree packets (over-
erating system [9, 15] uses a similar a b s t r a c t i o n - - t h e whelm a target with packets that have exceptional bits
p a t h - - a s the p r i m a r y resource and schedule principal. turned on in the header--e.g., IP options--dictating
Both systems have been shown to be able to defend the packet receive special processing). A less well-
against certain flooding DoS attacks. The improve- known attack, which we refer to as route cache poison-
ment results from more accurate resource accounting ing, involves an attacker flooding a router with packets
and service isolation. carrying a sequence of nonsensical IP addresses (e.g.,
An i m p o r t a n t contribution of resource containers is "I", "2", "3", and so on), thereby blowing the router's
the separation of resource principals and execution do- first level route cache. This causes the router's control
mains, but as an OS approach, resource m a n a g e m e n t processor to spend all its time building new microcode
policies are ultimately enforced via process schedul- and loading it into the switch engine. This happens at
ing a m o n g execution domains. In case an execution the expense of the router responding to its neighbors'
domain multiplexes among a set of resource princi- routing probes, which causes the neighbors to believe
pals, resource containers reduce to a passive account- the router is down.
ing facility. However, m a n y functionality-rich services, These examples illustrate that DoS attacks abuse a
such as web servers and routing daemons, are single- legitimate service by sending it a large volume of re-
process-event-driven. Intra-process protection is more quests, suggesting that rate limiting [17] and load con-
i m p o r t a n t for these applications, since we do not want ditioning [19] would be an effective defense. However,
to penalize the entire process when just one of its func- DoS attacks can also be carried out in a way that ren-
tions is being abused. This calls for a finer-grain re- ders rate limiting strategies ineffective. The following
source protection t h a n what can be provided by an OS example illustrates this possibility.
approach. Using annotations inserted by the program-
mer to monitor and control the execution p a t h within
3.1 Slow TCP Attacks
a process, our approach offers a finer-grain protection Many T C P - b a s e d services follow the request-reply
t h a n OS approaches. paradigm. Since a server must set aside resources while
Another system-level approach, SEDA [19], pro- a client request is being processed, it is possible to ex-
poses a p r o g r a m m i n g model in which a program is haust the server's resource by manipulating the oper-
divided into stages and each stage enforces its own re- ation of TCP. The idea behind the a t t a c k is for the
source management policy by controlling threads run- client to make the T C P connection as slow as possi-
ning in t h a t stage. This model differs from the tra- ble. This simple idea can be realized in three different
ditional process-based resource protection in t h a t re- ways.
source allocation not only depends on the process, but First, a client can send the request very slowly. Since

USENIX Association 5th Symposium on Operating Systems Design and Implementation 47

 T C P is a byte-stream protocol without record bound- firewall t h a t provides NAT or P r o x y services by repet-
aries, the server cannot interpret the client's request itively sending packets from all available ports to a
until all the d a t a is received. Suppose a request con- r a n d o m set of destinations. Once tile translation table
tains 2000 bytes, and the T C P MSS is 1000 bytes. on tile firewall is filled up, other users are effectively
Under normal operation, the client would send the re- cut off fi'om the rest of tile Internet.
quest in two packets. If, instead, the client sends the
request one byte at a time, which does not violate any
protocol and application requirements, it would take
2000 R T T s before the server can start to process the 3.2 Attacks Revisited
request. T h e client can insert additional delays be-
tween packets to further extend the duration. When characterizing DoS attacks, it is helpful to dis-
Second, once the server starts to send results back, tinguish between two types of resources: renewable re-
the client can read the d a t a very slowly. The server sources, such as C P U cycles, the b a n d w i d t h of net-
side T C P would interpret the closed T C P advertised work, disks, and buses; and nor~-r'er~ewable resources,
window in the acknowledgment packet as a signal t h a t such as processes, ports, buffers, PCBs, and locks. To
the client application is t e m p o r a r i l y busy, thus pause a t t a c k a renewable resource, the attacker continually
s e n d i n g ) T h e server will not be able to send more d a t a consumes the resource so t h a t legitimate services do
until the window is opened again. T h u s by abusing not receive enough of the resource over time. This
T C P ' s flow control mechanism the client can pace the is usually achieved by flooding the server with mas-
rate of d a t a sent by the server. sive number of requests in order to keep the target
Third, the client can acknowledge the response very system busy. In contrast, if the target resource is non-
slowly by pretending the packet was lost. W i t h o u t renewable, the attacker tries to acquire as m a n y re-
seeing an acknowledgment, the server will retransmit. source as possible and does not release them. This
Similar to the slow receiver, the client can pace the form of a t t a c k does not require flooding to make the
sending rate of the server by controlling when to ac- target busy.
knowledge a packet. In this scenario, the client abuses In the rest of the paper we denote an a t t a c k target-
T C P ' s reliable transmission feature. ing a renewable resource a busy attack, and an attack
One t a r g e t of the Slow T C P attack is web servers. targeting a non-renewable resource a claim-and-hold
Being a slow sender, an attacker can construct an attack. However, we note t h a t some attacks cannot be
extremely long H T T P request (e.g., copy the header clearly placed in one category. For instance, the target
"User-Agent: Slow TCP Sender \r\n" 5000 times) resource of SYN flooding a t t a & is half-open connec-
and send it at a very low rate (e.g. 1 byte every 50 tions, which is a non-renewable resource, but to ex-
seconds). Being a slow receiver or ACKer, an attacker haust this particular resource, the attacker must keep
just requests a big file then nibbles at the server's out- the system busy with a flood of new requests. In an-
put. The goal of the attacker is to keep the connection other example, router cache poisoning succeeds when
alive as long as possible. Since the number of concur- the router's C P U is overwhelmed, thus it is a busy at-
rent connections a web server can maintain is limited, tack, yet it works by directly attacking the route cache,
given sufficient number of slow attackers, the server's which is a non-renewable resource.
available connections will be exhausted, and all subse-
quent requests will be denied. These "exceptions" are not special cases, but in
We verified this idea experimentally b y implement- fact, phenomenon due to the duality between busy and
ing a H T T P request generator t h a t uses slow TCP, claim-and-hold attacks. Often in mending one vulner-
and tested it against two popular web servers: Apache ability, we open the system to another vulnerability.
[2] and Flash [10]. The a t t a c k proves to be extremely For example, the Apache web server sets a limit of
effective. Despite the fact t h a t T C P has a keep-alive 150 connections to protect itself from r u n a w a y resource
timer, the Linux T C P implementation limits the num- consumption, yet by enforcing this limit, connections
ber of retransmission a t t e m p t s to 12, and both Apache become a :'scarce" resource and the p r o g r a m is po-
and Flash have built-in mechanisms to time-out idle tentially vulnerable to claim-and-hold attacks. On
connections, all three forms of stow attacks are able tie the other hand, to protect non-renewable resources,
up a connection for several days, causing the servers the system must perform a recycling function when
to disappear from the net. We were also able to attack the resource becomes unavailable. This function it-
NIS servers in a similar way. self could become an accessory in a busy attack if it
In general, we believe such attacks are not limited to is not resource-controlled. This is the weakness ex-
T C P servers. For example, an attacker could disable a ploited by the route cache poisoning attack. Clearly,
a general defense mechanism must protect the system
1After some time, the server TCP will send a 1-byte packet from b o t h types of vulnerabilities at the same time;
to test if the client has consumed any data. watching only one type of attacks is not sufficient.

48 5th Symposium on Operating Systems Design and Implementation USENIX Association

 4 Defensive Strategies traction and all of them are straightforward. The ben-
Our overall strategy is to separate resources among ac- efit of marking functions instead of arbitrary code re-
tivities in a program along two dimensions. For renew- gions as services is that the user need only annotate
able resources we balance resource usage among pro- service entry points. Our compiler can then automat-
g r a m functionalities, thereby confining the impact of ically annotate the corresponding service exit points,
an attack to the individual service being attacked. For thereby reduce the overall programmer workload and
non-renewable resources, we identify principals that the chance of inconsistent marking. Also, the service
hold non-renewable resources and reclaim resources hierarchy structure is clearly represented by the func-
fl'om principals t h a t are not making minimal progress. tion call graph.
These two aspects of our strategy are discussed in turn. Services can be disjoint or nested. For example, in
the Linux IP stack (Figure 2), T C P - r e c v and UDP-recv
4.1 Busy Attack Defense are disjoint services, while the service of IP o p t i o n s
processing is nested inside IP processing. Nested ser-
The strategy is to balance resource usage among pro-
vices allow the p r o g r a m m e r to divide a coarse-grain
g r a m functionalities, thereby confining the impact of
service into finer-grain sub-services. Dividing services
an attack to the individual service being attacked. To- in this way has the advantage of confining the damage
wards this end we introduce the concept of service and
of an attack within a smaller range. W h e n a nested
propose a resource control mechanism with actuators
service tries to over-use some resource, action is taken
at service entries and sensors at resource access points.
only on the inner-most service t h a t directly uses the
resource, for fear t h a t doing anything to the parent
4.1.1 Services and Resources
services m a y over-penalize sibling services. For exam-
We define a service to be a program component t h a t ple, if we further divide the service of I P option han-
provides an independent functionality. Each service, in dling into a sub-service for every type of IP option,
turn, consumes some amount of renewable resources. then when the code dealing with one type of option is
Figure 1 shows the conceptual model of a server pro- attacked, all other IP options can be still be handled
g r a m divided into services. Client requests are served normally.
by different services, as they execute a code p a t h
through the program, and multiple services share var- ip_recv
ious resources. ip_local_deliver ip_f orward I
There is often a clear correspondence between ser- ' TCP-recv ICMP-recv IP options
vices and program code paths, and in m a n y cases, a
service is implemented by a particular function and as-
sociated subroutines. For example, in the Linux ker-
nel, each I C M P service is handled by a distinct func- Figure 2: Services in Linux IP Stack
tion with name icmp_<service> (e.g. icmp_echo).
Thus, a program can be divided into services accord- As services correspond to code paths, we can con-
ing to code paths. To expose the service structure of a trol resource usage of a service by rate-limiting exe-
program, we ask p r o g r a m m e r s to annotate the service cution on its code paths, especially the "expensive"
entry functions in their programs. We have also built ones. For example, the Linux kernel checks a rate
a set of compiler tools to help user check coverage and limit when deciding whether to send out an I C M P
consistency of service annotations. packet. We can view the act of changing from one
execution p a t h to another, based on resource usage,
i . . . . . . . . . . . . . . . . . . . . . . . :.17",,' [ ......... as intra-process "scheduling" among services. How-
ever, since we do not know which code p a t h will be
................... ::::::::::::::::::::::: attacked, and it is hard to precisely tell how expen-
sire code paths are, there are two interesting questions
in rate-limiting code paths: 1) where to place sensors
Services Resources
t h a t monitor resource usage and actuators t h a t change
the p r o g r a m execution path; and 2) at w h a t rates code
Figure 1: Service View of a P r o g r a m paths should be limited, or how to decide whether or
not to switch out of the current code p a t h each time
We assume each service is performed by a function. execution reaches the actuators.
When this is not the case, the p r o g r a m m e r must ex-
tract the part of code that performs the service and 4.1.2 Sensors and Actuators
wrap it in a separate function. Our experience with We need a systematic way to place sensors and actua-
the Flash web server and the Linux T C P / I P code sug- tors in the program, because placing t h e m in an ad hoc
gests t h a t there are few places we need to do the ex- way m a y leave holes to be e x p l o i t e d - - t h e code path

USENIX Association 5th Symposium on Operating Systems Design and Implementation 49

 being attacked might not have an annotation on it. 7' "~
(On tile other hand, we want to minimize the number TIME_$EN$OR -i
I
of'annotations, especially actuators~ because switching I

out of a code path needs to be handled in a program- 'I ~i!ii

I
specific way, and it takes programlner's effort to write f
'l . . . . . .
- MaxTirne
I
such a handler. 11 ~ SERVICE2
l
R a t e limiters found in existing software, such as the I
I
I

Linux kernel, are actually a composite component t h a t

I
I
I
I t
I
J-
L . . . . . . . . . . . . . - 1 "Oeadline
consists of b o t h a sensor and an actuator: the sensor
monitors the execution rate on the code path, and the
actuator deflects the execution to another code p a t h
when the rate limit is violated. This approach works (a) Rate Control (b) Time Control
well because we know which potential attacks we want
to defend against and therefore can put rate limiters Figure 3: Managing Renewable Resources
on the right code path. In our case, we do not assume
t h a t we know a b o u t any particular attack. W i t h this
different assumption, we found t h a t actuators and sen- and cannot be easily shared or reused. In contrast, it
sors need to be placed at different locations in the pro- is straightforward to measure the resource usage at the
gram, in order t h a t (1) actuation happens at the right point the resource is accessed, and it is relatively easy
place, and (2) resource usages to be properly limited. for the p r o g r a m m e r to specify an overall rate limit for
The following discusses the placement of actuators and each t y p e of resource.
sensors, in turn. Taken together, the sensors monitor b o t h the over-
For actuators t h a t control the execution path, we all resource usage and usages by individual services,
argue t h a t service entry points are the right place for thereby affecting admission decisions at a c t u a t o r s
t h e m to be placed. This is for three reasons. First, placed at service entry points. (See Figure 3(a)). Ac-
a service is the unit of fault isolation, and activities t u a t o r s control admission to a n y service t h a t tries to
within the same service share fate. Therefore, it is consume disproportional a m o u n t of resource. Further
better to not begin processing a service request if it details a b o u t the actual mechanism is discussed in Sec-
cannot acquire enough resources to complete. Sec- tion 5.3.
ond, it is easier to a b o r t or delay processing a service
request at the entry point t h a n in the midst of pro-
4.1.3 Controlling Continuous Resource
cessing. Third, each service needs only one actuator, T h e discussion to this point assumes t h a t resources are
thus the total n u m b e r of actuators depends only on always consumed at particular locations of the pro-
the number of services. gram. We further distinguish between two types of
A potential trade-off here is t h a t sometimes at the renewable resources: discrete resources, which include
service entrance we m a y not be able to precisely pre- almost all renewable resource except C P U t i m e (e.g.
dict whether a request can get enough resource. How- n e t w o r k / d i s k bandwidth); and continuous resources,
ever, in all b u s y attacks we know of, a service m u s t which include C P U time. Unlike discrete resources,
be invoked at a high rate in order to exhaust system C P U time is spent continuously as the p r o g r a m exe-
resource. Therefore, the effect of this inaccuracy is mi- cutes, so we can no longer monitor resource on some
nor, because it m a t t e r s only when the service is a b o u t particular code paths. Therefore it needs to be man-
to reach its resource quota. In other words, rate pre- aged differently.
cision is not so i m p o r t a n t in DoS defense, as we are There are mainly two questions: how to detect C P U
not making QoS guarantees. Finally, the p r o g r a m m e r overload and how to locate the service being exploited.
m a y define finer-grained services to achieve better pre- Our approach is to ask the user to specify time limits
cision. on some high-level functions for each invocation, and
For sensors t h a t monitors resource usage, we argue we control admission to the d o w n s t r e a m service t h a t
t h a t they should be put at resource access points, for violates the deadline, as shown in Figure 3(b). Again,
example, where a system call is invoked to t r a n s m i t a more details are given ill Section 5.3.
packet. If we were to put sensors together with actua-
tors at service entries, it would require much effort and 4.2 Claim-and-Hold Attack Defense
experience to set an a p p r o p r i a t e rate limit for each ser- In order to consume renewable resources, the attack-
vice because it is unclear how service rate limits would ing activity must be active, i.e., executing code on the
m a p onto actual resource usage. As we try to set the CPU. This observation has greatly simplified our so-
limits for services before knowing which service will be lution to defend busy a t t a c k s - - b a s i c a l l y we need to
attacked, there is a risk of being either too conservative control the execution frequency and duration of differ-
or too optimistic. Also, the choice is often host-specifc ent code paths. Protecting non-renewable resources,

50 5th Symposium on Operating Systems Design and Implementation USENIX Association

 Events ~. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i

existing ~ response : o :"

• q / "~_ I ~ / .~I / : ,:--~ i

• accepL ............................................................................... ~lm,....-I ~ $ . . . .

',___~,
: ~ ~ ~ -- ~ ~ Pressure Meter

@ Prog .......... (~) ........ S..... ~ R ............... p ....

Figure 4: Managing Non-renewable Resources in an Event-driven Web Server

however, is a different story. Attackers holding the re- making use of the resources it has acquired, and com-
source do not necessarily have to remain active once bine this information with other metrics such as age. A
the resource is acquired. client should be allowed to hold resources longer than
Protecting non-renewable resources is essentially a others, as long as it has a good reason. We use progress
process of specifying a replacement policy: when the to denote such a metric. The exact form of progress
resource becomes exhausted, which ones should be re- depends on the resource and application in question,
claimed. Resources can be reclaimed either periodi- but in general, a proper progress metric should reflect
cally or when some event indicates recycling is nec- how the principal holding a resource is making use of
essary. Thus, the problem boils down to one of de- it. Progress is expected to increase proportionally with
ciding: (1) what resources to reclaim, and (2) when time. In the web server example, how m a n y bytes the
to reclaim them. We introduce two metrics--progress server has sent to the client could be used to construct
and pressure t h a t characterize these two aspects of the progress metric.
a replacement policy, respectively. Our defense strat- A replacement policy also has to specify when to re-
egy involves annotating a program with sensors and claim resources. Since recycling itself could be an ex-
actuators t h a t set and react to these two metrics. pensive operation, uncontrolled invocations also open
up the possibility of busy attacks, which is what we
4.2.1 Progress and Pressure saw in the route cache poisoning attack. We define
In the Slow T C P attack against web servers, the a pressure metric to control the invocation of the re-
resource in question is the server connection. Nei- claim function. Intuitively, resources should be recy-
ther Apache or Flash implements an explicit replace- cled when the pressure on it exceeds a certain thresh-
ment policy. When connections are exhausted, the old, which could be caused either by too m a n y clients
server simply rejects new requests. The connection requesting the resource, or no clients releasing the re-
resource is returned when the client request is com- source.
pleted. It is also reclaimed by timers. In Flash, there Programmers can develop other metrics tailored to
are two build time parameters, CGI_TIMELIMIT and the application. As a general toolkit, we currently
IDLEC_TIMELIMIT. T h e former caps the m a x i m u m run- only support interfaces to keep track of progress and
ning time of a C G I p r o g r a m forked by a client request, pressure, on top of which a variety of policies can be
and the latter controls the m a x i m u m period a client built.
can be idle. W h e n either limit is exceeded, the con-
nection is dropped and resources associated with this
4.2.2 Placing Sensors and Actuators
connection are freed. Figure 4 illustrates how sensors and actuators can be
The weakness of this simple mechanism lies in the placed in an event-driven web server such as Flash.
fact t h a t an attacker can trick the server into thinking Sensors are inserted into a program to track (record)
it is still in the middle of a request, thereby holding re- progress in two ways. If the principal in question gen-
source without triggering the timers. Alternatively, to erates output of some kind, the unit of the output
guarantee availability, we could choose to tear down is a natural measure of progress; e.g., one can anno-
the oldest connection when the connection table be- tate a program with a progress sensor that records how
comes full. The problem with this approach is that it many bytes have been read or written, how many pack-
is biased against clients on a slow link or those down- ets have been forwarded, and so on. In a second sce-
loading a large file. nario, an entire task can be broken into stages, where
A b e t t e r solution is to measure how well a client is progress is recorded when the task moves from one

USENIX Association 5th Symposium on Operating Systems Design and Implementation 51

 stage to the next. For example, the Flash web server extreme situations, for instance an attacker causing
breaks client request processing into three stages: re- the p r o g r a m to enter an infinite loop, we could still lose
quest reading and parsing, back-end processing, and control. We considered other alternatives, such as us-
result sending. Some stages can be further divided ing a timer signal to perform resource checking, but it
depending on the operations required by a particular is extremely hard to perform resource reclamation in a
request (e.g, requesting a static page vs. dynamic con- signal handler while still guaranteeing such operations
tent). A stage is represented by a unique "handler" as- do not lead to inconsistencies. We consider this as one
sociated with a connection. In this example, progress limitation of intra-process p r o t e c t i o n - - s o m e t i m e s we
sensors can be placed where the connection handler is need to depend on inter-process protection provided
changed. by the OS. In other words, there is a trade-off between
It is usually obvious how to insert sensors into a pro- absolute control and preserving the original progrmn
g r a m to t r a c k pressure: there are often well-defined structure.
points in the p r o g r a m where non-renewable resources
are accessed; e.g., inside resource allocators and deallo- 5 Annotation Toolkit
cators. Pressure sensors can be placed at these points. This section describes our a n n o t a t i o n toolkit in detail,
Some a b s t r a c t non-renewable resources are not ac- focusing first on the annotations themselves, and then
cessed via an explicit function interface, in which case on the underlying implementation.
we need the p r o g r a m m e r to annotate the points at
which the resource is acquired and released. 5.1 Renewable Resource Management
Turning to the a c t u a t o r side, there is a single recla- The toolkit includes annotations t h a t are used to de-
m a t i o n a c t u a t o r t h a t is a function of b o t h metrics: it note admission control upon service entry, plus anno-
decides to reclaim resources if the pressure metric is tations t h a t serve as sensors for monitoring rate and
greater t h a n some threshold, and should this be the time limits. We consider each in turn.
ease, it uses the progress metric to decide which in-
stance of the resource to reclaim. Reclamation actu-
• SERVICE_ADMISSlON(min_rate)
ators are placed in two types of locations. First, the The user marks a function as a service entry point,
trigger role of the pressure sensor suggests t h a t a recla- specifying the minimum rate at which that service
m a t i o n a c t u a t o r should be placed immediately after a is allowed to proceed. For example, the following is
pressure sensor. In fact, we we envision a combined from the service that satisfies cold cache requests in
pressure a n n o t a t i o n marking the point where resources the Flash web server:
are claimed and released. SRCode
ProcessColdRequest (httpd_conn* hc)
In addition, however, pressure also needs to be ex- {
amined periodically, as it could build up even in the if ( !SERVICE_ADMISSION (3))
return SR_PLEASE TRY_AGAIN_LATER ;
absence of activity. This implies t h a t we also need to /* rest of the function ... */
insert a reclamation a c t u a t o r - - w h i c h we call a recla- }
mation checkpoint to distinguish it from the combined
This annotation does not directly change the ex-
pressure s e n s o r / a c t u a t o r - - t h a t is periodically visited
ecution path of the program, but returns a hint on
by the control flow. For most server p r o g r a m s this is
whether the service should be admitted based on its
not a problem as they are iterative by nature. For ex-
resource usage, allowing the program to (i) do neces-
ample in Flash, we could place such an a c t u a t o r inside
sary cleanup before aborting, (2) delay servicing the
its main event loop, as shown in Figure 4. An impor-
request, or (3) ignore the hint. T h e annotation takes
t a n t issue however, is t h a t when an action is taken,
p a r a m e t e r rain_rate and always returns 1 when the
it must not leave the server in an inconsistent state;
service is invoked below the minimal rate, regardless
e.g., not free all resources associated with an activity,
whether the service has used up its resource quota.
or continue to reference a principal t h a t is no longer
This allows users to guarantee service rate for some
valid due to the reclamation. We do not have a gen-
i m p o r t a n t services under resource contention.
eral solution to the problem, except t h a t by impos-
ing t r a n s a c t i o n semantics the risk of inconsistency can • RATE_SENSOR(max_rate, weight)
be reduced. In other words, the checkpoint should be This annotation is used to specify the maximal
placed outside all functions t h a t are considered atomic. weighted r a t e for a particular code path. For exam-
Finally, when placing a reclamation checkpoint we ple, in order to rate-limit the packet and byte rates of
need to consider how often it is visited by the p r o g r a m ICMP, we m a y annotate the code with the following
control flow. If the interval is not properly bounded, lines before I C M P pushes a packet to IP:
we effectively lose control on the resource. One way to if (!RATE_SENSOR (sysctl_icmp_max_msg_rate, i))
preserve granularity is to use the techniques presented icmp_msg_rat e_vio I at ion++ ;
if (!RATE SENSOR (sysctl_icmp_max_byte_rate, msg size))
in the previous section, s u c h as the time-sensor, to icmp_byt e rat e_violat ion++ ;
limit the branches leaving the checkpoint. But under ip_build_xmit (...) ;

52 5th Symposium on Operating Systems Design and Implementation USENIX Association

 RATE_SENSOR can be placed any where in the pro- Some applications disable new requests as soon as the
gram, unlike SERVICE~DMISSION which must be put resource is used. In this scenario, pressure cannot be
at function entries. It returns a hint on whether the tracked in a discrete fashion. Instead, pressure accu-
current measured rate of the code p a t h is within the mulates continually over time when no resources are
specified maximal rate. However, it is completely le- released. These two annotations are used in such sit-
gitimate for p r o g r a m m e r to ignore the hint (as in the uations.
example above) if the limit is not strict. This is be-
cause the annotation sends feed-back to the service
® PROGRESS_SENSOR(resid,p, prog)
admission point, thereby eventually limiting resource This amlotation updates the progress metric of a prin-
usage to the specified rate. cipal by prog. T h e use of the opaque pointer p should
be consistent with t h a t in RESOURCE_ACQUIRED and
• TIME_SENSOR (max_time) RESOURCE_RELEASED.
This annotation is used to monitor the execution time
o RECLAMATION_CHECKPOINT(resid, cb, min_pres,
of a function (and its subroutines) on each invoca-
min_prog)
tion. It is applied on functions in the same way as
SERVICE_ADMISSION. For example, to control the exe- This annotation is the actuator t h a t performs resource
cution time of an event handler in Flash web server, recycling. By default, it takes resources back from
we e x t r a c t the invocation of the event handler into the principal making the least progress. P r o g r a m m e r s
a separate function and annotate the function with can configure the operation with two additional pa-
TIME_SENSOR so t h a t admission to services invoked by rameters: min_pres specifies t h a t actions should be
event handlers will be bounded by the time limit. taken only when the pressure exceeds certain thresh-
old; mi'n_pro9 restricts the actions to be taken only
static void LaunchHandler(...) upon principals making less progress t h a n the p a r a m -
{
TIME SENSOR(handlerTimeLimit); eter. By setting different thresholds, a p r o g r a m m e r
h~ndler(tempConn, i, do_what); can control tile frequency of recycling and give prin-
}
cipals t h a t have already made significant progress an
allowance to finish the task. P r o g r a m m e r s also need
5.2 Non-renewable Resource Management to specify a callback function cb t h a t is invoked by the
The toolkit also includes a set of annotations t h a t b o t h actuator. It should free resources associated with a
d e m a r k the allocation and freeing of non-renewable re- principal (identified by the opaque pointer), but can
sources, and check to see if resources need to be re- also be used to log activity for offtine analysis.
claimed.
5.3 Implementation Details
® RESOURCE_DECL(resid)
Each annotation is implemented as a C-macro, and is
This annotation declares a non-renewable resource linked with an instance of a corresponding d a t a struc-
t h a t needs protection, where resid is a unique identi- ture. K e y d a t a structures in our toolkit include ser-
fier. T h e annotation initializes a d a t a structure to rep- vice, rate sensor, time sensor, resource, and principal,
resent the resource. This annotation should be placed with each maintaining a different set of counters.
in the initialization p a r t of a program. A service structure contains a rate counter for ser-
vice entry rate so t h a t it can tell whether the entry
® RESOURCE_ACQUIRED(resid, p, amt)
rate is below the minimal rate given in the annota-
® RESOURCE_RELEASED(resid, p, amt)
tion. It also contains flags to indicate resource or time
These two annotations take an opaque pointer and the limit violation b y the service. The rate counter is re-
amount of resource being accessed. The pointer serves set to zero at the end of every period (a period lasts
to identify the principal; it is usually an application- for one second in our prototype). The violation flag is
specific d a t a structure. The annotation also records also adjusted periodically.
the t i m e s t a m p of the operation in order to calculate To account resource usage of services, global vari-
the duration of resource being held b y the principal. able current_service points to the service currently be-
ing executed. As services can be nested, the variable
® PRESSURE_SENSOR(resid, s)
is updated on each service entry and exit. (Our com-
This annotation records pressure on the resource prier extension inserts service exit calls corresponding
caused by discrete events, such as a new request be- to [Link] annotations.) The following
ing denied due to the lack of resources. The second gives pseudo-code for service admission and exit:
a r g u m e n t can be used to express the severity of the
situation. do_service_admission (svc id, min_rate) {
if (at the end of period)
adjust rate and time violation;
® RESOURCE_UNAVAILABLE(resid) update service entry counter;
® RESOURCE_AVAILABLE(resid) check_deadline () ;

USENIX A s s o c i a t i o n 5th Symposium on Operating Systems Design and Implementation 53

 set current_service to svc_id; service being marked as the violating service will be
if (service within min_rate II there is no violation)
return I; rejected admission ibr some penalty period (with the
return O; same exception of minimal service rate), at which time
violation flag on the service is reset to 0. The duration
d o s e r v i c e _ e x i t () { of the penalty period depends on by how much time
check_deadline();
set current_service to parent service;
the service violates the time limit.
)
do_time_sensor(max_time) {
current_deadline = current_usage time + max_time;
The rate sensor structure contains a rate counter for passed_deadline = O;
}
each service that uses the rate sensor and a counter
for the overall rate. In addition, it maintains a shared check_deadline() {
rate limit for services: whenever a rate counter of any if(!passed_deadline aa current_usage_time > current_deadline) {
time_violation(currentservice) +=
service exceeds the shared rate limit, the service is penalty(current_usage time - current_deadline);
marked with a rate-limit violation flag, and its subse- p a s s e d d e a d l i n e = i;
}
quent admissions will be rejected until the end of the }
period (with the exception of services t h a t are admit-
ted because they are below the minimal service rate). The implementation of the interface for non-
T h e shared rate limit is adjusted at the end of each renewable resource management is straight-forward.
period with additive increase / muItiplicative decrease Most macros simply update the pressure or progress
(AIMD) depending on whether the overall rate exceeds counter in the data structure representing a resource
the given limit on the sensor. Below is the pseudo-code or a principal. As an example, we give pseudo-code
for rate sensor: for R E C L A M A T I O N _ C H E C K P O I N T :

do_rate_sensor(rate_id, max_rate) { do_reclamation_checkpoint(resid, cb, min_pres, m i n p r o g ) {

if (at the end of period) update pressure on resid;
adjust shared limit AIMD (total rate counter, max_rate); if (pressure(resid) > min pres) {
update per service and total rate counters; for (each pri holding the resource) {
if (per service counter > shared limit) { usage(pri) += (time_now - last_timestamp) * held amt(pri);
set rate violation on current_service; normalized_prog(pri) = absolute_prog(pri) / usage(pri);
return O; update worst_pri by comparing normalized_prog counters;
}
return (rate_counter(rate_id) <= max_rate); /* worst_pri records the pri making the least progress */
if (normalized_prog(worstpri) < min_prog)
(*sb)(worst_pri);
}
Adjusting the shared rate limit dynamically allows
more flexible rate control than computing the limit
with min-max algorithm, which assumes that every The only trick in the code is that comparisons are
service obeys the shared limit. T h e programmer may made in normalized progress, rather t h a n absolute
allow" some service to use more resources than the com- progress, as reported directly by the application via
mon s h a r e - - b y overriding it with minimal service rate the PROGRESS_SENSORmacro. The reason is t h a t com-
or ignoring the result of SERVICE. ADMISSION - - b u t the paring absolute progress is not fair to young princi-
shared rate limit is adjusted to a level so t h a t the over- pals t h a t have not yet received enough time to make
all rate still matches the specified limit. This allows progress. Intuitively, a principal holding resources
users to make application-specific decision on resource for a longer period of time should have made better
allocation other than purely "fair" sharing. progress.
Like the S E R V I C E _ A D M I S S I O N annotation, the scope
of a TIME_SENSORannotation includes the current func- 5.4 CompilerSupport
tion and all its subroutines. At entry TIME_SENSOR Because code path annotations are tightly coupled
computes and stores a deadline in global variable cur- with program control flow structure, we instrumented
rent_deadline. When T I M E _ S E N S O R is applied in a user- GCC and built some small tools to help users anno-
space process, the time-stamp is obtained by getting tate their code. In general, the compiler automatically
process usage tinie (which is process time plus sys- adds auxiliary annotations to complete those marked
tem time on behalf on the process) in order to ex- by user, and links the code annotation with the toolkit
clude the impact of process scheduling. (In contrast, data structures. It also checks consistency of annota-
[Link] and RATE_SENSORuses wall time.) tions and gives warning on potential discrepencies.
Within the scope of time-limit, the current time is GCC builds a syntax tree for each function b o d y
compared against eurrentJeadline (see the pseudo- after parsing. We added our extension to a hook be-
code for c h e c k _ t i m e _ l i m i t below) at each service en- tween parsing and intermediate language (RTL) gen-
try and exit. If the deadline is missed, the current eration. The compiler extension traverses syntax trees
service is marked as the violating service and follow- to look for service admission/time sensor annotations
ing services will not check the deadline any niore. The and function exit points. When a function is marked

54 5th Symposium on Operating Systems Design and Implementation USENIX Association

 with a service admission/time sensor annotation, the To limit time spent in each event handler func-
compiler inserts a call to the corresponding service tion invocation, we extract the handler function call
e x i t / t i m e sensor exit functions before each function in main loop and place it in a separate function,
exit. called LaunchHandler, and annotate this function
T h e instrumented G C C also writes the control flow with TIME_SENSOR.
graph to a file. Our code p a t h analyzer then reads this All non-renewable resources in Flash are consumed
file and gives warnings for following cases: (1) there is on behalf of a connection, which is itself a non-
a p a t h from an entry function to a rate-sensor anno- renewable resource. Flash disables new requests
tation that does not go through any service admission when numConnects reaches the upper limit. The
annotation, and (2) there are some expensive opera- following code illustrates how we annotated function
tions (e.g. loops and library flmction calls) enclosed A c c e p t C o n n e c t i o n s - - w e insert two sensors to track
by a time-sensor annotation and not enclosed by any usage and pressure on the connection resource. Note
service admission annotation. the pointer to the h t t p _ c o n n d a t a structure is used as
the principal identifier.

6 Evaluation int AcceptConnections(int cnum, int acceptMany) {

h t t p d _ c o n n * c;
We experimentally tested our toolkit on widely de- do (
ployed software: the Flash web server, Linux kernel PrepareConn0nAccept(c, newConnFD, &sin);
numConnects++;
networking code, and NIS (yellow page) server. For RESOURCEACQUIRED(HTTPCONN, c, 1);
each example, we annotate the code by asking our- } while (numConnects < maxConnects aa acceptMany);
if (numConnects >= maxConnects) {
selves the same set of q u e s t i o n s - - w h a t services need DisallowNewClientsO;
to be separated and what resources need protection. RESOURCE_UNAVAILABLE(HTTPCONN);
}
We then tested the robustness of b o t h the unmodi- }
fied and annotated servers under various attacks. We
found t h a t both busy and claim-and-hold attack vul- A typical H T T P connection goes through three
nerabilities exist in all test cases, and that by exploit- phases: request reading and parsing, back-end pro-
ing these vulnerabilities, an attacker could either dis- cessing (fetch a file from disk or execute a C G I
able, or seriously degrade the level of service. T h e program), and result sending. A connection makes
annotated servers are much more resilient under the progress when it moves to the next phase or sends out
attacks, which demonstrates the generality and effec- bytes. Thus, progress sensors are inserted where the
tiveness of our toolkit. We also found situations where "state" of a connection changes and d a t a is sent out:
our toolkit has difficulty in providing protection to the DoConnReadingBackend and DoSingleReadBackend
desirable level. We identify some as implementation are two examples of functions with embedded progress
issues t h a t can be improved by extending our toolkit, sensors.
while others are fundamental limitations of our ap-
proach. DoConnReadingBackend(httpdconn* c, int fd, int doReqReading)
{
switch(ProcessRequestReading(c)) {
6.1 Flash Web Server case PIh~_DONE:
/* end of request reading */
6.1.1 Annotating Flash Web Server PROGRESS_SENSOR(HTTPCONN, c, 10000);
break; /* switch connection to the next phase */
Flash [10] is a web server with a single-process-event- }
driven architecture. T h e main loop launches connec-
tion handlers on I / O events. We first annotate ev-
ery handier function called in main loop as a ser- DoSingleWriteBackend(httpd_conn* c, int fd, int testing)
{
vice entry point. Since some of these handlers im- sz = writev(c->hc_fd, ioBufs, numIOBufs);
plement more than one independent functions--e.g., it
)*'0k, we wrote something. */
m a y either read a file or execute a C G I p r o g r a m - - PROGRESS_SENSOR(HTTPCONN, c, sz);
we m a r k nested services in top-level services by func- }
tionality (e.g., C G I S t u f f ) . There are also some func-
tions t h a t contain loops or make system calls (and Finally, we explicitly declare the connection resource
thus have potential to be attacked). One such exam- before entering the server loop and insert a checkpoint
ple is M a k e C r o s s e d S t r i n g , which concatenates parts inside the loop. The annotated main loop is shown
of a cross-buffer string. Such functions are also below. DoneWithConnection is a Flash-provided re-
marked as separate services for fault isolation. A source deallocator, here conveniently used as the call-
fourth class of functions perform non-critical t a s k s - - back function for connection recycling. The choice of
e.g., R e d u e e C a c h e I f N e e d e d - - w h i e h we also m a r k as the parameters rnin_pres and min_prog are explained
services. Altogether, 46 services are annotated. in Section 6.1.3.

USENIX Association 5th Symposium on Operating Systems Design and Implementation 55

 I Main Loop I
void MainLoop(void) { J - - -jr- - ~
RESOURCE_DECL(HTTPCONN);
for (;;) {
RECLAMATION CHECKPOINT(HTTPCONN, DoneWithConnection, 5, 500);
for (each I/O event) {
Launchhandler(hemdler, tempConn .... );
}
if (!newClisntsDisallowsd) AcceptConnsctions(-l, TRUE);

6.1.2 Slash Attack

Flash is a very robust program: disk operations and
C G I jobs are separated into helper processes rather
Figure 5: Position of E x p a n d S y m l i n k s in Flash service
t h a n performed by the m a i n process, thereby allow-
hierarchy
ing the OS to protect the main process. Flash also
has some built-in mechanisms to control its resource
consumption; e.g. calls to f o r k ( ) are already rate-
service depending on how much time it takes for each
limited. However, it is extremely difficult to write a
invocation. T h e connection is closed on service admis-
p r o g r a m free of vulnerabilities, and Flash is not an
sion rejection, so t h a t connections do not accumulate
exception. We found the following code in function
over time. Service P r o c e s s C o l d R e q u e s t B a c k e n d 2 is
ExpandSymlinks, which parses a "cold" URL t h a t is
not invoked for "hot" URLs. By limiting C P U spent
not in server's hot URL cache:
for cold URLs, we insure access to hot pages under
/* Remove any leading slashes. */ slash attack.
while ( rest [03 == '/' )
{
(void) strcpy( rest, ~(rest[l]) ); no attacker 4.3 ms
}
--restlen; attacker # s l a s h = 0 4.3 ms
attacker # s l a s h = 10000, original 25,000 ms
T h e loop has time complexity quadratic in number attacker # s l a s h = 10000, a n n o t a t e d 5.1 ms
of leading slashes. As Flash does not limit the length
Table h Flash response t i m e under slash attack
of a URL, a URL with m a n y leading slashes takes a
lot time to parse: it takes 150 ms on a P I I I 700 ma-
chine to remove 10,000 leading slahes from a URL; Table 1 compares the average response t i m e for a
7 such requests per second is enough to s a t u r a t e an "hot" 10KB file for b o t h original Flash and a n n o t a t e d
u n - a n n o t a t e d server. Flash, when the server is under slash attack. T h e slash
Our attacker is a simple p r o g r a m t h a t sends H T T P attacker sends 10 requests per second to s a t u r a t e the
request " G E T / / / / / . . . / / i d " to the Flash server, where Flash server. We first measure response time to a sin-
id = 1, 2, 3, ... to avoid duplicate URLs. Under at- gle client without any attacker present. We then mea-
tack, the u n - a n n o t a t e d server soon reaches the maxi- sure response time to client when there is a competing
m u m n u m b e r of connections. Subsequent connection client; i.e. the attacker sends ten requests per second
requests enter a connection queue waiting to be ac- but with no leading slashes in the URL. T h e third
cepted. T h e server will accept a connection every 150 row shows response time from an u n p r o t e c t e d Flash
ms. Thus server response time is greater t h a n the con- server under attack, a 5000× slow down. T h e last
nection request queue length × 150 ms. row shows the response time from an a n n o t a t e d Flash
Slash a t t a c k serves our purpose well because it server. T h e small increase of response time for anno-
shows t h a t implementation inefficiencies t h a t lead to t a t e d Flash under a t t a c k is because Flash processes a
DoS vulnerability m a y a p p e a r at unexpected locations cold URL periodically and thus delays the hot request
in the source code. Ad hoc protection is not likely to for up to 150 ms. Despite this small fluctuation, the
cover such a vulnerability and we need a systematic ap- response time from an a n n o t a t e d Flash server does not
proach for DoS defense. Importantly, we knew about change by much on average under slash attack.
this problem to formulate the attack, but we did not On the other hand, access to cold URLs is limited
need to have knowledge of this bug when annotating for a n n o t a t e d Flash under slash attack. T h e probabil-
the code. ity of success for a cold request is linear to the ratio
For a Flash server t h a t is a n n o t a t e d with service ad- between the user request rate and the a t t a c k request
missions and a time sensor with a limit of 20 ms on rate. For example, if an attacker sends ten requests
L a u n c h H a n d l e r , the a t t a c k has no effect on requests per second (which is enough to s a t u r a t e an unpro-
of hot URLs. The annotations recognizes t h a t service tected server) and the user sends one request per sec-
P r o c e s s C o l d R e q u e s t B a c k e n d 2 (see Figure 5) takes ond, then with probability 50% it takes no more t h a n
too much time on each invocation and r a t e limits the t h a n l o g 0 . 5 / l o g 0 . 9 - 6.57 requests to access a cold

56 5th Symposium on Operating Systems Design and Implementation USENIX Association

 URL. However, since nothing prevents the attacker "very slow", another one third can be "slow", while
from sending requests at a higher rate, clients m a y not the rest have to be "fast" connections. This can be ac-
be able to access "cold" pages in m a n y attempts. This complished by putting more t h a n one checkpoint with
phenomenon shows t h a t the effectiveness of fault iso- multi-level progress-and-pressure thresholds, so that
lation depends on service granularity, and sometimes the server will recycle resources more aggressively un-
depends on p r o g r a m classification granularity. If Flash der higher pressure.
were to further classify requests into ones with short
URLs and those with long URLs, the impact of a slash 6.1.4 Overhead
attack would be further limited. Regarding programming overhead, we add in total 57
annotations into Flash source, which has more than
6.1.3 Slow TCP Attack 12,000 lines of code. 46 of the annotations are ser-
In unmodified Flash, the connection resource is recy- vice admission primitives t h a t divide the program into
cled by an idle timer associated with each connection. fine-grain services. The rest are annotations on indi-
The default time-out value IDLEC_TIMELIMIT is 500 vidual kinds of resources; e.g., C P U time and H T T P
seconds. The timer is reset by any event on the socket, connections. As the annotations specify general re-
such as d a t a arrival or T C P send buffer becoming source policies, they should be able to defend against
available. Thus, to launch a successful claim-and-hold not only the attacks in the experiments, but also other
attack, an attacker needs to generate an event before potential attacks targeting the a n n o t a t e d services and
the 500 second timer expires. Once the available con- resonrces.
nections run out, the unmodified Flash server enters In terms of request response time or server band-
the "denial-of-service" mode, disallowing new clients. width we did not observe any performance degradation
Our Slow T C P based clients can easily cause the situ- caused by annotation in our measurements. Table 2
ation to persist for days without generating very much reports the number of annotation primitives invoked
network traffic. on a typical H T T P request and the general cost of
By comparison, the annotated Flash server is able to each annotation. T h e n u m b e r of annotations executed
recover from the "denial-of-service" mode by recycling varies depending on the file's size and whether it is in
connections. Our current toolkit implementation uses server cache, which affects the call graph, the num-
a sliding window to record pressure history. Setting ber of server iterations, and the number of outgoing
min_pres to 5 instructs the server to reclaim resources packets. T h e cost of each annotation is given in the
from unproductive connections after it has been disal- number of instructions and "timestamp" operations.
lowing new clients for about 5 seconds. The progress The exact cost of t i m e s t a m p depends on whether the
of each client is tracked as follows: when a connection code being annotated is in kernel or user-space.
moves from one stage to another the absolute progress
of the connection is incremented by a numerical value Primitives Invocations Instructions/
per HTTP timestamps
of 10000; when the connection is in the final result connection per call
sending stage, its absolute progress increases as the SERVICE Entry/Exit 13 - 31 63/2
bytes being successfully written. In conjunction with RATE~ENSOR n/a 25/1
TIME_SENSOR iterations 36/2
the min_prog of 500, the server enforces the following RESOURCE_ACQUIRED 1 62/1
policy: a client should not stay in one stage (other t h a n RESOURCE_RELEASED 1 42/0
PROGRESS_SENSOR 2 + pkts 23/0
the last one) for more than 20 seconds, otherwise its RECLAMATION_CHECKPOINT iterations i21/i
normalized progress will drop below 10000/20 = 500 per principal
and be considered "unproductive". Once in the final
stage, the client should read at least 500 bytes of the Table 2: Annotation Overhead
server's response per second. With these resource lim- Note the 121 instructions are the worst-case cost of
its, well-behaved clients including those on slow links RECLAMATION_CHECKPOINTwhen the pressure is high
go largely unaffected, but claim-and-hold attackers are and each connection is checked. Also not shown in the
no longer able to tie up server resources for unreason- table is certain background processing of the toolkit
ably long periods of time. library, which executes once per second for each anno-
Note t h a t by specifying a single progress-and- tation and contains less t h a n 20 instructions per invo-
pressure threshold, we m a y not be able to completely cation.
eliminate the vulnerability to Slow T C P attacks. At-
tackers can still open m a n y connections and make each 6.2 Linux Networking Code
request proceed slowly while staying just above the
6.2.1 Annotating Linux Network Code
acceptable progress threshold. To solve this problem,
the p r o g r a m m e r can specify a more refined defensive We annotate part of Linux 2.4 network code to protect
policy with the toolkit: for example, under resource network outgoing bandwidth. Our goal is to insure
pressure, at most one third of the connections can be t h a t no single network activity can monopolize outgo-

USENIX Association 5th Symposium on Operating Systems Design and Implementation 57

 ing network bandwidth. (For incoming network band- 6.3 NIS Server
width, protection on local host m a y not be enough,
This section studies ypserv.--the yellow page server
however, we m a y want to limit C P U time spent on in-
available on most U N I X systems. Even though the
coming packets for hosts with high-bandwidth network
server program itselfis simple, it is interesting because
connections.)
it illustrates how different soRware architectures a~ct
Initially, we m a r k service entry points at the %end
robustness, ypserv is built on top of the R P C protocol
message" function of each protocol; e.g. udp_sendmsg.
[16]. Most R P C programs are built with t l P C library
This gives us protocol isolation. However, i c m p _ r e p l y
and tools like r p c g e n , which handles complex tasks
is an interesting case since it is called by multiple func-
such as packaging a call into a message, sending it
tions for sending different types of I C M P messages,
over the network, and server side message decoding.
e.g. icmp_echo and icmp_timestamp. To have fault
W i t h the R P C library, the p r o g r a m m e r only needs to
isolation between different types of I C M P messages,
provide a function t h a t is called when a request ar-
we push the service entry at i c m p _ r e p l y into functions
rives. The R P C package is valuable for constructing
for every t y p e of I C M P message t h a t calls i c m p _ r e p l y .
distributed systems, but it also comes with a poten-
For example, icmp_echo is now a service entry func-
tial disadvantage: its virtualization gives p r o g r a m m e r s
tion, while i c m p _ r e p l y is no longer marked as a ser-
less control on the execution of the program.
vice. icmp_send presents another interesting case: it
Linux ypserv-2.2 is a typical R P C server built us-
is called at l a locations to report different network er-
ing these tools. It starts by calling C lib functions
rors. To prevent one t y p e of error from suppressing
s v c u d p _ c r e a t e , svctcp_create, svc_register and
others, we w r a p each call site as a service. In total, we
svc_run, which create t r a n s p o r t channels, register YP
m a r k 27 services.
services, and start a server loop t h a t waits for re-
Since we m a y not be able to get notification a b o u t
quests. T h e main service routine ypprog_2 is passed
delivery of packets for protocols like ICMP, we can-
to s v c _ r e g i s t e r as the callback function, y p p r o g ~
not apply congestion control to m a n a g e bandwidth, as
dispatches incoming calls to second level routines
the Congestion Manager does [1]. Instead, we simply
such as y p p r o c a n a t c h _ 2 _ s v c and y p p r o e _ a l l _ 2 _ s v c ,
rate-limit messages from all protocols except TCP. 2
and sends results back by calling C lib function
On code paths that call ip_build_xmit, we insert a
svc_sendreply.
call to ip_rate_control, which includes RATE_SENSOR
annotations:
6.3.1 Claim-and-Hold Attacks
static __inline__ int ip_rate_control(int meg_size)
{ A client p r o g r a m like y p c a t requests the entire con-
int res = I; tent of a database from the server. T h e server handles
if ( !RATE_SENSOR (syscgl_ip_max_msg_rate, I)) {
res = O; ip_msg_rate_viola~ion++; the request b y calling y p p r o c _ a l l _ 2 _ s v c . W h e n ship-
} ping bulk d a t a over the network, y p s e r v uses T C P
if ( !RATE_SENS0R (sysctl_ip_max_byte_rate, meg_size)) {
res = 0; ip byte rate_violation++; as the t r a n s p o r t protocol. We found the same vul-
} nerability to Slow T C P attacks also exists in y p s e r v .
return res ;
} To verify this, we built a customized version of y p c a t
t h a t uses Slow T C P as its transport. We set up a
The user can adjust sysctl_ip_max_msg_rate and different number of y p e a t attackers, each requesting
sysctl_ip_max_byte_rate through the/proc file sys- a database of 150K bytes. While the a t t a c k is in
tem. progress, we test the server's availability by issuing
" r p c i n f o - [ t u ] s e r v e r y p s e r v " and n o r m a l y p c a t
6.2.2 ICMP-Echo Flood Attack commands from a different machine. In addition to
To simulate ICMP-echo flood attack, the attacker the latest version y p s e r v - 2 . 2 , we also tested an ear-
sends a flood of I C M P - e c h o packets to the victim using lier version ( y p s e r v - l . 3 ) . T h e main difference be-
the ' p i n g - f ' c o m m a n d . The attack has a 100Mbps tween tile two versions is t h a t y p s e r v - l . 3 executes
network link and the victim is on a 10Mbps link. T h e y p p r o c _ a l l _ 2 _ s v c in a forked child process, and keeps
victim Mso runs a Flash web server so t h a t we can the number of children process below 40. T h e results
measure how it is affected by the attack. are summarized in Table 3, where "Yes" means the
W i t h o u t protection, access to the Flash server on normal client successfully gets a response from the
the victim machine is virtually blocked by the I C M P server and "No" means the server is unable to reply.
flood. However, the a t t a c k has almost no effect on a T h e results show t h a t ypserv-2.2 becomes unrespon-
target s y s t e m with a n n o t a t e d Linux code, except for sive under the presence of any slow y p e a t attackers.
the high loss rate for ICMP-echo messages. This is not surprising since it is an iterative server
t h a t handles only one call at a time. Interestingly,
2Including T C P in rate-limiting does not work because T C P
will automatically back-off while other services are trying their version 1.3 with concurrency support also failed with
hardest to grab bandwidth. just 1 slow sender, and d a m a g e was done to not only

58 5th Symposium on Operating Systems Design and Implementation USENIX Association

 ypserv-2.2 ypserv-l.3 log-in. Since group is usually a very small database, it
rpcinfo ypcat rpcinfo ypcat
I slow sender No No No No is not vulnerable to a y p c a t attack. Generally, we do
1 slow reader No No Yes Yes not want to let y p c a t attacks on large databases affect
40 slow readers No No Yes No access to small databases. Since there are usually only
a small number of databases on a NIS server, we can
Table 3: Server Availability under Slow ypcat attacks solve this problem by associating a "dynamic" service
for each type of operation on each database, so that
" y p c a t g r o u p " and " y p c a t passwd" belong to sepa-
T C P but U D P services as well. The reason is t h a t rate services. To support dynamic service, we need to
s v c _ r u n essentially implements a poll loop as in Flash, add one new primitive, DYN_SERVICE.ADMISSION(svc_
but using synchronous I/O. When d a t a arrives on a i d , m i n _ r a t e ) , which is same as SERVICE_ADMISSION
registered channel, the R P C library tries to decode the except it takes an extra p a r a m e t e r svc_id for service
request message. If the request message is sent slowly, id.
tile m a i n server process blocks on a r e a d system call
until the entire message arrives. During this time, the
server is unable to reply to new requests. Tile con- 7 Limitations
currency, however, does help the server survive slow Our approach has several limitations. First, in m a n y
reader attacks, as they are handled by children pro- cases our approach limits only the scope of d a m a g e be-
cesses. W h e n the number of slow readers reaches the cause it cannot distinguish between "good" and "bad"
limit, y p c a t starts to fail, but the main process contin- requests t h a t happen to follow the same code path.
ues to respond to r p c i n f o and other YP clients such In other words, annotations simply augment the clas-
as ypmat ch. sification mechanisms already embedded in the code;
We found t h a t merely annotating ypserv does not they do not add any new ones of their own. To further
give us resilience to Slow T C P attack because the ac- differentiate between "good" requests and "bad" re-
tivities we would like to monitor actually occur in- quests, additional classification mechanisms must be
side the R P C library rather t h a n the application. added to the program so t h a t these requests effec-
Therefore, we really need to annotate the R P C li- tively follow different code paths. For cases where sep-
brary. However, the effectiveness of doing so is ham- arating services according code paths is not fine-grain
pered by the library's use of synchronous I / O . We enough, as we saw in the experiment on the NIS server,
suggest t h a t a more robust R P C library implementa- we believe t h a t adding DYN_SE1WICE_ADHISSlONto the
tion should employ the architecture of the Flash web toolkit will be necessary. We are currently extending
server, in which (1) low-level stub functions are pro- the toolkit to support such a facility.
cessed in non-blocking handlers, and (2) user applica- Second, the current toolkit is only applicable within
tions like y p s e r v are invoked as helper processes. If a single process because the sensors and actuators need
these changes were made, our annotation toolkit would to share state, and thus, they work only within a single
effectively protect the R P C library. m e m o r y space. This means our toolkit will not work
with the current implementation of Apache, for exam-
6.3.2 Busy Attacks ple. It is not clear that an I P C facility can help extend
There is an easy way to busy a t t a c k a ypserv-2.2 the mechanism to multi-process programs because I P C
NIS server when there is a big database: simply in- overhead will likely hinder fine-grain protection. How-
voke m a n y " y p c a t < b i g d a t a b a s e > " simultaneously ever, for multi-process programs, it is also possible to
to ask the service to send the whole database over apply the protection separately for each process. We
network. For a database of size 1.7MB, it takes a b o u t need more experience to say how effective t h a t will be.
20 ms for server to complete the transmission, during Third, rate-limiting controls only the quantity of re-
which the server does not process any other requests sources consumed by each service, but not the order
because of R P C ' s mutual exclusion property. Attack- t h a t resources are consumed. Sometimes it is desir-
ing a NIS server with y p c a t flood virtually blocks all able to change the order t h a t we allocate resources,
NIS operations using TCP, e.g. r p c i n f o . Operations especially when some resource consumers are latency-
t h a t use UDP still go through because they are in a sensitive. For example, in addition to specifying a rate
different queue than T C P in s e l e c t ( ) . for all n o n - T C P packets, we m a y want to b u m p T C P
We a n n o t a t e d the NIS server by wrapping each NIS packets to the front of the transmission queue. Not
operation as a service so t h a t YP_ALL requests (sent being able to schedule resource sometimes forces the
by y p c a t ) will not consume all the resources. An an- user to be more conservative in specifying resource lim-
n o t a t e d NIS server continues to respond to other Y P its. To be able to schedule resource allocation would
requests under a y p c a t attack, except access to YP_ALL require support for concurrency within a process, so
is very slow. However, this is not satisfactory because t h a t the program execution can save the state of the
YP_ALL access to database group is required for each current service task and switch to another service.

USENIX Association 5th Symposium on OperatingSystems Design and Implementation 59

 8 Conclusions of the Fourth USENiX Symposium on Operating System
Deszgn and Implementation (OSDI), October 2000.
This paper presents defensive programming as a new [5] D. Engler, D. Y. Chen, S. Hallem, A. Chou, and B. Chelf.
approach to offer proactive DoS attack protection. Af- Bugs as Deviant Behavior: A General Approach to
ter first identif}'ing two basic types of DoS attacks Inferring Errors in Systems Code. In Proceedings of the
busy and claim-and-hold--we build a toolkit that pro- 18th ACM Symposium on Operating Systems Principles,
October 2001.
vides an interface programmers use to annotate their [6] S. Forrest, S. A. Hofineyr, A. Somayaji, and T. A.
code. With compiler assistance, annotations are trans- Longstafl'. A Sense of Self for Unix Processes. In
lated into runtime sensors and actuators that watch for Proceedings of the 1996 IEEE Symposium on Corr~puter
resource abuse and take the appropriate action should Security and Privacy, May 1996.
[7] K. Kendall. A Database of Computer Attacks for the
abuse be detected. The main strengths of this ap- Evaluation of Intrusion Detection Systems. Master
proach are that it offers fine-grained intra-process pro- Thesis, MIT, June 1999.
tection, can be systematically applied to existing code, [8] Linux NIS(YP) Server. [Link]
protects software fi'om unknown attacks, and puts a [9] D. Mosberger and L. L. Peterson. Making Paths Explicit
minimal burden on the programmer. in the Scout Operating System. In Proceedings of the
Second USENIX Symposium on Operating System Design
Like any mechanism, however, the effectiveness of and Implerr~entatior~ (OSDI), pages 153-167, October
our approach depends on whether a good defensive 1996.
policy can be specified, which is the responsibility of [10] V. Pal, P. Druschel, and W. Zwaenepoel. Flash: An
the programmer. Our experience with DoS attacks Efficient and Portable Web Server. In Proceedings of the
USENIX '99 Annual Technical Conference, June 1999.
and applications has greatly influenced the design of
[11] S. E. Perl and W. E. Weihl. Performance assertion
the annotation interface in order to accommodate the checking. In Proceedings of the l~th ACM Symposium on
most common policies, but the interface is by no means Operating Systems Principles, pages 134-145, December
complete. Also, even with the help of our toolkit, non- 1993.
trivial programming effort is still required: (1) pro- [12] S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and
T. Anderson. Eraser: A Dynmnic Data Race Detector for
grammers need to mark service entry points and iden- Multithreaded Programs. A CM Transactions on
tify where their programs acquire/release/consume re- Computer Systems, 15(4):391-411, 1997.
sources, and (2) system administrators need to set [13] C. L. Schuba, I. V. Krsul, M. O. Kuhn, E. H. Spafford,
system-dependent parameters (e.g., rate limits). Our A. Sundaram, and D. Zamboni. Analysis of a Denial of
Service Attack on TCP. In Proceedings of the 1997 IEEE
view is that just as progranmmrs are responsible for Symposium on Computer Security and Privacy, May
making their programs correct, they should also be 1997.
responsible for making them defensive; we merely pro- [14] A. Somayaji and S. Forrest. Automated Response Using
vide a set of tools to help simplify this task. Prelim- System-Call Delays. In Proceedings of the 9th USENIX
Security Symposium, August 2000.
inary experience suggests that the programming bur-
[15] O. Spatscheck and L. L. Peterson. Defending Against
den is modest, but we expect to extend and refine the Denial of Service Attacks in Scout. In Proceedings of the
tools as we gain more experience. Third USENIX Symposium on Operating System Design
and Implementation (OSDI), Februray 1999.
[16] R. Srinivasan. RPC: Remote Procedure Call Protocol
Acknowledgments Specification Version 2. Request for Comments (RFC)
We would like to thank the anonymous reviewers and 1831, August 1995.
Greg Ganger, our shepherd, for helping us improve [17] C. Villamizar, R. Chandra, and R. Govindan. BGP Route
Flap Damping. Request for Comments (RFC) 2439 ,
the clarity and focus of the paper. This work was November 1998.
supported in part by NSF grant ANI-9906704, DARPA [18] D. Wagner and D. Dean. Intrusion Detection via Static
contract F30602-00-2-0561, and Intel Corporation. Analysis. In Proceedings of the 2001 IEEE Symposium on
Computer Security and Privacy, May 2001.
[19] M. Welsh, D. Culler, and E. Brewer. SEDA: An
9 REFERENCES Architecture for Well-Conditioned, Scalable Internet
[1] D. Andersen, D. Bansal, D. Curtis, S. Seshan, and Services. In Proceedings of the 18th ACM Symposium on
H. Balakrishnan. System Support for Bandwidth Operating Systems Principles, October 2001.
Management and Content Adaptation in Internet
Applications. In Proceedings of the Fourth USENIX
Symposium on Operating System Design and
Implementation (OSDI), Februray 2000.
[2] Apache Software Foundation. Apache Web Server.
[Link]
[3] G. Bangs, P. Druschel, and J. C. Mogul. Resource
Containers: A New Facility for Resource Management in
Server Systems. In Proceedings of the Third USENIX
Symposium on Operating System Design and
Implementation (OSDI), Februray 1999.
[4] D. Engler, B. Chelf, A. Chou, and S. Hallem. Checking
System Rules Using System-Specific,
Programmer-Written Compiler Extensions. In Proceedings

60 5th Symposium on Operating Systems Design and Implementation USENIX Association