[CVE-2017-12193,T,SRU,1/1] assoc_array: Fix a buggy node-splitting case

Message ID 20180606085239.22499-2-po-hsu.lin@canonical.com
State New
Headers show
Series
  • Fix for CVE-2017-12193
Related show

Commit Message

Po-Hsu Lin June 6, 2018, 8:52 a.m.
From: David Howells <dhowells@redhat.com>

CVE-2017-12193

BugLink: https://bugs.launchpad.net/bugs/1775316

This fixes CVE-2017-12193.

Fix a case in the assoc_array implementation in which a new leaf is
added that needs to go into a node that happens to be full, where the
existing leaves in that node cluster together at that level to the
exclusion of new leaf.

What needs to happen is that the existing leaves get moved out to a new
node, N1, at level + 1 and the existing node needs replacing with one,
N0, that has pointers to the new leaf and to N1.

The code that tries to do this gets this wrong in two ways:

 (1) The pointer that should've pointed from N0 to N1 is set to point
     recursively to N0 instead.

 (2) The backpointer from N0 needs to be set correctly in the case N0 is
     either the root node or reached through a shortcut.

Fix this by removing this path and using the split_node path instead,
which achieves the same end, but in a more general way (thanks to Eric
Biggers for spotting the redundancy).

The problem manifests itself as:

  BUG: unable to handle kernel NULL pointer dereference at 0000000000000010
  IP: assoc_array_apply_edit+0x59/0xe5

Fixes: 3cb989501c26 ("Add a generic associative array implementation.")
Reported-and-tested-by: WU Fan <u3536072@connect.hku.hk>
Signed-off-by: David Howells <dhowells@redhat.com>
Cc: stable@vger.kernel.org [v3.13-rc1+]
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
(cherry picked from commit ea6789980fdaa610d7eb63602c746bf6ec70cd2b)
Signed-off-by: Po-Hsu Lin <po-hsu.lin@canonical.com>
---
 lib/assoc_array.c | 51 +++++++++++++++++----------------------------------
 1 file changed, 17 insertions(+), 34 deletions(-)

Comments

