lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  linux-cve-announce  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Tue, 7 Nov 2023 16:48:51 -0800
From: Yury Norov <yury.norov@...il.com>
To: Kees Cook <keescook@...omium.org>
Cc: Alexander Lobakin <aleksander.lobakin@...el.com>,
	Alexander Potapenko <glider@...gle.com>,
	Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
	Syed Nayyar Waris <syednwaris@...il.com>,
	kernel test robot <lkp@...el.com>, oe-kbuild-all@...ts.linux.dev,
	linux-hardening@...r.kernel.org,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>
Subject: Re: [alobakin:pfcp 11/19] include/linux/bitmap.h:642:17: warning:
 array subscript [1, 1024] is outside array bounds of 'long unsigned int[1]'

On Tue, Nov 07, 2023 at 03:25:01PM -0800, Kees Cook wrote:
> On Tue, Nov 07, 2023 at 05:44:00PM +0100, Alexander Lobakin wrote:
> > From: Alexander Potapenko <glider@...gle.com>
> > Date: Tue, 7 Nov 2023 17:33:56 +0100
> > 
> > > On Tue, Nov 7, 2023 at 2:23 PM Alexander Lobakin
> > > <aleksander.lobakin@...el.com> wrote:
> > >>
> > >> From: Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
> > >> Date: Mon, 6 Nov 2023 20:23:52 +0200
> > >>
> > >>> On Mon, Nov 06, 2023 at 05:31:34PM +0100, Alexander Lobakin wrote:
> > >>>
> > >>>>> | Reported-by: kernel test robot <lkp@...el.com>
> > >>>>> | Closes: https://lore.kernel.org/oe-kbuild-all/202310170708.fJzLlgDM-lkp@intel.com/
> > >>>
> > >>>> Not sure how to approach this :z It was also captured on the version you
> > >>>> sent 2 weeks ago, so this could've been resolved already.
> > >>>
> > >>> Is it in the repository already? if so, we should revert it.
> > >>> Otherwise you have time to think and fix.
> > >>
> > >> Nah, neither Alex' series nor mine. And I'd say this should rather be
> > >> resolved in the functions Alex introduce.
> > >>
> > >> Thanks,
> > >> Olek
> > > 
> > > Sorry, I couldn't reproduce the problem using the instructions at
> > > https://download.01.org/0day-ci/archive/20231017/202310170708.fJzLlgDM-lkp@intel.com/reproduce
> > > locally, maybe that's because I only have gcc-11 and higher.
> > > 
> > > But if I'm understanding correctly what's going on, then GCC will be
> > > reporting the same issue in the following code:
> > > 
> > > =======================================================
> > > #include <stddef.h>
> > > #include <stdbool.h>
> > > 
> > > #define BITS_PER_LONG 64
> > > #define unlikely(x) x
> > > #define UL(x) (x##UL)
> > > #define GENMASK(h, l) \
> > >         (((~UL(0)) - (UL(1) << (l)) + 1) & \
> > >          (~UL(0) >> (BITS_PER_LONG - 1 - (h))))
> > > 
> > > #define BIT_WORD(nr)            ((nr) / BITS_PER_LONG)
> > > #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
> > > #define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
> > > 
> > > inline void bitmap_write(unsigned long *map,
> > >                                 unsigned long value,
> > >                                 unsigned long start, unsigned long nbits)
> > > {
> > >         size_t index;
> > >         unsigned long offset;
> > >         unsigned long space;
> > >         unsigned long mask;
> > >         bool fit;
> > > 
> > >         if (unlikely(!nbits))
> > >                 return;
> > > 
> > >         mask = BITMAP_LAST_WORD_MASK(nbits);
> > >         value &= mask;
> > >         offset = start % BITS_PER_LONG;
> > >         space = BITS_PER_LONG - offset;
> > >         fit = space >= nbits;
> > >         index = BIT_WORD(start);
> > > 
> > >         map[index] &= (fit ? (~(mask << offset)) :
> > > ~BITMAP_FIRST_WORD_MASK(start));
> > >         map[index] |= value << offset;
> > >         if (fit)
> > >                 return;
> > > 
> > >         map[index + 1] &= BITMAP_FIRST_WORD_MASK(start + nbits);
> > >         map[index + 1] |= (value >> space);
> > > }
> > > 
> > > unsigned long foo(unsigned int n) {
> > >     unsigned long bm[1] = {0};
> > >     bitmap_write(bm, 1, n, 2);
> > >     return bm[0];
> > > }
> > > =======================================================
> > > (see also https://godbolt.org/z/GfGfYje53)
> > > 
> > > If so, the problem is not specific to GCC 9, trunk GCC also barks on this code:
> > > 
> > > =======================================================
> > > In function 'bitmap_write',
> > >     inlined from 'bitmap_write' at <source>:15:13,
> > >     inlined from 'foo' at <source>:47:7:
> > > <source>:40:12: warning: array subscript 1 is outside array bounds of
> > > 'long unsigned int[1]' [-Warray-bounds=]
> > >    40 |         map[index + 1] &= BITMAP_FIRST_WORD_MASK(start + nbits);
> > >       |         ~~~^~~~~~~~~~~
> > > =======================================================
> > > 
> > > If this is true for the code in drivers/gpio/gpio-pca953x.c,
> > > suppressing the report for GCC 9 won't help for other versions.
> > > Given that this report is isolated in a single file, we probably need
> > 
> > I tested it on GCC 9 using modified make.cross from lkp and it triggers
> > on one more file:
> > 
> > drivers/thermal/intel/intel_soc_dts_iosf.c: In function 'sys_get_curr_temp':
> > ./include/linux/bitmap.h:601:18: error: array subscript [1,
> > 288230376151711744] is outside array bounds of 'long unsigned int[1]'
> > [-Werror=array-bounds]
> > 
> > > to give the compiler some hints about the range of values passed to
> > > bitmap_write() rather than suppressing the optimizations.
> > 
> > OPTIMIZER_HIDE_VAR() doesn't disable optimizations if I get it
> > correctly, rather shuts up the compiler in cases like this one.
> > 
> > I've been thinking of using __member_size() from fortify-string.h, we
> > could probably optimize the object code even a bit more while silencing
> > this warning.
> > Adding Kees, maybe he'd like to participate in sorting this out as well.
> 
> I'm trying to find all the pieces for this code, so I might be working
> from the wrong version or something, but I think this is the change:
> https://github.com/alobakin/linux/commit/66808fb20fed014a522b868322d54daef14a6bd8

This is the series:

https://www.spinics.net/lists/kernel/msg4985590.html

The relevant part of the function is:

+	offset = start % BITS_PER_LONG;
+	space = BITS_PER_LONG - offset;
+	fit = space >= nbits; // true if offset + nbits <= BITS_PER_LONG
+	index = BIT_WORD(start);
+
+	map[index] &= XXX;
+	map[index] |= value << offset;
+	if (fit)
+		return;
+
+	map[index + 1] = YYY;
 
Some background for you:

'fit' means that the requested part of bitmap fits into a single
machine word. For example, on 64-bit machine:

        DECLARE_BITMAP(map, 64); // unsigned long val[1];
        bitmap_write(map, val, 60, 4) // fit == true
        bitmap_write(map, val, 60, 8) // fit == false

It's possible that user may overrun the array boundary, like in the
2nd case, and compiler may correctly warn about it.

But in this case...

The code in question is:

        #define bitmap_set_value8(map, value, start)           \
                bitmap_write(map, value, start, BITS_PER_BYTE)
        #define BANK_SZ 8

        for (i = 0; i < NBANK(chip); i++)
                bitmap_set_value8(val, value[i], i * BANK_SZ);

Here nbits is always 8, and start is multiple of 8. With that, we're
always writing into a single word (fit == true), and 'idx + 1' path
is never hit. This makes me think that it the warning here is false
positive. Is that correct?

> and the induced warning is correctly analyzed in this thread (i.e. GCC
> can't convince itself that it'll never reach the out of bounds access).
> Does this work?
> 
> -	if (fit)
> +	if (fit || index + 1 >= __member_size(map))
>  		return;

I already commented this in the other email in this thread - this would
silence a true warning where people break the boundary:

        bitmap_write(map, val, 60, 8);

And as far as I can see, __member_size() implies some runtime
overhead, which I'd like to avoid.

Thanks,
Yury


Powered by blists - more mailing lists