[PATCH v4 0/2] IMA: Deferred measurement of keys

[PATCH v4 0/2] IMA: Deferred measurement of keys

[Lakshmi Ramasubramanian]

This patchset extends the previous version[1] by adding support for
deferred processing of keys.

With the patchset referenced above, the IMA subsystem supports
measuring asymmetric keys when the key is created or updated.
But keys created or updated before a custom IMA policy is loaded
are currently not measured. This includes keys added to, for instance,
.builtin_trusted_keys which happens early in the boot process.

This change adds support for queuing keys created or updated before
a custom IMA policy is loaded. The queued keys are processed when
a custom policy is loaded. Keys created or updated after a custom policy
is loaded are measured immediately (not queued).

If the kernel is built with both CONFIG_IMA and
CONFIG_ASYMMETRIC_PUBLIC_KEY_SUBTYPE enabled then the IMA policy
must be applied as a custom policy. Not providing a custom policy
in the above configuration would result in asymmeteric keys being queued
until a custom policy is loaded. This is by design.

[1] https://lore.kernel.org/linux-integrity/20191211164707.4698-1-nramas@linux.microsoft.com/

Testing performed:

  * Booted the kernel with this change.
  * Added .builtin_trusted_keys in "keyrings=" option in
    the IMA policy and verified the keys added to this
    keyring are measured.
  * Specified only func=KEY_CHECK and not "keyrings=" option,
    and verified the keys added to builtin_trusted_keys keyring
    are processed.
  * Added keys at runtime and verified they are measured
    if the IMA policy permitted.
      => For example, added keys to .ima keyring and verified.

Changelog:

  v4

  => Check and set ima_process_keys flag with mutex held.

  v3

  => Defined ima_process_keys flag to be static.
  => Set ima_process_keys with ima_keys_mutex held.
  => Added a comment in ima_process_queued_keys() function
     to state the use of temporary list for keys.

  v2

  => Rebased the changes to v5.5-rc1
  => Updated function names, variable names, and code comments
     to be less verbose.

  v1

  => Code cleanup

  v0

  => Based changes on v5.4-rc8
  => The following patchsets should be applied in that order
     https://lore.kernel.org/linux-integrity/1572492694-6520-1-git-send-email-zohar@linux.ibm.com
     https://lore.kernel.org/linux-integrity/20191204224131.3384-1-nramas@linux.microsoft.com/
  => Added functions to queue and dequeue keys, and process
     the queued keys when custom IMA policies are applied.

Lakshmi Ramasubramanian (2):
  IMA: Define workqueue for early boot key measurements
  IMA: Call workqueue functions to measure queued keys

 security/integrity/ima/ima.h                 |  15 ++
 security/integrity/ima/ima_asymmetric_keys.c | 136 +++++++++++++++++++
 security/integrity/ima/ima_policy.c          |   3 +
 3 files changed, 154 insertions(+)

-- 
2.17.1

[PATCH v4 1/2] IMA: Define workqueue for early boot "key" measurements

[Lakshmi Ramasubramanian]

Measuring keys requires a custom IMA policy to be loaded.
Keys created or updated before a custom IMA policy is loaded should
be queued and the keys should be processed after a custom policy
is loaded.

This patch defines workqueue for queuing keys when a custom IMA policy
has not yet been loaded.

A flag namely ima_process_keys is used to check if the key should be
queued or should be processed immediately.

Signed-off-by: Lakshmi Ramasubramanian <nramas@linux.microsoft.com>
---
 security/integrity/ima/ima.h                 |  15 +++
 security/integrity/ima/ima_asymmetric_keys.c | 128 +++++++++++++++++++
 2 files changed, 143 insertions(+)

diff --git a/security/integrity/ima/ima.h b/security/integrity/ima/ima.h
index f06238e41a7c..97f8a4078483 100644
--- a/security/integrity/ima/ima.h
+++ b/security/integrity/ima/ima.h
@@ -205,6 +205,21 @@ extern const char *const func_tokens[];
 
 struct modsig;
 