Stefan Bader June 6, 2018, 7:35 p.m. | #1
On 06.06.2018 01:52, Po-Hsu Lin wrote:
> From: David Howells <dhowells@redhat.com>
> 
> CVE-2017-12193
> 
> BugLink: https://bugs.launchpad.net/bugs/1775316
> 
> This fixes CVE-2017-12193.
> 
> Fix a case in the assoc_array implementation in which a new leaf is
> added that needs to go into a node that happens to be full, where the
> existing leaves in that node cluster together at that level to the
> exclusion of new leaf.
> 
> What needs to happen is that the existing leaves get moved out to a new
> node, N1, at level + 1 and the existing node needs replacing with one,
> N0, that has pointers to the new leaf and to N1.
> 
> The code that tries to do this gets this wrong in two ways:
> 
>  (1) The pointer that should've pointed from N0 to N1 is set to point
>      recursively to N0 instead.
> 
>  (2) The backpointer from N0 needs to be set correctly in the case N0 is
>      either the root node or reached through a shortcut.
> 
> Fix this by removing this path and using the split_node path instead,
> which achieves the same end, but in a more general way (thanks to Eric
> Biggers for spotting the redundancy).
> 
> The problem manifests itself as:
> 
>   BUG: unable to handle kernel NULL pointer dereference at 0000000000000010
>   IP: assoc_array_apply_edit+0x59/0xe5
> 
> Fixes: 3cb989501c26 ("Add a generic associative array implementation.")
> Reported-and-tested-by: WU Fan <u3536072@connect.hku.hk>
> Signed-off-by: David Howells <dhowells@redhat.com>
> Cc: stable@vger.kernel.org [v3.13-rc1+]
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> (cherry picked from commit ea6789980fdaa610d7eb63602c746bf6ec70cd2b)
> Signed-off-by: Po-Hsu Lin <po-hsu.lin@canonical.com>
Acked-by: Stefan Bader <stefan.bader@canonical.com>
> ---
>  lib/assoc_array.c | 51 +++++++++++++++++----------------------------------
>  1 file changed, 17 insertions(+), 34 deletions(-)
> 
> diff --git a/lib/assoc_array.c b/lib/assoc_array.c
> index afef906..035c236 100644
> --- a/lib/assoc_array.c
> +++ b/lib/assoc_array.c
> @@ -597,21 +597,31 @@ static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit *edit,
>  		if ((edit->segment_cache[ASSOC_ARRAY_FAN_OUT] ^ base_seg) == 0)
>  			goto all_leaves_cluster_together;
>  
> -		/* Otherwise we can just insert a new node ahead of the old
> -		 * one.
> +		/* Otherwise all the old leaves cluster in the same slot, but
> +		 * the new leaf wants to go into a different slot - so we
> +		 * create a new node (n0) to hold the new leaf and a pointer to
> +		 * a new node (n1) holding all the old leaves.
> +		 *
> +		 * This can be done by falling through to the node splitting
> +		 * path.
>  		 */
> -		goto present_leaves_cluster_but_not_new_leaf;
> +		pr_devel("present leaves cluster but not new leaf\n");
>  	}
>  
>  split_node:
>  	pr_devel("split node\n");
>  
> -	/* We need to split the current node; we know that the node doesn't
> -	 * simply contain a full set of leaves that cluster together (it
> -	 * contains meta pointers and/or non-clustering leaves).
> +	/* We need to split the current node.  The node must contain anything
> +	 * from a single leaf (in the one leaf case, this leaf will cluster
> +	 * with the new leaf) and the rest meta-pointers, to all leaves, some
> +	 * of which may cluster.
> +	 *
> +	 * It won't contain the case in which all the current leaves plus the
> +	 * new leaves want to cluster in the same slot.
>  	 *
>  	 * We need to expel at least two leaves out of a set consisting of the
> -	 * leaves in the node and the new leaf.
> +	 * leaves in the node and the new leaf.  The current meta pointers can
> +	 * just be copied as they shouldn't cluster with any of the leaves.
>  	 *
>  	 * We need a new node (n0) to replace the current one and a new node to
>  	 * take the expelled nodes (n1).
> @@ -716,33 +726,6 @@ found_slot_for_multiple_occupancy:
>  	pr_devel("<--%s() = ok [split node]\n", __func__);
>  	return true;
>  
> -present_leaves_cluster_but_not_new_leaf:
> -	/* All the old leaves cluster in the same slot, but the new leaf wants
> -	 * to go into a different slot, so we create a new node to hold the new
> -	 * leaf and a pointer to a new node holding all the old leaves.
> -	 */
> -	pr_devel("present leaves cluster but not new leaf\n");
> -
> -	new_n0->back_pointer = node->back_pointer;
> -	new_n0->parent_slot = node->parent_slot;
> -	new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
> -	new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);
> -	new_n1->parent_slot = edit->segment_cache[0];
> -	new_n1->nr_leaves_on_branch = node->nr_leaves_on_branch;
> -	edit->adjust_count_on = new_n0;
> -
> -	for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++)
> -		new_n1->slots[i] = node->slots[i];
> -
> -	new_n0->slots[edit->segment_cache[0]] = assoc_array_node_to_ptr(new_n0);
> -	edit->leaf_p = &new_n0->slots[edit->segment_cache[ASSOC_ARRAY_FAN_OUT]];
> -
> -	edit->set[0].ptr = &assoc_array_ptr_to_node(node->back_pointer)->slots[node->parent_slot];
> -	edit->set[0].to = assoc_array_node_to_ptr(new_n0);
> -	edit->excised_meta[0] = assoc_array_node_to_ptr(node);
> -	pr_devel("<--%s() = ok [insert node before]\n", __func__);
> -	return true;
> -
>  all_leaves_cluster_together:
>  	/* All the leaves, new and old, want to cluster together in this node
>  	 * in the same slot, so we have to replace this node with a shortcut to
>
Kleber Souza June 6, 2018, 10:57 p.m. | #2
On 06/06/18 01:52, Po-Hsu Lin wrote:
> From: David Howells <dhowells@redhat.com>
> 
> CVE-2017-12193
> 
> BugLink: https://bugs.launchpad.net/bugs/1775316
> 
> This fixes CVE-2017-12193.
> 
> Fix a case in the assoc_array implementation in which a new leaf is
> added that needs to go into a node that happens to be full, where the
> existing leaves in that node cluster together at that level to the
> exclusion of new leaf.
> 
> What needs to happen is that the existing leaves get moved out to a new
> node, N1, at level + 1 and the existing node needs replacing with one,
> N0, that has pointers to the new leaf and to N1.
> 
> The code that tries to do this gets this wrong in two ways:
> 
>  (1) The pointer that should've pointed from N0 to N1 is set to point
>      recursively to N0 instead.
> 
>  (2) The backpointer from N0 needs to be set correctly in the case N0 is
>      either the root node or reached through a shortcut.
> 
> Fix this by removing this path and using the split_node path instead,
> which achieves the same end, but in a more general way (thanks to Eric
> Biggers for spotting the redundancy).
> 
> The problem manifests itself as:
> 
>   BUG: unable to handle kernel NULL pointer dereference at 0000000000000010
>   IP: assoc_array_apply_edit+0x59/0xe5
> 
> Fixes: 3cb989501c26 ("Add a generic associative array implementation.")
> Reported-and-tested-by: WU Fan <u3536072@connect.hku.hk>
> Signed-off-by: David Howells <dhowells@redhat.com>
> Cc: stable@vger.kernel.org [v3.13-rc1+]
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> (cherry picked from commit ea6789980fdaa610d7eb63602c746bf6ec70cd2b)
> Signed-off-by: Po-Hsu Lin <po-hsu.lin@canonical.com>

Acked-by: Kleber Sacilotto de Souza <kleber.souza@canonical.com>

> ---
>  lib/assoc_array.c | 51 +++++++++++++++++----------------------------------
>  1 file changed, 17 insertions(+), 34 deletions(-)
> 
> diff --git a/lib/assoc_array.c b/lib/assoc_array.c
> index afef906..035c236 100644
> --- a/lib/assoc_array.c
> +++ b/lib/assoc_array.c
> @@ -597,21 +597,31 @@ static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit *edit,
>  		if ((edit->segment_cache[ASSOC_ARRAY_FAN_OUT] ^ base_seg) == 0)
>  			goto all_leaves_cluster_together;
>  
> -		/* Otherwise we can just insert a new node ahead of the old
> -		 * one.
> +		/* Otherwise all the old leaves cluster in the same slot, but
> +		 * the new leaf wants to go into a different slot - so we
> +		 * create a new node (n0) to hold the new leaf and a pointer to
> +		 * a new node (n1) holding all the old leaves.
> +		 *
> +		 * This can be done by falling through to the node splitting
> +		 * path.
>  		 */
> -		goto present_leaves_cluster_but_not_new_leaf;
> +		pr_devel("present leaves cluster but not new leaf\n");
>  	}
>  
>  split_node:
>  	pr_devel("split node\n");
>  
> -	/* We need to split the current node; we know that the node doesn't
> -	 * simply contain a full set of leaves that cluster together (it
> -	 * contains meta pointers and/or non-clustering leaves).
> +	/* We need to split the current node.  The node must contain anything
> +	 * from a single leaf (in the one leaf case, this leaf will cluster
> +	 * with the new leaf) and the rest meta-pointers, to all leaves, some
> +	 * of which may cluster.
> +	 *
> +	 * It won't contain the case in which all the current leaves plus the
> +	 * new leaves want to cluster in the same slot.
>  	 *
>  	 * We need to expel at least two leaves out of a set consisting of the
> -	 * leaves in the node and the new leaf.
> +	 * leaves in the node and the new leaf.  The current meta pointers can
> +	 * just be copied as they shouldn't cluster with any of the leaves.
>  	 *
>  	 * We need a new node (n0) to replace the current one and a new node to
>  	 * take the expelled nodes (n1).
> @@ -716,33 +726,6 @@ found_slot_for_multiple_occupancy:
>  	pr_devel("<--%s() = ok [split node]\n", __func__);
>  	return true;
>  
> -present_leaves_cluster_but_not_new_leaf:
> -	/* All the old leaves cluster in the same slot, but the new leaf wants
> -	 * to go into a different slot, so we create a new node to hold the new
> -	 * leaf and a pointer to a new node holding all the old leaves.
> -	 */
> -	pr_devel("present leaves cluster but not new leaf\n");
> -
> -	new_n0->back_pointer = node->back_pointer;
> -	new_n0->parent_slot = node->parent_slot;
> -	new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
> -	new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);
> -	new_n1->parent_slot = edit->segment_cache[0];
> -	new_n1->nr_leaves_on_branch = node->nr_leaves_on_branch;
> -	edit->adjust_count_on = new_n0;
> -
> -	for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++)
> -		new_n1->slots[i] = node->slots[i];
> -
> -	new_n0->slots[edit->segment_cache[0]] = assoc_array_node_to_ptr(new_n0);
> -	edit->leaf_p = &new_n0->slots[edit->segment_cache[ASSOC_ARRAY_FAN_OUT]];
> -
> -	edit->set[0].ptr = &assoc_array_ptr_to_node(node->back_pointer)->slots[node->parent_slot];
> -	edit->set[0].to = assoc_array_node_to_ptr(new_n0);
> -	edit->excised_meta[0] = assoc_array_node_to_ptr(node);
> -	pr_devel("<--%s() = ok [insert node before]\n", __func__);
> -	return true;
> -
>  all_leaves_cluster_together:
>  	/* All the leaves, new and old, want to cluster together in this node
>  	 * in the same slot, so we have to replace this node with a shortcut to
>

Patch

diff --git a/lib/assoc_array.c b/lib/assoc_array.c
index afef906..035c236 100644
--- a/lib/assoc_array.c
+++ b/lib/assoc_array.c
@@ -597,21 +597,31 @@  static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit *edit,
 		if ((edit->segment_cache[ASSOC_ARRAY_FAN_OUT] ^ base_seg) == 0)
 			goto all_leaves_cluster_together;
 
-		/* Otherwise we can just insert a new node ahead of the old
-		 * one.
+		/* Otherwise all the old leaves cluster in the same slot, but
+		 * the new leaf wants to go into a different slot - so we
+		 * create a new node (n0) to hold the new leaf and a pointer to
+		 * a new node (n1) holding all the old leaves.
+		 *
+		 * This can be done by falling through to the node splitting
+		 * path.
 		 */
