Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Andrew Morton]

On Tue, 26 Jun 2018 15:15:10 +0200 Andrey Konovalov <andreyknvl@google.com> wrote:

> This patchset adds a new mode to KASAN [1], which is called KHWASAN
> (Kernel HardWare assisted Address SANitizer).
> 
> The plan is to implement HWASan [2] for the kernel with the incentive,
> that it's going to have comparable to KASAN performance, but in the same
> time consume much less memory, trading that off for somewhat imprecise
> bug detection and being supported only for arm64.

Why do we consider this to be a worthwhile change?

Is KASAN's memory consumption actually a significant problem?  Some
data regarding that would be very useful.

If it is a large problem then we still have that problem on x86, so the
problem remains largely unsolved?

> ====== Benchmarks
> 
> The following numbers were collected on Odroid C2 board. Both KASAN and
> KHWASAN were used in inline instrumentation mode.
> 
> Boot time [1]:
> * ~1.7 sec for clean kernel
> * ~5.0 sec for KASAN
> * ~5.0 sec for KHWASAN
> 
> Slab memory usage after boot [2]:
> * ~40 kb for clean kernel
> * ~105 kb + 1/8th shadow ~= 118 kb for KASAN
> * ~47 kb + 1/16th shadow ~= 50 kb for KHWASAN
> 
> Network performance [3]:
> * 8.33 Gbits/sec for clean kernel
> * 3.17 Gbits/sec for KASAN
> * 2.85 Gbits/sec for KHWASAN
> 
> Note, that KHWASAN (compared to KASAN) doesn't require quarantine.
> 
> [1] Time before the ext4 driver is initialized.
> [2] Measured as `cat /proc/meminfo | grep Slab`.
> [3] Measured as `iperf -s & iperf -c 127.0.0.1 -t 30`.

The above doesn't actually demonstrate the whole point of the
patchset: to reduce KASAN's very high memory consumption?

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Kostya Serebryany]

On Wed, Jun 27, 2018 at 4:08 PM Andrew Morton <akpm@linux-foundation.org> wrote:
>
> On Tue, 26 Jun 2018 15:15:10 +0200 Andrey Konovalov <andreyknvl@google.com> wrote:
>
> > This patchset adds a new mode to KASAN [1], which is called KHWASAN
> > (Kernel HardWare assisted Address SANitizer).
> >
> > The plan is to implement HWASan [2] for the kernel with the incentive,
> > that it's going to have comparable to KASAN performance, but in the same
> > time consume much less memory, trading that off for somewhat imprecise
> > bug detection and being supported only for arm64.
>
> Why do we consider this to be a worthwhile change?
>
> Is KASAN's memory consumption actually a significant problem?  Some
> data regarding that would be very useful.

On mobile, ASAN's and KASAN's memory usage is a significant problem.
Not sure if I can find scientific evidence of that.
CC-ing Vishwath Mohan who deals with KASAN on Android to provide
anecdotal evidence.

There are several other benefits too:
* HWASAN more reliably detects non-linear-buffer-overflows compared to
ASAN (same for kernel-HWASAN vs kernel-ASAN)
* Same for detecting use-after-free (since HWASAN doesn't rely on quarantine).
* Much easier to implement stack-use-after-return detection (which
IIRC KASAN doesn't have yet, because in KASAN it's too hard)

> If it is a large problem then we still have that problem on x86, so the
> problem remains largely unsolved?

The problem is more significant on mobile devices than on desktop/server.
I'd love to have [K]HWASAN on x86_64 as well, but it's less trivial since x86_64
doesn't have an analog of aarch64's top-byte-ignore hardware feature.


>
> > ====== Benchmarks
> >
> > The following numbers were collected on Odroid C2 board. Both KASAN and
> > KHWASAN were used in inline instrumentation mode.
> >
> > Boot time [1]:
> > * ~1.7 sec for clean kernel
> > * ~5.0 sec for KASAN
> > * ~5.0 sec for KHWASAN
> >
> > Slab memory usage after boot [2]:
> > * ~40 kb for clean kernel
> > * ~105 kb + 1/8th shadow ~= 118 kb for KASAN
> > * ~47 kb + 1/16th shadow ~= 50 kb for KHWASAN
> >
> > Network performance [3]:
> > * 8.33 Gbits/sec for clean kernel
> > * 3.17 Gbits/sec for KASAN
> > * 2.85 Gbits/sec for KHWASAN
> >
> > Note, that KHWASAN (compared to KASAN) doesn't require quarantine.
> >
> > [1] Time before the ext4 driver is initialized.
> > [2] Measured as `cat /proc/meminfo | grep Slab`.
> > [3] Measured as `iperf -s & iperf -c 127.0.0.1 -t 30`.
>
> The above doesn't actually demonstrate the whole point of the
> patchset: to reduce KASAN's very high memory consumption?
>
> --
> You received this message because you are subscribed to the Google Groups "kasan-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to kasan-dev+unsubscribe@googlegroups.com.
> To post to this group, send email to kasan-dev@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/kasan-dev/20180627160800.3dc7f9ee41c0badbf7342520%40linux-foundation.org.
> For more options, visit https://groups.google.com/d/optout.

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Andrew Morton]

On Wed, 27 Jun 2018 17:59:00 -0700 Vishwath Mohan <vishwath@google.com> wrote:

> > > > time consume much less memory, trading that off for somewhat imprecise
> > > > bug detection and being supported only for arm64.
> > >
> > > Why do we consider this to be a worthwhile change?
> > >
> > > Is KASAN's memory consumption actually a significant problem?  Some
> > > data regarding that would be very useful.
> >
> > On mobile, ASAN's and KASAN's memory usage is a significant problem.
> > Not sure if I can find scientific evidence of that.
> > CC-ing Vishwath Mohan who deals with KASAN on Android to provide
> > anecdotal evidence.
> >
> Yeah, I can confirm that it's an issue. Like Kostya mentioned, I don't have
> data on-hand, but anecdotally both ASAN and KASAN have proven problematic
> to enable for environments that don't tolerate the increased memory
> pressure well. This includes,
> (a) Low-memory form factors - Wear, TV, Things, lower-tier phones like Go
> (c) Connected components like Pixel's visual core
> <https://www.blog.google/products/pixel/pixel-visual-core-image-processing-and-machine-learning-pixel-2/>
> 
> 
> These are both places I'd love to have a low(er) memory footprint option at
> my disposal.

Thanks.

It really is important that such information be captured in the
changelogs.  In as much detail as can be mustered.

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Geert Uytterhoeven]

Hi Kostya,

On Thu, Jun 28, 2018 at 2:04 AM Kostya Serebryany <kcc@google.com> wrote:
> On Wed, Jun 27, 2018 at 4:08 PM Andrew Morton <akpm@linux-foundation.org> wrote:
> > On Tue, 26 Jun 2018 15:15:10 +0200 Andrey Konovalov <andreyknvl@google.com> wrote:
> > > This patchset adds a new mode to KASAN [1], which is called KHWASAN
> > > (Kernel HardWare assisted Address SANitizer).
> > >
> > > The plan is to implement HWASan [2] for the kernel with the incentive,
> > > that it's going to have comparable to KASAN performance, but in the same
> > > time consume much less memory, trading that off for somewhat imprecise
> > > bug detection and being supported only for arm64.
> >
> > Why do we consider this to be a worthwhile change?
> >
> > Is KASAN's memory consumption actually a significant problem?  Some
> > data regarding that would be very useful.
>
> On mobile, ASAN's and KASAN's memory usage is a significant problem.
> Not sure if I can find scientific evidence of that.
> CC-ing Vishwath Mohan who deals with KASAN on Android to provide
> anecdotal evidence.
>
> There are several other benefits too:
> * HWASAN more reliably detects non-linear-buffer-overflows compared to
> ASAN (same for kernel-HWASAN vs kernel-ASAN)
> * Same for detecting use-after-free (since HWASAN doesn't rely on quarantine).
> * Much easier to implement stack-use-after-return detection (which
> IIRC KASAN doesn't have yet, because in KASAN it's too hard)
>
> > If it is a large problem then we still have that problem on x86, so the
> > problem remains largely unsolved?
>
> The problem is more significant on mobile devices than on desktop/server.
> I'd love to have [K]HWASAN on x86_64 as well, but it's less trivial since x86_64
> doesn't have an analog of aarch64's top-byte-ignore hardware feature.

This depends on your mobile devices and desktops and servers.
There exist mobile devices with more memory than some desktops or servers.

So actual numbers (O(KiB)? O(MiB)? O(GiB)?) would be nice to have.

Thanks!

Gr{oetje,eeting}s,

                        Geert

-- 
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Dave Martin]

On Tue, Jun 26, 2018 at 03:15:10PM +0200, Andrey Konovalov wrote:
> This patchset adds a new mode to KASAN [1], which is called KHWASAN
> (Kernel HardWare assisted Address SANitizer).
> 
> The plan is to implement HWASan [2] for the kernel with the incentive,
> that it's going to have comparable to KASAN performance, but in the same
> time consume much less memory, trading that off for somewhat imprecise
> bug detection and being supported only for arm64.
> 
> The overall idea of the approach used by KHWASAN is the following:
> 
> 1. By using the Top Byte Ignore arm64 CPU feature, we can store pointer
>    tags in the top byte of each kernel pointer.

[...]

This is a change from the current situation, so the kernel may be
making implicit assumptions about the top byte of kernel addresses.

Randomising the top bits may cause things like address conversions and
pointer arithmetic to break.

For example, (q - p) will not produce the expected result if q and p
have different tags.

Conversions, such as between pointer and pfn, may also go wrong if not
appropriately masked.

There are also potential pointer comparison and aliasing issues if
the tag bits are ever stripped or modified.


What was your approach to tracking down all the points in the code
where we have a potential issue?

(I haven't dug through the series in detail yet, so this may be
answered somewhere already...)

Cheers
---Dave

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Andrey Konovalov]

On Thu, Jun 28, 2018 at 3:11 AM, Andrew Morton
<akpm@linux-foundation.org> wrote:
> On Wed, 27 Jun 2018 17:59:00 -0700 Vishwath Mohan <vishwath@google.com> wrote:
>> Yeah, I can confirm that it's an issue. Like Kostya mentioned, I don't have
>> data on-hand, but anecdotally both ASAN and KASAN have proven problematic
>> to enable for environments that don't tolerate the increased memory
>> pressure well. This includes,
>> (a) Low-memory form factors - Wear, TV, Things, lower-tier phones like Go
>> (c) Connected components like Pixel's visual core
>> <https://www.blog.google/products/pixel/pixel-visual-core-image-processing-and-machine-learning-pixel-2/>
>>
>>
>> These are both places I'd love to have a low(er) memory footprint option at
>> my disposal.
>
> Thanks.
>
> It really is important that such information be captured in the
> changelogs.  In as much detail as can be mustered.

I'll add it to the changelog in v5. Thanks!

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Andrey Konovalov]

On Thu, Jun 28, 2018 at 1:08 AM, Andrew Morton
<akpm@linux-foundation.org> wrote:
> On Tue, 26 Jun 2018 15:15:10 +0200 Andrey Konovalov <andreyknvl@google.com> wrote:
>> ====== Benchmarks
>>
>> The following numbers were collected on Odroid C2 board. Both KASAN and
>> KHWASAN were used in inline instrumentation mode.
>>
>> Boot time [1]:
>> * ~1.7 sec for clean kernel
>> * ~5.0 sec for KASAN
>> * ~5.0 sec for KHWASAN
>>
>> Slab memory usage after boot [2]:
>> * ~40 kb for clean kernel
>> * ~105 kb + 1/8th shadow ~= 118 kb for KASAN
>> * ~47 kb + 1/16th shadow ~= 50 kb for KHWASAN
>>
>> Network performance [3]:
>> * 8.33 Gbits/sec for clean kernel
>> * 3.17 Gbits/sec for KASAN
>> * 2.85 Gbits/sec for KHWASAN
>>
>> Note, that KHWASAN (compared to KASAN) doesn't require quarantine.
>>
>> [1] Time before the ext4 driver is initialized.
>> [2] Measured as `cat /proc/meminfo | grep Slab`.
>> [3] Measured as `iperf -s & iperf -c 127.0.0.1 -t 30`.
>
> The above doesn't actually demonstrate the whole point of the
> patchset: to reduce KASAN's very high memory consumption?

You mean that memory usage numbers collected after boot don't give a
representative picture of actual memory consumption on real workloads?

What kind of memory consumption testing would you like to see?

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Andrey Konovalov]

On Thu, Jun 28, 2018 at 12:51 PM, Dave Martin <Dave.Martin@arm.com> wrote:
> On Tue, Jun 26, 2018 at 03:15:10PM +0200, Andrey Konovalov wrote:
>> 1. By using the Top Byte Ignore arm64 CPU feature, we can store pointer
>>    tags in the top byte of each kernel pointer.
>
> [...]
>
> This is a change from the current situation, so the kernel may be
> making implicit assumptions about the top byte of kernel addresses.
>
> Randomising the top bits may cause things like address conversions and
> pointer arithmetic to break.
>
> For example, (q - p) will not produce the expected result if q and p
> have different tags.

If q and p have different tags, that means they come from different
allocations. I don't think it would make sense to calculate pointer
difference in this case.

>
> Conversions, such as between pointer and pfn, may also go wrong if not
> appropriately masked.
>
> There are also potential pointer comparison and aliasing issues if
> the tag bits are ever stripped or modified.
>
>
> What was your approach to tracking down all the points in the code
> where we have a potential issue?

I've been fuzzing the kernel built with KWHASAN with syzkaller. This
gives a decent coverage and I was able to find some places where
fixups were required this way. Right now the fuzzer is running without
issues. It doesn't prove that all such places are fixed, but I don't
know a better way to test this.

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Andrew Morton]

