Re: [PATCH] lib/ts_fsm: preserve token types when exporting patterns

[Andrew Morton <akpm@linux-foundation.org>]

On Sat, 31 Oct 2026 13:23:07 +0800 Zhiqi Zhang <zhiqizhangg@gmail.com> wrote:

> fsm_init() replaces each token type with an internal character-class mask.
> fsm_get_pattern() then returns these masks as if they were public token
> types. Exporting a pattern and preparing another FSM configuration from
> it can therefore change the matching behaviour or fail with -EINVAL.
> 
> For example, a single TS_FSM_DIGIT token (type 2) becomes the _D mask (4).
> Preparing the exported pattern interprets 4 as TS_FSM_PRINT, so the new
> configuration accepts "A" while the original rejects it. The text ematch
> dump path uses textsearch_get_pattern() to return patterns to userspace.
> 
> Keep the public token types in the configuration and look up their masks
> in match_token(). This preserves the exported representation without
> adding another pattern allocation. Initialization still validates every
> type before it can be used to index token_map.
> 
> Add KUnit coverage for exporting and recreating all token types and a
> sequence with a repeated character class. Also check that exporting and
> recreating the pattern leaves the original configuration usable.
> 

The main user of textsearch appears to be netfilter, so please let's
keep the relevant developers in the loop.

netfilter peeps: I'm seeing a small number of textsearch patches lately
and I'm totally unfamiliar with it.  Can you please propose a
MAINTAINERS patch?

hp2:/usr/src/mm> scripts/get_maintainer.pl -f --nogit --nogit-fallback --no-rolestats lib/ts_bm.c lib/ts_fsm.c lib/ts_kmp.c  
Andrew Morton <akpm@linux-foundation.org>
linux-kernel@vger.kernel.org

Lonely!




Zhiqi, a thing which is missing from the changelog, and it's really
important, is a description of the userspace-visible runtime effects of
the bug.

> I identified this issue. OpenAI Codex helped confirm it and drafted the
> fix, KUnit tests and changelog. I reviewed the fix, built it and verified
> that the tests passed.

I'm suspecting "no such effects are known".  But that isn't enough -
once the issue is out there, LLM-using bad actors might be able to find
ways of exploiting the bug, so please discuss that aspect also.

My LLM suggested

: The userspace consequence is worth spelling out: dumping and restoring
: a traffic-control rule can silently change which packets it matches, or
: fail to restore the rule with EINVAL.

Also, and fyi, it told me

: Related finding: BM/KMP also export transformed patterns. With
: TS_IGNORECASE, repeated folding of 0xff changes it again
: (ff -> df -> bf). That's a separate API roundtrip problem, but I found
: no current userspace dump/restore path exposing it: em_text doesn't
: enable that flag, and xt_string retains the original pattern.

Also, regarding your patch:

: One small test improvement: after copying the exported pattern, add
: KUNIT_EXPECT_MEMEQ(test, exported, pattern, len). That directly checks
: the exported representation as well as its matching behavior.

And I'm thinking that a cc:stable is justified here.

Thanks.

