QP lookup() points iterator to an incorrect predecesor
Summary
QP trie with specific content leads to invalid iterator position after a lookup(). See below.
BIND version affected
Steps to reproduce
High-level: 0. Create an empty dns_qp_t.
- insert name
. - insert name
\000. - insert name
\000.\000. - insert name
\000\009.
At this point the QP should contain names - in DNSSEC-order - [., \000., \000.\000., \000\009.].
-
lookup() name
\007.and provide iterator Expected return code = DNS_R_PARTIALMATCH - that's okay. -
call dns_qpiter_current() on the returned iterator.
What is the current bug behavior?
In my tests it seems to point to name \000.\000.
What is the expected correct behavior?
I believe it should be pointing to name \000\009.
Hacky code reproducer
This is extremely ugly and very much work in progress. It is sort of "fuzzer" which wraps our libdns in C into a state machine written in Python, and uses library Python hypothesis to verify that all state transitions produce expected results. In pratical terms in compares behavior of our libdns with approximation based on dnspython library.
Usage: 0. Compile and install BIND version under test.
- Install python-cffi library
cd tests/dns- python qp_test_pythonbuild.py # compiles Python-C glue library
Execute the failing test case:
cd tests/dns- LD_PRELOAD=/usr/lib/libjemalloc.so.2 python qp_test.py
Execute fuzzing machinery:
cd tests/dnsLD_PRELOAD=/usr/lib/libjemalloc.so.2 pytest qp_test.py --hypothesis-show-statistics -k TestTrees
It might take ~ 10 minutes until it fails. If it succeeds run it again :-) It's doing pseudo-random walk through various QP-related operations so it might not find bugs right away.
When it fails it might or might not print a nice test case - it's random after all. In case of failure the text output should give you an idea about sequence of steps it tried in sort-of human terms. Beware - the text output typically contains dozens of "retries" from clean state. Read carefully and start with the last one.