LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: 李力琼 <liqiong@nfschina.com>
To: Mimi Zohar <zohar@linux.ibm.com>, THOBY Simon <Simon.THOBY@viveris.fr>
Cc: "dmitry.kasatkin@gmail.com" <dmitry.kasatkin@gmail.com>,
	"jmorris@namei.org" <jmorris@namei.org>,
	"serge@hallyn.com" <serge@hallyn.com>,
	"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>
Subject: Re: [PATCH] ima: fix infinite loop within "ima_match_policy" function.
Date: Mon, 23 Aug 2021 15:51:35 +0800	[thread overview]
Message-ID: <0b0ca83f-9c5b-e4b0-f2c2-b389053479c7@nfschina.com> (raw)
In-Reply-To: <f9798484-7090-0ddf-50a6-7c7c5bf0606c@nfschina.com>

Hi Simon :

Using a temporary ima_rules variable is not working for "ima_policy_next". void *ima_policy_next(struct seq_file *m, void *v, loff_t *pos) { struct ima_rule_entry *entry = v; + struct list_head *ima_rules_tmp = rcu_dereference(ima_rules); rcu_read_lock(); entry = list_entry_rcu(entry->list.next, struct ima_rule_entry, list); rcu_read_unlock(); (*pos)++; - return (&entry->list == ima_rules) ? NULL : entry; + return (&entry->list == ima_rules_tmp) ? NULL : entry; }

It seems no way to fix "ima_rules" change within this function, it will alway
return a entry if "ima_rules" being changed.

Regrads,

liqiong