On Thu, 28 Jun 2018 20:29:07 +0200 Andrey Konovalov <andreyknvl@google.com> wrote:

> >> Slab memory usage after boot [2]:
> >> * ~40 kb for clean kernel
> >> * ~105 kb + 1/8th shadow ~= 118 kb for KASAN
> >> * ~47 kb + 1/16th shadow ~= 50 kb for KHWASAN
> >>
> >> Network performance [3]:
> >> * 8.33 Gbits/sec for clean kernel
> >> * 3.17 Gbits/sec for KASAN
> >> * 2.85 Gbits/sec for KHWASAN
> >>
> >> Note, that KHWASAN (compared to KASAN) doesn't require quarantine.
> >>
> >> [1] Time before the ext4 driver is initialized.
> >> [2] Measured as `cat /proc/meminfo | grep Slab`.
> >> [3] Measured as `iperf -s & iperf -c 127.0.0.1 -t 30`.
> >
> > The above doesn't actually demonstrate the whole point of the
> > patchset: to reduce KASAN's very high memory consumption?
> 
> You mean that memory usage numbers collected after boot don't give a
> representative picture of actual memory consumption on real workloads?
> 
> What kind of memory consumption testing would you like to see?

Well, 100kb or so is a teeny amount on virtually any machine.  I'm
assuming the savings are (much) more significant once the machine gets
loaded up and doing work?

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Mark Rutland]

On Thu, Jun 28, 2018 at 08:56:41PM +0200, Andrey Konovalov wrote:
> On Thu, Jun 28, 2018 at 12:51 PM, Dave Martin <Dave.Martin@arm.com> wrote:
> > On Tue, Jun 26, 2018 at 03:15:10PM +0200, Andrey Konovalov wrote:
> >> 1. By using the Top Byte Ignore arm64 CPU feature, we can store pointer
> >>    tags in the top byte of each kernel pointer.
> >
> > [...]
> >
> > This is a change from the current situation, so the kernel may be
> > making implicit assumptions about the top byte of kernel addresses.

[...]

> > What was your approach to tracking down all the points in the code
> > where we have a potential issue?
> 
> I've been fuzzing the kernel built with KWHASAN with syzkaller. This
> gives a decent coverage and I was able to find some places where
> fixups were required this way. Right now the fuzzer is running without
> issues. It doesn't prove that all such places are fixed, but I don't
> know a better way to test this.

While fuzzing shows that the kernel doesn't crash (and this is very
important), it does not show that it exhibits the expected behaviour,
and there could be a number of soft failures present.

e.g. certain functions might just return an error code if a pointer has
a tag other than 0xff (such that it looks like a kernel pointer) or 0x00
(such that it looks like a user pointer), and this might not result in a
fatal error even though the behaviour is not what we require.

Perhaps it's possible to compare the behaviour of a kernel making use of
tags with one which does not, though I'm not sure at which level the
comparison needs to be performed.

Thanks,
Mark.

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Dave Martin]

On Thu, Jun 28, 2018 at 08:56:41PM +0200, Andrey Konovalov wrote:
> On Thu, Jun 28, 2018 at 12:51 PM, Dave Martin <Dave.Martin@arm.com> wrote:
> > On Tue, Jun 26, 2018 at 03:15:10PM +0200, Andrey Konovalov wrote:
> >> 1. By using the Top Byte Ignore arm64 CPU feature, we can store pointer
> >>    tags in the top byte of each kernel pointer.
> >
> > [...]
> >
> > This is a change from the current situation, so the kernel may be
> > making implicit assumptions about the top byte of kernel addresses.
> >
> > Randomising the top bits may cause things like address conversions and
> > pointer arithmetic to break.
> >
> > For example, (q - p) will not produce the expected result if q and p
> > have different tags.
> 
> If q and p have different tags, that means they come from different
> allocations. I don't think it would make sense to calculate pointer
> difference in this case.

It's not strictly valid to subtract pointers from different allocations
in C, but it's hard to prove statically that two pointers are guaranteed
to point into the same allocation.

It's likely that we're getting away with it in some places today.

> > Conversions, such as between pointer and pfn, may also go wrong if not
> > appropriately masked.
> >
> > There are also potential pointer comparison and aliasing issues if
> > the tag bits are ever stripped or modified.
> >
> >
> > What was your approach to tracking down all the points in the code
> > where we have a potential issue?
> 
> I've been fuzzing the kernel built with KWHASAN with syzkaller. This
> gives a decent coverage and I was able to find some places where
> fixups were required this way. Right now the fuzzer is running without
> issues. It doesn't prove that all such places are fixed, but I don't
> know a better way to test this.

Can sparse be hacked to identify pointer subtractions where the pointers
are cannot be statically proved to point into the same allocation?

Maybe the number of hits for this wouldn't be outrageously high, though
I expect there would be a fair number.

Tracking pointers that have been cast to integer types is harder.
Ideally we'd want to do that, to flag up potentially problematic
masking and other similar hacks.

Cheers
---Dave

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Catalin Marinas]

On Thu, Jun 28, 2018 at 08:56:41PM +0200, Andrey Konovalov wrote:
> On Thu, Jun 28, 2018 at 12:51 PM, Dave Martin <Dave.Martin@arm.com> wrote:
> > On Tue, Jun 26, 2018 at 03:15:10PM +0200, Andrey Konovalov wrote:
> >> 1. By using the Top Byte Ignore arm64 CPU feature, we can store pointer
> >>    tags in the top byte of each kernel pointer.
> >
> > [...]
> >
> > This is a change from the current situation, so the kernel may be
> > making implicit assumptions about the top byte of kernel addresses.
> >
> > Randomising the top bits may cause things like address conversions and
> > pointer arithmetic to break.
> >
> > For example, (q - p) will not produce the expected result if q and p
> > have different tags.
> 
> If q and p have different tags, that means they come from different
> allocations. I don't think it would make sense to calculate pointer
> difference in this case.

Well, there is a lot of pointer comparison in the kernel which means
pointer difference. Take is_vmalloc_addr() for example, even if your
patchset does not cover (IIUC) vmalloc() at the moment, this function
may be called with slab addresses. Presumably they would all fail the
check with a non-0xff tag but it's something needs understood. If you
later add support for vmalloc(), this test would fail (as would the
rb tree search in find_vmap_area(). Kmemleak would probably break as
well as it makes heavy use of rb tree.

Basically you need to be very clear about kernel pointer usage (with an
associated tag or type) vs address range it refers to and in most cases
converted to an unsigned long. See the other discussion on sparse, it
could potentially be useful if we can detect the places where a pointer
is converted to ulong and maybe hide such conversion behind a macro with
the arm64 implementation also clearing the tag.

-- 
Catalin

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Will Deacon]

On Thu, Jun 28, 2018 at 08:56:41PM +0200, Andrey Konovalov wrote:
> On Thu, Jun 28, 2018 at 12:51 PM, Dave Martin <Dave.Martin@arm.com> wrote:
> > On Tue, Jun 26, 2018 at 03:15:10PM +0200, Andrey Konovalov wrote:
> >> 1. By using the Top Byte Ignore arm64 CPU feature, we can store pointer
> >>    tags in the top byte of each kernel pointer.
> >
> > [...]
> >
> > This is a change from the current situation, so the kernel may be
> > making implicit assumptions about the top byte of kernel addresses.
> >
> > Randomising the top bits may cause things like address conversions and
> > pointer arithmetic to break.
> >
> > For example, (q - p) will not produce the expected result if q and p
> > have different tags.
> 
> If q and p have different tags, that means they come from different
> allocations. I don't think it would make sense to calculate pointer
> difference in this case.

It might not seen sensible, but we could still be relying on this in the
kernel and so this change would introduce a regression. I think we need
a way to identify such pointer usage before these patches can seriously be
considered for mainline inclusion. For example use of '>' and '<' to
compare pointers in an rbtree could be affected by the introduction of
tags.

Will

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Luc Van Oostenryck]

On Fri, Jun 29, 2018 at 12:04:22PM +0100, Dave Martin wrote:
> 
> Can sparse be hacked to identify pointer subtractions where the pointers
> are cannot be statically proved to point into the same allocation?

sparse only see the (deatils of) the function it analyses and all
visible declarations, nothing more.

It would be more a job for smatch which do global analysis.
But to identify such subtractions yu must already have a (good)
pointer alias analysis which I don't think smatch do (but I can
be wrong, Dan & smatch's ml added in CC).

-- Luc Van Oostenryck

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Andrey Konovalov]

On Thu, Jun 28, 2018 at 9:40 PM, Andrew Morton
<akpm@linux-foundation.org> wrote:
> On Thu, 28 Jun 2018 20:29:07 +0200 Andrey Konovalov <andreyknvl@google.com> wrote:
>
>> >> Slab memory usage after boot [2]:
>> >> * ~40 kb for clean kernel
>> >> * ~105 kb + 1/8th shadow ~= 118 kb for KASAN
>> >> * ~47 kb + 1/16th shadow ~= 50 kb for KHWASAN
>> >>
>> >> Network performance [3]:
>> >> * 8.33 Gbits/sec for clean kernel
>> >> * 3.17 Gbits/sec for KASAN
>> >> * 2.85 Gbits/sec for KHWASAN
>> >>
>> >> Note, that KHWASAN (compared to KASAN) doesn't require quarantine.
>> >>
>> >> [1] Time before the ext4 driver is initialized.
>> >> [2] Measured as `cat /proc/meminfo | grep Slab`.
>> >> [3] Measured as `iperf -s & iperf -c 127.0.0.1 -t 30`.
>> >
>> > The above doesn't actually demonstrate the whole point of the
>> > patchset: to reduce KASAN's very high memory consumption?
>>
>> You mean that memory usage numbers collected after boot don't give a
>> representative picture of actual memory consumption on real workloads?
>>
>> What kind of memory consumption testing would you like to see?
>
> Well, 100kb or so is a teeny amount on virtually any machine.  I'm
> assuming the savings are (much) more significant once the machine gets
> loaded up and doing work?

So with clean kernel after boot we get 40 kb memory usage. With KASAN
it is ~120 kb, which is 200% overhead. With KHWASAN it's 50 kb, which
is 25% overhead. This should approximately scale to any amounts of
used slab memory. For example with 100 mb memory usage we would get
+200 mb for KASAN and +25 mb with KHWASAN. (And KASAN also requires
quarantine for better use-after-free detection). I can explicitly
mention the overhead in %s in the changelog.

If you think it makes sense, I can also make separate measurements
with some workload. What kind of workload should I use?

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Mark Rutland]

On Fri, Jun 29, 2018 at 02:45:08PM +0200, Andrey Konovalov wrote:
> On Thu, Jun 28, 2018 at 9:40 PM, Andrew Morton
> <akpm@linux-foundation.org> wrote:
> > On Thu, 28 Jun 2018 20:29:07 +0200 Andrey Konovalov <andreyknvl@google.com> wrote:
> >
> >> >> Slab memory usage after boot [2]:
> >> >> * ~40 kb for clean kernel
> >> >> * ~105 kb + 1/8th shadow ~= 118 kb for KASAN
> >> >> * ~47 kb + 1/16th shadow ~= 50 kb for KHWASAN
> >> >>
> >> >> Network performance [3]:
> >> >> * 8.33 Gbits/sec for clean kernel
> >> >> * 3.17 Gbits/sec for KASAN
> >> >> * 2.85 Gbits/sec for KHWASAN
> >> >>
> >> >> Note, that KHWASAN (compared to KASAN) doesn't require quarantine.
> >> >>
> >> >> [1] Time before the ext4 driver is initialized.
> >> >> [2] Measured as `cat /proc/meminfo | grep Slab`.
> >> >> [3] Measured as `iperf -s & iperf -c 127.0.0.1 -t 30`.
> >> >
> >> > The above doesn't actually demonstrate the whole point of the
> >> > patchset: to reduce KASAN's very high memory consumption?
> >>
> >> You mean that memory usage numbers collected after boot don't give a
> >> representative picture of actual memory consumption on real workloads?
> >>
> >> What kind of memory consumption testing would you like to see?
> >
> > Well, 100kb or so is a teeny amount on virtually any machine.  I'm
> > assuming the savings are (much) more significant once the machine gets
> > loaded up and doing work?
> 
> So with clean kernel after boot we get 40 kb memory usage. With KASAN
> it is ~120 kb, which is 200% overhead. With KHWASAN it's 50 kb, which
> is 25% overhead. This should approximately scale to any amounts of
> used slab memory. For example with 100 mb memory usage we would get
> +200 mb for KASAN and +25 mb with KHWASAN. (And KASAN also requires
> quarantine for better use-after-free detection). I can explicitly
> mention the overhead in %s in the changelog.

Could you elaborate on where that SLAB overhead comes from?

IIUC that's not for the shadow itself (since it's allocated up-front and
not accounted to SLAB), and that doesn't take into account the
quarantine, so what's eating that space?

Thanks,
Mark.

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Andrey Konovalov]

On Fri, Jun 29, 2018 at 1:26 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Fri, Jun 29, 2018 at 12:04:22PM +0100, Dave Martin wrote:
>>
>> Can sparse be hacked to identify pointer subtractions where the pointers
>> are cannot be statically proved to point into the same allocation?

Re all the comments about finding all the places where we do pointer
subtraction/comparison:

I might be wrong, but I doubt you can easily do that with static analysis.

What we could do is to try to detect all such subtractions/comparisons
dynamically. The idea is to instrument all pointer/ulong
subtraction/comparison instructions and try to detect tags mismatch.
And then run some workload (e.g. syzkaller) to trigger more kernel
code. The question is how much false positives we would get, since I
imagine there would be a number of cases when we compare some random
ulongs.

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Dan Carpenter]

