Latest Update: CVE-1999-0199 was issued for this vulnerability after we presented our argument. We applaud MITRE.ORG for sticking to its true mission.
We implemented a map container as a thin wrapper of
<search.h>, a POSIX family functions included in
libc, in our Cloud IDE and were caught off
guard by the following warning for the return value of tdelete():
In tdelete()'s man page1, the RETURN VALUE specifies that "tdelete() returns a pointer to the parent of the item deleted, or NULL if the item was not found." It seems that tdelete() can return dangling pointers.
In order to verify the warning, we wrote a test to test both musl libc's and glibc's tdelete(). The output of the test (as seen below) shows that two dangling pointers are returned for each test.Returning a dangling pointer is dangerous, especially for functions included in libc, as dereferencing the dangling pointer can cause memory errors and security vulnerabilities. It's evident the problematic behavior of tdelete() has existed since the function's inception.
As pointed out by members of r/C_programming and HN, tdelete()'s man page on various systems warn about the risk of dangling pointers in different but convoluted ways:
The tdelete() function shall return a pointer to the parent of the deleted node, or an unspecified non-null pointer if the deleted node was the root node, or a null pointer if the node is not found.
The tdelete() function deletes a node from the specified binary search tree and returns a pointer to the parent of the node that was deleted. It takes the same arguments as tfind() and tsearch(). If the node to be deleted is the root of the binary search tree, rootp will be adjusted.
tdelete() returns a pointer to the parent of the node deleted, or NULL if the item was not found. If the deleted node was the root node, tdelete() returns a dangling pointer that must not be accessed.
tdelete() returns a pointer to the parent of the deleted node or an unspecified non-null pointer if the root node is deleted.
Correctly using the function's return values is counter-intuitive as shown in this example. It requires a very good understanding of C's memory model and how tdelete() adjusts the root pointer. To prevent any misuses by less experienced developers, we believe the most effective warning as pointed out by u/notaplumber is "the return value of tdelete() should not be relied on at all.". In terms of risk among these systems, OpenBSD's tdelete() is the safest for developers. Both glibc and musl libc still return 'legit' dangling pointers that can be dereferenced and therefore leave their users more vulnerable.
We were lucky because Cee.Studio automatically checks whether all memory accesses and pointers violate C's memory model. If we were relying on our man page and Google search, we would have introduced use-after-free bugs inadvertently.
After being surprised by tdelete()'s problematic return values, we searched CVE databases with the hope that this problem was documented. The search returned no such documentation, and we decided to file one. The following is the response from cve.mitre.org:
Unfortunately, we cannot assign a CVE ID for a documented behavior of tdelete. We can assign a CVE ID for an application that accesses the dangling pointer in a way that always causes a security-related impact. (We cannot assign a CVE ID for a finding that access to the dangling pointer is undefined behavior.)
MITRE's response is counterproductive to its mission in several ways: