SaiphC

tdelete()'s return values cannot be trusted

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():

    Warning: returning a dangling address.
    # The address-to-be-returned is of a memory-block (start:0x922a070, size:16 bytes) allocated at
    #    file:/tsearch.c::81, 6
    #    file:/prog.c::28, 8
    #    [libc-start-main]
    # The memory-block has been freed at
    #    file:/tdelete.c::45, 2
    #    file:/prog.c::32, 14
    #    [libc-start-main]
    # The memory-block has been freed, and its allocation location could have
    # been distorted by subsequent reuses.
    #
    # Stack trace (most recent call first)
    # [0]  file:/prog.c::32, 14
    # [1]  [libc-start-main]
    https://cee.studio/explanation

Here is the live demo to reproduce it.

In tdelete()'s man page¹, 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.

Testing glibc's tdelete
  ...

  call tdelete to delete 2
  >> free(0x7f52e7f503ec)
  tdelete returns 0x7f52e7f503ec <-- dangling pointer
  root is 0x7f52e7f50450

  call tdelete to delete 3
  >> free(0x7f52e7f50450)
  tdelete returns 0x7f52e7f50450 <-- dangling pointer
  root is (nil)

Testing musl libc's tdelete
  ...
    
  call tdelete to delete 2
  >> free(0x7f1d9d9553ec)
  tdelete returns 0x7f1d9d9553ec <-- dangling pointer
  root is 0x7f1d9d955450

  call tdelete to delete 3
  >> free(0x7f1d9d955450)
  tdelete returns 0x7f1d9d955450 <-- dangling pointer
  root is (nil)

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:

OpenGroup

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.

macOS man page:

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.

Debian buster

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.

OpenBSD

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:

The latest glibc and musl libc still return 'legit' dangling pointers that could be dereferenced without causing visible memory errors.
Many of Legacy OSs' man pages do not warn the user about the dangling pointer risk, and CVE# is not just for vulnerabilities in newer OSs.
Many production softwares are NOT developed on the latest OSs. Issuing a CVE# would have notified AppSec teams so they can to do self-checks as well as warn their developers. Similarly, AppSec companies can add the problem to their checklist.
CVE#s can be issued to existing or future misuses. However, the root cause would still not be addressed, allowing developers to introduce more vulnerabilities.

The lesson from this example is that employing comprehensive memory access violation checking and testing would be a more efficient way to prevent memory errors and potential security vulnerabilities.