Re: Missing cache considerations in randstruct performance feature

[Kees Cook]

On Sat, Oct 07, 2023 at 12:30:01AM +0200, Lukas Loidolt wrote:
> Hello!
> 
> I have been looking into the implementation of the "randstruct" gcc-plugin
> and noticed a potential bug in its performance version, which is supposed to
> limit randomization to cache-line sized groupings of structure members.
> I haven't been able to find too much documentation on this version of
> randstruct, but my general understanding of its intended behavior is as
> follows:
> 
> - in performance mode, randstruct groups structure members into cache line
> sized partitions of 64 bytes each
> - the order of these partitions is randomized
> - the order of structure members within each partition is also randomized
> 
> In my tests, however, the performance version behaves more or less like the
> full version of randstruct.
> For example, testing on a struct of 10 function pointers:
> 
> struct test_struct{
>     void (*func1)(void);
>     void (*func2)(void);
>     void (*func3)(void);
>     void (*func4)(void);
>     void (*func5)(void);
>     void (*func6)(void);
>     void (*func7)(void);
>     void (*func8)(void);
>     void (*func9)(void);
>     void (*func10)(void);
> };
> 
> resulted in the following randomized memory layout:
> 
> func3 (offset 0)
> func5 (offset 8)
> func10 (offset 16)
> func2 (offset 24)
> func1 (offset 32)
> func6 (offset 40)
> func8 (offset 48)
> func7 (offset 56)
> func9 (offset 64)
> func4 (offset 72)

I'd agree; this doesn't look like an expected layout.

> I would have expected cache-line sized partitions of (up to) 8 pointers, so
> that func1 through func8 are adjacent in the final layout, but these
> partitions are seemingly not preserved.

I'd expect the order of func1-func8 to be randomized together, and
func9-func10 order to be randomized together, and then they're pasted
together.

> Assuming that this is indeed not the intended behavior, the culprit is line
> 213 in "randomize_layout_plugin.c"
> https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/scripts/gcc-plugins/randomize_layout_plugin.c?id=f291209eca5eba0b4704fa0832af57b12dbc1a02#n213
> 
> where
> 
> randnum = ranval(prng_state) % (i + 1);
> 
> should probably be something like
> 
> randnum = size_group[x].start + ranval(prng_state) % size_group[x].length;

I thought the intent was to handle it in the loop offsets:

	for (i = size_group[x].start + size_group[x].length - 1; i > size_group[x].start; i--) {

But, no, this looks wrong, see below...

> After changing this line, cache-line sized partitions are created and
> preserved as expected.
> However, while structure members within each partition are randomized, the
> order of the partitions themselves is not randomized and remains the same as
> in the original struct declaration.

size_group[] is what holds the initial partitions. I would agree,
though, the group shuffling doesn't seem to do anything.

> I assume that the for loop in lines 200 to 206 is intended to shuffle the
> partition_group structures
> 
> for (i = num_groups - 1; i > 0; i--) {
>         struct partition_group tmp;
>         randnum = ranval(prng_state) % (i + 1);
>         tmp = size_group[i];
>         size_group[i] = size_group[randnum];
>         size_group[randnum] = tmp;
> }
> 
> but the order of the partition_group structs is not written back into the
> newtree object, so the randomization from this loop is not reflected in the
> final layout.

I'd expect the newtree index to start at 0, rather than reusing "i", if
the intent was to move groups around too. But in fact, the second
shuffle loop seems to just not work at all: it's not shuffling within
the group, since it operates from 0 to i, not size_group[x].start
through size_group[x].start + size_group[x].length.

> I would be interested to know if this is an actual issue with the
> implementation or if I'm misinterpreting how randstruct is supposed to work
> here.

I'd agree; this looks totally broken.

-Kees

-- 
Kees Cook