> ---
> Validation in isolated QEMU TCG guests:
> - ARM64 GCC 13.3: the same KUnit test and config change from 2/15 passing
>   before the fix to 15/15 passing afterwards.
> - ARM32 GCC 13.3 and ARM64 Clang 18.1.3: 15/15 passing.
> - An ARM64 rtnetlink smoke test creates a basic classifier with a text
>   ematch, dumps it, restores its payload, and dumps it again. The DIGIT
>   token changes 2 -> 4 -> 151 before the fix, and stays 2 afterwards.
> - W=1 for the changed objects: no warnings. Sparse reports no diagnostics
>   for these objects (an unchanged ARM64 vDSO object has a declaration
>   warning). Strict checkpatch passes after suppressing the new-file
>   MAINTAINERS reminder.
> 
> Packet traffic, module loading and throughput were not tested. Resolving
> masks in match_token() adds a lookup on nonliteral matches.
> 
>  lib/Kconfig.debug                |  14 ++++
>  lib/tests/Makefile               |   1 +
>  lib/tests/textsearch_fsm_kunit.c | 137 +++++++++++++++++++++++++++++++
>  lib/ts_fsm.c                     |   7 +-
>  4 files changed, 153 insertions(+), 6 deletions(-)
>  create mode 100644 lib/tests/textsearch_fsm_kunit.c
> 
> diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
> index 2d22638ec..416d033b0 100644
> --- a/lib/Kconfig.debug
> +++ b/lib/Kconfig.debug
> @@ -2531,6 +2531,20 @@ config STRING_HELPERS_KUNIT_TEST
>  	depends on KUNIT
>  	default KUNIT_ALL_TESTS
>  
> +config TEXTSEARCH_FSM_KUNIT_TEST
> +	tristate "KUnit tests for FSM text search" if !KUNIT_ALL_TESTS
> +	depends on KUNIT
> +	select TEXTSEARCH
> +	select TEXTSEARCH_FSM
> +	default KUNIT_ALL_TESTS
> +	help
> +	  Test that exporting and recreating an FSM text search configuration
> +	  preserves its matching behaviour. Exercise each public token type
> +	  and a sequence of tokens with a repeated character class. Check
> +	  that exporting also leaves the original configuration usable.
> +
> +	  If unsure, say N.
> +
>  config STRING_KUNIT_BENCH
>         bool "Benchmark string functions at runtime"
>         depends on STRING_KUNIT_TEST
> diff --git a/lib/tests/Makefile b/lib/tests/Makefile
> index df0537e1b..fa47ef5d3 100644
> --- a/lib/tests/Makefile
> +++ b/lib/tests/Makefile
> @@ -54,6 +54,7 @@ CFLAGS_stackinit_kunit.o += $(call cc-disable-warning, switch-unreachable)
>  obj-$(CONFIG_STACKINIT_KUNIT_TEST) += stackinit_kunit.o
>  obj-$(CONFIG_STRING_KUNIT_TEST) += string_kunit.o
>  obj-$(CONFIG_STRING_HELPERS_KUNIT_TEST) += string_helpers_kunit.o
> +obj-$(CONFIG_TEXTSEARCH_FSM_KUNIT_TEST) += textsearch_fsm_kunit.o
>  obj-$(CONFIG_USERCOPY_KUNIT_TEST) += usercopy_kunit.o
>  obj-$(CONFIG_UTIL_MACROS_KUNIT) += util_macros_kunit.o
>  obj-$(CONFIG_RATELIMIT_KUNIT_TEST) += test_ratelimit.o
> diff --git a/lib/tests/textsearch_fsm_kunit.c b/lib/tests/textsearch_fsm_kunit.c
> new file mode 100644
> index 000000000..bbf944ef8
> --- /dev/null
> +++ b/lib/tests/textsearch_fsm_kunit.c
> @@ -0,0 +1,137 @@
> +// SPDX-License-Identifier: GPL-2.0-or-later
> +/* Tests for exporting and recreating FSM text search configurations. */
> +
> +#include <kunit/test.h>
> +#include <linux/limits.h>
> +#include <linux/module.h>
> +#include <linux/string.h>
> +#include <linux/textsearch.h>
> +#include <linux/textsearch_fsm.h>
> +
> +struct fsm_test_case {
> +	const char *name;
> +	u16 type;
> +	const char *match;
> +	const char *miss;
> +};
> +
> +static const struct fsm_test_case fsm_test_cases[] = {
> +	{ "specific", TS_FSM_SPECIFIC, "x", "y" },
> +	{ "wildcard", TS_FSM_WILDCARD, "A", "" },
> +	{ "digit", TS_FSM_DIGIT, "7", "A" },
> +	{ "xdigit", TS_FSM_XDIGIT, "f", "g" },
> +	{ "print", TS_FSM_PRINT, "A", "\n" },
> +	{ "alpha", TS_FSM_ALPHA, "A", "7" },
> +	{ "alnum", TS_FSM_ALNUM, "7", "!" },
> +	{ "ascii", TS_FSM_ASCII, "A", "\200" },
> +	{ "cntrl", TS_FSM_CNTRL, "\n", "A" },
> +	{ "graph", TS_FSM_GRAPH, "!", " " },
> +	{ "lower", TS_FSM_LOWER, "a", "A" },
> +	{ "upper", TS_FSM_UPPER, "A", "a" },
> +	{ "punct", TS_FSM_PUNCT, "!", "A" },
> +	{ "space", TS_FSM_SPACE, " ", "A" },
> +};
> +
> +static void fsm_case_to_desc(const struct fsm_test_case *params, char *desc)
> +{
> +	snprintf(desc, KUNIT_PARAM_DESC_SIZE, "%s", params->name);
> +}
> +
> +KUNIT_ARRAY_PARAM(fsm, fsm_test_cases, fsm_case_to_desc);
> +
> +static void fsm_destroy_config(void *conf)
> +{
> +	textsearch_destroy(conf);
> +}
> +
> +static void fsm_expect_matches(struct kunit *test, struct ts_config *conf,
> +			       const struct fsm_test_case *params)
> +{
> +	struct ts_state state = {};
> +	unsigned int pos;
> +
> +	pos = textsearch_find_continuous(conf, &state, params->match,
> +					 strlen(params->match));
> +	KUNIT_EXPECT_EQ(test, pos, 0U);
> +	pos = textsearch_find_continuous(conf, &state, params->miss,
> +					 strlen(params->miss));
> +	KUNIT_EXPECT_EQ(test, pos, UINT_MAX);
> +}
> +
> +static void fsm_check_roundtrip(struct kunit *test,
> +				const struct ts_fsm_token *pattern,
> +				unsigned int len,
> +				const struct fsm_test_case *params)
> +{
> +	struct ts_fsm_token *exported;
> +	struct ts_config *conf, *recreated;
> +	int err;
> +
> +	conf = textsearch_prepare("fsm", pattern, len, GFP_KERNEL, TS_AUTOLOAD);
> +	KUNIT_ASSERT_NOT_ERR_OR_NULL(test, conf);
> +	err = kunit_add_action_or_reset(test, fsm_destroy_config, conf);
> +	KUNIT_ASSERT_EQ(test, err, 0);
> +	fsm_expect_matches(test, conf, params);
> +
> +	KUNIT_ASSERT_EQ(test, textsearch_get_pattern_len(conf), len);
> +	exported = kunit_kmalloc(test, len, GFP_KERNEL);
> +	KUNIT_ASSERT_NOT_NULL(test, exported);
> +	memcpy(exported, textsearch_get_pattern(conf), len);
> +
> +	/* Exporting a pattern must preserve the existing search behaviour. */
> +	fsm_expect_matches(test, conf, params);
> +
> +	recreated = textsearch_prepare("fsm", exported, len, GFP_KERNEL,
> +				       TS_AUTOLOAD);
> +	KUNIT_ASSERT_NOT_ERR_OR_NULL_MSG(test, recreated,
> +					 "exported token: type=%u recur=%u value=%u",
> +					 exported->type, exported->recur,
> +					 exported->value);
> +	err = kunit_add_action_or_reset(test, fsm_destroy_config, recreated);
> +	KUNIT_ASSERT_EQ(test, err, 0);
> +	fsm_expect_matches(test, recreated, params);
> +	fsm_expect_matches(test, conf, params);
> +}
> +
> +static void fsm_test_pattern_roundtrip(struct kunit *test)
> +{
> +	const struct fsm_test_case *params = test->param_value;
> +	struct ts_fsm_token pattern = {
> +		.type = params->type,
> +		.recur = TS_FSM_SINGLE,
> +		.value = 'x',
> +	};
> +
> +	fsm_check_roundtrip(test, &pattern, sizeof(pattern), params);
> +}
> +
> +static void fsm_test_sequence_roundtrip(struct kunit *test)
> +{
> +	static const struct ts_fsm_token pattern[] = {
> +		{ TS_FSM_DIGIT, TS_FSM_MULTI, 0 },
> +		{ TS_FSM_SPECIFIC, TS_FSM_SINGLE, ':' },
> +		{ TS_FSM_UPPER, TS_FSM_SINGLE, 0 },
> +	};
> +	static const struct fsm_test_case params = {
> +		.match = "77:A",
> +		.miss = "77:a",
> +	};
> +
> +	fsm_check_roundtrip(test, pattern, sizeof(pattern), &params);
> +}
> +
> +static struct kunit_case fsm_kunit_test_cases[] = {
> +	KUNIT_CASE_PARAM(fsm_test_pattern_roundtrip, fsm_gen_params),
> +	KUNIT_CASE(fsm_test_sequence_roundtrip),
> +	{}
> +};
> +
> +static struct kunit_suite fsm_test_suite = {
> +	.name = "textsearch-fsm",
> +	.test_cases = fsm_kunit_test_cases,
> +};
> +
> +kunit_test_suite(fsm_test_suite);
> +
> +MODULE_DESCRIPTION("FSM text search configuration tests");
> +MODULE_LICENSE("GPL");
> diff --git a/lib/ts_fsm.c b/lib/ts_fsm.c
> index 053615f4f..8725ea6f0 100644
> --- a/lib/ts_fsm.c
> +++ b/lib/ts_fsm.c
> @@ -126,7 +126,7 @@ _W|_L,         _W|_L,        _W|_L,        _W|_L};		/* 252-255 */
>  static inline int match_token(struct ts_fsm_token *t, u8 d)
>  {
>  	if (t->type)
> -		return (token_lookup_tbl[d] & t->type) != 0;
> +		return (token_lookup_tbl[d] & token_map[t->type]) != 0;
>  	else
>  		return t->value == d;
>  }
> @@ -288,11 +288,6 @@ static struct ts_config *fsm_init(const void *pattern, unsigned int len,
>  	fsm->ntokens = ntokens;
>  	memcpy(fsm->tokens, pattern, len);
>  
> -	for (i = 0; i < fsm->ntokens; i++) {
> -		struct ts_fsm_token *t = &fsm->tokens[i];
> -		t->type = token_map[t->type];
> -	}
> -
>  	return conf;
>  
>  errout:
> 
> base-commit: 2a500a04d6f969318c05f46aedb6e73fc1963a00
> -- 
> 2.54.0 (Apple Git-157)