
- Course Home
- Administration
- Assignments
- Calendar
- Online Resources
Practice Exercise #4
I once had an array of bytes, named buf.
The bytes were uninitialized, so had random values. I then hid a string in
buf, encoding it using a doubly linked list. Each element of the list
contained one character, and told me how to find the next element.
More particularly, each element of the list was an instance of this structure
typedef struct element_st {
uint32_t next;
uint32_t prev;
char c;
} element;
An element structure could be located starting at any byte offset in buf. The next
and prev values are byte offsets into buf, except that value 0 means
null (no next element). For instance,
if next equals 102, it means that the next element structure is stored in the
bytes that begin at &buf[102].
The prev pointer of the first element is null, and the next element of the last element
is null.
So long as I remember where the first element of the linked list is, I can recover my string by
traversing the linked list.
I lost the information about where the first element is. But, I still have the data bytes, in a file.
Write a C program that will recover my string by:
- using open (man 2 open) to open a binary data file, fstat to determine its length, and read (man 2 read) to read the file contents into an appropriately sized, malloc'ed, in memory buffer.
- applying some heuristics to find my string in among all those random bytes.
bash$ ./findData secretFile.txt Don't lose the location of the head element or you won't be able to find this string. bash$ ./findData findData.c No string found bash$ ./findData /usr/bin/gcc @Sample files that contain embedded strings are in directory ex04_files.
Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX