Make it possible to disable and control hash key traversal randomization
authorYves Orton <demerphq@gmail.com>
Sun, 5 May 2013 14:33:43 +0000 (16:33 +0200)
committerYves Orton <demerphq@gmail.com>
Tue, 7 May 2013 07:33:42 +0000 (09:33 +0200)
Adds support for PERL_PERTURB_KEYS environment variable, which in turn allows one to control
the level of randomization applied to keys() and friends.

When PERL_PERTURB_KEYS is 0 we will not randomize key order at all. The
chance that keys() changes due to an insert will be the same as in
previous perls, basically only when the bucket size is changed.

When PERL_PERTURB_KEYS is 1 we will randomize keys in a non repeatedable
way. The chance that keys() changes due to an insert will be very high.
This is the most secure and default mode.

When PERL_PERTURB_KEYS is 2 we will randomize keys in a repeatedable way.
Repititive runs of the same program should produce the same output every
time. The chance that keys changes due to an insert will be very high.

This patch also makes PERL_HASH_SEED imply a non-default
PERL_PERTURB_KEYS setting. Setting PERL_HASH_SEED=0 (exactly one 0) implies
PERL_PERTURB_KEYS=0 (hash key randomization disabled), settng PERL_HASH_SEED
to any other value, implies PERL_PERTURB_KEYS=2 (deterministic/repeatable
hash key randomization). Specifying PERL_PERTURB_KEYS explicitly to a
different level overrides this behavior.

Includes changes to allow one to compile out various aspects of the
patch. One can compile such that PERL_PERTURB_KEYS is not respected, or
can compile without hash key traversal randomization at all. Note that
support for these modes is incomplete, and currently a few tests will
fail.

Also includes a new subroutine in Hash::Util::hash_traversal_mask()
which can be used to ensure a given hash produces a predictable key
order (assuming the same hash seed is in effect). This sub acts as a
getter and a setter.

NOTE - this patch lacks tests, but I lack tuits to get them done quickly,
so I am pushing this with the hope that others can add them afterwards.

18 files changed:
dump.c
embed.fnc
embed.h
embedvar.h
ext/Hash-Util/Util.xs
ext/Hash-Util/lib/Hash/Util.pm
hv.c
hv.h
intrpvar.h
perl.c
perlvars.h
pod/perldiag.pod
pod/perlrun.pod
pod/perlsec.pod
proto.h
t/porting/globvar.t
t/porting/known_pod_issues.dat
util.c

