Week 1 Exercises

Welcome to CS 110L! We’re so glad you’re here.

Purpose

This week’s exercises are designed to help you get familiar with common C/C++ program analysis tools. Static and dynamic analyzers are extremely helpful, but they have major limitations and excel in different ways. These exercises will help you get a feel for the kind of errors that analyzers can detect, as well as those that are harder to find.

Confused? Have questions? We’d love to chat! You’re encouraged to discuss on Slack if you get stuck or are curious about the capabilities of these tools.

Due date: Thursday, April 8, 11:59pm (Pacific time)

This assignment should take 1-3 hours to complete.

Part 1: Getting oriented

In this assignment, we’ll be analyzing a few different programs. You can download the source code here, or, if you are working on myth, you can download it using the command line:

wget https://web.stanford.edu/class/cs110l/assignments/week-1-exercises/week1.zip
unzip week1.zip

You don’t need to write any code for this assignment, but we’ll have you write up some brief comments about what you find in your investigation. You’ll need to submit a PDF on Gradescope.

The myth machines already have the tools we will be using in this assignment, but if you would prefer to work on your own computer, it’s not hard to install them. You’ll need to install Valgrind and a recent version of LLVM (version 10 or newer) that includes clang-tidy and sanitizers. (If you’re on Mac, the default installation does not include the sanitizers we will be using, but you can install an alternate version using brew.)

Program 1: UPPERCASe

Our first target will be a simple program that takes a string as a command-line argument and prints that string uppercased:

🍉  ./uppercase "hello world"
HELLO WORLD

This program copies the input string into a mutable buffer, then replaces each lowercase character with its uppercased sibling. Unfortunately, the programmer who wrote this program forgot that strings have a null terminator at the end, and the buffer intended to hold the uppercase string is too small.

Give the code a quick read to make sure you understand the problem. Then, let’s try running some automated tools to see what they find!

Side note: You’ll need to write code sort of like this for Assignment 2 in CS 110 (not to uppercase the string, but to tokenize it into multiple pieces). Be sure to avoid making this same (common) mistake :)

Static analysis

This problem will manifest no matter what input you provide, and it’s one that an experienced programmer can easily find. How does clang-tidy fare?

clang-tidy is pretty easy to run. Give it a spin:

🍉  clang-tidy 1-uppercase.c
Error while trying to load a compilation database:
Could not auto-detect compilation database for file "1-uppercase.c"
No compilation database found in /afs/.ir/users/r/e/rebs/static-analyzer-test or any parent directory
fixed-compilation-database: Error while opening fixed database: No such file or directory
json-compilation-database: Error while opening JSON database: No such file or directory
Running without flags.

Based on what you know from lecture, why might clang-tidy not see this problem? (There is no one correct answer we’re looking for here. Just speculate.)

Dynamic analysis with Valgrind

Let’s see if Valgrind does any better. First, we need to make sure you’ve compiled the program. Then, run it under Valgrind:

🍉  make
🍉  valgrind ./1-uppercase "hello world"
==649566== Memcheck, a memory error detector
==649566== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==649566== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==649566== Command: ./1-uppercase hello\ world
==649566==
HELLO WORLD
==649566==
==649566== HEAP SUMMARY:
==649566==     in use at exit: 0 bytes in 0 blocks
==649566==   total heap usage: 1 allocs, 1 frees, 1,024 bytes allocated
==649566==
==649566== All heap blocks were freed -- no leaks are possible
==649566==
==649566== For lists of detected and suppressed errors, rerun with: -s
==649566== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Uh oh… Valgrind thinks we’re in the clear as well. Based on what you know from lecture, why does Valgrind fail us here?

Dynamic analysis with sanitizers

Recall that Valgrind does “binary instrumentation”: you give it a fully compiled binary, and it injects extra assembly code that helps it observe every time a program accesses/allocates/frees memory.

By contrast, LLVM sanitizers do “source instrumentation”: you give it source code, and it injects extra code that keeps track of memory accesses. Then, it compiles that modified source code into a binary that has these extra checks in place. Since this source instrumentation is actually part of the compilation process, we need to modify the way we run our compiler in order to use sanitizers.

This may sound intimidating, but it’s actually pretty simple. Normally, we can compile a .c file into a binary by running a command such as this:

clang -g -O0 1-uppercase.c -o 1-uppercase

(Translation: with debugging enabled (-g) and compiler optimizations turned off (-O0), compile 1-uppercase.c into the executable 1-uppercase.)

To inject sanitizers into our code, we can simply tell the compiler which sanitizers we’d like to run using the -fsanitize flag:

clang -g -O0 -fsanitize=address,leak,undefined 1-uppercase.c -o 1-uppercase

If you run this command, it will produce a 1-uppercase binary that you can run. The compiler has injected the sanitizers into your code, so they have also been compiled into this binary; when you run the binary, the sanitizers will run as well, keeping tabs on what your program is doing.

However, most people don’t compile their projects by running clang directly. You need to run the compiler on each individual source code file, and since most projects have many files (tens to millions), that would be far too cumbersome. Instead, we rely on build systems: we tell the build system what files make up our programs, and the build system puts together all the right compiler commands for us. Since this assignment is focused on tooling, we thought it might be apt to give you some more insight into how your existing tooling works and how you can modify it to add assurance checks for your code.

`make` crash course

make is the build system that we use in CS 110. When you run make, it searches for a Makefile that specifies how you want to run the compiler; then, it runs all the relevant commands for you:

🍉  make
/usr/bin/clang-10 -g -O0 -Wall -Wextra -std=c11   -c -o 1-uppercase.o 1-uppercase.c
/usr/bin/clang-10 1-uppercase.o  -o 1-uppercase

Side note: In this case, we’ve actually opted to split the compilation process into two commands: a first step that compiles the .c file into a .o “object file,” and a second “linker” step that assembles the .o file into a binary. This is unnecessary in our specific case, because our simple program is compiled from only one file. However, most programs are built from many separate files; each file needs to first be compiled into a .o file, and then all the .o files are combined into the final program. Because this is how your CS 110 programs are, we have written this Makefile in that way.

Let’s take a look at the Makefile to see how it is structured.

The first half of a Makefile typically declares variables. You can define any variables you like, although there are some with special names that have specific meanings. For example, CC and CXX specify the C and C++ compilers that make will use. CFLAGS and CXXFLAGS specify command-line arguments that should be passed to the C and C++ compilers, respectively. LDFLAGS specifies flags that should be passed to the linker (i.e. the second command that combines .o files into a binary).

The second half of a Makefile defines targets, which can be invoked by running make <target name>. For example, this is the definition of the clean target:

clean::
	rm -fr $(C_PROGS) $(C_PROGS_OBJ)
	rm -fr $(CXX_PROGS) $(CXX_PROGS_OBJ)

Because of this, when you run make clean, Make will run the rm commands specified above.

Additionally, targets can be run by other targets. When you run make (with no extra arguments), it will run the default target:

default: $(PROGS)

The PROGS variable will be expanded into default: 1-uppercase 2-linkedlist 3-bracket-parser 4-fibonacci, so make will then run the 1-uppercase, 2-linkedlist, and 3-bracket-parser targets, and so on.

Looking at this you might think: wait, but I don’t see a 1-uppercase target defined anywhere! This target is actually defined here:

$(C_PROGS): %:%.o
	$(CC) $^ $(LDFLAGS) -o $@

This is expanded into a bunch of targets, one for every string in the C_PROGS variable. Expanded, they look like this:

1-uppercase: 1-uppercase.o
	$(CC) $^ $(LDFLAGS) -o 1-uppercase

(If you’re curious, see the Makefile documentation about pattern rules.)

This says, “first, run the 1-uppercase.o target. Then, run the compiler with the provided $(CC) command (which is the linker command).”

Wait, I don’t see a 1-uppercase.o target either!!! This one is even more confusing, because it’s an implicit target that is built into make. Long story short, it will automatically compile 1-uppercase.o from 1-uppercase.c using your CC and CFLAGS variables.

This long and confusing sequence of targets generates and runs these two compiler commands:

/usr/bin/clang-10 -g -O0 -Wall -Wextra -std=c11   -c -o 1-uppercase.o 1-uppercase.c
/usr/bin/clang-10 1-uppercase.o  -o 1-uppercase

And, if you have many programs in C_PROGS and CXX_PROGS, it will generate the appropriate commands for all of them.

Note: Makefiles are really arcane and confusing, and there have been many attempts to build modern replacements, but they’re still often used because they work, and you can copy/paste a Makefile from one project and tweak a few things for your new project until it does what you want it to (without understanding the whole thing). That’s mostly what we’re doing here, but we wanted you to have some basic insight into how they’re structured.