-		goto present_leaves_cluster_but_not_new_leaf;
+		pr_devel("present leaves cluster but not new leaf\n");
 	}
 
 split_node:
 	pr_devel("split node\n");
 
-	/* We need to split the current node; we know that the node doesn't
-	 * simply contain a full set of leaves that cluster together (it
-	 * contains meta pointers and/or non-clustering leaves).
+	/* We need to split the current node.  The node must contain anything
+	 * from a single leaf (in the one leaf case, this leaf will cluster
+	 * with the new leaf) and the rest meta-pointers, to all leaves, some
+	 * of which may cluster.
+	 *
+	 * It won't contain the case in which all the current leaves plus the
+	 * new leaves want to cluster in the same slot.
 	 *
 	 * We need to expel at least two leaves out of a set consisting of the
-	 * leaves in the node and the new leaf.
+	 * leaves in the node and the new leaf.  The current meta pointers can
+	 * just be copied as they shouldn't cluster with any of the leaves.
 	 *
 	 * We need a new node (n0) to replace the current one and a new node to
 	 * take the expelled nodes (n1).
@@ -716,33 +726,6 @@  found_slot_for_multiple_occupancy:
 	pr_devel("<--%s() = ok [split node]\n", __func__);
 	return true;
 
-present_leaves_cluster_but_not_new_leaf:
-	/* All the old leaves cluster in the same slot, but the new leaf wants
-	 * to go into a different slot, so we create a new node to hold the new
-	 * leaf and a pointer to a new node holding all the old leaves.
-	 */
-	pr_devel("present leaves cluster but not new leaf\n");
-
-	new_n0->back_pointer = node->back_pointer;
-	new_n0->parent_slot = node->parent_slot;
-	new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
-	new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);
-	new_n1->parent_slot = edit->segment_cache[0];
-	new_n1->nr_leaves_on_branch = node->nr_leaves_on_branch;
-	edit->adjust_count_on = new_n0;
-
-	for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++)
-		new_n1->slots[i] = node->slots[i];
-
-	new_n0->slots[edit->segment_cache[0]] = assoc_array_node_to_ptr(new_n0);
-	edit->leaf_p = &new_n0->slots[edit->segment_cache[ASSOC_ARRAY_FAN_OUT]];
-
-	edit->set[0].ptr = &assoc_array_ptr_to_node(node->back_pointer)->slots[node->parent_slot];
-	edit->set[0].to = assoc_array_node_to_ptr(new_n0);
-	edit->excised_meta[0] = assoc_array_node_to_ptr(node);
-	pr_devel("<--%s() = ok [insert node before]\n", __func__);
-	return true;
-
 all_leaves_cluster_together:
 	/* All the leaves, new and old, want to cluster together in this node
 	 * in the same slot, so we have to replace this node with a shortcut to