khwasan: kernel hardware assisted address sanitizer

Quoted 4 lines · Andrey Konovalov

mm/kasan/common.c +0 -0

@@ -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)

mm/kasan/common.c void kasan_init_slab_obj(struct kmem_cache *cache, · line 352

Quoted 10 lines

mm/kasan/common.c +7 -1

  {
-       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?

Quoted 20 lines · Vincenzo Frascino at Foss

Quoted 4 lines · Andrey Konovalov

mm/kasan/common.c +0 -0

@@ -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)

mm/kasan/common.c void kasan_init_slab_obj(struct kmem_cache *cache, · line 352

Quoted 10 lines

mm/kasan/common.c +7 -1

  {
-       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)

Quoted 8 lines

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.

Quoted 31 lines · Andrey Konovalov

Quoted 28 lines · Vincenzo Frascino at Foss

Quoted 4 lines · Andrey Konovalov

mm/kasan/common.c +0 -0

@@ -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)

mm/kasan/common.c void kasan_init_slab_obj(struct kmem_cache *cache, · line 352

Quoted 10 lines

mm/kasan/common.c +7 -1

  {
-       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?

Quoted 4 lines

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.

Quoted 3 lines

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?

Quoted 10 lines · Dmitry Vyukov

Quoted 3 lines

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?

Quoted 39 lines · Andrey Ryabinin

Quoted 35 lines · Andrey Konovalov

Quoted 20 lines · Vincenzo Frascino at Foss

Quoted 4 lines · Andrey Konovalov

mm/kasan/common.c +0 -0

@@ -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)

mm/kasan/common.c void kasan_init_slab_obj(struct kmem_cache *cache, · line 352

Quoted 10 lines

mm/kasan/common.c +7 -1

  {
-       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)

Quoted 8 lines

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.

Quoted 3 lines

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?

Quoted 32 lines

Quoted 32 lines

Quoted 31 lines

Quoted 18 lines

Quoted 4 lines

mm/kasan/common.c +0 -0

@@ -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)

mm/kasan/common.c void kasan_init_slab_obj(struct kmem_cache *cache, · line 352

Quoted 10 lines

mm/kasan/common.c +7 -1

  {
-       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)

Quoted 8 lines

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.

Quoted 8 lines

Quoted 3 lines

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.

--
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 at googlegroups.com. To post to this group, send email to kasan-dev at 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.

Quoted 46 lines · Andrey Ryabinin

Quoted 32 lines

Quoted 32 lines

Quoted 31 lines

Quoted 18 lines

Quoted 4 lines

(quoted diff) +0 -0

@@ -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)

Review void kasan_init_slab_obj(struct kmem_cache *cache, · line 352

Quoted 10 lines

(quoted diff) +7 -1

  {
-       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)

Quoted 8 lines

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.

Quoted 8 lines

Quoted 3 lines

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)

Quoted 5 lines

(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.

Quoted 2 lines

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 :)

Quoted 4 lines · Andrey Konovalov

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.

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.

====== 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.

Quoted 7 lines · On Tue, 26 Jun 2018 15:15:10 +0200 Andrey Konovalov <[email protected]>…

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?

Quoted 21 lines

====== 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

Quoted 5 lines

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 at googlegroups.com. To post to this group, send email to kasan-dev at 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.

Quoted 2 lines · Andrew Morton

On Tue, 26 Jun 2018 15:15:10 +0200 Andrey Konovalov <

Quoted 6 lines · [email protected]> wrote:

Quoted 6 lines

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

Quoted 5 lines

Quoted 2 lines

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?

Quoted 2 lines

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)

Quoted 2 lines

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.

Quoted 27 lines

Quoted 21 lines

====== 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

Quoted 5 lines

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.

Quoted 5 lines

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.

Quoted 1 line

To unsubscribe from this group and stop receiving emails from it, send

an email to [email protected].

Quoted 2 lines

To post to this group, send email to [email protected]. To view this discussion on the web visit

https://groups.google.com/d/msgid/kasan-dev/20180627160800.3dc7f9ee41c0badbf7342520%40linux-foundation.org
.

Quoted 1 line

For more options, visit https://groups.google.com/d/optout.

Quoted 5 lines

Quoted 5 lines

Quoted 2 lines

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?

Quoted 8 lines

Quoted 2 lines

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.

Quoted 9 lines · On Wed, 27 Jun 2018 17:59:00 -0700 Vishwath Mohan <[email protected]> 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/>

Quoted 2 lines

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.

Quoted 9 lines · Andrew Morton

Quoted 7 lines · On Tue, 26 Jun 2018 15:15:10 +0200 Andrey Konovalov <[email protected]>…

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.

Quoted 4 lines

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)

Quoted 2 lines

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.

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.

Quoted 3 lines · Kostya Serebryany

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?

Quoted 20 lines · On Tue, 26 Jun 2018 15:15:10 +0200 Andrey Konovalov <[email protected]>…

====== 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

Quoted 5 lines

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?

Quoted 16 lines

Quoted 15 lines

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.

Quoted 2 lines

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?

Quoted 19 lines · On Thu, 28 Jun 2018 20:29:07 +0200 Andrey Konovalov <[email protected]>…

Quoted 18 lines

Quoted 10 lines

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

Quoted 5 lines

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?

Quoted 4 lines

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?

Quoted 21 lines · Andrew Morton

Quoted 19 lines · On Thu, 28 Jun 2018 20:29:07 +0200 Andrey Konovalov <[email protected]>…

