[PATCH] ima: fix infinite loop within "ima_match_policy" function.

[THOBY Simon]

Hi Liqiong,

On 8/20/21 7:53 PM, liqiong wrote:
> Hi Simon,
> 
> On 2021/8/20 21:23, 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.
> I got it,  how about this:
>  /*
>   * The previous list has to traverse to new list,
>   * Or there may be a deadly loop within

Maybe 'deadlock' would be clearer than 'deadly loop'?

>   * "list_for_each_entry_rcu(entry, ima_rules, list)"
>   *
>   * That is tricky, after updated "ima_rules", restore the previous list.

Maybe something like "This is tricky, so we restore the previous list (ima_default_rules)
once 'ima_rules' is updated" ?

>   */>>
>>
>>> +               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 :)
> 
> 
> Sorry for the mistake, I copy/paste the patch and delete/edit some lines,
> have reviewed before sending, but not found. I have made a case to reproduce
> the error, dumping "ima_rules" and every item address of list in the error
> situaiton, I can watchthe "ima_rules" change, old list traversing to the new list.
> And I have been doing a reboot test which found this bug. This patch seems to work fine.
> 

No worries, i just wanted to make sure I understood you correctly.

> 
>>
>>> +               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 ?
>>
>> 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'
>>                                                                     /\
>> 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.
> 
> 
> Yes, It's the workflow.
> 
> 
>> 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?
> 
> 
> Yes,  "ima_rules" cache not update in time, It's a risk. I am not sure if "WRITE_ONCE"
> can do this trick. How about:
>     WRITE_ONCE(prev_rules->next, policy->next);
>     WRITE_ONCE(ima_rules, policy);

Quite frankly, I don't know. As I said earlier, this is really way above my level.
I'm fine waiting for more experienced opinions on this one.

On the aspect of maintainability, I do think this solution is perhaps too complex
when compared to other solutions like the semaphore you first proposed.
A solution of similar complexity with RCU would be ideal to prevent adding a
semaphore on a read-mostly scenario, but I'm still more confident in the semaphore
than in the solution above, because it is easy to have confidence in the semaphore,
while this patch is not at all obvious to me, and maybe the next person who will
have to edit that piece of code.

> 
> If can't fix the cache issue, maybe the "ima_rules_tmp" solution is the best way.
> I will test it.
> 
> 
>> 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 :-)
>>
>>> ----------
>>> Regards,
>>> liqiong

Thanks,
Simon