diff --git a/dump.c b/dump.c
index b2857d3..13736d7 100644 (file)
--- a/dump.c
+++ b/dump.c
@@ -1808,12 +1808,13 @@ Perl_do_sv_dump(pTHX_ I32 level, PerlIO *file, SV *sv, I32 nest, I32 maxnest, bo
         if (SvOOK(sv)) {
            Perl_dump_indent(aTHX_ level, file, "  RITER = %"IVdf"\n", (IV)HvRITER_get(sv));
            Perl_dump_indent(aTHX_ level, file, "  EITER = 0x%"UVxf"\n", PTR2UV(HvEITER_get(sv)));
+#ifdef PERL_HASH_RANDOMIZE_KEYS
            Perl_dump_indent(aTHX_ level, file, "  RAND = 0x%"UVxf, (UV)HvRAND_get(sv));
             if (HvRAND_get(sv) != HvLASTRAND_get(sv) && HvRITER_get(sv) != -1 ) {
-               PerlIO_printf(file, " (LAST = 0x%"UVxf")\n", (UV)HvLASTRAND_get(sv));
-            } else {
-               PerlIO_putc(file, '\n');
+                PerlIO_printf(file, " (LAST = 0x%"UVxf")", (UV)HvLASTRAND_get(sv));
             }
+#endif
+            PerlIO_putc(file, '\n');
         }
        {
            MAGIC * const mg = mg_find(sv, PERL_MAGIC_symtab);
index ecdde73..c032be0 100644 (file)
--- a/embed.fnc
+++ b/embed.fnc
@@ -2435,6 +2435,7 @@ ApoR      |I32*   |hv_riter_p     |NN HV *hv
 ApoR   |HE**   |hv_eiter_p     |NN HV *hv
 Apo    |void   |hv_riter_set   |NN HV *hv|I32 riter
 Apo    |void   |hv_eiter_set   |NN HV *hv|NULLOK HE *eiter
+Ap      |void   |hv_rand_set    |NN HV *hv|U32 new_xhv_rand
 Ap     |void   |hv_name_set    |NN HV *hv|NULLOK const char *name|U32 len|U32 flags
 p      |void   |hv_ename_add   |NN HV *hv|NN const char *name|U32 len \
                                |U32 flags
diff --git a/embed.h b/embed.h
index 96309b2..9054358 100644 (file)
--- a/embed.h
+++ b/embed.h
 #define hv_iterval(a,b)                Perl_hv_iterval(aTHX_ a,b)
 #define hv_ksplit(a,b)         Perl_hv_ksplit(aTHX_ a,b)
 #define hv_name_set(a,b,c,d)   Perl_hv_name_set(aTHX_ a,b,c,d)
+#define hv_rand_set(a,b)       Perl_hv_rand_set(aTHX_ a,b)
 #define hv_scalar(a)           Perl_hv_scalar(aTHX_ a)
 #define init_i18nl10n(a)       Perl_init_i18nl10n(aTHX_ a)
 #define init_i18nl14n(a)       Perl_init_i18nl14n(aTHX_ a)
index a738dd7..e689c5e 100644 (file)
 #define PL_globalstash         (vTHX->Iglobalstash)
 #define PL_globhook            (vTHX->Iglobhook)
 #define PL_hash_rand_bits      (vTHX->Ihash_rand_bits)
+#define PL_hash_rand_bits_enabled      (vTHX->Ihash_rand_bits_enabled)
 #define PL_hintgv              (vTHX->Ihintgv)
 #define PL_hints               (vTHX->Ihints)
 #define PL_hv_fetch_ent_mh     (vTHX->Ihv_fetch_ent_mh)
index c8a692f..33bce41 100644 (file)
@@ -68,6 +68,7 @@ hash_seed()
     mXPUSHs(newSVpvn((char *)PERL_HASH_SEED,PERL_HASH_SEED_BYTES));
     XSRETURN(1);
 
+
 void
 hash_value(string)
         SV* string
@@ -81,6 +82,27 @@ hash_value(string)
     PERL_HASH(uv,pv,len);
     XSRETURN_UV(uv);
 
+void
+hash_traversal_mask(rhv, ...)
+        SV* rhv
+    PPCODE:
+{
+#ifdef PERL_HASH_RANDOMIZE_KEYS
+    if (SvROK(rhv) && SvTYPE(SvRV(rhv))==SVt_PVHV && !SvMAGICAL(SvRV(rhv))) {
+        const HV * const hv = (const HV *) SvRV(rhv);
+        if (items>1) {
+            hv_rand_set(hv, SvUV(ST(1)));
+        }
+        if (SvOOK(hv)) {
+            XSRETURN_UV(HvRAND_get(hv));
+        } else {
+            XSRETURN_UNDEF;
+        }
+    }
+#else
+    Perl_croak(aTHX_ "Perl has not been compiled with support for randomized hash key traversal");
+#endif
+}
 
 void
 bucket_info(rhv)
index 050f926..336a28e 100644 (file)
@@ -32,7 +32,7 @@ our @EXPORT_OK  = qw(
                      bucket_stats bucket_info bucket_array
                      lock_hash_recurse unlock_hash_recurse
                     );
-our $VERSION = '0.15';
+our $VERSION = '0.16';
 require XSLoader;
 XSLoader::load();
 
diff --git a/hv.c b/hv.c
index ec1bfe8..76b0a8c 100644 (file)
--- a/hv.c
+++ b/hv.c
@@ -787,20 +787,29 @@ Perl_hv_common(pTHX_ HV *hv, SV *keysv, const char *key, STRLEN klen,
        HeKEY_hek(entry) = save_hek_flags(key, klen, hash, flags);
     HeVAL(entry) = val;
 
+#ifdef PERL_HASH_RANDOMIZE_KEYS
     /* This logic semi-randomizes the insert order in a bucket.
      * Either we insert into the top, or the slot below the top,
      * making it harder to see if there is a collision. We also
      * reset the iterator randomizer if there is one.
      */
-    PL_hash_rand_bits += (PTRV)entry ^ hash; /* we don't bother to use ptr_hash here */
-    if ( !*oentry || (PL_hash_rand_bits & 1) ) {
+    if ( *oentry && PL_HASH_RAND_BITS_ENABLED) {
+        PL_hash_rand_bits++;
+        PL_hash_rand_bits= ROTL_UV(PL_hash_rand_bits,1);
+        if ( PL_hash_rand_bits & 1 ) {
+            HeNEXT(entry) = HeNEXT(*oentry);
+            HeNEXT(*oentry) = entry;
+        } else {
+            HeNEXT(entry) = *oentry;
+            *oentry = entry;
+        }
+    } else
+#endif
+    {
         HeNEXT(entry) = *oentry;
         *oentry = entry;
-    } else {
-        HeNEXT(entry) = HeNEXT(*oentry);
-        HeNEXT(*oentry) = entry;
     }
-    PL_hash_rand_bits= ROTL_UV(PL_hash_rand_bits,1);
+#ifdef PERL_HASH_RANDOMIZE_KEYS
     if (SvOOK(hv)) {
         /* Currently this makes various tests warn in annoying ways.
          * So Silenced for now. - Yves | bogus end of comment =>* /
@@ -811,8 +820,14 @@ Perl_hv_common(pTHX_ HV *hv, SV *keysv, const char *key, STRLEN klen,
                              pTHX__VALUE);
         }
         */
+        if (PL_HASH_RAND_BITS_ENABLED) {
+            if (PL_HASH_RAND_BITS_ENABLED == 1)
+                PL_hash_rand_bits += (PTRV)entry + 1;  /* we don't bother to use ptr_hash here */
+            PL_hash_rand_bits= ROTL_UV(PL_hash_rand_bits,1);
+        }
         HvAUX(hv)->xhv_rand= (U32)PL_hash_rand_bits;
     }
+#endif
 
     if (val == &PL_sv_placeholder)
        HvPLACEHOLDERS(hv)++;
@@ -1148,20 +1163,27 @@ S_hsplit(pTHX_ HV *hv, STRLEN const oldsize, STRLEN newsize)
       PL_nomemok = FALSE;
       return;
     }
+#ifdef PERL_HASH_RANDOMIZE_KEYS
     /* the idea of this is that we create a "random" value by hashing the address of
      * the array, we then use the low bit to decide if we insert at the top, or insert
      * second from top. After each such insert we rotate the hashed value. So we can
      * use the same hashed value over and over, and in normal build environments use
      * very few ops to do so. ROTL32() should produce a single machine operation. */
-    PL_hash_rand_bits += ptr_hash((PTRV)a);
-    PL_hash_rand_bits = ROTL_UV(PL_hash_rand_bits,1);
+    if (PL_HASH_RAND_BITS_ENABLED) {
+        if (PL_HASH_RAND_BITS_ENABLED == 1)
+            PL_hash_rand_bits += ptr_hash((PTRV)a);
+        PL_hash_rand_bits = ROTL_UV(PL_hash_rand_bits,1);
+    }
+#endif
 
     if (SvOOK(hv)) {
         struct xpvhv_aux *const dest
             = (struct xpvhv_aux*) &a[newsize * sizeof(HE*)];
         Move(&a[oldsize * sizeof(HE*)], dest, 1, struct xpvhv_aux);
         /* we reset the iterator's xhv_rand as well, so they get a totally new ordering */
+#ifdef PERL_HASH_RANDOMIZE_KEYS
         dest->xhv_rand = (U32)PL_hash_rand_bits;
+#endif
     }
 
     PL_nomemok = FALSE;
@@ -1183,17 +1205,30 @@ S_hsplit(pTHX_ HV *hv, STRLEN const oldsize, STRLEN newsize)
             U32 j = (HeHASH(entry) & newsize);
            if (j != (U32)i) {
                *oentry = HeNEXT(entry);
-                /* if the target cell is empty insert to top, otherwise
-                 * rotate the bucket rand 1 bit, and use the new low bit
-                 * to decide if we insert at top, or next from top.
-                 * IOW, we rotate only if we are dealing with colliding
-                 * elements. */
-                if (!aep[j] || ((PL_hash_rand_bits= ROTL_UV(PL_hash_rand_bits,1)) & 1)) {
+#ifdef PERL_HASH_RANDOMIZE_KEYS
+                /* if the target cell is empty or PL_HASH_RAND_BITS_ENABLED is false
+                 * insert to top, otherwise rotate the bucket rand 1 bit,
+                 * and use the new low bit to decide if we insert at top,
+                 * or next from top. IOW, we only rotate on a collision.*/
+                if (aep[j] && PL_HASH_RAND_BITS_ENABLED) {
+                    PL_hash_rand_bits+= ROTL_UV(HeHASH(entry), 17);
+                    PL_hash_rand_bits= ROTL_UV(PL_hash_rand_bits,1);
+                    if (PL_hash_rand_bits & 1) {
+                        HeNEXT(entry)= HeNEXT(aep[j]);
+                        HeNEXT(aep[j])= entry;
+                    } else {
+                        /* Note, this is structured in such a way as the optimizer
+                        * should eliminate the duplicated code here and below without
+                        * us needing to explicitly use a goto. */
+                        HeNEXT(entry) = aep[j];
+                        aep[j] = entry;
+                    }
+                } else
+#endif
+                {
+                    /* see comment above about duplicated code */
                     HeNEXT(entry) = aep[j];
                     aep[j] = entry;
-                } else {
-                    HeNEXT(entry)= HeNEXT(aep[j]);
-                    HeNEXT(aep[j])= entry;
                 }
            }
            else {
@@ -1632,7 +1667,9 @@ Perl_hfree_next_entry(pTHX_ HV *hv, STRLEN *indexp)
        }
        iter->xhv_riter = -1;   /* HvRITER(hv) = -1 */
        iter->xhv_eiter = NULL; /* HvEITER(hv) = NULL */
+#ifdef PERL_HASH_RANDOMIZE_KEYS
         iter->xhv_last_rand = iter->xhv_rand;
+#endif
     }
 
     if (!((XPVHV*)SvANY(hv))->xhv_keys)
@@ -1868,17 +1905,25 @@ S_hv_auxinit(pTHX_ HV *hv) {
         }
         HvARRAY(hv) = (HE**)array;
         SvOOK_on(hv);
-        PL_hash_rand_bits += ptr_hash((PTRV)array);
-        PL_hash_rand_bits = ROTL_UV(PL_hash_rand_bits,1);
         iter = HvAUX(hv);
+#ifdef PERL_HASH_RANDOMIZE_KEYS
+        if (PL_HASH_RAND_BITS_ENABLED) {
+            /* mix in some new state to PL_hash_rand_bits to "randomize" the traversal order*/
+            if (PL_HASH_RAND_BITS_ENABLED == 1)
+                PL_hash_rand_bits += ptr_hash((PTRV)array);
+            PL_hash_rand_bits = ROTL_UV(PL_hash_rand_bits,1);
+        }
         iter->xhv_rand = (U32)PL_hash_rand_bits;
+#endif
     } else {
         iter = HvAUX(hv);
     }
 
     iter->xhv_riter = -1;      /* HvRITER(hv) = -1 */
     iter->xhv_eiter = NULL;    /* HvEITER(hv) = NULL */
+#ifdef PERL_HASH_RANDOMIZE_KEYS
     iter->xhv_last_rand = iter->xhv_rand;
+#endif
     iter->xhv_name_u.xhvnameu_name = 0;
     iter->xhv_name_count = 0;
     iter->xhv_backreferences = 0;
@@ -1921,7 +1966,9 @@ Perl_hv_iterinit(pTHX_ HV *hv)
        }
        iter->xhv_riter = -1;   /* HvRITER(hv) = -1 */
        iter->xhv_eiter = NULL; /* HvEITER(hv) = NULL */
+#ifdef PERL_HASH_RANDOMIZE_KEYS
         iter->xhv_last_rand = iter->xhv_rand;
+#endif
     } else {
        hv_auxinit(hv);
     }
