Possible UaF in tkvdb_node_new_generic (node.c:139)

[bladchan]

Hi, this is a wonderful work.
I conducted some fuzz testing on this library and discovered a use-after-free vulnerability in one of generated call sequences.

The call sequence:

// bug_uaf.c
#include "tkvdb.h" 

static size_t trsize = 100 * 1024 * 1024;

int 
main(){
	
	char db_file[] = "db_1";
	tkvdb_params* params = tkvdb_params_create();
	 /* we don't need dynamic reallocation of transaction buffer */
	tkvdb_param_set(params, TKVDB_PARAM_TR_DYNALLOC, 0);  // <--- ? 
	/* set buffer size */
	tkvdb_param_set(params, TKVDB_PARAM_TR_LIMIT, trsize);
	/* align values */
	// tkvdb_param_set(params, TKVDB_PARAM_ALIGNVAL, sizeof(uint64_t));
	tkvdb *db = tkvdb_open(db_file, params);

	tkvdb_tr* tr1 = tkvdb_tr_create(db, 0);
	tr1->begin(tr1);

	char key_str[] = "Hello World!";
	char value_str[] = "This value!";
	tkvdb_datum key;
	tkvdb_datum value;
	value.data = value_str;
	value.size = sizeof(value_str);
	key.data = key_str;
	key.size = sizeof(key_str);
	tr1->put(tr1, &key, &value);
	tr1->commit(tr1);
	
	tr1->begin(tr1);
	tr1->del(tr1, &key, 1);
	
	tr1->free(tr1);   // <--- trigger uaf bug? without asan it will lead to a SEGV?
	
}

---

Trigger condition maybe?:

1. Disable TKVDB_PARAM_TR_DYNALLOC;
2. Specific sequence: put/commit -> del -> free

---

Reproduce:

1. Compile the above poc code with ASAN:
   $ clang -g -fsanitize=address bug_uaf.c tkvdb.c -I./ -o bug_uaf
2. Run poc:
   ./bug_uaf

---

ASAN says:

$ ./bug_uaf 
=================================================================
==2796==ERROR: AddressSanitizer: heap-use-after-free on address 0x7f384d2ff870 at pc 0x000000514e33 bp 0x7ffea0bc4910 sp 0x7ffea0bc4908
WRITE of size 4 at 0x7f384d2ff870 thread T0
    #0 0x514e32 in tkvdb_node_new_generic (/home/ubuntu/tkvdb/bug_uaf+0x514e32)
    #1 0x5772f0 in tkvdb_do_del_generic (/home/ubuntu/tkvdb/bug_uaf+0x5772f0)
    #2 0x53a28b in tkvdb_del_generic (/home/ubuntu/tkvdb/bug_uaf+0x53a28b)
    #3 0x512658 in main (/home/ubuntu/tkvdb/bug_uaf+0x512658)
    #4 0x7f385617ac86 in __libc_start_main /build/glibc-CVJwZb/glibc-2.27/csu/../csu/libc-start.c:310
    #5 0x419e29 in _start (/home/ubuntu/tkvdb/bug_uaf+0x419e29)

0x7f384d2ff870 is located 112 bytes inside of 104857600-byte region [0x7f384d2ff800,0x7f38536ff800)
freed by thread T0 here:
    #0 0x4d9b10 in __interceptor_free.localalias.0 (/home/ubuntu/tkvdb/bug_uaf+0x4d9b10)
    #1 0x575459 in tkvdb_node_free_generic (/home/ubuntu/tkvdb/bug_uaf+0x575459)
    #2 0x5772b9 in tkvdb_do_del_generic (/home/ubuntu/tkvdb/bug_uaf+0x5772b9)
    #3 0x53a28b in tkvdb_del_generic (/home/ubuntu/tkvdb/bug_uaf+0x53a28b)
    #4 0x512658 in main (/home/ubuntu/tkvdb/bug_uaf+0x512658)
    #5 0x7f385617ac86 in __libc_start_main /build/glibc-CVJwZb/glibc-2.27/csu/../csu/libc-start.c:310

previously allocated by thread T0 here:
    #0 0x4d9ce0 in malloc (/home/ubuntu/tkvdb/bug_uaf+0x4d9ce0)
    #1 0x517095 in tkvdb_tr_create (/home/ubuntu/tkvdb/bug_uaf+0x517095)
    #2 0x5123c5 in main (/home/ubuntu/tkvdb/bug_uaf+0x5123c5)
    #3 0x7f385617ac86 in __libc_start_main /build/glibc-CVJwZb/glibc-2.27/csu/../csu/libc-start.c:310

SUMMARY: AddressSanitizer: heap-use-after-free (/home/ubuntu/tkvdb/bug_uaf+0x514e32) in tkvdb_node_new_generic
Shadow bytes around the buggy address:
  0x0fe789a57eb0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0fe789a57ec0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0fe789a57ed0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0fe789a57ee0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0fe789a57ef0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x0fe789a57f00: fd fd fd fd fd fd fd fd fd fd fd fd fd fd[fd]fd
  0x0fe789a57f10: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0fe789a57f20: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0fe789a57f30: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0fe789a57f40: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0fe789a57f50: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==2796==ABORTING

It's noticed that there's a SEGV issue when the poc compiled without ASAN.

[vmxdev]

Hello!

Thanks for the report and testing.
The real problem is with the del() function. It is not working properly right now.
We're using tkvdb in our applications (mostly telecom), where deleting single key-value pairs is not really necessary.

As a workaround, you can make a special mark inside the value notifying this key-value pair has been deleted.

We already have an issue on this topic ( #9 ), but there is no time to fix it yet. Correct deletion in a trie, with the merge of the remaining nodes, is a rather complicated task. It's much more complicated than inserts, updates and selects

[bladchan]

Got it!
Thanks for your quick replying.
I'll close this issue.