在 2021年08月23日 11:04, 李力琼 写道:
> Hi Mimi :
>
> The situation is a little different,'list_splice_init_rcu'
> don't change the list head. If "ima_rules" being changed,
> readers may can't reload the new value in time for cpu cache
> or compiler optimization. Defining "ima_rules" as a volatile 
> variable can fix, but It is inefficient.
>
> Maybe using a temporary ima_rules variable for every 
> "list_for_each_entry_rcu(entry, ima_rules, list)" loop is 
> a better solution to fix the "endless loop" bug. 
>
> Regards,
>
> liqiong
>
> 在 2021年08月20日 23:48, Mimi Zohar 写道:
>> On Fri, 2021-08-20 at 13:23 +0000, THOBY Simon wrote:
>>> Hi Liqiong,
>>>
>>> On 8/20/21 12:15 PM, 李力琼 wrote:
>>>> Hi, Simon:
>>>>
>>>> This solution is better then rwsem, a temp "ima_rules" variable should 
>>>> can fix. I also have a another idea, with a little trick, default list
>>>> can traverse to the new list, so we don't need care about the read side. 
>>>>
>>>> here is the patch:
>>>>
>>>> @@ -918,8 +918,21 @@ void ima_update_policy(void)
>>>>         list_splice_tail_init_rcu(&ima_temp_rules, policy, synchronize_rcu);
>>>>
>>>>         if (ima_rules != policy) {
>>>> +               struct list_head *prev_rules = ima_rules;
>>>> +               struct list_head *first = ima_rules->next;
>>>>                 ima_policy_flag = 0;
>>>> +
>>>> +               /*
>>>> +                * Make the previous list can traverse to new list,
>>>> +                * that is tricky, or there is a deadly loop whithin
>>>> +                * "list_for_each_entry_rcu(entry, ima_rules, list)"
>>>> +                *
>>>> +                * After update "ima_rules", restore the previous list.
>>>> +                */
>>> I think this could be rephrased to be a tad clearer, I am not quite sure
>>> how I must interpret the first sentence of the comment.
>>>
>>>
>>>> +               prev_rules->next = policy->next;
>>>>                 ima_rules = policy;
>>>> +               syncchronize_rcu();
>>> I'm a bit puzzled as you seem to imply in the mail this patch was tested,
>>> but there is no 'syncchronize_rcu' (with two 'c') symbol in the kernel.
>>> Was that a copy/paste error? Or maybe you forgot the 'not' in "This
>>> patch has been tested"? These errors happen, and I am myself quite an
>>> expert in doing them :)
>>>
>>>> +               prev_rules->next = first;
>>>>
>>>>
>>>> The side effect is the "ima_default_rules" will be changed a little while.
>>>> But it make sense, the process should be checked again by the new policy.
>>>>
>>>> This patch has been tested, if will do, I can resubmit this patch.> 
>>>> How about this ?
>>> least
>>>
>>> Correct me if I'm wrong, here is how I think I understand you patch.
>>> We start with a situation like that (step 0):
>>> ima_rules --> List entry 0 (head node) = ima_default_rules <-> List entry 1 <-> List entry 2 <-> ... <-> List entry 0
>>>
>>> Then we decide to update the policy for the first time, so
>>> 'ima_rules [&ima_default_rules] != policy [&ima_policy_rules]'.
>>> We enter the condition.
>>> First we copy the current value of ima_rules (&ima_default_rules)
>>> to a temporary variable 'prev_rules'. We also create a pointer dubbed
>>> 'first' to the entry 1 in the default list (step 1):
>>> prev_rules -------------
>>>                        \/
>>> ima_rules --> List entry 0 (head node) = ima_default_rules <-> List entry 1 <-> List entry 2 <-> ... <-> List entry 0
>>>                                                                    /\
>>> first --------------------------------------------------------------
>>>
>>>
>>> Then we update prev_rules->next to point to policy->next (step 2):
>>> List entry 1 <-> List entry 2 <-> ... -> List entry 0
>>>  /\
>>> first
>>> 	(notice that list entry 0 no longer points backwards to 'list entry 1',
>>> 	but I don't think there is any reverse iteration in IMA, so it should be
>>> 	safe)
>>>
>>> prev_rules -------------
>>>                        \/
>>> ima_rules --> List entry 0 (head node) = ima_default_rules   
>>>                        |
>>>                        |
>>>                        -------------------------------------------
>>>                                                                  \/
>>> policy --> policy entry 0' (head node) = ima_policy_rules <-> policy entry 1' <-> policy entry 2' <-> .... <-> policy entry 0'
>>>
>>>
>>> We then update ima_rules to point to ima_policy_rules (step 3):
>>> List entry 1 <-> List entry 2 <-> ... -> List entry 0
>>>  /\
>>> first
>>>
>>> prev_rules -------------
>>>                        \/
>>> ima_rules     List entry 0 (head node) = ima_default_rules   
>>>      |                 |
>>>      |                 |
>>>      |                 ------------------------------------------
>>>      ---------------                                            |
>>>                    \/                                           \/
>>> policy --> policy entry 0' (head node) = ima_policy_rules <-> policy entry 1' <-> policy entry 2' <-> .... <-> policy entry 0'
>>>                                                   synchronize_rcu                 /\
>>> first --------------------------------------------------------------
>>>
>>> Then we run synchronize_rcu() to wait for any RCU reader to exit their loops (step 4).
>>>
>>> Finally we update prev_rules->next to point back to the ima policy and fix the loop (step 5):
>>>
>>> List entry 1 <-> List entry 2 <-> ... -> List entry 0
>>>  /\
>>> first
>>>
>>> prev_rules ---> List entry 0 (head node) = ima_default_rules <-> List entry 1 <-> List entry 2 <-> ... <-> List entry 0
>>>                                                                      /\
>>>                                                                  first (now useless)
>>> ima_rules        
>>>      |
>>>      |
>>>      |
>>>      ---------------
>>>                    \/
>>> policy --> policy entry 0' (head node) = ima_policy_rules <-> policy entry 1' <-> policy entry 2' <-> .... <-> policy entry 0'
>>>
>>> The goal is that readers should still be able to loop
>>> (forward, as we saw that backward looping is temporarily broken)
>>> while in steps 0-4.
>>>
>>> I'm not completely sure what would happen to a client that started iterating
>>> over ima_rules right after step 2.
>>>
>>> Wouldn't they be able to start looping through the new policy
>>> as 'List entry 0 (head node) = ima_default_rules' points to ima_policy_rules?
>>> And if they, wouldn't they loop until the write to 'ima_rule' at step 3 (admittedly
>>> very shortly thereafter) completed?
>>> And would the compiler be allowed to optimize the read to 'ima_rules' in the
>>> list_for_each_entry() loop, thereby never reloading the new value for
>>> 'ima_rules', and thus looping forever, just what we are trying to avoid?
>>>
>>> Overall, I'm tempted to say this is perhaps a bit too complex (at least,
>>> my head tells me it is, but that may very well be because I'm terrible
>>> at concurrency issues).
>>>
>>> Honestly, in this case I think awaiting input from more experienced
>>> kernel devs than I is the best path forward :-)
>> I'm far from an expert on RCU locking, but __list_splice_init_rcu()
>> provides an example of how to make sure there aren't any readers
>> traversing the list, before two lists are spliced together.   In our
>> case, after there aren't any readers, instead of splicing two lists
>> together, it should be safe to point to the new list.
>>
>> thanks,
>>
>> Mimi
>>


  reply	other threads:[~2021-08-23  7:52 UTC|newest]

