This page is for a prior offering of CS 3330. It is not up-to-date.
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, since this lab depends on having a fairly recent C compiler and some related utilities that you may not have.
For this lab, and many others to come, you will submit your work to to archimedes.
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 Makefile builds two versions of the testing program. One is built using a memory-error debugging tool called AddressSanitizer, described below. You can run this version of the test program using make test. This produce output like this:
user@machine:~/asanlab$ make test
./ll-test-sanitize
>>> running empty test
>>> running singleton test
=================================================================
==12270==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000f000 at pc 0x7f66d0f09709 bp 0x7ffd854ca110 sp 0x7ffd854c98b8
WRITE of size 17 at 0x60200000f000 thread T0
...indicating that the test program ./ll-test-sanitize was ran, and in the middle of its singleton test
some errors were detected. This failure is due to a problem with memory management in ll.c. Your goal for this lab is to fix ll.c so that make test reports no errors.
You can also run a version of the test program built without using AddressSanitizer using ./ll-test after recompiling ll-test, if needed, with make ll-test or make. This will produce output indicating a crash in malloc, also due an a memory management problem in ll.c, but provide less information about the cause of the error.
Running without AddressSanitizer will generally be faster but will fail to detect memory errors. Most notably, it will never indicate when memory leaks occur since these waste memory rather than every causing the program to behave incorrectly. Even for memory errors that involve writing or reading after the end of a memory allocation, running the program normally may work correctly, since the following memory may happen to be valid but not used for anything important.
Because the problems are due to memory errors and memory layout varies between implementations of malloc, the exact output may vary between machines.
Since memory errors like these are notoriously tricky to debug, we’ve built 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 malloc. These 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 addressable
region.
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 ll-test.c.
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 ll.c.
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 ll.c.
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.
Edit 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 ll.h.
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 (via archimedes your ll.c with whatever progress you made by the end of the lab.