From fb183076a3a6580a4aba435c53ce033ef89e7fe6 Mon Sep 17 00:00:00 2001 From: Denys Vlasenko Date: Thu, 13 Mar 2014 12:52:43 +0100 Subject: ash,hush: improve randomness of $RANDOM, add easy-ish way to test it function old new delta next_random 68 113 +45 change_random 103 121 +18 Signed-off-by: Denys Vlasenko --- shell/random.c | 136 +++++++++++++++++++++++++++++++++++++++++++++++++++------ shell/random.h | 16 +++++-- 2 files changed, 135 insertions(+), 17 deletions(-) (limited to 'shell') diff --git a/shell/random.c b/shell/random.c index 853ab085a..9a64f54b0 100644 --- a/shell/random.c +++ b/shell/random.c @@ -6,17 +6,51 @@ * * Licensed under GPLv2, see file LICENSE in this source tree. */ -#include "libbb.h" -#include "random.h" + +/* For testing against dieharder, you need only random.{c,h} + * Howto: + * gcc -O2 -Wall -DRANDTEST random.c -o random + * ./random | dieharder -g 200 -a + */ + +#if !defined RANDTEST + +# include "libbb.h" +# include "random.h" +# define RAND_BASH_MASK 0x7fff + +#else +# include +# include +# include +# include +# define RAND_BASH_MASK 0xffffffff /* off */ +# define FAST_FUNC /* nothing */ +# define PUSH_AND_SET_FUNCTION_VISIBILITY_TO_HIDDEN /* nothing */ +# define POP_SAVED_FUNCTION_VISIBILITY /* nothing */ +# define monotonic_us() time(NULL) +# include "random.h" +#endif uint32_t FAST_FUNC next_random(random_t *rnd) { - /* Galois LFSR parameter */ - /* Taps at 32 31 29 1: */ + /* Galois LFSR parameter: + * Taps at 32 31 29 1: + */ enum { MASK = 0x8000000b }; /* Another example - taps at 32 31 30 10: */ - /* MASK = 0x00400007 */ + /* enum { MASK = 0x00400007 }; */ + + /* Xorshift parameters: + * Choices for a,b,c: 10,13,10; 8,9,22; 2,7,3; 23,3,24 + * (given by algorithm author) + */ + enum { + a = 2, + b = 7, + c = 3, + }; uint32_t t; @@ -27,18 +61,94 @@ next_random(random_t *rnd) INIT_RANDOM_T(rnd, getpid(), monotonic_us()); } - /* LCG has period of 2^32 and alternating lowest bit */ + /* LCG: period of 2^32, but quite weak: + * bit 0 alternates beetween 0 and 1 (pattern of length 2) + * bit 1 has a repeating pattern of length 4 + * bit 2 has a repeating pattern of length 8 + * etc... + */ rnd->LCG = 1664525 * rnd->LCG + 1013904223; - /* Galois LFSR has period of 2^32-1 = 3 * 5 * 17 * 257 * 65537 */ + + /* Galois LFSR: + * period of 2^32-1 = 3 * 5 * 17 * 257 * 65537. + * Successive values are right-shifted one bit + * and possibly xored with a sparse constant. + */ t = (rnd->galois_LFSR << 1); if (rnd->galois_LFSR < 0) /* if we just shifted 1 out of msb... */ t ^= MASK; rnd->galois_LFSR = t; - /* Both are weak, combining them gives better randomness - * and ~2^64 period. & 0x7fff is probably bash compat - * for $RANDOM range. Combining with subtraction is - * just for fun. + and ^ would work equally well. */ - t = (t - rnd->LCG) & 0x7fff; - return t; + /* http://en.wikipedia.org/wiki/Xorshift + * Period 2^64-1 = 3 * 715827883 * 2147483647 + * Moderately good statistical properties: + * fails the following "dieharder -g 200 -a" tests: + * diehard_operm5| 0 + * diehard_oqso| 0 + * diehard_count_1s_byt| 0 + * diehard_3dsphere| 3 + * diehard_squeeze| 0 + * diehard_runs| 0 + * diehard_runs| 0 + * diehard_craps| 0 + * diehard_craps| 0 + * rgb_minimum_distance| 3 + * rgb_minimum_distance| 4 + * rgb_minimum_distance| 5 + * rgb_permutations| 3 + * rgb_permutations| 4 + * rgb_permutations| 5 + * dab_filltree| 32 + * dab_filltree| 32 + * dab_monobit2| 12 + */ + t = rnd->xs64_x ^ (rnd->xs64_x << a); + rnd->xs64_x = rnd->xs64_y; + rnd->xs64_y = rnd->xs64_y ^ (rnd->xs64_y >> c) ^ t ^ (t >> b); + + /* Combined LCG + Galois LFSR have 2^32 * 2^32-1 period. + * Strength: + * individually, both are extremely weak cryptographycally; + * when combined, they fail the following "dieharder -g 200 -a" tests: + * diehard_rank_6x8| 0 + * diehard_oqso| 0 + * diehard_dna| 0 + * diehard_count_1s_byt| 0 + * rgb_bitdist| 2 + * dab_monobit2| 12 + * + * Combining them with xorshift-64 increases period to + * 2^32 * 2^32-1 * 2^64-1 / 3 + * (2^32-1 and 2^64-1 have one common divisor 3, hence "/ 3" part), + * which is about 2^128 / 3, or in base 10 ~1.13*10^38. + * Strength of the combination: + * passes all "dieharder -g 200 -a" tests. + * + * Combining with subtraction and addition is just for fun. + * It does not add meaningful strength, could use xor operation instead. + */ + t = rnd->galois_LFSR - rnd->LCG + rnd->xs64_y; + + /* bash compat $RANDOM range: */ + return t & RAND_BASH_MASK; } + +#ifdef RANDTEST +static random_t rnd; + +int main(int argc, char **argv) +{ + int i; + int buf[4096]; + + for (;;) { + for (i = 0; i < sizeof(buf) / sizeof(buf[0]); i++) { + buf[i] = next_random(&rnd); + } + write(1, buf, sizeof(buf)); + } + + return 0; +} + +#endif diff --git a/shell/random.h b/shell/random.h index 180c48abb..c4eb44c13 100644 --- a/shell/random.h +++ b/shell/random.h @@ -12,16 +12,24 @@ PUSH_AND_SET_FUNCTION_VISIBILITY_TO_HIDDEN typedef struct random_t { - /* Random number generators */ - int32_t galois_LFSR; /* Galois LFSR (fast but weak). signed! */ - uint32_t LCG; /* LCG (fast but weak) */ + /* State of random number generators: */ + + /* Galois LFSR (fast but weak) */ + int32_t galois_LFSR; /* must be signed! */ + + /* LCG (fast but weak) */ + uint32_t LCG; + + /* 64-bit xorshift (fast, moderate strength) */ + uint32_t xs64_x; + uint32_t xs64_y; } random_t; #define UNINITED_RANDOM_T(rnd) \ ((rnd)->galois_LFSR == 0) #define INIT_RANDOM_T(rnd, nonzero, v) \ - ((rnd)->galois_LFSR = (nonzero), (rnd)->LCG = (v)) + ((rnd)->galois_LFSR = (rnd)->xs64_x = (nonzero), (rnd)->LCG = (rnd)->xs64_y = (v)) #define CLEAR_RANDOM_T(rnd) \ ((rnd)->galois_LFSR = 0) -- cgit v1.2.3-55-g6feb From f93187512d0a8db6b7160088d3d0b325dd83c937 Mon Sep 17 00:00:00 2001 From: Denys Vlasenko Date: Thu, 13 Mar 2014 13:03:27 +0100 Subject: random: cosmetic tweaks in debug code Signed-off-by: Denys Vlasenko --- shell/random.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'shell') diff --git a/shell/random.c b/shell/random.c index 9a64f54b0..fc2dfc26d 100644 --- a/shell/random.c +++ b/shell/random.c @@ -24,12 +24,12 @@ # include # include # include -# define RAND_BASH_MASK 0xffffffff /* off */ # define FAST_FUNC /* nothing */ # define PUSH_AND_SET_FUNCTION_VISIBILITY_TO_HIDDEN /* nothing */ # define POP_SAVED_FUNCTION_VISIBILITY /* nothing */ # define monotonic_us() time(NULL) # include "random.h" +# define RAND_BASH_MASK 0xffffffff /* off */ #endif uint32_t FAST_FUNC @@ -139,7 +139,7 @@ static random_t rnd; int main(int argc, char **argv) { int i; - int buf[4096]; + uint32_t buf[4096]; for (;;) { for (i = 0; i < sizeof(buf) / sizeof(buf[0]); i++) { -- cgit v1.2.3-55-g6feb From 2bba591991f5ac9b97582e37375dd49492c63df0 Mon Sep 17 00:00:00 2001 From: Denys Vlasenko Date: Fri, 14 Mar 2014 12:43:57 +0100 Subject: hush: make "true" built-in Signed-off-by: Denys Vlasenko --- shell/hush.c | 1 + 1 file changed, 1 insertion(+) (limited to 'shell') diff --git a/shell/hush.c b/shell/hush.c index 927193450..7b0ea8b0c 100644 --- a/shell/hush.c +++ b/shell/hush.c @@ -944,6 +944,7 @@ static const struct built_in_command bltins1[] = { BLTIN("source" , builtin_source , "Run commands in a file"), #endif BLTIN("trap" , builtin_trap , "Trap signals"), + BLTIN("true" , builtin_true , NULL), BLTIN("type" , builtin_type , "Show command type"), BLTIN("ulimit" , shell_builtin_ulimit , "Control resource limits"), BLTIN("umask" , builtin_umask , "Set file creation mask"), -- cgit v1.2.3-55-g6feb From ac03a40cbac4545909b6529d358c253f8a6d3b45 Mon Sep 17 00:00:00 2001 From: Denys Vlasenko Date: Sat, 15 Mar 2014 09:25:46 +0100 Subject: ash,hush: fix a thinko about 2^64-1 factorization function old new delta next_random 113 119 +6 Signed-off-by: Denys Vlasenko --- shell/random.c | 16 +++++++++++----- 1 file changed, 11 insertions(+), 5 deletions(-) (limited to 'shell') diff --git a/shell/random.c b/shell/random.c index fc2dfc26d..5d3620516 100644 --- a/shell/random.c +++ b/shell/random.c @@ -80,7 +80,6 @@ next_random(random_t *rnd) rnd->galois_LFSR = t; /* http://en.wikipedia.org/wiki/Xorshift - * Period 2^64-1 = 3 * 715827883 * 2147483647 * Moderately good statistical properties: * fails the following "dieharder -g 200 -a" tests: * diehard_operm5| 0 @@ -102,11 +101,19 @@ next_random(random_t *rnd) * dab_filltree| 32 * dab_monobit2| 12 */ + again: t = rnd->xs64_x ^ (rnd->xs64_x << a); rnd->xs64_x = rnd->xs64_y; rnd->xs64_y = rnd->xs64_y ^ (rnd->xs64_y >> c) ^ t ^ (t >> b); + /* + * Period 2^64-1 = 2^32+1 * 2^32-1 has a common divisor with Galois LFSR. + * By skipping two possible states (0x1 and 0x2) we reduce period to + * 2^64-3 = 13 * 3889 * 364870227143809 which has no common divisors: + */ + if (rnd->xs64_y == 0 && rnd->xs64_x <= 2) + goto again; - /* Combined LCG + Galois LFSR have 2^32 * 2^32-1 period. + /* Combined LCG + Galois LFSR rng has 2^32 * 2^32-1 period. * Strength: * individually, both are extremely weak cryptographycally; * when combined, they fail the following "dieharder -g 200 -a" tests: @@ -118,9 +125,8 @@ next_random(random_t *rnd) * dab_monobit2| 12 * * Combining them with xorshift-64 increases period to - * 2^32 * 2^32-1 * 2^64-1 / 3 - * (2^32-1 and 2^64-1 have one common divisor 3, hence "/ 3" part), - * which is about 2^128 / 3, or in base 10 ~1.13*10^38. + * 2^32 * 2^32-1 * 2^64-3 + * which is about 2^128, or in base 10 ~3.40*10^38. * Strength of the combination: * passes all "dieharder -g 200 -a" tests. * -- cgit v1.2.3-55-g6feb From 109ee5d33694a03cda3424b4846584250832ba8e Mon Sep 17 00:00:00 2001 From: Denys Vlasenko Date: Sun, 16 Mar 2014 18:41:11 +0100 Subject: ash: make "locak VAR" unset VAR (bash does that) Signed-off-by: Denys Vlasenko --- shell/ash.c | 3 +++ shell/ash_test/ash-misc/local1.right | 4 ++++ shell/ash_test/ash-misc/local1.tests | 11 +++++++++++ 3 files changed, 18 insertions(+) create mode 100644 shell/ash_test/ash-misc/local1.right create mode 100755 shell/ash_test/ash-misc/local1.tests (limited to 'shell') diff --git a/shell/ash.c b/shell/ash.c index 04ba447b1..7a097c814 100644 --- a/shell/ash.c +++ b/shell/ash.c @@ -8960,6 +8960,9 @@ mklocal(char *name) vp->flags |= VSTRFIXED|VTEXTFIXED; if (eq) setvareq(name, 0); + else + /* "local VAR" unsets VAR: */ + setvar(name, NULL, 0); } } lvp->vp = vp; diff --git a/shell/ash_test/ash-misc/local1.right b/shell/ash_test/ash-misc/local1.right new file mode 100644 index 000000000..a2d121df6 --- /dev/null +++ b/shell/ash_test/ash-misc/local1.right @@ -0,0 +1,4 @@ +A1:'A' +A2:'' +A3:'' +A4:'A' diff --git a/shell/ash_test/ash-misc/local1.tests b/shell/ash_test/ash-misc/local1.tests new file mode 100755 index 000000000..b1e675059 --- /dev/null +++ b/shell/ash_test/ash-misc/local1.tests @@ -0,0 +1,11 @@ +a=A +f() { + local a + # the above line unsets $a + echo "A2:'$a'" + unset a + echo "A3:'$a'" +} +echo "A1:'$a'" +f +echo "A4:'$a'" -- cgit v1.2.3-55-g6feb From 3fa97af7ccc75264fb237f279f253eddf0ba4da1 Mon Sep 17 00:00:00 2001 From: Denys Vlasenko Date: Tue, 15 Apr 2014 11:43:29 +0200 Subject: ash,hush: set $HOSTNAME is bash compat. Closes 7028 function old new delta hush_main 1056 1128 +72 ash_main 1442 1487 +45 Signed-off-by: Denys Vlasenko --- shell/ash.c | 6 ++++++ shell/hush.c | 11 ++++++++++- 2 files changed, 16 insertions(+), 1 deletion(-) (limited to 'shell') diff --git a/shell/ash.c b/shell/ash.c index 7a097c814..cabeb40c5 100644 --- a/shell/ash.c +++ b/shell/ash.c @@ -41,6 +41,7 @@ #include #include #include +#include /* for setting $HOSTNAME */ #include "busybox.h" /* for applet_names */ #include "unicode.h" @@ -13018,6 +13019,11 @@ init(void) #if ENABLE_ASH_BASH_COMPAT p = lookupvar("SHLVL"); setvar("SHLVL", utoa((p ? atoi(p) : 0) + 1), VEXPORT); + if (!lookupvar("HOSTNAME")) { + struct utsname uts; + uname(&uts); + setvar2("HOSTNAME", uts.nodename); + } #endif p = lookupvar("PWD"); if (p) { diff --git a/shell/hush.c b/shell/hush.c index 7b0ea8b0c..e1d0ece29 100644 --- a/shell/hush.c +++ b/shell/hush.c @@ -91,6 +91,7 @@ #if ENABLE_HUSH_CASE # include #endif +#include /* for setting $HOSTNAME */ #include "busybox.h" /* for APPLET_IS_NOFORK/NOEXEC */ #include "unicode.h" @@ -7786,6 +7787,14 @@ int hush_main(int argc, char **argv) /* Export PWD */ set_pwd_var(/*exp:*/ 1); + +#if ENABLE_HUSH_BASH_COMPAT + /* Set (but not export) HOSTNAME unless already set */ + if (!get_local_var_value("HOSTNAME")) { + struct utsname uts; + uname(&uts); + set_local_var_from_halves("HOSTNAME", uts.nodename); + } /* bash also exports SHLVL and _, * and sets (but doesn't export) the following variables: * BASH=/bin/bash @@ -7794,7 +7803,6 @@ int hush_main(int argc, char **argv) * HOSTTYPE=i386 * MACHTYPE=i386-pc-linux-gnu * OSTYPE=linux-gnu - * HOSTNAME= * PPID= - we also do it elsewhere * EUID= * UID= @@ -7822,6 +7830,7 @@ int hush_main(int argc, char **argv) * PS2='> ' * PS4='+ ' */ +#endif #if ENABLE_FEATURE_EDITING G.line_input_state = new_line_input_t(FOR_SHELL); -- cgit v1.2.3-55-g6feb