InterleavedSearcher: choose() called on empty tree during recovery

[jordr]

~~TODO: try to reproduce with legacy Chopper ~~
E: this is a KLEE bug

❯ klee --skip-functions-not=open_new_file --split-search -libc=uclibc --posix-runtime --allow-external-sym-calls bc.bc --sym-args 0 8 16 --sym-files 1 64 --sym-stdin 8 --sym-stdout
[dc58bf] KLEE: ■  __uClibc_main
[dc58bf] KLEE: ■ ■  memset
[dc58bf] KLEE: ■ ■  __uClibc_init
[dc58bf] KLEE: ■ ■ ■  _stdio_init
[dc58bf] KLEE: ■ ■ ■ ■  isatty
[dc58bf] KLEE: ■ ■ ■ ■ ■  tcgetattr
[6e6b35] KLEE: ■ ■ ■ ■ ■ ■  __wrap_ioctl (skipped)
[dc58bf] KLEE: ■ ■ ■ ■ ■ ■  mempcpy
[dc58bf] KLEE: ■ ■ ■ ■ ■ ■  memset
[dc58bf] KLEE: ■ ■ ■ ■  isatty
[dc58bf] KLEE: ■ ■ ■ ■ ■  tcgetattr
[6e6b35] KLEE: ■ ■ ■ ■ ■ ■  __wrap_ioctl (skipped)
[dc58bf] KLEE: ■ ■ ■ ■ ■ ■  mempcpy
[dc58bf] KLEE: ■ ■ ■ ■ ■ ■  memset
[dc58bf] KLEE: ■ ■  strrchr
[dc58bf] KLEE: ■ ■  __errno_location
[dc58bf] KLEE: ■ ■  __h_errno_location
[dc58bf] KLEE: ■ ■  __user_main
[3254a2] KLEE: WARNING ONCE: calling __user_main with extra arguments. (from __uClibc_main)
[6e6b35] KLEE: ■ ■ ■  klee_init_env (skipped)
[baf203] KLEE: ■ ■ ■  klee_init_env (recovery) 
[6e6b35] KLEE: R R R  klee_init_env (skipped)
klee: /home/ubuntu/code/chopper/include/klee/Internal/ADT/DiscretePDF.inc:169: T klee::DiscretePDF<T>::choose(double) [with T = klee::ExecutionState*]: Assertion `0 && "choose: choose() called on empty tree"' failed.
klee: /home/ubuntu/code/chopper/include/klee/Internal/ADT/DiscretePDF.inc:169: T klee::DiscretePDF<T>::choose(double) [with T = klee::ExecutionState*]: Assertion `0 && "choose: choose() called on empty tree"' failed.
0  klee            0x000055b9f206a492 llvm::sys::PrintStackTrace(_IO_FILE*) + 50
1  klee            0x000055b9f2069d8c
2  libpthread.so.0 0x00007f6e1dc08890
3  libc.so.6       0x00007f6e1cad6e97 gsignal + 199
4  libc.so.6       0x00007f6e1cad8801 abort + 321
5  libc.so.6       0x00007f6e1cac839a
6  libc.so.6       0x00007f6e1cac8412
7  klee            0x000055b9f1668607 klee::DiscretePDF<klee::ExecutionState*>::choose(double) + 121
8  klee            0x000055b9f1663dd7 klee::WeightedRandomSearcher::selectState() + 41
9  klee            0x000055b9f1665fc9 klee::InterleavedSearcher::selectState() + 123
10 klee            0x000055b9f1666284 klee::SplittedSearcher::selectState() + 266
11 klee            0x000055b9f15cedff klee::Executor::run(klee::ExecutionState&) + 2033
12 klee            0x000055b9f15d48b7 klee::Executor::runFunctionAsMain(llvm::Function*, int, char**, char**) + 2235
13 klee            0x000055b9f15a35b6 main + 7838
14 libc.so.6       0x00007f6e1cab9b97 __libc_start_main + 231
15 klee            0x000055b9f159c4ca _start + 42

[jordr]

This is related to --split-search

main.c:

#include <klee/klee.h>

int global;
int a3;
void f3r()
{
    global = a3;
}

void f3w()
{
    a3 = 1;
}

int main(int argc, char *argv[]) {
    f3w(); // skip this
    f3r();

    return global;
}

kleegacy -libc=uclibc --split-search --skip-functions=f3w main.bc
KLEE: NOTE: Using klee-uclibc : /home/ubuntu/code/chopper/legacy_build/Release+Asserts/lib/klee-uclibc.bca
KLEE: output directory is "/home/ubuntu/code/chopper/examples/exrecovery/klee-out-8"
Using STP solver backend
KLEE: Runnining pointer analysis...
KLEE: Runnining reachability analysis...
KLEE: Runnining mod-ref analysis...
KLEE: WARNING: undefined reference to function: __crit_2_0
KLEE: WARNING: undefined reference to function: fcntl
KLEE: WARNING: undefined reference to function: fstat
KLEE: WARNING: undefined reference to function: ioctl
KLEE: WARNING: undefined reference to function: open
KLEE: WARNING ONCE: calling external: ioctl(0, 21505, 94642363638720)
KLEE: WARNING ONCE: calling __user_main with extra arguments.
kleegacy: /home/ubuntu/code/chopper/include/klee/Internal/ADT/DiscretePDF.inc:169: T klee::DiscretePDF<T>::choose(double) [with T = klee::ExecutionState*]: Assertion `0 && "choose: choose() called on empty tree"' failed.

kleegacy -libc=uclibc --skip-functions=f3w main.bc
KLEE: NOTE: Using klee-uclibc : /home/ubuntu/code/chopper/legacy_build/Release+Asserts/lib/klee-uclibc.bca
KLEE: output directory is "/home/ubuntu/code/chopper/examples/exrecovery/klee-out-9"
Using STP solver backend
KLEE: Runnining pointer analysis...
KLEE: Runnining reachability analysis...
KLEE: Runnining mod-ref analysis...
KLEE: WARNING: undefined reference to function: __crit_2_0
KLEE: WARNING: undefined reference to function: fcntl
KLEE: WARNING: undefined reference to function: fstat
KLEE: WARNING: undefined reference to function: ioctl
KLEE: WARNING: undefined reference to function: open
KLEE: WARNING ONCE: calling external: ioctl(0, 21505, 94718872635568)
KLEE: WARNING ONCE: calling __user_main with extra arguments.
INFO: Points-to analysis took 0 sec 0 ms
INFO: Reaching defs analysis took 0 sec 0 ms
INFO: Adding Def-Use edges took 0 sec 0 ms
INFO: Computing control dependencies took 0 sec 0 ms
INFO: Finding dependent nodes took 0 sec 0 ms
INFO: Slicing dependence graph took 0 sec 0 ms
INFO: Sliced away 1 from 4 nodes in DG
INFO: saving sliced module to: test.sliced

KLEE: done: total instructions = 3460
KLEE: done: completed paths = 1
KLEE: done: generated tests = 1
KLEE: done: recovery states = 1
KLEE: done: generated slices = 1
KLEE: done: created snapshots = 1

[jordr]

Fixed by klee/klee#1207