Dangling pointers, Tombstones, and Lock and Keys.
What is a dangling pointer?
A pointer pointing to data that does not exist anymore is called a dangling pointer.
d is a dangling pointer.
How are they formed?
- A dynamically created object is de-allocated.
After deallocation, ptr points to an empty memory location.
2. Address of local variables is returned from functions.
After execution of the return statement, the stack frame of the function func is popped. So, we are returning the address of a variable that will no longer exist when control returns to the main function.
3. When the address of an out-of-scope variable is assigned to the pointer, it becomes a dangling pointer in the outer block.
Why care about them?
- In some cases, dangling pointers point to memory that our program is not allowed to use. Accessing this memory causes memory faults. OS terminates the process abruptly when a memory fault occurs.
- They might over-write information critical to the program. This will cause unexpected behavior and bugs while executing the program.
Let pointer ptr have the address of a local variable returned from a function. ptr points to a location in the run-time stack that is not currently owned by the program. Dereferencing ptr will cause memory fault and termination of the program.
There’s a chance that the program runs some other function calls and they use the stack frame to which ptr points. Using ptr won’t cause a memory fault because the memory is still owned by the program. However, ptr can over-write and ruin the stack frame.
Let’s take one more example.
There’s a fair chance that memory deallocated from pointer p will be allocated to q. In that case, contents of q can be over-written using p.
3. Dangling pointers were viewed as a software quality issue that would just cause some over-writing and system crashes. They weren’t given their due importance as security issues until Watchfire demonstrated how they hacked Microsoft Corp.’s IIS 5.1 server software by exploiting a dangling pointer vulnerability at a BlackHat conference.
How to deal with them?
A good practice would be to set the pointer to NULL as soon as it is freed. However, this won’t work if multiple pointers point to the same location.
We can also use tools such as Valgrind and Polyspace to detect them.
Another approach would be to implement mechanisms in language systems that prevent the dangling pointer from accessing memory locations. One such proposed mechanism is the Tombstones.
As soon as memory is allocated, it is assigned to a pointer called the tombstone. The pointers in our program which are supposed to point to this memory, point to the tombstone instead. Let’s understand why are we doing this.
As shown in the diagram, we would have to double dereference the pointers i.e. *(*a) or *(*b) to access the memory.
Now, the memory is deallocated using pointer a. Soon after deallocation, we assign a NULL value to the tombstone. Now, if we try to access the memory using a or b, we get a NULL pointer dereference error i.e. *(*NULL) is an invalid operation. This prevented the dangling pointers from accessing the memory location.
However, this method is quite taxing in terms of time and space. The time to access memory is more as we are dereferencing two times. Also, we cannot use the same tombstone if the deallocated memory is allocated again. We would have to make a new one.
If we use the same tombstone for c, we give the memory access to a and b too. This defeats our purpose of using tombstones. The tombstones keep on piling up as garbage in the heap. No popular languages use this mechanism.
An alternative to Tombstones is Lock and Keys, used in the implementation of UW-Pascal.
When memory is allocated, space for one more cell called the lock cell is allocated. This cell is assigned a value. The pointer which points to this memory is stored as a tuple containing an address and a key. A pointer is allowed to access the memory only if the values of the lock and keys match. Otherwise, it will throw a runtime error.
Now, the memory is deallocated using pointer a. Soon after deallocation, we assign a NULL value to the lock. Now, if we try to access the memory using a or b, the values of the lock and the keys do not match and runtime error is thrown. This prevented the dangling pointers from accessing the memory location.
Also, we won’t need a new lock cell when the memory is re-allocated. We can simply change the value of the lock.
As the value of the lock was changed, pointers a and b cannot access it.
This method is time costly as on every pointer access, lock and key comparison is done. There’s a space overhead too. We have to allocate extra cells for storing the lock and key values.
Dangling pointers are born out of human negligence. So, the best way to deal with them would be to take deallocation out of the hands of developers. If developers cannot explicitly deallocate them, they will no longer exist. Runtime systems would implicitly deallocate them when they are no longer in use. LISP, Java, and C# use this approach.
