CS 3330: Computer Architecture

This page does not represent the most current semester of this course; it is present merely as an archive.

1 Memory Safety Lab

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.

2 Getting the Code

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.

3 AddressSanitizer

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.

3.1 Running and Interpreting Output

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.

3.2 Memory Leaks

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.

4 Your Task

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.

Copyright © 2016 by Luther Tychonievich and Charles Reiss. All rights reserved.
Last updated 2016-11-28 11:04:47