Skip to main content Link Menu Expand (external link) Document Search Copy Copied
6.5950/6.5951

C Crash Course Lab

Due Date: Feb 11; Last Updated Date: Feb 1

Table of Contents

Lab Details

Collaboration Policy

Our full Academic Honesty policy can be found on the Course Information page of our website. As a reminder, all 6.5950/6.5951 labs should be completed individually. You may discuss the lab at a high level with a classmate, but you may not work on code together or share any of your code.

Getting Started

This lab is done on the Unicorn server - you will receive an email with login instructions. This can also be solved locally through the provided Dockerfile.

We are using git for all the labs – instructions for setting up the git repository can be found on the labs page.

In addition to submitting code, you are required to submit a PDF lab report containing your answers to Discussion Questions to Gradescope.

Introduction

For the labs in this class, you will have to write a lot of C. This includes plenty of debugging too! Every year, we encounter many students who come to office hours due to a lack of understanding of basic C, so we decided to make this lab as a crash course.

In this lab, you will help fix the bugs of a basic note taking library. We will run it through a series of test cases to catch for bugs and functionality problems. While we don’t expect the lab to be trivial for most people, if you find yourself struggling significantly to get through this lab, you should consider if this course is fit for you. And please do not use LLMs to analyze shd-lib.c - later labs won’t be solveable through them. LLMs are perfectly fine though if you are rusty on C and need a crash course.

Setup

Please do the lab on the provided machines once available. This is important, because I have setup the tests to layout the process heap in a specific way to maximize the chances of catching specific bugs (and we will grade in this same environment)! For those who start before the machines are provisioned, feel free to use the provided docker-run.sh script and Dockerfile. You can also solve this lab locally (especially if you are on Ubuntu 22.04), but please do a final check on the provided machines!

First, clone the lab from git.

You can now modify shd-lib.c (and only this, we will ignore all other diffs during submission) and then run the tester binary. Note that your modifications only rebuild the library, which the tester uses. We do not provide the source for the tester or any debugging symbols on purpose - feel free to reverse engineer it, but it’s much pretty trivial to deduce the test cases from the library anyways. If you can reconstruct the tester binary to a reasonable degree and demonstrate so through a report with readable pseudo-C, we’ll give you full credit for this lab automatically.

Use make libshd-lib.so to rebuild the library, and then make run to run the tester (or ./tester). You can also run it with SANITIZED=1 make libshd-lib.so to build with ASAN and UBSAN (we will elaborate on this later on). You will need to use make sanitized-run for this version (or ./sanitized_tester), which has specifies the correct libraries to use for sanitizers.

The default Makefile rule runs the checks, which builds a sanitized version of libshd-lib.so. This means the library will only work with sanizited_tester and not tester. Run make libshd-lib.so to get a version that works with tester.

Finally, make check is what we will use for grading. There are many bugs that trigger silently (ie. no visible corruption), and we will use Valgrind to catch a subset of those.

Feel free to write your own tester binary as well and link it to libshd-lib.so. You can add a Makefile rule and call make <rule_name>. This can be good practice for writing more C! For example:

LDFLAGS = -L. -lshd-lib -Wl,-rpath=.

tester: custom.c libshd-lib.so
    $(CC) $(CFLAGS) custom.c -o tester $(LDFLAGS)

LLMs are really good for writing Makefiles too if you want to do some other setup.

Lastly, some tips for using Makefiles. The filenames appearing after a rule name are the dependencies - make re-runs a rule if the file which correlates to a rule name has an earlier modification timestamp than its dependent filenames. make clean has been setup to clean the local build directories, make -B will force a re-make of everything regardless of modification timestamps, and make -j<num> will parallelize the build process with num cores (you shouldn’t need this at all for this lab).

Common types of Bugs

C is very prone to bugs. Despite the many existing solutions, C is still the lingua franca of low-level systems programming, and gives you the most precise control over generated machine code. In this lab, you should encounter most of these bugs unless otherwise stated:

Memory Safety Bugs

Spatial Memory Safety Bugs

Unlike most modern languages, C has no runtime bounds checking for array/buffer access. Combined with unchecked pointer arithmetic, one can really reference any offset from an object and potentially achieve arbitrary read or write. These issues are known as spatial memory violations. They can corrupt adjacent objects, stack return addresses, and other elements necessary for correct program execution. Some common bugs that fall under this category are known as OOB (out-of-bound) accesses and buffer overflows. While many of these seem trivial to fix, beware of string related operations. C represents strings as a null-terminated char array, and that final null byte can lead to a lot of off-by-one errors.

Temporal Memory Safety Bugs

