Bug #4808: Improper seeding of PRNG - ndn-cxx - NDN project issue tracking system

Bug #4808

closed

Improper seeding of PRNG

Added by Junxiao Shi almost 6 years ago. Updated almost 6 years ago.

Status:

Closed

Priority:

Normal

Assignee:

Davide Pesavento

Category:

Utils

Target version:

v0.7

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
Notes
Property changes

Actions

Copy link

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

Actions

Copy link

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.

Actions

Copy link

Updated by Davide Pesavento almost 6 years 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.

Actions

Copy link