Assaf Gordon wrote, On 03/08/2013 04:28 PM: > Pádraig Brady wrote, On 03/07/2013 06:26 PM: >> >> Cool, I was considering testing with rngtest or something, so it'll >> be good to have something independent. > ( http://lists.gnu.org/archive/html/coreutils/2013-03/msg00030.html ) > > Using rngtest is probably much more reliable than the independent test - > attached are tests for sort and shuf with rngtest. > They are marked 'expensive' as they require an external program and they run > each test 10 times.
Same patch, rebased with the latest shuf/reservoir-sampling, and with "require_rngtest_" added to "init.cfg". -gordon
>From c4130abf2baf1f1484c9f72e0d2845b996d55210 Mon Sep 17 00:00:00 2001 From: Assaf Gordon <[email protected]> Date: Fri, 8 Mar 2013 15:54:24 -0500 Subject: [PATCH] tests: test sort,shuf with rngtest rngtest check the randomness of data using FIPS 140-2 tests. http://sourceforge.net/projects/gkernel/ If rngtest is not installed (and available in the PATH), the tests will be skipped. These tests are marked 'expensive'. To run directly: $ make check TESTS=tests/misc/sort-rand-rngtest.sh \ SUBDIRS=. RUN_EXPENSIVE_TESTS=yes $ make check TESTS=tests/misc/shuf-rand-rngtest.sh \ SUBDIRS=. RUN_EXPENSIVE_TESTS=yes * tests/misc/shuf-rand-rngtest.sh - test shuf with rngtest. * tests/misc/sort-rand-rngtest.sh - test sort with rngtest. * tests/local.mk - add above tests. * init.cfg - add 'require_rngtest_' function. --- init.cfg | 7 ++++ tests/local.mk | 2 + tests/misc/shuf-rand-rngtest.sh | 75 +++++++++++++++++++++++++++++++++++++++ tests/misc/sort-rand-rngtest.sh | 68 +++++++++++++++++++++++++++++++++++ 4 files changed, 152 insertions(+), 0 deletions(-) create mode 100755 tests/misc/shuf-rand-rngtest.sh create mode 100755 tests/misc/sort-rand-rngtest.sh diff --git a/init.cfg b/init.cfg index afee930..27d7627 100644 --- a/init.cfg +++ b/init.cfg @@ -169,6 +169,13 @@ require_valgrind_() skip_ "requires a working valgrind" } +# Skip the current test if rngtest doesn't work +require_rngtest_() +{ + rngtest -V 2>/dev/null || + skip_ "requires a working rngtest" +} + require_setfacl_() { setfacl -m user::rwx . \ diff --git a/tests/local.mk b/tests/local.mk index dc87ef4..a75cfa3 100644 --- a/tests/local.mk +++ b/tests/local.mk @@ -313,6 +313,7 @@ all_tests = \ tests/misc/shred-passes.sh \ tests/misc/shred-remove.sh \ tests/misc/shuf.sh \ + tests/misc/shuf-rand-rngtest.sh \ tests/misc/shuf-reservoir.sh \ tests/misc/sort.pl \ tests/misc/sort-benchmark-random.sh \ @@ -330,6 +331,7 @@ all_tests = \ tests/misc/sort-month.sh \ tests/misc/sort-exit-early.sh \ tests/misc/sort-rand.sh \ + tests/misc/sort-rand-rngtest.sh \ tests/misc/sort-spinlock-abuse.sh \ tests/misc/sort-stale-thread-mem.sh \ tests/misc/sort-unique.sh \ diff --git a/tests/misc/shuf-rand-rngtest.sh b/tests/misc/shuf-rand-rngtest.sh new file mode 100755 index 0000000..934791f --- /dev/null +++ b/tests/misc/shuf-rand-rngtest.sh @@ -0,0 +1,75 @@ +#!/bin/sh +# Test shuf's random output with rngtest +# +# NOTE: +# rngtest must be installed, or the test will be skipped. +# rngtest is available here: http://sourceforge.net/projects/gkernel/ + +# Copyright (C) 2013 Free Software Foundation, Inc. + +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation, either version 3 of the License, or +# (at your option) any later version. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. + +# You should have received a copy of the GNU General Public License +# along with this program. If not, see <http://www.gnu.org/licenses/>. + +. "${srcdir=.}/tests/init.sh"; path_prepend_ ./src +print_ver_ shuf +expensive_ +require_rngtest_ + +# Test for randomness several times. +# On the reare occasion when the randomly sorted data doesn't pass rngtest, +# it should be just one failure out of 10 rounds. +# If more rounds fail in a single run - there's likely a real problem. +ROUNDS=10 + +( yes 1 | head -n 10000 ; yes 0 | head -n 10000 ) > in || framework_failure_ + +# rgntest always reads the first 32 bits as bootstrap data +printf "\x00\x00\x00\x00" > rngtest_header || framework_failure_ + + +# Sanity check: +# unsorted data should not be random +cat in | tr -d '\n' | \ + perl -npe '$_=pack("b*",$_)' > out_non_random || framework_failure_ + +echo "Testing rngtest on non-random input:" 1>&2 +cat rngtest_header out_non_random | rngtest && + { fail=1 ; echo "rngtest failed to detect non-random data." 1>&2 ; } + +# +# Check randomness of shuf's output +# (using the 'read-entire-file' code path) +for i in $(seq $ROUNDS) ; do + cat in | shuf | tr -d '\n' | \ + perl -npe '$_=pack("b*",$_)' > out_random$i || framework_failure_ + + echo "Testing rngtest on randomly-sorted input (round $i of $ROUNDS):" 1>&2 + cat rngtest_header out_random$i | rngtest || + { fail=1 ; echo "shuf random output did not pass rngtest" \ + " (round $i of $ROUNDS)." 1>&2 ; } +done + +# +# Check randomness of shuf's output +# (using the '--head-count=N' code path) +for i in $(seq $ROUNDS) ; do + cat 'in' 'in' 'in' 'in' | shuf -n 20000 | tr -d '\n' | \ + perl -npe '$_=pack("b*",$_)' > out_n_random$i || framework_failure_ + + echo "Testing rngtest on randomly-sorted input (round $i of $ROUNDS):" 1>&2 + cat rngtest_header out_n_random$i | rngtest || + { fail=1 ; echo "shuf -n random output did not pass rngtest" \ + " (round $i of $ROUNDS)." 1>&2 ; } +done + +Exit $fail diff --git a/tests/misc/sort-rand-rngtest.sh b/tests/misc/sort-rand-rngtest.sh new file mode 100755 index 0000000..ac6b9ba --- /dev/null +++ b/tests/misc/sort-rand-rngtest.sh @@ -0,0 +1,68 @@ +#!/bin/sh +# Test sort's random output with rngtest +# +# NOTE: +# rngtest must be installed, or the test will be skipped. +# rngtest is available here: http://sourceforge.net/projects/gkernel/ + +# Copyright (C) 2013 Free Software Foundation, Inc. + +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation, either version 3 of the License, or +# (at your option) any later version. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. + +# You should have received a copy of the GNU General Public License +# along with this program. If not, see <http://www.gnu.org/licenses/>. + +. "${srcdir=.}/tests/init.sh"; path_prepend_ ./src +print_ver_ sort +expensive_ +require_rngtest_ + +# Test for randomness several times. +# On the reare occasion when the randomly sorted data doesn't pass rngtest, +# it should be just one failure out of 10 rounds. +# If more rounds fail in a single run - there's likely a real problem. +ROUNDS=10 + +# NOTE: +# We sort 20000 integers, but use only their LSB for the test. +# Before sorting, their LSB should not be random (alternating 0/1 for odd/even +# integers). After sorting, the LSBs should be randomly ordered. +seq 1 20000 > in || framework_failure_ + +# rgntest always reads the first 32 bits as bootstrap data +printf "\x00\x00\x00\x00" > rngtest_header || framework_failure_ + + + +# Sanity check: +# unsorted data should not be random +cat in | awk '{printf "%d",and($0,1)}' | \ + perl -npe '$_=pack("b*",$_)' > out_non_random || framework_failure_ + +echo "Testing rngtest on non-random input:" 1>&2 +cat rngtest_header out_non_random | rngtest && + { fail=1 ; echo "rngtest failed to detect non-random data." 1>&2 ; } + + +# +# Check randomness of sort's random +# +for i in $(seq $ROUNDS) ; do + cat in | sort --random-sort | awk '{printf "%d",and($0,1)}' | \ + perl -npe '$_=pack("b*",$_)' > out_random$i || framework_failure_ + + echo "Testing rngtest on randomly-sorted input (round $i of $ROUNDS):" 1>&2 + cat rngtest_header out_random$i | rngtest || + { fail=1 ; echo "sort random output did not pass rngtest" \ + " (round $i of $ROUNDS)." 1>&2 ; } +done + +Exit $fail -- 1.7.7.4