Unlike garbage-collected languages, memory is manually managed in C. Unlike smarter manual memory management languages like Rust or Ada (and really modern C++ too if you know how to use it correctly), C provides no compile time guarantees to act as guard rails for memory management. Temporal violations often involve de-referencing freed memory, which are known as use-after-frees. This can then lead to corruption within the allocator state or objects that are re-allocated in the same region (this is known as a type confusion bug). Double frees, in which memory is freed twice, will also trigger similar issues. This may seem like a silly issue for one to program, but will happen quite easily as code complexity increases.

Memory Leaks

This closely relates to temporal memory safety bugs. Without a garbage collector, there is no runtime object liveness analysis. If you forget to manually free memory, your program will continue to grow in memory size. While perfectly fine for short-lived programs (and probably the correct thing to do for performance), this becomes a major problem for larger programs. Leak enough memory on Linux and you will trigger the OOM-killer, which starts going down your OS’s process list and terminating processes to free up memory. Our usage of Valgrind will specifically catch for this type of bug.

Uninitialized Types

There is no default initialization value in C. If you don’t explicitly initialize a variable, its contents will be undefined (usually, the contents come from a previous value at that same location). This can lead to a source of bugs! An extremely common case last year was students not initializing a data array, and ending up confused of how the sum of 0 data points for a certain index resulted in a random large number.

Errorneous Return Values

C doesn’t really have a built-in exception system nor does it have the concept of a result/option monad like in Rust or Haskell for error checking. The type system thus causes an errorneous return value to share the same type as a successful return value (C has unions, but those unions have no enforced safety guarantees). A common case for this is in syscall relevant functions such as read - on success, it tells you the number of bytes that are read, but on failure, it returns a specific negative value. Another example more relevant to this lab are functions that return heap-allocated objects. On success, they will return a valid pointer, but on failure, it will return a null pointer. Technically, the address 0x0 can still be a valid address depending on system configuration, which makes null pointers especially problematic in certain scenarios… Tony Hoare calls this his billion dollar mistake.

Integer Overflows

If you are familiar with a real programming language, then you already know this. If you come from Python, then pay attention. Integer primitives in real languages are backed by hardware registers, which are limited in size. Eventually, a register will overflow (Ex. adding 1 to 2^63-1 will overflow and bring the value back to 0). You should expect the natural number wrapping behavior for unsigned integers in C, but this overflow becomes undefined behavior for signed integers, which leads to our next point. There are also many other integer related quirks - take this quiz to see how much you know!

Undefined Behavior

This is a very large class of bugs. C lists many different things as undefined behaviors, which basically means the compiler can do whatever it wants, including wiping your whole hard drive, and make any assumptions it wants (usually for the purpose of code optimization). This can lead to very very surprising behavior! Technically many of the previously discussed bugs fall in the category of “undefined behavior.”

Race Conditions

You won’t encounter this in our lab. But this is a problem that plagues every language whenever concurrency and parallelism enters the picture. A subclass of this includes data races, which some strongly typed languages like Rust has solved.

Debugging Tips:

There are a few ways to debug in C.

The best way in my opinion is print debugging. Use printf to add print statements wherever you need them. You can easily deduce all the test cases as well with this technique. Note that our tester binary includes the following initial call:

setbuf(stdin, NULL);
setbuf(stdout, NULL);
setbuf(stderr, NULL);

Standard library level IO functions often buffer input - you might miss a print statement if you don’t end the text with a newline as the default is line-buffering (and will also affect the heap layout). These setbuf calls disable bufferring.

C print functions rely on format specifiers, and you can learn all about them https://man7.org/linux/man-pages/man3/fprintf.3.html. Generally, you only need %d for uint32_t (I highly recommend that everyone use the bitwidth typed integers in C from stdint.h instead of the default integer types in C), %lld for uint64_t, %x for uint32_t in unsigned hex, %llx for uint64_t in unsigned hex, %p for pointers, %c for chars, and %s for strings.

For example, if foo is a pointer to some struct, bar is an uint32_t, and foobar is a string, you would do this:

printf("foo: %p bar: %x foobar: %s", foo, bar, foobar);

Do not ever directly print a non-compile time constant string as the first argument in printf ever in C code. Doing so will get your codebase compromised thanks to a specifier known as %n that allows for arbitrary write into memory.

Sanitizer Debugging

Recall ASAN and UBSAN from earlier. These are helpful tools that instrument your code to help catch most memory safety and undefined behavior bugs during runtime. You run the instrumented version and whenever a violation is detected, you receive a report with a backtrace. For example, the starter code will trigger the following backtrace one of the first test cases.