Updating your Makefile to enable sanitizers

Recall that the compiler and linker flags are controlled by the CFLAGS, CXXFLAGS, and LDFLAGS variables. To tell the compiler to inject AddressSanitizer, LeakSanitizer, and UndefinedBehaviorSanitizer into our programs, we simply need to add -fsanitize=address,leak,undefined to each of those three variables in our Makefile. Then, every time make runs the compiler, it will include that flag.

Recompile and run

With the Makefile updated, we can recompile and rerun (don’t forget to make clean):

🍉  make clean
rm -fr 1-uppercase 1-uppercase.o
rm -fr
🍉  make
/usr/bin/clang-10 -g -O0 -Wall -Wextra -std=c11 -fsanitize=address,leak,undefined   -c -o 1-uppercase.o 1-uppercase.c
/usr/bin/clang-10 1-uppercase.o -fsanitize=address,leak,undefined -o 1-uppercase
🍉  ./1-uppercase "hello world"
=================================================================
==655208==ERROR: AddressSanitizer: dynamic-stack-buffer-overflow on address 0x7ffda54e74eb at pc 0x0000004c32dc bp 0x7ffda54e7420 sp 0x7ffda54e7418

Question for you

Based on our discussions in lecture, how does AddressSanitizer find this error?

Comments

It is common to compile debug builds with sanitizers enabled. That way, you don’t need to go out of your way to test that your program doesn’t have memory errors (e.g. by separately running valgrind ./myprogram); every time you run it, the sanitizers will already be checking for you. However, sanitizers do slow your program down, so they are not included in release builds (i.e. versions of your program for others to use).

If you feel like trying sanitizers out on your CS 110 assignments, we’d love to hear how it goes! Later in the course, you won’t be doing much manual memory management, but there still may be a few things that the sanitizers catch. When you start writing multithreaded code, ThreadSanitizer will be very helpful.

Program 2: Linked~~~Lists–

Take a look at 2-linkedlist.c. This program creates a basic linked list with 20 elements. Then, it goes to the middle of the list and replaces the 10th node with a different one. Finally, it prints the list and frees all the elements.

There are at least two bugs in this program:

When replacing the 10th node, it removes an element from the list but does not free it, hence leaking memory.
At the end, when iterating over the list to print the values and free the nodes, the while condition is wrong. As written, it doesn’t print or free the last element of the list. (The condition should be while (curr != NULL))

Static analysis

Try running clang-tidy on this program. What do you find?

clang-tidy 2-linkedlist.c

I’m using clang-tidy from LLVM 10 (you can check the version by running clang-tidy -v), and at least in this version, clang-tidy reports a false positive about some dereference of a null pointer. That’s not actually possible in this program. Also, clang-tidy does not catch either memory leak.

Based on our discussions in class, speculate about what might be happening here. (There is no right answer that we are looking for.)

Interestingly, if you add const to kNumElements (it is declared as a global variable, even though it really should be a constant), the false positive goes away. Feel free to speculate about why, although this is optional. (It still does not catch the memory leaks.)

Dynamic analysis

Let’s try running the sanitizers on this example! (No need to run Valgrind for this program.)

Your Makefile modifications for Program 1 should mean that Program 2 was also compiled with sanitizers included. If so, you can simply run the program:

./2-linkedlist

What do you find?

Program 3: Parsing and Early Returns

Take a look at 3-bracket-parser.c. This program takes a string formatted like "abcd[efg]hij" as an argument and prints out the portion of the string in brackets. For example:

🍉  ./3-bracket-parser 'hi [hello world]!'
Parsed string: hello world

However, this program has a very common error: it allocates resources at the beginning of the parse function, but fails to free the allocated memory if an error occurs (in this case, if a close ] is not found).

Static analysis

You know the drill! Let’s try running clang-tidy:

clang-tidy ./3-bracket-parser.c

What do you find?

Dynamic analysis

Let’s try running sanitizers, which should already be baked into the program from your work in Program 1:

./3-bracket-parser 'hi [hello world]!'

Do the sanitizers catch any problems? Why or why not?

Fuzzing

Recall that a “fuzzer” feeds a program with many semi-random inputs, aiming to find unusual inputs that trigger badly-behaved edge cases.

Let’s see if we can use a fuzzer to discover our bug. The two most common general-purpose fuzzers are AFL and libFuzzer. In this exercise, we’ll give libFuzzer a spin.