On Fri, Jun 29, 2018 at 01:26:14PM +0200, Luc Van Oostenryck wrote:
> On Fri, Jun 29, 2018 at 12:04:22PM +0100, Dave Martin wrote:
> > 
> > Can sparse be hacked to identify pointer subtractions where the pointers
> > are cannot be statically proved to point into the same allocation?
> 
> sparse only see the (deatils of) the function it analyses and all
> visible declarations, nothing more.
> 
> It would be more a job for smatch which do global analysis.
> But to identify such subtractions yu must already have a (good)
> pointer alias analysis which I don't think smatch do (but I can
> be wrong, Dan & smatch's ml added in CC).

That would be hard to manage.  Maybe in a year from now...

Pointer math errors tend to get caught pretty quick because they're on
the success path so I don't imagine there are huge numbers of bugs.

regards,
dan carpenter

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Andrey Konovalov]

On Fri, Jun 29, 2018 at 3:01 PM, Mark Rutland <mark.rutland@arm.com> wrote:
> On Fri, Jun 29, 2018 at 02:45:08PM +0200, Andrey Konovalov wrote:
>> So with clean kernel after boot we get 40 kb memory usage. With KASAN
>> it is ~120 kb, which is 200% overhead. With KHWASAN it's 50 kb, which
>> is 25% overhead. This should approximately scale to any amounts of
>> used slab memory. For example with 100 mb memory usage we would get
>> +200 mb for KASAN and +25 mb with KHWASAN. (And KASAN also requires
>> quarantine for better use-after-free detection). I can explicitly
>> mention the overhead in %s in the changelog.
>
> Could you elaborate on where that SLAB overhead comes from?
>
> IIUC that's not for the shadow itself (since it's allocated up-front and
> not accounted to SLAB), and that doesn't take into account the
> quarantine, so what's eating that space?

Redzones. KHWASAN doesn't need them since the next slab object is
marked with a different tag (with a high probability) and acts as a
redzone.

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Andrey Konovalov]

On Fri, Jun 29, 2018 at 1:07 PM, Will Deacon <will.deacon@arm.com> wrote:
> It might not seen sensible, but we could still be relying on this in the
> kernel and so this change would introduce a regression. I think we need
> a way to identify such pointer usage before these patches can seriously be
> considered for mainline inclusion.

Another point that I have here is that KHWASAN is a debugging tool not
meant to be used in production. We're not trying to change the ABI or
something like that (referring to the other HWASAN patchset). We can
fix up the non obvious places where untagging is needed in a case by
case basis with additional patches when testing reveals it.

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Andrew Morton]

On Fri, 29 Jun 2018 14:45:08 +0200 Andrey Konovalov <andreyknvl@google.com> wrote:

> >> What kind of memory consumption testing would you like to see?
> >
> > Well, 100kb or so is a teeny amount on virtually any machine.  I'm
> > assuming the savings are (much) more significant once the machine gets
> > loaded up and doing work?
> 
> So with clean kernel after boot we get 40 kb memory usage. With KASAN
> it is ~120 kb, which is 200% overhead. With KHWASAN it's 50 kb, which
> is 25% overhead. This should approximately scale to any amounts of
> used slab memory. For example with 100 mb memory usage we would get
> +200 mb for KASAN and +25 mb with KHWASAN. (And KASAN also requires
> quarantine for better use-after-free detection). I can explicitly
> mention the overhead in %s in the changelog.
> 
> If you think it makes sense, I can also make separate measurements
> with some workload. What kind of workload should I use?

Whatever workload people were running when they encountered problems
with KASAN memory consumption ;)

I dunno, something simple.  `find / > /dev/null'?

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Evgenii Stepanov]

Looking at a live Android device under load, slab (according to
/proc/meminfo) + kernel stack take 8-10% available RAM (~350MB).
Kasan's overhead of 2x - 3x on top of it is not insignificant.

On Fri, Jun 29, 2018 at 7:41 PM, Andrew Morton
<akpm@linux-foundation.org> wrote:
> On Fri, 29 Jun 2018 14:45:08 +0200 Andrey Konovalov <andreyknvl@google.com> wrote:
>
>> >> What kind of memory consumption testing would you like to see?
>> >
>> > Well, 100kb or so is a teeny amount on virtually any machine.  I'm
>> > assuming the savings are (much) more significant once the machine gets
>> > loaded up and doing work?
>>
>> So with clean kernel after boot we get 40 kb memory usage. With KASAN
>> it is ~120 kb, which is 200% overhead. With KHWASAN it's 50 kb, which
>> is 25% overhead. This should approximately scale to any amounts of
>> used slab memory. For example with 100 mb memory usage we would get
>> +200 mb for KASAN and +25 mb with KHWASAN. (And KASAN also requires
>> quarantine for better use-after-free detection). I can explicitly
>> mention the overhead in %s in the changelog.
>>
>> If you think it makes sense, I can also make separate measurements
>> with some workload. What kind of workload should I use?
>
> Whatever workload people were running when they encountered problems
> with KASAN memory consumption ;)
>
> I dunno, something simple.  `find / > /dev/null'?
>

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Andrew Morton]

On Mon, 2 Jul 2018 12:16:42 -0700 Evgenii Stepanov <eugenis@google.com> wrote:

> On Fri, Jun 29, 2018 at 7:41 PM, Andrew Morton
> <akpm@linux-foundation.org> wrote:
> > On Fri, 29 Jun 2018 14:45:08 +0200 Andrey Konovalov <andreyknvl@google.com> wrote:
> >
> >> >> What kind of memory consumption testing would you like to see?
> >> >
> >> > Well, 100kb or so is a teeny amount on virtually any machine.  I'm
> >> > assuming the savings are (much) more significant once the machine gets
> >> > loaded up and doing work?
> >>
> >> So with clean kernel after boot we get 40 kb memory usage. With KASAN
> >> it is ~120 kb, which is 200% overhead. With KHWASAN it's 50 kb, which
> >> is 25% overhead. This should approximately scale to any amounts of
> >> used slab memory. For example with 100 mb memory usage we would get
> >> +200 mb for KASAN and +25 mb with KHWASAN. (And KASAN also requires
> >> quarantine for better use-after-free detection). I can explicitly
> >> mention the overhead in %s in the changelog.
> >>
> >> If you think it makes sense, I can also make separate measurements
> >> with some workload. What kind of workload should I use?
> >
> > Whatever workload people were running when they encountered problems
> > with KASAN memory consumption ;)
> >
> > I dunno, something simple.  `find / > /dev/null'?
> >
>
> Looking at a live Android device under load, slab (according to
> /proc/meminfo) + kernel stack take 8-10% available RAM (~350MB).
> Kasan's overhead of 2x - 3x on top of it is not insignificant.
> 

(top-posting repaired.  Please don't)

For a debugging, not-for-production-use feature, that overhead sounds
quite acceptable to me.  What problems is it known to cause?

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Evgenii Stepanov]

On Mon, Jul 2, 2018 at 12:21 PM, Andrew Morton
<akpm@linux-foundation.org> wrote:
> On Mon, 2 Jul 2018 12:16:42 -0700 Evgenii Stepanov <eugenis@google.com> wrote:
>
>> On Fri, Jun 29, 2018 at 7:41 PM, Andrew Morton
>> <akpm@linux-foundation.org> wrote:
>> > On Fri, 29 Jun 2018 14:45:08 +0200 Andrey Konovalov <andreyknvl@google.com> wrote:
>> >
>> >> >> What kind of memory consumption testing would you like to see?
>> >> >
>> >> > Well, 100kb or so is a teeny amount on virtually any machine.  I'm
>> >> > assuming the savings are (much) more significant once the machine gets
>> >> > loaded up and doing work?
>> >>
>> >> So with clean kernel after boot we get 40 kb memory usage. With KASAN
>> >> it is ~120 kb, which is 200% overhead. With KHWASAN it's 50 kb, which
>> >> is 25% overhead. This should approximately scale to any amounts of
>> >> used slab memory. For example with 100 mb memory usage we would get
>> >> +200 mb for KASAN and +25 mb with KHWASAN. (And KASAN also requires
>> >> quarantine for better use-after-free detection). I can explicitly
>> >> mention the overhead in %s in the changelog.
>> >>
>> >> If you think it makes sense, I can also make separate measurements
>> >> with some workload. What kind of workload should I use?
>> >
>> > Whatever workload people were running when they encountered problems
>> > with KASAN memory consumption ;)
>> >
>> > I dunno, something simple.  `find / > /dev/null'?
>> >
>>
>> Looking at a live Android device under load, slab (according to
>> /proc/meminfo) + kernel stack take 8-10% available RAM (~350MB).
>> Kasan's overhead of 2x - 3x on top of it is not insignificant.
>>
>
> (top-posting repaired.  Please don't)
>
> For a debugging, not-for-production-use feature, that overhead sounds
> quite acceptable to me.  What problems is it known to cause?

Not having this overhead enables near-production use - ex. running
kasan/khasan kernel on a personal, daily-use device to catch bugs that
do not reproduce in test configuration. These are the ones that often
cost the most engineering time to track down.

CPU overhead is bad, but generally tolerable. RAM is critical, in our
experience. Once it gets low enough, OOM-killer makes your life
miserable.

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Andrew Morton]

On Mon, 2 Jul 2018 13:22:23 -0700 Evgenii Stepanov <eugenis@google.com> wrote:

> On Mon, Jul 2, 2018 at 12:21 PM, Andrew Morton
> <akpm@linux-foundation.org> wrote:
> > On Mon, 2 Jul 2018 12:16:42 -0700 Evgenii Stepanov <eugenis@google.com> wrote:
> >
> >> On Fri, Jun 29, 2018 at 7:41 PM, Andrew Morton
> >> <akpm@linux-foundation.org> wrote:
> >> > On Fri, 29 Jun 2018 14:45:08 +0200 Andrey Konovalov <andreyknvl@google.com> wrote:
> >> >
> >> >> >> What kind of memory consumption testing would you like to see?
> >> >> >
> >> >> > Well, 100kb or so is a teeny amount on virtually any machine.  I'm
> >> >> > assuming the savings are (much) more significant once the machine gets
> >> >> > loaded up and doing work?
> >> >>
> >> >> So with clean kernel after boot we get 40 kb memory usage. With KASAN
> >> >> it is ~120 kb, which is 200% overhead. With KHWASAN it's 50 kb, which
> >> >> is 25% overhead. This should approximately scale to any amounts of
> >> >> used slab memory. For example with 100 mb memory usage we would get
> >> >> +200 mb for KASAN and +25 mb with KHWASAN. (And KASAN also requires
> >> >> quarantine for better use-after-free detection). I can explicitly
> >> >> mention the overhead in %s in the changelog.
> >> >>
> >> >> If you think it makes sense, I can also make separate measurements
> >> >> with some workload. What kind of workload should I use?
> >> >
> >> > Whatever workload people were running when they encountered problems
> >> > with KASAN memory consumption ;)
> >> >
> >> > I dunno, something simple.  `find / > /dev/null'?
> >> >
> >>
> >> Looking at a live Android device under load, slab (according to
> >> /proc/meminfo) + kernel stack take 8-10% available RAM (~350MB).
> >> Kasan's overhead of 2x - 3x on top of it is not insignificant.
> >>
> >
> > (top-posting repaired.  Please don't)
> >
> > For a debugging, not-for-production-use feature, that overhead sounds
> > quite acceptable to me.  What problems is it known to cause?
> 
> Not having this overhead enables near-production use - ex. running
> kasan/khasan kernel on a personal, daily-use device to catch bugs that
> do not reproduce in test configuration. These are the ones that often
> cost the most engineering time to track down.
> 
> CPU overhead is bad, but generally tolerable. RAM is critical, in our
> experience. Once it gets low enough, OOM-killer makes your life
> miserable.

OK, anecdotal experience works for me.  But this is all stuff that
should have been in the changelog from day zero, please.  It describes
the reason for the patchset's existence!

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Matthew Wilcox]

On Wed, Jun 27, 2018 at 05:04:28PM -0700, Kostya Serebryany wrote:
> The problem is more significant on mobile devices than on desktop/server.
> I'd love to have [K]HWASAN on x86_64 as well, but it's less trivial since x86_64
> doesn't have an analog of aarch64's top-byte-ignore hardware feature.

Well, can we emulate it in software?

We've got 48 bits of virtual address space on x86.  If we need all 8
bits, then that takes us down to 40 bits (39 bits for user and 39 bits
for kernel).  My laptop only has 34 bits of physical memory, so could
we come up with a memory layout which works for me?

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Evgenii Stepanov]

On Mon, Jul 2, 2018 at 1:33 PM, Matthew Wilcox <willy@infradead.org> wrote:
> On Wed, Jun 27, 2018 at 05:04:28PM -0700, Kostya Serebryany wrote:
>> The problem is more significant on mobile devices than on desktop/server.
>> I'd love to have [K]HWASAN on x86_64 as well, but it's less trivial since x86_64
>> doesn't have an analog of aarch64's top-byte-ignore hardware feature.
>
> Well, can we emulate it in software?
>
> We've got 48 bits of virtual address space on x86.  If we need all 8
> bits, then that takes us down to 40 bits (39 bits for user and 39 bits
> for kernel).  My laptop only has 34 bits of physical memory, so could
> we come up with a memory layout which works for me?

Yes, probably.

We've tried this in userspace by mapping a file multiple times, but
that's very slow, likely because of the extra TLB pressure.
It should be possible to achieve better performance in the kernel with
some page table tricks (i.e. if we take top 8 bits out of 48, then
there would be only two second-level tables, and the top-level table
will look like [p1, p2, p1, p2, ...]). I'm not 100% sure if that would
work.

I don't think this should be part of this patchset, but it's good to
keep this in mind.

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Will Deacon]

On Fri, Jun 29, 2018 at 06:36:10PM +0200, Andrey Konovalov wrote:
> On Fri, Jun 29, 2018 at 1:07 PM, Will Deacon <will.deacon@arm.com> wrote:
> > It might not seen sensible, but we could still be relying on this in the
> > kernel and so this change would introduce a regression. I think we need
> > a way to identify such pointer usage before these patches can seriously be
> > considered for mainline inclusion.
> 
> Another point that I have here is that KHWASAN is a debugging tool not
> meant to be used in production. We're not trying to change the ABI or
> something like that (referring to the other HWASAN patchset). We can
> fix up the non obvious places where untagging is needed in a case by
> case basis with additional patches when testing reveals it.

Hmm, but elsewhere in this thread, Evgenii is motivating the need for this
patch set precisely because the lower overhead means it's suitable for
"near-production" use. So I don't think writing this off as a debugging
feature is the right approach, and we instead need to put effort into
analysing the impact of address tags on the kernel as a whole. Playing
whack-a-mole with subtle tag issues sounds like the worst possible outcome
for the long-term.

Will

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Andrey Konovalov]

On Mon, Jul 2, 2018 at 10:30 PM, Andrew Morton
<akpm@linux-foundation.org> wrote:
> OK, anecdotal experience works for me.  But this is all stuff that
> should have been in the changelog from day zero, please.  It describes
> the reason for the patchset's existence!

I will add all those points to the cover letter in v5.

On Tue, Jul 3, 2018 at 7:36 PM, Will Deacon <will.deacon@arm.com> wrote:
> Hmm, but elsewhere in this thread, Evgenii is motivating the need for this
> patch set precisely because the lower overhead means it's suitable for
> "near-production" use. So I don't think writing this off as a debugging
> feature is the right approach, and we instead need to put effort into
> analysing the impact of address tags on the kernel as a whole. Playing
> whack-a-mole with subtle tag issues sounds like the worst possible outcome
> for the long-term.

I don't see a way to find cases where pointer tags would matter
statically, so I've implemented the dynamic approach that I mentioned
above. I've instrumented all pointer comparisons/subtractions in an
LLVM compiler pass and used a kernel module that would print a bug
report whenever two pointers with different tags are being
compared/subtracted (ignoring comparisons with NULL pointers and with
pointers obtained by casting an error code to a pointer type). Then I
tried booting the kernel in QEMU and on an Odroid C2 board and I ran
syzkaller overnight.

This yielded the following results.

======

The two places that look interesting are:

is_vmalloc_addr in include/linux/mm.h (already mentioned by Catalin)
is_kernel_rodata in mm/util.c

Here we compare a pointer with some fixed untagged values to make sure
that the pointer lies in a particular part of the kernel address
space. Since KWHASAN doesn't add tags to pointers that belong to
rodata or vmalloc regions, this should work as is. To make sure I've
added debug checks to those two functions that check that the result
doesn't change whether we operate on pointers with or without
untagging.

======

A few other cases that don't look that interesting:

Comparing pointers to achieve unique sorting order of pointee objects
(e.g. sorting locks addresses before performing a double lock):

tty_ldisc_lock_pair_timeout in drivers/tty/tty_ldisc.c
pipe_double_lock in fs/pipe.c
unix_state_double_lock in net/unix/af_unix.c
lock_two_nondirectories in fs/inode.c
mutex_lock_double in kernel/events/core.c

ep_cmp_ffd in fs/eventpoll.c
fsnotify_compare_groups fs/notify/mark.c

Nothing needs to be done here, since the tags embedded into pointers
don't change, so the sorting order would still be unique.

Check that a pointer belongs to some particular allocation:

is_sibling_entry lib/radix-tree.c
object_is_on_stack in include/linux/sched/task_stack.h

Nothing needs to be here either, since two pointers can only belong to
the same allocation if they have the same tag.

======

Will, Catalin, WDYT?

Re: [PATCH v4 13/17] khwasan: add hooks implementation

[Andrey Konovalov]

On Wed, Jul 25, 2018 at 3:44 PM, Vincenzo Frascino@Foss
<vincenzo.frascino@arm.com> wrote:
> On 06/26/2018 02:15 PM, Andrey Konovalov wrote:
>
>> @@ -325,18 +341,41 @@ void kasan_init_slab_obj(struct kmem_cache *cache,
>> const void *object)
>>     void *kasan_slab_alloc(struct kmem_cache *cache, void *object, gfp_t
>> flags)
>>   {
>> -       return kasan_kmalloc(cache, object, cache->object_size, flags);
>> +       object = kasan_kmalloc(cache, object, cache->object_size, flags);
>> +       if (IS_ENABLED(CONFIG_KASAN_HW) && unlikely(cache->ctor)) {
>> +               /*
>> +                * Cache constructor might use object's pointer value to
>> +                * initialize some of its fields.
>> +                */
>> +               cache->ctor(object);
>>
> This seams breaking the kmem_cache_create() contract: "The @ctor is run when
> new pages are allocated by the cache."
> (https://elixir.bootlin.com/linux/v3.7/source/mm/slab_common.c#L83)
>
> Since there might be preexisting code relying on it, this could lead to
> global side effects. Did you verify that this is not the case?
>
> Another concern is performance related if we consider this solution suitable
> for "near-production", since with the current implementation you call the
> ctor (where present) on an object multiple times and this ends up memsetting
> and repopulating the memory every time (i.e. inode.c: inode_init_once). Do
> you know what is the performance impact?

We can assign tags to objects with constructors when a slab is
allocated and call constructors once as usual. The downside is that
such object would always have the same tag when it is reallocated, so
we won't catch use-after-frees. But that is probably something we'll
have to deal with if we're aiming for "near-production". I'll add this
change to v5, thanks!

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Andrey Konovalov]

On Wed, Jul 18, 2018 at 7:16 PM, Andrey Konovalov <andreyknvl@google.com> wrote:
> On Tue, Jul 3, 2018 at 7:36 PM, Will Deacon <will.deacon@arm.com> wrote:
>> Hmm, but elsewhere in this thread, Evgenii is motivating the need for this
>> patch set precisely because the lower overhead means it's suitable for
>> "near-production" use. So I don't think writing this off as a debugging
>> feature is the right approach, and we instead need to put effort into
>> analysing the impact of address tags on the kernel as a whole. Playing
>> whack-a-mole with subtle tag issues sounds like the worst possible outcome
>> for the long-term.
>
> I don't see a way to find cases where pointer tags would matter
> statically, so I've implemented the dynamic approach that I mentioned
> above. I've instrumented all pointer comparisons/subtractions in an
> LLVM compiler pass and used a kernel module that would print a bug
> report whenever two pointers with different tags are being
> compared/subtracted (ignoring comparisons with NULL pointers and with
> pointers obtained by casting an error code to a pointer type). Then I
> tried booting the kernel in QEMU and on an Odroid C2 board and I ran
> syzkaller overnight.
>
> This yielded the following results.
>
> ======
>
> The two places that look interesting are:
>
> is_vmalloc_addr in include/linux/mm.h (already mentioned by Catalin)
> is_kernel_rodata in mm/util.c
>
> Here we compare a pointer with some fixed untagged values to make sure
> that the pointer lies in a particular part of the kernel address
> space. Since KWHASAN doesn't add tags to pointers that belong to
> rodata or vmalloc regions, this should work as is. To make sure I've
> added debug checks to those two functions that check that the result
> doesn't change whether we operate on pointers with or without
> untagging.
>
> ======
>
> A few other cases that don't look that interesting:
>
> Comparing pointers to achieve unique sorting order of pointee objects
> (e.g. sorting locks addresses before performing a double lock):
>
> tty_ldisc_lock_pair_timeout in drivers/tty/tty_ldisc.c
> pipe_double_lock in fs/pipe.c
> unix_state_double_lock in net/unix/af_unix.c
> lock_two_nondirectories in fs/inode.c
> mutex_lock_double in kernel/events/core.c
>
> ep_cmp_ffd in fs/eventpoll.c
> fsnotify_compare_groups fs/notify/mark.c
>
> Nothing needs to be done here, since the tags embedded into pointers
> don't change, so the sorting order would still be unique.
>
> Check that a pointer belongs to some particular allocation:
>
> is_sibling_entry lib/radix-tree.c
> object_is_on_stack in include/linux/sched/task_stack.h
>
> Nothing needs to be here either, since two pointers can only belong to
> the same allocation if they have the same tag.
>
> ======
>
> Will, Catalin, WDYT?

ping

Re: [PATCH v4 13/17] khwasan: add hooks implementation

[Andrey Ryabinin]

On 07/31/2018 04:05 PM, Andrey Konovalov wrote:
> On Wed, Jul 25, 2018 at 3:44 PM, Vincenzo Frascino@Foss
> <vincenzo.frascino@arm.com> wrote:
>> On 06/26/2018 02:15 PM, Andrey Konovalov wrote:
>>
>>> @@ -325,18 +341,41 @@ void kasan_init_slab_obj(struct kmem_cache *cache,
>>> const void *object)
>>>     void *kasan_slab_alloc(struct kmem_cache *cache, void *object, gfp_t
>>> flags)
>>>   {
>>> -       return kasan_kmalloc(cache, object, cache->object_size, flags);
>>> +       object = kasan_kmalloc(cache, object, cache->object_size, flags);
>>> +       if (IS_ENABLED(CONFIG_KASAN_HW) && unlikely(cache->ctor)) {
>>> +               /*
>>> +                * Cache constructor might use object's pointer value to
>>> +                * initialize some of its fields.
>>> +                */
>>> +               cache->ctor(object);
>>>
>> This seams breaking the kmem_cache_create() contract: "The @ctor is run when
>> new pages are allocated by the cache."
>> (https://elixir.bootlin.com/linux/v3.7/source/mm/slab_common.c#L83)
>>
>> Since there might be preexisting code relying on it, this could lead to
>> global side effects. Did you verify that this is not the case?
>>
>> Another concern is performance related if we consider this solution suitable
>> for "near-production", since with the current implementation you call the
>> ctor (where present) on an object multiple times and this ends up memsetting
>> and repopulating the memory every time (i.e. inode.c: inode_init_once). Do
>> you know what is the performance impact?
> 
> We can assign tags to objects with constructors when a slab is
> allocated and call constructors once as usual. The downside is that
> such object would always have the same tag when it is reallocated, so
> we won't catch use-after-frees. 

Actually you should do this for SLAB_TYPESAFE_BY_RCU slabs. Usually they are with ->ctors but there
are few without constructors.
We can't reinitialize or even retag them. The latter will definitely cause false-positive use-after-free reports.

As for non-SLAB_TYPESAFE_BY_RCU caches with constructors, it's probably ok to reinitialize and retag such objects.
I don't see how could any code rely on the current ->ctor() behavior in non-SLAB_TYPESAFE_BY_RCU case,
unless it does something extremely stupid or weird.
But let's not do it now. If you care, you cand do it later, with a separate patch, so we could just revert
it if anything goes wrong.

Re: [PATCH v4 13/17] khwasan: add hooks implementation

[Dmitry Vyukov]

On Tue, Jul 31, 2018 at 4:50 PM, Andrey Ryabinin
<aryabinin@virtuozzo.com> wrote:
>
>
> On 07/31/2018 04:05 PM, Andrey Konovalov wrote:
>> On Wed, Jul 25, 2018 at 3:44 PM, Vincenzo Frascino@Foss
>> <vincenzo.frascino@arm.com> wrote:
>>> On 06/26/2018 02:15 PM, Andrey Konovalov wrote:
>>>
>>>> @@ -325,18 +341,41 @@ void kasan_init_slab_obj(struct kmem_cache *cache,
>>>> const void *object)
>>>>     void *kasan_slab_alloc(struct kmem_cache *cache, void *object, gfp_t
>>>> flags)
>>>>   {
>>>> -       return kasan_kmalloc(cache, object, cache->object_size, flags);
>>>> +       object = kasan_kmalloc(cache, object, cache->object_size, flags);
>>>> +       if (IS_ENABLED(CONFIG_KASAN_HW) && unlikely(cache->ctor)) {
>>>> +               /*
>>>> +                * Cache constructor might use object's pointer value to
>>>> +                * initialize some of its fields.
>>>> +                */
>>>> +               cache->ctor(object);
>>>>
>>> This seams breaking the kmem_cache_create() contract: "The @ctor is run when
>>> new pages are allocated by the cache."
>>> (https://elixir.bootlin.com/linux/v3.7/source/mm/slab_common.c#L83)
>>>
>>> Since there might be preexisting code relying on it, this could lead to
>>> global side effects. Did you verify that this is not the case?
>>>
>>> Another concern is performance related if we consider this solution suitable
>>> for "near-production", since with the current implementation you call the
>>> ctor (where present) on an object multiple times and this ends up memsetting
>>> and repopulating the memory every time (i.e. inode.c: inode_init_once). Do
>>> you know what is the performance impact?
>>
>> We can assign tags to objects with constructors when a slab is
>> allocated and call constructors once as usual. The downside is that
>> such object would always have the same tag when it is reallocated, so
>> we won't catch use-after-frees.
>
> Actually you should do this for SLAB_TYPESAFE_BY_RCU slabs. Usually they are with ->ctors but there
> are few without constructors.
> We can't reinitialize or even retag them. The latter will definitely cause false-positive use-after-free reports.

Somewhat offtopic, but I can't understand how SLAB_TYPESAFE_BY_RCU
slabs can be useful without ctors or at least memset(0). Objects in
such slabs need to be type-stable, but I can't understand how it's
possible to establish type stability without a ctor... Are these bugs?
Or I am missing something subtle? What would be a canonical usage of
SLAB_TYPESAFE_BY_RCU slab without a ctor?

Re: [PATCH v4 13/17] khwasan: add hooks implementation

[Andrey Konovalov]

On Tue, Jul 31, 2018 at 4:50 PM, Andrey Ryabinin
<aryabinin@virtuozzo.com> wrote:
> On 07/31/2018 04:05 PM, Andrey Konovalov wrote:
>> We can assign tags to objects with constructors when a slab is
>> allocated and call constructors once as usual. The downside is that
>> such object would always have the same tag when it is reallocated, so
>> we won't catch use-after-frees.
>
> Actually you should do this for SLAB_TYPESAFE_BY_RCU slabs. Usually they are with ->ctors but there
> are few without constructors.
> We can't reinitialize or even retag them. The latter will definitely cause false-positive use-after-free reports.
>
> As for non-SLAB_TYPESAFE_BY_RCU caches with constructors, it's probably ok to reinitialize and retag such objects.
> I don't see how could any code rely on the current ->ctor() behavior in non-SLAB_TYPESAFE_BY_RCU case,
> unless it does something extremely stupid or weird.
> But let's not do it now. If you care, you cand do it later, with a separate patch, so we could just revert
> it if anything goes wrong.

OK, will do it then when there's either a constructor or the slab is
SLAB_TYPESAFE_BY_RCU.

Re: [PATCH v4 13/17] khwasan: add hooks implementation

[Christopher Lameter]

On Tue, 31 Jul 2018, Dmitry Vyukov wrote:

> > Actually you should do this for SLAB_TYPESAFE_BY_RCU slabs. Usually they are with ->ctors but there
> > are few without constructors.
> > We can't reinitialize or even retag them. The latter will definitely cause false-positive use-after-free reports.
>
> Somewhat offtopic, but I can't understand how SLAB_TYPESAFE_BY_RCU
> slabs can be useful without ctors or at least memset(0). Objects in
> such slabs need to be type-stable, but I can't understand how it's
> possible to establish type stability without a ctor... Are these bugs?
> Or I am missing something subtle? What would be a canonical usage of
> SLAB_TYPESAFE_BY_RCU slab without a ctor?

True that sounds fishy. Would someone post a list of SLAB_TYPESAFE_BY_RCU
slabs without ctors?

Re: [PATCH v4 13/17] khwasan: add hooks implementation

[Dmitry Vyukov]

On Tue, Jul 31, 2018 at 5:38 PM, Christopher Lameter <cl@linux.com> wrote:
> On Tue, 31 Jul 2018, Dmitry Vyukov wrote:
>
>> > Actually you should do this for SLAB_TYPESAFE_BY_RCU slabs. Usually they are with ->ctors but there
>> > are few without constructors.
>> > We can't reinitialize or even retag them. The latter will definitely cause false-positive use-after-free reports.
>>
>> Somewhat offtopic, but I can't understand how SLAB_TYPESAFE_BY_RCU
>> slabs can be useful without ctors or at least memset(0). Objects in
>> such slabs need to be type-stable, but I can't understand how it's
>> possible to establish type stability without a ctor... Are these bugs?
>> Or I am missing something subtle? What would be a canonical usage of
>> SLAB_TYPESAFE_BY_RCU slab without a ctor?
>
> True that sounds fishy. Would someone post a list of SLAB_TYPESAFE_BY_RCU
> slabs without ctors?

https://elixir.bootlin.com/linux/latest/source/fs/jbd2/journal.c#L2395
https://elixir.bootlin.com/linux/latest/source/fs/kernfs/mount.c#L415
https://elixir.bootlin.com/linux/latest/source/net/netfilter/nf_conntrack_core.c#L2065
https://elixir.bootlin.com/linux/latest/source/drivers/gpu/drm/i915/i915_gem.c#L5501
https://elixir.bootlin.com/linux/latest/source/drivers/gpu/drm/i915/selftests/mock_gem_device.c#L212
https://elixir.bootlin.com/linux/latest/source/drivers/staging/lustre/lustre/ldlm/ldlm_lockd.c#L1131

Also these in proto structs:
https://elixir.bootlin.com/linux/latest/source/net/dccp/ipv4.c#L959
https://elixir.bootlin.com/linux/latest/source/net/dccp/ipv6.c#L1048
https://elixir.bootlin.com/linux/latest/source/net/ipv4/tcp_ipv4.c#L2461
https://elixir.bootlin.com/linux/latest/source/net/ipv6/tcp_ipv6.c#L1980
https://elixir.bootlin.com/linux/latest/source/net/llc/af_llc.c#L145
https://elixir.bootlin.com/linux/latest/source/net/smc/af_smc.c#L105

They later created in net/core/sock.c without ctor.

Re: [PATCH v4 13/17] khwasan: add hooks implementation

[Andrey Ryabinin]

On 07/31/2018 06:03 PM, Dmitry Vyukov wrote:
> On Tue, Jul 31, 2018 at 4:50 PM, Andrey Ryabinin
> <aryabinin@virtuozzo.com> wrote:
>>
>>
>> On 07/31/2018 04:05 PM, Andrey Konovalov wrote:
>>> On Wed, Jul 25, 2018 at 3:44 PM, Vincenzo Frascino@Foss
>>> <vincenzo.frascino@arm.com> wrote:
>>>> On 06/26/2018 02:15 PM, Andrey Konovalov wrote:
>>>>
>>>>> @@ -325,18 +341,41 @@ void kasan_init_slab_obj(struct kmem_cache *cache,
>>>>> const void *object)
>>>>>     void *kasan_slab_alloc(struct kmem_cache *cache, void *object, gfp_t
>>>>> flags)
>>>>>   {
>>>>> -       return kasan_kmalloc(cache, object, cache->object_size, flags);
>>>>> +       object = kasan_kmalloc(cache, object, cache->object_size, flags);
>>>>> +       if (IS_ENABLED(CONFIG_KASAN_HW) && unlikely(cache->ctor)) {
>>>>> +               /*
>>>>> +                * Cache constructor might use object's pointer value to
>>>>> +                * initialize some of its fields.
>>>>> +                */
>>>>> +               cache->ctor(object);
>>>>>
>>>> This seams breaking the kmem_cache_create() contract: "The @ctor is run when
>>>> new pages are allocated by the cache."
>>>> (https://elixir.bootlin.com/linux/v3.7/source/mm/slab_common.c#L83)
>>>>
>>>> Since there might be preexisting code relying on it, this could lead to
>>>> global side effects. Did you verify that this is not the case?
>>>>
>>>> Another concern is performance related if we consider this solution suitable
>>>> for "near-production", since with the current implementation you call the
>>>> ctor (where present) on an object multiple times and this ends up memsetting
>>>> and repopulating the memory every time (i.e. inode.c: inode_init_once). Do
>>>> you know what is the performance impact?
>>>
>>> We can assign tags to objects with constructors when a slab is
>>> allocated and call constructors once as usual. The downside is that
>>> such object would always have the same tag when it is reallocated, so
>>> we won't catch use-after-frees.
>>
>> Actually you should do this for SLAB_TYPESAFE_BY_RCU slabs. Usually they are with ->ctors but there
>> are few without constructors.
>> We can't reinitialize or even retag them. The latter will definitely cause false-positive use-after-free reports.
> 
> Somewhat offtopic, but I can't understand how SLAB_TYPESAFE_BY_RCU
> slabs can be useful without ctors or at least memset(0). Objects in
> such slabs need to be type-stable, but I can't understand how it's
> possible to establish type stability without a ctor... Are these bugs?

Yeah, I puzzled by this too. However, I think it's hard but possible to make it work, at least in theory.
There must be an initializer, which consists of two parts:
a) initilize objects fields
b) expose object to the world (add it to list or something like that)

(a) part must somehow to be ok to race with another cpu which might already use the object.
(b) part must must use e.g. barriers to make sure that racy users will see previously inilized fields.
Racy users must have parring barrier of course.

But it sound fishy, and very easy to fuck up. I won't be surprised if every single one SLAB_TYPESAFE_BY_RCU user
without ->ctor is bogus. It certainly would be better to convert those to use ->ctor.

Such caches seems used by networking subsystem in proto_register():

		prot->slab = kmem_cache_create_usercopy(prot->name,
					prot->obj_size, 0,
					SLAB_HWCACHE_ALIGN | SLAB_ACCOUNT |
					prot->slab_flags,
					prot->useroffset, prot->usersize,
					NULL);

And certain protocols specify SLAB_TYPESAFE_BY_RCU in ->slab_flags, such as:
llc_proto, smc_proto, smc_proto6, tcp_prot, tcpv6_prot, dccp_v6_prot, dccp_v4_prot.


Also nf_conntrack_cachep, kernfs_node_cache, jbd2_journal_head_cache and i915_request cache.

Re: [PATCH v4 13/17] khwasan: add hooks implementation

[Dmitry Vyukov]

On Tue, Jul 31, 2018 at 6:04 PM, Andrey Ryabinin
<aryabinin@virtuozzo.com> wrote:
>>>>>> @@ -325,18 +341,41 @@ void kasan_init_slab_obj(struct kmem_cache *cache,
>>>>>> const void *object)
>>>>>>     void *kasan_slab_alloc(struct kmem_cache *cache, void *object, gfp_t
>>>>>> flags)
>>>>>>   {
>>>>>> -       return kasan_kmalloc(cache, object, cache->object_size, flags);
>>>>>> +       object = kasan_kmalloc(cache, object, cache->object_size, flags);
>>>>>> +       if (IS_ENABLED(CONFIG_KASAN_HW) && unlikely(cache->ctor)) {
>>>>>> +               /*
>>>>>> +                * Cache constructor might use object's pointer value to
>>>>>> +                * initialize some of its fields.
>>>>>> +                */
>>>>>> +               cache->ctor(object);
>>>>>>
>>>>> This seams breaking the kmem_cache_create() contract: "The @ctor is run when
>>>>> new pages are allocated by the cache."
>>>>> (https://elixir.bootlin.com/linux/v3.7/source/mm/slab_common.c#L83)
>>>>>
>>>>> Since there might be preexisting code relying on it, this could lead to
>>>>> global side effects. Did you verify that this is not the case?
>>>>>
>>>>> Another concern is performance related if we consider this solution suitable
>>>>> for "near-production", since with the current implementation you call the
>>>>> ctor (where present) on an object multiple times and this ends up memsetting
>>>>> and repopulating the memory every time (i.e. inode.c: inode_init_once). Do
>>>>> you know what is the performance impact?
>>>>
>>>> We can assign tags to objects with constructors when a slab is
>>>> allocated and call constructors once as usual. The downside is that
>>>> such object would always have the same tag when it is reallocated, so
>>>> we won't catch use-after-frees.
>>>
>>> Actually you should do this for SLAB_TYPESAFE_BY_RCU slabs. Usually they are with ->ctors but there
>>> are few without constructors.
>>> We can't reinitialize or even retag them. The latter will definitely cause false-positive use-after-free reports.
>>
>> Somewhat offtopic, but I can't understand how SLAB_TYPESAFE_BY_RCU
>> slabs can be useful without ctors or at least memset(0). Objects in
>> such slabs need to be type-stable, but I can't understand how it's
>> possible to establish type stability without a ctor... Are these bugs?
>
> Yeah, I puzzled by this too. However, I think it's hard but possible to make it work, at least in theory.
> There must be an initializer, which consists of two parts:
> a) initilize objects fields
> b) expose object to the world (add it to list or something like that)
>
> (a) part must somehow to be ok to race with another cpu which might already use the object.
> (b) part must must use e.g. barriers to make sure that racy users will see previously inilized fields.
> Racy users must have parring barrier of course.
>
> But it sound fishy, and very easy to fuck up.


Agree on both fronts: theoretically possible but easy to fuck up. Even
if it works, complexity of the code should be brain damaging and there
are unlikely good reasons to just not be more explicit and use a ctor.


> I won't be surprised if every single one SLAB_TYPESAFE_BY_RCU user
> without ->ctor is bogus. It certainly would be better to convert those to use ->ctor.

I have another hypothesis: they are not bogus, just don't need
SLAB_TYPESAFE_BY_RCU :)


> Such caches seems used by networking subsystem in proto_register():
>
>                 prot->slab = kmem_cache_create_usercopy(prot->name,
>                                         prot->obj_size, 0,
>                                         SLAB_HWCACHE_ALIGN | SLAB_ACCOUNT |
>                                         prot->slab_flags,
>                                         prot->useroffset, prot->usersize,
>                                         NULL);
>
> And certain protocols specify SLAB_TYPESAFE_BY_RCU in ->slab_flags, such as:
> llc_proto, smc_proto, smc_proto6, tcp_prot, tcpv6_prot, dccp_v6_prot, dccp_v4_prot.
>
>
> Also nf_conntrack_cachep, kernfs_node_cache, jbd2_journal_head_cache and i915_request cache.
>
>
> --
> You received this message because you are subscribed to the Google Groups "kasan-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to kasan-dev+unsubscribe@googlegroups.com.
> To post to this group, send email to kasan-dev@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/kasan-dev/b6b58786-85c9-e831-5571-58b5580c84ba%40virtuozzo.com.
> For more options, visit https://groups.google.com/d/optout.

Re: [PATCH v4 13/17] khwasan: add hooks implementation

[Andrey Ryabinin]

On 07/31/2018 07:08 PM, Dmitry Vyukov wrote:
> On Tue, Jul 31, 2018 at 6:04 PM, Andrey Ryabinin
> <aryabinin@virtuozzo.com> wrote:
>>>>>>> @@ -325,18 +341,41 @@ void kasan_init_slab_obj(struct kmem_cache *cache,
>>>>>>> const void *object)
>>>>>>>     void *kasan_slab_alloc(struct kmem_cache *cache, void *object, gfp_t
>>>>>>> flags)
>>>>>>>   {
>>>>>>> -       return kasan_kmalloc(cache, object, cache->object_size, flags);
>>>>>>> +       object = kasan_kmalloc(cache, object, cache->object_size, flags);
>>>>>>> +       if (IS_ENABLED(CONFIG_KASAN_HW) && unlikely(cache->ctor)) {
>>>>>>> +               /*
>>>>>>> +                * Cache constructor might use object's pointer value to
>>>>>>> +                * initialize some of its fields.
>>>>>>> +                */
>>>>>>> +               cache->ctor(object);
>>>>>>>
>>>>>> This seams breaking the kmem_cache_create() contract: "The @ctor is run when
>>>>>> new pages are allocated by the cache."
>>>>>> (https://elixir.bootlin.com/linux/v3.7/source/mm/slab_common.c#L83)
>>>>>>
>>>>>> Since there might be preexisting code relying on it, this could lead to
>>>>>> global side effects. Did you verify that this is not the case?
>>>>>>
>>>>>> Another concern is performance related if we consider this solution suitable
>>>>>> for "near-production", since with the current implementation you call the
>>>>>> ctor (where present) on an object multiple times and this ends up memsetting
>>>>>> and repopulating the memory every time (i.e. inode.c: inode_init_once). Do
>>>>>> you know what is the performance impact?
>>>>>
>>>>> We can assign tags to objects with constructors when a slab is
>>>>> allocated and call constructors once as usual. The downside is that
>>>>> such object would always have the same tag when it is reallocated, so
>>>>> we won't catch use-after-frees.
>>>>
>>>> Actually you should do this for SLAB_TYPESAFE_BY_RCU slabs. Usually they are with ->ctors but there
>>>> are few without constructors.
>>>> We can't reinitialize or even retag them. The latter will definitely cause false-positive use-after-free reports.
>>>
>>> Somewhat offtopic, but I can't understand how SLAB_TYPESAFE_BY_RCU
>>> slabs can be useful without ctors or at least memset(0). Objects in
>>> such slabs need to be type-stable, but I can't understand how it's
>>> possible to establish type stability without a ctor... Are these bugs?
>>
>> Yeah, I puzzled by this too. However, I think it's hard but possible to make it work, at least in theory.
>> There must be an initializer, which consists of two parts:
>> a) initilize objects fields
>> b) expose object to the world (add it to list or something like that)
>>
>> (a) part must somehow to be ok to race with another cpu which might already use the object.
>> (b) part must must use e.g. barriers to make sure that racy users will see previously inilized fields.
>> Racy users must have parring barrier of course.
>>
>> But it sound fishy, and very easy to fuck up.
> 
> 
> Agree on both fronts: theoretically possible but easy to fuck up. Even
> if it works, complexity of the code should be brain damaging and there
> are unlikely good reasons to just not be more explicit and use a ctor.
> 
> 
>> I won't be surprised if every single one SLAB_TYPESAFE_BY_RCU user
>> without ->ctor is bogus. It certainly would be better to convert those to use ->ctor.
> 
> I have another hypothesis: they are not bogus, just don't need
> SLAB_TYPESAFE_BY_RCU :)
> 

I'd call this a bug too.

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Will Deacon]

Hi Andrey,

On Tue, Jul 31, 2018 at 03:22:13PM +0200, Andrey Konovalov wrote:
> On Wed, Jul 18, 2018 at 7:16 PM, Andrey Konovalov <andreyknvl@google.com> wrote:
> > On Tue, Jul 3, 2018 at 7:36 PM, Will Deacon <will.deacon@arm.com> wrote:
> >> Hmm, but elsewhere in this thread, Evgenii is motivating the need for this
> >> patch set precisely because the lower overhead means it's suitable for
> >> "near-production" use. So I don't think writing this off as a debugging
> >> feature is the right approach, and we instead need to put effort into
> >> analysing the impact of address tags on the kernel as a whole. Playing
> >> whack-a-mole with subtle tag issues sounds like the worst possible outcome
> >> for the long-term.
> >
> > I don't see a way to find cases where pointer tags would matter
> > statically, so I've implemented the dynamic approach that I mentioned
> > above. I've instrumented all pointer comparisons/subtractions in an
> > LLVM compiler pass and used a kernel module that would print a bug
> > report whenever two pointers with different tags are being
> > compared/subtracted (ignoring comparisons with NULL pointers and with
> > pointers obtained by casting an error code to a pointer type). Then I
> > tried booting the kernel in QEMU and on an Odroid C2 board and I ran
> > syzkaller overnight.
> >
> > This yielded the following results.
> >
> > ======
> >
> > The two places that look interesting are:
> >
> > is_vmalloc_addr in include/linux/mm.h (already mentioned by Catalin)
> > is_kernel_rodata in mm/util.c
> >
> > Here we compare a pointer with some fixed untagged values to make sure
> > that the pointer lies in a particular part of the kernel address
> > space. Since KWHASAN doesn't add tags to pointers that belong to
> > rodata or vmalloc regions, this should work as is. To make sure I've
> > added debug checks to those two functions that check that the result
> > doesn't change whether we operate on pointers with or without
> > untagging.
> >
> > ======
> >
> > A few other cases that don't look that interesting:
> >
> > Comparing pointers to achieve unique sorting order of pointee objects
> > (e.g. sorting locks addresses before performing a double lock):
> >
> > tty_ldisc_lock_pair_timeout in drivers/tty/tty_ldisc.c
> > pipe_double_lock in fs/pipe.c
> > unix_state_double_lock in net/unix/af_unix.c
> > lock_two_nondirectories in fs/inode.c
> > mutex_lock_double in kernel/events/core.c
> >
> > ep_cmp_ffd in fs/eventpoll.c
> > fsnotify_compare_groups fs/notify/mark.c
> >
> > Nothing needs to be done here, since the tags embedded into pointers
> > don't change, so the sorting order would still be unique.
> >
> > Check that a pointer belongs to some particular allocation:
> >
> > is_sibling_entry lib/radix-tree.c
> > object_is_on_stack in include/linux/sched/task_stack.h
> >
> > Nothing needs to be here either, since two pointers can only belong to
> > the same allocation if they have the same tag.
> >
> > ======
> >
> > Will, Catalin, WDYT?
> 
> ping

Thanks for tracking these cases down and going through each of them. The
obvious follow-up question is: how do we ensure that we keep on top of
this in mainline? Are you going to repeat your experiment at every kernel
release or every -rc or something else? I really can't see how we can
maintain this in the long run, especially given that the coverage we have
is only dynamic -- do you have an idea of how much coverage you're actually
getting for, say, a defconfig+modules build?

I'd really like to enable pointer tagging in the kernel, I'm just still
failing to see how we can do it in a controlled manner where we can reason
about the semantic changes using something other than a best-effort,
case-by-case basis which is likely to be fragile and error-prone.
Unfortunately, if that's all we have, then this gets relegated to a
debug feature, which sort of defeats the point in my opinion.

Will

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Dmitry Vyukov]

On Wed, Aug 1, 2018 at 6:35 PM, Will Deacon <will.deacon@arm.com> wrote:
> Hi Andrey,
>
> On Tue, Jul 31, 2018 at 03:22:13PM +0200, Andrey Konovalov wrote:
>> On Wed, Jul 18, 2018 at 7:16 PM, Andrey Konovalov <andreyknvl@google.com> wrote:
>> > On Tue, Jul 3, 2018 at 7:36 PM, Will Deacon <will.deacon@arm.com> wrote:
>> >> Hmm, but elsewhere in this thread, Evgenii is motivating the need for this
>> >> patch set precisely because the lower overhead means it's suitable for
>> >> "near-production" use. So I don't think writing this off as a debugging
>> >> feature is the right approach, and we instead need to put effort into
>> >> analysing the impact of address tags on the kernel as a whole. Playing
>> >> whack-a-mole with subtle tag issues sounds like the worst possible outcome
>> >> for the long-term.
>> >
>> > I don't see a way to find cases where pointer tags would matter
>> > statically, so I've implemented the dynamic approach that I mentioned
>> > above. I've instrumented all pointer comparisons/subtractions in an
>> > LLVM compiler pass and used a kernel module that would print a bug
>> > report whenever two pointers with different tags are being
>> > compared/subtracted (ignoring comparisons with NULL pointers and with
>> > pointers obtained by casting an error code to a pointer type). Then I
>> > tried booting the kernel in QEMU and on an Odroid C2 board and I ran
>> > syzkaller overnight.
>> >
>> > This yielded the following results.
>> >
>> > ======
>> >
>> > The two places that look interesting are:
>> >
>> > is_vmalloc_addr in include/linux/mm.h (already mentioned by Catalin)
>> > is_kernel_rodata in mm/util.c
>> >
>> > Here we compare a pointer with some fixed untagged values to make sure
>> > that the pointer lies in a particular part of the kernel address
>> > space. Since KWHASAN doesn't add tags to pointers that belong to
>> > rodata or vmalloc regions, this should work as is. To make sure I've
>> > added debug checks to those two functions that check that the result
>> > doesn't change whether we operate on pointers with or without
>> > untagging.
>> >
>> > ======
>> >
>> > A few other cases that don't look that interesting:
>> >
>> > Comparing pointers to achieve unique sorting order of pointee objects
>> > (e.g. sorting locks addresses before performing a double lock):
>> >
>> > tty_ldisc_lock_pair_timeout in drivers/tty/tty_ldisc.c
>> > pipe_double_lock in fs/pipe.c
>> > unix_state_double_lock in net/unix/af_unix.c
>> > lock_two_nondirectories in fs/inode.c
>> > mutex_lock_double in kernel/events/core.c
>> >
>> > ep_cmp_ffd in fs/eventpoll.c
>> > fsnotify_compare_groups fs/notify/mark.c
>> >
>> > Nothing needs to be done here, since the tags embedded into pointers
>> > don't change, so the sorting order would still be unique.
>> >
>> > Check that a pointer belongs to some particular allocation:
>> >
>> > is_sibling_entry lib/radix-tree.c
>> > object_is_on_stack in include/linux/sched/task_stack.h
>> >
>> > Nothing needs to be here either, since two pointers can only belong to
>> > the same allocation if they have the same tag.
>> >
>> > ======
>> >
>> > Will, Catalin, WDYT?
>>
>> ping
>
> Thanks for tracking these cases down and going through each of them. The
> obvious follow-up question is: how do we ensure that we keep on top of
> this in mainline? Are you going to repeat your experiment at every kernel
> release or every -rc or something else? I really can't see how we can
> maintain this in the long run, especially given that the coverage we have
> is only dynamic -- do you have an idea of how much coverage you're actually
> getting for, say, a defconfig+modules build?
>
> I'd really like to enable pointer tagging in the kernel, I'm just still
> failing to see how we can do it in a controlled manner where we can reason
> about the semantic changes using something other than a best-effort,
> case-by-case basis which is likely to be fragile and error-prone.
> Unfortunately, if that's all we have, then this gets relegated to a
> debug feature, which sort of defeats the point in my opinion.

Well, in some cases there is no other way as resorting to dynamic testing.
How do we ensure that kernel does not dereference NULL pointers, does
not access objects after free or out of bounds? Nohow. And, yes, it's
constant maintenance burden resolved via dynamic testing.
In some sense HWASAN is better in this regard because it's like, say,
LOCKDEP in this regard. It's enabled only when one does dynamic
testing and collect, analyze and fix everything that pops up. Any
false positives will fail loudly (as opposed to, say, silent memory
corruptions due to use-after-frees), so any false positives will be
just first things to fix during the tool application.

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Catalin Marinas]

On Wed, Aug 01, 2018 at 06:52:09PM +0200, Dmitry Vyukov wrote:
> On Wed, Aug 1, 2018 at 6:35 PM, Will Deacon <will.deacon@arm.com> wrote:
> > On Tue, Jul 31, 2018 at 03:22:13PM +0200, Andrey Konovalov wrote:
> >> On Wed, Jul 18, 2018 at 7:16 PM, Andrey Konovalov <andreyknvl@google.com> wrote:
> >> > On Tue, Jul 3, 2018 at 7:36 PM, Will Deacon <will.deacon@arm.com> wrote:
> >> >> Hmm, but elsewhere in this thread, Evgenii is motivating the need for this
> >> >> patch set precisely because the lower overhead means it's suitable for
> >> >> "near-production" use. So I don't think writing this off as a debugging
> >> >> feature is the right approach, and we instead need to put effort into
> >> >> analysing the impact of address tags on the kernel as a whole. Playing
> >> >> whack-a-mole with subtle tag issues sounds like the worst possible outcome
> >> >> for the long-term.
> >> >
> >> > I don't see a way to find cases where pointer tags would matter
> >> > statically, so I've implemented the dynamic approach that I mentioned
> >> > above. I've instrumented all pointer comparisons/subtractions in an
> >> > LLVM compiler pass and used a kernel module that would print a bug
> >> > report whenever two pointers with different tags are being
> >> > compared/subtracted (ignoring comparisons with NULL pointers and with
> >> > pointers obtained by casting an error code to a pointer type). Then I
> >> > tried booting the kernel in QEMU and on an Odroid C2 board and I ran
> >> > syzkaller overnight.
> >> >
> >> > This yielded the following results.
> >> >
> >> > ======
> >> >
> >> > The two places that look interesting are:
> >> >
> >> > is_vmalloc_addr in include/linux/mm.h (already mentioned by Catalin)
> >> > is_kernel_rodata in mm/util.c
> >> >
> >> > Here we compare a pointer with some fixed untagged values to make sure
> >> > that the pointer lies in a particular part of the kernel address
> >> > space. Since KWHASAN doesn't add tags to pointers that belong to
> >> > rodata or vmalloc regions, this should work as is. To make sure I've
> >> > added debug checks to those two functions that check that the result
> >> > doesn't change whether we operate on pointers with or without
> >> > untagging.
> >> >
> >> > ======
> >> >
> >> > A few other cases that don't look that interesting:
> >> >
> >> > Comparing pointers to achieve unique sorting order of pointee objects
> >> > (e.g. sorting locks addresses before performing a double lock):
> >> >
> >> > tty_ldisc_lock_pair_timeout in drivers/tty/tty_ldisc.c
> >> > pipe_double_lock in fs/pipe.c
> >> > unix_state_double_lock in net/unix/af_unix.c
> >> > lock_two_nondirectories in fs/inode.c
> >> > mutex_lock_double in kernel/events/core.c
> >> >
> >> > ep_cmp_ffd in fs/eventpoll.c
> >> > fsnotify_compare_groups fs/notify/mark.c
> >> >
> >> > Nothing needs to be done here, since the tags embedded into pointers
> >> > don't change, so the sorting order would still be unique.
> >> >
> >> > Check that a pointer belongs to some particular allocation:
> >> >
> >> > is_sibling_entry lib/radix-tree.c
> >> > object_is_on_stack in include/linux/sched/task_stack.h
> >> >
> >> > Nothing needs to be here either, since two pointers can only belong to
> >> > the same allocation if they have the same tag.
> >> >
> >> > ======
> >> >
> >> > Will, Catalin, WDYT?
> >>
> >> ping
> >
> > Thanks for tracking these cases down and going through each of them. The
> > obvious follow-up question is: how do we ensure that we keep on top of
> > this in mainline? Are you going to repeat your experiment at every kernel
> > release or every -rc or something else? I really can't see how we can
> > maintain this in the long run, especially given that the coverage we have
> > is only dynamic -- do you have an idea of how much coverage you're actually
> > getting for, say, a defconfig+modules build?
> >
> > I'd really like to enable pointer tagging in the kernel, I'm just still
> > failing to see how we can do it in a controlled manner where we can reason
> > about the semantic changes using something other than a best-effort,
> > case-by-case basis which is likely to be fragile and error-prone.
> > Unfortunately, if that's all we have, then this gets relegated to a
> > debug feature, which sort of defeats the point in my opinion.
> 
> Well, in some cases there is no other way as resorting to dynamic testing.
> How do we ensure that kernel does not dereference NULL pointers, does
> not access objects after free or out of bounds?

We should not confuse software bugs (like NULL pointer dereference) with
unexpected software behaviour introduced by khwasan where pointers no
longer represent only an address range (e.g. calling find_vmap_area())
but rather an address and a tag. Parts of the kernel rely on pointers
being just address ranges.

It's the latter that we'd like to identify more easily and avoid subtle
bugs or change in behaviour when running correctly written code.

> And, yes, it's
> constant maintenance burden resolved via dynamic testing.
> In some sense HWASAN is better in this regard because it's like, say,
> LOCKDEP in this regard. It's enabled only when one does dynamic
> testing and collect, analyze and fix everything that pops up. Any
> false positives will fail loudly (as opposed to, say, silent memory
> corruptions due to use-after-frees), so any false positives will be
> just first things to fix during the tool application.

Again, you are talking about the bugs that khwasan would discover. We
don't deny its value and false positives are acceptable here.

However, not untagging a pointer when converting to long may have
side-effects in some cases and I consider these bugs introduced by the
khwasan support rather than bugs in the original kernel code. Ideally
we'd need some tooling on top of khwasan to detect such shortcomings but
I'm not sure we can do this statically, as Andrey already mentioned. For
__user pointers, things are slightly better as we can detect the
conversion either with sparse (modified) or some LLVM changes.

-- 
Catalin

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Dmitry Vyukov]

On Thu, Aug 2, 2018 at 1:10 PM, Catalin Marinas <catalin.marinas@arm.com> wrote:
> On Wed, Aug 01, 2018 at 06:52:09PM +0200, Dmitry Vyukov wrote:
>> On Wed, Aug 1, 2018 at 6:35 PM, Will Deacon <will.deacon@arm.com> wrote:
>> > On Tue, Jul 31, 2018 at 03:22:13PM +0200, Andrey Konovalov wrote:
>> >> On Wed, Jul 18, 2018 at 7:16 PM, Andrey Konovalov <andreyknvl@google.com> wrote:
>> >> > On Tue, Jul 3, 2018 at 7:36 PM, Will Deacon <will.deacon@arm.com> wrote:
>> >> >> Hmm, but elsewhere in this thread, Evgenii is motivating the need for this
>> >> >> patch set precisely because the lower overhead means it's suitable for
>> >> >> "near-production" use. So I don't think writing this off as a debugging
>> >> >> feature is the right approach, and we instead need to put effort into
>> >> >> analysing the impact of address tags on the kernel as a whole. Playing
>> >> >> whack-a-mole with subtle tag issues sounds like the worst possible outcome
>> >> >> for the long-term.
>> >> >
>> >> > I don't see a way to find cases where pointer tags would matter
>> >> > statically, so I've implemented the dynamic approach that I mentioned
>> >> > above. I've instrumented all pointer comparisons/subtractions in an
>> >> > LLVM compiler pass and used a kernel module that would print a bug
>> >> > report whenever two pointers with different tags are being
>> >> > compared/subtracted (ignoring comparisons with NULL pointers and with
>> >> > pointers obtained by casting an error code to a pointer type). Then I
>> >> > tried booting the kernel in QEMU and on an Odroid C2 board and I ran
>> >> > syzkaller overnight.
>> >> >
>> >> > This yielded the following results.
>> >> >
>> >> > ======
>> >> >
>> >> > The two places that look interesting are:
>> >> >
>> >> > is_vmalloc_addr in include/linux/mm.h (already mentioned by Catalin)
>> >> > is_kernel_rodata in mm/util.c
>> >> >
>> >> > Here we compare a pointer with some fixed untagged values to make sure
>> >> > that the pointer lies in a particular part of the kernel address
>> >> > space. Since KWHASAN doesn't add tags to pointers that belong to
>> >> > rodata or vmalloc regions, this should work as is. To make sure I've
>> >> > added debug checks to those two functions that check that the result
>> >> > doesn't change whether we operate on pointers with or without
>> >> > untagging.
>> >> >
>> >> > ======
>> >> >
>> >> > A few other cases that don't look that interesting:
>> >> >
>> >> > Comparing pointers to achieve unique sorting order of pointee objects
>> >> > (e.g. sorting locks addresses before performing a double lock):
>> >> >
>> >> > tty_ldisc_lock_pair_timeout in drivers/tty/tty_ldisc.c
>> >> > pipe_double_lock in fs/pipe.c
>> >> > unix_state_double_lock in net/unix/af_unix.c
>> >> > lock_two_nondirectories in fs/inode.c
>> >> > mutex_lock_double in kernel/events/core.c
>> >> >
>> >> > ep_cmp_ffd in fs/eventpoll.c
>> >> > fsnotify_compare_groups fs/notify/mark.c
>> >> >
>> >> > Nothing needs to be done here, since the tags embedded into pointers
>> >> > don't change, so the sorting order would still be unique.
>> >> >
>> >> > Check that a pointer belongs to some particular allocation:
>> >> >
>> >> > is_sibling_entry lib/radix-tree.c
>> >> > object_is_on_stack in include/linux/sched/task_stack.h
>> >> >
>> >> > Nothing needs to be here either, since two pointers can only belong to
>> >> > the same allocation if they have the same tag.
>> >> >
>> >> > ======
>> >> >
>> >> > Will, Catalin, WDYT?
>> >>
>> >> ping
>> >
>> > Thanks for tracking these cases down and going through each of them. The
>> > obvious follow-up question is: how do we ensure that we keep on top of
>> > this in mainline? Are you going to repeat your experiment at every kernel
>> > release or every -rc or something else? I really can't see how we can
>> > maintain this in the long run, especially given that the coverage we have
>> > is only dynamic -- do you have an idea of how much coverage you're actually
>> > getting for, say, a defconfig+modules build?
>> >
>> > I'd really like to enable pointer tagging in the kernel, I'm just still
>> > failing to see how we can do it in a controlled manner where we can reason
>> > about the semantic changes using something other than a best-effort,
>> > case-by-case basis which is likely to be fragile and error-prone.
>> > Unfortunately, if that's all we have, then this gets relegated to a
>> > debug feature, which sort of defeats the point in my opinion.
>>
>> Well, in some cases there is no other way as resorting to dynamic testing.
>> How do we ensure that kernel does not dereference NULL pointers, does
>> not access objects after free or out of bounds?
>
> We should not confuse software bugs (like NULL pointer dereference) with
> unexpected software behaviour introduced by khwasan where pointers no
> longer represent only an address range (e.g. calling find_vmap_area())
> but rather an address and a tag.

These are also software bugs, not different from NULL derefs that we
do not detect statically.

> Parts of the kernel rely on pointers
> being just address ranges.
>
> It's the latter that we'd like to identify more easily and avoid subtle
> bugs or change in behaviour when running correctly written code.

You mean _previously_ correct code, now it's just incorrect code. Not
different from any other types of incorrect code, and we do have
thousands of types of incorrect code already, most of these types are
not detectable statically.

>> And, yes, it's
>> constant maintenance burden resolved via dynamic testing.
>> In some sense HWASAN is better in this regard because it's like, say,
>> LOCKDEP in this regard. It's enabled only when one does dynamic
>> testing and collect, analyze and fix everything that pops up. Any
>> false positives will fail loudly (as opposed to, say, silent memory
>> corruptions due to use-after-frees), so any false positives will be
>> just first things to fix during the tool application.
>
> Again, you are talking about the bugs that khwasan would discover. We
> don't deny its value and false positives are acceptable here.

I am talking about the same thing you are talking about. New crashes
of changes in behavior will also pop up and will need to be fixed.

> However, not untagging a pointer when converting to long may have
> side-effects in some cases and I consider these bugs introduced by the
> khwasan support rather than bugs in the original kernel code. Ideally
> we'd need some tooling on top of khwasan to detect such shortcomings but
> I'm not sure we can do this statically, as Andrey already mentioned. For
> __user pointers, things are slightly better as we can detect the
> conversion either with sparse (modified) or some LLVM changes.

I agree. Ideally we have strict static checking for this type of bugs.
Ideally we have it for all types of bugs. NULL derefs,
use-after-frees, or say confusion between a function returning 0/1 for
ok/failure with a function returning true/false. How do we detect that
statically? Nohow.

For example, LOCKDEP has the same problem. Previously correct code can
become incorrect and require finer-grained lock class annotations.
KMEMLEAK has the same problem: previously correct code that hides a
pointer may now need changes to unhide the pointer.

If somebody has a practical idea how to detect these statically, let's
do it. Otherwise let's go with the traditional solution to this --
dynamic testing. The patch series show that the problem is not a
disaster and we won't need to change just every line of kernel code.

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Catalin Marinas]

(trimming the quoted text a bit)

On Thu, Aug 02, 2018 at 01:36:25PM +0200, Dmitry Vyukov wrote:
> On Thu, Aug 2, 2018 at 1:10 PM, Catalin Marinas <catalin.marinas@arm.com> wrote:
> > On Wed, Aug 01, 2018 at 06:52:09PM +0200, Dmitry Vyukov wrote:
> >> On Wed, Aug 1, 2018 at 6:35 PM, Will Deacon <will.deacon@arm.com> wrote:
> >> > I'd really like to enable pointer tagging in the kernel, I'm just still
> >> > failing to see how we can do it in a controlled manner where we can reason
> >> > about the semantic changes using something other than a best-effort,
> >> > case-by-case basis which is likely to be fragile and error-prone.
> >> > Unfortunately, if that's all we have, then this gets relegated to a
> >> > debug feature, which sort of defeats the point in my opinion.
> >>
> >> Well, in some cases there is no other way as resorting to dynamic testing.
> >> How do we ensure that kernel does not dereference NULL pointers, does
> >> not access objects after free or out of bounds?
> >
> > We should not confuse software bugs (like NULL pointer dereference) with
> > unexpected software behaviour introduced by khwasan where pointers no
> > longer represent only an address range (e.g. calling find_vmap_area())
> > but rather an address and a tag.
[...]
> > However, not untagging a pointer when converting to long may have
> > side-effects in some cases and I consider these bugs introduced by the
> > khwasan support rather than bugs in the original kernel code. Ideally
> > we'd need some tooling on top of khwasan to detect such shortcomings but
> > I'm not sure we can do this statically, as Andrey already mentioned. For
> > __user pointers, things are slightly better as we can detect the
> > conversion either with sparse (modified) or some LLVM changes.
[...]
> For example, LOCKDEP has the same problem. Previously correct code can
> become incorrect and require finer-grained lock class annotations.
> KMEMLEAK has the same problem: previously correct code that hides a
> pointer may now need changes to unhide the pointer.

It's not actually the same. Take the kmemleak example as I'm familiar
with, previously correct code _continues_ to run correctly in the
presence of kmemleak. The annotation or unhiding is only necessary to
reduce the kmemleak false positives. With khwasan, OTOH, an explicit
untagging is necessary so that the code functions correctly again.

IOW, kmemleak only monitors the behaviour of the original code while
khwasan changes such behaviour by tagging the pointers.

> If somebody has a practical idea how to detect these statically, let's
> do it. Otherwise let's go with the traditional solution to this --
> dynamic testing. The patch series show that the problem is not a
> disaster and we won't need to change just every line of kernel code.

It's indeed not a disaster but we had to do this exercise to find out
whether there are better ways of detecting where untagging is necessary.

If you want to enable khwasan in "production" and since enabling it
could potentially change the behaviour of existing code paths, the
run-time validation space doubles as we'd need to get the same code
coverage with and without the feature being enabled. I wouldn't say it's
a blocker for khwasan, more like something to be aware of.

The awareness is a bit of a problem as the normal programmer would have
to pay more attention to conversions between pointer and long. Given
that this is an arm64-only feature, we have a risk of khwasan-triggered
bugs being introduced in generic code in the future (hence the
suggestion of some static checker, if possible).

-- 
Catalin

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Andrey Ryabinin]

On 08/02/2018 04:52 PM, Catalin Marinas wrote:
> 
>> If somebody has a practical idea how to detect these statically, let's
>> do it. Otherwise let's go with the traditional solution to this --
>> dynamic testing. The patch series show that the problem is not a
>> disaster and we won't need to change just every line of kernel code.
> 
> It's indeed not a disaster but we had to do this exercise to find out
> whether there are better ways of detecting where untagging is necessary.
> 
> If you want to enable khwasan in "production" and since enabling it
> could potentially change the behaviour of existing code paths, the
> run-time validation space doubles as we'd need to get the same code
> coverage with and without the feature being enabled. I wouldn't say it's
> a blocker for khwasan, more like something to be aware of.
> 
> The awareness is a bit of a problem as the normal programmer would have
> to pay more attention to conversions between pointer and long. Given
> that this is an arm64-only feature, we have a risk of khwasan-triggered
> bugs being introduced in generic code in the future (hence the
> suggestion of some static checker, if possible).
 
I don't see how we can implement such checker. There is no simple rule which defines when we need
to remove the tag and when we can leave it in place.
The cast to long have nothing to do with the need to remove the tag. If pointers compared for sorting objects,
or lock ordering, than having tags is fine and it doesn't matter whether pointers compared as 'unsigned long'
or as 'void *'.
If developer needs to check whether the pointer is in linear mapping, than tag has to be removed.
But again, it doesn't matter if pointer is 'unsigned long' or 'void *'. Either way, the tag has to go away.

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Will Deacon]

On Wed, Aug 01, 2018 at 06:52:09PM +0200, Dmitry Vyukov wrote:
> On Wed, Aug 1, 2018 at 6:35 PM, Will Deacon <will.deacon@arm.com> wrote:
> > Thanks for tracking these cases down and going through each of them. The
> > obvious follow-up question is: how do we ensure that we keep on top of
> > this in mainline? Are you going to repeat your experiment at every kernel
> > release or every -rc or something else? I really can't see how we can
> > maintain this in the long run, especially given that the coverage we have
> > is only dynamic -- do you have an idea of how much coverage you're actually
> > getting for, say, a defconfig+modules build?
> >
> > I'd really like to enable pointer tagging in the kernel, I'm just still
> > failing to see how we can do it in a controlled manner where we can reason
> > about the semantic changes using something other than a best-effort,
> > case-by-case basis which is likely to be fragile and error-prone.
> > Unfortunately, if that's all we have, then this gets relegated to a
> > debug feature, which sort of defeats the point in my opinion.
> 
> Well, in some cases there is no other way as resorting to dynamic testing.
> How do we ensure that kernel does not dereference NULL pointers, does
> not access objects after free or out of bounds? Nohow. And, yes, it's
> constant maintenance burden resolved via dynamic testing.

... and the advantage of NULL pointer issues is that you're likely to see
them as a synchronous exception at runtime, regardless of architecture and
regardless of Kconfig options. With pointer tagging, that's certainly not
the case, and so I don't think we can just treat issues there like we do for
NULL pointers.

Will

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Dmitry Vyukov]

On Fri, Aug 3, 2018 at 11:23 AM, Will Deacon <will.deacon@arm.com> wrote:
> On Wed, Aug 01, 2018 at 06:52:09PM +0200, Dmitry Vyukov wrote:
>> On Wed, Aug 1, 2018 at 6:35 PM, Will Deacon <will.deacon@arm.com> wrote:
>> > Thanks for tracking these cases down and going through each of them. The
>> > obvious follow-up question is: how do we ensure that we keep on top of
>> > this in mainline? Are you going to repeat your experiment at every kernel
>> > release or every -rc or something else? I really can't see how we can
>> > maintain this in the long run, especially given that the coverage we have
>> > is only dynamic -- do you have an idea of how much coverage you're actually
>> > getting for, say, a defconfig+modules build?
>> >
>> > I'd really like to enable pointer tagging in the kernel, I'm just still
>> > failing to see how we can do it in a controlled manner where we can reason
>> > about the semantic changes using something other than a best-effort,
>> > case-by-case basis which is likely to be fragile and error-prone.
>> > Unfortunately, if that's all we have, then this gets relegated to a
>> > debug feature, which sort of defeats the point in my opinion.
>>
>> Well, in some cases there is no other way as resorting to dynamic testing.
>> How do we ensure that kernel does not dereference NULL pointers, does
>> not access objects after free or out of bounds? Nohow. And, yes, it's
>> constant maintenance burden resolved via dynamic testing.
>
> ... and the advantage of NULL pointer issues is that you're likely to see
> them as a synchronous exception at runtime, regardless of architecture and
> regardless of Kconfig options. With pointer tagging, that's certainly not
> the case, and so I don't think we can just treat issues there like we do for
> NULL pointers.

Well, let's take use-after-frees, out-of-bounds, info leaks, data
races is a good example, deadlocks and just logical bugs...

> If you want to enable khwasan in "production" and since enabling it
> could potentially change the behaviour of existing code paths, the
> run-time validation space doubles as we'd need to get the same code
> coverage with and without the feature being enabled.

This is true for just any change in configs, sysctls or just a
different workload. Any of this can enable new code, exiting code
working differently, or just working with data in new states. And we
have tens of thousands of bugs, so blindly deploying anything new to
production without proper testing is a bad idea. It's not specific to
HWASAN in any way. And when you enable HWASAN you actually do mean to
retest everything as hard as possible.

And in the end we do not seem to have any action points here, right?

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Will Deacon]

On Fri, Aug 03, 2018 at 11:42:32AM +0200, Dmitry Vyukov wrote:
> On Fri, Aug 3, 2018 at 11:23 AM, Will Deacon <will.deacon@arm.com> wrote:
> > On Wed, Aug 01, 2018 at 06:52:09PM +0200, Dmitry Vyukov wrote:
> >> On Wed, Aug 1, 2018 at 6:35 PM, Will Deacon <will.deacon@arm.com> wrote:
> >> > Thanks for tracking these cases down and going through each of them. The
> >> > obvious follow-up question is: how do we ensure that we keep on top of
> >> > this in mainline? Are you going to repeat your experiment at every kernel
> >> > release or every -rc or something else? I really can't see how we can
> >> > maintain this in the long run, especially given that the coverage we have
> >> > is only dynamic -- do you have an idea of how much coverage you're actually
> >> > getting for, say, a defconfig+modules build?
> >> >
> >> > I'd really like to enable pointer tagging in the kernel, I'm just still
> >> > failing to see how we can do it in a controlled manner where we can reason
> >> > about the semantic changes using something other than a best-effort,
> >> > case-by-case basis which is likely to be fragile and error-prone.
> >> > Unfortunately, if that's all we have, then this gets relegated to a
> >> > debug feature, which sort of defeats the point in my opinion.
> >>
> >> Well, in some cases there is no other way as resorting to dynamic testing.
> >> How do we ensure that kernel does not dereference NULL pointers, does
> >> not access objects after free or out of bounds? Nohow. And, yes, it's
> >> constant maintenance burden resolved via dynamic testing.
> >
> > ... and the advantage of NULL pointer issues is that you're likely to see
> > them as a synchronous exception at runtime, regardless of architecture and
> > regardless of Kconfig options. With pointer tagging, that's certainly not
> > the case, and so I don't think we can just treat issues there like we do for
> > NULL pointers.
> 
> Well, let's take use-after-frees, out-of-bounds, info leaks, data
> races is a good example, deadlocks and just logical bugs...

Ok, but it was you that brought up NULL pointers, so there's some goalpost
moving here. And as with NULL pointers, all of the issues you mention above
apply to other architectures and the majority of their configurations, so my
concerns about this feature remain.

> > If you want to enable khwasan in "production" and since enabling it
> > could potentially change the behaviour of existing code paths, the
> > run-time validation space doubles as we'd need to get the same code
> > coverage with and without the feature being enabled.
> 
> This is true for just any change in configs, sysctls or just a
> different workload. Any of this can enable new code, exiting code
> working differently, or just working with data in new states. And we
> have tens of thousands of bugs, so blindly deploying anything new to
> production without proper testing is a bad idea. It's not specific to
> HWASAN in any way. And when you enable HWASAN you actually do mean to
> retest everything as hard as possible.

I suppose I'm trying to understand whether we have to resort to testing, or
whether we can do better. I'm really uncomfortable with testing as our only
means of getting this right because this is a non-standard, arm64-specific
option and I don't think it will get very much testing in mainline at all.
Rather, we'll get spurious bug reports from forks of -stable many releases
later and we'll actually be worse-off for it.

> And in the end we do not seem to have any action points here, right?

Right now, it feels like this series trades one set of bugs for another,
so I'd like to get to a position where this new set of bugs is genuinely
more manageable (i.e. detectable, fixable, preventable) than the old set.
Unfortunately, the only suggestion seems to be "testing", which I really
don't find convincing :(

Could we do things like:

  - Set up a dedicated arm64 test farm, running mainline and with a public
    frontend, aimed at getting maximum coverage of the kernel with KHWASAN
    enabled?

  - Have an implementation of KHWASAN for other architectures? (Is this even
    possible?)

  - Have a compiler plugin to clear out the tag for pointer arithmetic?
    Could we WARN if two pointers are compared with different tags?
    Could we manipulate the tag on cast-to-pointer so that a mismatch would
    be qualifier to say that pointer was created via a cast?

  - ...

?

Will

Re: [PATCH v4 00/17] khwasan: kernel hardware assisted address sanitizer

[Dmitry Vyukov]

On Wed, Aug 8, 2018 at 6:27 PM, Will Deacon <will.deacon@arm.com> wrote:
>> >> > Thanks for tracking these cases down and going through each of them. The
>> >> > obvious follow-up question is: how do we ensure that we keep on top of
>> >> > this in mainline? Are you going to repeat your experiment at every kernel
>> >> > release or every -rc or something else? I really can't see how we can
>> >> > maintain this in the long run, especially given that the coverage we have
>> >> > is only dynamic -- do you have an idea of how much coverage you're actually
>> >> > getting for, say, a defconfig+modules build?
>> >> >
>> >> > I'd really like to enable pointer tagging in the kernel, I'm just still
>> >> > failing to see how we can do it in a controlled manner where we can reason
>> >> > about the semantic changes using something other than a best-effort,
>> >> > case-by-case basis which is likely to be fragile and error-prone.
>> >> > Unfortunately, if that's all we have, then this gets relegated to a
>> >> > debug feature, which sort of defeats the point in my opinion.
>> >>
>> >> Well, in some cases there is no other way as resorting to dynamic testing.
>> >> How do we ensure that kernel does not dereference NULL pointers, does
>> >> not access objects after free or out of bounds? Nohow. And, yes, it's
>> >> constant maintenance burden resolved via dynamic testing.
>> >
>> > ... and the advantage of NULL pointer issues is that you're likely to see
>> > them as a synchronous exception at runtime, regardless of architecture and
>> > regardless of Kconfig options. With pointer tagging, that's certainly not
>> > the case, and so I don't think we can just treat issues there like we do for
>> > NULL pointers.
>>
>> Well, let's take use-after-frees, out-of-bounds, info leaks, data
>> races is a good example, deadlocks and just logical bugs...
>
> Ok, but it was you that brought up NULL pointers, so there's some goalpost
> moving here.

I moved it only because our views on bugs seems to be somewhat
different. I would put it all including NULL derefs into the same
bucket of bugs. But the point I wanted to make holds if we take NULL
derefs out of equation too, so I took them out so that we don't
concentrate on "synchronous exceptions" only.

> And as with NULL pointers, all of the issues you mention above
> apply to other architectures and the majority of their configurations, so my
> concerns about this feature remain.
>
>> > If you want to enable khwasan in "production" and since enabling it
>> > could potentially change the behaviour of existing code paths, the
>> > run-time validation space doubles as we'd need to get the same code
>> > coverage with and without the feature being enabled.
>>
>> This is true for just any change in configs, sysctls or just a
>> different workload. Any of this can enable new code, exiting code
>> working differently, or just working with data in new states. And we
>> have tens of thousands of bugs, so blindly deploying anything new to
>> production without proper testing is a bad idea. It's not specific to
>> HWASAN in any way. And when you enable HWASAN you actually do mean to
>> retest everything as hard as possible.
>
> I suppose I'm trying to understand whether we have to resort to testing, or
> whether we can do better. I'm really uncomfortable with testing as our only
> means of getting this right because this is a non-standard, arm64-specific
> option and I don't think it will get very much testing in mainline at all.
> Rather, we'll get spurious bug reports from forks of -stable many releases
> later and we'll actually be worse-off for it.
>
>> And in the end we do not seem to have any action points here, right?
>
> Right now, it feels like this series trades one set of bugs for another,
> so I'd like to get to a position where this new set of bugs is genuinely
> more manageable (i.e. detectable, fixable, preventable) than the old set.
> Unfortunately, the only suggestion seems to be "testing", which I really
> don't find convincing :(
>
> Could we do things like:
>
>   - Set up a dedicated arm64 test farm, running mainline and with a public
>     frontend, aimed at getting maximum coverage of the kernel with KHWASAN
>     enabled?

FWIW we could try to setup a syzbot instance with qemu/arm64
emulation. We run such combination few times, but I am not sure how
stable it will be wrt flaky timeouts/stalls/etc. If works, it will
give instant coverage of about 1MLOC.

>   - Have an implementation of KHWASAN for other architectures? (Is this even
>     possible?)
>
>   - Have a compiler plugin to clear out the tag for pointer arithmetic?
>     Could we WARN if two pointers are compared with different tags?
>     Could we manipulate the tag on cast-to-pointer so that a mismatch would
>     be qualifier to say that pointer was created via a cast?
>
>   - ...
>
> ?
>
> Will