+#ifdef CONFIG_ASYMMETRIC_PUBLIC_KEY_SUBTYPE
+/*
+ * To track keys that need to be measured.
+ */
+struct ima_key_entry {
+	struct list_head list;
+	void *payload;
+	size_t payload_len;
+	char *keyring_name;
+};
+void ima_process_queued_keys(void);
+#else
+static inline void ima_process_queued_keys(void) {}
+#endif /* CONFIG_ASYMMETRIC_PUBLIC_KEY_SUBTYPE */
+
 /* LIM API function definitions */
 int ima_get_action(struct inode *inode, const struct cred *cred, u32 secid,
 		   int mask, enum ima_hooks func, int *pcr,
diff --git a/security/integrity/ima/ima_asymmetric_keys.c b/security/integrity/ima/ima_asymmetric_keys.c
index fea2e7dd3b09..ae6de1bb2e79 100644
--- a/security/integrity/ima/ima_asymmetric_keys.c
+++ b/security/integrity/ima/ima_asymmetric_keys.c
@@ -14,6 +14,134 @@
 #include <keys/asymmetric-type.h>
 #include "ima.h"
 
+/*
+ * Flag to indicate whether a key can be processed
+ * right away or should be queued for processing later.
+ */
+static bool ima_process_keys;
+
+/*
+ * To synchronize access to the list of keys that need to be measured
+ */
+static DEFINE_MUTEX(ima_keys_mutex);
+static LIST_HEAD(ima_keys);
+
+static void ima_free_key_entry(struct ima_key_entry *entry)
+{
+	if (entry) {
+		kfree(entry->payload);
+		kfree(entry->keyring_name);
+		kfree(entry);
+	}
+}
+
+static struct ima_key_entry *ima_alloc_key_entry(
+	struct key *keyring,
+	const void *payload, size_t payload_len)
+{
+	int rc = 0;
+	struct ima_key_entry *entry;
+
+	entry = kzalloc(sizeof(*entry), GFP_KERNEL);
+	if (entry) {
+		entry->payload = kmemdup(payload, payload_len, GFP_KERNEL);
+		entry->keyring_name = kstrdup(keyring->description,
+					      GFP_KERNEL);
+		entry->payload_len = payload_len;
+	}
+
+	if ((entry == NULL) || (entry->payload == NULL) ||
+	    (entry->keyring_name == NULL)) {
+		rc = -ENOMEM;
+		goto out;
+	}
+
+	INIT_LIST_HEAD(&entry->list);
+
+out:
+	if (rc) {
+		ima_free_key_entry(entry);
+		entry = NULL;
+	}
+
+	return entry;
+}
+
+bool ima_queue_key(struct key *keyring, const void *payload,
+		   size_t payload_len)
+{
+	bool queued = false;
+	struct ima_key_entry *entry;
+
+	entry = ima_alloc_key_entry(keyring, payload, payload_len);
+	if (!entry)
+		return false;
+
+	mutex_lock(&ima_keys_mutex);
+	if (!ima_process_keys) {
+		list_add_tail(&entry->list, &ima_keys);
+		queued = true;
+	}
+	mutex_unlock(&ima_keys_mutex);
+
+	if (!queued)
+		ima_free_key_entry(entry);
+
+	return queued;
+}
+
+/*
+ * ima_process_queued_keys() - process keys queued for measurement
+ *
+ * This function sets ima_process_keys to true and processes queued keys.
+ * From here on keys will be processed right away (not queued).
+ */
+void ima_process_queued_keys(void)
+{
+	struct ima_key_entry *entry, *tmp;
+	LIST_HEAD(temp_ima_keys);
+	bool process = false;
+
+	if (ima_process_keys)
+		return;
+
+	/*
+	 * To avoid holding the mutex when processing queued keys,
+	 * transfer the queued keys with the mutex held to a temp list,
+	 * release the mutex, and then process the queued keys from
+	 * the temp list.
+	 *
+	 * Since ima_process_keys is set to true, any new key will be
+	 * processed immediately and not be queued.
+	 */
+	INIT_LIST_HEAD(&temp_ima_keys);
+
+	mutex_lock(&ima_keys_mutex);
+
+	if (!ima_process_keys) {
+		ima_process_keys = true;
+
+		if (!list_empty(&ima_keys)) {
+			list_for_each_entry_safe(entry, tmp, &ima_keys, list)
+				list_move_tail(&entry->list, &temp_ima_keys);
+			process = true;
+		}
+	}
+
+	mutex_unlock(&ima_keys_mutex);
+
+	if (!process)
+		return;
+
+	list_for_each_entry_safe(entry, tmp, &temp_ima_keys, list) {
+		process_buffer_measurement(entry->payload, entry->payload_len,
+					   entry->keyring_name, KEY_CHECK, 0,
+					   entry->keyring_name);
+		list_del(&entry->list);
+		ima_free_key_entry(entry);
+	}
+}
+
 /**
  * ima_post_key_create_or_update - measure asymmetric keys
  * @keyring: keyring to which the key is linked to
-- 
2.17.1

[PATCH v4 2/2] IMA: Call workqueue functions to measure queued keys

[Lakshmi Ramasubramanian]

Measuring keys requires a custom IMA policy to be loaded.
Keys should be queued for measurement if a custom IMA policy
is not yet loaded. Keys queued for measurement, if any, should be
processed when a custom IMA policy is loaded.

This patch updates the IMA hook function ima_post_key_create_or_update()
to queue the key if a custom IMA policy has not yet been loaded.
And, ima_update_policy() function, which is called when
a custom IMA policy is loaded, is updated to process queued keys.

Sample "key" measurement rule in the IMA policy:

measure func=KEY_CHECK uid=0 keyrings=.ima|.builtin_trusted_keys template=ima-buf

If the kernel is built with one or more built-in trusted certificates,
IMA measurement should list all the keys imported from those certificates.

Display "key" measurement in the IMA measurement list:

cat /sys/kernel/security/ima/ascii_runtime_measurements

10 faf3...e702 ima-buf sha256:27c915b8ddb9fae7214cf0a8a7043cc3eeeaa7539bcb136f8427067b5f6c3b7b .builtin_trusted_keys 308202863082...4aee

Verify "key" measurement data for a key added to ".builtin_trusted_keys" keyring:

cat /sys/kernel/security/integrity/ima/ascii_runtime_measurements | grep -m 1 "\.builtin_trusted_keys" | cut -d' ' -f 6 | xxd -r -p |tee btk-cert.der | sha256sum | cut -d' ' -f 1

The output of the above command should match the template hash
of the first "key" measurement entry in the IMA measurement list for
the key added to ".builtin_trusted_keys" keyring.

The file namely "btk-cert.der" generated by the above command
should be a valid x509 certificate (in DER format) and should match
the one that was used to import the key to the ".builtin_trusted_keys" keyring.
The certificate file can be verified using openssl tool.

Signed-off-by: Lakshmi Ramasubramanian <nramas@linux.microsoft.com>
---
 security/integrity/ima/ima_asymmetric_keys.c | 8 ++++++++
 security/integrity/ima/ima_policy.c          | 3 +++
 2 files changed, 11 insertions(+)

diff --git a/security/integrity/ima/ima_asymmetric_keys.c b/security/integrity/ima/ima_asymmetric_keys.c
index ae6de1bb2e79..8a9d8bc7e10d 100644
--- a/security/integrity/ima/ima_asymmetric_keys.c
+++ b/security/integrity/ima/ima_asymmetric_keys.c
@@ -158,6 +158,8 @@ void ima_post_key_create_or_update(struct key *keyring, struct key *key,
 				   const void *payload, size_t payload_len,
 				   unsigned long flags, bool create)
 {
+	bool queued = false;
+
 	/* Only asymmetric keys are handled by this hook. */
 	if (key->type != &key_type_asymmetric)
 		return;
@@ -165,6 +167,12 @@ void ima_post_key_create_or_update(struct key *keyring, struct key *key,
 	if (!payload || (payload_len == 0))
 		return;
 
+	if (!ima_process_keys)
+		queued = ima_queue_key(keyring, payload, payload_len);
+
+	if (queued)
+		return;
+
 	/*
 	 * keyring->description points to the name of the keyring
 	 * (such as ".builtin_trusted_keys", ".ima", etc.) to
diff --git a/security/integrity/ima/ima_policy.c b/security/integrity/ima/ima_policy.c
index a4dde9d575b2..04b9c6c555de 100644
--- a/security/integrity/ima/ima_policy.c
+++ b/security/integrity/ima/ima_policy.c
@@ -807,6 +807,9 @@ void ima_update_policy(void)
 		kfree(arch_policy_entry);
 	}
 	ima_update_policy_flag();
+
+	/* Custom IMA policy has been loaded */
+	ima_process_queued_keys();
 }
 
 /* Keep the enumeration in sync with the policy_tokens! */
-- 
2.17.1

Re: [PATCH v4 2/2] IMA: Call workqueue functions to measure queued keys

[James Bottomley]

On Fri, 2019-12-13 at 09:18 -0800, Lakshmi Ramasubramanian wrote:
[...]
> @@ -165,6 +167,12 @@ void ima_post_key_create_or_update(struct key
> *keyring, struct key *key,
>  	if (!payload || (payload_len == 0))
>  		return;
>  
> +	if (!ima_process_keys)
> +		queued = ima_queue_key(keyring, payload,
> payload_len);
> +
> +	if (queued)
> +		return;
> +
>  	/*
>  	 * keyring->description points to the name of the keyring
>  	 * (such as ".builtin_trusted_keys", ".ima", etc.) to
> diff --git a/security/integrity/ima/ima_policy.c
> b/security/integrity/ima/ima_policy.c
> index a4dde9d575b2..04b9c6c555de 100644
> --- a/security/integrity/ima/ima_policy.c
> +++ b/security/integrity/ima/ima_policy.c
> @@ -807,6 +807,9 @@ void ima_update_policy(void)
>  		kfree(arch_policy_entry);
>  	}
>  	ima_update_policy_flag();
> +
> +	/* Custom IMA policy has been loaded */
> +	ima_process_queued_keys();
>  }

There's no locking around the ima_process_keys flag.  If you get two
policy updates in quick succession can't this flag change as you're
processing the second update meaning you lose it because the flag was
false when you decided to build it for the queue but becomes true
before you check above whether you need to queue it?

Note you don't need locking to fix this, you just need to ensure that
you use the same copy of the flag value for both tests.

James

Re: [PATCH v4 2/2] IMA: Call workqueue functions to measure queued keys

[Lakshmi Ramasubramanian]

On 12/13/19 9:25 AM, James Bottomley wrote:

Hi James,

> 
> There's no locking around the ima_process_keys flag.  If you get two
> policy updates in quick succession can't this flag change as you're
> processing the second update meaning you lose it because the flag was
> false when you decided to build it for the queue but becomes true
> before you check above whether you need to queue it?
> 
> Note you don't need locking to fix this, you just need to ensure that
> you use the same copy of the flag value for both tests.
> 
> James
> 

Same flag (ima_process_keys) is used for making the queuing decision.

Taking a lock to access ima_process_keys is required only if the flag is 
false. That is handled in ima_queue_key() and ima_process_queued_keys() 
functions.

Queued keys are processed when the first policy update occurs. 
Subsequently, the keys are processed immediately (not queued).

Could you please review those functions in this patch and let me know if 
you see a problem?

thanks,
  -lakshmi

Re: [PATCH v4 2/2] IMA: Call workqueue functions to measure queued keys

[James Bottomley]

On Fri, 2019-12-13 at 09:31 -0800, Lakshmi Ramasubramanian wrote:
> On 12/13/19 9:25 AM, James Bottomley wrote:
> 
> Hi James,
> 
> > 
> > There's no locking around the ima_process_keys flag.  If you get
> > two policy updates in quick succession can't this flag change as
> > you're processing the second update meaning you lose it because the
> > flag was false when you decided to build it for the queue but
> > becomes true before you check above whether you need to queue it?
> > 
> > Note you don't need locking to fix this, you just need to ensure
> > that you use the same copy of the flag value for both tests.
> > 
> > James
> > 
> 
> Same flag (ima_process_keys) is used for making the queuing decision.
> 
> Taking a lock to access ima_process_keys is required only if the flag
> is false. That is handled in ima_queue_key() and
> ima_process_queued_keys() functions.
> 
> Queued keys are processed when the first policy update occurs. 
> Subsequently, the keys are processed immediately (not queued).
> 
> Could you please review those functions in this patch and let me know
> if you see a problem?

This is the problem:

if (!flag)
    pre()
.
.
.
if (!flag)
    post()

And your pre and post function either have to both run or neither must.
 However, the flag is set asynchronously, so if it gets set while
another thread is running through the above code, it can change after
pre is run but before post is.

James

Re: [PATCH v4 2/2] IMA: Call workqueue functions to measure queued keys

[Lakshmi Ramasubramanian]

On 12/15/2019 7:22 AM, James Bottomley wrote:

Hi James,

> 
> This is the problem:
> 
> if (!flag)
>      pre()
> .
> .
> .
> if (!flag)
>      post()
> 
> And your pre and post function either have to both run or neither must.
>   However, the flag is set asynchronously, so if it gets set while
> another thread is running through the above code, it can change after
> pre is run but before post is.
> 
> James

The pre() and post() functions you have referenced above including the 
check for the flag are executed with the mutex held.

Please see Mimi's response to the v3 email. I have copied it below:

************************************
Reading the flag IS lock protected, just spread across two functions.
For performance, ima_post_key_create_or_update() checks
ima_process_keys, before calling ima_queue_key(), which takes the
mutex before checking ima_process_keys again.

As long as both the reader and writer, take the mutex before checking
the flag, the locking is fine.  The additional check, before taking
the mutex, is simply for performance.
************************************

The flag is checked with the mutex held in the "reader" - 
ima_queue_key(). The key is queued with the mutex held only if the flag 
is false.

The flag is protected in the "writer" also - ima_process_queued_keys(). 
The flag is checked with the mutex held, set to true, and queued keys 
(if any) are transferred to the temp list.

As Mimi has pointed out the additional check of the flag, before taking 
the mutex in ima_post_key_create_or_update() and in 
ima_process_queued_keys(), is for performance reason.

If the flag is true, there is no need to take the mutex to check it 
again in those functions.

thanks,
  -lakshmi

Re: [PATCH v4 2/2] IMA: Call workqueue functions to measure queued keys

[James Bottomley]

On Sun, 2019-12-15 at 17:12 -0800, Lakshmi Ramasubramanian wrote:
> On 12/15/2019 7:22 AM, James Bottomley wrote:
> 
> Hi James,
> 
> > 
> > This is the problem:
> > 
> > if (!flag)
> >      pre()
> > .
> > .
> > .
> > if (!flag)
> >      post()
> > 
> > And your pre and post function either have to both run or neither
> > must.
> >   However, the flag is set asynchronously, so if it gets set while
> > another thread is running through the above code, it can change
> > after
> > pre is run but before post is.
> > 
> > James
> 
> The pre() and post() functions you have referenced above including
> the 
> check for the flag are executed with the mutex held.
> 
> Please see Mimi's response to the v3 email. I have copied it below:
> 
> ************************************
> Reading the flag IS lock protected, just spread across two functions.
> For performance, ima_post_key_create_or_update() checks
> ima_process_keys, before calling ima_queue_key(), which takes the
> mutex before checking ima_process_keys again.
> 
> As long as both the reader and writer, take the mutex before checking
> the flag, the locking is fine.  The additional check, before taking
> the mutex, is simply for performance.
> ************************************
> 
> The flag is checked with the mutex held in the "reader" - 
> ima_queue_key(). The key is queued with the mutex held only if the
> flag 
> is false.
> 
> The flag is protected in the "writer" also -
> ima_process_queued_keys(). 
> The flag is checked with the mutex held, set to true, and queued
> keys 
> (if any) are transferred to the temp list.
> 
> As Mimi has pointed out the additional check of the flag, before
> taking 
> the mutex in ima_post_key_create_or_update() and in 
> ima_process_queued_keys(), is for performance reason.
> 
> If the flag is true, there is no need to take the mutex to check it 
> again in those functions.

That doesn't matter ... the question is, is the input assumption that
both pre/post have to be called or neither must correct?  If so, the
code is wrong, if not, explain why.

James

Re: [PATCH v4 1/2] IMA: Define workqueue for early boot "key" measurements

[Mimi Zohar]

On Fri, 2019-12-13 at 09:18 -0800, Lakshmi Ramasubramanian wrote:

> +/*
> + * ima_process_queued_keys() - process keys queued for measurement
> + *
> + * This function sets ima_process_keys to true and processes queued keys.
> + * From here on keys will be processed right away (not queued).
> + */
> +void ima_process_queued_keys(void)
> +{
> +	struct ima_key_entry *entry, *tmp;
> +	LIST_HEAD(temp_ima_keys);
> +	bool process = false;
> +
> +	if (ima_process_keys)
> +		return;
> +
> +	/*
> +	 * To avoid holding the mutex when processing queued keys,
> +	 * transfer the queued keys with the mutex held to a temp list,
> +	 * release the mutex, and then process the queued keys from
> +	 * the temp list.
> +	 *
> +	 * Since ima_process_keys is set to true, any new key will be
> +	 * processed immediately and not be queued.
> +	 */
> +	INIT_LIST_HEAD(&temp_ima_keys);
> +
> +	mutex_lock(&ima_keys_mutex);
> +
> +	if (!ima_process_keys) {
> +		ima_process_keys = true;

Thank you for moving the initialization here.  The comment is now
valid and the following code is now guaranteed to execute just once.

> +
> +		if (!list_empty(&ima_keys)) {
> +			list_for_each_entry_safe(entry, tmp, &ima_keys, list)
> +				list_move_tail(&entry->list, &temp_ima_keys);
> +			process = true;
> +		}
> +	}
> +
> +	mutex_unlock(&ima_keys_mutex);
> +
> +	if (!process)
> +		return;

The new changes - checking if the list is empty and this test - are
unnecessary, as you implied earlier.

Mimi

> +
> +	list_for_each_entry_safe(entry, tmp, &temp_ima_keys, list) {
> +		process_buffer_measurement(entry->payload, entry->payload_len,
> +					   entry->keyring_name, KEY_CHECK, 0,
> +					   entry->keyring_name);
> +		list_del(&entry->list);
> +		ima_free_key_entry(entry);
> +	}
> +}
> +
>  /**
>   * ima_post_key_create_or_update - measure asymmetric keys
>   * @keyring: keyring to which the key is linked to

Re: [PATCH v4 2/2] IMA: Call workqueue functions to measure queued keys

[Mimi Zohar]

On Mon, 2019-12-16 at 15:53 +0900, James Bottomley wrote:
> That doesn't matter ... the question is, is the input assumption that
> both pre/post have to be called or neither must correct?  If so, the
> code is wrong, if not, explain why.

Thanks, James, for looking at the locking.

"ima_process_keys" is set once.  Once it is set, the keys are measured
immediately.  For performance to avoid taking the mutex, both the
reader and writer check "ima_process_keys" twice, once without taking
the lock and, again, after taking the lock.  Based on the second test,
the reader queues the "key" or not.  Refer to ima_queue_key().

The latest patch version sets "ima_process_keys" after taking the
lock.  With this change, the comment in ima_process_queued_keys() is
now correct.  We're now guaranteed to process the queued "keys" just
once and not drop any "key" measurements.

I hope this answers your question.

Mimi

Re: [PATCH v4 2/2] IMA: Call workqueue functions to measure queued keys

[Lakshmi Ramasubramanian]

On 12/15/2019 10:53 PM, James Bottomley wrote:

Hi James,

> On Sun, 2019-12-15 at 17:12 -0800, Lakshmi Ramasubramanian wrote:
>> On 12/15/2019 7:22 AM, James Bottomley wrote:
>>
>> Hi James,
>>
>>>
>>> This is the problem:
>>>
>>> if (!flag)
>>>       pre()
>>> .
>>> .
>>> .
>>> if (!flag)
>>>       post()
>>>
>>> And your pre and post function either have to both run or neither
>>> must.
>>>    However, the flag is set asynchronously, so if it gets set while
>>> another thread is running through the above code, it can change
>>> after
>>> pre is run but before post is.
>>>

> 
> That doesn't matter ... the question is, is the input assumption that
> both pre/post have to be called or neither must correct?  If so, the
> code is wrong, if not, explain why.
> 
> James
> 

I assume you are asking
"What happens if the flag changes between the check done without the 
mutex held (pre()) and the check done after the mutex is taken (post())".

If I misunderstood your question, please clarify.

"READER" functions: ima_post_key_create_or_update() and ima_queue_key()
***********************************************************************
In ima_post_key_create_or_update() the flag is checked first without the 
mutex taken:

  => If the flag is true, then there is no need to queue the key and it 
can be processed immediately.

     This condition means that either queued keys have already been 
processed OR there is another thread in the middle of processing queued 
keys. In both these conditions, the new key should NOT be queued, but 
processed immediately.

  => If the flag is false, ima_queue_key() is called. In this function, 
the mutex is taken and flag checked again.

Say, the flag changed from false to true at this point, the key will NOT 
be queued. ima_queue_key() will return false and in response 
ima_post_key_create_or_update() will process the key immediately.

But if the flag is still false, the key will be queued by 
ima_queue_key() and will be processed later.

"WRITER" function: ima_process_queued_keys()
********************************************
In ima_process_queued_keys() the flag is checked first without the mutex 
taken:

  => If the flag is true, either the queued keys have already been 
processed OR is in the middle of being processed. So no further action 
is required.

  => If the flag is false, mutex is taken and the flag is checked again. 
If the flag changed from false to true between the above two tests, that 
means another thread had raced to call ima_process_queued_keys() and has 
processed the queued keys. So again, no further action is required.

  But if the flag is still false (after the mutex is taken), then the 
queued keys are processed and the flag is set to true.

The above sequence ensures that queued keys are processed one and only 
once. Subsequent keys are always processed immediately.

To the best of my knowledge, there is no condition under which a key 
would ever be dropped or be queued up without ever getting processed.
I hope that answers your question.

If you are still not convinced, please describe a sequence of steps that 
can cause incorrect functionality.

thanks,
  -lakshmi

Re: [PATCH v4 2/2] IMA: Call workqueue functions to measure queued keys

[James Bottomley]

On Mon, 2019-12-16 at 11:20 -0800, Lakshmi Ramasubramanian wrote:
>   => If the flag is false, mutex is taken and the flag is checked
> again. If the flag changed from false to true between the above two
> tests, that means another thread had raced to call
> ima_process_queued_keys() and has  processed the queued keys. So
> again, no further action is required.

This is the problem: in the race case you may still be adding keys to
the queue after the other thread has processed it. Those keys won't get
processed because the flag is now false in the post check so the
current thread won't process them either.

James

Re: [PATCH v4 2/2] IMA: Call workqueue functions to measure queued keys

[Lakshmi Ramasubramanian]

On 12/16/2019 1:17 PM, James Bottomley wrote:
> On Mon, 2019-12-16 at 11:20 -0800, Lakshmi Ramasubramanian wrote:
>>    => If the flag is false, mutex is taken and the flag is checked
>> again. If the flag changed from false to true between the above two
>> tests, that means another thread had raced to call
>> ima_process_queued_keys() and has  processed the queued keys. So
>> again, no further action is required.
> 
> This is the problem: in the race case you may still be adding keys to
> the queue after the other thread has processed it. Those keys won't get
> processed because the flag is now false in the post check so the
> current thread won't process them either.
> 
> James
> 

I am not sure how a key could get added to the queue after another 
thread has processed the queued keys.

The flag changes from false to true only once - in 
ima_process_queued_keys(). This change is done under the lock. The 
thread that makes this change will process all the queued keys.

Once the above change is done, ima_process_keys flag will never become 
false again.

Another thread that is trying to queue the key will wait on the mutex - 
in ima_queue_key(). If this thread finds the flag is true after taking 
the mutex, it will NOT queue the key.

Please see my explanation below:


"READER" functions: ima_post_key_create_or_update() and ima_queue_key()
***********************************************************************
In ima_post_key_create_or_update() the flag is checked first without the 
mutex taken:

  => If the flag is true, then there is no need to queue the key and it 
can be processed immediately.

     This condition means that either queued keys have already been 
processed OR there is another thread in the middle of processing queued 
keys. In both these conditions, the new key should NOT be queued, but 
processed immediately.

  => If the flag is false, ima_queue_key() is called. In this function, 
the mutex is taken and flag checked again.

Say, the flag changed from false to true at this point, the key will NOT 
be queued. ima_queue_key() will return false and in response 
ima_post_key_create_or_update() will process the key immediately.

But if the flag is still false, the key will be queued by 
ima_queue_key() and will be processed later.

Re: [PATCH v4 2/2] IMA: Call workqueue functions to measure queued keys

[Lakshmi Ramasubramanian]

On 12/16/2019 1:37 PM, Lakshmi Ramasubramanian wrote:
> 
> On 12/16/2019 1:17 PM, James Bottomley wrote:
>> On Mon, 2019-12-16 at 11:20 -0800, Lakshmi Ramasubramanian wrote:
>>>    => If the flag is false, mutex is taken and the flag is checked
>>> again. If the flag changed from false to true between the above two
>>> tests, that means another thread had raced to call
>>> ima_process_queued_keys() and has  processed the queued keys. So
>>> again, no further action is required.
>>
>> This is the problem: in the race case you may still be adding keys to
>> the queue after the other thread has processed it. Those keys won't get
>> processed because the flag is now false in the post check so the
>> current thread won't process them either.
>>
>> James
>>

Please keep in mind that ima_queue_key() returns a boolean indicating 
whether or not the key was queued. This flag is set inside the lock - 
please see the code snippet from ima_queue_key() below:

+	mutex_lock(&ima_keys_mutex);
+	if (!ima_process_keys) {
+		list_add_tail(&entry->list, &ima_keys);
+		queued = true;
+	}
+	mutex_unlock(&ima_keys_mutex);

If ima_process_keys had changed from false to true, ima_queue_key() will 
not queue the key and return false to ima_post_key_create_or_update().

Code snippet in ima_post_key_create_or_update():

+	if (!ima_process_keys)
+		queued = ima_queue_key(keyring, payload, payload_len);
+
+	if (queued)
+		return;

If the "queued" is false, ima_post_key_create_or_update() will process 
the key immediately.

  -lakshmi

Re: [PATCH v4 1/2] IMA: Define workqueue for early boot "key" measurements

[Lakshmi Ramasubramanian]

On 12/16/2019 4:30 AM, Mimi Zohar wrote:

>> +
>> +		if (!list_empty(&ima_keys)) {
>> +			list_for_each_entry_safe(entry, tmp, &ima_keys, list)
>> +				list_move_tail(&entry->list, &temp_ima_keys);
>> +			process = true;
>> +		}
>> +	}
>> +
>> +	mutex_unlock(&ima_keys_mutex);
>> +
>> +	if (!process)
>> +		return;
> 
> The new changes - checking if the list is empty and this test - are
> unnecessary, as you implied earlier.
> 
> Mimi

Do you want me to remove this check? I feel it is safer to have this 
check - use a local flag "process" to return if no keys were moved to 
the temp list. Would like to leave it as is - if you don't mind.

thanks,
  -lakshmi

Re: [PATCH v4 1/2] IMA: Define workqueue for early boot "key" measurements

[Mimi Zohar]

On Mon, 2019-12-16 at 15:44 -0800, Lakshmi Ramasubramanian wrote:
> On 12/16/2019 4:30 AM, Mimi Zohar wrote:
> 
> >> +
> >> +		if (!list_empty(&ima_keys)) {
> >> +			list_for_each_entry_safe(entry, tmp, &ima_keys, list)
> >> +				list_move_tail(&entry->list, &temp_ima_keys);
> >> +			process = true;
> >> +		}
> >> +	}
> >> +
> >> +	mutex_unlock(&ima_keys_mutex);
> >> +
> >> +	if (!process)
> >> +		return;
> > 
> > The new changes - checking if the list is empty and this test - are
> > unnecessary, as you implied earlier.
> > 
> > Mimi
> 
> Do you want me to remove this check? I feel it is safer to have this 
> check - use a local flag "process" to return if no keys were moved to 
> the temp list. Would like to leave it as is - if you don't mind.

Sure
  

Re: [PATCH v4 2/2] IMA: Call workqueue functions to measure queued keys

[Lakshmi Ramasubramanian]

Hi James,

>>>
>>> This is the problem: in the race case you may still be adding keys to
>>> the queue after the other thread has processed it. Those keys won't get
>>> processed because the flag is now false in the post check so the
>>> current thread won't process them either.
>>>
>>> James
>>>

Please let me know if you still think there is a race condition.

If yes, please explain how a key would be added to the queue after 
ima_process_queued_keys() has processed queued keys.
ima_process_keys flag will be true when queued keys have been processed.

> 
> Please keep in mind that ima_queue_key() returns a boolean indicating 
> whether or not the key was queued. This flag is set inside the lock - 
> please see the code snippet from ima_queue_key() below:
> 
> +    mutex_lock(&ima_keys_mutex);
> +    if (!ima_process_keys) {
> +        list_add_tail(&entry->list, &ima_keys);
> +        queued = true;
> +    }
> +    mutex_unlock(&ima_keys_mutex);
> 
> If ima_process_keys had changed from false to true, ima_queue_key() will 
> not queue the key and return false to ima_post_key_create_or_update().
> 
> Code snippet in ima_post_key_create_or_update():
> 
> +    if (!ima_process_keys)
> +        queued = ima_queue_key(keyring, payload, payload_len);
> +
> +    if (queued)
> +        return;
> 
> If the "queued" is false, ima_post_key_create_or_update() will process 
> the key immediately.
> 
>   -lakshmi

thanks,
  -lakshmi

Re: [PATCH v4 2/2] IMA: Call workqueue functions to measure queued keys

[James Bottomley]

On Tue, 2019-12-17 at 14:22 -0800, Lakshmi Ramasubramanian wrote:
> Hi James,
> 
> > > > 
> > > > This is the problem: in the race case you may still be adding
> > > > keys to
> > > > the queue after the other thread has processed it. Those keys
> > > > won't get
> > > > processed because the flag is now false in the post check so
> > > > the
> > > > current thread won't process them either.
> > > > 
> > > > James
> > > > 
> 
> Please let me know if you still think there is a race condition.
> 
> If yes, please explain how a key would be added to the queue after 
> ima_process_queued_keys() has processed queued keys.
> ima_process_keys flag will be true when queued keys have been
> processed.

This code is confusing me:

+       /*
+        * To avoid holding the mutex when processing queued keys,
+        * transfer the queued keys with the mutex held to a temp list,
+        * release the mutex, and then process the queued keys from
+        * the temp list.
+        *
+        * Since ima_process_keys is set to true, any new key will be
+        * processed immediately and not be queued.
+        */
+       INIT_LIST_HEAD(&temp_ima_keys);
+
+       mutex_lock(&ima_keys_mutex);
+
+       if (!ima_process_keys) {
+               ima_process_keys = true;
+
+               if (!list_empty(&ima_keys)) {
+                       list_for_each_entry_safe(entry, tmp, &ima_keys, list)
+                               list_move_tail(&entry->list, &temp_ima_keys);
+                       process = true;
+               }
+       }
+
+       mutex_unlock(&ima_keys_mutex);
+
+       if (!process)
+               return;
+
+       list_for_each_entry_safe(entry, tmp, &temp_ima_keys, list) {
+               process_buffer_measurement(entry->payload, entry->payload_len,
+                                          entry->keyring_name, KEY_CHECK, 0,
+                                          entry->keyring_name);
+               list_del(&entry->list);
+               ima_free_key_entry(entry);
+       }
+}
+

