====== Lab 4 ======
===== Handin Procedure =====
When you are finished, edit the ''answers.txt'' file and add your name(s) and email
address(es), student ID(s), any challenge problems you may have done, and
any other information you'd like us to have. **You must also include an
example URL that crashed the original ''ospweb'' with a buffer overflow.**
Then run ''make tarball'', which will generate a file ''lab4-//yourusername//.tar.gz''
inside the lab4 directory. Upload this file to CourseWeb using a web
browser to turn in the project.
===== Overview =====
This lab concerns the subjects of networking and security. We give you a
simple web server that can handle one connection at a time. You'll change
that server to handle "CGI scripts" (dynamic web serving), multiple concurrent connections, using the method of
//event-driven programming//. Then you'll patch a couple security holes in
our server.
This lab can be completed on any Unix-compatible machine, including the
SEASnet Solaris machines, the Linux lab machines, and Macintosh machines.
An HTTP (web) server serves web clients with files. HTTP clients use the
TCP transport protocol to contact web servers and request content. The
client opens a TCP connection to the server, and transmits a HTTP request
header that specifies the requested content. The web server reads the
request, locates the file requested by the client on the local file system
and responds to the client with the requested file.
Typing ''gmake'' (on some Linux distributions, just plain ''make'') in this
directory will build the programs ''ospweb'', ''cgi-bin/slow'',
''cgi-bin/poem'' and ''slowget''. The ''ospweb'' program is a simple Web
server. The version we hand out can serve at most one connection at a
time. To give it a try, run
$ gmake && ./ospweb
and then point a Web browser at this URL:
http://localhost:8000/
You should see a friendly greeting. The server will serve any other file
in the lab4 directory, too. If you are using your own Linux machine, and
you can't get the page to load, you may have a firewall enabled which you
can often disable until the next reboot by running this command as root:
# /sbin/iptables -F
===== CGI programming =====
"CGI", or "Common Gateway Interface", was the first standard that let
external programs handle some of a web server's requests. CGI is a very
simple interface. The web server starts a process to handle the request,
reads that process's standard output, and writes the output to the client's
network connection. What could be simpler? Why, you've done something
very similar to this already, in Lab 1!
''ospweb'' implements a variant of CGI. A URL like
http://localhost:8000/cgi-bin/slow?pokercats.gif
should cause the server to run the command "slow" with the arguments "slow
pokercats.gif". Your first job is to make this happen. Use the system
calls ''fork'', ''dup2'', ''close'', and ''execvp'', just like in Lab 1.
Test your code by accessing the following URL:
http://localhost:8000/cgi-bin/poem?99
You should see a poem of sorts.
===== Serving Concurrent Connections =====
The ''slow'' CGI program will make it very clear that the current server
processes at most 1 connection at a time. First, run this command at the
shell prompt:
$ cgi-bin/slow ospweb.c
See what happens? ''slow'' prints a file v-e-r-y s-l-o-w-l-y, making it easy
for you to evaluate concurrency. Now try this URL with a browser:
http://localhost:8000/cgi-bin/slow?pokercats.gif
and watch the cats show up v-e-r-y s-l-o-w-l-y. (Some browsers, such as
Mac OS X Safari, may not show the cats at all until they are complete!)
While you're waiting for the cats, open another browser window and access
"http://localhost:8000/hello.txt" again. Notice that it doesn't come up
//at all// until the pokercats are done. Your job is to fix this: to make it
so that ''hello.txt'' isn't slowed down by ''cgi-bin/slow?pokercats.gif''.
===== Event-Driven Programming =====
The conventional way to serve multiple connections simultaneously is simply
to fork: to serve each connection from a different process or thread. You
may have done this already in CS 118. The Apache web server uses a forking
model. Each Apache server process can handle one request at a time; in
order to handle concurrent requests, Apache forks a number of "spare
server" processes, to which it forwards requests. Performance isn't as bad
as it could be, since the spare servers are kept around (rather than forked
off on every request).
Multi-process servers have real problems, however. The multiple processes
have significant overhead. Since the processes are isolated, it is
difficult for them to share resources, such as a cache of recently-accessed
pages. Some of these problems can be mitigated by using threads instead of
processes, but that introduces synchronization issues.
In this lab, you will implement an operating system-like solution: make
this server serve multiple simultaneous connections using **nonblocking
I/O** and **event-driven programming**. All of the programming methods
have their advantages and disadvantages, but since event-driven programming
often requires less resources, it is used for the fasted servers out there.
In event-driven programming, all file descriptors are changed to use
non-blocking I/O instead of blocking I/O. This means that the server never
blocks because a file descriptor isn't ready; instead, the read or write --
whichever operation would have blocked -- will return immediately with an
error like ''EWOULDBLOCK''. The server can then skip any not-ready file
descriptors and move on to the next connection. The server blocks in only
one place, during a call to the ''poll()'' system call. ''poll()'' allows the
server to block until **any one of a set** of file descriptors becomes ready.
Event-driven programming introduces a couple of wrinkles.
* Event-driven programs must maintain application-level buffers of connection data. This is because the program might read a partial data item before it would block; the program must remember the partially-read data. A similar statement holds for writing.
* Event-driven programs tend to be broken into many small chunks, rather than large, easy-to-understand functions. This is because a single thread handles the processing of many connections ("cooperative multitasking"). To handle many tasks in one thread, it is easiest to break those tasks into separate functions and call each one when it is ready.
For example, here's some pseudocode for parsing the beginning of an HTTP
connection. The HTTP header is read from ''rfd'', and the response is
written to ''wfd''.
begin_connection(int rfd, int wfd) {
char header[BUFSIZ];
while (header is not complete)
read header from rfd; // might block
write response to wfd; // might block
}
In an event-driven program, we can't allow either ''read_header()'' or
''write_response()'' to block -- that would prevent other connections from
running! Our first, incorrect, attempt might look like this.
begin_connection_event(int rfd, int wfd) {
char header[BUFSIZ];
if (header is not complete) {
try to read header from rfd;
if (would block)
return;
}
try to write response to wfd;
if (would block)
return;
}
dispatch_loop() {
while (1) {
if (rfd or wfd is ready)
begin_connection_event(rfd, wfd);
}
}
This function detects cases that would block and returns early. When the
relevant file descriptor becomes ready again, a central dispatch loop will
call ''begin_connection_event()'' again so it can complete (or at least get
further along). This code is not correct, however. The ''header[]'' variable
is stored on the stack, so it will disappear when ''begin_connection_event()''
returns. But ''begin_connection_event()'' might return
before the header has been read! Real event-driven programs store buffer
variables like ''header[]'' on the //heap//, in a connection state object. For
example:
typedef struct connection {
char header[BUFSIZ];
int rfd;
int wfd;
} connection_t;
begin_connection_event(connection_t *conn) {
if (conn->header is not complete) {
try to read conn->header from conn->rfd;
if (would block)
return;
}
try to write response to conn->wfd;
if (would block)
return;
}
dispatch_loop() {
create conn;
while (1) {
for (each connection conn)
if (conn->rfd or conn->wfd is ready)
begin_connection_event(conn);
}
}
This is much better, since the ''conn->header'' variable persists across calls.
However, the dispatch loop will call ''begin_connection_event()'' too many
times. In the first phase, before ''conn->header'' is complete, the code
**never tries to write to ''conn->wfd''**. Therefore, it doesn't matter whether
or not ''conn->wfd'' is ready; we only care about ''conn->rfd''.
The fix for this is to separate the ''begin_connection_event()'' function into
multiple **states**, where different states wait on different collections of
events, or react differently to events. Each state corresponds to a single
**callback function**.
typedef struct connection {
char header[BUFSIZ];
int rfd;
int wfd;
int state;
} connection_t;
read_header_event(connection_t *conn) {
assert(conn->state == READ_HEADER);
try to read conn->header from conn->rfd;
if (conn->header is complete)
conn->state = WRITE_RESPONSE;
}
write_response_event(connection_t *conn) {
assert(conn->state == WRITE_RESPONSE);
try to write response to conn->wfd;
}
dispatch_loop() {
create conn, initial state is READ_HEADER;
while (1) {
for (each connection conn) {
if (conn->state == READ_HEADER
&& (conn->rfd ready for reading || error on conn->rfd))
read_header_event(conn);
else if (conn->state == WRITE_RESPONSE
&& (conn->wfd ready for writing || error on conn->wfd))
write_response_event(conn);
}
}
}
(The "error" cases are necessary in case the remote client closes the connection
prematurely. We assume that the ''read_header_event''/''write_response_event'' functions
will detect the error and do the right thing when they see the error; we just need to make
sure that in the main loop, we detect error states as well as "ready" states.)
The last step is to add a blocking step in the dispatch loop. This step
will block until any connection is ready. The relevant system call is
called poll. poll works by blocking on a list of file descriptors
(files, sockets, and so forth) and returns when at least one file
descriptor is ready: that is, when data arrives on a socket, or when a
socket becomes writable. The file descriptor list is represented by an
array of ''struct pollfd''s. The relevant fields are ''fd'', ''events'',
and ''revents'', and the relevant events are ''POLLIN'', ''POLLOUT'', and (sometimes) ''POLLHUP''.
See the ''poll'' man page for further details.
Poll-based operations are performed in the following manner:
* Add the file descriptors from which you want to read or write to the ''struct pollfd'' array and set the ''POLLIN'' and/or ''POLLOUT'' events.
* Call ''poll()'', passing the ''struct pollfd'' array, the number of elements in the array, and a timeout.
* Check to see which file descriptors are available by inspecting the ''revents'' field of each ''pollfd'' and call the relevant callback functions.
* Repeat.
NOTE: Since your program blocks when there is no work to do, your
program SHOULD NOT use all CPU time while idle or serving files.
The program ''top'' may be helpful here; top shows running processes
and the percent time each is using.
Event-driven programming is more complex than a threaded version, but has
several important advantages.
- Since the entire server is cooperatively scheduled, there are no synchronization issues! No locks, no nothing.
- This code uses very little resources and will perform well.
- Embedded system programming, device driver programming, and so forth must generally use an event-driven style since threads are not supported.
===== Event-Driven Programming Exercises =====
Turn ''ospweb.c'' into an event-driven program that supports multiple
simultaneous connections. Much of the work has already been done for you;
for example, ospweb already keeps track of connection states. Your job
is mostly to write the dispatch loop. See the instructions in ''ospweb.c''.
All the event-driven programming exercises are labeled with ''EXERCISE''.
You may also find the state transition diagram for ospweb helpful; it is
in the image file ''states.png'' (which you can view using a web browser and
ospweb!).
**How to test.** Run the program ''top'' in a terminal window. This shows
you a list of different programs on your system, and shows how much CPU
time each program is taking up. Your job is to make ''ospweb'' serve
multiple files in parallel **without** taking up all the CPU time. In
particular, ''ospweb'' should //not// show 99-100% CPU usage, and should
//not// stay at the top of the ''top'' process list.
To test this, it might be tempting to download two copies of the same file
in parallel, but this will not work. Most browsers will load only one at a
time. Instead, try downloading two DIFFERENT files in parallel, in two
different browser windows, such as:
http://localhost:8000/cgi-bin/slow?ospweb.c
http://localhost:8000/cgi-bin/slow?pokercats.gif
The ''poem'' program generates a large, text-based webpage to help detect
blocking ospweb code. To generate 99 lines of text visit this URL:
http://localhost:8000/cgi-bin/poem?99
Once you have ''ospweb'' working for slow CGI scripts, make sure it also
works for slow //clients//. The ''slowget'' program gets files via HTTP,
reading very slowly to help detect blocking code. To get the above URL:
$ ./slowget -r /cgi-bin/poem?99
''slowget'' defaults to adding a short pause while sending the HTTP request
and slowly reading the HTTP response. Further information is available
by running ''./slowget -h''.
===== Security and Defensive Programming =====
Writing server programs is difficult not just because of the need for
speed, but also because it is very important to avoid *security holes*.
These are programming mistakes that might allow an attacker to crash the
server, to cause it to misbehave, to trick it into doing something it
shouldn't, or even to gain access to the machine.
Your job is to find and fix the current ospweb's security holes related
to CGI programs and file access.
Here's what ospweb //should// do: its intended specification.
* ospweb serves files located in the directory in which it runs, as well as any subdirectories. Thus, if the user requests "http://localhost:8000/hello.txt", ospweb returns the ''hello.txt'' file in its current directory.
* ospweb **does not** serve files located in any other directory, unless they are accessible by a symbolic link.
* Requests such as "/cgi-bin/program?arg1&arg2&arg3" cause a program to be run. Specifically, ospweb creates a process running ''cgi-bin/program''. It passes the three arguments on the command line. The process's output is sent to the client.
* Only ''/cgi-bin/'' URLs should run a program, and they should run programs in the ''cgi-bin'' subdirectory.
How well does ospweb do? Not that well!
http://localhost:8000/hello.txt
=> works correctly
http://localhost:8000/etc/passwd
=> reports "No such file or directory" correctly
http://localhost:8000//etc/passwd
=> Returns the password file!!!
http://localhost:8000/cgi-bin/slow?hello.txt
=> works correctly
http://localhost:8000/cgi-bin/slow?/etc/passwd
=> Returns the password file!!!
http://localhost:8000/cgi-bin/echo?foo
=> reports "Can't execute" correctly
http://localhost:8000/echo?foo
=> Runs "echo foo" and returns the result!!!
http://localhost:8000/rm?-rf&.
=> DO NOT RUN THIS URL!!! IT WILL DELETE THE LAB FILES!!!
Furthermore, there is at least one way to construct a URL that will corrupt
ospweb's memory, causing a segmentation fault or -- worse -- giving the
attacker control over the ospweb process! (This buffer overflow bug has
to do with CGI script handling.) While the buffer overflow bug would not
happen in a safe language like Java, the other bugs can happen in **any**
language. It is important for you to understand the need for careful
programming in any server environment like this.
Your job is to solve the following problems:
* ospweb should not serve files outside the current directory. (Change ''ospweb.c'''s ''ospweb_prepare_header'' function.)
* ospweb should not run binaries outside the cgi-bin directory. (Change ''ospweb.c'''s ''ospweb_prepare_cgi'' function.)
* The "slow" cgi-bin script should not provide access to files outside the current directory. (Change ''slow.c'''s main function.)
* The buffer overflow bug should be fixed. (Change ''ospweb.c'''s ''ospweb_prepare_cgi'' function.) You must also supply an example URL that would have triggered this bug; put it in your LAB file.
If you find other problems, feel free to solve them too, and tell us about
them.
Good luck!!!
===== Design Problems =====
[[design|On design problems]]
==== Threaded Server ====
Design a way to turn ''ospweb'' into a threaded server, rather than an
event-driven server. Your new ''ospweb'' should start a new thread per
connection. When the thread is done with its connection, it should exit.
Use the pthreads library to create new threads, and make sure you use the
pthread synchronization functions, such as ''pthread_mutex_lock'' and
''pthread_mutex_unlock'', when appropriate. (Where will it be
appropriate?) Also, design a way to measure the threaded server's
performance in some meaningful way. Would you expect it to be better or
worse than the event-driven server? And by how much?
==== Access Control ====
The ''ospweb'' server is happy to serve clients any data contained in the
''ospweb'' directory. Real servers allow users to specify which files in a
directory can be served. For example, this syntax tells Apache to refuse
to serve the ''ospweb.c'' file:
Order allow,deny
Deny from all
This syntax would usually go in a file called ''.htaccess'', in the
directory containing ''ospweb.c''.
Design an access control syntax for ''ospweb'' servers. Will you support
Apache-style ''.htaccess'' files, or something else? What type of syntax
will you support? How will you handle subdirectories? Check out Apache
for some ideas.
==== Authentication ====
Design a user authentication protocol for ''ospweb''. A user should not be
able to download //any// file from ''ospweb'' until they have "logged in"
with a user name and password. Some questions you will have to answer:
Where does the list of user names and passwords come from? Are passwords
sent in cleartext, or not? (It is much easier to do cleartext at first!)
How can ospweb remember that a particular user has logged in? (Valid
options are "cookies", http://www.cookiecentral.com/cm002.htm , tagging on
extra text to the URLs the user sees, and others.) When should a user's
"login session" expire?
==== Performance ====
Design a couple techniques to improve ''ospweb'''s performance, and discuss
how those techniques relate to optimizations we've discussed in class, such
as batching, dallying, speculation, and general interface design. Take a
look in particular at the ''epoll'' system call, and search on line for "file
descriptor passing". You may also be interested in [[http://www.cs.princeton.edu/~vivek/flash/|this work]].