@@ -1976,6 +2023,27 @@ Perl_hv_riter_set(pTHX_ HV *hv, I32 riter) {
     iter->xhv_riter = riter;
 }
 
+void
+Perl_hv_rand_set(pTHX_ HV *hv, U32 new_xhv_rand) {
+    struct xpvhv_aux *iter;
+
+    PERL_ARGS_ASSERT_HV_RAND_SET;
+
+#ifdef PERL_HASH_RANDOMIZE_KEYS
+    if (!hv)
+        Perl_croak(aTHX_ "Bad hash");
+
+    if (SvOOK(hv)) {
+        iter = HvAUX(hv);
+    } else {
+        iter = hv_auxinit(hv);
+    }
+    iter->xhv_rand = new_xhv_rand;
+#else
+    Perl_croak(aTHX_ "This Perl has not been built with support for randomized hash key traversal but something called Perl_hv_rand_set().");
+#endif
+}
+
 void
 Perl_hv_eiter_set(pTHX_ HV *hv, HE *eiter) {
     struct xpvhv_aux *iter;
@@ -2381,6 +2449,8 @@ Perl_hv_iternext_flags(pTHX_ HV *hv, I32 flags)
             }
        }
     }
+
+#ifdef PERL_HASH_RANDOMIZE_KEYS
     if (iter->xhv_last_rand != iter->xhv_rand) {
         if (iter->xhv_riter != -1) {
             Perl_ck_warner_d(aTHX_ packWARN(WARN_INTERNAL),
@@ -2390,6 +2460,7 @@ Perl_hv_iternext_flags(pTHX_ HV *hv, I32 flags)
         }
         iter->xhv_last_rand = iter->xhv_rand;
     }
+#endif
 
     /* Skip the entire loop if the hash is empty.   */
     if ((flags & HV_ITERNEXT_WANTPLACEHOLDERS)
@@ -2401,10 +2472,12 @@ Perl_hv_iternext_flags(pTHX_ HV *hv, I32 flags)
            if (iter->xhv_riter > (I32)xhv->xhv_max /* HvRITER(hv) > HvMAX(hv) */) {
                /* There is no next one.  End of the hash.  */
                iter->xhv_riter = -1; /* HvRITER(hv) = -1 */
-                iter->xhv_last_rand = iter->xhv_rand;
+#ifdef PERL_HASH_RANDOMIZE_KEYS
+                iter->xhv_last_rand = iter->xhv_rand; /* reset xhv_last_rand so we can detect inserts during traversal */
+#endif
                break;
            }
-            entry = (HvARRAY(hv))[(iter->xhv_riter ^ iter->xhv_rand) & xhv->xhv_max];
+            entry = (HvARRAY(hv))[ PERL_HASH_ITER_BUCKET(iter) & xhv->xhv_max ];
 
            if (!(flags & HV_ITERNEXT_WANTPLACEHOLDERS)) {
                /* If we have an entry, but it's a placeholder, don't count it.
@@ -2419,7 +2492,9 @@ Perl_hv_iternext_flags(pTHX_ HV *hv, I32 flags)
     }
     else {
         iter->xhv_riter = -1;
+#ifdef PERL_HASH_RANDOMIZE_KEYS
         iter->xhv_last_rand = iter->xhv_rand;
+#endif
     }
 
     if (oldentry && HvLAZYDEL(hv)) {           /* was deleted earlier? */
diff --git a/hv.h b/hv.h
index 270ae00..0d619f2 100644 (file)
--- a/hv.h
+++ b/hv.h
@@ -8,6 +8,22 @@
  *
  */
 
+/* These control hash traversal randomization and the environment variable PERL_PERTURB_KEYS.
+ * Currently disabling this functionality will break a few tests, but should otherwise work fine.
+ * See perlrun for more details. */
+#define PERL_HASH_RANDOMIZE_KEYS 1
+#define USE_PERL_PERTURB_KEYS 1
+
+
+#ifdef PERL_HASH_RANDOMIZE_KEYS
+#   if defined(DEBUGGING) || defined(USE_PERL_PERTURB_KEYS)
+#       define PL_HASH_RAND_BITS_ENABLED PL_hash_rand_bits_enabled
+#   endif
+#   define PERL_HASH_ITER_BUCKET(iter) (((iter)->xhv_riter) ^ ((iter)->xhv_rand))
+#else
+#   define PERL_HASH_ITER_BUCKET(iter) ((iter)->xhv_riter)
+#endif
+
 /* entry in hash value chain */
 struct he {
     /* Keep hent_next first in this structure, because sv_free_arenas take
@@ -92,9 +108,11 @@ struct xpvhv_aux {
     I32                xhv_name_count;
     struct mro_meta *xhv_mro_meta;
     HV *       xhv_super;      /* SUPER method cache */
+#ifdef PERL_HASH_RANDOMIZE_KEYS
     U32         xhv_rand;       /* random value for hash traversal */
     U32         xhv_last_rand;  /* last random value for hash traversal,
                                    used to detect each() after insert for warnings */
+#endif
 };
 
 /* hash structure: */
index baa5f98..e87abf5 100644 (file)
@@ -64,7 +64,12 @@ PERLVAR(I, markstack,        I32 *)          /* stack_sp locations we're
 PERLVAR(I, markstack_ptr, I32 *)
 PERLVAR(I, markstack_max, I32 *)
 
+#ifdef PERL_HASH_RANDOMIZE_KEYS
+#ifdef USE_PERL_PERTURB_KEYS
+PERLVARI(I, hash_rand_bits_enabled, U8, 1) /* used to randomize hash stuff 0 == no-random, 1 == random, 2 == determinsitic */
+#endif
 PERLVARI(I, hash_rand_bits, UV, 0)      /* used to randomize hash stuff */
+#endif
 PERLVAR(I, strtab,     HV *)           /* shared string table */
 
 /* Fields used by magic variables such as $@, $/ and so on */
diff --git a/perl.c b/perl.c
index a39d66f..1689bbf 100644 (file)
--- a/perl.c
+++ b/perl.c
@@ -1490,6 +1490,11 @@ perl_parse(pTHXx_ XSINIT_t xsinit, int argc, char **argv, char **env)
             while (seed < seed_end) {
                 PerlIO_printf(Perl_debug_log, "%02x", *seed++);
             }
+#ifdef PERL_HASH_RANDOMIZE_KEYS
+            PerlIO_printf(Perl_debug_log, " PERTURB_KEYS = %d (%s)",
+                    PL_HASH_RAND_BITS_ENABLED,
+                    PL_HASH_RAND_BITS_ENABLED == 0 ? "NO" : PL_HASH_RAND_BITS_ENABLED == 1 ? "RANDOM" : "DETERMINISTIC");
+#endif
             PerlIO_printf(Perl_debug_log, "\n");
         }
     }
index f8bb821..96dfe04 100644 (file)
@@ -233,4 +233,4 @@ PERLVAR(G, malloc_mutex, perl_mutex)        /* Mutex for malloc */
 #endif
 
 PERLVARI(G, hash_seed_set, bool, FALSE)        /* perl.c */
-PERLVARA(G, hash_seed, PERL_HASH_SEED_BYTES, unsigned char) /* and hv.h */
+PERLVARA(G, hash_seed, PERL_HASH_SEED_BYTES, unsigned char) /* perl.c and hv.h */
index 3d8212e..8bcdd33 100644 (file)
@@ -4047,6 +4047,7 @@ on the version of Perl you are using because it is too new.
 Maybe the code needs to be updated, or maybe it is simply
 wrong and the version check should just be removed.
 
+
 =item perl: warning: Setting locale failed.
 
 (S) The whole warning message will look something like:
@@ -4069,12 +4070,26 @@ fix the problem, however, you will get the same error message each
 time you run Perl.  How to really fix the problem can be found in
 L<perllocale> section B<LOCALE PROBLEMS>.
 
-=item perl: warning: Non hex character in '$ENV{PERL_HASH_SEED}', seed only 
-partially set
+=item perl: warning: Non hex character in '$ENV{PERL_HASH_SEED}', seed only partially set
 
 (W) PERL_HASH_SEED should match /^\s*(?:0x)?[0-9a-fA-F]+\s*\z/ but it
-contained a non hex character. This could mean your hash randomization
-is not being set correctly.
+contained a non hex character. This could mean you are not using the hash
+seed you think you are.
+
+=item perl: warning: strange setting in '$ENV{PERL_PERTURB_KEYS}': '%s'
+
+(W) Perl was run with the environment variable PERL_PERTURB_KEYS defined
+but containing an unexpected value. The legal values of this setting
+are as follows.
+
+  Numeric | String        | Result
+  --------+---------------+-----------------------------------------
+  0       | NO            | Disables key traversal randomization
+  1       | RANDOM        | Enables full key traversal randomization
+  2       | DETERMINISTIC | Enables repeatable key traversal randomization
+
+Both numeric and string values are accepted, but note that string values are
+case sensitive. The default for this setting is "RANDOM" or 1.
 
 =item pid %x not a child
 
@@ -5090,6 +5105,14 @@ F<PERL_ENV_TABLES> (see L<perlvms>) so that the environ array isn't the
 target of the change to
 %ENV which produced the warning.
 
+=item This Perl has not been built with support for randomized hash key traversal but something called Perl_hv_rand_set().
+
+(F) Something has attempted to use an internal API call which
+depends on Perl being compiled with the default support for randomized hash
+key traversal, but this Perl has been compiled without it. You should
+report this warning to the relevant upstream party, or recompile perl
+with default options.
+
 =item thread failed to start: %s
 
 (W threads)(S) The entry point function of threads->create() failed for some reason.
index 8ef53b4..9078677 100644 (file)
@@ -1251,45 +1251,70 @@ PERL_ENCODING environment variable is consulted for an encoding name.
 =item PERL_HASH_SEED
 X<PERL_HASH_SEED>
 
-(Since Perl 5.8.1.)  Used to randomize Perl's internal hash function.
-To emulate the pre-5.8.1 behaviour, set to an integer; C<"0"> means
-exactly the same order as in 5.8.0.  "Pre-5.8.1" means, among other
-things, that hash keys will always have the same ordering between
-different runs of Perl.
+(Since Perl 5.8.1, new semantics in Perl 5.18.0)  Used to override
+the randomization of Perl's internal hash function. The value is expressed
+in hexadecimal, and may include a leading 0x. Truncated patterns
+are treated as though they are suffixed with sufficient 0's as required.
 
-Most hashes by default return elements in the same order as in Perl 5.8.0.
-On a hash by hash basis, if pathological data is detected during a hash
-key insertion, then that hash will switch to an alternative random hash
-seed.
-
-The default behaviour is to randomize unless the PERL_HASH_SEED is set.
-If Perl has been compiled with B<-DUSE_HASH_SEED_EXPLICIT>, the default
-behaviour is I<not> to randomize unless the PERL_HASH_SEED is set.
-
-If PERL_HASH_SEED is unset or set to a non-numeric string, Perl uses
-the pseudorandom seed supplied by the operating system and libraries.
+If the option is provided, and C<PERL_PERTURB_KEYS> is NOT set, then
+a value of '0' implies C<PERL_PERTURB_KEYS=0> and any other value
+implies C<PERL_PERTURB_KEYS=2>.
 
 B<PLEASE NOTE: The hash seed is sensitive information>. Hashes are
 randomized to protect against local and remote attacks against Perl
 code. By manually setting a seed, this protection may be partially or
 completely lost.
 
-See L<perlsec/"Algorithmic Complexity Attacks"> and
+See L<perlsec/"Algorithmic Complexity Attacks"> and L</PERL_PERTURB_KEYS>
 L</PERL_HASH_SEED_DEBUG> for more information.
 
+=item PERL_PERTURB_KEYS
+X<PERL_PERTURB_KEYS>
+
+(Since Perl 5.18.0)  Set to C<"0"> or C<"NO"> then traversing keys
+will be repeatedable from run to run for the same PERL_HASH_SEED.
+Insertion into a hash will not change the order, except to provide
+for more space in the hash. When combined with setting PERL_HASH_SEED
+this mode is as close to pre 5.18 behavior as you can get.
+
+When set to C<"1"> or C<"RANDOM"> then traversing keys will be randomized.
+Every time a hash is inserted into the key order will change in a random
+fashion. The order may not be repeatedable in a following program run
+even if the PERL_HASH_SEED has been specified. This is the default
+mode for perl.
+
+When set to C<"2"> or C<"DETERMINISTIC"> then inserting keys into a hash
+will cause the key order to change, but in a way that is repeatedable
+from program run to program run.
+
+B<NOTE:> Use of this option is considered insecure, and is intended only
+for debugging non-deterministic behavior in Perl's hash function. Do
+not use it in production.
+
+See L<perlsec/"Algorithmic Complexity Attacks"> and L</PERL_HASH_SEED>
+and L</PERL_HASH_SEED_DEBUG> for more information. You can get and set the
+key traversal mask for a specific hash by using the C<hash_traversal_mask()>
+function from L<Hash::Util>.
+
 =item PERL_HASH_SEED_DEBUG
 X<PERL_HASH_SEED_DEBUG>
 
-(Since Perl 5.8.1.)  Set to C<"1"> to display (to STDERR) the value of
-the hash seed at the beginning of execution.  This, combined with
-L</PERL_HASH_SEED> is intended to aid in debugging nondeterministic
-behaviour caused by hash randomization.
+(Since Perl 5.8.1.)  Set to C<"1"> to display (to STDERR) information
+about the hash function, seed, and what type of key traversal
+randomization is in effect at the beginning of execution.  This, combined
+with L</PERL_HASH_SEED> and L</PERL_PERTURB_KEYS> is intended to aid in
+debugging nondeterministic behaviour caused by hash randomization.
+
+B<Note> that any information about the hash function, especially the hash
+seed is B<sensitive information>: by knowing it, one can craft a denial-of-service
+attack against Perl code, even remotely; see L<perlsec/"Algorithmic Complexity Attacks">
+for more information. B<Do not disclose the hash seed> to people who
+don't need to know it. See also C<hash_seed()> and
+C<key_traversal_mask()> in L<Hash::Util>.
+
+An example output might be:
 
-B<Note that the hash seed is sensitive information>: by knowing it, one
-can craft a denial-of-service attack against Perl code, even remotely;
-see L<perlsec/"Algorithmic Complexity Attacks"> for more information.
-B<Do not disclose the hash seed> to people who don't need to know it.
-See also hash_seed() in L<Hash::Util>.
+    HASH_FUNCTION = ONE_AT_A_TIME_HARD HASH_SEED = 0x652e9b9349a7a032 PERTURB_KEYS = 1 (RANDOM)
 
 =item PERL_MEM_LOG
 X<PERL_MEM_LOG>
index eb079a3..98fa513 100644 (file)
@@ -454,49 +454,71 @@ I<Denial of Service> (DoS) attacks.
 
 =item *
 
-Hash Function - the algorithm used to "order" hash elements has been
-changed several times during the development of Perl, mainly to be
-reasonably fast.  In Perl 5.8.1 also the security aspect was taken
-into account.
-
-In Perls before 5.8.1 one could rather easily generate data that as
-hash keys would cause Perl to consume large amounts of time because
-internal structure of hashes would badly degenerate.  In Perl 5.8.1
-the hash function is randomly perturbed by a pseudorandom seed which
-makes generating such naughty hash keys harder.
-See L<perlrun/PERL_HASH_SEED> for more information.
-
-In Perl 5.8.1 the random perturbation was done by default, but as of
-5.8.2 it is only used on individual hashes if the internals detect the
-insertion of pathological data. If one wants for some reason emulate the
-old behaviour (and expose oneself to DoS attacks) one can set the
-environment variable PERL_HASH_SEED to zero to disable the protection
-(or any other integer to force a known perturbation, rather than random). 
-One possible reason for wanting to emulate the old behaviour is that in the
-new behaviour consecutive runs of Perl will order hash keys differently,
-which may confuse some applications (like Data::Dumper: the outputs of two
-different runs are no longer identical).
-
-In Perl 5.18.0 the rehash mechanism has been removed, and replaced by
-true randomization similar to that used in 5.8.1. Additionally measures
-have been taken to ensure that C<keys>, C<values>, and C<each> return items
-in a per-hash randomized order. Modifying a hash by insertion is
-guaranteed to change the iteration order. Combined with a hardened
-hash function we believe that discovery attacks on the hash seed
-are very unlikely.  This traversal randomization cannot be disabled,
-and is unaffected by the value of PERL_HASH_SEED.
-
-In addition to these measures, as of Perl 5.18.0 the source code includes
-multiple hash algorithms to choose from.  While we believe that the
-default perl hash is robust to attack we have included the hash function
-Siphash as a fallback option; at the time of release of Perl 5.18.0 Siphash
-is believed to be of cryptographic strength.  This is not the default as it
-is much slower than the default hash.
-
-B<Perl has never guaranteed any ordering of the hash keys>, and the
-ordering has already changed several times during the lifetime of
-Perl 5.  Also, the ordering of hash keys has always been, and
-continues to be, affected by the insertion order.
+Hash Algorithm - Hash algorithms like the one used in Perl are well
+known to be vulnerable to collision attacks on their hash function.
+Such attacks involve constructing a set of keys which collide into
+the same bucket producing inefficient behavior. Such attacks often
+depend on discovering the seed of the hash function used to map the
+keys to buckets which is then used to brute force an key set which
+can be used to mount a denial of service attack. In Perl 5.8.1 changes
+were introduced to harden Perl to such attacks, and then later in
+Perl 5.18.0 these features were enhanced and additional protections
+added.
+
+As of Perl 5.18.0 the following measures are in place to mitigate attacks:
+
+=over 4
+
+=item Hash Seed Randomization
+
+In order to make it impossible to know what seed to generate an attack
+key set for this seed is randomly initialzed at process start, but this
+may be overriden by using the PERL_HASH_SEED envrionment variable, see
+L<perlrun/PERL_HASH_SEED>. This controls how items are actually stored,
+not how they are presented via C<keys>, C<values> and C<each>.
+
+=item Hash Traversal Randomization
+
+Independent of which seed has been used in the hash function, C<keys>,
+C<values>, and C<each> return items in a per-hash randomized order.
+Modifying a hash by insertion will change the iteration order of that hash.
+This behavior can be overriden by using C<hash_traversal_mask()> from
+L<Hash::Util> or by using the PERL_PERTURB_KEYS environment variable,
+see L<perlrun/PERL_PERTURB_KEYS>. Note that this feature controls the
+"visible" order of the keys, and not the actual order they are stored in.
+
+=item Bucket Order Perturbance
+
+When items collide into a given bucket the order they are stored in
+the chain is no longer predictable with the intention of making
+it harder to observe a collisions. This behavior can be overriden by using
+the PERL_PERTURB_KEYS environment variable, see L<perlrun/PERL_PERTURB_KEYS>.
+
+=item New Default Hash Function
+
+The default hash function has been modified with the intention of making
+it harder to infer the hash seed.
+
+=item Alternative Hash Functions
+
+The source code includes multiple hash algorithms to choose from.  While we
+believe that the default perl hash is robust to attack we have included the
+hash function Siphash as a fallback option; at the time of release of
+Perl 5.18.0 Siphash is believed to be of cryptographic strength.  This is
+not the default as it is much slower than the default hash.
+
+=back
+
+Without compiling a special Perl there is no way to get the exact same
+behavior of any versions prior to Perl 5.18.0. The closest one can get
+is by setting PERL_PERTURB_KEYS to 0 and setting the PERL_HASH_SEED
+to a known value.
+
+B<Perl has never guaranteed any ordering of the hash keys>, and
+the ordering has already changed several times during the lifetime of
+Perl 5.  Also, the ordering of hash keys has always been, and continues
+to be, affected by the insertion order and the history of changes made
+to the hash over its lifetime.
 
 Also note that while the order of the hash elements might be
 randomised, this "pseudoordering" should B<not> be used for
diff --git a/proto.h b/proto.h
index 59ecbc6..13d9668 100644 (file)
--- a/proto.h
+++ b/proto.h
@@ -1635,6 +1635,11 @@ PERL_CALLCONV void       Perl_hv_placeholders_set(pTHX_ HV *hv, I32 ph)
 #define PERL_ARGS_ASSERT_HV_PLACEHOLDERS_SET   \
        assert(hv)
 
+PERL_CALLCONV void     Perl_hv_rand_set(pTHX_ HV *hv, U32 new_xhv_rand)
+                       __attribute__nonnull__(pTHX_1);
+#define PERL_ARGS_ASSERT_HV_RAND_SET   \
+       assert(hv)
+
 PERL_CALLCONV I32*     Perl_hv_riter_p(pTHX_ HV *hv)
                        __attribute__warn_unused_result__
                        __attribute__nonnull__(pTHX_1);
index 795673b..fd169c7 100644 (file)
@@ -18,6 +18,9 @@ my %skip = map { ("PL_$_", 1) }
          watchaddr watchok warn_uninit_sv
      );
 