./sanitized_tester
------------------------------------------------------------
Running BUG_CHECK_0 Test, notebook length: 10
------------------------------------------------------------
read_page
AddressSanitizer:DEADLYSIGNAL
=================================================================
==357005==ERROR: AddressSanitizer: SEGV on unknown address 0x607000013980 (pc 0x7f7d7371584e bp 0x7ffd21a66fc0 sp 0x7ffd21a66fa0 T0)
==357005==The signal is caused by a READ memory access.
    #0 0x7f7d7371584e in read_page /shd-lib.c:25
    #1 0x5e37b6534bd9  (/sanitized_tester+0xaabd9)
    #2 0x5e37b6554c54  (/sanitized_tester+0xcac54)
    #3 0x5e37b6529301  (/sanitized_tester+0x9f301)
    #4 0x5e37b65133b7  (/sanitized_tester+0x893b7)
    #5 0x7f7d71c29d8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #6 0x7f7d71c29e3f in __libc_start_main_impl ../csu/libc-start.c:392
    #7 0x5e37b6513944  (/sanitized_tester+0x89944)

AddressSanitizer can not provide additional info.
SUMMARY: AddressSanitizer: SEGV /shd-lib.c:25 in read_page
==357005==ABORTING

You can catch a lot of bugs just with this technique.

Using an Actual Debugger

This should be your last resort, but can be useful for pinpointing some hard to catch bugs. The debugger I recommend is GDB with GEF extensions. Vanilla GDB looks ugly, isn’t fun to use, and defaults to AT&T assembly syntax. There are many GDB guides out there, but these are what I find useful (though GEF already automatically shows a lot of the information these commands can reveal).

  • bt: for dumping a stack backtrace
  • p $<var>: display the value of a variable (which can just be a register name or an address). You can also typecase the var in C syntax to get a pretty-print, but that is dependent on whether there is sufficient DWARF debug information.
  • disas <address>: disassembles the current function, or starting from an address if specified.
  • x/<NUM><specifier>x <address>: Shows NUM specifier sized elements in hex starting from address. Specifiers include g for giant word (8 bytes), w for word (4 bytes), h for half-word (2 bytes), or b for byte. If you replace the x after the specifier with an i, you can get a disassembly dump as well.
  • b sym/b address: set a breakpoint at an address. You can also specify a conditional expression for conditional breakpoints.
  • watch: watchpoints are like breakpoints, but for value changes in the program. I really doubt you’ll ever need it in this class, but a useful tool to have
  • c: continue program execution
  • r: start program execution
  • s/n: step and next. Step goes to the next source line, entering function calls, while next goes to the next source line, skipping function calls. There are many different variations of this, so take a look here. One variation worth mentioning are the stepi and nexti variants, which operate at the instruction granularity.
  • search-pattern: a GEF specific extension that is a life-saver. This allows you to search for arbitrary memory patterns at arbitrary address ranges.

The Lab

The goal of this lab is to fix the bugs - passing the tester checks should satisfy most of that.

The Basics

Refer very carefully to the comments in shd-lib.h for the spec. One thing to realize about the struct definitions is the array declaration in page_t:

typedef struct {
    size_t len;
    char content[];
} page_t;

Usually, variable length arrays are not allowed in structs, except when it is the last field. This is a very common pattern in networking or IPC code. You can allocate these types of elastic structs with the following pattern: malloc(sizeof(elastic_type) + additional_size).

In general, this library provides notebook objects with a fixed amount of pages, which users can read, write, erase, grow, and append to.

Example Bug

One really simple bug that you should catch immediately is the lack of bounds checking in all the notebook relevant operations. Users have to specify a page_nr for most of them, yet there are no checks to see whether the page_nr is even possible for this notebook’s pages array.

Some hints

  • As mentioned earlier, the null byte in C strings can be really finnicky, especially when performing operations on them.
  • The first 6 bugs we discussed earlier all appear here (and technically the 7th, because all those bugs lead to undefined behavior)
  • I talked about reading the spec for shd-lib.h earlier, but what about malloc, free, and realloc
  • Remember the base size of flexible structs.
  • One really tricky bug comes directly from a real world bug. Look into the root cause of CVE-2022-0185 for the Linux kernel. Don’t worry, all you need is basic C knowledge and it’s a one line fix!

Additional Tester Features

Since certain bugs more easily manifest themselves from a simpler heap state in these short test cases (before many deallocations occur), you can manually run the ./tester binary with a list of names of certain BUG_CHECKS to run through. For example: ./tester BUG_CHECK_3 BUG_CHECK_6 BUG_CHECK_9.

1-1 Exercise

Fix all the bugs in shd-lib.c so that the test cases can pass!

1-2 Discussion Question

Write about 5 bugs that you found in this lab. A single sentence for each will suffice.

Grading

The programming component makes up 90% of the points in this lab. Each test case is worth the same (with the final valgrind test being considered a single test case). Our grader does NOT take into consideration of a passing test case that comes after a crashing test case.

The discussion makes up 10% of the points in this lab.

Submission

Push your code to the Github classroom, and submit your discussion responses to Gradescope.

Acknolwedgements

Contributors: William Liu, Shixin Song, Mengjia Yan