In perl.git, the branch yves/hv_h_split has been created
<http://perl5.git.perl.org/perl.git/commitdiff/c4d184cc8a4d181c3b07b0fc0e1b5efab6287506?hp=0000000000000000000000000000000000000000>
at c4d184cc8a4d181c3b07b0fc0e1b5efab6287506 (commit)
- Log -----------------------------------------------------------------
commit c4d184cc8a4d181c3b07b0fc0e1b5efab6287506
Author: Yves Orton <[email protected]>
Date: Mon Mar 18 00:28:03 2013 +0100
detect each() after insert and produce warnings when we do
Inserting into a hash that is being traversed with each()
has always produced undefined behavior. With hash traversal
randomization this is more pronounced, and at the same
time relatively easy to spot. At the cost of an extra U32
in the xpvhv_aux structure we can detect that the xhv_rand
has changed and then produce a warning if it has.
It was suggested on IRC that this should produce a fatal
error, but I couldn't see a clean way to manage that with
"strict", it was much easier to create a "severe" (internal)
warning, which is enabled by default but suppressible with
C<no warnings "internal";> if people /really/ wanted.
M hv.c
M hv.h
M pod/perldiag.pod
M t/op/each.t
commit d2859456f3adae4fba46b90343a99196c12220a5
Author: Yves Orton <[email protected]>
Date: Sun Mar 17 20:48:45 2013 +0100
ensure that inserting into a hash causes its hash iteration order to change
This serves two functions, it makes it harder for an attacker
to learn useful information by viewing the output of keys(),
and it makes "insert during traversal" errors much easier to
spot, as they will almost always produce degenerate behavior.
M hv.c
commit 59997784c6d806447904a21d2c50f0a6d0246952
Author: Yves Orton <[email protected]>
Date: Sun Mar 17 20:33:19 2013 +0100
perturb insertion order and update xhv_rand during insertion and S_hsplit()
When inserting into a hash results in a collision the order of the items
in the bucket chain is predictable (FILO), and can be used to determine
that a collision has occured.
When a hash is too small for the number of items it holds we double
its size and remap the items as required. During this process the
keys in a bucket will reverse order, and exposes information to an
attacker that a collision has occured.
We therefore use the PL_hash_rand_bits() and the S_ptr_hash()
infrastructure to randomly "perturb" the order that colliding
items are inserted into the bucket chain. During insertion and
mapping instead of doing a simple "insert to top" we check the low
bit of PL_hash_rand_bits() and depending if it is set or not we
insert at the top of the chain, otherwise second from the top.
The end result being that the order in a bucket is less predictable,
which should make it harder for an attacker to spot a collision.
Every insert (via hv_common), and bucket doubling (via hsplit())
results in us updating PL_hash_rand_bits() using "randomish" data
like the hashed bucket address, the hash of the inserted item, and
the address of the inserted item.
This also updates the xhv_rand() of the hash, if there is one, during
S_hsplit() so that the iteration order changes when S_hsplit() is
called. This also is intended to make it harder for an attacker to
aquire information about collisions.
M hv.c
commit 0b9b6b38a67fd2a594e0480e64e5f952364361f0
Author: Yves Orton <[email protected]>
Date: Sun Mar 17 20:19:09 2013 +0100
Harden hashes against hash seed discovery by randomizing hash iteration
Adds:
S_ptr_hash() - A new static function in hv.c which can be used to
hash a pointer or integer.
PL_hash_rand_bits - A new interpreter variable used as a cheap
provider of "semi-random" state for use by the hash infrastructure.
xpvhv_aux.xhv_rand - Used as a mask which is xored against the
xpvhv_aux.riter during iteration to randomize the order the actual
buckets are visited.
PL_hash_rand_bits is initialized as interpreter start from the random
hash seed, and then modified by "mixing in" the result of ptr_hash()
on the bucket array pointer in the hv (HvARRAY(hv)) every time
hv_auxinit() allocates a new iterator structure.
The net result is that every hash has its own iteration order, which
should make it much more difficult to determine what the current hash
seed is.
This required some test to be restructured, as they tested for something
that was not necessarily true, we never guaranteed that two hashes with
the same keys would produce the same key order, we merely promised that
using keys(), values(), or each() on the same hash, without any
insertions in between, would produce the same order of visiting the
key/values.
M embed.fnc
M embed.h
M embedvar.h
M hv.c
M hv.h
M intrpvar.h
M proto.h
M t/op/smartkve.t
M util.c
commit 5b6383a960ae6b78d85382a864cdb505e788afb5
Author: Yves Orton <[email protected]>
Date: Sun Mar 17 15:20:20 2013 +0100
rework ROTL definitions (and add ROTL_UV)
M hv_func.h
commit 0ca1e175cd675d1bdbc2d06adfa5b0144ad95ece
Author: Yves Orton <[email protected]>
Date: Tue Feb 12 05:06:48 2013 +0100
default to PERL_FUNC_ONE_AT_A_TIME_HARD for all builds
For testing, but maybe for ever
M hv_func.h
commit cee8b93cd7b326f0b2938f1b62373943782f92c4
Author: Yves Orton <[email protected]>
Date: Tue Dec 11 08:50:58 2012 +0100
silence signed mistmatch in comparison warning in Murmurhash
as far as I can tell 'i' can only be positive here.
M hv_func.h
commit 2e2fe67cb8278fdadaf7a17dd4c87c1256d5ce8a
Author: Yves Orton <[email protected]>
Date: Mon Dec 10 08:36:43 2012 +0100
add a hardened one-at-a-time hash variant
Mix in additional randomness into the final value.
M hv_func.h
commit 9bcdf9d39c08a67e26a086a7d05e0e8d17dfc703
Author: Yves Orton <[email protected]>
Date: Sat Dec 8 16:24:06 2012 +0100
Split out hash functions into new file and turn into inline static functions
This includes various tweaks related to building SipHash and other
cleanup.
M Cross/Makefile-cross-SH
M MANIFEST
M Makefile.SH
M Makefile.micro
M NetWare/Makefile
M configpm
M hv.h
A hv_func.h
M win32/Makefile
M win32/Makefile.ce
commit 039ae63cdd47e70208fb3cbad82681fead958206
Author: Yves Orton <[email protected]>
Date: Tue Dec 11 23:46:37 2012 +0100
add a "hash quality score" to Hash::Util::bucket_stats()
M ext/Hash-Util/lib/Hash/Util.pm
commit f9a8360370e580039c6a31d64d54385cfb79fcac
Author: Yves Orton <[email protected]>
Date: Mon Dec 10 09:43:59 2012 +0100
update ExtUtils-MakeMaker to github v6.65_01
Perl core specific highlights:
* Fix hash related issues for 5.18.
* Do not hard code the list of perl header files - discover them from disk
instead
* Don't need completely different include file collector on VMS.
M MANIFEST
M cpan/ExtUtils-MakeMaker/Changes
M cpan/ExtUtils-MakeMaker/MANIFEST
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/Command/MM.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/Liblist.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/Liblist/Kid.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_AIX.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_Any.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_BeOS.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_Cygwin.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_DOS.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_Darwin.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_MacOS.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_NW5.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_OS2.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_QNX.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_UWIN.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_Unix.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_VMS.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_VOS.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_Win32.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_Win95.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MY.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MakeMaker.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MakeMaker/Config.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MakeMaker/FAQ.pod
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MakeMaker/Tutorial.pod
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/Mkbootstrap.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/Mksymlists.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/testlib.pm
A cpan/ExtUtils-MakeMaker/t/Liblist_Kid.t
M cpan/ExtUtils-MakeMaker/t/basic.t
A cpan/ExtUtils-MakeMaker/t/liblist/win32/test.meep
M cpan/ExtUtils-MakeMaker/t/pod2man.t
-----------------------------------------------------------------------
--
Perl5 Master Repository