Thread overview: 36+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-08-19 10:15 liqiong
2021-08-19 12:58 ` THOBY Simon
2021-08-19 13:47   ` Mimi Zohar
2021-08-19 19:31     ` Mimi Zohar
2021-08-20 10:15   ` 李力琼
2021-08-20 13:23     ` THOBY Simon
2021-08-20 15:48       ` Mimi Zohar
2021-08-23  3:04         ` 李力琼
2021-08-23  7:51           ` 李力琼 [this message]
2021-08-23  8:06           ` liqiong
2021-08-23  8:14             ` THOBY Simon
2021-08-23 11:57               ` Mimi Zohar
2021-08-23 12:02                 ` THOBY Simon
2021-08-23 12:09                   ` Mimi Zohar
2021-08-23 12:56               ` liqiong
2021-08-23 11:22           ` Mimi Zohar
2021-08-20 17:53       ` liqiong
2021-08-23  7:13         ` THOBY Simon
2021-08-24  8:57 ` [PATCH] ima: fix deadlock " liqiong
2021-08-24  9:50   ` THOBY Simon
2021-08-24 12:09     ` liqiong
2021-08-24 12:38       ` Mimi Zohar
2021-08-25  7:05         ` [PATCH] ima: fix deadlock within RCU list of ima_rules liqiong
2021-08-25 11:45           ` liqiong
2021-08-25 12:03             ` THOBY Simon
2021-08-26  8:15               ` liqiong
2021-08-26  9:01                 ` THOBY Simon
2021-08-27  6:41                   ` liqiong
2021-08-27  7:30                     ` THOBY Simon
2021-08-27  9:10                       ` liqiong
2021-08-27  9:20                         ` THOBY Simon
2021-08-27 10:35   ` [PATCH] ima: fix deadlock when traversing "ima_default_rules" liqiong
2021-08-27 16:16     ` Mimi Zohar
2021-09-18  3:11     ` liqiong
2021-09-30 19:46       ` Mimi Zohar
2021-10-09 10:38       ` liqiong

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=0b0ca83f-9c5b-e4b0-f2c2-b389053479c7@nfschina.com \
    --to=liqiong@nfschina.com \
    --cc=Simon.THOBY@viveris.fr \
    --cc=dmitry.kasatkin@gmail.com \
    --cc=jmorris@namei.org \
    --cc=linux-integrity@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-security-module@vger.kernel.org \
    --cc=serge@hallyn.com \
    --cc=zohar@linux.ibm.com \
    --subject='Re: [PATCH] ima: fix infinite loop within "ima_match_policy" function.' \
    /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).