[RFC] arm64: Detecting tagged addresses

Commit Message

Andrew Murray June 19, 2019, 12:16 p.m. UTC

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:




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/

Comments

Catalin Marinas June 26, 2019, 5:45 p.m. UTC | #1

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/[e-mail]/

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/

Andrew Murray June 27, 2019, 1:18 p.m. UTC | #2

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/[e-mail]/
> 
> 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

Vincenzo Frascino June 29, 2019, 7:17 a.m. UTC | #3

+ Dan and [e-mail]

Hi Andrew,

I am adding Dan to this thread since he is the smatch maintainer, and the
[e-mail] list.

@Dan and @[e-mail]: 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/[e-mail]/
>>
>> 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

Patch

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