Initial work for key rotation.

Introduces the upgrade-keyset tag to AndroidManifest.xml. This specifies a
KeySet by which an apk must be signed in order to update the app. Multiple
upgrade KeySets may be specified, in which case one of them must be used to
sign the updating apk.  If no upgrade-keyset is specified, the current logic
involving signatures is used.

Current Key Rotation Design Decisions:
-Apps using a shared user id may not rotate keys.
-All acceptable upgrade keysets must be specified, including the key signing
the app.  This enables key rotation in one update, but also 'locks' an app if
an incorrect upgrade keyset is specified.
-Minimal changes to existing KeySet code.

Bug: 6967056
Change-Id: Ib9bb693d4e9ea1aec375291ecdc182554890d29c
diff --git a/core/java/android/content/pm/PackageParser.java b/core/java/android/content/pm/PackageParser.java
index b40a441..f176dfb 100644
--- a/core/java/android/content/pm/PackageParser.java
+++ b/core/java/android/content/pm/PackageParser.java
@@ -828,8 +828,8 @@
                 if (pkg.mCertificates == null) {
                     pkg.mCertificates = entryCerts;
                     pkg.mSignatures = convertToSignatures(entryCerts);
-                    pkg.mSigningKeys = new ArraySet<>();
-                    for (int i = 0; i < entryCerts.length; i++) {
+                    pkg.mSigningKeys = new ArraySet<PublicKey>();
+                    for (int i=0; i < entryCerts.length; i++) {
                         pkg.mSigningKeys.add(entryCerts[i][0].getPublicKey());
                     }
                 } else {
@@ -1222,6 +1222,17 @@
                 if (parsePermissionTree(pkg, res, parser, attrs, outError) == null) {
                     return null;
                 }
+            } else if (tagName.equals("upgrade-keyset")) {
+                sa = res.obtainAttributes(attrs,
+                        com.android.internal.R.styleable.AndroidManifestUpgradeKeySet);
+                String name = sa.getNonResourceString(
+                        com.android.internal.R.styleable.AndroidManifestUpgradeKeySet_name);
+                sa.recycle();
+                if (pkg.mUpgradeKeySets == null) {
+                    pkg.mUpgradeKeySets = new ArraySet<String>();
+                }
+                pkg.mUpgradeKeySets.add(name);
+                XmlUtils.skipCurrentTag(parser);
             } else if (tagName.equals("uses-permission")) {
                 if (!parseUsesPermission(pkg, res, parser, attrs, outError)) {
                     return null;
@@ -1795,7 +1806,7 @@
             }
         }
 
-        owner.mKeySetMapping = new ArrayMap<String, ArraySet<PublicKey>>();
+        owner.mKeySetMapping = new ArrayMap<String, Set<PublicKey>>();
         for (Map.Entry<PublicKey, Set<String>> e : definedKeySets.entrySet()) {
             PublicKey key = e.getKey();
             Set<String> keySetNames = e.getValue();
@@ -1803,7 +1814,7 @@
                 if (owner.mKeySetMapping.containsKey(alias)) {
                     owner.mKeySetMapping.get(alias).add(key);
                 } else {
-                    ArraySet<PublicKey> keys = new ArraySet<PublicKey>();
+                    Set<PublicKey> keys = new ArraySet<PublicKey>();
                     keys.add(key);
                     owner.mKeySetMapping.put(alias, keys);
                 }
@@ -3795,8 +3806,9 @@
         /**
          * Data used to feed the KeySetManager
          */
-        public ArraySet<PublicKey> mSigningKeys;
-        public ArrayMap<String, ArraySet<PublicKey>> mKeySetMapping;
+        public Set<PublicKey> mSigningKeys;
+        public Set<String> mUpgradeKeySets;
+        public Map<String, Set<PublicKey>> mKeySetMapping;
 
         public Package(String packageName) {
             this.packageName = packageName;
diff --git a/core/res/res/values/attrs_manifest.xml b/core/res/res/values/attrs_manifest.xml
index fc1d0df..afaf2e9 100644
--- a/core/res/res/values/attrs_manifest.xml
+++ b/core/res/res/values/attrs_manifest.xml
@@ -2019,4 +2019,10 @@
     <declare-styleable name="KeySet">
         <attr name="name" />
     </declare-styleable>
+
+    <!-- Associate declared KeySets with upgrading capability -->
+    <declare-styleable name="AndroidManifestUpgradeKeySet" parent="AndroidManifest">
+      <attr name="name" />
+    </declare-styleable>
+
 </resources>
diff --git a/core/tests/coretests/apks/keyset/Android.mk b/core/tests/coretests/apks/keyset/Android.mk
new file mode 100644
index 0000000..e44ac6c
--- /dev/null
+++ b/core/tests/coretests/apks/keyset/Android.mk
@@ -0,0 +1,91 @@
+LOCAL_PATH:= $(call my-dir)
+
+#apks signed by keyset_A
+include $(CLEAR_VARS)
+LOCAL_SRC_FILES := $(call all-subdir-java-files)
+LOCAL_PACKAGE_NAME := keyset_sa_unone
+LOCAL_CERTIFICATE := $(LOCAL_PATH)/../../certs/keyset_A
+LOCAL_MANIFEST_FILE := uNone/AndroidManifest.xml
+include $(FrameworkCoreTests_BUILD_PACKAGE)
+
+include $(CLEAR_VARS)
+LOCAL_SRC_FILES := $(call all-subdir-java-files)
+LOCAL_PACKAGE_NAME := keyset_sa_ua
+LOCAL_CERTIFICATE := $(LOCAL_PATH)/../../certs/keyset_A
+LOCAL_MANIFEST_FILE := uA/AndroidManifest.xml
+include $(FrameworkCoreTests_BUILD_PACKAGE)
+
+include $(CLEAR_VARS)
+LOCAL_SRC_FILES := $(call all-subdir-java-files)
+LOCAL_PACKAGE_NAME := keyset_sa_ub
+LOCAL_CERTIFICATE := $(LOCAL_PATH)/../../certs/keyset_A
+LOCAL_MANIFEST_FILE := uB/AndroidManifest.xml
+include $(FrameworkCoreTests_BUILD_PACKAGE)
+
+include $(CLEAR_VARS)
+LOCAL_SRC_FILES := $(call all-subdir-java-files)
+LOCAL_PACKAGE_NAME := keyset_sa_uab
+LOCAL_CERTIFICATE := $(LOCAL_PATH)/../../certs/keyset_A
+LOCAL_MANIFEST_FILE := uAB/AndroidManifest.xml
+include $(FrameworkCoreTests_BUILD_PACKAGE)
+
+include $(CLEAR_VARS)
+LOCAL_SRC_FILES := $(call all-subdir-java-files)
+LOCAL_PACKAGE_NAME := keyset_sa_ua_ub
+LOCAL_CERTIFICATE := $(LOCAL_PATH)/../../certs/keyset_A
+LOCAL_MANIFEST_FILE := uAuB/AndroidManifest.xml
+include $(FrameworkCoreTests_BUILD_PACKAGE)
+
+include $(CLEAR_VARS)
+LOCAL_SRC_FILES := $(call all-subdir-java-files)
+LOCAL_PACKAGE_NAME := keyset_permdef_sa_unone
+LOCAL_CERTIFICATE := $(LOCAL_PATH)/../../certs/keyset_A
+LOCAL_MANIFEST_FILE := permDef/AndroidManifest.xml
+include $(FrameworkCoreTests_BUILD_PACKAGE)
+
+include $(CLEAR_VARS)
+LOCAL_SRC_FILES := $(call all-subdir-java-files)
+LOCAL_PACKAGE_NAME := keyset_permuse_sa_ua_ub
+LOCAL_CERTIFICATE := $(LOCAL_PATH)/../../certs/keyset_A
+LOCAL_MANIFEST_FILE := permUse/AndroidManifest.xml
+include $(FrameworkCoreTests_BUILD_PACKAGE)
+
+#apks signed by keyset_B
+include $(CLEAR_VARS)
+LOCAL_SRC_FILES := $(call all-subdir-java-files)
+LOCAL_PACKAGE_NAME := keyset_sb_ua
+LOCAL_CERTIFICATE := $(LOCAL_PATH)/../../certs/keyset_B
+LOCAL_MANIFEST_FILE := uA/AndroidManifest.xml
+include $(FrameworkCoreTests_BUILD_PACKAGE)
+
+include $(CLEAR_VARS)
+LOCAL_SRC_FILES := $(call all-subdir-java-files)
+LOCAL_PACKAGE_NAME := keyset_sb_ub
+LOCAL_CERTIFICATE := $(LOCAL_PATH)/../../certs/keyset_B
+LOCAL_MANIFEST_FILE := uB/AndroidManifest.xml
+include $(FrameworkCoreTests_BUILD_PACKAGE)
+
+include $(CLEAR_VARS)
+LOCAL_SRC_FILES := $(call all-subdir-java-files)
+LOCAL_PACKAGE_NAME := keyset_permuse_sb_ua_ub
+LOCAL_CERTIFICATE := $(LOCAL_PATH)/../../certs/keyset_B
+LOCAL_MANIFEST_FILE := permUse/AndroidManifest.xml
+include $(FrameworkCoreTests_BUILD_PACKAGE)
+
+#apks signed by keyset_A and keyset_B
+include $(CLEAR_VARS)
+LOCAL_SRC_FILES := $(call all-subdir-java-files)
+LOCAL_PACKAGE_NAME := keyset_sab_ua
+LOCAL_CERTIFICATE := $(LOCAL_PATH)/../../certs/keyset_A
+LOCAL_ADDITIONAL_CERTIFICATES := $(LOCAL_PATH)/../../certs/keyset_B
+LOCAL_MANIFEST_FILE := uA/AndroidManifest.xml
+include $(FrameworkCoreTests_BUILD_PACKAGE)
+
+#apks signed by keyset_A and unit_test
+include $(CLEAR_VARS)
+LOCAL_SRC_FILES := $(call all-subdir-java-files)
+LOCAL_PACKAGE_NAME := keyset_sau_ub
+LOCAL_CERTIFICATE := $(LOCAL_PATH)/../../certs/keyset_A
+LOCAL_ADDITIONAL_CERTIFICATES := $(LOCAL_PATH)/../../certs/keyset_B
+LOCAL_MANIFEST_FILE := uB/AndroidManifest.xml
+include $(FrameworkCoreTests_BUILD_PACKAGE)
\ No newline at end of file
diff --git a/core/tests/coretests/apks/keyset/permDef/AndroidManifest.xml b/core/tests/coretests/apks/keyset/permDef/AndroidManifest.xml
new file mode 100644
index 0000000..8f7ad4a
--- /dev/null
+++ b/core/tests/coretests/apks/keyset/permDef/AndroidManifest.xml
@@ -0,0 +1,24 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!-- Copyright (C) 2010 The Android Open Source Project
+
+     Licensed under the Apache License, Version 2.0 (the "License");
+     you may not use this file except in compliance with the License.
+     You may obtain a copy of the License at
+
+          http://www.apache.org/licenses/LICENSE-2.0
+
+     Unless required by applicable law or agreed to in writing, software
+     distributed under the License is distributed on an "AS IS" BASIS,
+     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+     See the License for the specific language governing permissions and
+     limitations under the License.
+-->
+<manifest xmlns:android="http://schemas.android.com/apk/res/android"
+        package="com.android.frameworks.coretests.keysets_permdef">
+    <application android:hasCode="false">
+    </application>
+    <permission android:description="@string/keyset_perm_desc"
+                android:label="@string/keyset_perm_label"
+                android:name="com.android.frameworks.coretests.keysets_permdef.keyset_perm"
+                android:protectionLevel="signature" />
+</manifest>
diff --git a/core/tests/coretests/apks/keyset/permUse/AndroidManifest.xml b/core/tests/coretests/apks/keyset/permUse/AndroidManifest.xml
new file mode 100644
index 0000000..41a2974
--- /dev/null
+++ b/core/tests/coretests/apks/keyset/permUse/AndroidManifest.xml
@@ -0,0 +1,31 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!-- Copyright (C) 2010 The Android Open Source Project
+
+     Licensed under the Apache License, Version 2.0 (the "License");
+     you may not use this file except in compliance with the License.
+     You may obtain a copy of the License at
+
+          http://www.apache.org/licenses/LICENSE-2.0
+
+     Unless required by applicable law or agreed to in writing, software
+     distributed under the License is distributed on an "AS IS" BASIS,
+     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+     See the License for the specific language governing permissions and
+     limitations under the License.
+-->
+<manifest xmlns:android="http://schemas.android.com/apk/res/android"
+        package="com.android.frameworks.coretests.keysets">
+    <application android:hasCode="false">
+    </application>
+    <uses-permission android:name="com.android.frameworks.coretests.keysets_permdef.keyset_perm" />
+    <keys>
+      <publicKey android:value="MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAJoN1Nsgqf0V4C/bbN8wo8O2X/S5D76+5Mb9mlIsHkUTUTbHCNk+LxHIUYLm89YbP9zImrV0bUHLUAZUyoMUCiMCAwEAAQ==">
+        <keyset android:name="A" />
+      </publicKey>
+      <publicKey android:value="MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAMTfQsY8UuXiXmvw/y7Tpr7HoyfAC0nE/8Qdk3ZtEr9asa5qqP0F6xzCI1PGVFV+WLVRwm6FdB9StENL5EKyQFcCAwEAAQ==">
+        <keyset android:name="B" />
+      </publicKey>
+    </keys>
+    <upgrade-keyset android:name="A"/>
+    <upgrade-keyset android:name="B"/>
+</manifest>
diff --git a/core/tests/coretests/apks/keyset/res/values/strings.xml b/core/tests/coretests/apks/keyset/res/values/strings.xml
new file mode 100644
index 0000000..ff99ffa
--- /dev/null
+++ b/core/tests/coretests/apks/keyset/res/values/strings.xml
@@ -0,0 +1,8 @@
+<?xml version="1.0" encoding="utf-8"?>
+
+<!-- Just need this dummy file to have something to build. -->
+<resources xmlns:xliff="urn:oasis:names:tc:xliff:document:1.2">
+  <string name="dummy">dummy</string>
+  <string name="keyset_perm_desc">keyset_perm_description</string>
+  <string name="keyset_perm_label">keyset_perm_label</string>
+</resources>
diff --git a/core/tests/coretests/apks/keyset/uA/AndroidManifest.xml b/core/tests/coretests/apks/keyset/uA/AndroidManifest.xml
new file mode 100644
index 0000000..87c420e
--- /dev/null
+++ b/core/tests/coretests/apks/keyset/uA/AndroidManifest.xml
@@ -0,0 +1,26 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!-- Copyright (C) 2010 The Android Open Source Project
+
+     Licensed under the Apache License, Version 2.0 (the "License");
+     you may not use this file except in compliance with the License.
+     You may obtain a copy of the License at
+
+          http://www.apache.org/licenses/LICENSE-2.0
+
+     Unless required by applicable law or agreed to in writing, software
+     distributed under the License is distributed on an "AS IS" BASIS,
+     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+     See the License for the specific language governing permissions and
+     limitations under the License.
+-->
+<manifest xmlns:android="http://schemas.android.com/apk/res/android"
+        package="com.android.frameworks.coretests.keysets">
+    <application android:hasCode="false">
+    </application>
+    <keys>
+      <publicKey android:value="MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAJoN1Nsgqf0V4C/bbN8wo8O2X/S5D76+5Mb9mlIsHkUTUTbHCNk+LxHIUYLm89YbP9zImrV0bUHLUAZUyoMUCiMCAwEAAQ==">
+        <keyset android:name="A" />
+      </publicKey>
+    </keys>
+    <upgrade-keyset android:name="A"/>
+</manifest>
diff --git a/core/tests/coretests/apks/keyset/uAB/AndroidManifest.xml b/core/tests/coretests/apks/keyset/uAB/AndroidManifest.xml
new file mode 100644
index 0000000..a65f085
--- /dev/null
+++ b/core/tests/coretests/apks/keyset/uAB/AndroidManifest.xml
@@ -0,0 +1,29 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!-- Copyright (C) 2010 The Android Open Source Project
+
+     Licensed under the Apache License, Version 2.0 (the "License");
+     you may not use this file except in compliance with the License.
+     You may obtain a copy of the License at
+
+          http://www.apache.org/licenses/LICENSE-2.0
+
+     Unless required by applicable law or agreed to in writing, software
+     distributed under the License is distributed on an "AS IS" BASIS,
+     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+     See the License for the specific language governing permissions and
+     limitations under the License.
+-->
+<manifest xmlns:android="http://schemas.android.com/apk/res/android"
+        package="com.android.frameworks.coretests.keysets">
+    <application android:hasCode="false">
+    </application>
+    <keys>
+      <publicKey android:value="MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAJoN1Nsgqf0V4C/bbN8wo8O2X/S5D76+5Mb9mlIsHkUTUTbHCNk+LxHIUYLm89YbP9zImrV0bUHLUAZUyoMUCiMCAwEAAQ==">
+        <keyset android:name="AB" />
+      </publicKey>
+      <publicKey android:value="MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAMTfQsY8UuXiXmvw/y7Tpr7HoyfAC0nE/8Qdk3ZtEr9asa5qqP0F6xzCI1PGVFV+WLVRwm6FdB9StENL5EKyQFcCAwEAAQ==">
+        <keyset android:name="AB" />
+      </publicKey>
+    </keys>
+    <upgrade-keyset android:name="AB"/>
+</manifest>
diff --git a/core/tests/coretests/apks/keyset/uAuB/AndroidManifest.xml b/core/tests/coretests/apks/keyset/uAuB/AndroidManifest.xml
new file mode 100644
index 0000000..5b0b864
--- /dev/null
+++ b/core/tests/coretests/apks/keyset/uAuB/AndroidManifest.xml
@@ -0,0 +1,30 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!-- Copyright (C) 2010 The Android Open Source Project
+
+     Licensed under the Apache License, Version 2.0 (the "License");
+     you may not use this file except in compliance with the License.
+     You may obtain a copy of the License at
+
+          http://www.apache.org/licenses/LICENSE-2.0
+
+     Unless required by applicable law or agreed to in writing, software
+     distributed under the License is distributed on an "AS IS" BASIS,
+     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+     See the License for the specific language governing permissions and
+     limitations under the License.
+-->
+<manifest xmlns:android="http://schemas.android.com/apk/res/android"
+        package="com.android.frameworks.coretests.keysets">
+    <application android:hasCode="false">
+    </application>
+    <keys>
+      <publicKey android:value="MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAJoN1Nsgqf0V4C/bbN8wo8O2X/S5D76+5Mb9mlIsHkUTUTbHCNk+LxHIUYLm89YbP9zImrV0bUHLUAZUyoMUCiMCAwEAAQ==">
+        <keyset android:name="A" />
+      </publicKey>
+      <publicKey android:value="MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAMTfQsY8UuXiXmvw/y7Tpr7HoyfAC0nE/8Qdk3ZtEr9asa5qqP0F6xzCI1PGVFV+WLVRwm6FdB9StENL5EKyQFcCAwEAAQ==">
+        <keyset android:name="B" />
+      </publicKey>
+    </keys>
+    <upgrade-keyset android:name="A"/>
+    <upgrade-keyset android:name="B"/>
+</manifest>
diff --git a/core/tests/coretests/apks/keyset/uB/AndroidManifest.xml b/core/tests/coretests/apks/keyset/uB/AndroidManifest.xml
new file mode 100644
index 0000000..9b89961
--- /dev/null
+++ b/core/tests/coretests/apks/keyset/uB/AndroidManifest.xml
@@ -0,0 +1,26 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!-- Copyright (C) 2010 The Android Open Source Project
+
+     Licensed under the Apache License, Version 2.0 (the "License");
+     you may not use this file except in compliance with the License.
+     You may obtain a copy of the License at
+
+          http://www.apache.org/licenses/LICENSE-2.0
+
+     Unless required by applicable law or agreed to in writing, software
+     distributed under the License is distributed on an "AS IS" BASIS,
+     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+     See the License for the specific language governing permissions and
+     limitations under the License.
+-->
+<manifest xmlns:android="http://schemas.android.com/apk/res/android"
+        package="com.android.frameworks.coretests.keysets">
+    <application android:hasCode="false">
+    </application>
+    <keys>
+      <publicKey android:value="MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAMTfQsY8UuXiXmvw/y7Tpr7HoyfAC0nE/8Qdk3ZtEr9asa5qqP0F6xzCI1PGVFV+WLVRwm6FdB9StENL5EKyQFcCAwEAAQ==">
+        <keyset android:name="B" />
+      </publicKey>
+    </keys>
+    <upgrade-keyset android:name="B"/>
+</manifest>
diff --git a/core/tests/coretests/apks/keyset/uNone/AndroidManifest.xml b/core/tests/coretests/apks/keyset/uNone/AndroidManifest.xml
new file mode 100644
index 0000000..9c9ef2b
--- /dev/null
+++ b/core/tests/coretests/apks/keyset/uNone/AndroidManifest.xml
@@ -0,0 +1,20 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!-- Copyright (C) 2010 The Android Open Source Project
+
+     Licensed under the Apache License, Version 2.0 (the "License");
+     you may not use this file except in compliance with the License.
+     You may obtain a copy of the License at
+
+          http://www.apache.org/licenses/LICENSE-2.0
+
+     Unless required by applicable law or agreed to in writing, software
+     distributed under the License is distributed on an "AS IS" BASIS,
+     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+     See the License for the specific language governing permissions and
+     limitations under the License.
+-->
+<manifest xmlns:android="http://schemas.android.com/apk/res/android"
+        package="com.android.frameworks.coretests.keysets">
+    <application android:hasCode="false">
+    </application>
+</manifest>
diff --git a/core/tests/coretests/certs/keyset_A.pk8 b/core/tests/coretests/certs/keyset_A.pk8
new file mode 100644
index 0000000..3976b94
--- /dev/null
+++ b/core/tests/coretests/certs/keyset_A.pk8
Binary files differ
diff --git a/core/tests/coretests/certs/keyset_A.x509.pem b/core/tests/coretests/certs/keyset_A.x509.pem
new file mode 100644
index 0000000..0fe334e
--- /dev/null
+++ b/core/tests/coretests/certs/keyset_A.x509.pem
@@ -0,0 +1,14 @@
+-----BEGIN CERTIFICATE-----
+MIICKjCCAdQCCQCpDXPnNpO5UjANBgkqhkiG9w0BAQUFADCBmzELMAkGA1UEBhMC
+VVMxEzARBgNVBAgTCkNhbGlmb3JuaWExFjAUBgNVBAcTDU1vdW50YWluIFZpZXcx
+DzANBgNVBAoTBkdvb2dsZTEQMA4GA1UECxMHQW5kcm9pZDEYMBYGA1UEAxMPd3d3
+LmV4YW1wbGUuY29tMSIwIAYJKoZIhvcNAQkBFhNkY2FzaG1hbkBnb29nbGUuY29t
+MB4XDTE0MDQyMTE4MTkwM1oXDTE3MDQyMDE4MTkwM1owgZsxCzAJBgNVBAYTAlVT
+MRMwEQYDVQQIEwpDYWxpZm9ybmlhMRYwFAYDVQQHEw1Nb3VudGFpbiBWaWV3MQ8w
+DQYDVQQKEwZHb29nbGUxEDAOBgNVBAsTB0FuZHJvaWQxGDAWBgNVBAMTD3d3dy5l
+eGFtcGxlLmNvbTEiMCAGCSqGSIb3DQEJARYTZGNhc2htYW5AZ29vZ2xlLmNvbTBc
+MA0GCSqGSIb3DQEBAQUAA0sAMEgCQQCaDdTbIKn9FeAv22zfMKPDtl/0uQ++vuTG
+/ZpSLB5FE1E2xwjZPi8RyFGC5vPWGz/cyJq1dG1By1AGVMqDFAojAgMBAAEwDQYJ
+KoZIhvcNAQEFBQADQQCPTVDKxVZpxFH6Nm7sxpRplLzxbs/xyGELLIjEBVrgB0CM
+HAxFpPRHDSFpTxGG2mBCSrf+lD2Bf+WiIojx+RLY
+-----END CERTIFICATE-----
diff --git a/core/tests/coretests/certs/keyset_B.pk8 b/core/tests/coretests/certs/keyset_B.pk8
new file mode 100644
index 0000000..a44ebb3
--- /dev/null
+++ b/core/tests/coretests/certs/keyset_B.pk8
Binary files differ
diff --git a/core/tests/coretests/certs/keyset_B.x509.pem b/core/tests/coretests/certs/keyset_B.x509.pem
new file mode 100644
index 0000000..2806de5
--- /dev/null
+++ b/core/tests/coretests/certs/keyset_B.x509.pem
@@ -0,0 +1,14 @@
+-----BEGIN CERTIFICATE-----
+MIICKjCCAdQCCQC+5GnAgmYS6DANBgkqhkiG9w0BAQUFADCBmzELMAkGA1UEBhMC
+VVMxEzARBgNVBAgTCkNhbGlmb3JuaWExFjAUBgNVBAcTDU1vdW50YWluIFZpZXcx
+DzANBgNVBAoTBkdvb2dsZTEQMA4GA1UECxMHQW5kcm9pZDEYMBYGA1UEAxMPd3d3
+LmV4YW1wbGUuY29tMSIwIAYJKoZIhvcNAQkBFhNkY2FzaG1hbkBnb29nbGUuY29t
+MB4XDTE0MDQyMTE4MjczM1oXDTE3MDQyMDE4MjczM1owgZsxCzAJBgNVBAYTAlVT
+MRMwEQYDVQQIEwpDYWxpZm9ybmlhMRYwFAYDVQQHEw1Nb3VudGFpbiBWaWV3MQ8w
+DQYDVQQKEwZHb29nbGUxEDAOBgNVBAsTB0FuZHJvaWQxGDAWBgNVBAMTD3d3dy5l
+eGFtcGxlLmNvbTEiMCAGCSqGSIb3DQEJARYTZGNhc2htYW5AZ29vZ2xlLmNvbTBc
+MA0GCSqGSIb3DQEBAQUAA0sAMEgCQQDE30LGPFLl4l5r8P8u06a+x6MnwAtJxP/E
+HZN2bRK/WrGuaqj9BescwiNTxlRVfli1UcJuhXQfUrRDS+RCskBXAgMBAAEwDQYJ
+KoZIhvcNAQEFBQADQQCYYyur2/sMB88MOhQE8RHNmdO0zEQYAz66z3ctTNqiNsbK
+T9iKj0CT3cjqgfN5ex4onhnoIIPtON7DIHFWke5x
+-----END CERTIFICATE-----
diff --git a/core/tests/coretests/src/android/content/pm/PackageManagerTests.java b/core/tests/coretests/src/android/content/pm/PackageManagerTests.java
index 7f41ac1c..0244425 100644
--- a/core/tests/coretests/src/android/content/pm/PackageManagerTests.java
+++ b/core/tests/coretests/src/android/content/pm/PackageManagerTests.java
@@ -61,7 +61,10 @@
 import java.io.File;
 import java.io.IOException;
 import java.io.InputStream;
+import java.util.HashSet;
 import java.util.List;
+import java.util.Set;
+
 import java.util.concurrent.CountDownLatch;
 import java.util.concurrent.TimeUnit;
 
@@ -3069,6 +3072,262 @@
     }
 
     /**
+     * The following tests are related to testing KeySets-based key rotation
+     */
+    /*
+     * Check if an apk which does not specify an upgrade-keyset may be upgraded
+     * by an apk which does
+     */
+    public void testNoKSToUpgradeKS() throws Exception {
+        replaceCerts(R.raw.keyset_sa_unone, R.raw.keyset_sa_ua, true, false, -1);
+    }
+
+    /*
+     * Check if an apk which does specify an upgrade-keyset may be downgraded to
+     * an apk which does not
+     */
+    public void testUpgradeKSToNoKS() throws Exception {
+        replaceCerts(R.raw.keyset_sa_ua, R.raw.keyset_sa_unone, true, false, -1);
+    }
+
+    /*
+     * Check if an apk signed by a key other than the upgrade keyset can update
+     * an app
+     */
+    public void testUpgradeKSWithWrongKey() throws Exception {
+        replaceCerts(R.raw.keyset_sa_ua, R.raw.keyset_sb_ua, true, true,
+                PackageManager.INSTALL_PARSE_FAILED_INCONSISTENT_CERTIFICATES);
+    }
+
+    /*
+     * Check if an apk signed by its signing key, which is not an upgrade key,
+     * can upgrade an app.
+     */
+    public void testUpgradeKSWithWrongSigningKey() throws Exception {
+        replaceCerts(R.raw.keyset_sa_ub, R.raw.keyset_sa_ub, true, true,
+                PackageManager.INSTALL_PARSE_FAILED_INCONSISTENT_CERTIFICATES);
+    }
+
+    /*
+     * Check if an apk signed by its upgrade key, which is not its signing key,
+     * can upgrade an app.
+     */
+    public void testUpgradeKSWithUpgradeKey() throws Exception {
+        replaceCerts(R.raw.keyset_sa_ub, R.raw.keyset_sb_ub, true, false, -1);
+    }
+    /*
+     * Check if an apk signed by its upgrade key, which is its signing key, can
+     * upgrade an app.
+     */
+    public void testUpgradeKSWithSigningUpgradeKey() throws Exception {
+        replaceCerts(R.raw.keyset_sa_ua, R.raw.keyset_sa_ua, true, false, -1);
+    }
+
+    /*
+     * Check if an apk signed by multiple keys, one of which is its upgrade key,
+     * can upgrade an app.
+     */
+    public void testMultipleUpgradeKSWithUpgradeKey() throws Exception {
+        replaceCerts(R.raw.keyset_sa_ua, R.raw.keyset_sab_ua, true, false, -1);
+    }
+
+    /*
+     * Check if an apk signed by multiple keys, one of which is its signing key,
+     * but none of which is an upgrade key, can upgrade an app.
+     */
+    public void testMultipleUpgradeKSWithSigningKey() throws Exception {
+        replaceCerts(R.raw.keyset_sau_ub, R.raw.keyset_sa_ua, true, true,
+                PackageManager.INSTALL_PARSE_FAILED_INCONSISTENT_CERTIFICATES);
+    }
+
+    /*
+     * Check if an apk which defines multiple (two) upgrade keysets is
+     * upgrade-able by either.
+     */
+    public void testUpgradeKSWithMultipleUpgradeKeySets() throws Exception {
+        replaceCerts(R.raw.keyset_sa_ua_ub, R.raw.keyset_sa_ua, true, false, -1);
+        replaceCerts(R.raw.keyset_sa_ua_ub, R.raw.keyset_sb_ub, true, false, -1);
+    }
+
+    /*
+     * Check if an apk's sigs are changed after upgrading with a non-signing
+     * key.
+     *
+     * TODO: consider checking against hard-coded Signatures in the Sig-tests
+     */
+    public void testSigChangeAfterUpgrade() throws Exception {
+        // install original apk and grab sigs
+        installFromRawResource("tmp.apk", R.raw.keyset_sa_ub,
+                0, false, false, -1, PackageInfo.INSTALL_LOCATION_UNSPECIFIED);
+        PackageManager pm = getPm();
+        String pkgName = "com.android.frameworks.coretests.keysets";
+        PackageInfo pi = pm.getPackageInfo(pkgName, PackageManager.GET_SIGNATURES);
+        assertTrue("Package should only have one signature, sig A",
+                pi.signatures.length == 1);
+        String sigBefore = pi.signatures[0].toCharsString();
+        // install apk signed by different upgrade KeySet
+        installFromRawResource("tmp2.apk", R.raw.keyset_sb_ub,
+                PackageManager.INSTALL_REPLACE_EXISTING, false, false, -1,
+                PackageInfo.INSTALL_LOCATION_UNSPECIFIED);
+        pi = pm.getPackageInfo(pkgName, PackageManager.GET_SIGNATURES);
+        assertTrue("Package should only have one signature, sig B",
+                pi.signatures.length == 1);
+        String sigAfter = pi.signatures[0].toCharsString();
+        assertFalse("Package signatures did not change after upgrade!",
+                sigBefore.equals(sigAfter));
+        cleanUpInstall(pkgName);
+    }
+
+    /*
+     * Check if an apk's sig is the same  after upgrading with a signing
+     * key.
+     */
+    public void testSigSameAfterUpgrade() throws Exception {
+        // install original apk and grab sigs
+        installFromRawResource("tmp.apk", R.raw.keyset_sa_ua,
+                0, false, false, -1, PackageInfo.INSTALL_LOCATION_UNSPECIFIED);
+        PackageManager pm = getPm();
+        String pkgName = "com.android.frameworks.coretests.keysets";
+        PackageInfo pi = pm.getPackageInfo(pkgName, PackageManager.GET_SIGNATURES);
+        assertTrue("Package should only have one signature, sig A",
+                pi.signatures.length == 1);
+        String sigBefore = pi.signatures[0].toCharsString();
+        // install apk signed by same upgrade KeySet
+        installFromRawResource("tmp2.apk", R.raw.keyset_sa_ua,
+                PackageManager.INSTALL_REPLACE_EXISTING, false, false, -1,
+                PackageInfo.INSTALL_LOCATION_UNSPECIFIED);
+        pi = pm.getPackageInfo(pkgName, PackageManager.GET_SIGNATURES);
+        assertTrue("Package should only have one signature, sig A",
+                pi.signatures.length == 1);
+        String sigAfter = pi.signatures[0].toCharsString();
+        assertTrue("Package signatures changed after upgrade!",
+                sigBefore.equals(sigAfter));
+        cleanUpInstall(pkgName);
+    }
+
+    /*
+     * Check if an apk's sigs are the same after upgrading with an app with
+     * a subset of the original signing keys.
+     */
+    public void testSigRemovedAfterUpgrade() throws Exception {
+        // install original apk and grab sigs
+        installFromRawResource("tmp.apk", R.raw.keyset_sab_ua,
+                0, false, false, -1, PackageInfo.INSTALL_LOCATION_UNSPECIFIED);
+        PackageManager pm = getPm();
+        String pkgName = "com.android.frameworks.coretests.keysets";
+        PackageInfo pi = pm.getPackageInfo(pkgName, PackageManager.GET_SIGNATURES);
+        assertTrue("Package should have two signatures, sig A and sig B",
+                pi.signatures.length == 2);
+        Set<String> sigsBefore = new HashSet<String>();
+        for (int i = 0; i < pi.signatures.length; i++) {
+            sigsBefore.add(pi.signatures[i].toCharsString());
+        }
+        // install apk signed subset upgrade KeySet
+        installFromRawResource("tmp2.apk", R.raw.keyset_sa_ua,
+                PackageManager.INSTALL_REPLACE_EXISTING, false, false, -1,
+                PackageInfo.INSTALL_LOCATION_UNSPECIFIED);
+        pi = pm.getPackageInfo(pkgName, PackageManager.GET_SIGNATURES);
+        assertTrue("Package should only have one signature, sig A",
+                pi.signatures.length == 1);
+        String sigAfter = pi.signatures[0].toCharsString();
+        assertTrue("Original package signatures did not contain new sig",
+                sigsBefore.contains(sigAfter));
+        cleanUpInstall(pkgName);
+    }
+
+    /*
+     * Check if an apk's sigs are added to after upgrading with an app with
+     * a superset of the original signing keys.
+     */
+    public void testSigAddedAfterUpgrade() throws Exception {
+        // install original apk and grab sigs
+        installFromRawResource("tmp.apk", R.raw.keyset_sa_ua,
+                0, false, false, -1, PackageInfo.INSTALL_LOCATION_UNSPECIFIED);
+        PackageManager pm = getPm();
+        String pkgName = "com.android.frameworks.coretests.keysets";
+        PackageInfo pi = pm.getPackageInfo(pkgName, PackageManager.GET_SIGNATURES);
+        assertTrue("Package should only have one signature, sig A",
+                pi.signatures.length == 1);
+        String sigBefore = pi.signatures[0].toCharsString();
+        // install apk signed subset upgrade KeySet
+        installFromRawResource("tmp2.apk", R.raw.keyset_sab_ua,
+                PackageManager.INSTALL_REPLACE_EXISTING, false, false, -1,
+                PackageInfo.INSTALL_LOCATION_UNSPECIFIED);
+        pi = pm.getPackageInfo(pkgName, PackageManager.GET_SIGNATURES);
+        assertTrue("Package should have two signatures, sig A and sig B",
+                pi.signatures.length == 2);
+        Set<String> sigsAfter = new HashSet<String>();
+        for (int i = 0; i < pi.signatures.length; i++) {
+            sigsAfter.add(pi.signatures[i].toCharsString());
+        }
+        assertTrue("Package signatures did not change after upgrade!",
+                sigsAfter.contains(sigBefore));
+        cleanUpInstall(pkgName);
+    }
+
+    /*
+     * Check if an apk gains signature-level permission after changing to the a
+     * new signature, for which a permission should be granted.
+     */
+    public void testUpgradeSigPermGained() throws Exception {
+        // install apk which defines permission
+        installFromRawResource("permDef.apk", R.raw.keyset_permdef_sa_unone,
+                0, false, false, -1, PackageInfo.INSTALL_LOCATION_UNSPECIFIED);
+        // install apk which uses permission but does not have sig
+        installFromRawResource("permUse.apk", R.raw.keyset_permuse_sb_ua_ub,
+                0, false, false, -1, PackageInfo.INSTALL_LOCATION_UNSPECIFIED);
+        // verify that package does not have perm before
+        PackageManager pm = getPm();
+        String permPkgName = "com.android.frameworks.coretests.keysets_permdef";
+        String pkgName = "com.android.frameworks.coretests.keysets";
+        String permName = "com.android.frameworks.coretests.keysets_permdef.keyset_perm";
+        assertFalse("keyset permission granted to app without same signature!",
+                    pm.checkPermission(permName, pkgName)
+                    == PackageManager.PERMISSION_GRANTED);
+        // upgrade to apk with perm signature
+        installFromRawResource("permUse2.apk", R.raw.keyset_permuse_sa_ua_ub,
+                PackageManager.INSTALL_REPLACE_EXISTING, false, false, -1,
+                PackageInfo.INSTALL_LOCATION_UNSPECIFIED);
+        assertTrue("keyset permission not granted to app after upgrade to same sig",
+                    pm.checkPermission(permName, pkgName)
+                    == PackageManager.PERMISSION_GRANTED);
+        cleanUpInstall(permPkgName);
+        cleanUpInstall(pkgName);
+    }
+
+    /*
+     * Check if an apk loses signature-level permission after changing to the a
+     * new signature, from one which a permission should be granted.
+     */
+    public void testUpgradeSigPermLost() throws Exception {
+        // install apk which defines permission
+        installFromRawResource("permDef.apk", R.raw.keyset_permdef_sa_unone,
+                0, false, false, -1, PackageInfo.INSTALL_LOCATION_UNSPECIFIED);
+        // install apk which uses permission, signed by same sig
+        installFromRawResource("permUse.apk", R.raw.keyset_permuse_sa_ua_ub,
+                0, false, false, -1, PackageInfo.INSTALL_LOCATION_UNSPECIFIED);
+        // verify that package does not have perm before
+        PackageManager pm = getPm();
+        String permPkgName = "com.android.frameworks.coretests.keysets_permdef";
+        String pkgName = "com.android.frameworks.coretests.keysets";
+        String permName = "com.android.frameworks.coretests.keysets_permdef.keyset_perm";
+        assertTrue("keyset permission not granted to app with same sig",
+                    pm.checkPermission(permName, pkgName)
+                    == PackageManager.PERMISSION_GRANTED);
+        // upgrade to apk without perm signature
+        installFromRawResource("permUse2.apk", R.raw.keyset_permuse_sb_ua_ub,
+                PackageManager.INSTALL_REPLACE_EXISTING, false, false, -1,
+                PackageInfo.INSTALL_LOCATION_UNSPECIFIED);
+
+        assertFalse("keyset permission not revoked from app which upgraded to a "
+                    + "different signature",
+                    pm.checkPermission(permName, pkgName)
+                    == PackageManager.PERMISSION_GRANTED);
+        cleanUpInstall(permPkgName);
+        cleanUpInstall(pkgName);
+    }
+
+    /**
      * The following tests are related to testing the checkSignatures api.
      */
     private void checkSignatures(int apk1, int apk2, int expMatchResult) throws Exception {
diff --git a/services/core/java/com/android/server/pm/KeySetManager.java b/services/core/java/com/android/server/pm/KeySetManagerService.java
similarity index 69%
rename from services/core/java/com/android/server/pm/KeySetManager.java
rename to services/core/java/com/android/server/pm/KeySetManagerService.java
index 1056cd0..96e8f30 100644
--- a/services/core/java/com/android/server/pm/KeySetManager.java
+++ b/services/core/java/com/android/server/pm/KeySetManagerService.java
@@ -19,13 +19,14 @@
 import android.content.pm.KeySet;
 import android.content.pm.PackageParser;
 import android.os.Binder;
+import android.util.ArraySet;
 import android.util.Base64;
+import android.util.Slog;
 import android.util.LongSparseArray;
 
 import java.io.IOException;
 import java.io.PrintWriter;
 import java.security.PublicKey;
-import java.util.HashSet;
 import java.util.Map;
 import java.util.Set;
 
@@ -36,15 +37,20 @@
 /*
  * Manages system-wide KeySet state.
  */
-public class KeySetManager {
+public class KeySetManagerService {
 
-    static final String TAG = "KeySetManager";
+    static final String TAG = "KeySetManagerService";
+
+    /* original keysets implementation had no versioning info, so this is the first */
+    public static final int FIRST_VERSION = 1;
+
+    public static final int CURRENT_VERSION = FIRST_VERSION;
 
     /** Sentinel value returned when a {@code KeySet} is not found. */
     public static final long KEYSET_NOT_FOUND = -1;
 
     /** Sentinel value returned when public key is not found. */
-    private static final long PUBLIC_KEY_NOT_FOUND = -1;
+    protected static final long PUBLIC_KEY_NOT_FOUND = -1;
 
     private final Object mLockObject = new Object();
 
@@ -52,7 +58,7 @@
 
     private final LongSparseArray<PublicKey> mPublicKeys;
 
-    private final LongSparseArray<Set<Long>> mKeySetMapping;
+    protected final LongSparseArray<Set<Long>> mKeySetMapping;
 
     private final Map<String, PackageSetting> mPackages;
 
@@ -60,7 +66,7 @@
 
     private static long lastIssuedKeyId = 0;
 
-    public KeySetManager(Map<String, PackageSetting> packages) {
+    public KeySetManagerService(Map<String, PackageSetting> packages) {
         mKeySets = new LongSparseArray<KeySet>();
         mPublicKeys = new LongSparseArray<PublicKey>();
         mKeySetMapping = new LongSparseArray<Set<Long>>();
@@ -100,28 +106,48 @@
     public void addDefinedKeySetToPackage(String packageName,
             Set<PublicKey> keys, String alias) {
         if ((packageName == null) || (keys == null) || (alias == null)) {
-            //Log.d(TAG, "Got null argument for a defined keyset, ignoring!");
+            Slog.w(TAG, "Got null argument for a defined keyset, ignoring!");
             return;
         }
         synchronized (mLockObject) {
-            KeySet ks = addKeySetLocked(keys);
             PackageSetting pkg = mPackages.get(packageName);
             if (pkg == null) {
                 throw new NullPointerException("Unknown package");
             }
+            // Add to KeySets, then to package
+            KeySet ks = addKeySetLocked(keys);
             long id = getIdByKeySetLocked(ks);
             pkg.keySetData.addDefinedKeySet(id, alias);
         }
     }
 
     /**
+     * This informs the system that the given package has defined a KeySet
+     * alias in its manifest to be an upgradeKeySet.  This must be called
+     * after all of the defined KeySets have been added.
+     */
+    public void addUpgradeKeySetToPackage(String packageName, String alias) {
+        if ((packageName == null) || (alias == null)) {
+            Slog.w(TAG, "Got null argument for a defined keyset, ignoring!");
+            return;
+        }
+        synchronized (mLockObject) {
+            PackageSetting pkg = mPackages.get(packageName);
+            if (pkg == null) {
+                throw new NullPointerException("Unknown package");
+            }
+            pkg.keySetData.addUpgradeKeySet(alias);
+        }
+    }
+
+    /**
      * Similar to the above, this informs the system that the given package
      * was signed by the provided KeySet.
      */
     public void addSigningKeySetToPackage(String packageName,
             Set<PublicKey> signingKeys) {
         if ((packageName == null) || (signingKeys == null)) {
-            //Log.d(TAG, "Got null argument for a signing keyset, ignoring!");
+            Slog.w(TAG, "Got null argument for a signing keyset, ignoring!");
             return;
         }
         synchronized (mLockObject) {
@@ -138,13 +164,13 @@
             if (pkg == null) {
                 throw new NullPointerException("No such package!");
             }
-            pkg.keySetData.addSigningKeySet(id);
-
-            // for each KeySet the package defines which is a subset of
-            // the one above, add the KeySet id to the package's signing KeySets
-            for (Long keySetID : pkg.keySetData.getDefinedKeySets()) {
+            pkg.keySetData.setProperSigningKeySet(id);
+            // for each KeySet which is a subset of the one above, add the
+            // KeySet id to the package's signing KeySets
+            for (int keySetIndex = 0; keySetIndex < mKeySets.size(); keySetIndex++) {
+                long keySetID = mKeySets.keyAt(keySetIndex);
                 Set<Long> definedKeys = mKeySetMapping.get(keySetID);
-                if (publicKeyIds.contains(definedKeys)) {
+                if (publicKeyIds.containsAll(definedKeys)) {
                     pkg.keySetData.addSigningKeySet(keySetID);
                 }
             }
@@ -184,10 +210,10 @@
     }
 
     /**
-     * Fetches the KeySet that a given package refers to by the provided alias.
+     * Fetches the {@link KeySet} that a given package refers to by the provided alias.
      *
-     * If the package isn't known to us, throws an IllegalArgumentException.
-     * Returns null if the alias isn't known to us.
+     * @throws IllegalArgumentException if the package has no keyset data.
+     * @throws NullPointerException if the package is unknown.
      */
     public KeySet getKeySetByAliasAndPackageName(String packageName, String alias) {
         synchronized (mLockObject) {
@@ -204,12 +230,59 @@
     }
 
     /**
+     * Fetches the {@link PublicKey public keys} which belong to the specified
+     * KeySet id.
+     *
+     * Returns {@code null} if the identifier doesn't
+     * identify a {@link KeySet}.
+     */
+    public Set<PublicKey> getPublicKeysFromKeySet(long id) {
+        synchronized (mLockObject) {
+            if(mKeySetMapping.get(id) == null) {
+                return null;
+            }
+            Set<PublicKey> mPubKeys = new ArraySet<PublicKey>();
+            for (long pkId : mKeySetMapping.get(id)) {
+                mPubKeys.add(mPublicKeys.get(pkId));
+            }
+            return mPubKeys;
+        }
+    }
+
+    /**
      * Fetches all the known {@link KeySet KeySets} that signed the given
-     * package. Returns {@code null} if package is unknown.
+     * package.
+     *
+     * @throws IllegalArgumentException if the package has no keyset data.
+     * @throws NullPointerException if the package is unknown.
      */
     public Set<KeySet> getSigningKeySetsByPackageName(String packageName) {
         synchronized (mLockObject) {
-            Set<KeySet> signingKeySets = new HashSet<KeySet>();
+            Set<KeySet> signingKeySets = new ArraySet<KeySet>();
+            PackageSetting p = mPackages.get(packageName);
+            if (p == null) {
+                throw new NullPointerException("Unknown package");
+            }
+            if (p.keySetData == null || p.keySetData.getSigningKeySets() == null) {
+                throw new IllegalArgumentException("Package has no keySet data");
+            }
+            for (long l : p.keySetData.getSigningKeySets()) {
+                signingKeySets.add(mKeySets.get(l));
+            }
+            return signingKeySets;
+        }
+    }
+
+    /**
+     * Fetches all the known {@link KeySet KeySets} that may upgrade the given
+     * package.
+     *
+     * @throws IllegalArgumentException if the package has no keyset data.
+     * @throws NullPointerException if the package is unknown.
+     */
+    public Set<KeySet> getUpgradeKeySetsByPackageName(String packageName) {
+        synchronized (mLockObject) {
+            Set<KeySet> upgradeKeySets = new ArraySet<KeySet>();
             PackageSetting p = mPackages.get(packageName);
             if (p == null) {
                 throw new NullPointerException("Unknown package");
@@ -217,10 +290,12 @@
             if (p.keySetData == null) {
                 throw new IllegalArgumentException("Package has no keySet data");
             }
-            for (long l : p.keySetData.getSigningKeySets()) {
-                signingKeySets.add(mKeySets.get(l));
+            if (p.keySetData.isUsingUpgradeKeySets()) {
+                for (long l : p.keySetData.getUpgradeKeySets()) {
+                    upgradeKeySets.add(mKeySets.get(l));
+                }
             }
-            return signingKeySets;
+            return upgradeKeySets;
         }
     }
 
@@ -233,6 +308,9 @@
      * If the KeySet isn't known to the system, this adds that and creates the
      * mapping to the PublicKeys. If it is known, then it's deduped.
      *
+     * If the KeySet isn't known to the system, this adds it to all appropriate
+     * signingKeySets
+     *
      * Throws if the provided set is {@code null}.
      */
     private KeySet addKeySetLocked(Set<PublicKey> keys) {
@@ -240,7 +318,7 @@
             throw new NullPointerException("Provided keys cannot be null");
         }
         // add each of the keys in the provided set
-        Set<Long> addedKeyIds = new HashSet<Long>(keys.size());
+        Set<Long> addedKeyIds = new ArraySet<Long>(keys.size());
         for (PublicKey k : keys) {
             long id = addPublicKeyLocked(k);
             addedKeyIds.add(id);
@@ -260,6 +338,19 @@
         mKeySets.put(id, ks);
         // add the stable key ids to the mapping
         mKeySetMapping.put(id, addedKeyIds);
+        // add this KeySet id to all packages which are signed by it
+        for (String pkgName : mPackages.keySet()) {
+            PackageSetting p = mPackages.get(pkgName);
+            if (p.keySetData != null) {
+                long pProperSigning = p.keySetData.getProperSigningKeySet();
+                if (pProperSigning != PackageKeySetData.KEYSET_UNASSIGNED) {
+                    Set<Long> pSigningKeys = mKeySetMapping.get(pProperSigning);
+                    if (pSigningKeys.containsAll(addedKeyIds)) {
+                        p.keySetData.addSigningKeySet(id);
+                    }
+                }
+            }
+        }
         // go home
         return ks;
     }
@@ -299,6 +390,15 @@
     /**
      * Finds the stable identifier for a PublicKey or PUBLIC_KEY_NOT_FOUND.
      */
+    protected long getIdForPublicKey(PublicKey k) {
+        synchronized (mLockObject) {
+            return getIdForPublicKeyLocked(k);
+        }
+    }
+
+    /**
+     * Finds the stable identifier for a PublicKey or PUBLIC_KEY_NOT_FOUND.
+     */
     private long getIdForPublicKeyLocked(PublicKey k) {
         String encodedPublicKey = new String(k.getEncoded());
         for (int publicKeyIndex = 0; publicKeyIndex < mPublicKeys.size(); publicKeyIndex++) {
@@ -330,8 +430,8 @@
     public void removeAppKeySetData(String packageName) {
         synchronized (mLockObject) {
             // Get the package's known keys and KeySets
-            Set<Long> deletableKeySets = getKnownKeySetsByPackageNameLocked(packageName);
-            Set<Long> deletableKeys = new HashSet<Long>();
+            Set<Long> deletableKeySets = getOriginalKeySetsByPackageNameLocked(packageName);
+            Set<Long> deletableKeys = new ArraySet<Long>();
             Set<Long> knownKeys = null;
             for (Long ks : deletableKeySets) {
                 knownKeys = mKeySetMapping.get(ks);
@@ -340,14 +440,14 @@
                 }
             }
 
-            // Now remove the keys and KeySets known to any other package
+            // Now remove the keys and KeySets on which any other package relies
             for (String pkgName : mPackages.keySet()) {
                 if (pkgName.equals(packageName)) {
                     continue;
                 }
-                Set<Long> knownKeySets = getKnownKeySetsByPackageNameLocked(pkgName);
+                Set<Long> knownKeySets = getOriginalKeySetsByPackageNameLocked(pkgName);
                 deletableKeySets.removeAll(knownKeySets);
-                knownKeys = new HashSet<Long>();
+                knownKeys = new ArraySet<Long>();
                 for (Long ks : knownKeySets) {
                     knownKeys = mKeySetMapping.get(ks);
                     if (knownKeys != null) {
@@ -356,7 +456,7 @@
                 }
             }
 
-            // The remaining keys and KeySets are not known to any other
+            // The remaining keys and KeySets are not relied on by any other
             // application and so can be safely deleted.
             for (Long ks : deletableKeySets) {
                 mKeySets.delete(ks);
@@ -366,18 +466,28 @@
                 mPublicKeys.delete(keyId);
             }
 
-            // Now remove them from the KeySets known to each package
+            // Now remove the deleted KeySets from each package's signingKeySets
             for (String pkgName : mPackages.keySet()) {
                 PackageSetting p = mPackages.get(pkgName);
                 for (Long ks : deletableKeySets) {
                     p.keySetData.removeSigningKeySet(ks);
-                    p.keySetData.removeDefinedKeySet(ks);
                 }
             }
+
+            // Finally, remove all KeySets from the original package
+            PackageSetting p = mPackages.get(packageName);
+            clearPackageKeySetDataLocked(p);
         }
     }
 
-    private Set<Long> getKnownKeySetsByPackageNameLocked(String packageName) {
+    private void clearPackageKeySetDataLocked(PackageSetting p) {
+        p.keySetData.removeAllSigningKeySets();
+        p.keySetData.removeAllUpgradeKeySets();
+        p.keySetData.removeAllDefinedKeySets();
+        return;
+    }
+
+    private Set<Long> getOriginalKeySetsByPackageNameLocked(String packageName) {
         PackageSetting p = mPackages.get(packageName);
         if (p == null) {
             throw new NullPointerException("Unknown package");
@@ -385,12 +495,12 @@
         if (p.keySetData == null) {
             throw new IllegalArgumentException("Package has no keySet data");
         }
-        Set<Long> knownKeySets = new HashSet<Long>();
-        for (long ks : p.keySetData.getSigningKeySets()) {
-            knownKeySets.add(ks);
-        }
-        for (long ks : p.keySetData.getDefinedKeySets()) {
-            knownKeySets.add(ks);
+        Set<Long> knownKeySets = new ArraySet<Long>();
+        knownKeySets.add(p.keySetData.getProperSigningKeySet());
+        if (p.keySetData.isUsingDefinedKeySets()) {
+            for (long ks : p.keySetData.getDefinedKeySets()) {
+                knownKeySets.add(ks);
+            }
         }
         return knownKeySets;
     }
@@ -433,14 +543,16 @@
                         pw.println("");
                     }
                     printedLabel = false;
-                    for (long keySetId : pkg.keySetData.getDefinedKeySets()) {
-                        if (!printedLabel) {
-                            pw.print("      Defined KeySets: ");
-                            printedLabel = true;
-                        } else {
-                            pw.print(", ");
+                    if (pkg.keySetData.isUsingDefinedKeySets()) {
+                        for (long keySetId : pkg.keySetData.getDefinedKeySets()) {
+                            if (!printedLabel) {
+                                pw.print("      Defined KeySets: ");
+                                printedLabel = true;
+                            } else {
+                                pw.print(", ");
+                            }
+                            pw.print(Long.toString(keySetId));
                         }
-                        pw.print(Long.toString(keySetId));
                     }
                     if (printedLabel) {
                         pw.println("");
@@ -458,13 +570,29 @@
                     if (printedLabel) {
                         pw.println("");
                     }
+                    printedLabel = false;
+                    if (pkg.keySetData.isUsingUpgradeKeySets()) {
+                        for (long keySetId : pkg.keySetData.getUpgradeKeySets()) {
+                            if (!printedLabel) {
+                                pw.print("      Upgrade KeySets: ");
+                                printedLabel = true;
+                            } else {
+                                pw.print(", ");
+                            }
+                            pw.print(Long.toString(keySetId));
+                        }
+                    }
+                    if (printedLabel) {
+                        pw.println("");
+                    }
                 }
             }
         }
     }
 
-    void writeKeySetManagerLPr(XmlSerializer serializer) throws IOException {
+    void writeKeySetManagerServiceLPr(XmlSerializer serializer) throws IOException {
         serializer.startTag(null, "keyset-settings");
+        serializer.attribute(null, "version", Integer.toString(CURRENT_VERSION));
         writePublicKeysLPr(serializer);
         writeKeySetsLPr(serializer);
         serializer.startTag(null, "lastIssuedKeyId");
@@ -511,7 +639,24 @@
             throws XmlPullParserException, IOException {
         int type;
         long currentKeySetId = 0;
-        while ((type = parser.next()) != XmlPullParser.END_DOCUMENT) {
+        int outerDepth = parser.getDepth();
+        String recordedVersion = parser.getAttributeValue(null, "version");
+        if (recordedVersion == null || Integer.parseInt(recordedVersion) != CURRENT_VERSION) {
+            while ((type = parser.next()) != XmlPullParser.END_DOCUMENT
+                    && (type != XmlPullParser.END_TAG || parser.getDepth() > outerDepth)) {
+                // Our version is different than the one which generated the old keyset data.
+                // We don't want any of the old data, but we must advance the parser
+                continue;
+            }
+            // The KeySet information read previously from packages.xml is invalid.
+            // Destroy it all.
+            for (PackageSetting p : mPackages.values()) {
+                clearPackageKeySetDataLocked(p);
+            }
+            return;
+        }
+        while ((type = parser.next()) != XmlPullParser.END_DOCUMENT
+               && (type != XmlPullParser.END_TAG || parser.getDepth() > outerDepth)) {
             if (type == XmlPullParser.END_TAG || type == XmlPullParser.TEXT) {
                 continue;
             }
@@ -520,6 +665,10 @@
                 readKeysLPw(parser);
             } else if (tagName.equals("keysets")) {
                 readKeySetListLPw(parser);
+            } else if (tagName.equals("lastIssuedKeyId")) {
+                lastIssuedKeyId = Long.parseLong(parser.getAttributeValue(null, "value"));
+            } else if (tagName.equals("lastIssuedKeySetId")) {
+                lastIssuedKeySetId = Long.parseLong(parser.getAttributeValue(null, "value"));
             }
         }
     }
@@ -536,10 +685,6 @@
             final String tagName = parser.getName();
             if (tagName.equals("public-key")) {
                 readPublicKeyLPw(parser);
-            } else if (tagName.equals("lastIssuedKeyId")) {
-                lastIssuedKeyId = Long.parseLong(parser.getAttributeValue(null, "value"));
-            } else if (tagName.equals("lastIssuedKeySetId")) {
-                lastIssuedKeySetId = Long.parseLong(parser.getAttributeValue(null, "value"));
             }
         }
     }
@@ -558,7 +703,7 @@
             if (tagName.equals("keyset")) {
                 currentKeySetId = readIdentifierLPw(parser);
                 mKeySets.put(currentKeySetId, new KeySet(new Binder()));
-                mKeySetMapping.put(currentKeySetId, new HashSet<Long>());
+                mKeySetMapping.put(currentKeySetId, new ArraySet<Long>());
             } else if (tagName.equals("key-id")) {
                 long id = readIdentifierLPw(parser);
                 mKeySetMapping.get(currentKeySetId).add(id);
diff --git a/services/core/java/com/android/server/pm/PackageKeySetData.java b/services/core/java/com/android/server/pm/PackageKeySetData.java
index ebded28..d470807 100644
--- a/services/core/java/com/android/server/pm/PackageKeySetData.java
+++ b/services/core/java/com/android/server/pm/PackageKeySetData.java
@@ -16,108 +16,137 @@
 
 package com.android.server.pm;
 
+import com.android.internal.util.ArrayUtils;
+
 import java.util.Arrays;
 import java.util.HashMap;
 import java.util.Map;
 
 public class PackageKeySetData {
 
+    static final long KEYSET_UNASSIGNED = -1;
+
+    /* KeySet containing all signing keys - superset of the others */
+    private long mProperSigningKeySet;
+
     private long[] mSigningKeySets;
 
+    private long[] mUpgradeKeySets;
+
     private long[] mDefinedKeySets;
 
     private final Map<String, Long> mKeySetAliases;
 
     PackageKeySetData() {
-        mSigningKeySets = new long[0];
-        mDefinedKeySets = new long[0];
-        mKeySetAliases =  new HashMap<String, Long>();
+        mProperSigningKeySet = KEYSET_UNASSIGNED;
+        mKeySetAliases = new HashMap<String, Long>();
     }
 
     PackageKeySetData(PackageKeySetData original) {
         mSigningKeySets = original.getSigningKeySets().clone();
+        mUpgradeKeySets = original.getUpgradeKeySets().clone();
         mDefinedKeySets = original.getDefinedKeySets().clone();
         mKeySetAliases = new HashMap<String, Long>();
         mKeySetAliases.putAll(original.getAliases());
     }
 
-    public void addSigningKeySet(long ks) {
-        // deduplicate
-        for (long knownKeySet : mSigningKeySets) {
-            if (ks == knownKeySet) {
-                return;
-            }
+    protected void setProperSigningKeySet(long ks) {
+        if (ks == mProperSigningKeySet) {
+
+            /* nothing to change */
+            return;
         }
-        int end = mSigningKeySets.length;
-        mSigningKeySets = Arrays.copyOf(mSigningKeySets, end + 1);
-        mSigningKeySets[end] = ks;
+
+        /* otherwise, our current signing keysets are likely invalid */
+        removeAllSigningKeySets();
+        mProperSigningKeySet = ks;
+        addSigningKeySet(ks);
+        return;
     }
 
-    public void removeSigningKeySet(long ks) {
-        if (packageIsSignedBy(ks)) {
-            long[] keysets = new long[mSigningKeySets.length - 1];
-            int index = 0;
-            for (long signingKeySet : mSigningKeySets) {
-                if (signingKeySet != ks) {
-                    keysets[index] = signingKeySet;
-                    index += 1;
-                }
-            }
-            mSigningKeySets = keysets;
+    protected long getProperSigningKeySet() {
+        return mProperSigningKeySet;
+    }
+
+    protected void addSigningKeySet(long ks) {
+        mSigningKeySets = ArrayUtils.appendLong(mSigningKeySets, ks);
+    }
+
+    protected void removeSigningKeySet(long ks) {
+        mSigningKeySets = ArrayUtils.removeLong(mSigningKeySets, ks);
+    }
+
+    protected void addUpgradeKeySet(String alias) {
+
+        /* must have previously been defined */
+        Long ks = mKeySetAliases.get(alias);
+        if (ks != null) {
+            mUpgradeKeySets = ArrayUtils.appendLong(mUpgradeKeySets, ks);
+        } else {
+            throw new IllegalArgumentException("Upgrade keyset alias " + alias
+                    + "does not refer to a defined keyset alias!");
         }
     }
 
-    public void addDefinedKeySet(long ks, String alias) {
-        // deduplicate
-        for (long knownKeySet : mDefinedKeySets) {
-            if (ks == knownKeySet) {
-                return;
-            }
-        }
-        int end = mDefinedKeySets.length;
-        mDefinedKeySets = Arrays.copyOf(mDefinedKeySets, end + 1);
-        mDefinedKeySets[end] = ks;
+    /*
+     * Used only when restoring keyset data from persistent storage.  Must
+     * correspond to a defined-keyset.
+     */
+    protected void addUpgradeKeySetById(long ks) {
+        mSigningKeySets = ArrayUtils.appendLong(mSigningKeySets, ks);
+    }
+
+    protected void addDefinedKeySet(long ks, String alias) {
+        mDefinedKeySets = ArrayUtils.appendLong(mDefinedKeySets, ks);
         mKeySetAliases.put(alias, ks);
     }
 
-    public void removeDefinedKeySet(long ks) {
-        if (mKeySetAliases.containsValue(ks)) {
-            long[] keysets = new long[mDefinedKeySets.length - 1];
-            int index = 0;
-            for (long definedKeySet : mDefinedKeySets) {
-                if (definedKeySet != ks) {
-                    keysets[index] = definedKeySet;
-                    index += 1;
-                }
-            }
-            mDefinedKeySets = keysets;
-            for (String alias : mKeySetAliases.keySet()) {
-                if (mKeySetAliases.get(alias) == ks) {
-                    mKeySetAliases.remove(alias);
-                    break;
-                }
-            }
-        }
+    protected void removeAllSigningKeySets() {
+        mProperSigningKeySet = KEYSET_UNASSIGNED;
+        mSigningKeySets = null;
+        return;
     }
 
-    public boolean packageIsSignedBy(long ks) {
-        for (long signingKeySet : mSigningKeySets) {
-            if (ks == signingKeySet) {
-                return true;
-            }
-        }
-        return false;
+    protected void removeAllUpgradeKeySets() {
+        mUpgradeKeySets = null;
+        return;
     }
 
-    public long[] getSigningKeySets() {
+    protected void removeAllDefinedKeySets() {
+        mDefinedKeySets = null;
+        mKeySetAliases.clear();
+        return;
+    }
+
+    protected boolean packageIsSignedBy(long ks) {
+        return ArrayUtils.contains(mSigningKeySets, ks);
+    }
+
+    protected long[] getSigningKeySets() {
         return mSigningKeySets;
     }
 
-    public long[] getDefinedKeySets() {
+    protected long[] getUpgradeKeySets() {
+        return mUpgradeKeySets;
+    }
+
+    protected long[] getDefinedKeySets() {
         return mDefinedKeySets;
     }
 
-    public Map<String, Long> getAliases() {
+    protected Map<String, Long> getAliases() {
         return mKeySetAliases;
     }
+
+    protected boolean isUsingDefinedKeySets() {
+
+        /* should never be the case that mDefinedKeySets.length == 0 */
+        return (mDefinedKeySets != null && mDefinedKeySets.length > 0);
+    }
+
+    protected boolean isUsingUpgradeKeySets() {
+
+        /* should never be the case that mUpgradeKeySets.length == 0 */
+        return (mUpgradeKeySets != null && mUpgradeKeySets.length > 0);
+    }
 }
\ No newline at end of file
diff --git a/services/core/java/com/android/server/pm/PackageManagerService.java b/services/core/java/com/android/server/pm/PackageManagerService.java
old mode 100755
new mode 100644
index cac27bc..bad16c8
--- a/services/core/java/com/android/server/pm/PackageManagerService.java
+++ b/services/core/java/com/android/server/pm/PackageManagerService.java
@@ -2990,7 +2990,7 @@
             // Migrate the old signatures to the new scheme.
             existingSigs.assignSignatures(scannedPkg.mSignatures);
             // The new KeySets will be re-added later in the scanning process.
-            mSettings.mKeySetManager.removeAppKeySetData(scannedPkg.packageName);
+            mSettings.mKeySetManagerService.removeAppKeySetData(scannedPkg.packageName);
             return PackageManager.SIGNATURE_MATCH;
         }
         return PackageManager.SIGNATURE_NO_MATCH;
@@ -4309,11 +4309,15 @@
                 && ps.codePath.equals(srcFile)
                 && ps.timeStamp == srcFile.lastModified()
                 && !isCompatSignatureUpdateNeeded(pkg)) {
+            long mSigningKeySetId = ps.keySetData.getProperSigningKeySet();
             if (ps.signatures.mSignatures != null
-                    && ps.signatures.mSignatures.length != 0) {
+                    && ps.signatures.mSignatures.length != 0
+                    && mSigningKeySetId != PackageKeySetData.KEYSET_UNASSIGNED) {
                 // Optimization: reuse the existing cached certificates
                 // if the package appears to be unchanged.
                 pkg.mSignatures = ps.signatures.mSignatures;
+                KeySetManagerService ksms = mSettings.mKeySetManagerService;
+                pkg.mSigningKeys = ksms.getPublicKeysFromKeySet(mSigningKeySetId);
                 return true;
             }
 
@@ -4584,6 +4588,7 @@
                 return false;
             }
         }
+
         // Check for shared user signatures
         if (pkgSetting.sharedUser != null && pkgSetting.sharedUser.signatures.mSignatures != null) {
             // Already existing package. Make sure signatures match
@@ -5276,33 +5281,43 @@
 
             pkg.applicationInfo.uid = pkgSetting.appId;
             pkg.mExtras = pkgSetting;
-
-            if (!verifySignaturesLP(pkgSetting, pkg)) {
-                if ((parseFlags&PackageParser.PARSE_IS_SYSTEM_DIR) == 0) {
-                    return null;
-                }
-                // The signature has changed, but this package is in the system
-                // image...  let's recover!
-                pkgSetting.signatures.mSignatures = pkg.mSignatures;
-                // However...  if this package is part of a shared user, but it
-                // doesn't match the signature of the shared user, let's fail.
-                // What this means is that you can't change the signatures
-                // associated with an overall shared user, which doesn't seem all
-                // that unreasonable.
-                if (pkgSetting.sharedUser != null) {
-                    if (compareSignatures(pkgSetting.sharedUser.signatures.mSignatures,
-                            pkg.mSignatures) != PackageManager.SIGNATURE_MATCH) {
-                        Log.w(TAG, "Signature mismatch for shared user : " + pkgSetting.sharedUser);
-                        mLastScanError = PackageManager.INSTALL_PARSE_FAILED_INCONSISTENT_CERTIFICATES;
+            if (!pkgSetting.keySetData.isUsingUpgradeKeySets() || pkgSetting.sharedUser != null) {
+                if (!verifySignaturesLP(pkgSetting, pkg)) {
+                    if ((parseFlags&PackageParser.PARSE_IS_SYSTEM_DIR) == 0) {
                         return null;
                     }
-                }
-                // File a report about this.
-                String msg = "System package " + pkg.packageName
+                    // The signature has changed, but this package is in the system
+                    // image...  let's recover!
+                    pkgSetting.signatures.mSignatures = pkg.mSignatures;
+                    // However...  if this package is part of a shared user, but it
+                    // doesn't match the signature of the shared user, let's fail.
+                    // What this means is that you can't change the signatures
+                    // associated with an overall shared user, which doesn't seem all
+                    // that unreasonable.
+                    if (pkgSetting.sharedUser != null) {
+                        if (compareSignatures(pkgSetting.sharedUser.signatures.mSignatures,
+                                              pkg.mSignatures) != PackageManager.SIGNATURE_MATCH) {
+                            Log.w(TAG, "Signature mismatch for shared user : " + pkgSetting.sharedUser);
+                            mLastScanError = PackageManager.INSTALL_PARSE_FAILED_INCONSISTENT_CERTIFICATES;
+                            return null;
+                        }
+                    }
+                    // File a report about this.
+                    String msg = "System package " + pkg.packageName
                         + " signature changed; retaining data.";
-                reportSettingsProblem(Log.WARN, msg);
+                    reportSettingsProblem(Log.WARN, msg);
+                }
+            } else {
+                if (!checkUpgradeKeySetLP(pkgSetting, pkg)) {
+                    Slog.e(TAG, "Package " + pkg.packageName
+                           + " upgrade keys do not match the previously installed version; ");
+                    mLastScanError = PackageManager.INSTALL_FAILED_UPDATE_INCOMPATIBLE;
+                    return null;
+                } else {
+                    // signatures may have changed as result of upgrade
+                    pkgSetting.signatures.mSignatures = pkg.mSignatures;
+                }
             }
-
             // Verify that this new package doesn't have any content providers
             // that conflict with existing packages.  Only do this if the
             // package isn't already installed, since we don't want to break
@@ -5808,16 +5823,24 @@
                 }
             }
 
-            // Add the package's KeySets to the global KeySetManager
-            KeySetManager ksm = mSettings.mKeySetManager;
+            // Add the package's KeySets to the global KeySetManagerService
+            KeySetManagerService ksms = mSettings.mKeySetManagerService;
             try {
-                ksm.addSigningKeySetToPackage(pkg.packageName, pkg.mSigningKeys);
+                // Old KeySetData no longer valid.
+                ksms.removeAppKeySetData(pkg.packageName);
+                ksms.addSigningKeySetToPackage(pkg.packageName, pkg.mSigningKeys);
                 if (pkg.mKeySetMapping != null) {
-                    for (Map.Entry<String, ArraySet<PublicKey>> entry :
+                    for (Map.Entry<String, Set<PublicKey>> entry :
                             pkg.mKeySetMapping.entrySet()) {
                         if (entry.getValue() != null) {
-                            ksm.addDefinedKeySetToPackage(pkg.packageName,
-                                entry.getValue(), entry.getKey());
+                            ksms.addDefinedKeySetToPackage(pkg.packageName,
+                                                          entry.getValue(), entry.getKey());
+                        }
+                    }
+                    if (pkg.mUpgradeKeySets != null
+                            && pkg.mKeySetMapping.keySet().containsAll(pkg.mUpgradeKeySets)) {
+                        for (String upgradeAlias : pkg.mUpgradeKeySets) {
+                            ksms.addUpgradeKeySetToPackage(pkg.packageName, upgradeAlias);
                         }
                     }
                 }
@@ -10019,10 +10042,28 @@
         }
     }
 
+    private boolean checkUpgradeKeySetLP(PackageSetting oldPS, PackageParser.Package newPkg) {
+        // Upgrade keysets are being used.  Determine if new package has a superset of the
+        // required keys.
+        long[] upgradeKeySets = oldPS.keySetData.getUpgradeKeySets();
+        KeySetManagerService ksms = mSettings.mKeySetManagerService;
+        Set<Long> newSigningKeyIds = new ArraySet<Long>();
+        for (PublicKey pk : newPkg.mSigningKeys) {
+            newSigningKeyIds.add(ksms.getIdForPublicKey(pk));
+        }
+        //remove PUBLIC_KEY_NOT_FOUND, although not necessary
+        newSigningKeyIds.remove(ksms.PUBLIC_KEY_NOT_FOUND);
+        for (int i = 0; i < upgradeKeySets.length; i++) {
+            if (newSigningKeyIds.containsAll(ksms.mKeySetMapping.get(upgradeKeySets[i]))) {
+                return true;
+            }
+        }
+        return false;
+    }
+
     private void replacePackageLI(PackageParser.Package pkg,
             int parseFlags, int scanMode, UserHandle user,
             String installerPackageName, PackageInstalledInfo res, String abiOverride) {
-
         PackageParser.Package oldPackage;
         String pkgName = pkg.packageName;
         int[] allUsers;
@@ -10032,15 +10073,25 @@
         synchronized(mPackages) {
             oldPackage = mPackages.get(pkgName);
             if (DEBUG_INSTALL) Slog.d(TAG, "replacePackageLI: new=" + pkg + ", old=" + oldPackage);
-            if (compareSignatures(oldPackage.mSignatures, pkg.mSignatures)
+            PackageSetting ps = mSettings.mPackages.get(pkgName);
+            if (ps == null || !ps.keySetData.isUsingUpgradeKeySets() || ps.sharedUser != null) {
+                // default to original signature matching
+                if (compareSignatures(oldPackage.mSignatures, pkg.mSignatures)
                     != PackageManager.SIGNATURE_MATCH) {
-                Slog.w(TAG, "New package has a different signature: " + pkgName);
-                res.returnCode = PackageManager.INSTALL_PARSE_FAILED_INCONSISTENT_CERTIFICATES;
-                return;
+                    Slog.w(TAG, "New package has a different signature: " + pkgName);
+                    res.returnCode = PackageManager.INSTALL_PARSE_FAILED_INCONSISTENT_CERTIFICATES;
+                    return;
+                }
+            } else {
+                if(!checkUpgradeKeySetLP(ps, pkg)) {
+                    Slog.w(TAG, "New package not signed by keys specified by upgrade-keysets: "
+                           + pkgName);
+                    res.returnCode = PackageManager.INSTALL_PARSE_FAILED_INCONSISTENT_CERTIFICATES;
+                    return;
+                }
             }
 
             // In case of rollback, remember per-user/profile install state
-            PackageSetting ps = mSettings.mPackages.get(pkgName);
             allUsers = sUserManager.getUserIds();
             perUserInstalled = new boolean[allUsers.length];
             for (int i = 0; i < allUsers.length; i++) {
@@ -10794,6 +10845,7 @@
             if (deletedPs != null) {
                 if ((flags&PackageManager.DELETE_KEEP_DATA) == 0) {
                     if (outInfo != null) {
+                        mSettings.mKeySetManagerService.removeAppKeySetData(packageName);
                         outInfo.removedAppId = mSettings.removePackageLPw(packageName);
                     }
                     if (deletedPs != null) {
@@ -11048,7 +11100,6 @@
         }
 
         boolean ret = false;
-        mSettings.mKeySetManager.removeAppKeySetData(packageName);
         if (isSystemApp(ps)) {
             if (DEBUG_REMOVE) Slog.d(TAG, "Removing system package:" + ps.name);
             // When an updated system application is deleted we delete the existing resources as well and
@@ -12429,7 +12480,7 @@
             }
 
             if (!checkin && dumpState.isDumping(DumpState.DUMP_KEYSETS)) {
-                mSettings.mKeySetManager.dump(pw, packageName, dumpState);
+                mSettings.mKeySetManagerService.dump(pw, packageName, dumpState);
             }
 
             if (dumpState.isDumping(DumpState.DUMP_PACKAGES)) {
diff --git a/services/core/java/com/android/server/pm/Settings.java b/services/core/java/com/android/server/pm/Settings.java
index 1867ff3..4304dee 100644
--- a/services/core/java/com/android/server/pm/Settings.java
+++ b/services/core/java/com/android/server/pm/Settings.java
@@ -244,7 +244,7 @@
 
     private final File mSystemDir;
 
-    public final KeySetManager mKeySetManager = new KeySetManager(mPackages);
+    public final KeySetManagerService mKeySetManagerService = new KeySetManagerService(mPackages);
 
     // A mapping of (sourceUserId, targetUserId, packageNames) for forwarding the intents of a
     // package.
@@ -1721,7 +1721,7 @@
                 }
             }
             
-            mKeySetManager.writeKeySetManagerLPr(serializer);
+            mKeySetManagerService.writeKeySetManagerServiceLPr(serializer);
 
             serializer.endTag(null, "packages");
 
@@ -1936,6 +1936,7 @@
         }
 
         writeSigningKeySetsLPr(serializer, pkg.keySetData);
+        writeUpgradeKeySetsLPr(serializer, pkg.keySetData);
         writeKeySetAliasesLPr(serializer, pkg.keySetData);
 
         serializer.endTag(null, "package");
@@ -1943,10 +1944,23 @@
 
     void writeSigningKeySetsLPr(XmlSerializer serializer,
             PackageKeySetData data) throws IOException {
-        for (long id : data.getSigningKeySets()) {
-            serializer.startTag(null, "signing-keyset");
-            serializer.attribute(null, "identifier", Long.toString(id));
-            serializer.endTag(null, "signing-keyset");
+        if (data.getSigningKeySets() != null) {
+            for (long id : data.getSigningKeySets()) {
+                serializer.startTag(null, "signing-keyset");
+                serializer.attribute(null, "identifier", Long.toString(id));
+                serializer.endTag(null, "signing-keyset");
+            }
+        }
+    }
+
+    void writeUpgradeKeySetsLPr(XmlSerializer serializer,
+            PackageKeySetData data) throws IOException {
+        if (data.isUsingUpgradeKeySets()) {
+            for (long id : data.getUpgradeKeySets()) {
+                serializer.startTag(null, "upgrade-keyset");
+                serializer.attribute(null, "identifier", Long.toString(id));
+                serializer.endTag(null, "upgrade-keyset");
+            }
         }
     }
 
@@ -2157,7 +2171,7 @@
                     final String enforcement = parser.getAttributeValue(null, ATTR_ENFORCEMENT);
                     mReadExternalStorageEnforced = "1".equals(enforcement);
                 } else if (tagName.equals("keyset-settings")) {
-                    mKeySetManager.readKeySetsLPw(parser);
+                    mKeySetManagerService.readKeySetsLPw(parser);
                 } else {
                     Slog.w(PackageManagerService.TAG, "Unknown element under <packages>: "
                             + parser.getName());
@@ -2893,8 +2907,9 @@
                 } else if (tagName.equals("signing-keyset")) {
                     long id = Long.parseLong(parser.getAttributeValue(null, "identifier"));
                     packageSetting.keySetData.addSigningKeySet(id);
-                    if (false) Slog.d(TAG, "Adding signing keyset " + Long.toString(id)
-                            + " to " + name);
+                } else if (tagName.equals("upgrade-keyset")) {
+                    long id = Long.parseLong(parser.getAttributeValue(null, "identifier"));
+                    packageSetting.keySetData.addUpgradeKeySetById(id);
                 } else if (tagName.equals("defined-keyset")) {
                     long id = Long.parseLong(parser.getAttributeValue(null, "identifier"));
                     String alias = parser.getAttributeValue(null, "alias");