The direct implication of the comment and the lock dance with the
temporary list and the processed flag is that stuff can be added to the
ima_keys list after you drop the mutex.  Your explanation in the prior
couple of emails says that nothing can be added because the
ima_process_keys flag setting prevents it.  If the latter is true, you
can simply drop the lock after setting the flag and rely on ima_keys
not changing to run it through process_buffer_measurement without
needing any of the intermediate list or the processed flag.  If the
latter isn't true then any key added to ima_keys after the mutex is
dropped is never processed.

James

Re: [PATCH v4 2/2] IMA: Call workqueue functions to measure queued keys

[Lakshmi Ramasubramanian]

On 12/17/2019 6:01 PM, James Bottomley wrote:

> 
> This code is confusing me:
> 
> +       /*
> +        * To avoid holding the mutex when processing queued keys,
> +        * transfer the queued keys with the mutex held to a temp list,
> +        * release the mutex, and then process the queued keys from
> +        * the temp list.
> +        *
> +        * Since ima_process_keys is set to true, any new key will be
> +        * processed immediately and not be queued.
> +        */
> +       INIT_LIST_HEAD(&temp_ima_keys);
> +
> +       mutex_lock(&ima_keys_mutex);
> +
> +       if (!ima_process_keys) {
> +               ima_process_keys = true;
> +
> +               if (!list_empty(&ima_keys)) {
> +                       list_for_each_entry_safe(entry, tmp, &ima_keys, list)
> +                               list_move_tail(&entry->list, &temp_ima_keys);
> +                       process = true;
> +               }
> +       }
> +
> +       mutex_unlock(&ima_keys_mutex);
> +
> 
> The direct implication of the comment and the lock dance with the
> temporary list and the processed flag is that stuff can be added to the
> ima_keys list after you drop the mutex.  Your explanation in the prior
> couple of emails says that nothing can be added because the
> ima_process_keys flag setting prevents it.  If the latter is true, you
> can simply drop the lock after setting the flag and rely on ima_keys
> not changing to run it through process_buffer_measurement without
> needing any of the intermediate list or the processed flag.  If the
> latter isn't true then any key added to ima_keys after the mutex is
> dropped is never processed.
> 
> James

