linux-kernel - Re: [PATCH v3 2/2] selinux: improve bucket distribution uniformity of avc

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20251017095342.1180797-1-zhanghongru@xiaomi.com>
Date: Fri, 17 Oct 2025 17:53:42 +0800
From: Hongru Zhang <zhanghongru06@...il.com>
To: paul@...l-moore.com
Cc: linux-kernel@...r.kernel.org,
	omosnace@...hat.com,
	selinux@...r.kernel.org,
	stephen.smalley.work@...il.com,
	zhanghongru06@...il.com,
	zhanghongru@...omi.com
Subject: Re: [PATCH v3 2/2] selinux: improve bucket distribution uniformity of avc_hash()

> On Sep 26, 2025 Hongru Zhang <zhanghongru06@...il.com> wrote:
> > 
> > Under heavy stress testing (on an 8-core system sustaining over 50,000
> > authentication events per second), sample once per second and take the
> > mean of 1800 samples:
> > 
> > 1. Bucket utilization rate and length of longest chain
> > +--------------------------+-----------------------------------------+
> > |                          | bucket utilization rate / longest chain |
> > |                          +--------------------+--------------------+
> > |                          |      no-patch      |     with-patch     |
> > +--------------------------+--------------------+--------------------+
> > |  512 nodes,  512 buckets |      52.5%/7.5     |     58.2%/6.2      |
> > +--------------------------+--------------------+--------------------+
> > | 1024 nodes,  512 buckets |      68.9%/12.1    |     82.4%/8.9      |
> > +--------------------------+--------------------+--------------------+
> > | 2048 nodes,  512 buckets |      83.7%/19.4    |     94.8%/15.2     |
> > +--------------------------+--------------------+--------------------+
> > | 8192 nodes, 8192 buckets |      49.5%/11.4    |     61.9%/6.6      |
> > +--------------------------+--------------------+--------------------+
> > 
> > 2. avc_search_node latency (total latency of hash operation and table
> > lookup)
> > +--------------------------+-----------------------------------------+
> > |                          |   latency of function avc_search_node   |
> > |                          +--------------------+--------------------+
> > |                          |      no-patch      |     with-patch     |
> > +--------------------------+--------------------+--------------------+
> > |  512 nodes,  512 buckets |        87ns        |        79ns        |
> > +--------------------------+--------------------+--------------------+
> > | 1024 nodes,  512 buckets |        97ns        |        91ns        |
> > +--------------------------+--------------------+--------------------+
> > | 2048 nodes,  512 buckets |       118ns        |       110ns        |
> > +--------------------------+--------------------+--------------------+
> > | 8192 nodes, 8192 buckets |       106ns        |        94ns        |
> > +--------------------------+--------------------+--------------------+
> > 
> > Although the multiplication in the new hash algorithm has higher overhead
> > than the bitwise operations in the original algorithm, the data shows
> > that the new algorithm achieves better distribution, reducing average
> > lookup time. Consequently, the total latency of hashing and table lookup
> > is lower than before.
> > 
> > Signed-off-by: Hongru Zhang <zhanghongru@...omi.com>
> > Reviewed-by: Stephen Smalley <stephen.smalley.work@...il.com>
> > ---
> >  security/selinux/avc.c | 17 ++++++++++++++++-
> >  1 file changed, 16 insertions(+), 1 deletion(-)
> 
> My understanding from previous iterations of this patch is that this new
> hash function was AI generated and hasn't really gone through the any
> rigorus analysis beyond the performance measurements above, is that
> correct?  I'm not opposed to using AI to assist in patch development or
> algorithm creation, especially if there is some acknowledgement in the
> commit description, but I do hold the patches to the same standard as
> any other proposed change.  For this reason, I would expect some third
> party review of the hash function by someone with enough experience to
> provide a reasonable analysis of the hash function in comparison to
> other existing options.
> 
> ... and yes, I do recognize that the existing AVC hash function likely
> did not have to go through the same level of scrutiny, but it has the
> significant advantage of being a known quantity, problems and all.
> 
> If you want to change the AVC hash to something else with better
> performance, I suggest sticking with a well known hash algorithm,
> ideally one already present in the kernel; that is going to be the
> quickest path towards acceptance.

Stephen initially suggested I refer to the jhash or MurmurHash3 algorithms
in the kernel. In my previous testing, MurmurHash3 also achieved
performance improvements compared to the original algorithm, so it's good.

I plan to move the MurmurHash3 implementation from avtab_hash() to a newly
created file security/selinux/include/hash.h as a public function, which
will be called by both avtab_hash() and avc_hash(). Is this ok?