Re: [RFC PATCH] libselinux: restore previous regex spec ordering

[Petr Lautrbach <lautrbach@redhat.com>]

Christian Göttsche <cgoettsche@seltendoof.de> writes:

> From: Christian Göttsche <cgzones@googlemail.com>
>
> Prior the recent selabel_file(5) rework regular expressions for a
> certain stem where matched in the order given by the input.
> The Reference and Fedora Policy as well as CIL and libsemanage pre-sort
> the file context definitions based on the prefix stem length, so this
> ordering was adopted.
> Do not alter the order by the input of regex specifications to retain
> backward compatibility, e.g. for Android.
>
> Reported-by: Takaya Saeki <takayas@chromium.org>
> Closes: https://lore.kernel.org/selinux/CAH9xa6eFO6BNeGko90bsq8CuDba9eO+qdDoF+7zfyAUHEDpH9g@mail.gmail.com/
> Fixes: 92306da ("libselinux: rework selabel_file(5) database")
> Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
> ---
> **NOTE**:
> Using a pre-compiled fcontext file generated with 3.8-rc1 (3.7 and prior
> is fine) will result in vastly wrong lookup results.
> Thus all users upgrading from 3.8-rc1 **should** remove their
> pre-compiled fcontext definitions, e.g. via
>
>   rm /etc/selinux/*/contexts/files/*.bin
>
> In case this commits get applied this should be mentioned in the release
> notes for 3.8-rc2.
>

Thanks!

I've  missed this set of emails and I've already pushed 3.8-rc2 but I
will not announce it and wait for this and then release rc3.




> ---
>  libselinux/src/label_file.c | 163 +++++++++++++++++-------------------
>  libselinux/src/label_file.h |  34 +-------
>  2 files changed, 80 insertions(+), 117 deletions(-)
>
> diff --git a/libselinux/src/label_file.c b/libselinux/src/label_file.c
> index 80a7c5ab..3e35381d 100644
> --- a/libselinux/src/label_file.c
> +++ b/libselinux/src/label_file.c
> @@ -87,14 +87,14 @@ void sort_spec_node(struct spec_node *node, struct spec_node *parent)
>  
>  	node->parent = parent;
>  
> -	/* Sort for comparison support and binary search lookup */
> +	/*
> +	 * Sort for comparison support and binary search lookup,
> +	 * except for regex specs which are matched in reverse input order.
> +	 */
>  
>  	if (node->literal_specs_num > 1)
>  		qsort(node->literal_specs, node->literal_specs_num, sizeof(struct literal_spec), compare_literal_spec);
>  
> -	if (node->regex_specs_num > 1)
> -		qsort(node->regex_specs, node->regex_specs_num, sizeof(struct regex_spec), compare_regex_spec);
> -
>  	if (node->children_num > 1)
>  		qsort(node->children, node->children_num, sizeof(struct spec_node), compare_spec_node);
>  
> @@ -144,36 +144,38 @@ static int nodups_spec_node(const struct spec_node *node, const char *path)
>  
>  	if (node->regex_specs_num > 1) {
>  		for (uint32_t i = 0; i < node->regex_specs_num - 1; i++) {
> -			const struct regex_spec *node1 = &node->regex_specs[i];
> -			const struct regex_spec *node2 = &node->regex_specs[i+1];
> +			for (uint32_t j = i; j < node->regex_specs_num - 1; j++) {
> +				const struct regex_spec *node1 = &node->regex_specs[i];
> +				const struct regex_spec *node2 = &node->regex_specs[j + 1];
>  
> -			if (node1->prefix_len != node2->prefix_len)
> -				continue;
> +				if (node1->prefix_len != node2->prefix_len)
> +					continue;
>  
> -			if (strcmp(node1->regex_str, node2->regex_str) != 0)
> -				continue;
> +				if (strcmp(node1->regex_str, node2->regex_str) != 0)
> +					continue;
>  
> -			if (node1->file_kind != LABEL_FILE_KIND_ALL && node2->file_kind != LABEL_FILE_KIND_ALL && node1->file_kind != node2->file_kind)
> -				continue;
> +				if (node1->file_kind != LABEL_FILE_KIND_ALL && node2->file_kind != LABEL_FILE_KIND_ALL && node1->file_kind != node2->file_kind)
> +					continue;
>  
> -			rc = -1;
> -			errno = EINVAL;
> -			if (strcmp(node1->lr.ctx_raw, node2->lr.ctx_raw) != 0) {
> -				COMPAT_LOG
> -					(SELINUX_ERROR,
> -						"%s: Multiple different specifications for %s %s  (%s and %s).\n",
> -						path,
> -						file_kind_to_string(node1->file_kind),
> -						node1->regex_str,
> -						node1->lr.ctx_raw,
> -						node2->lr.ctx_raw);
> -			} else {
> -				COMPAT_LOG
> -					(SELINUX_ERROR,
> -						"%s: Multiple same specifications for %s %s.\n",
> -						path,
> -						file_kind_to_string(node1->file_kind),
> -						node1->regex_str);
> +				rc = -1;
> +				errno = EINVAL;
> +				if (strcmp(node1->lr.ctx_raw, node2->lr.ctx_raw) != 0) {
> +					COMPAT_LOG
> +						(SELINUX_ERROR,
> +							"%s: Multiple different specifications for %s %s  (%s and %s).\n",
> +							path,
> +							file_kind_to_string(node1->file_kind),
> +							node1->regex_str,
> +							node1->lr.ctx_raw,
> +							node2->lr.ctx_raw);
> +				} else {
> +					COMPAT_LOG
> +						(SELINUX_ERROR,
> +							"%s: Multiple same specifications for %s %s.\n",
> +							path,
> +							file_kind_to_string(node1->file_kind),
> +							node1->regex_str);
> +				}
>  			}
>  		}
>  	}
> @@ -1637,8 +1639,9 @@ static struct lookup_result *lookup_check_node(struct spec_node *node, const cha
>  					  : (strcmp(n->literal_specs[literal_idx].literal_match, key) == 0)));
>  		}
>  
> -		for (uint32_t i = 0; i < n->regex_specs_num; i++) {
> -			struct regex_spec *rspec = &n->regex_specs[i];
> +		for (uint32_t i = n->regex_specs_num; i > 0; i--) {
> +			/* search in reverse order */
> +			struct regex_spec *rspec = &n->regex_specs[i - 1];
>  			const char *errbuf = NULL;
>  			int rc;
>  
> @@ -2221,81 +2224,69 @@ static enum selabel_cmp_result spec_node_cmp(const struct spec_node *node1, cons
>  		while (iter1 < node1->regex_specs_num && iter2 < node2->regex_specs_num) {
>  			const struct regex_spec *rspec1 = &node1->regex_specs[iter1];
>  			const struct regex_spec *rspec2 = &node2->regex_specs[iter2];
> -			int cmp;
> -
> -			if (rspec1->prefix_len > rspec2->prefix_len) {
> -				if (result == SELABEL_EQUAL || result == SELABEL_SUPERSET) {
> -					result = SELABEL_SUPERSET;
> -					iter1++;
> -					continue;
> -				}
> +			bool found_successor;
>  
> -				return rspec_incomp(node1->stem, rspec1, rspec2, "regex_prefix_length", iter1, iter2);
> +			if (rspec1->file_kind == rspec2->file_kind && strcmp(rspec1->regex_str, rspec2->regex_str) == 0) {
> +				iter1++;
> +				iter2++;
> +				continue;
>  			}
>  
> -			if (rspec1->prefix_len < rspec2->prefix_len) {
> -				if (result == SELABEL_EQUAL || result == SELABEL_SUBSET) {
> -					result = SELABEL_SUBSET;
> -					iter2++;
> -					continue;
> -				}
> +			if (result == SELABEL_SUPERSET) {
> +				iter1++;
> +				continue;
> +			}
>  
> -				return rspec_incomp(node1->stem, rspec1, rspec2, "regex_prefix_length", iter1, iter2);
> +			if (result == SELABEL_SUBSET) {
> +				iter2++;
> +				continue;
>  			}
>  
> -			/* If prefix length is equal compare regex string */
> +			assert(result == SELABEL_EQUAL);
>  
> -			cmp = strcmp(rspec1->regex_str, rspec2->regex_str);
> -			if (cmp < 0) {
> -				if (result == SELABEL_EQUAL || result == SELABEL_SUPERSET) {
> -					result = SELABEL_SUPERSET;
> -					iter1++;
> -					continue;
> -				}
> +			found_successor = false;
>  
> -				return rspec_incomp(node1->stem, rspec1, rspec2, "regex_str", iter1, iter2);
> -			}
> +			for (uint32_t i = iter2; i < node2->regex_specs_num; i++) {
> +				const struct regex_spec *successor = &node2->regex_specs[i];
>  
> -			if (cmp > 0) {
> -				if (result == SELABEL_EQUAL || result == SELABEL_SUBSET) {
> +				if (rspec1->file_kind == successor->file_kind && strcmp(rspec1->regex_str, successor->regex_str) == 0) {
>  					result = SELABEL_SUBSET;
> -					iter2++;
> -					continue;
> +					iter1++;
> +					iter2 = i + 1;
> +					found_successor = true;
> +					break;
>  				}
> -
> -				return rspec_incomp(node1->stem, rspec1, rspec2, "regex_str", iter1, iter2);
>  			}
>  
> -			/* If literal match is equal compare file kind */
> -
> -			if (rspec1->file_kind > rspec2->file_kind) {
> -				if (result == SELABEL_EQUAL || result == SELABEL_SUPERSET) {
> -					result = SELABEL_SUPERSET;
> -					iter1++;
> -					continue;
> -				}
> +			if (found_successor)
> +				continue;
>  
> -				return rspec_incomp(node1->stem, rspec1, rspec2, "file_kind", iter1, iter2);
> -			}
> +			for (uint32_t i = iter1; i < node1->regex_specs_num; i++) {
> +				const struct regex_spec *successor = &node1->regex_specs[i];
>  
> -			if (rspec1->file_kind < rspec2->file_kind) {
> -				if (result == SELABEL_EQUAL || result == SELABEL_SUBSET) {
> -					result = SELABEL_SUBSET;
> +				if (successor->file_kind == rspec2->file_kind && strcmp(successor->regex_str, rspec2->regex_str) == 0) {
> +					result = SELABEL_SUPERSET;
> +					iter1 = i + 1;
>  					iter2++;
> -					continue;
> +					found_successor = true;
> +					break;
>  				}
> -
> -				return rspec_incomp(node1->stem, rspec1, rspec2, "file_kind", iter1, iter2);
>  			}
>  
> -			iter1++;
> -			iter2++;
> +			if (found_successor)
> +				continue;
> +
> +			return rspec_incomp(node1->stem, rspec1, rspec2, "regex", iter1, iter2);
>  		}
>  		if (iter1 != node1->regex_specs_num) {
>  			if (result == SELABEL_EQUAL || result == SELABEL_SUPERSET) {
>  				result = SELABEL_SUPERSET;
>  			} else {
> -				selinux_log(SELINUX_INFO, "selabel_cmp: mismatch regex_str left remnant in stem %s\n", fmt_stem(node1->stem));
> +				const struct regex_spec *rspec1 = &node1->regex_specs[iter1];
> +
> +				selinux_log(SELINUX_INFO, "selabel_cmp: mismatch regex left remnant in stem %s entry %u: (%s, %s, %s)\n",
> +					    fmt_stem(node1->stem),
> +					    iter1, rspec1->regex_str, file_kind_to_string(rspec1->file_kind), rspec1->lr.ctx_raw);
>  				return SELABEL_INCOMPARABLE;
>  			}
>  		}
> @@ -2303,7 +2294,11 @@ static enum selabel_cmp_result spec_node_cmp(const struct spec_node *node1, cons
>  			if (result == SELABEL_EQUAL || result == SELABEL_SUBSET) {
>  				result = SELABEL_SUBSET;
>  			} else {
> -				selinux_log(SELINUX_INFO, "selabel_cmp: mismatch regex_str right remnant in stem %s\n", fmt_stem(node1->stem));
> +				const struct regex_spec *rspec2 = &node2->regex_specs[iter2];
> +
> +				selinux_log(SELINUX_INFO, "selabel_cmp: mismatch regex right remnant in stem %s entry %u: (%s, %s, %s)\n",
> +					    fmt_stem(node1->stem),
> +					    iter2, rspec2->regex_str, file_kind_to_string(rspec2->file_kind), rspec2->lr.ctx_raw);
>  				return SELABEL_INCOMPARABLE;
>  			}
>  		}
> diff --git a/libselinux/src/label_file.h b/libselinux/src/label_file.h
> index c7fe3a48..7e999ce8 100644
> --- a/libselinux/src/label_file.h
> +++ b/libselinux/src/label_file.h
> @@ -123,7 +123,7 @@ struct spec_node {
>  	uint32_t literal_specs_num, literal_specs_alloc;
>  
>  	/*
> -	 * Array of regular expression specifications (ordered from most to least specific)
> +	 * Array of regular expression specifications (order preserved from input)
>  	 */
>  	struct regex_spec *regex_specs;
>  	uint32_t regex_specs_num, regex_specs_alloc;
> @@ -369,38 +369,6 @@ static inline int compare_literal_spec(const void *p1, const void *p2)
>  	return (l1->file_kind < l2->file_kind) - (l1->file_kind > l2->file_kind);
>  }
>  
> -static inline int compare_regex_spec(const void *p1, const void *p2)
> -{
> -	const struct regex_spec *r1 = p1;
> -	const struct regex_spec *r2 = p2;
> -	size_t regex_len1, regex_len2;
> -	int ret;
> -
> -	/* Order from high prefix length to low */
> -	ret = (r1->prefix_len < r2->prefix_len) - (r1->prefix_len > r2->prefix_len);
> -	if (ret)
> -		return ret;
> -
> -	/* Order from long total regex length to short */
> -	regex_len1 = strlen(r1->regex_str);
> -	regex_len2 = strlen(r2->regex_str);
> -	ret = (regex_len1 < regex_len2) - (regex_len1 > regex_len2);
> -	if (ret)
> -		return ret;
> -
> -	/*
> -	 * Order for no-duplicates check.
> -	 * Use reverse alphabetically order to retain the Fedora ordering of
> -	 * `/usr/(.* /)?lib(/.*)?` before `/usr/(.* /)?bin(/.*)?`.
> -	 */
> -	ret = strcmp(r1->regex_str, r2->regex_str);
> -	if (ret)
> -		return -ret;
> -
> -	/* Order wildcard mode (0) last */
> -	return (r1->file_kind < r2->file_kind) - (r1->file_kind > r2->file_kind);
> -}
> -
>  static inline int compare_spec_node(const void *p1, const void *p2)
>  {
>  	const struct spec_node *n1 = p1;
> -- 
> 2.45.2