You are expected to understand this. CS 111 Operating Systems Principles, Fall 2006
You are here: CS111: [[2006fall:lab4]]
 
 
 

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 pollfds. 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.

  1. Since the entire server is cooperatively scheduled, there are no synchronization issues! No locks, no nothing.
  2. This code uses very little resources and will perform well.
  3. 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

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:

   <Files "ospweb.c">
   Order allow,deny
   Deny from all
   </Files>

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 this work.

 
2006fall/lab4.txt · Last modified: 2006/11/28 13:26 (external edit)
 
Recent changes RSS feed Driven by DokuWiki