Testing Memcached

Cloud9 can test distributed systems by simulating them using a program that forks multiple processes, which communicate through network sockets. In this case study, we test the memcached distributed in-memory object cache by modifying its testing harness to send symbolic packets. We'll use the most recent version of the code available at the moment of writing this tutorial. A similar setup was used to discover a security vulnerability in memcached (which was fixed in the mean time).

Building libevent

memcached requires libevent, so we first have to generate a static LLVM binary that we'll link into the final memcached executable.

Download libevent-2.0.19 and unpack it.
Enable the Cloud9 LLVM build toolchain in your terminal:

$ source $CLOUD9_ROOT/src/testing_targets/build/prepare_build_env.sh
Configure libevent:

$ ./configure --disable-shared --enable-static
Fix the generated config.h to disable all polling mechanisms, except for select:

$ $CLOUD9_ROOT/src/testing_targets/build/fix_autogen_conf config.h \
-u HAVE_EVENT_PORTS -u HAVE_WORKING_KQUEUE -u HAVE_EPOLL \
-u HAVE_DEVPOLL -u HAVE_POLL -d HAVE_SELECT
Build libevent:

$ make -j3

You should now have the .libs/libevent.a static LLVM library.

Building memcached

Building memcached using the LLVM toolchain is similar to building libevent. However, the original memcached code produces only the server executable. In order to test memcached with symbolic packets, we need to change the program entry point to fork both a server and a client. The modified memcached code (called memcached-llvm) can be found here, together with a change list.

Checkout memcached-llvm:

$ git clone https://github.com/dslab-epfl/memcached-llvm.git memcached-llvm
Configure memcached:

$ ./configure --disable-sasl --disable-docs --disable-dtrace --enable-64bit \ --disable-coverage --with-libevent=<libevent dir>/.libs

Replace <libevent dir> with the path of the libevent code. Also make sure that the LLVM build toolchain is still active in your terminal (a simple way to check that is to echo the value of the $CC variable).
Build the debug version of memcached (the release build doesn't work in the adapted version of the code):

$ make memcached-debug

You should now have the memcached-debug.bc LLVM binary.

Testing memcached

Running the Test Suite

The new memcached-debug.bc binary can run the original memcached test suite, minus a few test cases that involve the use of signals, which are not yet fully supported. So we simply need to run:

$ GLOG_logtostderr=1 c9-worker --stand-alone --posix-runtime memcached-debug.bc

You should see each test case being executed and passed. Note that the execution is linear - each test case is executed one after the other as a single path.

Running Symbolic Test Cases

We can now ask Cloud9 to inject symbolic packets into memcached, by running memcached-debug.bc with the --sym command line argument. This instructs the client to inject 2 symbolic packets instead of running the test suite (see here exactly how the symbolic packets are built):

$ GLOG_logtostderr=1 c9-worker --stand-alone --posix-runtime memcached-debug.bc --sym

Now memcached runs along multiple paths, since the execution forks inside the server code for each branch depending on the packet contents. Notice that most of the paths are erroneous -- the packet structure is invalid, so memcached terminates the connection.

Final Note

We mentioned earlier that the original memcached code produces only the server executable. So what happens if we ran the server directly? Let's assume that we download the original code, and build it using the procedure above. When we run the server using a command like:

$ c9-worker --stand-alone --posix-runtime memcached-debug.bc -v -p 11211 -U 0 -u root

we see that the memcached execution ends with an error message like ******** hang (possible deadlock?).

So why is this happening? It's very unlikely that memcached would hang or deadlock at initialization when we run it for real. However, in the context of symbolic execution, memcached runs in a "closed universe". The symbolic state contains only its process, and as soon as memcached initializes and starts listening for connections, no other thread or process exists to be scheduled. Cloud9 detects this as a "hang", since the system can no longer progress at that point.

Comments