Once the flag is set no new key will be added to ima_keys list.

You are right - if the flag is set with the lock taken, then there is no 
need for the temp list. After dropping the lock, measurement can be done 
directly from ima_keys list.

Thanks for reviewing the code. I'll send an update tomorrow.

  -lakshmi

Re: [PATCH v4 2/2] IMA: Call workqueue functions to measure queued keys

[Lakshmi Ramasubramanian]

On 12/17/2019 6:44 PM, Lakshmi Ramasubramanian wrote:

>>
>> The direct implication of the comment and the lock dance with the
>> temporary list and the processed flag is that stuff can be added to the
>> ima_keys list after you drop the mutex.  Your explanation in the prior
>> couple of emails says that nothing can be added because the
>> ima_process_keys flag setting prevents it.  If the latter is true, you
>> can simply drop the lock after setting the flag and rely on ima_keys
>> not changing to run it through process_buffer_measurement without
>> needing any of the intermediate list or the processed flag.  If the
>> latter isn't true then any key added to ima_keys after the mutex is
>> dropped is never processed.
>>
>> James

One more scenario needs to be taken care - that still doesn't require a 
temp list, but will need a local flag.

Say, two threads race to call ima_process_queued_keys().
Both find ima_process_keys flag is false.
They now race to take to the lock.
Only the 1st one setting the flag to true should process queued keys.

  -lakshmi