+$skip{PL_hash_rand_bits}= $skip{PL_hash_rand_bits_enabled}= 1; # we can be compiled without these, so skip testing them
+
+
 my $trial = "nm globals$Config{_o} 2>&1";
 my $yes = `$trial`;
 
@@ -57,13 +60,17 @@ foreach my $file (map {$_ . $Config{_o}} qw(globals regcomp)) {
     close $fh or die "Problem running nm $file";
 }
 
-fail("Attempting to export '$_' which is never defined")
-    foreach sort keys %exported;
+foreach (sort keys %exported) {
+ SKIP: {
+    skip("We dont't export '$_' (Perl not built with this enabled?)",1) if $skip{$_};
+    fail("Attempting to export '$_' which is never defined");
+ }
+}
 
 foreach (sort keys %unexported) {
  SKIP: {
-       skip("We don't export $_", 1) if $skip{$_};
-       fail("$_ is defined, but we do not export it");
+        skip("We don't export '$_'", 1) if $skip{$_};
+        fail("'$_' is defined, but we do not export it");
     }
 }
 
index 9e09571..6afa049 100644 (file)
@@ -105,6 +105,8 @@ PerlIO::via::Base64
 PerlIO::via::StripHTML
 perllexwarn(1)
 perlthanks
+pod/perldiag.pod        Verbatim line length including indents exceeds 79 by        1
+pod/perlrun.pod        Verbatim line length including indents exceeds 79 by        3
 POD2::FR
 POD2::IT
 pod2ipf(1)
