diff --git a/services/backup/java/com/android/server/backup/BackupManagerService.java b/services/backup/java/com/android/server/backup/BackupManagerService.java
index b6e2dca..d6f6c6c 100644
--- a/services/backup/java/com/android/server/backup/BackupManagerService.java
+++ b/services/backup/java/com/android/server/backup/BackupManagerService.java
@@ -1398,7 +1398,7 @@
     // Returns the set of all applications that define an android:backupAgent attribute
     private List<PackageInfo> allAgentPackages() {
         // !!! TODO: cache this and regenerate only when necessary
-        int flags = PackageManager.GET_SIGNATURES;
+        int flags = PackageManager.GET_SIGNING_CERTIFICATES;
         List<PackageInfo> packages = mPackageManager.getInstalledPackages(flags);
         int N = packages.size();
         for (int a = N - 1; a >= 0; a--) {
@@ -1643,7 +1643,7 @@
             }
             try {
                 PackageInfo packageInfo = mPackageManager.getPackageInfo(packageName,
-                        PackageManager.GET_SIGNATURES);
+                        PackageManager.GET_SIGNING_CERTIFICATES);
                 if (!AppBackupUtils.appIsEligibleForBackup(packageInfo.applicationInfo,
                         mPackageManager)) {
                     BackupObserverUtils.sendBackupOnPackageResult(observer, packageName,
@@ -2353,7 +2353,8 @@
         if (DEBUG) Slog.v(TAG, "clearBackupData() of " + packageName + " on " + transportName);
         PackageInfo info;
         try {
-            info = mPackageManager.getPackageInfo(packageName, PackageManager.GET_SIGNATURES);
+            info = mPackageManager.getPackageInfo(packageName,
+                    PackageManager.GET_SIGNING_CERTIFICATES);
         } catch (NameNotFoundException e) {
             Slog.d(TAG, "No such package '" + packageName + "' - not clearing backup data");
             return;
diff --git a/services/backup/java/com/android/server/backup/PackageManagerBackupAgent.java b/services/backup/java/com/android/server/backup/PackageManagerBackupAgent.java
index 3cf374f..dc28cd1 100644
--- a/services/backup/java/com/android/server/backup/PackageManagerBackupAgent.java
+++ b/services/backup/java/com/android/server/backup/PackageManagerBackupAgent.java
@@ -23,6 +23,7 @@
 import android.content.pm.ApplicationInfo;
 import android.content.pm.PackageInfo;
 import android.content.pm.PackageManager;
+import android.content.pm.PackageManagerInternal;
 import android.content.pm.ResolveInfo;
 import android.content.pm.PackageManager.NameNotFoundException;
 import android.content.pm.Signature;
@@ -30,6 +31,7 @@
 import android.os.ParcelFileDescriptor;
 import android.util.Slog;
 
+import com.android.server.LocalServices;
 import com.android.server.backup.utils.AppBackupUtils;
 
 import java.io.BufferedInputStream;
@@ -154,7 +156,7 @@
 
     public static List<PackageInfo> getStorableApplications(PackageManager pm) {
         List<PackageInfo> pkgs;
-        pkgs = pm.getInstalledPackages(PackageManager.GET_SIGNATURES);
+        pkgs = pm.getInstalledPackages(PackageManager.GET_SIGNING_CERTIFICATES);
         int N = pkgs.size();
         for (int a = N-1; a >= 0; a--) {
             PackageInfo pkg = pkgs.get(a);
@@ -235,10 +237,17 @@
         if (home != null) {
             try {
                 homeInfo = mPackageManager.getPackageInfo(home.getPackageName(),
-                        PackageManager.GET_SIGNATURES);
+                        PackageManager.GET_SIGNING_CERTIFICATES);
                 homeInstaller = mPackageManager.getInstallerPackageName(home.getPackageName());
                 homeVersion = homeInfo.getLongVersionCode();
-                homeSigHashes = BackupUtils.hashSignatureArray(homeInfo.signatures);
+                Signature[][] signingHistory = homeInfo.signingCertificateHistory;
+                if (signingHistory == null || signingHistory.length == 0) {
+                    Slog.e(TAG, "Home app has no signing history");
+                } else {
+                    // retrieve the newest sigs to back up
+                    Signature[] homeInfoSignatures = signingHistory[signingHistory.length - 1];
+                    homeSigHashes = BackupUtils.hashSignatureArray(homeInfoSignatures);
+                }
             } catch (NameNotFoundException e) {
                 Slog.w(TAG, "Can't access preferred home info");
                 // proceed as though there were no preferred home set
@@ -252,10 +261,11 @@
             //    2. the home app [or absence] we now use differs from the prior state,
             // OR 3. it looks like we use the same home app + version as before, but
             //       the signatures don't match so we treat them as different apps.
+            PackageManagerInternal pmi = LocalServices.getService(PackageManagerInternal.class);
             final boolean needHomeBackup = (homeVersion != mStoredHomeVersion)
                     || !Objects.equals(home, mStoredHomeComponent)
                     || (home != null
-                        && !BackupUtils.signaturesMatch(mStoredHomeSigHashes, homeInfo));
+                        && !BackupUtils.signaturesMatch(mStoredHomeSigHashes, homeInfo, pmi));
             if (needHomeBackup) {
                 if (DEBUG) {
                     Slog.i(TAG, "Home preference changed; backing up new state " + home);
@@ -304,7 +314,7 @@
                     PackageInfo info = null;
                     try {
                         info = mPackageManager.getPackageInfo(packName,
-                                PackageManager.GET_SIGNATURES);
+                                PackageManager.GET_SIGNING_CERTIFICATES);
                     } catch (NameNotFoundException e) {
                         // Weird; we just found it, and now are told it doesn't exist.
                         // Treat it as having been removed from the device.
@@ -323,9 +333,9 @@
                             continue;
                         }
                     }
-                    
-                    if (info.signatures == null || info.signatures.length == 0)
-                    {
+
+                    Signature[][] signingHistory = info.signingCertificateHistory;
+                    if (signingHistory == null || signingHistory.length == 0) {
                         Slog.w(TAG, "Not backing up package " + packName
                                 + " since it appears to have no signatures.");
                         continue;
@@ -347,8 +357,10 @@
                     } else {
                         outputBufferStream.writeInt(info.versionCode);
                     }
+                    // retrieve the newest sigs to back up
+                    Signature[] infoSignatures = signingHistory[signingHistory.length - 1];
                     writeSignatureHashArray(outputBufferStream,
-                            BackupUtils.hashSignatureArray(info.signatures));
+                            BackupUtils.hashSignatureArray(infoSignatures));
 
                     if (DEBUG) {
                         Slog.v(TAG, "+ writing metadata for " + packName
diff --git a/services/backup/java/com/android/server/backup/fullbackup/PerformAdbBackupTask.java b/services/backup/java/com/android/server/backup/fullbackup/PerformAdbBackupTask.java
index 2e2d3eb..821cca1 100644
--- a/services/backup/java/com/android/server/backup/fullbackup/PerformAdbBackupTask.java
+++ b/services/backup/java/com/android/server/backup/fullbackup/PerformAdbBackupTask.java
@@ -129,7 +129,7 @@
                 try {
                     PackageInfo info = backupManagerService.getPackageManager().getPackageInfo(
                             pkgName,
-                            PackageManager.GET_SIGNATURES);
+                            PackageManager.GET_SIGNING_CERTIFICATES);
                     set.put(pkgName, info);
                 } catch (NameNotFoundException e) {
                     Slog.w(TAG, "Unknown package " + pkgName + ", skipping");
@@ -240,7 +240,8 @@
 
         // doAllApps supersedes the package set if any
         if (mAllApps) {
-            List<PackageInfo> allPackages = pm.getInstalledPackages(PackageManager.GET_SIGNATURES);
+            List<PackageInfo> allPackages = pm.getInstalledPackages(
+                    PackageManager.GET_SIGNING_CERTIFICATES);
             for (int i = 0; i < allPackages.size(); i++) {
                 PackageInfo pkg = allPackages.get(i);
                 // Exclude system apps if we've been asked to do so
diff --git a/services/backup/java/com/android/server/backup/fullbackup/PerformFullTransportBackupTask.java b/services/backup/java/com/android/server/backup/fullbackup/PerformFullTransportBackupTask.java
index f9c36699..2c2dd85 100644
--- a/services/backup/java/com/android/server/backup/fullbackup/PerformFullTransportBackupTask.java
+++ b/services/backup/java/com/android/server/backup/fullbackup/PerformFullTransportBackupTask.java
@@ -181,7 +181,7 @@
         for (String pkg : whichPackages) {
             try {
                 PackageManager pm = backupManagerService.getPackageManager();
-                PackageInfo info = pm.getPackageInfo(pkg, PackageManager.GET_SIGNATURES);
+                PackageInfo info = pm.getPackageInfo(pkg, PackageManager.GET_SIGNING_CERTIFICATES);
                 mCurrentPackage = info;
                 if (!AppBackupUtils.appIsEligibleForBackup(info.applicationInfo, pm)) {
                     // Cull any packages that have indicated that backups are not permitted,
diff --git a/services/backup/java/com/android/server/backup/internal/PerformBackupTask.java b/services/backup/java/com/android/server/backup/internal/PerformBackupTask.java
index 0ba83cf..11394e66 100644
--- a/services/backup/java/com/android/server/backup/internal/PerformBackupTask.java
+++ b/services/backup/java/com/android/server/backup/internal/PerformBackupTask.java
@@ -422,7 +422,8 @@
         // package's backup agent.
         try {
             PackageManager pm = backupManagerService.getPackageManager();
-            mCurrentPackage = pm.getPackageInfo(request.packageName, PackageManager.GET_SIGNATURES);
+            mCurrentPackage = pm.getPackageInfo(request.packageName,
+                    PackageManager.GET_SIGNING_CERTIFICATES);
             if (!AppBackupUtils.appIsEligibleForBackup(mCurrentPackage.applicationInfo, pm)) {
                 // The manifest has changed but we had a stale backup request pending.
                 // This won't happen again because the app won't be requesting further
diff --git a/services/backup/java/com/android/server/backup/restore/FullRestoreEngine.java b/services/backup/java/com/android/server/backup/restore/FullRestoreEngine.java
index 0ca4f25..c1a1c1d 100644
--- a/services/backup/java/com/android/server/backup/restore/FullRestoreEngine.java
+++ b/services/backup/java/com/android/server/backup/restore/FullRestoreEngine.java
@@ -36,11 +36,13 @@
 import android.content.pm.ApplicationInfo;
 import android.content.pm.PackageInfo;
 import android.content.pm.PackageManager.NameNotFoundException;
+import android.content.pm.PackageManagerInternal;
 import android.content.pm.Signature;
 import android.os.ParcelFileDescriptor;
 import android.os.RemoteException;
 import android.util.Slog;
 
+import com.android.server.LocalServices;
 import com.android.server.backup.BackupRestoreTask;
 import com.android.server.backup.FileMetadata;
 import com.android.server.backup.KeyValueAdbRestoreEngine;
@@ -207,8 +209,11 @@
                 if (info.path.equals(BACKUP_MANIFEST_FILENAME)) {
                     Signature[] signatures = tarBackupReader.readAppManifestAndReturnSignatures(
                             info);
+                    PackageManagerInternal pmi = LocalServices.getService(
+                            PackageManagerInternal.class);
                     RestorePolicy restorePolicy = tarBackupReader.chooseRestorePolicy(
-                            mBackupManagerService.getPackageManager(), allowApks, info, signatures);
+                            mBackupManagerService.getPackageManager(), allowApks, info, signatures,
+                            pmi);
                     mManifestSignatures.put(info.packageName, signatures);
                     mPackagePolicies.put(pkg, restorePolicy);
                     mPackageInstallers.put(pkg, info.installerPackageName);
diff --git a/services/backup/java/com/android/server/backup/restore/PerformAdbRestoreTask.java b/services/backup/java/com/android/server/backup/restore/PerformAdbRestoreTask.java
index e576b3c..dacde0b 100644
--- a/services/backup/java/com/android/server/backup/restore/PerformAdbRestoreTask.java
+++ b/services/backup/java/com/android/server/backup/restore/PerformAdbRestoreTask.java
@@ -40,6 +40,7 @@
 import android.content.pm.ApplicationInfo;
 import android.content.pm.PackageInfo;
 import android.content.pm.PackageManager.NameNotFoundException;
+import android.content.pm.PackageManagerInternal;
 import android.content.pm.Signature;
 import android.os.Environment;
 import android.os.ParcelFileDescriptor;
@@ -47,6 +48,7 @@
 import android.util.Slog;
 
 import com.android.internal.annotations.VisibleForTesting;
+import com.android.server.LocalServices;
 import com.android.server.backup.BackupManagerService;
 import com.android.server.backup.FileMetadata;
 import com.android.server.backup.KeyValueAdbRestoreEngine;
@@ -470,9 +472,11 @@
                 if (info.path.equals(BACKUP_MANIFEST_FILENAME)) {
                     Signature[] signatures = tarBackupReader.readAppManifestAndReturnSignatures(
                             info);
+                    PackageManagerInternal pmi = LocalServices.getService(
+                            PackageManagerInternal.class);
                     RestorePolicy restorePolicy = tarBackupReader.chooseRestorePolicy(
                             mBackupManagerService.getPackageManager(), allowApks,
-                            info, signatures);
+                            info, signatures, pmi);
                     mManifestSignatures.put(info.packageName, signatures);
                     mPackagePolicies.put(pkg, restorePolicy);
                     mPackageInstallers.put(pkg, info.installerPackageName);
diff --git a/services/backup/java/com/android/server/backup/restore/PerformUnifiedRestoreTask.java b/services/backup/java/com/android/server/backup/restore/PerformUnifiedRestoreTask.java
index 3caa1e7..4b467e5 100644
--- a/services/backup/java/com/android/server/backup/restore/PerformUnifiedRestoreTask.java
+++ b/services/backup/java/com/android/server/backup/restore/PerformUnifiedRestoreTask.java
@@ -43,6 +43,7 @@
 import android.content.pm.ApplicationInfo;
 import android.content.pm.PackageInfo;
 import android.content.pm.PackageManager;
+import android.content.pm.PackageManagerInternal;
 import android.content.pm.PackageManager.NameNotFoundException;
 import android.os.Bundle;
 import android.os.Message;
@@ -57,6 +58,7 @@
 import com.android.internal.backup.IBackupTransport;
 import com.android.server.AppWidgetBackupBridge;
 import com.android.server.EventLogTags;
+import com.android.server.LocalServices;
 import com.android.server.backup.BackupRestoreTask;
 import com.android.server.backup.BackupUtils;
 import com.android.server.backup.PackageManagerBackupAgent;
@@ -504,7 +506,7 @@
 
             try {
                 mCurrentPackage = backupManagerService.getPackageManager().getPackageInfo(
-                        pkgName, PackageManager.GET_SIGNATURES);
+                        pkgName, PackageManager.GET_SIGNING_CERTIFICATES);
             } catch (NameNotFoundException e) {
                 // Whoops, we thought we could restore this package but it
                 // turns out not to be present.  Skip it.
@@ -619,7 +621,8 @@
         }
 
         Metadata metaInfo = mPmAgent.getRestoredMetadata(packageName);
-        if (!BackupUtils.signaturesMatch(metaInfo.sigHashes, mCurrentPackage)) {
+        PackageManagerInternal pmi = LocalServices.getService(PackageManagerInternal.class);
+        if (!BackupUtils.signaturesMatch(metaInfo.sigHashes, mCurrentPackage, pmi)) {
             Slog.w(TAG, "Signature mismatch restoring " + packageName);
             mMonitor = BackupManagerMonitorUtils.monitorEvent(mMonitor,
                     BackupManagerMonitor.LOG_EVENT_ID_SIGNATURE_MISMATCH, mCurrentPackage,
diff --git a/services/backup/java/com/android/server/backup/utils/AppBackupUtils.java b/services/backup/java/com/android/server/backup/utils/AppBackupUtils.java
index 6780563..5518374 100644
--- a/services/backup/java/com/android/server/backup/utils/AppBackupUtils.java
+++ b/services/backup/java/com/android/server/backup/utils/AppBackupUtils.java
@@ -25,6 +25,7 @@
 import android.content.pm.ApplicationInfo;
 import android.content.pm.PackageInfo;
 import android.content.pm.PackageManager;
+import android.content.pm.PackageManagerInternal;
 import android.content.pm.Signature;
 import android.os.Process;
 import android.util.Slog;
@@ -37,6 +38,9 @@
  * Utility methods wrapping operations on ApplicationInfo and PackageInfo.
  */
 public class AppBackupUtils {
+
+    private static final boolean DEBUG = false;
+
     /**
      * Returns whether app is eligible for backup.
      *
@@ -88,7 +92,8 @@
     public static boolean appIsRunningAndEligibleForBackupWithTransport(
             @Nullable TransportClient transportClient, String packageName, PackageManager pm) {
         try {
-            PackageInfo packageInfo = pm.getPackageInfo(packageName, PackageManager.GET_SIGNATURES);
+            PackageInfo packageInfo = pm.getPackageInfo(packageName,
+                    PackageManager.GET_SIGNING_CERTIFICATES);
             ApplicationInfo applicationInfo = packageInfo.applicationInfo;
             if (!appIsEligibleForBackup(applicationInfo, pm)
                     || appIsStopped(applicationInfo)
@@ -165,13 +170,19 @@
      *
      * <ul>
      *   <li>Source and target have at least one signature each
-     *   <li>Target contains all signatures in source
+     *   <li>Target contains all signatures in source, and nothing more
      * </ul>
      *
+     * or if both source and target have exactly one signature, and they don't match, we check
+     * if the app was ever signed with source signature (i.e. app has rotated key)
+     * Note: key rotation is only supported for apps ever signed with one key, and those apps will
+     * not be allowed to be signed by more certificates in the future
+     *
      * Note that if {@param target} is null we return false.
      */
-    public static boolean signaturesMatch(Signature[] storedSigs, PackageInfo target) {
-        if (target == null) {
+    public static boolean signaturesMatch(Signature[] storedSigs, PackageInfo target,
+            PackageManagerInternal pmi) {
+        if (target == null || target.packageName == null) {
             return false;
         }
 
@@ -187,33 +198,52 @@
             return true;
         }
 
-        Signature[] deviceSigs = target.signatures;
-        if (MORE_DEBUG) {
-            Slog.v(TAG, "signaturesMatch(): stored=" + storedSigs + " device=" + deviceSigs);
-        }
-
         // Don't allow unsigned apps on either end
-        if (ArrayUtils.isEmpty(storedSigs) || ArrayUtils.isEmpty(deviceSigs)) {
+        if (ArrayUtils.isEmpty(storedSigs)) {
             return false;
         }
 
-        // Signatures can be added over time, so the target-device apk needs to contain all the
-        // source-device apk signatures, but not necessarily the other way around.
-        int nStored = storedSigs.length;
-        int nDevice = deviceSigs.length;
+        Signature[][] deviceHistorySigs = target.signingCertificateHistory;
+        if (ArrayUtils.isEmpty(deviceHistorySigs)) {
+            Slog.w(TAG, "signingCertificateHistory is empty, app was either unsigned or the flag" +
+                    " PackageManager#GET_SIGNING_CERTIFICATES was not specified");
+            return false;
+        }
 
-        for (int i = 0; i < nStored; i++) {
-            boolean match = false;
-            for (int j = 0; j < nDevice; j++) {
-                if (storedSigs[i].equals(deviceSigs[j])) {
-                    match = true;
-                    break;
+        if (DEBUG) {
+            Slog.v(TAG, "signaturesMatch(): stored=" + storedSigs + " device=" + deviceHistorySigs);
+        }
+
+        final int nStored = storedSigs.length;
+        if (nStored == 1) {
+            // if the app is only signed with one sig, it's possible it has rotated its key
+            // (the checks with signing history are delegated to PackageManager)
+            // TODO(b/73988180): address the case that app has declared restoreAnyVersion and is
+            // restoring from higher version to lower after having rotated the key (i.e. higher
+            // version has different sig than lower version that we want to restore to)
+            return pmi.isDataRestoreSafe(storedSigs[0], target.packageName);
+        } else {
+            // the app couldn't have rotated keys, since it was signed with multiple sigs - do
+            // a check to see if we find a match for all stored sigs
+            // since app hasn't rotated key, we only need to check with deviceHistorySigs[0]
+            Signature[] deviceSigs = deviceHistorySigs[0];
+            int nDevice = deviceSigs.length;
+
+            // ensure that each stored sig matches an on-device sig
+            for (int i = 0; i < nStored; i++) {
+                boolean match = false;
+                for (int j = 0; j < nDevice; j++) {
+                    if (storedSigs[i].equals(deviceSigs[j])) {
+                        match = true;
+                        break;
+                    }
+                }
+                if (!match) {
+                    return false;
                 }
             }
-            if (!match) {
-                return false;
-            }
+            // we have found a match for all stored sigs
+            return true;
         }
-        return true;
     }
 }
diff --git a/services/backup/java/com/android/server/backup/utils/FullBackupUtils.java b/services/backup/java/com/android/server/backup/utils/FullBackupUtils.java
index d2ab099..994d5a9 100644
--- a/services/backup/java/com/android/server/backup/utils/FullBackupUtils.java
+++ b/services/backup/java/com/android/server/backup/utils/FullBackupUtils.java
@@ -104,11 +104,16 @@
         printer.println((installerName != null) ? installerName : "");
 
         printer.println(withApk ? "1" : "0");
-        if (pkg.signatures == null) {
+
+        // write the signature block
+        Signature[][] signingHistory = pkg.signingCertificateHistory;
+        if (signingHistory == null) {
             printer.println("0");
         } else {
-            printer.println(Integer.toString(pkg.signatures.length));
-            for (Signature sig : pkg.signatures) {
+            // retrieve the newest sigs to write
+            Signature[] signatures = signingHistory[signingHistory.length - 1];
+            printer.println(Integer.toString(signatures.length));
+            for (Signature sig : signatures) {
                 printer.println(sig.toCharsString());
             }
         }
diff --git a/services/backup/java/com/android/server/backup/utils/RestoreUtils.java b/services/backup/java/com/android/server/backup/utils/RestoreUtils.java
index 10f0695..df7e6d4 100644
--- a/services/backup/java/com/android/server/backup/utils/RestoreUtils.java
+++ b/services/backup/java/com/android/server/backup/utils/RestoreUtils.java
@@ -30,6 +30,7 @@
 import android.content.pm.PackageInstaller.Session;
 import android.content.pm.PackageInstaller.SessionParams;
 import android.content.pm.PackageManager;
+import android.content.pm.PackageManagerInternal;
 import android.content.pm.Signature;
 import android.os.Bundle;
 import android.os.IBinder;
@@ -37,6 +38,7 @@
 import android.util.Slog;
 
 import com.android.internal.annotations.GuardedBy;
+import com.android.server.LocalServices;
 import com.android.server.backup.FileMetadata;
 import com.android.server.backup.restore.RestoreDeleteObserver;
 import com.android.server.backup.restore.RestorePolicy;
@@ -142,9 +144,8 @@
                     uninstall = true;
                 } else {
                     try {
-                        PackageInfo pkg = packageManager.getPackageInfo(
-                                info.packageName,
-                                PackageManager.GET_SIGNATURES);
+                        PackageInfo pkg = packageManager.getPackageInfo(info.packageName,
+                                PackageManager.GET_SIGNING_CERTIFICATES);
                         if ((pkg.applicationInfo.flags & ApplicationInfo.FLAG_ALLOW_BACKUP)
                                 == 0) {
                             Slog.w(TAG, "Restore stream contains apk of package "
@@ -154,7 +155,9 @@
                         } else {
                             // So far so good -- do the signatures match the manifest?
                             Signature[] sigs = manifestSignatures.get(info.packageName);
-                            if (AppBackupUtils.signaturesMatch(sigs, pkg)) {
+                            PackageManagerInternal pmi = LocalServices.getService(
+                                    PackageManagerInternal.class);
+                            if (AppBackupUtils.signaturesMatch(sigs, pkg, pmi)) {
                                 // If this is a system-uid app without a declared backup agent,
                                 // don't restore any of the file data.
                                 if ((pkg.applicationInfo.uid < Process.FIRST_APPLICATION_UID)
diff --git a/services/backup/java/com/android/server/backup/utils/TarBackupReader.java b/services/backup/java/com/android/server/backup/utils/TarBackupReader.java
index cc26ff8..6dd5284 100644
--- a/services/backup/java/com/android/server/backup/utils/TarBackupReader.java
+++ b/services/backup/java/com/android/server/backup/utils/TarBackupReader.java
@@ -50,6 +50,7 @@
 import android.content.pm.ApplicationInfo;
 import android.content.pm.PackageInfo;
 import android.content.pm.PackageManager;
+import android.content.pm.PackageManagerInternal;
 import android.content.pm.Signature;
 import android.os.Bundle;
 import android.os.Process;
@@ -385,7 +386,8 @@
      * @return a restore policy constant.
      */
     public RestorePolicy chooseRestorePolicy(PackageManager packageManager,
-            boolean allowApks, FileMetadata info, Signature[] signatures) {
+            boolean allowApks, FileMetadata info, Signature[] signatures,
+            PackageManagerInternal pmi) {
         if (signatures == null) {
             return RestorePolicy.IGNORE;
         }
@@ -395,7 +397,7 @@
         // Okay, got the manifest info we need...
         try {
             PackageInfo pkgInfo = packageManager.getPackageInfo(
-                    info.packageName, PackageManager.GET_SIGNATURES);
+                    info.packageName, PackageManager.GET_SIGNING_CERTIFICATES);
             // Fall through to IGNORE if the app explicitly disallows backup
             final int flags = pkgInfo.applicationInfo.flags;
             if ((flags & ApplicationInfo.FLAG_ALLOW_BACKUP) != 0) {
@@ -411,7 +413,7 @@
                     // such packages are signed with the platform cert instead of
                     // the app developer's cert, so they're different on every
                     // device.
-                    if (AppBackupUtils.signaturesMatch(signatures, pkgInfo)) {
+                    if (AppBackupUtils.signaturesMatch(signatures, pkgInfo, pmi)) {
                         if ((pkgInfo.applicationInfo.flags
                                 & ApplicationInfo.FLAG_RESTORE_ANY_VERSION) != 0) {
                             Slog.i(TAG, "Package has restoreAnyVersion; taking data");
diff --git a/services/core/java/com/android/server/backup/BackupUtils.java b/services/core/java/com/android/server/backup/BackupUtils.java
index e5d564d..d817534 100644
--- a/services/core/java/com/android/server/backup/BackupUtils.java
+++ b/services/core/java/com/android/server/backup/BackupUtils.java
@@ -18,9 +18,12 @@
 
 import android.content.pm.ApplicationInfo;
 import android.content.pm.PackageInfo;
+import android.content.pm.PackageManagerInternal;
 import android.content.pm.Signature;
 import android.util.Slog;
 
+import com.android.internal.util.ArrayUtils;
+
 import java.security.MessageDigest;
 import java.security.NoSuchAlgorithmException;
 import java.util.ArrayList;
@@ -30,13 +33,13 @@
 public class BackupUtils {
     private static final String TAG = "BackupUtils";
 
-    private static final boolean DEBUG = false; // STOPSHIP if true
+    private static final boolean DEBUG = false;
 
-    public static boolean signaturesMatch(ArrayList<byte[]> storedSigHashes, PackageInfo target) {
-        if (target == null) {
+    public static boolean signaturesMatch(ArrayList<byte[]> storedSigHashes, PackageInfo target,
+            PackageManagerInternal pmi) {
+        if (target == null || target.packageName == null) {
             return false;
         }
-
         // If the target resides on the system partition, we allow it to restore
         // data from the like-named package in a restore set even if the signatures
         // do not match.  (Unlike general applications, those flashed to the system
@@ -47,48 +50,53 @@
             return true;
         }
 
-        // Allow unsigned apps, but not signed on one device and unsigned on the other
-        // !!! TODO: is this the right policy?
-        Signature[] deviceSigs = target.signatures;
-        if (DEBUG) Slog.v(TAG, "signaturesMatch(): stored=" + storedSigHashes
-                + " device=" + deviceSigs);
-        if ((storedSigHashes == null || storedSigHashes.size() == 0)
-                && (deviceSigs == null || deviceSigs.length == 0)) {
-            return true;
-        }
-        if (storedSigHashes == null || deviceSigs == null) {
+        // Don't allow unsigned apps on either end
+        if (ArrayUtils.isEmpty(storedSigHashes)) {
             return false;
         }
 
-        // !!! TODO: this demands that every stored signature match one
-        // that is present on device, and does not demand the converse.
-        // Is this this right policy?
-        final int nStored = storedSigHashes.size();
-        final int nDevice = deviceSigs.length;
-
-        // hash each on-device signature
-        ArrayList<byte[]> deviceHashes = new ArrayList<byte[]>(nDevice);
-        for (int i = 0; i < nDevice; i++) {
-            deviceHashes.add(hashSignature(deviceSigs[i]));
+        Signature[][] deviceHistorySigs = target.signingCertificateHistory;
+        if (ArrayUtils.isEmpty(deviceHistorySigs)) {
+            Slog.w(TAG, "signingCertificateHistory is empty, app was either unsigned or the flag" +
+                    " PackageManager#GET_SIGNING_CERTIFICATES was not specified");
+            return false;
         }
 
-        // now ensure that each stored sig (hash) matches an on-device sig (hash)
-        for (int n = 0; n < nStored; n++) {
-            boolean match = false;
-            final byte[] storedHash = storedSigHashes.get(n);
-            for (int i = 0; i < nDevice; i++) {
-                if (Arrays.equals(storedHash, deviceHashes.get(i))) {
-                    match = true;
-                    break;
+        if (DEBUG) {
+            Slog.v(TAG, "signaturesMatch(): stored=" + storedSigHashes
+                    + " device=" + deviceHistorySigs);
+        }
+
+        final int nStored = storedSigHashes.size();
+        if (nStored == 1) {
+            // if the app is only signed with one sig, it's possible it has rotated its key
+            // the checks with signing history are delegated to PackageManager
+            // TODO(b/73988180): address the case that app has declared restoreAnyVersion and is
+            // restoring from higher version to lower after having rotated the key (i.e. higher
+            // version has different sig than lower version that we want to restore to)
+            return pmi.isDataRestoreSafe(storedSigHashes.get(0), target.packageName);
+        } else {
+            // the app couldn't have rotated keys, since it was signed with multiple sigs - do
+            // a check to see if we find a match for all stored sigs
+            // since app hasn't rotated key, we only need to check with deviceHistorySigs[0]
+            ArrayList<byte[]> deviceHashes = hashSignatureArray(deviceHistorySigs[0]);
+            int nDevice = deviceHashes.size();
+            // ensure that each stored sig matches an on-device sig
+            for (int i = 0; i < nStored; i++) {
+                boolean match = false;
+                for (int j = 0; j < nDevice; j++) {
+                    if (Arrays.equals(storedSigHashes.get(i), deviceHashes.get(j))) {
+                        match = true;
+                        break;
+                    }
+                }
+                if (!match) {
+                    return false;
                 }
             }
-            // match is false when no on-device sig matched one of the stored ones
-            if (!match) {
-                return false;
-            }
+            // we have found a match for all stored sigs
+            return true;
         }
-
-        return true;
     }
 
     public static byte[] hashSignature(byte[] signature) {
diff --git a/services/core/java/com/android/server/pm/PackageManagerService.java b/services/core/java/com/android/server/pm/PackageManagerService.java
index f0922b34..d9c0f2f 100644
--- a/services/core/java/com/android/server/pm/PackageManagerService.java
+++ b/services/core/java/com/android/server/pm/PackageManagerService.java
@@ -176,6 +176,7 @@
 import android.content.pm.PackageParser.PackageParserException;
 import android.content.pm.PackageParser.ParseFlags;
 import android.content.pm.PackageParser.ServiceIntentInfo;
+import android.content.pm.PackageParser.SigningDetails;
 import android.content.pm.PackageParser.SigningDetails.SignatureSchemeVersion;
 import android.content.pm.PackageStats;
 import android.content.pm.PackageUserState;
@@ -23383,6 +23384,36 @@
         }
 
         @Override
+        public boolean isDataRestoreSafe(byte[] restoringFromSigHash, String packageName) {
+            SigningDetails sd = getSigningDetails(packageName);
+            if (sd == null) {
+                return false;
+            }
+            return sd.hasSha256Certificate(restoringFromSigHash,
+                    SigningDetails.CertCapabilities.INSTALLED_DATA);
+        }
+
+        @Override
+        public boolean isDataRestoreSafe(Signature restoringFromSig, String packageName) {
+            SigningDetails sd = getSigningDetails(packageName);
+            if (sd == null) {
+                return false;
+            }
+            return sd.hasCertificate(restoringFromSig,
+                    SigningDetails.CertCapabilities.INSTALLED_DATA);
+        }
+
+        private SigningDetails getSigningDetails(@NonNull String packageName) {
+            synchronized (mPackages) {
+                PackageParser.Package p = mPackages.get(packageName);
+                if (p == null) {
+                    return null;
+                }
+                return p.mSigningDetails;
+            }
+        }
+
+        @Override
         public int getPermissionFlagsTEMP(String permName, String packageName, int userId) {
             return PackageManagerService.this.getPermissionFlags(permName, packageName, userId);
         }
diff --git a/services/core/java/com/android/server/pm/ShortcutPackageInfo.java b/services/core/java/com/android/server/pm/ShortcutPackageInfo.java
index 520ed25..eeaa333 100644
--- a/services/core/java/com/android/server/pm/ShortcutPackageInfo.java
+++ b/services/core/java/com/android/server/pm/ShortcutPackageInfo.java
@@ -18,10 +18,13 @@
 import android.annotation.NonNull;
 import android.annotation.UserIdInt;
 import android.content.pm.PackageInfo;
+import android.content.pm.PackageManagerInternal;
 import android.content.pm.ShortcutInfo;
+import android.content.pm.Signature;
 import android.util.Slog;
 
 import com.android.internal.annotations.VisibleForTesting;
+import com.android.server.LocalServices;
 import com.android.server.backup.BackupUtils;
 
 import libcore.util.HexEncoding;
@@ -137,7 +140,8 @@
 
     //@DisabledReason
     public int canRestoreTo(ShortcutService s, PackageInfo currentPackage, boolean anyVersionOkay) {
-        if (!BackupUtils.signaturesMatch(mSigHashes, currentPackage)) {
+        PackageManagerInternal pmi = LocalServices.getService(PackageManagerInternal.class);
+        if (!BackupUtils.signaturesMatch(mSigHashes, currentPackage, pmi)) {
             Slog.w(TAG, "Can't restore: Package signature mismatch");
             return ShortcutInfo.DISABLED_REASON_SIGNATURE_MISMATCH;
         }
@@ -159,13 +163,15 @@
     public static ShortcutPackageInfo generateForInstalledPackageForTest(
             ShortcutService s, String packageName, @UserIdInt int packageUserId) {
         final PackageInfo pi = s.getPackageInfoWithSignatures(packageName, packageUserId);
-        if (pi.signatures == null || pi.signatures.length == 0) {
+        // retrieve the newest sigs
+        Signature[][] signingHistory = pi.signingCertificateHistory;
+        if (signingHistory == null || signingHistory.length == 0) {
             Slog.e(TAG, "Can't get signatures: package=" + packageName);
             return null;
         }
+        Signature[] signatures = signingHistory[signingHistory.length - 1];
         final ShortcutPackageInfo ret = new ShortcutPackageInfo(pi.getLongVersionCode(),
-                pi.lastUpdateTime, BackupUtils.hashSignatureArray(pi.signatures),
-                /* shadow=*/ false);
+                pi.lastUpdateTime, BackupUtils.hashSignatureArray(signatures), /* shadow=*/ false);
 
         ret.mBackupSourceBackupAllowed = s.shouldBackupApp(pi);
         ret.mBackupSourceVersionCode = pi.getLongVersionCode();
@@ -185,7 +191,15 @@
             Slog.w(TAG, "Package not found: " + pkg.getPackageName());
             return;
         }
-        mSigHashes = BackupUtils.hashSignatureArray(pi.signatures);
+        // retrieve the newest sigs
+        Signature[][] signingHistory = pi.signingCertificateHistory;
+        if (signingHistory == null || signingHistory.length == 0) {
+            Slog.w(TAG, "Not refreshing signature for " + pkg.getPackageName()
+                    + " since it appears to have no signature history.");
+            return;
+        }
+        Signature[] signatures = signingHistory[signingHistory.length - 1];
+        mSigHashes = BackupUtils.hashSignatureArray(signatures);
     }
 
     public void saveToXml(ShortcutService s, XmlSerializer out, boolean forBackup)
@@ -221,7 +235,6 @@
 
     public void loadFromXml(XmlPullParser parser, boolean fromBackup)
             throws IOException, XmlPullParserException {
-
         // Don't use the version code from the backup file.
         final long versionCode = ShortcutService.parseLongAttribute(parser, ATTR_VERSION,
                 ShortcutInfo.VERSION_CODE_UNKNOWN);
diff --git a/services/core/java/com/android/server/pm/ShortcutService.java b/services/core/java/com/android/server/pm/ShortcutService.java
index 265cc8e..15b4617 100644
--- a/services/core/java/com/android/server/pm/ShortcutService.java
+++ b/services/core/java/com/android/server/pm/ShortcutService.java
@@ -3121,7 +3121,8 @@
         try {
             return mIPackageManager.getPackageInfo(
                     packageName, PACKAGE_MATCH_FLAGS
-                            | (getSignatures ? PackageManager.GET_SIGNATURES : 0), userId);
+                            | (getSignatures ? PackageManager.GET_SIGNING_CERTIFICATES : 0),
+                    userId);
         } catch (RemoteException e) {
             // Shouldn't happen.
             Slog.wtf(TAG, "RemoteException", e);
diff --git a/services/tests/servicestests/src/com/android/server/backup/utils/AppBackupUtilsTest.java b/services/tests/servicestests/src/com/android/server/backup/utils/AppBackupUtilsTest.java
index 86c83d6..d37db20 100644
--- a/services/tests/servicestests/src/com/android/server/backup/utils/AppBackupUtilsTest.java
+++ b/services/tests/servicestests/src/com/android/server/backup/utils/AppBackupUtilsTest.java
@@ -18,9 +18,14 @@
 
 import static com.google.common.truth.Truth.assertThat;
 
+import static org.mockito.Mockito.doReturn;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.when;
+
 import android.content.pm.ApplicationInfo;
 import android.content.pm.PackageInfo;
 import android.content.pm.PackageManager;
+import android.content.pm.PackageManagerInternal;
 import android.content.pm.Signature;
 import android.os.Process;
 import android.platform.test.annotations.Presubmit;
@@ -30,6 +35,7 @@
 import com.android.server.backup.BackupManagerService;
 import com.android.server.backup.testutils.PackageManagerStub;
 
+import org.junit.Before;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 
@@ -45,7 +51,14 @@
     private static final Signature SIGNATURE_3 = generateSignature((byte) 3);
     private static final Signature SIGNATURE_4 = generateSignature((byte) 4);
 
-    private final PackageManagerStub mPackageManagerStub = new PackageManagerStub();
+    private PackageManagerStub mPackageManagerStub;
+    private PackageManagerInternal mMockPackageManagerInternal;
+
+    @Before
+    public void setUp() throws Exception {
+        mPackageManagerStub = new PackageManagerStub();
+        mMockPackageManagerInternal = mock(PackageManagerInternal.class);
+    }
 
     @Test
     public void appIsEligibleForBackup_backupNotAllowed_returnsFalse() throws Exception {
@@ -358,7 +371,8 @@
 
     @Test
     public void signaturesMatch_targetIsNull_returnsFalse() throws Exception {
-        boolean result = AppBackupUtils.signaturesMatch(new Signature[] {SIGNATURE_1}, null);
+        boolean result = AppBackupUtils.signaturesMatch(new Signature[] {SIGNATURE_1}, null,
+                mMockPackageManagerInternal);
 
         assertThat(result).isFalse();
     }
@@ -366,10 +380,12 @@
     @Test
     public void signaturesMatch_systemApplication_returnsTrue() throws Exception {
         PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
         packageInfo.applicationInfo = new ApplicationInfo();
         packageInfo.applicationInfo.flags |= ApplicationInfo.FLAG_SYSTEM;
 
-        boolean result = AppBackupUtils.signaturesMatch(new Signature[0], packageInfo);
+        boolean result = AppBackupUtils.signaturesMatch(new Signature[0], packageInfo,
+                mMockPackageManagerInternal);
 
         assertThat(result).isTrue();
     }
@@ -378,10 +394,12 @@
     public void signaturesMatch_disallowsUnsignedApps_storedSignatureNull_returnsFalse()
             throws Exception {
         PackageInfo packageInfo = new PackageInfo();
-        packageInfo.signatures = new Signature[] {SIGNATURE_1};
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[][] {{SIGNATURE_1}};
         packageInfo.applicationInfo = new ApplicationInfo();
 
-        boolean result = AppBackupUtils.signaturesMatch(null, packageInfo);
+        boolean result = AppBackupUtils.signaturesMatch(null, packageInfo,
+                mMockPackageManagerInternal);
 
         assertThat(result).isFalse();
     }
@@ -390,10 +408,12 @@
     public void signaturesMatch_disallowsUnsignedApps_storedSignatureEmpty_returnsFalse()
             throws Exception {
         PackageInfo packageInfo = new PackageInfo();
-        packageInfo.signatures = new Signature[] {SIGNATURE_1};
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[][] {{SIGNATURE_1}};
         packageInfo.applicationInfo = new ApplicationInfo();
 
-        boolean result = AppBackupUtils.signaturesMatch(new Signature[0], packageInfo);
+        boolean result = AppBackupUtils.signaturesMatch(new Signature[0], packageInfo,
+                mMockPackageManagerInternal);
 
         assertThat(result).isFalse();
     }
@@ -404,11 +424,12 @@
     signaturesMatch_disallowsUnsignedApps_targetSignatureEmpty_returnsFalse()
             throws Exception {
         PackageInfo packageInfo = new PackageInfo();
-        packageInfo.signatures = new Signature[0];
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[0][0];
         packageInfo.applicationInfo = new ApplicationInfo();
 
-        boolean result = AppBackupUtils.signaturesMatch(new Signature[] {SIGNATURE_1},
-                packageInfo);
+        boolean result = AppBackupUtils.signaturesMatch(new Signature[] {SIGNATURE_1}, packageInfo,
+                mMockPackageManagerInternal);
 
         assertThat(result).isFalse();
     }
@@ -418,11 +439,12 @@
     signaturesMatch_disallowsUnsignedApps_targetSignatureNull_returnsFalse()
             throws Exception {
         PackageInfo packageInfo = new PackageInfo();
-        packageInfo.signatures = null;
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = null;
         packageInfo.applicationInfo = new ApplicationInfo();
 
-        boolean result = AppBackupUtils.signaturesMatch(new Signature[] {SIGNATURE_1},
-                packageInfo);
+        boolean result = AppBackupUtils.signaturesMatch(new Signature[] {SIGNATURE_1}, packageInfo,
+                mMockPackageManagerInternal);
 
         assertThat(result).isFalse();
     }
@@ -431,10 +453,11 @@
     public void signaturesMatch_disallowsUnsignedApps_bothSignaturesNull_returnsFalse()
             throws Exception {
         PackageInfo packageInfo = new PackageInfo();
-        packageInfo.signatures = null;
+        packageInfo.signingCertificateHistory = null;
         packageInfo.applicationInfo = new ApplicationInfo();
 
-        boolean result = AppBackupUtils.signaturesMatch(null, packageInfo);
+        boolean result = AppBackupUtils.signaturesMatch(null, packageInfo,
+                mMockPackageManagerInternal);
 
         assertThat(result).isFalse();
     }
@@ -443,10 +466,12 @@
     public void signaturesMatch_disallowsUnsignedApps_bothSignaturesEmpty_returnsFalse()
             throws Exception {
         PackageInfo packageInfo = new PackageInfo();
-        packageInfo.signatures = new Signature[0];
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[0][0];
         packageInfo.applicationInfo = new ApplicationInfo();
 
-        boolean result = AppBackupUtils.signaturesMatch(new Signature[0], packageInfo);
+        boolean result = AppBackupUtils.signaturesMatch(new Signature[0], packageInfo,
+                mMockPackageManagerInternal);
 
         assertThat(result).isFalse();
     }
@@ -458,11 +483,15 @@
         Signature signature3Copy = new Signature(SIGNATURE_3.toByteArray());
 
         PackageInfo packageInfo = new PackageInfo();
-        packageInfo.signatures = new Signature[]{SIGNATURE_1, SIGNATURE_2, SIGNATURE_3};
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[][] {
+                {SIGNATURE_1, SIGNATURE_2, SIGNATURE_3}
+        };
         packageInfo.applicationInfo = new ApplicationInfo();
 
         boolean result = AppBackupUtils.signaturesMatch(
-                new Signature[]{signature3Copy, signature1Copy, signature2Copy}, packageInfo);
+                new Signature[] {signature3Copy, signature1Copy, signature2Copy}, packageInfo,
+                mMockPackageManagerInternal);
 
         assertThat(result).isTrue();
     }
@@ -473,11 +502,15 @@
         Signature signature2Copy = new Signature(SIGNATURE_2.toByteArray());
 
         PackageInfo packageInfo = new PackageInfo();
-        packageInfo.signatures = new Signature[]{SIGNATURE_1, SIGNATURE_2, SIGNATURE_3};
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[][] {
+                {SIGNATURE_1, SIGNATURE_2, SIGNATURE_3}
+        };
         packageInfo.applicationInfo = new ApplicationInfo();
 
         boolean result = AppBackupUtils.signaturesMatch(
-                new Signature[]{signature2Copy, signature1Copy}, packageInfo);
+                new Signature[]{signature2Copy, signature1Copy}, packageInfo,
+                mMockPackageManagerInternal);
 
         assertThat(result).isTrue();
     }
@@ -488,11 +521,15 @@
         Signature signature2Copy = new Signature(SIGNATURE_2.toByteArray());
 
         PackageInfo packageInfo = new PackageInfo();
-        packageInfo.signatures = new Signature[]{signature1Copy, signature2Copy};
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[][] {
+                {signature1Copy, signature2Copy}
+        };
         packageInfo.applicationInfo = new ApplicationInfo();
 
         boolean result = AppBackupUtils.signaturesMatch(
-                new Signature[]{SIGNATURE_1, SIGNATURE_2, SIGNATURE_3}, packageInfo);
+                new Signature[]{SIGNATURE_1, SIGNATURE_2, SIGNATURE_3}, packageInfo,
+                mMockPackageManagerInternal);
 
         assertThat(result).isFalse();
     }
@@ -503,11 +540,77 @@
         Signature signature2Copy = new Signature(SIGNATURE_2.toByteArray());
 
         PackageInfo packageInfo = new PackageInfo();
-        packageInfo.signatures = new Signature[]{SIGNATURE_1, SIGNATURE_2, SIGNATURE_3};
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[][] {
+                {SIGNATURE_1, SIGNATURE_2, SIGNATURE_3}
+        };
         packageInfo.applicationInfo = new ApplicationInfo();
 
         boolean result = AppBackupUtils.signaturesMatch(
-                new Signature[]{signature1Copy, signature2Copy, SIGNATURE_4}, packageInfo);
+                new Signature[]{signature1Copy, signature2Copy, SIGNATURE_4}, packageInfo,
+                mMockPackageManagerInternal);
+
+        assertThat(result).isFalse();
+    }
+
+    @Test
+    public void signaturesMatch_singleStoredSignatureNoRotation_returnsTrue()
+            throws Exception {
+        Signature signature1Copy = new Signature(SIGNATURE_1.toByteArray());
+
+        PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[][] {{SIGNATURE_1}};
+        packageInfo.applicationInfo = new ApplicationInfo();
+
+        doReturn(true).when(mMockPackageManagerInternal).isDataRestoreSafe(signature1Copy,
+                packageInfo.packageName);
+
+        boolean result = AppBackupUtils.signaturesMatch(new Signature[] {signature1Copy},
+                packageInfo, mMockPackageManagerInternal);
+
+        assertThat(result).isTrue();
+    }
+
+    @Test
+    public void signaturesMatch_singleStoredSignatureWithRotationAssumeDataCapability_returnsTrue()
+            throws Exception {
+        Signature signature1Copy = new Signature(SIGNATURE_1.toByteArray());
+
+        PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[][] {{SIGNATURE_1}, {SIGNATURE_2}};
+        packageInfo.applicationInfo = new ApplicationInfo();
+
+        // we know signature1Copy is in history, and we want to assume it has
+        // SigningDetails.CertCapabilities.INSTALLED_DATA capability
+        doReturn(true).when(mMockPackageManagerInternal).isDataRestoreSafe(signature1Copy,
+                packageInfo.packageName);
+
+        boolean result = AppBackupUtils.signaturesMatch(new Signature[] {signature1Copy},
+                packageInfo, mMockPackageManagerInternal);
+
+        assertThat(result).isTrue();
+    }
+
+    @Test
+    public void
+            signaturesMatch_singleStoredSignatureWithRotationAssumeNoDataCapability_returnsFalse()
+            throws Exception {
+        Signature signature1Copy = new Signature(SIGNATURE_1.toByteArray());
+
+        PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[][] {{SIGNATURE_1}, {SIGNATURE_2}};
+        packageInfo.applicationInfo = new ApplicationInfo();
+
+        // we know signature1Copy is in history, but we want to assume it does not have
+        // SigningDetails.CertCapabilities.INSTALLED_DATA capability
+        doReturn(false).when(mMockPackageManagerInternal).isDataRestoreSafe(signature1Copy,
+                packageInfo.packageName);
+
+        boolean result = AppBackupUtils.signaturesMatch(new Signature[] {signature1Copy},
+                packageInfo, mMockPackageManagerInternal);
 
         assertThat(result).isFalse();
     }
diff --git a/services/tests/servicestests/src/com/android/server/backup/utils/TarBackupReaderTest.java b/services/tests/servicestests/src/com/android/server/backup/utils/TarBackupReaderTest.java
index 0cdf04b..5f052ce 100644
--- a/services/tests/servicestests/src/com/android/server/backup/utils/TarBackupReaderTest.java
+++ b/services/tests/servicestests/src/com/android/server/backup/utils/TarBackupReaderTest.java
@@ -28,6 +28,9 @@
 
 import static com.google.common.truth.Truth.assertThat;
 
+import static org.mockito.Mockito.doReturn;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.when;
 import static org.mockito.Mockito.verify;
 import static org.mockito.Mockito.verifyNoMoreInteractions;
 import static org.mockito.Mockito.verifyZeroInteractions;
@@ -37,6 +40,7 @@
 import android.content.Context;
 import android.content.pm.ApplicationInfo;
 import android.content.pm.PackageInfo;
+import android.content.pm.PackageManagerInternal;
 import android.content.pm.Signature;
 import android.os.Bundle;
 import android.os.Process;
@@ -79,6 +83,7 @@
 
     @Mock private BytesReadListener mBytesReadListenerMock;
     @Mock private IBackupManagerMonitor mBackupManagerMonitorMock;
+    @Mock private PackageManagerInternal mMockPackageManagerInternal;
 
     private final PackageManagerStub mPackageManagerStub = new PackageManagerStub();
     private Context mContext;
@@ -139,7 +144,8 @@
         Signature[] signatures = tarBackupReader.readAppManifestAndReturnSignatures(
                 fileMetadata);
         RestorePolicy restorePolicy = tarBackupReader.chooseRestorePolicy(
-                mPackageManagerStub, false /* allowApks */, fileMetadata, signatures);
+                mPackageManagerStub, false /* allowApks */, fileMetadata, signatures,
+                mMockPackageManagerInternal);
 
         assertThat(restorePolicy).isEqualTo(RestorePolicy.IGNORE);
         assertThat(fileMetadata.packageName).isEqualTo(TEST_PACKAGE_NAME);
@@ -152,7 +158,8 @@
         signatures = tarBackupReader.readAppManifestAndReturnSignatures(
                 fileMetadata);
         restorePolicy = tarBackupReader.chooseRestorePolicy(
-                mPackageManagerStub, false /* allowApks */, fileMetadata, signatures);
+                mPackageManagerStub, false /* allowApks */, fileMetadata, signatures,
+                mMockPackageManagerInternal);
 
         assertThat(restorePolicy).isEqualTo(RestorePolicy.IGNORE);
         assertThat(fileMetadata.packageName).isEqualTo(TEST_PACKAGE_NAME);
@@ -214,7 +221,8 @@
                 mBytesReadListenerMock, mBackupManagerMonitorMock);
 
         RestorePolicy policy = tarBackupReader.chooseRestorePolicy(mPackageManagerStub,
-                true /* allowApks */, new FileMetadata(), null /* signatures */);
+                true /* allowApks */, new FileMetadata(), null /* signatures */,
+                mMockPackageManagerInternal);
 
         assertThat(policy).isEqualTo(RestorePolicy.IGNORE);
         verifyZeroInteractions(mBackupManagerMonitorMock);
@@ -234,7 +242,8 @@
         PackageManagerStub.sPackageInfo = null;
 
         RestorePolicy policy = tarBackupReader.chooseRestorePolicy(mPackageManagerStub,
-                true /* allowApks */, info, new Signature[0] /* signatures */);
+                true /* allowApks */, info, new Signature[0] /* signatures */,
+                mMockPackageManagerInternal);
 
         assertThat(policy).isEqualTo(RestorePolicy.ACCEPT_IF_APK);
         ArgumentCaptor<Bundle> bundleCaptor = ArgumentCaptor.forClass(Bundle.class);
@@ -258,7 +267,8 @@
         PackageManagerStub.sPackageInfo = null;
 
         RestorePolicy policy = tarBackupReader.chooseRestorePolicy(mPackageManagerStub,
-                true /* allowApks */, info, new Signature[0] /* signatures */);
+                true /* allowApks */, info, new Signature[0] /* signatures */,
+                mMockPackageManagerInternal);
 
         assertThat(policy).isEqualTo(RestorePolicy.ACCEPT_IF_APK);
         ArgumentCaptor<Bundle> bundleCaptor = ArgumentCaptor.forClass(Bundle.class);
@@ -283,7 +293,8 @@
         PackageManagerStub.sPackageInfo = null;
 
         RestorePolicy policy = tarBackupReader.chooseRestorePolicy(mPackageManagerStub,
-                false /* allowApks */, new FileMetadata(), new Signature[0] /* signatures */);
+                false /* allowApks */, new FileMetadata(), new Signature[0] /* signatures */,
+                mMockPackageManagerInternal);
 
         assertThat(policy).isEqualTo(RestorePolicy.IGNORE);
         ArgumentCaptor<Bundle> bundleCaptor = ArgumentCaptor.forClass(Bundle.class);
@@ -307,7 +318,8 @@
         PackageManagerStub.sPackageInfo = packageInfo;
 
         RestorePolicy policy = tarBackupReader.chooseRestorePolicy(mPackageManagerStub,
-                false /* allowApks */, new FileMetadata(), new Signature[0] /* signatures */);
+                false /* allowApks */, new FileMetadata(), new Signature[0] /* signatures */,
+                mMockPackageManagerInternal);
 
         assertThat(policy).isEqualTo(RestorePolicy.IGNORE);
         ArgumentCaptor<Bundle> bundleCaptor = ArgumentCaptor.forClass(Bundle.class);
@@ -333,7 +345,8 @@
         PackageManagerStub.sPackageInfo = packageInfo;
 
         RestorePolicy policy = tarBackupReader.chooseRestorePolicy(mPackageManagerStub,
-                false /* allowApks */, new FileMetadata(), new Signature[0] /* signatures */);
+                false /* allowApks */, new FileMetadata(), new Signature[0] /* signatures */,
+                mMockPackageManagerInternal);
 
         assertThat(policy).isEqualTo(RestorePolicy.IGNORE);
         ArgumentCaptor<Bundle> bundleCaptor = ArgumentCaptor.forClass(Bundle.class);
@@ -358,11 +371,11 @@
         packageInfo.applicationInfo.flags |= ApplicationInfo.FLAG_ALLOW_BACKUP;
         packageInfo.applicationInfo.uid = Process.FIRST_APPLICATION_UID;
         packageInfo.applicationInfo.backupAgentName = null;
-        packageInfo.signatures = new Signature[]{FAKE_SIGNATURE_2};
+        packageInfo.signingCertificateHistory = new Signature[][] {{FAKE_SIGNATURE_2}};
         PackageManagerStub.sPackageInfo = packageInfo;
 
         RestorePolicy policy = tarBackupReader.chooseRestorePolicy(mPackageManagerStub,
-                false /* allowApks */, new FileMetadata(), signatures);
+                false /* allowApks */, new FileMetadata(), signatures, mMockPackageManagerInternal);
 
         assertThat(policy).isEqualTo(RestorePolicy.IGNORE);
         ArgumentCaptor<Bundle> bundleCaptor = ArgumentCaptor.forClass(Bundle.class);
@@ -383,16 +396,19 @@
         Signature[] signatures = new Signature[]{FAKE_SIGNATURE_1};
 
         PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
         packageInfo.applicationInfo = new ApplicationInfo();
         packageInfo.applicationInfo.flags |=
                 ApplicationInfo.FLAG_ALLOW_BACKUP | ApplicationInfo.FLAG_RESTORE_ANY_VERSION;
         packageInfo.applicationInfo.uid = Process.SYSTEM_UID;
         packageInfo.applicationInfo.backupAgentName = "backup.agent";
-        packageInfo.signatures = new Signature[]{FAKE_SIGNATURE_1};
+        packageInfo.signingCertificateHistory = new Signature[][] {{FAKE_SIGNATURE_1}};
         PackageManagerStub.sPackageInfo = packageInfo;
 
+        doReturn(true).when(mMockPackageManagerInternal).isDataRestoreSafe(FAKE_SIGNATURE_1,
+                packageInfo.packageName);
         RestorePolicy policy = tarBackupReader.chooseRestorePolicy(mPackageManagerStub,
-                false /* allowApks */, new FileMetadata(), signatures);
+                false /* allowApks */, new FileMetadata(), signatures, mMockPackageManagerInternal);
 
         assertThat(policy).isEqualTo(RestorePolicy.ACCEPT);
         ArgumentCaptor<Bundle> bundleCaptor = ArgumentCaptor.forClass(Bundle.class);
@@ -412,16 +428,19 @@
         Signature[] signatures = new Signature[]{FAKE_SIGNATURE_1};
 
         PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
         packageInfo.applicationInfo = new ApplicationInfo();
         packageInfo.applicationInfo.flags |=
                 ApplicationInfo.FLAG_ALLOW_BACKUP | ApplicationInfo.FLAG_RESTORE_ANY_VERSION;
         packageInfo.applicationInfo.uid = Process.FIRST_APPLICATION_UID;
         packageInfo.applicationInfo.backupAgentName = null;
-        packageInfo.signatures = new Signature[]{FAKE_SIGNATURE_1};
+        packageInfo.signingCertificateHistory = new Signature[][] {{FAKE_SIGNATURE_1}};
         PackageManagerStub.sPackageInfo = packageInfo;
 
+        doReturn(true).when(mMockPackageManagerInternal).isDataRestoreSafe(FAKE_SIGNATURE_1,
+                packageInfo.packageName);
         RestorePolicy policy = tarBackupReader.chooseRestorePolicy(mPackageManagerStub,
-                false /* allowApks */, new FileMetadata(), signatures);
+                false /* allowApks */, new FileMetadata(), signatures, mMockPackageManagerInternal);
 
         assertThat(policy).isEqualTo(RestorePolicy.ACCEPT);
         ArgumentCaptor<Bundle> bundleCaptor = ArgumentCaptor.forClass(Bundle.class);
@@ -444,17 +463,20 @@
         info.version = 1;
 
         PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
         packageInfo.applicationInfo = new ApplicationInfo();
         packageInfo.applicationInfo.flags |= ApplicationInfo.FLAG_ALLOW_BACKUP;
         packageInfo.applicationInfo.flags &= ~ApplicationInfo.FLAG_RESTORE_ANY_VERSION;
         packageInfo.applicationInfo.uid = Process.FIRST_APPLICATION_UID;
         packageInfo.applicationInfo.backupAgentName = null;
-        packageInfo.signatures = new Signature[]{FAKE_SIGNATURE_1};
+        packageInfo.signingCertificateHistory = new Signature[][] {{FAKE_SIGNATURE_1}};
         packageInfo.versionCode = 2;
         PackageManagerStub.sPackageInfo = packageInfo;
 
+        doReturn(true).when(mMockPackageManagerInternal).isDataRestoreSafe(FAKE_SIGNATURE_1,
+                packageInfo.packageName);
         RestorePolicy policy = tarBackupReader.chooseRestorePolicy(mPackageManagerStub,
-                false /* allowApks */, info, signatures);
+                false /* allowApks */, info, signatures, mMockPackageManagerInternal);
 
         assertThat(policy).isEqualTo(RestorePolicy.ACCEPT);
         ArgumentCaptor<Bundle> bundleCaptor = ArgumentCaptor.forClass(Bundle.class);
@@ -479,17 +501,20 @@
         info.hasApk = true;
 
         PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
         packageInfo.applicationInfo = new ApplicationInfo();
         packageInfo.applicationInfo.flags |= ApplicationInfo.FLAG_ALLOW_BACKUP;
         packageInfo.applicationInfo.flags &= ~ApplicationInfo.FLAG_RESTORE_ANY_VERSION;
         packageInfo.applicationInfo.uid = Process.FIRST_APPLICATION_UID;
         packageInfo.applicationInfo.backupAgentName = null;
-        packageInfo.signatures = new Signature[]{FAKE_SIGNATURE_1};
+        packageInfo.signingCertificateHistory = new Signature[][] {{FAKE_SIGNATURE_1}};
         packageInfo.versionCode = 1;
         PackageManagerStub.sPackageInfo = packageInfo;
 
+        doReturn(true).when(mMockPackageManagerInternal).isDataRestoreSafe(FAKE_SIGNATURE_1,
+                packageInfo.packageName);
         RestorePolicy policy = tarBackupReader.chooseRestorePolicy(mPackageManagerStub,
-                true /* allowApks */, info, signatures);
+                true /* allowApks */, info, signatures, mMockPackageManagerInternal);
 
         assertThat(policy).isEqualTo(RestorePolicy.ACCEPT_IF_APK);
         verifyNoMoreInteractions(mBackupManagerMonitorMock);
@@ -510,17 +535,20 @@
         info.version = 2;
 
         PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
         packageInfo.applicationInfo = new ApplicationInfo();
         packageInfo.applicationInfo.flags |= ApplicationInfo.FLAG_ALLOW_BACKUP;
         packageInfo.applicationInfo.flags &= ~ApplicationInfo.FLAG_RESTORE_ANY_VERSION;
         packageInfo.applicationInfo.uid = Process.FIRST_APPLICATION_UID;
         packageInfo.applicationInfo.backupAgentName = null;
-        packageInfo.signatures = new Signature[]{FAKE_SIGNATURE_1};
+        packageInfo.signingCertificateHistory = new Signature[][] {{FAKE_SIGNATURE_1}};
         packageInfo.versionCode = 1;
         PackageManagerStub.sPackageInfo = packageInfo;
 
+        doReturn(true).when(mMockPackageManagerInternal).isDataRestoreSafe(FAKE_SIGNATURE_1,
+                packageInfo.packageName);
         RestorePolicy policy = tarBackupReader.chooseRestorePolicy(mPackageManagerStub,
-                false /* allowApks */, info, signatures);
+                false /* allowApks */, info, signatures, mMockPackageManagerInternal);
 
         assertThat(policy).isEqualTo(RestorePolicy.IGNORE);
         ArgumentCaptor<Bundle> bundleCaptor = ArgumentCaptor.forClass(Bundle.class);
diff --git a/services/tests/servicestests/src/com/android/server/pm/BaseShortcutManagerTest.java b/services/tests/servicestests/src/com/android/server/pm/BaseShortcutManagerTest.java
index 51d27fe..1974750 100644
--- a/services/tests/servicestests/src/com/android/server/pm/BaseShortcutManagerTest.java
+++ b/services/tests/servicestests/src/com/android/server/pm/BaseShortcutManagerTest.java
@@ -1015,7 +1015,8 @@
                 | ApplicationInfo.FLAG_ALLOW_BACKUP;
         pi.versionCode = version;
         pi.applicationInfo.versionCode = version;
-        pi.signatures = genSignatures(signatures);
+        pi.signatures = null;
+        pi.signingCertificateHistory = new Signature[][] {genSignatures(signatures)};
 
         return pi;
     }
@@ -1103,7 +1104,8 @@
                 !mDisabledPackages.contains(PackageWithUser.of(userId, packageName));
 
         if (getSignatures) {
-            ret.signatures = pi.signatures;
+            ret.signatures = null;
+            ret.signingCertificateHistory = pi.signingCertificateHistory;
         }
 
         return ret;
diff --git a/services/tests/servicestests/src/com/android/server/pm/ShortcutManagerTest1.java b/services/tests/servicestests/src/com/android/server/pm/ShortcutManagerTest1.java
index 845e05d..7815004 100644
--- a/services/tests/servicestests/src/com/android/server/pm/ShortcutManagerTest1.java
+++ b/services/tests/servicestests/src/com/android/server/pm/ShortcutManagerTest1.java
@@ -62,6 +62,7 @@
 
 import static org.mockito.Matchers.any;
 import static org.mockito.Matchers.anyInt;
+import static org.mockito.Matchers.anyString;
 import static org.mockito.Matchers.eq;
 import static org.mockito.Mockito.doReturn;
 import static org.mockito.Mockito.mock;
@@ -3987,6 +3988,10 @@
         if (!nowBackupAllowed) {
             pi.applicationInfo.flags &= ~ApplicationInfo.FLAG_ALLOW_BACKUP;
         }
+
+        doReturn(expected != DISABLED_REASON_SIGNATURE_MISMATCH).when(
+                mMockPackageManagerInternal).isDataRestoreSafe(any(byte[].class), anyString());
+
         assertEquals(expected, spi.canRestoreTo(mService, pi, anyVersionOk));
     }
 
@@ -4959,6 +4964,9 @@
         assertNull(user0.getAllLaunchersForTest().get(PackageWithUser.of(USER_0, LAUNCHER_3)));
         assertNull(user0.getAllLaunchersForTest().get(PackageWithUser.of(USER_P0, LAUNCHER_1)));
 
+        doReturn(true).when(mMockPackageManagerInternal).isDataRestoreSafe(any(byte[].class),
+                anyString());
+
         installPackage(USER_0, CALLING_PACKAGE_1);
         runWithCaller(CALLING_PACKAGE_1, USER_0, () -> {
             assertWith(getCallerVisibleShortcuts())
@@ -5151,6 +5159,10 @@
 
     protected void checkBackupAndRestore_publisherNotRestored(
             int package1DisabledReason) {
+        doReturn(package1DisabledReason != ShortcutInfo.DISABLED_REASON_SIGNATURE_MISMATCH).when(
+                mMockPackageManagerInternal).isDataRestoreSafe(any(byte[].class),
+                eq(CALLING_PACKAGE_1));
+
         installPackage(USER_0, CALLING_PACKAGE_1);
         runWithCaller(CALLING_PACKAGE_1, USER_0, () -> {
             assertEquals(0, mManager.getDynamicShortcuts().size());
@@ -5159,6 +5171,8 @@
         assertFalse(mService.getPackageShortcutForTest(CALLING_PACKAGE_1, USER_0)
                 .getPackageInfo().isShadow());
 
+        doReturn(true).when(mMockPackageManagerInternal).isDataRestoreSafe(
+                any(byte[].class), anyString());
 
         installPackage(USER_0, CALLING_PACKAGE_2);
         runWithCaller(CALLING_PACKAGE_2, USER_0, () -> {
@@ -5276,7 +5290,7 @@
 
         addPackage(LAUNCHER_1, LAUNCHER_UID_1, 10, "sigx"); // different signature
 
-        checkBackupAndRestore_launcherNotRestored();
+        checkBackupAndRestore_launcherNotRestored(true);
     }
 
     public void testBackupAndRestore_launcherNoLongerBackupTarget() {
@@ -5285,10 +5299,13 @@
         updatePackageInfo(LAUNCHER_1,
                 pi -> pi.applicationInfo.flags &= ~ApplicationInfo.FLAG_ALLOW_BACKUP);
 
-        checkBackupAndRestore_launcherNotRestored();
+        checkBackupAndRestore_launcherNotRestored(false);
     }
 
-    protected void checkBackupAndRestore_launcherNotRestored() {
+    protected void checkBackupAndRestore_launcherNotRestored(boolean differentSignatures) {
+        doReturn(true).when(mMockPackageManagerInternal).isDataRestoreSafe(
+                any(byte[].class), anyString());
+
         installPackage(USER_0, CALLING_PACKAGE_1);
         runWithCaller(CALLING_PACKAGE_1, USER_0, () -> {
             assertEquals(0, mManager.getDynamicShortcuts().size());
@@ -5307,6 +5324,9 @@
                     "s1", "s2", "s3");
         });
 
+        doReturn(!differentSignatures).when(mMockPackageManagerInternal).isDataRestoreSafe(
+                any(byte[].class), eq(LAUNCHER_1));
+
         // Now we try to restore launcher 1.  Then we realize it's not restorable, so L1 has no pinned
         // shortcuts.
         installPackage(USER_0, LAUNCHER_1);
@@ -5333,6 +5353,9 @@
                     "s2");
         });
 
+        doReturn(true).when(mMockPackageManagerInternal).isDataRestoreSafe(
+                any(byte[].class), anyString());
+
         installPackage(USER_0, LAUNCHER_2);
         runWithCaller(LAUNCHER_2, USER_0, () -> {
             assertShortcutIds(assertAllPinned(
@@ -5388,6 +5411,8 @@
     }
 
     protected void checkBackupAndRestore_publisherAndLauncherNotRestored() {
+        doReturn(true).when(mMockPackageManagerInternal).isDataRestoreSafe(any(byte[].class),
+                anyString());
         installPackage(USER_0, CALLING_PACKAGE_1);
         runWithCaller(CALLING_PACKAGE_1, USER_0, () -> {
             assertEquals(0, mManager.getDynamicShortcuts().size());
@@ -5501,6 +5526,9 @@
         assertNull(user0.getAllLaunchersForTest().get(PackageWithUser.of(USER_0, LAUNCHER_3)));
         assertNull(user0.getAllLaunchersForTest().get(PackageWithUser.of(USER_P0, LAUNCHER_1)));
 
+        doReturn(true).when(mMockPackageManagerInternal).isDataRestoreSafe(any(byte[].class),
+                anyString());
+
         installPackage(USER_0, CALLING_PACKAGE_1);
         runWithCaller(CALLING_PACKAGE_1, USER_0, () -> {
             assertWith(getCallerVisibleShortcuts())
@@ -5586,6 +5614,8 @@
                     .areAllDisabled();
         });
 
+        doReturn(true).when(mMockPackageManagerInternal).isDataRestoreSafe(
+                any(byte[].class), anyString());
         backupAndRestore();
 
         // When re-installing the app, the manifest shortcut should be re-published.
@@ -5695,6 +5725,8 @@
                     .haveIds("s1", "ms1");
         });
 
+        doReturn(true).when(mMockPackageManagerInternal).isDataRestoreSafe(any(byte[].class),
+                anyString());
         // Backup and *without restarting the service, just call applyRestore()*.
         {
             int prevUid = mInjectedCallingUid;
@@ -5768,6 +5800,9 @@
                     list("ms1", "ms2", "ms3", "ms4", "s1", "s2"), HANDLE_USER_0);
         });
 
+        doReturn(true).when(mMockPackageManagerInternal).isDataRestoreSafe(
+                any(byte[].class), anyString());
+
         backupAndRestore();
 
         // Lower the version and remove the manifest shortcuts.
@@ -5994,6 +6029,9 @@
         addPackage(CALLING_PACKAGE_1, CALLING_UID_1, 10, "22222");
         addPackage(LAUNCHER_1, LAUNCHER_UID_1, 10, "11111");
 
+        doReturn(true).when(mMockPackageManagerInternal).isDataRestoreSafe(
+                any(byte[].class), anyString());
+
         runWithSystemUid(() -> mService.applyRestore(payload, USER_0));
 
         runWithCaller(CALLING_PACKAGE_1, USER_0, () -> {
diff --git a/services/tests/servicestests/src/com/android/server/pm/ShortcutManagerTest5.java b/services/tests/servicestests/src/com/android/server/pm/ShortcutManagerTest5.java
index 29c98dc..cd7feea 100644
--- a/services/tests/servicestests/src/com/android/server/pm/ShortcutManagerTest5.java
+++ b/services/tests/servicestests/src/com/android/server/pm/ShortcutManagerTest5.java
@@ -76,11 +76,13 @@
                 mMyPackage, mMyUserId, /*signature*/ false);
         assertEquals(mMyPackage, pi.packageName);
         assertNull(pi.signatures);
+        assertNull(pi.signingCertificateHistory);
 
         pi = mShortcutService.getPackageInfo(
                 mMyPackage, mMyUserId, /*signature*/ true);
         assertEquals(mMyPackage, pi.packageName);
-        assertNotNull(pi.signatures);
+        assertNull(pi.signatures);
+        assertNotNull(pi.signingCertificateHistory);
 
         pi = mShortcutService.getPackageInfo(
                 "no.such.package", mMyUserId, /*signature*/ true);
diff --git a/services/tests/servicestests/src/com/android/server/pm/backup/BackupUtilsTest.java b/services/tests/servicestests/src/com/android/server/pm/backup/BackupUtilsTest.java
index c016e61..1ac7cb8 100644
--- a/services/tests/servicestests/src/com/android/server/pm/backup/BackupUtilsTest.java
+++ b/services/tests/servicestests/src/com/android/server/pm/backup/BackupUtilsTest.java
@@ -15,73 +15,309 @@
  */
 package com.android.server.pm.backup;
 
+import static com.google.common.truth.Truth.assertThat;
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.assertEquals;
+import static org.mockito.Mockito.doReturn;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.when;
+
 import android.content.pm.ApplicationInfo;
 import android.content.pm.PackageInfo;
+import android.content.pm.PackageManagerInternal;
 import android.content.pm.PackageParser.Package;
 import android.content.pm.Signature;
-import android.test.AndroidTestCase;
 import android.test.MoreAsserts;
-import android.test.suitebuilder.annotation.SmallTest;
+import android.platform.test.annotations.Presubmit;
+import android.support.test.filters.SmallTest;
+import android.support.test.runner.AndroidJUnit4;
 
 import com.android.server.backup.BackupUtils;
 
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+
 import java.util.ArrayList;
 import java.util.Arrays;
 
 @SmallTest
-public class BackupUtilsTest extends AndroidTestCase {
+@Presubmit
+@RunWith(AndroidJUnit4.class)
+public class BackupUtilsTest {
 
-    private Signature[] genSignatures(String... signatures) {
-        final Signature[] sigs = new Signature[signatures.length];
-        for (int i = 0; i < signatures.length; i++){
-            sigs[i] = new Signature(signatures[i].getBytes());
-        }
-        return sigs;
+    private static final Signature SIGNATURE_1 = generateSignature((byte) 1);
+    private static final Signature SIGNATURE_2 = generateSignature((byte) 2);
+    private static final Signature SIGNATURE_3 = generateSignature((byte) 3);
+    private static final Signature SIGNATURE_4 = generateSignature((byte) 4);
+    private static final byte[] SIGNATURE_HASH_1 = BackupUtils.hashSignature(SIGNATURE_1);
+    private static final byte[] SIGNATURE_HASH_2 = BackupUtils.hashSignature(SIGNATURE_2);
+    private static final byte[] SIGNATURE_HASH_3 = BackupUtils.hashSignature(SIGNATURE_3);
+    private static final byte[] SIGNATURE_HASH_4 = BackupUtils.hashSignature(SIGNATURE_4);
+
+    private PackageManagerInternal mMockPackageManagerInternal;
+
+    @Before
+    public void setUp() throws Exception {
+        mMockPackageManagerInternal = mock(PackageManagerInternal.class);
     }
 
-    private PackageInfo genPackage(String... signatures) {
-        final PackageInfo pi = new PackageInfo();
-        pi.packageName = "package";
-        pi.applicationInfo = new ApplicationInfo();
-        pi.signatures = genSignatures(signatures);
+    @Test
+    public void signaturesMatch_targetIsNull_returnsFalse() throws Exception {
+        ArrayList<byte[]> storedSigHashes = new ArrayList<>();
+        storedSigHashes.add(SIGNATURE_HASH_1);
+        boolean result = BackupUtils.signaturesMatch(storedSigHashes, null,
+                mMockPackageManagerInternal);
 
-        return pi;
+        assertThat(result).isFalse();
     }
 
-    public void testSignaturesMatch() {
-        final ArrayList<byte[]> stored1 = BackupUtils.hashSignatureArray(Arrays.asList(
-                "abc".getBytes()));
-        final ArrayList<byte[]> stored2 = BackupUtils.hashSignatureArray(Arrays.asList(
-                "abc".getBytes(), "def".getBytes()));
+    @Test
+    public void signaturesMatch_systemApplication_returnsTrue() throws Exception {
+        PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
+        packageInfo.applicationInfo = new ApplicationInfo();
+        packageInfo.applicationInfo.flags |= ApplicationInfo.FLAG_SYSTEM;
 
-        PackageInfo pi;
+        ArrayList<byte[]> storedSigHashes = new ArrayList<>();
+        storedSigHashes.add(SIGNATURE_HASH_1);
+        boolean result = BackupUtils.signaturesMatch(storedSigHashes, packageInfo,
+                mMockPackageManagerInternal);
 
-        // False for null package.
-        assertFalse(BackupUtils.signaturesMatch(stored1, null));
-
-        // If it's a system app, signatures don't matter.
-        pi = genPackage("xyz");
-        pi.applicationInfo.flags |= ApplicationInfo.FLAG_SYSTEM;
-        assertTrue(BackupUtils.signaturesMatch(stored1, pi));
-
-        // Non system apps.
-        assertTrue(BackupUtils.signaturesMatch(stored1, genPackage("abc")));
-
-        // Superset is okay.
-        assertTrue(BackupUtils.signaturesMatch(stored1, genPackage("abc", "xyz")));
-        assertTrue(BackupUtils.signaturesMatch(stored1, genPackage("xyz", "abc")));
-
-        assertFalse(BackupUtils.signaturesMatch(stored1, genPackage("xyz")));
-        assertFalse(BackupUtils.signaturesMatch(stored1, genPackage("xyz", "def")));
-
-        assertTrue(BackupUtils.signaturesMatch(stored2, genPackage("def", "abc")));
-        assertTrue(BackupUtils.signaturesMatch(stored2, genPackage("x", "def", "abc", "y")));
-
-        // Subset is not okay.
-        assertFalse(BackupUtils.signaturesMatch(stored2, genPackage("abc")));
-        assertFalse(BackupUtils.signaturesMatch(stored2, genPackage("def")));
+        assertThat(result).isTrue();
     }
 
+    @Test
+    public void signaturesMatch_disallowsUnsignedApps_storedSignatureNull_returnsFalse()
+            throws Exception {
+        PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[][] {{SIGNATURE_1}};
+        packageInfo.applicationInfo = new ApplicationInfo();
+
+        boolean result = BackupUtils.signaturesMatch(null, packageInfo,
+                mMockPackageManagerInternal);
+
+        assertThat(result).isFalse();
+    }
+
+    @Test
+    public void signaturesMatch_disallowsUnsignedApps_storedSignatureEmpty_returnsFalse()
+            throws Exception {
+        PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[][] {{SIGNATURE_1}};
+        packageInfo.applicationInfo = new ApplicationInfo();
+
+        ArrayList<byte[]> storedSigHashes = new ArrayList<>();
+        boolean result = BackupUtils.signaturesMatch(storedSigHashes, packageInfo,
+                mMockPackageManagerInternal);
+
+        assertThat(result).isFalse();
+    }
+
+
+    @Test
+    public void
+    signaturesMatch_disallowsUnsignedApps_targetSignatureEmpty_returnsFalse()
+            throws Exception {
+        PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[0][0];
+        packageInfo.applicationInfo = new ApplicationInfo();
+
+        ArrayList<byte[]> storedSigHashes = new ArrayList<>();
+        storedSigHashes.add(SIGNATURE_HASH_1);
+        boolean result = BackupUtils.signaturesMatch(storedSigHashes, packageInfo,
+                mMockPackageManagerInternal);
+
+        assertThat(result).isFalse();
+    }
+
+    @Test
+    public void
+    signaturesMatch_disallowsUnsignedApps_targetSignatureNull_returnsFalse()
+            throws Exception {
+        PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = null;
+        packageInfo.applicationInfo = new ApplicationInfo();
+
+        ArrayList<byte[]> storedSigHashes = new ArrayList<>();
+        storedSigHashes.add(SIGNATURE_HASH_1);
+        boolean result = BackupUtils.signaturesMatch(storedSigHashes, packageInfo,
+                mMockPackageManagerInternal);
+
+        assertThat(result).isFalse();
+    }
+
+    @Test
+    public void signaturesMatch_disallowsUnsignedApps_bothSignaturesNull_returnsFalse()
+            throws Exception {
+        PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = null;
+        packageInfo.applicationInfo = new ApplicationInfo();
+
+        boolean result = BackupUtils.signaturesMatch(null, packageInfo,
+                mMockPackageManagerInternal);
+
+        assertThat(result).isFalse();
+    }
+
+    @Test
+    public void signaturesMatch_disallowsUnsignedApps_bothSignaturesEmpty_returnsFalse()
+            throws Exception {
+        PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[0][0];
+        packageInfo.applicationInfo = new ApplicationInfo();
+
+        ArrayList<byte[]> storedSigHashes = new ArrayList<>();
+        boolean result = BackupUtils.signaturesMatch(storedSigHashes, packageInfo,
+                mMockPackageManagerInternal);
+
+        assertThat(result).isFalse();
+    }
+
+    @Test
+    public void signaturesMatch_equalSignatures_returnsTrue() throws Exception {
+        PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[][] {
+                {SIGNATURE_1, SIGNATURE_2, SIGNATURE_3}
+        };
+        packageInfo.applicationInfo = new ApplicationInfo();
+
+        ArrayList<byte[]> storedSigHashes = new ArrayList<>();
+        storedSigHashes.add(SIGNATURE_HASH_1);
+        storedSigHashes.add(SIGNATURE_HASH_2);
+        storedSigHashes.add(SIGNATURE_HASH_3);
+        boolean result = BackupUtils.signaturesMatch(storedSigHashes, packageInfo,
+                mMockPackageManagerInternal);
+
+        assertThat(result).isTrue();
+    }
+
+    @Test
+    public void signaturesMatch_extraSignatureInTarget_returnsTrue() throws Exception {
+        PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[][] {
+                {SIGNATURE_1, SIGNATURE_2, SIGNATURE_3}
+        };
+        packageInfo.applicationInfo = new ApplicationInfo();
+
+        ArrayList<byte[]> storedSigHashes = new ArrayList<>();
+        storedSigHashes.add(SIGNATURE_HASH_1);
+        storedSigHashes.add(SIGNATURE_HASH_2);
+        boolean result = BackupUtils.signaturesMatch(storedSigHashes, packageInfo,
+                mMockPackageManagerInternal);
+
+        assertThat(result).isTrue();
+    }
+
+    @Test
+    public void signaturesMatch_extraSignatureInStored_returnsFalse() throws Exception {
+        PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[][] {{SIGNATURE_1, SIGNATURE_2}};
+        packageInfo.applicationInfo = new ApplicationInfo();
+
+        ArrayList<byte[]> storedSigHashes = new ArrayList<>();
+        storedSigHashes.add(SIGNATURE_HASH_1);
+        storedSigHashes.add(SIGNATURE_HASH_2);
+        storedSigHashes.add(SIGNATURE_HASH_3);
+        boolean result = BackupUtils.signaturesMatch(storedSigHashes, packageInfo,
+                mMockPackageManagerInternal);
+
+        assertThat(result).isFalse();
+    }
+
+    @Test
+    public void signaturesMatch_oneNonMatchingSignature_returnsFalse() throws Exception {
+        PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[][] {
+                {SIGNATURE_1, SIGNATURE_2, SIGNATURE_3}
+        };
+        packageInfo.applicationInfo = new ApplicationInfo();
+
+        ArrayList<byte[]> storedSigHashes = new ArrayList<>();
+        storedSigHashes.add(SIGNATURE_HASH_1);
+        storedSigHashes.add(SIGNATURE_HASH_2);
+        storedSigHashes.add(SIGNATURE_HASH_4);
+        boolean result = BackupUtils.signaturesMatch(storedSigHashes, packageInfo,
+                mMockPackageManagerInternal);
+
+        assertThat(result).isFalse();
+    }
+
+    @Test
+    public void signaturesMatch_singleStoredSignatureNoRotation_returnsTrue()
+            throws Exception {
+        PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[][] {{SIGNATURE_1}};
+        packageInfo.applicationInfo = new ApplicationInfo();
+
+        doReturn(true).when(mMockPackageManagerInternal).isDataRestoreSafe(SIGNATURE_HASH_1,
+                packageInfo.packageName);
+
+        ArrayList<byte[]> storedSigHashes = new ArrayList<>();
+        storedSigHashes.add(SIGNATURE_HASH_1);
+        boolean result = BackupUtils.signaturesMatch(storedSigHashes, packageInfo,
+                mMockPackageManagerInternal);
+
+        assertThat(result).isTrue();
+    }
+
+    @Test
+    public void signaturesMatch_singleStoredSignatureWithRotationAssumeDataCapability_returnsTrue()
+            throws Exception {
+        PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[][] {{SIGNATURE_1}, {SIGNATURE_2}};
+        packageInfo.applicationInfo = new ApplicationInfo();
+
+        // we know SIGNATURE_1 is in history, and we want to assume it has
+        // SigningDetails.CertCapabilities.INSTALLED_DATA capability
+        doReturn(true).when(mMockPackageManagerInternal).isDataRestoreSafe(SIGNATURE_HASH_1,
+                packageInfo.packageName);
+
+        ArrayList<byte[]> storedSigHashes = new ArrayList<>();
+        storedSigHashes.add(SIGNATURE_HASH_1);
+        boolean result = BackupUtils.signaturesMatch(storedSigHashes, packageInfo,
+                mMockPackageManagerInternal);
+
+        assertThat(result).isTrue();
+    }
+
+    @Test
+    public void
+            signaturesMatch_singleStoredSignatureWithRotationAssumeNoDataCapability_returnsFalse()
+            throws Exception {
+        PackageInfo packageInfo = new PackageInfo();
+        packageInfo.packageName = "test";
+        packageInfo.signingCertificateHistory = new Signature[][] {{SIGNATURE_1}, {SIGNATURE_2}};
+        packageInfo.applicationInfo = new ApplicationInfo();
+
+        // we know SIGNATURE_1 is in history, but we want to assume it does not have
+        // SigningDetails.CertCapabilities.INSTALLED_DATA capability
+        doReturn(false).when(mMockPackageManagerInternal).isDataRestoreSafe(SIGNATURE_HASH_1,
+                packageInfo.packageName);
+
+        ArrayList<byte[]> storedSigHashes = new ArrayList<>();
+        storedSigHashes.add(SIGNATURE_HASH_1);
+        boolean result = BackupUtils.signaturesMatch(storedSigHashes, packageInfo,
+                mMockPackageManagerInternal);
+
+        assertThat(result).isFalse();
+    }
+
+    @Test
     public void testHashSignature() {
         final byte[] sig1 = "abc".getBytes();
         final byte[] sig2 = "def".getBytes();
@@ -115,4 +351,10 @@
         MoreAsserts.assertEquals(hash2a, listA.get(1));
         MoreAsserts.assertEquals(hash2a, listB.get(1));
     }
+
+    private static Signature generateSignature(byte i) {
+        byte[] signatureBytes = new byte[256];
+        signatureBytes[0] = i;
+        return new Signature(signatureBytes);
+    }
 }