Skip to contentSkip to conversation

KVM: Fix out-of-bounds memslot access

PATCH In review Sean Christopherson 5 participants 14 messages Apr 8, 2020

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

cover KVM: Fix out-of-bounds memslot access

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(-)
Signature · 1 line
2.24.1
#1 lore raw

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

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 [email protected]
---
 include/linux/kvm_host.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
include/linux/kvm_host.h +1 -1
index 6d58beb65454..01276e3d01b9 100644
@@ -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];
Signature · 1 line
2.24.1
Reviewed-by on v1 1/2
#2 lore raw

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

Quoted 28 lines · On Tue, 7 Apr 2020 23:40:58 -0700 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 [email protected]
---
 include/linux/kvm_host.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
include/linux/kvm_host.h +0 -0
index 6d58beb65454..01276e3d01b9 100644

include/linux/kvm_host.h search_memslots(struct kvm_memslots *slots, gfn_t gfn) · line 1054

Quoted 8 lines
include/linux/kvm_host.h +1 -1
@@ -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];
#3 lore raw

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

In reply to 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")
---
 arch/s390/kvm/kvm-s390.c | 3 +++
 1 file changed, 3 insertions(+)
arch/s390/kvm/kvm-s390.c +3 -0
index 19a81024fe16..5dcf9ff12828 100644
@@ -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);
Signature · 1 line
2.24.1
Reviewed-by on v1 2/2
#4 lore raw

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

Quoted 8 lines · On Tue, 7 Apr 2020 23:40:59 -0700 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.

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

Quoted 11 lines
Fixes afdad61615cc3 ("KVM: s390: Fix storage attributes migration with memory slots")
---
 arch/s390/kvm/kvm-s390.c | 3 +++
 1 file changed, 3 insertions(+)
arch/s390/kvm/kvm-s390.c +0 -0
index 19a81024fe16..5dcf9ff12828 100644

arch/s390/kvm/kvm-s390.c static int gfn_to_memslot_approx(struct kvm_memslots *slots, gfn_t gfn) · line 1947

Quoted 9 lines
arch/s390/kvm/kvm-s390.c +3 -0
@@ -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);
maintainer
#5 lore raw

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

Quoted 8 lines · Cornelia Huck
Quoted 5 lines · On Tue, 7 Apr 2020 23:40:59 -0700 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).

Quoted 6 lines
Quoted 3 lines

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 [email protected] # 4.19.x: 0774a964ef56: KVM: Fix out of range accesses to memslots
Cc [email protected] # 4.19.x

Paolo

#6 lore raw

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

In reply to Sean Christopherson
Quoted 20 lines · 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")
---
 arch/s390/kvm/kvm-s390.c | 3 +++
 1 file changed, 3 insertions(+)
arch/s390/kvm/kvm-s390.c +0 -0
index 19a81024fe16..5dcf9ff12828 100644

arch/s390/kvm/kvm-s390.c static int gfn_to_memslot_approx(struct kvm_memslots *slots, gfn_t gfn) · line 1947

Quoted 9 lines
arch/s390/kvm/kvm-s390.c +3 -0
@@ -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?

maintainer Reviewed-by on v1 2/2
#7 lore raw

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

In reply to Sean Christopherson
Quoted 19 lines · On Tue, 7 Apr 2020 23:40:59 -0700 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 <[email protected]> ---

 arch/s390/kvm/kvm-s390.c | 3 +++
 1 file changed, 3 insertions(+)
arch/s390/kvm/kvm-s390.c +0 -0
index 19a81024fe16..5dcf9ff12828 100644

arch/s390/kvm/kvm-s390.c static int gfn_to_memslot_approx(struct · line 1947

Quoted 9 lines
arch/s390/kvm/kvm-s390.c +3 -0
@@ -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.

maintainer
#8 lore raw

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

Quoted 8 lines · Claudio Imbrenda

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.

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

#9 lore raw

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

Quoted 5 lines · Paolo Bonzini
Quoted 4 lines · Claudio Imbrenda

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.

Quoted 8 lines
Quoted 4 lines

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

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.

#10 lore raw
In reply to Sean Christopherson
Quoted 10 lines · 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.

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: <[email protected]> # 3.3.x: a1f84a3: sched: Check for idle
     Cc: <[email protected]> # 3.3.x: 1b9508f: sched: Rate-limit newidle
     Cc: <[email protected]> # 3.3.x: fd21073: sched: Fix affinity logic
     Cc: <[email protected]> # 3.3.x
     Signed-off-by: Ingo Molnar <[email protected]>

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

#11 lore raw
In reply to Sean Christopherson
Quoted 8 lines · 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

I cannot find the commit id 774a964ef56

#12 lore raw
Quoted 5 lines · On Wed, 8 Apr 2020 09:24:27 +0200 Christian Borntraeger…
Quoted 4 lines · 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.

Quoted 7 lines
Quoted 4 lines

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.

#13 lore raw
Quoted 13 lines · Cornelia Huck
Quoted 10 lines · On Wed, 8 Apr 2020 09:24:27 +0200 Christian Borntraeger…
Quoted 8 lines · 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

Quoted 4 lines
Quoted 2 lines

I cannot find the commit id 774a964ef56

It's 0774a964ef561b7170d8d1b1bfe6f88002b6d219 in my tree.

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