This page does not represent the most current semester of this course; it is present merely as an archive.
In this lab, you will diagnose and fix memory errors in a simple program. We recommend doing this lab on the lab machines either via SSH or by directly logging into one.
Download the asanlab.tar and extract it on a lab machine. After extracting the archive run
make in the root directory. This will build a buggy circular doubly linked-list library (described in the
ll.h header file and implemented in
ll.c) and a test-case for it (in
ll-test.c). The testing program is called
ll-test. If you run it, you will get output like:
>>> running empty test >>> running singleton test >>> running string sizes test failed test: length of a's string: strlen(cur->value) == i was false failed test: length of a's string: strlen(cur->value) == i was false failed test: length of a's string: strlen(cur->value) == i was false failed test: length of a's string: strlen(cur->value) == i was false failed test: length of a's string: strlen(cur->value) == i was false >>> running replace/add test >>> running big test ll-test: malloc.c:2395: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed. Aborted (core dumped)
indicating that some tests failed and
malloc experienced an error. This failure is due to a problem with memory management in
Because the problems are due to memory errors and memory layout varies between implementations of
malloc, the output may vary between machines.
Since memory errors like these are notoriously tricky to debug, we’ve also build a version of the testing program with a tool called AddressSanitizer. AddressSanitizer is one of many tools that are available to help programmers diagnose memory errors.
AddressSanitizer is a combination of a compiler extension and runtime library for detecting and diagnosing memory errors. It works by maintaining a
shadow memory indicating the status of every byte of memory allocated by the program. The shadow memory has one byte for every 8 bytes of normal memory, which is 0 if the memory is addressable and another value otherwise. Memory allocation code, including both
malloc and the compiler’s allocations of space on the stack, is modified to update this
shadow memory. Then, before every memory access that uses a pointer or array, the compiler inserts code to check this shadow memory, reporting an error if the corresponding status is unexpected.
In order to also detect out-of-bounds accesses, AddressSanitizer ensures that there is a
redzone before and after variables in memory, both on the stack and as allocated by
redzones have an invalid status in the shadow memory.
You can run ll-test using address sanitizer by using
make test. Since the programs access unallocated memory, this will produce output that includes two stack traces:
==12270==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000f000 at pc 0x7f66d0f09709 bp 0x7ffd854ca110 sp 0x7ffd854c98b8 WRITE of size 17 at 0x60200000f000 thread T0 #0 0x7f66d0f09708 (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x62708) #1 0x400e6b in strcpy /usr/include/x86_64-linux-gnu/bits/string3.h:110 #2 0x400e6b in ll_add_after /home/cr4bd/cs3330-site/asanlab/ll.c:34 #3 0x40169f in singleton_list_test /home/cr4bd/cs3330-site/asanlab/ll-test.c:61 #4 0x402174 in main /home/cr4bd/cs3330-site/asanlab/ll-test.c:133 #5 0x7f66d0afe82f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f) #6 0x400bf8 in _start (/home/cr4bd/cs3330-site/asanlab/ll-test-sanitize+0x400bf8) 0x60200000f000 is located 0 bytes to the right of 16-byte region [0x60200000eff0,0x60200000f000) allocated by thread T0 here: #0 0x7f66d0f3f602 in malloc (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x98602) #1 0x400e2f in ll_add_after /home/cr4bd/cs3330-site/asanlab/ll.c:32 #2 0x40169f in singleton_list_test /home/cr4bd/cs3330-site/asanlab/ll-test.c:61 #3 0x402174 in main /home/cr4bd/cs3330-site/asanlab/ll-test.c:133 #4 0x7f66d0afe82f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
After these two stack traces, the output will include information about the shadow memory, showing that the access corresponded to a
red zone segment memory which was right next to an
The two stack traces have the most important information, with the first stack trace usually being the more useful of the two.
The first one is where a
WRITE (as indicated by the line before the stack trace) to invalid memory occurred. The stack trace indicates that this write occurred in
strcpy(), which was called from
ll_add_after() on line 34 of
ll.c. This call to
ll_add_after() was in turn made from line 61 of
The second stack trace indicates where the valid memory most related to the valid memory was allocated. In this case, the header indicates that the invalid memory address was
located 0 bytes to the right of a 16-byte region … allocated with
malloc() as called by
ll_add_after() on line 32 of
These stack traces indicate that the
strcpy() on line 34 of
ll.c wrote past the end of whatever was allocated on line 32 of
AddressSanitizer also detects memory leaks, where memory is allocated but not freed. It reports memory leaks with output like:
==23580==ERROR: LeakSanitizer: detected memory leaks Direct leak of 24 byte(s) in 1 object(s) allocated from: #0 0x7f6499eb4602 in malloc (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x98602) #1 0x400e65 in ll_new /home/cr4bd/cs3330-site/asanlab/ll.c:16 #2 0x4012de in ll_copy_list /home/cr4bd/cs3330-site/asanlab/ll.c:75 #3 0x401b84 in replace_add_test /home/cr4bd/cs3330-site/asanlab/ll-test.c:81 #4 0x402353 in main /home/cr4bd/cs3330-site/asanlab/ll-test.c:138 #5 0x7f6499a7382f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f) ....
Each stack trace labelled a
leak of (some number) byte(s) indicates a place where memory was allocated. To fix these memory leaks, you must ensure the memory is freed somewhere, probably not where it was allocated.
ll.c to fix all the memory errors. For a description of what the functions in
ll.c are supposed to do, read the comments in
You are successful if
make test reports no errors (from ll-test.c or AddressSanitzer). Note that it is possible for
ll.c to still have memory errors even though all tests in
ll-test.c produce the correct result.
You may use any tool you like to debug the program. Submit your
ll.c with whatever progress you made by the end of the lab.