Bug #4808
closed
Improper seeding of PRNG
100%
Description
ndn::random::generateWord64() is using an improperly seeded PRNG. It is seeded with only a single uint32_t.
Updated by Junxiao Shi almost 6 years ago
Even since we increased entropy, GoodnessOfFit for generateWord64 function appears to have higher failure rate. However, the problem doesn't seem to be entropy. I used this script to run the test 1000 times on ndn-cxx:commit:c53df03ff33bcfc59d6630b6f8aaa9e3d5eaada9 and its modifications:
SUCC=0
FAIL=0
for I in $(seq 1000); do
if build/unit-tests -t 'Util/TestRandom/Goodness*'; then
SUCC=$((SUCC+1))
else
FAIL=$((FAIL+1))
fi
done
echo $SUCC $FAIL
- Seed with 256-bit entropy: SUCC=827 FAIL=173
- Seed with 32-bit entropy: SUCC=836 FAIL=164
- Seed with 20480-bit entropy: SUCC=848 FAIL=152
Updated by Junxiao Shi almost 6 years ago
- % Done changed from 70 to 100
git bisect pinpoints the offending commit to be ndn-cxx:commit:8db61525569e924752caafceeb9004951f43336e. Then I notice that before that commit, the tests were BOOST_WARN_* so they can never fail.
I read about K-S test and found that they were not implemented correctly. In particular, the previous implementation places samples into bins before calling K-S test. It appeared to be a mix-up between K-S test and Chi-Square test.
I reimplemented K-S test in https://gerrit.named-data.net/5131 patchset 2. I also tried Chi-Square test earlier but it does not work well with fewer than 64 million samples.
I tested my current implementation. It failed 1 time of 10000 executions.
Updated by Davide Pesavento almost 6 years ago
Junxiao Shi wrote:
Even since we increased entropy,
GoodnessOfFitforgenerateWord64function appears to have higher failure rate.
No, I simply changed BOOST_WARN_LE to BOOST_CHECK_LE. BOOST_WARN_* doesn't make the test fail, so it was pointless and was not actually testing anything. The GoodnessOfFit test has always been semi-broken.
Updated by Junxiao Shi almost 6 years ago
The GoodnessOfFit test has always been semi-broken.
Yes, but the solution should be fixing it, not deleting it and losing test coverage.
Updated by Alex Afanasyev almost 6 years ago
Jan 21, 2018 NDN platform call decided to delete the GoodnessOfFit test cases.
Updated by Davide Pesavento almost 6 years ago
- Status changed from In Progress to Closed
- Assignee changed from Junxiao Shi to Davide Pesavento
- Start date deleted (
01/18/2019)
Updated by Junxiao Shi almost 6 years ago
:-(
My "protest" will be no new Changes to this repository for 5 days, counting from Jan 18.