Wallet Test Fails, Segmentation Fault

[cadaniluk]

_{(Repost from jonasschnelli/libbtc with minor adjustments.)}

Bug Report

Built with ./autogen.sh && ./configure --enable-debug && make check.
Uncommented the wallet test in test/unittester.c, which was commented out for some reason in commit 9dda1cf9.

Running tests with ./tests:

PASSED - test_sha_256()
PASSED - test_sha_512()
PASSED - test_sha_hmac()
PASSED - test_utils()
PASSED - test_cstr()
PASSED - test_buffer()
PASSED - test_serialize()
PASSED - test_memory()
PASSED - test_random()
PASSED - test_bitcoin_hash()
PASSED - test_base58check()
PASSED - test_aes()
PASSED - test_bip32()
PASSED - test_ecc()
PASSED - test_vector()
PASSED - test_tx_serialization()
PASSED - test_invalid_tx_deser()
PASSED - test_tx_sign()
PASSED - test_tx_sighash()
PASSED - test_tx_sighash_ext()
PASSED - test_tx_negative_version()
PASSED - test_block_header()
PASSED - test_script_parse()
PASSED - test_script_op_codeseperator()
PASSED - test_eckey()
xpriv: xprv9uHRZZhk6KAJC1avXpDAp4MDc3sQKNxDiPvvkX8Br5ngLNv1TxvUxt4cV1rGL5hj6KCesnDYUhd7oWgT11eZG7XnxHrnYeSvkzY7d2bhkJ7
Segmentation fault (core dumped)

test-suite.log:

============================================================================
Testsuite summary for libbtc 0.1
============================================================================
# TOTAL: 1
# PASS:  0
# SKIP:  0
# XFAIL: 0
# FAIL:  1
# XPASS: 0
# ERROR: 0
============================================================================
See ./test-suite.log
Please report to https://github.com/jonasschnelli/libbtc/issues
============================================================================

System Info:
OS: Fedora 27, 64-Bit
uname -r: 4.15.15-300.fc27.x86_64
gdb version: GNU gdb (GDB) Fedora 8.0.1-36.fc27
glibc 2.26

Analysis

Running the tests program with gdb (gdb ./tests) yields the following stack trace:

#0  btc_wallet_free (wallet=0xdc9ab0) at src/wallet.c:245
#1  0x000000000040911a in test_wallet () at test/wallet_tests.c:36
#2  0x0000000000401ce6 in main () at test/unittester.c:117

After experimenting a bit, I found that after the insertion performed by tsearch, the left node pointer is 0x1, unlike the right one, which is 0x0.
This is because, as explained in a comment in misc/tsearch.c, if malloc returns aligned addresses, the lower bits of the left node's address are zero anyway and can be used to store whether the node is a red or a black one in the LSB. The definition of SETLEFT in that case, the macro used to set the left node's value, is defined as:

#define SETLEFT(N,L) (N)->left_node = (((N)->left_node & (uintptr_t) 0x1) \
| (uintptr_t)(L))

In btc_btree_tdestroy:63 in file include/btc/utils.h the tree is destroyed recursively, but the base case is r == 0, so if the node from the red-black tree is red, but has no children, this check might fail and the function could end up destroying a pointer with value 0x1, which has undefined behavior and might result in a segmentation fault, as it does in my case.

Solution

The easy fix is to check for r == 0 || (uintptr_t) r == 1 instead of just r == 0 and clearing the LSB of r afterwards, but then you rely on the implementation of tsearch. I would not write it like that.
(r == NULL seems cleaner to me anyway.)

I just discovered this comments:

/* support substitude for GNU only tdestroy */
/* Let's hope the node struct is always compatible */

With this patch, they introduced a compile-time switch, which, if possible, includes the color bit in the left node, rendering the r == 0 insufficient. If the compiler determines that this is not possible, because malloc returns unaligned addresses, a separate struct member to indicate whether the node is red or black. Either way, the code is not well-defined: either the check fails and it ends up trying to destroy the address 0x1, which is undefined, or your struct is not compatible because of the additional red/black flag, also rendering the code undefined.

The cleanest way would probably be to quit using tsearch and friends and rolling your own red-black tree implementation entirely. tsearch is only supposed to be, and can, in a clean, portable way, only be used together with the other functions of the <search.h> interface and if you opt against using the other functions, it does not make sense to use tsearch either, I think.

[jonasschnelli]

Thanks for the report!
I try to take a closer look soon.