Page MenuHomeFreeBSD

bitstring: exit early if _start is past size of the bitstring
ClosedPublic

Authored by jacob.e.keller_intel.com on Nov 15 2019, 11:50 PM.
Tags
None
Referenced Files
Unknown Object (File)
Mon, Mar 4, 2:04 PM
Unknown Object (File)
Mon, Mar 4, 2:04 PM
Unknown Object (File)
Mon, Mar 4, 2:04 PM
Unknown Object (File)
Feb 21 2024, 9:59 PM
Unknown Object (File)
Jan 16 2024, 3:17 AM
Unknown Object (File)
Dec 28 2023, 11:28 PM
Unknown Object (File)
Dec 28 2023, 11:28 PM
Unknown Object (File)
Dec 28 2023, 11:28 PM
Subscribers

Details

Summary

bit_ffs_at and bit_ffc_at both take _start parameters which indicate to
start searching from _start onwards.

If the given _start index is past the size of the bit string, these
functions will calculate an address of the current bitstring which is
after the expected size. The function will also dereference the memory,
resulting in a read buffer overflow.

The output of the function remains correct, because the tests ensure to
stop the loop if the current bitstring chunk passes the stop bitstring
chunk, and because of a check to ensure the reported _value is never
past _nbits.

However, if <sys/bitstring.h> is ever used in code which is checked by
-fsanitize=undefined, or similar static analysis, it can produce
warnings about reading past the buffer size.

Because of the above mentioned checks, these buffer overflows do not
occur as long as _start is less than _nbits. Additionally, by definition
bit_ffs_at and bif_ffc_at should set _result to -1 in any case where the
_start is after the _nbits.

Check for this case at the start of the function and exit early if so,
preventing the buffer read overflow, and reducing the amount of
computation that occurs.

Note that it may seem odd to ever have code that could call bit_ffc_at
or bit_ffs_at with a _start value greater than _nbits. However, consider
a for-loop that used bit_ffs and bit_ffs_at to loop over a bit string
and perform some operation on each bit that was set. If the last bit of
the bit string was set, the simplest loop implementation would call
bit_ffs_at with a start of _nbits, and expect that to return -1. While
it does infact perform correctly, this is what ultimately triggers the
unexpected buffer read overflow.

Signed-off-by: Jacob Keller <jacob.e.keller@intel.com>

Diff Detail

Repository
rS FreeBSD src repository - subversion
Lint
Lint Not Applicable
Unit
Tests Not Applicable

Event Timeline

asomers requested changes to this revision.Nov 18 2019, 9:27 PM

Would you mind adding tests to tests/sys/sys/bitstring_test.c?

Curiously, I can only reproduce the failure when I disable the optimizer. At -O2, the compiler is smart enough to eliminate the out-of-bounds array read.

This revision now requires changes to proceed.Nov 18 2019, 9:27 PM

Would you mind adding tests to tests/sys/sys/bitstring_test.c?

Yep, I saw the test file after I submitted this patch. Will update.

Curiously, I can only reproduce the failure when I disable the optimizer. At -O2, the compiler is smart enough to eliminate the out-of-bounds array read.

Yea, I think that matches my experience too. The out-of-bounds read doesn't result in behavior changes because of the checks afterwards, and it would make sense for the compiler to elide the reads when optimizing.

add test cases to help cover the expected behavior

dereference _result properly before trying to assign it

This revision is now accepted and ready to land.Nov 20 2019, 1:51 AM