libFuzzer is built into LLVM/clang and injects extra code into your program similar to how the sanitizers work. libFuzzer will call a function in your program, providing you with some semi-random input; you can then pass that input to the code you want to fuzz.

Let’s see how this works.

Adding the fuzz target

First, add this function to 3-bracket-parser.c:

int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
    // TODO: do something with `data` and `size`

    // libFuzzer functions always return 0
    return 0;
}

When we compile with libFuzzer, the fuzzer will dream up a strange input and pass a buffer/size containing this data to LLVMFuzzerTestOneInput. We can then manipulate this input and pass it to the part of our code that we are trying to fuzz.

In our case, we want to test our parse function. This function takes a null-terminated C string. Let’s transform libFuzzer’s input (which is just a buffer of arbitrary bytes) into a C string. First, allocate a buffer with enough space to fit the libFuzzer input plus a null terminator:

char buf[size + 1];

Next, copy the input into the buffer:

memcpy(buf, data, size);

Finally, null-terminate the string:

buf[size] = '\0';

Now, buf contains a null-terminated string. Call parse on this string, and your fuzz target is complete!

One last change: libFuzzer will inject its own main function into your code, which starts the fuzzer (i.e. starts generating inputs and passing them to LLVMFuzzerTestOneInput). As such, you will need to comment out our main function, so that the two do not conflict.

Compiling with fuzzing enabled

To compile libFuzzer into our code, we simply add fuzzer to the list of sanitizers:

-fsanitize=fuzzer,address,leak,undefined

Doing this in the Makefile will cause problems because our Makefile is compiling several different programs, and we only set up one of them for fuzzing. Because our program is pretty simple, let’s just compile it directly without using make:

clang-10 -g -O0 -Wall -Wextra -std=gnu99 -fsanitize=fuzzer,address,leak,undefined -o 3-bracket-parser 3-bracket-parser.c

(If you are not running on myth, you may need to replace clang-10 with whatever compiler you have installed.)

Running the fuzzer

Once everything is compiled, simply run the binary to start the fuzzer:

./3-bracket-parser

It shouldn’t take long for the fuzzer to find the memory leak. Take a look at the second to last line, which should say something like “Test unit written to ./leak-somelongstring.” You can cat that file to view the input that libFuzzer found to cause your problem. In my case, the input was \n[j, although it’s likely to change each time you run the fuzzer.

Question for you

What input did your fuzzer generate?

Comments

Our parser is extremely simple and you could identify a problematic test case by hand, but parser code is known for being complicated, and there are many parsers with complex webs of if and switch statements and loops that are too hard to analyze by hand. Fuzzers are invaluable for analyzing these programs and have uncovered countless critical bugs in production software.

“This Man Thought Opening a TXT File is Fine. He Thought Wrong” is a fascinating writeup of a bug in MacOS TextEdit that allowed an attacker to steal arbitrary files via a simple .txt file. Fuzzing played a key role in discovering this vulnerability. (While fuzzing is usually used to figure out how to trigger memory errors in program, this researcher used it to figure out how to get TextEdit to send him information through a network request.)

Program 4: Fibonacci

Take a look at 4-fibonacci.cpp. This program has correctness problems. (For reference, the fibonacci sequence should be 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …)

Does clang-tidy find any problems with this file? What about the sanitizers? Why do you think this might be?

Part 5: Weekly survey

As you know, this is still an experimental class, and we want to make it as enjoyable and meaningful of an experience as possible. Please let us know how you’re doing using this survey.

When you have submitted the survey, you should see a password. Include this code in your writeup when submitting.

Submitting your work

Please submit a PDF writeup of your work on Gradescope.

There are five parts to this assignment, each worth 20%. You’ll earn the full 20% for each part if we can see that you’ve made a good-faith effort to complete it.

CS 110L

Week 1 Exercises

Purpose

Part 1: Getting oriented

Program 1: UPPERCASe

Static analysis

Dynamic analysis with Valgrind

Dynamic analysis with sanitizers

make crash course

Updating your Makefile to enable sanitizers

Recompile and run

Question for you

Comments

Program 2: Linked~~~Lists–

Static analysis

Dynamic analysis

Program 3: Parsing and Early Returns

Static analysis

Dynamic analysis

Fuzzing

Adding the fuzz target

Compiling with fuzzing enabled

Running the fuzzer

Question for you

Comments

Program 4: Fibonacci

Part 5: Weekly survey

Submitting your work

`make` crash course