tyler/bitset — Issue #9: Invalid reads in binary operations
Author: chrisavl
Created: 2012-01-16 11:16:06+00:00
State: open

Binary operations of bitsets of differing length can lead to invalid reads if the second operand is shorter than the first.

Solution: Either only allow binary operations on bitsets of equal length or only iterate over MIN(max, other_max). Will post a patch after preferred solution has been decided.

A simple example validated with valgrind:

$ cat test.rb
require "bitset"
bs1 = Bitset.new(128)
bs2 = Bitset.new(8)
bs3 = bs1 & bs2
$ valgrind --dsymutil=yes ruby test.rb
// Ignore lots of gc related warnings..
// ...
==29948== Invalid read of size 8
==29948== at 0x918D31: rb_bitset_intersect (bitset.c:180)
==29948== by 0x190BE2: vm_call_method (vm_insnhelper.c:402)
==29948== by 0x17CD93: vm_exec_core (insns.def:1006)
==29948== by 0x184A32: vm_exec (vm.c:1147)
==29948== by 0x184D3A: rb_iseq_eval_main (vm.c:1388)
==29948== by 0x54461: ruby_exec_internal (eval.c:214)
==29948== by 0x56DEB: ruby_run_node (eval.c:261)
==29948== by 0x100000EDE: main (main.c:35)
==29948== Address 0x100c58c58 is 0 bytes after a block of size 8 alloc'd
==29948== at 0xC3F3: calloc (vg_replace_malloc.c:569)
==29948== by 0x918F1E: rb_bitset_initialize (bitset.c:23)
==29948== by 0x1861F3: vm_call0 (vm_eval.c:79)
==29948== by 0x18B40D: rb_funcall2 (vm_eval.c:235)
==29948== by 0xA51B2: rb_class_new_instance (object.c:1545)
==29948== by 0x190BE2: vm_call_method (vm_insnhelper.c:402)
==29948== by 0x17CD93: vm_exec_core (insns.def:1006)
==29948== by 0x184A32: vm_exec (vm.c:1147)
==29948== by 0x184D3A: rb_iseq_eval_main (vm.c:1388)
==29948== by 0x54461: ruby_exec_internal (eval.c:214)
==29948== by 0x56DEB: ruby_run_node (eval.c:261)
==29948== by 0x100000EDE: main (main.c:35)