@@ -223,6 +225,7 @@ pod/perldebguts.pod Verbatim line length including indents exceeds 79 by    34
 pod/perldebtut.pod     Verbatim line length including indents exceeds 79 by    22
 pod/perldebug.pod      Verbatim line length including indents exceeds 79 by    3
 pod/perldiag.pod       =item type mismatch     1
+pod/perldiag.pod       Verbatim line length including indents exceeds 79 by    1
 pod/perldsc.pod        Verbatim line length including indents exceeds 79 by    4
 pod/perldtrace.pod     Verbatim line length including indents exceeds 79 by    26
 pod/perlebcdic.pod     Verbatim line length including indents exceeds 79 by    13
@@ -261,7 +264,7 @@ pod/perlpodstyle.pod        Verbatim line length including indents exceeds 79 by    1
 pod/perlref.pod        Verbatim line length including indents exceeds 79 by    1
 pod/perlrequick.pod    Verbatim line length including indents exceeds 79 by    3
 pod/perlretut.pod      Verbatim line length including indents exceeds 79 by    13
-pod/perlrun.pod        Verbatim line length including indents exceeds 79 by    2
+pod/perlrun.pod        Verbatim line length including indents exceeds 79 by    3
 pod/perlsolaris.pod    Verbatim line length including indents exceeds 79 by    14
 pod/perlsource.pod     ? Should you be using F<...> or maybe L<...> instead of 1
 pod/perlsub.pod        ? Should you be using F<...> or maybe L<...> instead of 3
