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

Wed Jun 6 19:35:55 UTC 2018

On 06.06.2018 01:52, Po-Hsu Lin wrote:
> From: David Howells <dhowells at 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 at connect.hku.hk>
> Signed-off-by: David Howells <dhowells at redhat.com>
> Cc: stable at vger.kernel.org [v3.13-rc1+]
> Signed-off-by: Linus Torvalds <torvalds at linux-foundation.org>
> (cherry picked from commit ea6789980fdaa610d7eb63602c746bf6ec70cd2b)
> Signed-off-by: Po-Hsu Lin <po-hsu.lin at canonical.com>
Acked-by: Stefan Bader <stefan.bader at 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
> 


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <https://lists.ubuntu.com/archives/kernel-team/attachments/20180606/b96bf181/attachment.sig>