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 ll.c
.
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 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 your ll.c
with whatever progress you made by the end of the lab.