Lab 3: Black-box testing
Goals for this lab
By the time you have completed this lab, you should:
- have a better understanding of separate compilation
- understand at a high level the array list implementation
- be able to think a bit like a black-box attacker
The purpose of this lab is for you to discover bugs in my array-based implementation of the list structure.
For this lab you may work with a partner. To facilitate your submissions as a pair you MUST pair up using the submission system. When you visit the project page from where you can view all your submission you should see a link to a page where you can join a group. Of the two people in the group, one of you must invite the other, and the other must confirm the invitation. Once you group up, any submissions that either you, or your partner have already made will be visible to each other in addition to all future submissions.
At this point, everyone should have a COE account. If you do not, you need to make that a priority and should partner up with someone who already has an account.
Before you begin, let's prepare a cs24 directory in your home directory if you don't already have one. In that directory we'll create a subdirectory for the files for this lab. Note that these instructions assume you are using either a CSIL machine or one of the lab machines:
After logging in, create the directory (assuming you haven't already done so):
mkdir -p cs24/lab3
Change the permissions of the cs24 directory such that only your account can access the files inside this directory. This step is incredibly important. If omitted, other students can peek at your work and you may be held partially responsible. It should also go without saying that you may not give other students access to your account. If you've done that in the past please change your password at this time.
chmod 700 cs24
Change into the lab3 directory and copy the files you will need for this lab:
cd cs24/lab3 cp ~bboe/public_html/cs24_f13/code/lab3/* .
The provided files
In your directory you will find the following files:
array_list.o -- This is my implementation of the array-based version of the structure library which contains 4 bugs. The separate compilation concept that clang supports is what allows me to provide you with this object file and not the source code (you will not be able to find the source using gdb).
lab3.c -- This is the file you will edit, and the only file you will submit.
list.h -- This is the same list.h file provided with project 1. In this file you will find the comments for all the
list_*functions which you may find useful.
Makefile - This file specifies how the
test_arraybinary should be compiled. Notice that it utilizes
test_list.c - This is almost identical to the
test_list.cprovided with project 1. However, it adds
#include "lab3.c"so that the code you write in
lab3.cis incorporated into the test set.
Compiling and running the test suite
As given, you can compile the
test_array executable by simply running:
The, you can run all the tests in the test suite by running:
./test_array 0 20
which will initially provide the output:
Test 00: construct_destruct Passed Test 01: at_0_after_push_back_one Passed Test 02: at_minus1_after_construct Passed Test 03: at_minus1_after_push_back_one Passed Test 04: at_neg1_after_push_back_one Passed Test 05: at_plus1_after_construct Passed Test 06: at_plus1_after_push_back_one Passed Test 07: get_size_after_construct Passed Test 08: get_size_after_push_back_one Passed Test 09: is_empty_after_construct Passed Test 10: is_empty_after_push_back_one Passed Test 11: output_after_construct Passed Test 12: output_after_push_back_one Passed Test 13: push_back_remove_at_0 Passed Test 14: push_back_remove_at_neg1 Passed Test 15: remove_at_0_after_construct Passed Test 16: remove_at_neg1_after_construct Passed Test 17: find_list_at_bug Failed Test 18: find_list_destruct_bug Failed Test 19: find_list_push_back_bug Failed Test 20: find_list_remove_at_bug Failed
Your task is to update the four functions in
lab3.c such that each of the
functions triggers the appropriate bug (and only the appropriate bug). When
completed the final should be:
Test 00: construct_destruct Passed Test 01: at_0_after_push_back_one Passed Test 02: at_minus1_after_construct Passed Test 03: at_minus1_after_push_back_one Passed Test 04: at_neg1_after_push_back_one Passed Test 05: at_plus1_after_construct Passed Test 06: at_plus1_after_push_back_one Passed Test 07: get_size_after_construct Passed Test 08: get_size_after_push_back_one Passed Test 09: is_empty_after_construct Passed Test 10: is_empty_after_push_back_one Passed Test 11: output_after_construct Passed Test 12: output_after_push_back_one Passed Test 13: push_back_remove_at_0 Passed Test 14: push_back_remove_at_neg1 Passed Test 15: remove_at_0_after_construct Passed Test 16: remove_at_neg1_after_construct Passed Test 17: find_list_at_bug discovered list_at bug Failed Test 18: find_list_destruct_bug discovered list_destruct bug Failed Test 19: find_list_push_back_bug discovered list_push_back bug Failed Test 20: find_list_remove_at_bug discovered list_remove_at bug Failed
Notice the addition of the messages
discovered list_??? bug for the
appropriate function. These messages are output in certain cases the provided
array-based list structure implementation in
Writing the test cases to find the bug
In each respective function in
lab3.c you have to trigger the exact bug that
function is looking for. This will require some (maybe a lot) of
experimenting. Take the time to think about what has already been tested
(notice that all the existing tests already pass), and more importantly what
hasn't been tested. When you think you're on to something code it up, compile
it, and then test it locally (you don't need to submit to test).
Note that each function may require more than one
list_* function call, and
may require calls to
list_* functions other than the one you're attempting to
find the bug for. Also, you should not directly manipulate the list structure
as that will likely result in an unexpected bug which is not part of the
challenge. It is desirable for libraries to assume their structures are valid,
hence why it is not ideal to directly manipulate structure contents and why the
list structure attributes are all prefixed with
So that there is no confusion: if you make a submission that directly outputs
(or attempts to directly output) one of the expected messages you will receive
a 0 on this assignment. The only acceptable way to pass the tests is
through the correct cominbation of calls to the
Submitting the assignment
Only one person in a group need submit the assignment but make sure that both you and your partner can view the submission on the submission site. If you cannot, you need to complete the making a group process. Please review the submission instructions as needed. Note that you may resubmit this assignment as many times as necessary up until the deadline.