Project

General

Profile

Bug #4808

Improper seeding of PRNG

Added by Junxiao Shi 7 months ago. Updated 7 months ago.

Status:
Closed
Priority:
Normal
Category:
Utils
Target version:
Start date:
Due date:
% Done:

100%

Estimated time:
3.00 h

Description

ndn::random::generateWord64() is using an improperly seeded PRNG. It is seeded with only a single uint32_t.

History

#1 Updated by Junxiao Shi 7 months 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

#2 Updated by Junxiao Shi 7 months 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.

#3 Updated by Davide Pesavento 7 months ago

Junxiao Shi wrote:

Even since we increased entropy, GoodnessOfFit for generateWord64 function 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.

#4 Updated by Junxiao Shi 7 months ago

The GoodnessOfFit test has always been semi-broken.

Yes, but the solution should be fixing it, not deleting it and losing test coverage.

#5 Updated by Alex Afanasyev 7 months ago

Jan 21, 2018 NDN platform call decided to delete the GoodnessOfFit test cases.

#6 Updated by Davide Pesavento 7 months ago

  • Status changed from In Progress to Closed
  • Assignee changed from Junxiao Shi to Davide Pesavento
  • Start date deleted (01/18/2019)

#7 Updated by Junxiao Shi 7 months ago

:-(

My "protest" will be no new Changes to this repository for 5 days, counting from Jan 18.

Also available in: Atom PDF