linux-integrity.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Mimi Zohar <zohar@linux.ibm.com>
To: Roberto Sassu <roberto.sassu@huawei.com>
Cc: "linux-integrity@vger.kernel.org"
	<linux-integrity@vger.kernel.org>,
	"linux-security-module@vger.kernel.org" 
	<linux-security-module@vger.kernel.org>,
	"linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
	Krzysztof Struczynski <krzysztof.struczynski@huawei.com>,
	Silviu Vlasceanu <Silviu.Vlasceanu@huawei.com>,
	"stable@vger.kernel.org" <stable@vger.kernel.org>
Subject: Re: [PATCH 3/5] ima: Fix ima digest hash table key calculation
Date: Fri, 24 Apr 2020 10:45:44 -0400	[thread overview]
Message-ID: <1587739544.5190.14.camel@linux.ibm.com> (raw)
In-Reply-To: <59a280b928db4c478f660d14c33cdd87@huawei.com>

On Fri, 2020-04-24 at 12:18 +0000, Roberto Sassu wrote:

> > On Thu, 2020-04-23 at 10:21 +0000, Roberto Sassu wrote:
> > > > Hi Roberto, Krsysztof,
> > > >
> > > > On Wed, 2020-03-25 at 17:11 +0100, Roberto Sassu wrote:
> > > > > From: Krzysztof Struczynski <krzysztof.struczynski@huawei.com>
> > > > >
> > > > > Function hash_long() accepts unsigned long, while currently only one
> > byte
> > > > > is passed from ima_hash_key(), which calculates a key for ima_htable.
> > > > Use
> > > > > more bytes to avoid frequent collisions.
> > > > >
> > > > > Length of the buffer is not explicitly passed as a function parameter,
> > > > > because this function expects a digest whose length is greater than
> > the
> > > > > size of unsigned long.
> > > >
> > > > Somehow I missed the original report of this problem https://lore.kern
> > > > el.org/patchwork/patch/674684/.  This patch is definitely better, but
> > > > how many unique keys are actually being used?  Is it anywhere near
> > > > IMA_MEASURE_HTABLE_SIZE(512)?
> > >
> > > I did a small test (with 1043 measurements):
> > >
> > > slots: 250, max depth: 9 (without the patch)
> > > slots: 448, max depth: 7 (with the patch)
> > 
> > 448 out of 512 slots are used.
> > 
> > >
> > > Then, I increased the number of bits to 10:
> > >
> > > slots: 251, max depth: 9 (without the patch)
> > > slots: 660, max depth: 4 (with the patch)
> > 
> > 660 out of 1024 slots are used.
> > 
> > I wonder if there is any benefit to hashing a digest, instead of just
> > using the first bits.
> 
> Before I calculated max depth until there is a match, not the full depth.
> 
> #1
> return hash_long(*((unsigned long *)digest), IMA_HASH_BITS);
> #define IMA_HASH_BITS 9
> 
> Runtime measurements: 1488
> Violations: 0
> Slots (used/available): 484/512
> Max depth hash table: 10
> 
> #2
> return *(unsigned long *)digest % IMA_MEASURE_HTABLE_SIZE;
> #define IMA_HASH_BITS 9
> 
> Runtime measurements: 1491
> Violations: 2
> Slots (used/available): 489/512
> Max depth hash table: 10
> 
> #3
> return hash_long(*((unsigned long *)digest), IMA_HASH_BITS);
> #define IMA_HASH_BITS 10
> 
> Runtime measurements: 1489
> Violations: 0
> Slots (used/available): 780/1024
> Max depth hash table: 6
> 
> #4
> return *(unsigned long *)digest % IMA_MEASURE_HTABLE_SIZE;
> #define IMA_HASH_BITS 10
> 
> Runtime measurements: 1489
> Violations: 0
> Slots (used/available): 793/1024
> Max depth hash table: 6

At least for this measurement list sample, there doesn't seem to be
any benefit to hashing the digest.  In terms of increasing the number
of slots, the additional memory is minimal and shouldn't negatively
affect small embedded devices.  Please make sure checkpatch doesn't
flag it.

thanks,

Mimi

  reply	other threads:[~2020-04-24 14:46 UTC|newest]

Thread overview: 15+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-03-25 16:11 [PATCH 1/5] ima: Set file->f_mode instead of file->f_flags in ima_calc_file_hash() Roberto Sassu
2020-03-25 16:11 ` [PATCH 2/5] evm: Check also if *tfm is an error pointer in init_desc() Roberto Sassu
2020-04-22 13:45   ` Mimi Zohar
2020-04-22 15:37     ` Roberto Sassu
2020-03-25 16:11 ` [PATCH 3/5] ima: Fix ima digest hash table key calculation Roberto Sassu
2020-04-22 20:56   ` Mimi Zohar
2020-04-23 10:21     ` Roberto Sassu
2020-04-23 16:53       ` Mimi Zohar
2020-04-24 12:18         ` Roberto Sassu
2020-04-24 14:45           ` Mimi Zohar [this message]
2020-03-25 16:14 ` [PATCH 4/5] ima: Remove redundant policy rule set in add_rules() Roberto Sassu
2020-03-25 16:14   ` [PATCH 5/5] ima: Remove unused build_ima_appraise variable Roberto Sassu
2020-04-22 22:59     ` Mimi Zohar
2020-04-22 12:03 ` [PATCH 1/5] ima: Set file->f_mode instead of file->f_flags in ima_calc_file_hash() Mimi Zohar
2020-04-22 15:39   ` Roberto Sassu

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1587739544.5190.14.camel@linux.ibm.com \
    --to=zohar@linux.ibm.com \
    --cc=Silviu.Vlasceanu@huawei.com \
    --cc=krzysztof.struczynski@huawei.com \
    --cc=linux-integrity@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-security-module@vger.kernel.org \
    --cc=roberto.sassu@huawei.com \
    --cc=stable@vger.kernel.org \
    --subject='Re: [PATCH 3/5] ima: Fix ima digest hash table key calculation' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).