[PATCH 0/2] KVM: Fix out-of-bounds memslot access

[PATCH 0/2] KVM: Fix out-of-bounds memslot access

[Sean Christopherson]

Two fixes for what are effectively the same bug.  The binary search used
for memslot lookup doesn't check the resolved index and can access memory
beyond the end of the memslot array.

I split the s390 specific change to a separate patch because it's subtly
different, and to simplify backporting.  The KVM wide fix can be applied
to stable trees as is, but AFAICT the s390 change would need to be paired
with the !used_slots check from commit 774a964ef56 ("KVM: Fix out of range
accesses to memslots").  This is why I tagged only the KVM wide patch for
stable.

Sean Christopherson (2):
  KVM: Check validity of resolved slot when searching memslots
  KVM: s390: Return last valid slot if approx index is out-of-bounds

 arch/s390/kvm/kvm-s390.c | 3 +++
 include/linux/kvm_host.h | 2 +-
 2 files changed, 4 insertions(+), 1 deletion(-)

-- 
2.24.1

[PATCH 1/2] KVM: Check validity of resolved slot when searching memslots

[Sean Christopherson]

Check that the resolved slot (somewhat confusingly named 'start') is a
valid/allocated slot before doing the final comparison to see if the
specified gfn resides in the associated slot.  The resolved slot can be
invalid if the binary search loop terminated because the search index
was incremented beyond the number of used slots.

This bug has existed since the binary search algorithm was introduced,
but went unnoticed because KVM statically allocated memory for the max
number of slots, i.e. the access would only be truly out-of-bounds if
all possible slots were allocated and the specified gfn was less than
the base of the lowest memslot.  Commit 36947254e5f98 ("KVM: Dynamically
size memslot array based on number of used slots") eliminated the "all
possible slots allocated" condition and made the bug embarrasingly easy
to hit.

Fixes: 9c1a5d38780e6 ("kvm: optimize GFN to memslot lookup with large slots amount")
Reported-by: syzbot+d889b59b2bb87d4047a2@syzkaller.appspotmail.com
Cc: stable@vger.kernel.org
Signed-off-by: Sean Christopherson <sean.j.christopherson@intel.com>
---
 include/linux/kvm_host.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
index 6d58beb65454..01276e3d01b9 100644
--- a/include/linux/kvm_host.h
+++ b/include/linux/kvm_host.h
@@ -1048,7 +1048,7 @@ search_memslots(struct kvm_memslots *slots, gfn_t gfn)
 			start = slot + 1;
 	}
 
-	if (gfn >= memslots[start].base_gfn &&
+	if (start < slots->used_slots && gfn >= memslots[start].base_gfn &&
 	    gfn < memslots[start].base_gfn + memslots[start].npages) {
 		atomic_set(&slots->lru_slot, start);
 		return &memslots[start];
-- 
2.24.1

[PATCH 2/2] KVM: s390: Return last valid slot if approx index is out-of-bounds

[Sean Christopherson]

Return the index of the last valid slot from gfn_to_memslot_approx() if
its binary search loop yielded an out-of-bounds index.  The index can
be out-of-bounds if the specified gfn is less than the base of the
lowest memslot (which is also the last valid memslot).

Note, the sole caller, kvm_s390_get_cmma(), ensures used_slots is
non-zero.

Fixes: afdad61615cc3 ("KVM: s390: Fix storage attributes migration with memory slots")
Signed-off-by: Sean Christopherson <sean.j.christopherson@intel.com>
---
 arch/s390/kvm/kvm-s390.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/arch/s390/kvm/kvm-s390.c b/arch/s390/kvm/kvm-s390.c
index 19a81024fe16..5dcf9ff12828 100644
--- a/arch/s390/kvm/kvm-s390.c
+++ b/arch/s390/kvm/kvm-s390.c
@@ -1939,6 +1939,9 @@ static int gfn_to_memslot_approx(struct kvm_memslots *slots, gfn_t gfn)
 			start = slot + 1;
 	}
 
+	if (start >= slots->used_slots)
+		return slots->used_slots - 1;
+
 	if (gfn >= memslots[start].base_gfn &&
 	    gfn < memslots[start].base_gfn + memslots[start].npages) {
 		atomic_set(&slots->lru_slot, start);
-- 
2.24.1

Re: [PATCH 0/2] KVM: Fix out-of-bounds memslot access

[Christian Borntraeger]

On 08.04.20 08:40, Sean Christopherson wrote:
> Two fixes for what are effectively the same bug.  The binary search used
> for memslot lookup doesn't check the resolved index and can access memory
> beyond the end of the memslot array.
> 
> I split the s390 specific change to a separate patch because it's subtly
> different, and to simplify backporting.  The KVM wide fix can be applied
> to stable trees as is, but AFAICT the s390 change would need to be paired
> with the !used_slots check from commit 774a964ef56 ("KVM: Fix out of range
> accesses to memslots").  This is why I tagged only the KVM wide patch for
> stable.

You can specify dependencies like

see

Documentation/process/stable-kernel-rules.rst

-----------snip---------------
Additionally, some patches submitted via :ref:`option_1` may have additional
patch prerequisites which can be cherry-picked. This can be specified in the
following format in the sign-off area:

.. code-block:: none

     Cc: <stable@vger.kernel.org> # 3.3.x: a1f84a3: sched: Check for idle
     Cc: <stable@vger.kernel.org> # 3.3.x: 1b9508f: sched: Rate-limit newidle
     Cc: <stable@vger.kernel.org> # 3.3.x: fd21073: sched: Fix affinity logic
     Cc: <stable@vger.kernel.org> # 3.3.x
     Signed-off-by: Ingo Molnar <mingo@elte.hu>

The tag sequence has the meaning of:

.. code-block:: none

     git cherry-pick a1f84a3
     git cherry-pick 1b9508f
     git cherry-pick fd21073
     git cherry-pick <this commit>

-----------snip---------------

Re: [PATCH 1/2] KVM: Check validity of resolved slot when searching memslots

[Cornelia Huck]

On Tue,  7 Apr 2020 23:40:58 -0700
Sean Christopherson <sean.j.christopherson@intel.com> wrote:

> Check that the resolved slot (somewhat confusingly named 'start') is a
> valid/allocated slot before doing the final comparison to see if the
> specified gfn resides in the associated slot.  The resolved slot can be
> invalid if the binary search loop terminated because the search index
> was incremented beyond the number of used slots.
> 
> This bug has existed since the binary search algorithm was introduced,
> but went unnoticed because KVM statically allocated memory for the max
> number of slots, i.e. the access would only be truly out-of-bounds if
> all possible slots were allocated and the specified gfn was less than
> the base of the lowest memslot.  Commit 36947254e5f98 ("KVM: Dynamically
> size memslot array based on number of used slots") eliminated the "all
> possible slots allocated" condition and made the bug embarrasingly easy
> to hit.
> 
> Fixes: 9c1a5d38780e6 ("kvm: optimize GFN to memslot lookup with large slots amount")
> Reported-by: syzbot+d889b59b2bb87d4047a2@syzkaller.appspotmail.com
> Cc: stable@vger.kernel.org
> Signed-off-by: Sean Christopherson <sean.j.christopherson@intel.com>
> ---
>  include/linux/kvm_host.h | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
> index 6d58beb65454..01276e3d01b9 100644
> --- a/include/linux/kvm_host.h
> +++ b/include/linux/kvm_host.h
> @@ -1048,7 +1048,7 @@ search_memslots(struct kvm_memslots *slots, gfn_t gfn)
>  			start = slot + 1;
>  	}
>  
> -	if (gfn >= memslots[start].base_gfn &&
> +	if (start < slots->used_slots && gfn >= memslots[start].base_gfn &&
>  	    gfn < memslots[start].base_gfn + memslots[start].npages) {
>  		atomic_set(&slots->lru_slot, start);
>  		return &memslots[start];

Reviewed-by: Cornelia Huck <cohuck@redhat.com>

Re: [PATCH 2/2] KVM: s390: Return last valid slot if approx index is out-of-bounds

[Cornelia Huck]

On Tue,  7 Apr 2020 23:40:59 -0700
Sean Christopherson <sean.j.christopherson@intel.com> wrote:

> Return the index of the last valid slot from gfn_to_memslot_approx() if
> its binary search loop yielded an out-of-bounds index.  The index can
> be out-of-bounds if the specified gfn is less than the base of the
> lowest memslot (which is also the last valid memslot).
> 
> Note, the sole caller, kvm_s390_get_cmma(), ensures used_slots is
> non-zero.
> 

This also should be cc:stable, with the dependency expressed as
mentioned by Christian.

> Fixes: afdad61615cc3 ("KVM: s390: Fix storage attributes migration with memory slots")
> Signed-off-by: Sean Christopherson <sean.j.christopherson@intel.com>
> ---
>  arch/s390/kvm/kvm-s390.c | 3 +++
>  1 file changed, 3 insertions(+)
> 
> diff --git a/arch/s390/kvm/kvm-s390.c b/arch/s390/kvm/kvm-s390.c
> index 19a81024fe16..5dcf9ff12828 100644
> --- a/arch/s390/kvm/kvm-s390.c
> +++ b/arch/s390/kvm/kvm-s390.c
> @@ -1939,6 +1939,9 @@ static int gfn_to_memslot_approx(struct kvm_memslots *slots, gfn_t gfn)
>  			start = slot + 1;
>  	}
>  
> +	if (start >= slots->used_slots)
> +		return slots->used_slots - 1;
> +
>  	if (gfn >= memslots[start].base_gfn &&
>  	    gfn < memslots[start].base_gfn + memslots[start].npages) {
>  		atomic_set(&slots->lru_slot, start);

Reviewed-by: Cornelia Huck <cohuck@redhat.com>

Re: [PATCH 0/2] KVM: Fix out-of-bounds memslot access

[Christian Borntraeger]

On 08.04.20 08:40, Sean Christopherson wrote:
> Two fixes for what are effectively the same bug.  The binary search used
> for memslot lookup doesn't check the resolved index and can access memory
> beyond the end of the memslot array.
> 
> I split the s390 specific change to a separate patch because it's subtly
> different, and to simplify backporting.  The KVM wide fix can be applied
> to stable trees as is, but AFAICT the s390 change would need to be paired
> with the !used_slots check from commit 774a964ef56 ("KVM: Fix out of range

I cannot find the commit id 774a964ef56

Re: [PATCH 2/2] KVM: s390: Return last valid slot if approx index is out-of-bounds

[Christian Borntraeger]

On 08.04.20 08:40, Sean Christopherson wrote:
> Return the index of the last valid slot from gfn_to_memslot_approx() if
> its binary search loop yielded an out-of-bounds index.  The index can
> be out-of-bounds if the specified gfn is less than the base of the
> lowest memslot (which is also the last valid memslot).
> 
> Note, the sole caller, kvm_s390_get_cmma(), ensures used_slots is
> non-zero.
> 
> Fixes: afdad61615cc3 ("KVM: s390: Fix storage attributes migration with memory slots")
> Signed-off-by: Sean Christopherson <sean.j.christopherson@intel.com>
> ---
>  arch/s390/kvm/kvm-s390.c | 3 +++
>  1 file changed, 3 insertions(+)
> 
> diff --git a/arch/s390/kvm/kvm-s390.c b/arch/s390/kvm/kvm-s390.c
> index 19a81024fe16..5dcf9ff12828 100644
> --- a/arch/s390/kvm/kvm-s390.c
> +++ b/arch/s390/kvm/kvm-s390.c
> @@ -1939,6 +1939,9 @@ static int gfn_to_memslot_approx(struct kvm_memslots *slots, gfn_t gfn)
>  			start = slot + 1;
>  	}
>  
> +	if (start >= slots->used_slots)
> +		return slots->used_slots - 1;
> +
>  	if (gfn >= memslots[start].base_gfn &&
>  	    gfn < memslots[start].base_gfn + memslots[start].npages) {
>  		atomic_set(&slots->lru_slot, start);
> 

Claudio, can you have a look?

Re: [PATCH 0/2] KVM: Fix out-of-bounds memslot access

[Cornelia Huck]

On Wed, 8 Apr 2020 09:24:27 +0200
Christian Borntraeger <borntraeger@de.ibm.com> wrote:

> On 08.04.20 08:40, Sean Christopherson wrote:
> > Two fixes for what are effectively the same bug.  The binary search used
> > for memslot lookup doesn't check the resolved index and can access memory
> > beyond the end of the memslot array.
> > 
> > I split the s390 specific change to a separate patch because it's subtly
> > different, and to simplify backporting.  The KVM wide fix can be applied
> > to stable trees as is, but AFAICT the s390 change would need to be paired
> > with the !used_slots check from commit 774a964ef56 ("KVM: Fix out of range  
> 
> I cannot find the commit id 774a964ef56
> 

It's 0774a964ef561b7170d8d1b1bfe6f88002b6d219 in my tree.

Re: [PATCH 2/2] KVM: s390: Return last valid slot if approx index is out-of-bounds

[Paolo Bonzini]

On 08/04/20 09:10, Cornelia Huck wrote:
> On Tue,  7 Apr 2020 23:40:59 -0700
> Sean Christopherson <sean.j.christopherson@intel.com> wrote:
> 
>> Return the index of the last valid slot from gfn_to_memslot_approx() if
>> its binary search loop yielded an out-of-bounds index.  The index can
>> be out-of-bounds if the specified gfn is less than the base of the
>> lowest memslot (which is also the last valid memslot).
>>
>> Note, the sole caller, kvm_s390_get_cmma(), ensures used_slots is
>> non-zero.
>>
> This also should be cc:stable, with the dependency expressed as
> mentioned by Christian.
> 

So,

Cc: stable@vger.kernel.org # 4.19.x: 0774a964ef56: KVM: Fix out of range accesses to memslots
Cc: stable@vger.kernel.org # 4.19.x

Paolo

Re: [PATCH 2/2] KVM: s390: Return last valid slot if approx index is out-of-bounds

[Claudio Imbrenda]

On Tue,  7 Apr 2020 23:40:59 -0700
Sean Christopherson <sean.j.christopherson@intel.com> wrote:

> Return the index of the last valid slot from gfn_to_memslot_approx()
> if its binary search loop yielded an out-of-bounds index.  The index
> can be out-of-bounds if the specified gfn is less than the base of the
> lowest memslot (which is also the last valid memslot).
> 
> Note, the sole caller, kvm_s390_get_cmma(), ensures used_slots is
> non-zero.
> 
> Fixes: afdad61615cc3 ("KVM: s390: Fix storage attributes migration
> with memory slots") Signed-off-by: Sean Christopherson
> <sean.j.christopherson@intel.com> ---
>  arch/s390/kvm/kvm-s390.c | 3 +++
>  1 file changed, 3 insertions(+)
> 
> diff --git a/arch/s390/kvm/kvm-s390.c b/arch/s390/kvm/kvm-s390.c
> index 19a81024fe16..5dcf9ff12828 100644
> --- a/arch/s390/kvm/kvm-s390.c
> +++ b/arch/s390/kvm/kvm-s390.c
> @@ -1939,6 +1939,9 @@ static int gfn_to_memslot_approx(struct
> kvm_memslots *slots, gfn_t gfn) start = slot + 1;
>  	}
>  
> +	if (start >= slots->used_slots)
> +		return slots->used_slots - 1;
> +
>  	if (gfn >= memslots[start].base_gfn &&
>  	    gfn < memslots[start].base_gfn + memslots[start].npages)
> { atomic_set(&slots->lru_slot, start);

on s390 memory always starts at 0; you can't even boot a system missing
the first pages of physical memory, so this means this situation would
never happen in practice. 

of course, a malicious userspace program could create an (unbootable) VM
and trigger this bug, so the patch itself makes sense.

Reviewed-by: Claudio Imbrenda <imbrenda@linux.ibm.com>

Re: [PATCH 2/2] KVM: s390: Return last valid slot if approx index is out-of-bounds

[Paolo Bonzini]

On 08/04/20 12:21, Claudio Imbrenda wrote:
> on s390 memory always starts at 0; you can't even boot a system missing
> the first pages of physical memory, so this means this situation would
> never happen in practice. 
> 
> of course, a malicious userspace program could create an (unbootable) VM
> and trigger this bug, so the patch itself makes sense.
> 
> Reviewed-by: Claudio Imbrenda <imbrenda@linux.ibm.com>

What about using KVM just for isolation and not just to run a full-blown
OS (that is, you might even only have the guest run in problem state)?
Would that be feasible on s390?

Thanks,

Paolo

Re: [PATCH 2/2] KVM: s390: Return last valid slot if approx index is out-of-bounds

[Christian Borntraeger]

On 08.04.20 13:33, Paolo Bonzini wrote:
> On 08/04/20 12:21, Claudio Imbrenda wrote:
>> on s390 memory always starts at 0; you can't even boot a system missing
>> the first pages of physical memory, so this means this situation would
>> never happen in practice. 
>>
>> of course, a malicious userspace program could create an (unbootable) VM
>> and trigger this bug, so the patch itself makes sense.
>>
>> Reviewed-by: Claudio Imbrenda <imbrenda@linux.ibm.com>
> 
> What about using KVM just for isolation and not just to run a full-blown
> OS (that is, you might even only have the guest run in problem state)?
> Would that be feasible on s390?

You always need 2 prefix pages. Otherwise the SIE instruction refuses to start.
By default this starts as address 0. You might be also to set the prefix register
to something else adn then this could maybe work. 

Re: [PATCH 0/2] KVM: Fix out-of-bounds memslot access

[Sean Christopherson]

On Wed, Apr 08, 2020 at 10:10:04AM +0200, Cornelia Huck wrote:
> On Wed, 8 Apr 2020 09:24:27 +0200
> Christian Borntraeger <borntraeger@de.ibm.com> wrote:
> 
> > On 08.04.20 08:40, Sean Christopherson wrote:
> > > Two fixes for what are effectively the same bug.  The binary search used
> > > for memslot lookup doesn't check the resolved index and can access memory
> > > beyond the end of the memslot array.
> > > 
> > > I split the s390 specific change to a separate patch because it's subtly
> > > different, and to simplify backporting.  The KVM wide fix can be applied
> > > to stable trees as is, but AFAICT the s390 change would need to be paired
> > > with the !used_slots check from commit 774a964ef56 ("KVM: Fix out of range  
> > 
> > I cannot find the commit id 774a964ef56
> > 
> 
> It's 0774a964ef561b7170d8d1b1bfe6f88002b6d219 in my tree.

Argh, I botched the copy.  Thanks for hunting it down!