diff --git a/util.c b/util.c
index 42fd70f..56cf5f1 100644 (file)
--- a/util.c
+++ b/util.c
@@ -5676,6 +5676,13 @@ Perl_get_hash_seed(pTHX_ unsigned char *seed_buffer)
     {
         while (isSPACE(*s))
            s++;
+#ifdef USE_PERL_PERTURB_KEYS
+        if (s[0] == '0' && s[1] == 0) {
+            PL_hash_rand_bits_enabled= 0;
+        } else {
+            PL_hash_rand_bits_enabled= 2;
+        }
+#endif
         if (s[0] == '0' && s[1] == 'x')
             s += 2;
 
@@ -5703,16 +5710,31 @@ Perl_get_hash_seed(pTHX_ unsigned char *seed_buffer)
             *ptr++ = (unsigned char)(Drand01() * (U8_MAX+1));
         }
     }
+#ifdef USE_PERL_PERTURB_KEYS
     {   /* initialize PL_hash_rand_bits from the hash seed.
          * This value is highly volatile, it is updated every
          * hash insert, and is used as part of hash bucket chain
          * randomization and hash iterator randomization. */
         unsigned long i;
-        PL_hash_rand_bits= 0;
+        PL_hash_rand_bits= 0xee49d17f;
         for( i = 0; i < sizeof(UV) ; i++ ) {
-            PL_hash_rand_bits = (PL_hash_rand_bits << 8) | seed_buffer[i % PERL_HASH_SEED_BYTES];
+            PL_hash_rand_bits += seed_buffer[i % PERL_HASH_SEED_BYTES];
+            PL_hash_rand_bits = ROTL_UV(PL_hash_rand_bits,8);
         }
     }
+    s= PerlEnv_getenv("PERL_PERTURB_KEYS");
+    if (s) {
+        if (strEQ(s,"0") || strEQ(s,"NO")) {
+            PL_hash_rand_bits_enabled= 0;
+        } else if (strEQ(s,"1") || strEQ(s,"RANDOM")) {
+            PL_hash_rand_bits_enabled= 1;
+        } else if (strEQ(s,"2") || strEQ(s,"DETERMINISTIC")) {
+            PL_hash_rand_bits_enabled= 2;
+        } else {
+            Perl_warn(aTHX_ "perl: warning: strange setting in '$ENV{PERL_PERTURB_KEYS}': '%s'\n",s);
+        }
+    }
+#endif
 }
 
 #ifdef PERL_GLOBAL_STRUCT