Quoted 18 lines

Quoted 10 lines

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

Quoted 5 lines

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?

Quoted 8 lines

Quoted 4 lines

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.

Quoted 7 lines · Andrey Konovalov

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?

Quoted 5 lines

Quoted 1 line

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?

Quoted 14 lines · On Fri, 29 Jun 2018 14:45:08 +0200 Andrey Konovalov <[email protected]>…

Quoted 5 lines

Quoted 1 line

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.

Quoted 2 lines

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'?

Quoted 22 lines · Andrew Morton

Quoted 14 lines · On Fri, 29 Jun 2018 14:45:08 +0200 Andrey Konovalov <[email protected]>…

Quoted 5 lines

Quoted 1 line

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.

Quoted 2 lines

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 ;)

Quoted 2 lines

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.

Quoted 24 lines · On Mon, 2 Jul 2018 12:16:42 -0700 Evgenii Stepanov <[email protected]> wrote:

Quoted 22 lines · Andrew Morton

Quoted 14 lines · On Fri, 29 Jun 2018 14:45:08 +0200 Andrey Konovalov <[email protected]>…

Quoted 5 lines

Quoted 1 line

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.

Quoted 2 lines

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 ;)

Quoted 7 lines

Quoted 2 lines

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?

Quoted 34 lines · Andrew Morton

Quoted 24 lines · On Mon, 2 Jul 2018 12:16:42 -0700 Evgenii Stepanov <[email protected]> wrote:

Quoted 22 lines · Andrew Morton

Quoted 14 lines · On Fri, 29 Jun 2018 14:45:08 +0200 Andrey Konovalov <[email protected]>…

Quoted 5 lines

Quoted 1 line

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.

Quoted 2 lines

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 ;)

Quoted 7 lines

Quoted 2 lines

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.

Quoted 4 lines

(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.

Quoted 1 line · Andrew Morton

On Mon, 2 Jul 2018 12:16:42 -0700 Evgenii Stepanov <[email protected]>

Quoted 4 lines · wrote:

Quoted 4 lines

Quoted 1 line · Andrew Morton

On Fri, 29 Jun 2018 14:45:08 +0200 Andrey Konovalov <

Quoted 5 lines · [email protected]> wrote:

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

Quoted 2 lines

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

Quoted 24 lines

Quoted 16 lines

Quoted 16 lines

Quoted 10 lines

Quoted 1 line

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.

Quoted 2 lines

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 ;)

Quoted 7 lines

Quoted 2 lines

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.

Quoted 4 lines

(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.

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.

Quoted 2 lines · Andrey Konovalov

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?

Quoted 8 lines · Dave Martin

Quoted 2 lines · Andrey Konovalov

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.

Quoted 2 lines

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.

Quoted 12 lines · Dave Martin

Quoted 2 lines · Andrey Konovalov

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.

Quoted 2 lines

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.

Quoted 7 lines

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.

Quoted 2 lines

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?

Quoted 3 lines · Dave Martin

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

Quoted 3 lines · Dave Martin

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).

Quoted 12 lines · Dave Martin

Quoted 2 lines · Andrey Konovalov

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.

Quoted 2 lines

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.

Quoted 4 lines · Will Deacon

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.

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!

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.

Quoted 7 lines · Will Deacon

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?

Quoted 60 lines · Andrey Konovalov

Quoted 7 lines · Will Deacon

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

Quoted 6 lines

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

Hi Andrey,

Quoted 61 lines · Andrey Konovalov

Quoted 60 lines · Andrey Konovalov

Quoted 7 lines · Will Deacon

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

Quoted 8 lines

Quoted 6 lines

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.

Quoted 79 lines · Will Deacon

Quoted 61 lines · Andrey Konovalov

Quoted 60 lines · Andrey Konovalov

Quoted 7 lines · Will Deacon

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

Quoted 8 lines

Quoted 6 lines

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?

Quoted 6 lines

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?

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.

Quoted 87 lines · Dmitry Vyukov

Quoted 85 lines · Will Deacon

Quoted 61 lines · Andrey Konovalov

Quoted 60 lines · Andrey Konovalov

Quoted 7 lines · Will Deacon

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

Quoted 8 lines

Quoted 6 lines

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.

Quoted 3 lines

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.

Quoted 8 lines

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.

Quoted 17 lines · Catalin Marinas

Quoted 11 lines · Dmitry Vyukov

Quoted 6 lines · Will Deacon

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.

Quoted 7 lines

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.

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.

Quoted 5 lines

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).

Quoted 8 lines · Will Deacon

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?

Quoted 6 lines

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.

Quoted 16 lines · Dmitry Vyukov

Quoted 8 lines · Will Deacon

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?

Quoted 6 lines

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.

Quoted 4 lines

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.

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.

Quoted 22 lines · Will Deacon

Quoted 20 lines · Dmitry Vyukov

Quoted 8 lines · Will Deacon

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?

Quoted 6 lines

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.

Quoted 5 lines

... 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...

Quoted 4 lines

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?

Quoted 26 lines

Quoted 25 lines

Quoted 15 lines

Quoted 8 lines

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?

Quoted 6 lines

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.

Quoted 4 lines

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.

Quoted 2 lines

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.

Quoted 5 lines

Quoted 4 lines

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.

Quoted 7 lines

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.

Quoted 1 line

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

Quoted 12 lines · Dave Martin

Quoted 2 lines · Andrey Konovalov

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.

Quoted 2 lines

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.