Hello,
The proposed introduction of a relaxed ARM64 ABI [1] will allow tagged memory addresses to be passed through the user-kernel syscall ABI boundary. Tagged memory addresses are those which contain a non-zero top byte (the hardware has always ignored this top byte due to TCR_EL1.TBI0) and may be useful for features such as HWASan.
To permit this relaxation a proposed patchset [2] strips the top byte (tag) from user provided memory addresses prior to use in kernel functions which require untagged addresses (for example comparasion/arithmetic of addresses). The author of this patchset relied on a variety of techniques [2] (such as grep, BUG_ON, sparse etc) to identify as many instances of possible where tags need to be stipped.
To support this effort and to catch future regressions (e.g. in new syscalls or ioctls), I've devised an additional approach for detecting the use of tagged addresses in functions that do not want them. This approach makes use of Smatch [3] and is outlined in this RFC. Due to the ability of Smatch to do flow analysis I believe we can annotate the kernel in fewer places than a similar approach in sparse.
I'm keen for feedback on the likely usefulness of this approach.
We first add some new annotations that are exclusively consumed by Smatch:
--- a/include/linux/compiler_types.h +++ b/include/linux/compiler_types.h @@ -19,6 +19,7 @@ # define __cond_lock(x,c) ((c) ? ({ __acquire(x); 1; }) : 0) # define __percpu __attribute__((noderef, address_space(3))) # define __rcu __attribute__((noderef, address_space(4))) +# define __untagged __attribute__((address_space(5))) # define __private __attribute__((noderef)) extern void __chk_user_ptr(const volatile void __user *); extern void __chk_io_ptr(const volatile void __iomem *); @@ -45,6 +46,7 @@ extern void __chk_io_ptr(const volatile void __iomem *); ...
The purpose of this annotation is to indicate in function prototypes that a given argument must not be a user tagged memory address. (The address space number isn't significant here and could be replaced with any other annotation that we get Smatch to understand).
An example of how we use this annotation is as follows:
--- a/mm/mmap.c +++ b/mm/mmap.c @@ -2224,7 +2224,7 @@ get_unmapped_area(struct file *file, unsigned long addr, unsigned long len, EXPORT_SYMBOL(get_unmapped_area);
/* Look up the first VMA which satisfies addr < vm_end, NULL if none. */ -struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr) +struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long __untagged addr) { struct rb_node *rb_node; struct vm_area_struct *vma;
Thus our intent here is to flag up whenever addr is tagged. Specifically modifications I've made to Smatch to test this will flag an issue where all the following conditions are met:
1. the parameter is used in the function 2. the data in the parameter has originated or been derived from userspace (this relies on existing Smatch functionality to detect where data has come from) 3. the data's top byte is non-zero (via flow analysis to determine the range of values that it may be given the known call-tree).
Due to the use of smatch and its flow-analysis we don't need to propogate the __untagged annotation up the call chain to the callers and their callers - thus allowing us to only annotate functions that actually does something with the address and it's only necessary if the function has the potential to receive user data. I.e. we only need to tag find_vma to catch an issue with mmap_region (because it calls count_vma_pages_range which calls find_vma_intersection which calls find_vma).
Due to condition 3 above, the use of the existing untagged_addr macro (or anything that does something similar) will prevent smatch from producing a warning.
Using a vanilla (v5.2-rc2) kernel, and a single find_vma annotation, smatch will produce the following warnings:
mm/mmap.c:2227 find_vma() warn: Variable addr looks like a tagged address - it is not allowed here mm/mmap.c:2227 find_vma() warn: Variable addr looks like a tagged address - it is not allowed here mm/mmap.c:2227 find_vma() warn: Variable addr looks like a tagged address - it is not allowed here ...
The warning is printed for each call site that calls find_vma with a tagged address from userspace. After 6 runs of smatch, 24 warnings are produced.
The warnings are helpful in detecting issues, but not useful in providing enough information to debug the issue and find the offending functions higher up the call stack that call find_vma. Smatch is good at determining the ranges of values that can be passed to a function, but it doesn't keep track of how it determined those ranges - this makes it difficult to determine the offending function.
However even this level of limited functionality is helpful - as once the kernel is initially sanitized of tagged addresses, then the use of smatch here can spot regressions and offending code identified via git aiaiai/bisect.
Smatch builds a database which includes a table of functions, who they are called by and with what range of parameters. Smatch also provides a bunch of perl and python scripts which can be used to extract helpful information for example to produce a call tree for a given function. I've adapted these scripts such that for a given function (e.g. find_vma) it will show you the call tree where callers pass user data and where that data is tagged addresses. The output looks something like this:
find_vma() - 0-u64max (1) kvm_arch_prepare_memory_region() - 0-u64max (1) __kvm_set_memory_region() - 0-u64max (1) kvm_set_memory_region() - 0-u64max (1) kvm_vm_ioctl_set_memory_region() - 0-u64max (1) hugetlb_get_unmapped_area() - 0-u64max (1) shm_get_unmapped_area() - 0-u64max (1) shm_get_unmapped_area() - 32785,40977,98321,106513,2097151-u64max[c] (1) ...
In summary the following are found, note this currently unhelpfuly includes functions inbetween find_vma and the leaf functions:
$ cat find_vma_tree_orig | sed -e 's/^[ \t]*//' | cut -d ' ' -f 1 | sort | uniq call_mmap() check_and_migrate_cma_pages() compat_ipv6_getsockopt() compat_sock_common_getsockopt() compat_tcp_getsockopt() count_vma_pages_range() __do_compat_sys_get_mempolicy() do_get_mempolicy() do_ioctl() do_mincore() do_mlock() do_mmap() do_mmap_pgoff() ...
As you can see, this gives a good point in the right direction for hunting down callers of find_vma with tagged addresses.
This can be further improved - the problem here is that for a given function, e.g. find_vma we look for callers where *any* of the parameters passed to find_vma are tagged addresses from userspace - i.e. not *just* the annotated parameter. This is also true for find_vma's callers' callers'. This results in the call tree having false positives.
It *is* possible to track parameters (e.g. find_vma arg 1 comes from arg 3 of do_pages_stat_array etc), but this is limited as if functions modify the data then the tracking is stopped (however this can be fixed).
After apply the patchset ([PATCH v16 00/16] arm64: untag user pointers passed to the kernel)[2] which untags user addresses, smatch indicates 11 issues. The call tree is reduced. After grep'ing the call tree output, there are some valid instances where untagging is needed, e.g:
gntdev_ioctl_get_offset_for_vaddr() kvm_vm_ioctl_set_memory_region() privcmd_ioctl_mmap_batch() privcmd_ioctl_mmap_resource() __se_sys_brk() __se_sys_mremap() __se_sys_munmap() __se_sys_remap_file_pages() __se_sys_shmat() __se_sys_shmdt() __vm_munmap() ...
An example of a false positve is do_mlock. We untag the address and pass that to apply_vma_lock_flags - however we also pass a length - because the length came from userspace and could have the top bits set - it's flagged. However with improved parameter tracking we can remove this false positive and similar.
Prior to smatch I attempted a similar approach with sparse - however it seemed necessary to propogate the __untagged annotation in every function up the call tree, and resulted in adding the __untagged annotation to functions that would never get near user provided data. This leads to a littering of __untagged all over the kernel which doesn't seem appealing. Smatch is more capable, however it almost certainly won't pick up 100% of issues due to the difficulity of making flow analysis understand everything a compiler can.
Is it likely to be acceptable to use the __untagged annotation in user-path functions that require untagged addresses across the kernel?
Thanks,
Andrew Murray
[1] https://lkml.org/lkml/2019/6/13/534 [2] https://patchwork.kernel.org/cover/10989517/ [3] http://smatch.sourceforge.net/
Hi Andrew,
Cc'ing Luc (sparse maintainer) who's been involved in the past discussions around static checking of user pointers:
https://lore.kernel.org/linux-arm-kernel/20180905190316.a34yycthgbamx2t3@lto...
So I think the difference here from the previous approach is that we explicitly mark functions that cannot take tagged addresses (like find_vma()) and identify the callers.
More comments below:
On Wed, Jun 19, 2019 at 01:16:20PM +0100, Andrew Murray wrote:
The proposed introduction of a relaxed ARM64 ABI [1] will allow tagged memory addresses to be passed through the user-kernel syscall ABI boundary. Tagged memory addresses are those which contain a non-zero top byte (the hardware has always ignored this top byte due to TCR_EL1.TBI0) and may be useful for features such as HWASan.
To permit this relaxation a proposed patchset [2] strips the top byte (tag) from user provided memory addresses prior to use in kernel functions which require untagged addresses (for example comparasion/arithmetic of addresses). The author of this patchset relied on a variety of techniques [2] (such as grep, BUG_ON, sparse etc) to identify as many instances of possible where tags need to be stipped.
To support this effort and to catch future regressions (e.g. in new syscalls or ioctls), I've devised an additional approach for detecting the use of tagged addresses in functions that do not want them. This approach makes use of Smatch [3] and is outlined in this RFC. Due to the ability of Smatch to do flow analysis I believe we can annotate the kernel in fewer places than a similar approach in sparse.
I'm keen for feedback on the likely usefulness of this approach.
We first add some new annotations that are exclusively consumed by Smatch:
--- a/include/linux/compiler_types.h +++ b/include/linux/compiler_types.h @@ -19,6 +19,7 @@ # define __cond_lock(x,c) ((c) ? ({ __acquire(x); 1; }) : 0) # define __percpu __attribute__((noderef, address_space(3))) # define __rcu __attribute__((noderef, address_space(4))) +# define __untagged __attribute__((address_space(5))) # define __private __attribute__((noderef)) extern void __chk_user_ptr(const volatile void __user *); extern void __chk_io_ptr(const volatile void __iomem *);
[...]
--- a/mm/mmap.c +++ b/mm/mmap.c @@ -2224,7 +2224,7 @@ get_unmapped_area(struct file *file, unsigned long addr, unsigned long len, EXPORT_SYMBOL(get_unmapped_area); /* Look up the first VMA which satisfies addr < vm_end, NULL if none. */ -struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr) +struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long __untagged addr) { struct rb_node *rb_node; struct vm_area_struct *vma;
[...]
This can be further improved - the problem here is that for a given function, e.g. find_vma we look for callers where *any* of the parameters passed to find_vma are tagged addresses from userspace - i.e. not *just* the annotated parameter. This is also true for find_vma's callers' callers'. This results in the call tree having false positives.
It *is* possible to track parameters (e.g. find_vma arg 1 comes from arg 3 of do_pages_stat_array etc), but this is limited as if functions modify the data then the tracking is stopped (however this can be fixed).
[...]
An example of a false positve is do_mlock. We untag the address and pass that to apply_vma_lock_flags - however we also pass a length - because the length came from userspace and could have the top bits set - it's flagged. However with improved parameter tracking we can remove this false positive and similar.
Could we track only the conversions from __user * that eventually end up as __untagged? (I'm not familiar with smatch, so not sure what it can do). We could assume that an unsigned long argument to a syscall is default __untagged, unless explicitly marked as __tagged. For example, sys_munmap() is allowed to take a tagged address.
Prior to smatch I attempted a similar approach with sparse - however it seemed necessary to propogate the __untagged annotation in every function up the call tree, and resulted in adding the __untagged annotation to functions that would never get near user provided data. This leads to a littering of __untagged all over the kernel which doesn't seem appealing.
Indeed. We attempted this last year (see the above thread).
Smatch is more capable, however it almost certainly won't pick up 100% of issues due to the difficulity of making flow analysis understand everything a compiler can.
Is it likely to be acceptable to use the __untagged annotation in user-path functions that require untagged addresses across the kernel?
If it helps with identifying missing untagged_addr() calls, I would say yes (as long as we keep them to a minimum).
[1] https://lkml.org/lkml/2019/6/13/534 [2] https://patchwork.kernel.org/cover/10989517/ [3] http://smatch.sourceforge.net/
On Wed, Jun 26, 2019 at 06:45:03PM +0100, Catalin Marinas wrote:
Hi Andrew,
Cc'ing Luc (sparse maintainer) who's been involved in the past discussions around static checking of user pointers:
https://lore.kernel.org/linux-arm-kernel/20180905190316.a34yycthgbamx2t3@lto...
So I think the difference here from the previous approach is that we explicitly mark functions that cannot take tagged addresses (like find_vma()) and identify the callers.
Indeed.
More comments below:
On Wed, Jun 19, 2019 at 01:16:20PM +0100, Andrew Murray wrote:
The proposed introduction of a relaxed ARM64 ABI [1] will allow tagged memory addresses to be passed through the user-kernel syscall ABI boundary. Tagged memory addresses are those which contain a non-zero top byte (the hardware has always ignored this top byte due to TCR_EL1.TBI0) and may be useful for features such as HWASan.
To permit this relaxation a proposed patchset [2] strips the top byte (tag) from user provided memory addresses prior to use in kernel functions which require untagged addresses (for example comparasion/arithmetic of addresses). The author of this patchset relied on a variety of techniques [2] (such as grep, BUG_ON, sparse etc) to identify as many instances of possible where tags need to be stipped.
To support this effort and to catch future regressions (e.g. in new syscalls or ioctls), I've devised an additional approach for detecting the use of tagged addresses in functions that do not want them. This approach makes use of Smatch [3] and is outlined in this RFC. Due to the ability of Smatch to do flow analysis I believe we can annotate the kernel in fewer places than a similar approach in sparse.
I'm keen for feedback on the likely usefulness of this approach.
We first add some new annotations that are exclusively consumed by Smatch:
--- a/include/linux/compiler_types.h +++ b/include/linux/compiler_types.h @@ -19,6 +19,7 @@ # define __cond_lock(x,c) ((c) ? ({ __acquire(x); 1; }) : 0) # define __percpu __attribute__((noderef, address_space(3))) # define __rcu __attribute__((noderef, address_space(4))) +# define __untagged __attribute__((address_space(5))) # define __private __attribute__((noderef)) extern void __chk_user_ptr(const volatile void __user *); extern void __chk_io_ptr(const volatile void __iomem *);
[...]
--- a/mm/mmap.c +++ b/mm/mmap.c @@ -2224,7 +2224,7 @@ get_unmapped_area(struct file *file, unsigned long addr, unsigned long len, EXPORT_SYMBOL(get_unmapped_area); /* Look up the first VMA which satisfies addr < vm_end, NULL if none. */ -struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr) +struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long __untagged addr) { struct rb_node *rb_node; struct vm_area_struct *vma;
[...]
This can be further improved - the problem here is that for a given function, e.g. find_vma we look for callers where *any* of the parameters passed to find_vma are tagged addresses from userspace - i.e. not *just* the annotated parameter. This is also true for find_vma's callers' callers'. This results in the call tree having false positives.
It *is* possible to track parameters (e.g. find_vma arg 1 comes from arg 3 of do_pages_stat_array etc), but this is limited as if functions modify the data then the tracking is stopped (however this can be fixed).
[...]
An example of a false positve is do_mlock. We untag the address and pass that to apply_vma_lock_flags - however we also pass a length - because the length came from userspace and could have the top bits set - it's flagged. However with improved parameter tracking we can remove this false positive and similar.
Could we track only the conversions from __user * that eventually end up as __untagged? (I'm not familiar with smatch, so not sure what it can do).
I assume you mean 'that eventually end up as an argument annotated __untagged'?
The warnings smatch currently produce relate to only the conversions you mention - however further work is needed in smatch to improve the scripts that retrospectively provide call traces (without false positives).
We could assume that an unsigned long argument to a syscall is default __untagged, unless explicitly marked as __tagged. For example, sys_munmap() is allowed to take a tagged address.
I'll give this some further thought.
Prior to smatch I attempted a similar approach with sparse - however it seemed necessary to propogate the __untagged annotation in every function up the call tree, and resulted in adding the __untagged annotation to functions that would never get near user provided data. This leads to a littering of __untagged all over the kernel which doesn't seem appealing.
Indeed. We attempted this last year (see the above thread).
Smatch is more capable, however it almost certainly won't pick up 100% of issues due to the difficulity of making flow analysis understand everything a compiler can.
Is it likely to be acceptable to use the __untagged annotation in user-path functions that require untagged addresses across the kernel?
If it helps with identifying missing untagged_addr() calls, I would say yes (as long as we keep them to a minimum).
Thanks for the feedback.
Andrew Murray
[1] https://lkml.org/lkml/2019/6/13/534 [2] https://patchwork.kernel.org/cover/10989517/ [3] http://smatch.sourceforge.net/
-- Catalin
+ Dan and smatch@vger.kernel.org
Hi Andrew,
I am adding Dan to this thread since he is the smatch maintainer, and the smatch@vger.kernel.org list.
@Dan and @smatch@vger.kernel.org: a reference to the beginning of this thread can be found at [1].
[1] https://lkml.org/lkml/2019/6/19/376
On 6/27/19 2:18 PM, Andrew Murray wrote:
On Wed, Jun 26, 2019 at 06:45:03PM +0100, Catalin Marinas wrote:
Hi Andrew,
Cc'ing Luc (sparse maintainer) who's been involved in the past discussions around static checking of user pointers:
https://lore.kernel.org/linux-arm-kernel/20180905190316.a34yycthgbamx2t3@lto...
So I think the difference here from the previous approach is that we explicitly mark functions that cannot take tagged addresses (like find_vma()) and identify the callers.
Indeed.
More comments below:
On Wed, Jun 19, 2019 at 01:16:20PM +0100, Andrew Murray wrote:
The proposed introduction of a relaxed ARM64 ABI [1] will allow tagged memory addresses to be passed through the user-kernel syscall ABI boundary. Tagged memory addresses are those which contain a non-zero top byte (the hardware has always ignored this top byte due to TCR_EL1.TBI0) and may be useful for features such as HWASan.
To permit this relaxation a proposed patchset [2] strips the top byte (tag) from user provided memory addresses prior to use in kernel functions which require untagged addresses (for example comparasion/arithmetic of addresses). The author of this patchset relied on a variety of techniques [2] (such as grep, BUG_ON, sparse etc) to identify as many instances of possible where tags need to be stipped.
To support this effort and to catch future regressions (e.g. in new syscalls or ioctls), I've devised an additional approach for detecting the use of tagged addresses in functions that do not want them. This approach makes use of Smatch [3] and is outlined in this RFC. Due to the ability of Smatch to do flow analysis I believe we can annotate the kernel in fewer places than a similar approach in sparse.
I'm keen for feedback on the likely usefulness of this approach.
We first add some new annotations that are exclusively consumed by Smatch:
--- a/include/linux/compiler_types.h +++ b/include/linux/compiler_types.h @@ -19,6 +19,7 @@ # define __cond_lock(x,c) ((c) ? ({ __acquire(x); 1; }) : 0) # define __percpu __attribute__((noderef, address_space(3))) # define __rcu __attribute__((noderef, address_space(4))) +# define __untagged __attribute__((address_space(5))) # define __private __attribute__((noderef)) extern void __chk_user_ptr(const volatile void __user *); extern void __chk_io_ptr(const volatile void __iomem *);
[...]
--- a/mm/mmap.c +++ b/mm/mmap.c @@ -2224,7 +2224,7 @@ get_unmapped_area(struct file *file, unsigned long addr, unsigned long len, EXPORT_SYMBOL(get_unmapped_area); /* Look up the first VMA which satisfies addr < vm_end, NULL if none. */ -struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr) +struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long __untagged addr) { struct rb_node *rb_node; struct vm_area_struct *vma;
[...]
This can be further improved - the problem here is that for a given function, e.g. find_vma we look for callers where *any* of the parameters passed to find_vma are tagged addresses from userspace - i.e. not *just* the annotated parameter. This is also true for find_vma's callers' callers'. This results in the call tree having false positives.
It *is* possible to track parameters (e.g. find_vma arg 1 comes from arg 3 of do_pages_stat_array etc), but this is limited as if functions modify the data then the tracking is stopped (however this can be fixed).
[...]
An example of a false positve is do_mlock. We untag the address and pass that to apply_vma_lock_flags - however we also pass a length - because the length came from userspace and could have the top bits set - it's flagged. However with improved parameter tracking we can remove this false positive and similar.
Could we track only the conversions from __user * that eventually end up as __untagged? (I'm not familiar with smatch, so not sure what it can do).
I assume you mean 'that eventually end up as an argument annotated __untagged'?
The warnings smatch currently produce relate to only the conversions you mention - however further work is needed in smatch to improve the scripts that retrospectively provide call traces (without false positives).
We could assume that an unsigned long argument to a syscall is default __untagged, unless explicitly marked as __tagged. For example, sys_munmap() is allowed to take a tagged address.
I'll give this some further thought.
Prior to smatch I attempted a similar approach with sparse - however it seemed necessary to propogate the __untagged annotation in every function up the call tree, and resulted in adding the __untagged annotation to functions that would never get near user provided data. This leads to a littering of __untagged all over the kernel which doesn't seem appealing.
Indeed. We attempted this last year (see the above thread).
Smatch is more capable, however it almost certainly won't pick up 100% of issues due to the difficulity of making flow analysis understand everything a compiler can.
Is it likely to be acceptable to use the __untagged annotation in user-path functions that require untagged addresses across the kernel?
If it helps with identifying missing untagged_addr() calls, I would say yes (as long as we keep them to a minimum).
Thanks for the feedback.
Andrew Murray
[1] https://lkml.org/lkml/2019/6/13/534 [2] https://patchwork.kernel.org/cover/10989517/ [3] http://smatch.sourceforge.net/
-- Catalin
linux-kselftest-mirror@lists.linaro.org
-
Andrew Murray -
Catalin Marinas -
Vincenzo Frascino