Support Union and Difference in AuthorizationSetandroid-7.1.2_r9android-7.1.2_r8android-7.1.2_r6android-7.1.2_r5android-7.1.2_r4android-7.1.2_r39android-7.1.2_r38android-7.1.2_r37android-7.1.2_r36android-7.1.2_r33android-7.1.2_r32android-7.1.2_r30android-7.1.2_r3android-7.1.2_r29android-7.1.2_r28android-7.1.2_r27android-7.1.2_r25android-7.1.2_r24android-7.1.2_r23android-7.1.2_r2android-7.1.2_r19android-7.1.2_r18android-7.1.2_r17android-7.1.2_r16android-7.1.2_r15android-7.1.2_r14android-7.1.2_r13android-7.1.2_r12android-7.1.2_r11android-7.1.2_r10android-7.1.2_r1nougat-mr2.3-releasenougat-mr2.2-releasenougat-mr2.1-releasenougat-mr2-security-releasenougat-mr2-releasenougat-mr2-pixel-releasenougat-mr2-dev

In order to allow the KeyStore to load and populate the key
characteristics from disk, we need to be able to take the union and
difference of the AuthorizationSet retrieved from disk and the KM
device.

BUG: 30701680
Change-Id: Iced0a4abeda1f281b36c03e72d556071c4e0260d

3 files changed, 152 insertions, 0 deletions

diff --git a/authorization_set.cpp b/authorization_set.cpp
index 9f6810d..4cf070c 100644
--- a/authorization_set.cpp
+++ b/authorization_set.cpp
@@ -179,6 +179,32 @@ void AuthorizationSet::Deduplicate() {
     memmove(elems_, elems_ + invalid_count, size() * sizeof(*elems_));
 }
 
+void AuthorizationSet::Union(const keymaster_key_param_set_t& set) {
+    if (set.length == 0)
+        return;
+
+    push_back(set);
+    Deduplicate();
+}
+
+void AuthorizationSet::Difference(const keymaster_key_param_set_t& set) {
+    if (set.length == 0)
+        return;
+
+    Deduplicate();
+
+    for (size_t i = 0; i < set.length; i++) {
+        int index = -1;
+        do {
+            index = find(set.params[i].tag, index);
+            if (index != -1 && keymaster_param_compare(&elems_[index], &set.params[i]) == 0) {
+                erase(index);
+                break;
+            }
+        } while (index != -1);
+    }
+}
+
 void AuthorizationSet::CopyToParamSet(keymaster_key_param_set_t* set) const {
     assert(set);
 
diff --git a/authorization_set_test.cpp b/authorization_set_test.cpp
index ddc7df3..f3f4412 100644
--- a/authorization_set_test.cpp
+++ b/authorization_set_test.cpp
@@ -626,5 +626,120 @@ TEST(Deduplication, DuplicateBlob) {
     // The real test here is that valgrind reports no leak.
 }
 
+TEST(Union, Disjoint) {
+    AuthorizationSet set1(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    AuthorizationSet set2(AuthorizationSetBuilder()
+                             .Authorization(TAG_USER_ID, 7)
+                             .Authorization(TAG_APPLICATION_DATA, "foo", 3)
+                             .Authorization(TAG_USER_AUTH_TYPE, HW_AUTH_PASSWORD));
+
+    AuthorizationSet expected(AuthorizationSetBuilder()
+                             .Authorization(TAG_USER_AUTH_TYPE, HW_AUTH_PASSWORD)
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_USER_ID, 7)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4)
+                             .Authorization(TAG_APPLICATION_DATA, "foo", 3));
+
+    set1.Union(set2);
+    EXPECT_EQ(expected, set1);
+}
+
+TEST(Union, Overlap) {
+    AuthorizationSet set1(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    AuthorizationSet set2(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    AuthorizationSet expected(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    set1.Union(set2);
+    EXPECT_EQ(expected, set1);
+}
+
+TEST(Union, Empty) {
+    AuthorizationSet set1(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    AuthorizationSet set2;
+
+    AuthorizationSet expected(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    set1.Union(set2);
+    EXPECT_EQ(expected, set1);
+}
+
+TEST(Difference, Disjoint) {
+    AuthorizationSet set1(AuthorizationSetBuilder()
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4)
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10));
+
+    AuthorizationSet set2(AuthorizationSetBuilder()
+                             .Authorization(TAG_USER_ID, 7)
+                             .Authorization(TAG_APPLICATION_DATA, "foo", 3)
+                             .Authorization(TAG_USER_AUTH_TYPE, HW_AUTH_PASSWORD));
+
+    // Elements are the same as set1, but happen to be in a different order
+    AuthorizationSet expected(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    set1.Difference(set2);
+    EXPECT_EQ(expected, set1);
+}
+
+TEST(Difference, Overlap) {
+    AuthorizationSet set1(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    AuthorizationSet set2(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    AuthorizationSet empty;
+    set1.Difference(set2);
+    EXPECT_EQ(empty, set1);
+    EXPECT_EQ(0U, set1.size());
+}
+
+TEST(Difference, NullSet) {
+    AuthorizationSet set1(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    AuthorizationSet set2;
+
+    AuthorizationSet expected(AuthorizationSetBuilder()
+                             .Authorization(TAG_PURPOSE, KM_PURPOSE_VERIFY)
+                             .Authorization(TAG_ACTIVE_DATETIME, 10)
+                             .Authorization(TAG_APPLICATION_DATA, "data", 4));
+
+    set1.Difference(set2);
+    EXPECT_EQ(expected, set1);
+}
+
 }  // namespace test
 }  // namespace keymaster
diff --git a/include/keymaster/authorization_set.h b/include/keymaster/authorization_set.h
index ec68de0..1a7894d 100644
--- a/include/keymaster/authorization_set.h
+++ b/include/keymaster/authorization_set.h
@@ -164,6 +164,17 @@ class AuthorizationSet : public Serializable, public keymaster_key_param_set_t {
     void Deduplicate();
 
     /**
+     * Adds all elements from \p set that are not already present in this AuthorizationSet.  As a
+     * side-effect, if \p set is not null this AuthorizationSet will end up sorted.
+     */
+    void Union(const keymaster_key_param_set_t& set);
+
+    /**
+     * Removes all elements in \p set from this AuthorizationSet.
+     */
+    void Difference(const keymaster_key_param_set_t& set);
+
+    /**
      * Returns the data in a keymaster_key_param_set_t, suitable for returning to C code.  For C
      * compatibility, the contents are malloced, not new'ed, and so must be freed with free(), or
      * better yet with keymaster_free_param_set, not delete.  The caller takes ownership.