Re: [PATCH v4 2/2] IMA: Call workqueue functions to measure queued keys

[James Bottomley]

On Tue, 2019-12-17 at 19:00 -0800, Lakshmi Ramasubramanian wrote:
> On 12/17/2019 6:44 PM, Lakshmi Ramasubramanian wrote:
> 
> > > 
> > > The direct implication of the comment and the lock dance with the
> > > temporary list and the processed flag is that stuff can be added
> > > to the ima_keys list after you drop the mutex.  Your explanation
> > > in the prior couple of emails says that nothing can be added
> > > because the ima_process_keys flag setting prevents it.  If the
> > > latter is true, you can simply drop the lock after setting the
> > > flag and rely on ima_keys not changing to run it through
> > > process_buffer_measurement without needing any of the
> > > intermediate list or the processed flag.  If the latter isn't
> > > true then any key added to ima_keys after the mutex
> > > is dropped is never processed.
> > > 
> > > James
> 
> One more scenario needs to be taken care - that still doesn't require
> a temp list, but will need a local flag.
> 
> Say, two threads race to call ima_process_queued_keys().
> Both find ima_process_keys flag is false.
> They now race to take to the lock.
> Only the 1st one setting the flag to true should process queued keys.

Kernel developers are systems people ... this is what we do with bit
test and set ... but the API is definitely less friendly than boolean
flags.

James