Generalize vdex class redefinition check

The check introduced in CL If0c56b1970d8ebe701d198ffccec52f586aea9e6
skips fast verification if an apk's class is overshadowed by a class in
boot classpath because the vdex dependencies do not contain intra-apk
dependencies.

However, the change only checks for presence of a duplicate class in the
boot classloader, while a duplicate class could be in any of the parent
classloaders. Fix this and move the check into VerifierDeps to make it
a proper part of the verification process.

The CL also refactors VerifierDeps::ValidateDependencies to output
an error string for better logging.

Bug: 122968669
Test: test/testrunner/testrunner.py -t 719
Test: m test-art-gtest-verifier_deps_test
Change-Id: I0d06b82e31088c58d4493723a5435309740f1d0c

7 files changed, 340 insertions, 377 deletions

diff --git a/compiler/driver/compiler_driver.cc b/compiler/driver/compiler_driver.cc
index d46cffb1e8..bfa039edab 100644
--- a/compiler/driver/compiler_driver.cc
+++ b/compiler/driver/compiler_driver.cc
@@ -1765,42 +1765,6 @@ static void LoadAndUpdateStatus(const ClassAccessor& accessor,
   }
 }
 
-// Returns true if any of the given dex files define a class from the boot classpath.
-static bool DexFilesRedefineBootClasses(
-    const std::vector<const DexFile*>& dex_files,
-    TimingLogger* timings) {
-  TimingLogger::ScopedTiming t("Fast Verify: Boot Class Redefinition Check", timings);
-
-  ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
-  Thread* self = Thread::Current();
-  ScopedObjectAccess soa(self);
-
-  bool foundRedefinition = false;
-  for (const DexFile* dex_file : dex_files) {
-    for (ClassAccessor accessor : dex_file->GetClasses()) {
-      const char* descriptor = accessor.GetDescriptor();
-      StackHandleScope<1> hs_class(self);
-      Handle<mirror::Class> klass =
-          hs_class.NewHandle(class_linker->FindSystemClass(self, descriptor));
-      if (klass == nullptr) {
-        self->ClearException();
-      } else {
-        LOG(WARNING) << "Redefinition of boot class " << descriptor
-            << " App dex file: " <<  accessor.GetDexFile().GetLocation()
-            << " Boot dex file: " << klass->GetDexFile().GetLocation();
-        foundRedefinition = true;
-        if (!VLOG_IS_ON(verifier)) {
-          // If we are not in verbose mode, return early.
-          // Otherwise continue and log all the collisions for easier debugging.
-          return true;
-        }
-      }
-    }
-  }
-
-  return foundRedefinition;
-}
-
 bool CompilerDriver::FastVerify(jobject jclass_loader,
                                 const std::vector<const DexFile*>& dex_files,
                                 TimingLogger* timings,
@@ -1813,21 +1777,14 @@ bool CompilerDriver::FastVerify(jobject jclass_loader,
   }
   TimingLogger::ScopedTiming t("Fast Verify", timings);
 
-  // We cannot do fast verification if the app redefines classes from the boot classpath.
-  // Vdex does not record resolution chains for boot classes and we might wrongfully
-  // resolve a class to the app when it should have been resolved to the boot classpath
-  // (e.g. if we verified against the SDK and the app redefines a boot class which is not
-  // in the SDK.)
-  if (DexFilesRedefineBootClasses(dex_files, timings)) {
-    LOG(WARNING) << "Found redefinition of boot classes. Not doing fast verification.";
-    return false;
-  }
-
   ScopedObjectAccess soa(Thread::Current());
   StackHandleScope<2> hs(soa.Self());
   Handle<mirror::ClassLoader> class_loader(
       hs.NewHandle(soa.Decode<mirror::ClassLoader>(jclass_loader)));
-  if (!verifier_deps->ValidateDependencies(class_loader, soa.Self())) {
+  std::string error_msg;
+
+  if (!verifier_deps->ValidateDependencies(class_loader, soa.Self(), &error_msg)) {
+    LOG(WARNING) << "Fast verification failed: " << error_msg;
     return false;
   }
 
diff --git a/compiler/verifier_deps_test.cc b/compiler/verifier_deps_test.cc
index 092e931944..5c6b815ad5 100644
--- a/compiler/verifier_deps_test.cc
+++ b/compiler/verifier_deps_test.cc
@@ -449,6 +449,28 @@ class VerifierDepsTest : public CommonCompilerTest {
            has_unverified_classes;
   }
 
+  // Load the dex file again with a new class loader, decode the VerifierDeps
+  // in `buffer`, allow the caller to modify the deps and then run validation.
+  template<typename Fn>
+  bool RunValidation(Fn fn, const std::vector<uint8_t>& buffer, std::string* error_msg) {
+    ScopedObjectAccess soa(Thread::Current());
+
+    jobject second_loader = LoadDex("VerifierDeps");
+    const auto& second_dex_files = GetDexFiles(second_loader);
+
+    VerifierDeps decoded_deps(second_dex_files, ArrayRef<const uint8_t>(buffer));
+    VerifierDeps::DexFileDeps* decoded_dex_deps =
+        decoded_deps.GetDexFileDeps(*second_dex_files.front());
+
+    // Let the test modify the dependencies.
+    fn(*decoded_dex_deps);
+
+    StackHandleScope<1> hs(soa.Self());
+    Handle<mirror::ClassLoader> new_class_loader =
+        hs.NewHandle<mirror::ClassLoader>(soa.Decode<mirror::ClassLoader>(second_loader));
+    return decoded_deps.ValidateDependencies(new_class_loader, soa.Self(), error_msg);
+  }
+
   std::unique_ptr<verifier::VerifierDeps> verifier_deps_;
   std::vector<const DexFile*> dex_files_;
   const DexFile* primary_dex_file_;
@@ -1177,8 +1199,9 @@ TEST_F(VerifierDepsTest, UnverifiedOrder) {
 }
 
 TEST_F(VerifierDepsTest, VerifyDeps) {
-  VerifyDexFile();
+  std::string error_msg;
 
+  VerifyDexFile();
   ASSERT_EQ(1u, NumberOfCompiledDexFiles());
   ASSERT_TRUE(HasEachKindOfRecord());
 
@@ -1186,249 +1209,166 @@ TEST_F(VerifierDepsTest, VerifyDeps) {
   // the existing `class_loader_` may contain erroneous classes,
   // that ClassLinker::FindClass won't return.
 
-  ScopedObjectAccess soa(Thread::Current());
-  StackHandleScope<1> hs(soa.Self());
-  MutableHandle<mirror::ClassLoader> new_class_loader(hs.NewHandle<mirror::ClassLoader>(nullptr));
-  {
-    new_class_loader.Assign(soa.Decode<mirror::ClassLoader>(LoadDex("VerifierDeps")));
-    ASSERT_TRUE(verifier_deps_->ValidateDependencies(new_class_loader, soa.Self()));
-  }
-
   std::vector<uint8_t> buffer;
   verifier_deps_->Encode(dex_files_, &buffer);
   ASSERT_FALSE(buffer.empty());
 
-  {
-    VerifierDeps decoded_deps(dex_files_, ArrayRef<const uint8_t>(buffer));
-    new_class_loader.Assign(soa.Decode<mirror::ClassLoader>(LoadDex("VerifierDeps")));
-    ASSERT_TRUE(decoded_deps.ValidateDependencies(new_class_loader, soa.Self()));
-  }
-
-  // Fiddle with the dependencies to make sure we catch any change and fail to verify.
-
-  {
-    // Mess up with the assignable_types.
-    VerifierDeps decoded_deps(dex_files_, ArrayRef<const uint8_t>(buffer));
-    VerifierDeps::DexFileDeps* deps = decoded_deps.GetDexFileDeps(*primary_dex_file_);
-    deps->assignable_types_.insert(*deps->unassignable_types_.begin());
-    new_class_loader.Assign(soa.Decode<mirror::ClassLoader>(LoadDex("VerifierDeps")));
-    ASSERT_FALSE(decoded_deps.ValidateDependencies(new_class_loader, soa.Self()));
-  }
-
-  {
-    // Mess up with the unassignable_types.
-    VerifierDeps decoded_deps(dex_files_, ArrayRef<const uint8_t>(buffer));
-    VerifierDeps::DexFileDeps* deps = decoded_deps.GetDexFileDeps(*primary_dex_file_);
-    deps->unassignable_types_.insert(*deps->assignable_types_.begin());
-    new_class_loader.Assign(soa.Decode<mirror::ClassLoader>(LoadDex("VerifierDeps")));
-    ASSERT_FALSE(decoded_deps.ValidateDependencies(new_class_loader, soa.Self()));
-  }
-
-  // Mess up with classes.
-  {
-    VerifierDeps decoded_deps(dex_files_, ArrayRef<const uint8_t>(buffer));
-    VerifierDeps::DexFileDeps* deps = decoded_deps.GetDexFileDeps(*primary_dex_file_);
-    bool found = false;
-    for (const auto& entry : deps->classes_) {
-      if (entry.IsResolved()) {
-        deps->classes_.insert(VerifierDeps::ClassResolution(
-            entry.GetDexTypeIndex(), VerifierDeps::kUnresolvedMarker));
-        found = true;
-        break;
-      }
-    }
-    ASSERT_TRUE(found);
-    new_class_loader.Assign(soa.Decode<mirror::ClassLoader>(LoadDex("VerifierDeps")));
-    ASSERT_FALSE(decoded_deps.ValidateDependencies(new_class_loader, soa.Self()));
-  }
-
-  {
-    VerifierDeps decoded_deps(dex_files_, ArrayRef<const uint8_t>(buffer));
-    VerifierDeps::DexFileDeps* deps = decoded_deps.GetDexFileDeps(*primary_dex_file_);
-    bool found = false;
-    for (const auto& entry : deps->classes_) {
-      if (!entry.IsResolved()) {
-        deps->classes_.insert(VerifierDeps::ClassResolution(
-            entry.GetDexTypeIndex(), VerifierDeps::kUnresolvedMarker - 1));
-        found = true;
-        break;
-      }
-    }
-    ASSERT_TRUE(found);
-    new_class_loader.Assign(soa.Decode<mirror::ClassLoader>(LoadDex("VerifierDeps")));
-    ASSERT_FALSE(decoded_deps.ValidateDependencies(new_class_loader, soa.Self()));
-  }
-
-  {
-    VerifierDeps decoded_deps(dex_files_, ArrayRef<const uint8_t>(buffer));
-    VerifierDeps::DexFileDeps* deps = decoded_deps.GetDexFileDeps(*primary_dex_file_);
-    bool found = false;
-    for (const auto& entry : deps->classes_) {
-      if (entry.IsResolved()) {
-        deps->classes_.insert(VerifierDeps::ClassResolution(
-            entry.GetDexTypeIndex(), entry.GetAccessFlags() - 1));
-        found = true;
-        break;
-      }
-    }
-    ASSERT_TRUE(found);
-    new_class_loader.Assign(soa.Decode<mirror::ClassLoader>(LoadDex("VerifierDeps")));
-    ASSERT_FALSE(decoded_deps.ValidateDependencies(new_class_loader, soa.Self()));
-  }
-
-  // Mess up with fields.
-  {
-    VerifierDeps decoded_deps(dex_files_, ArrayRef<const uint8_t>(buffer));
-    VerifierDeps::DexFileDeps* deps = decoded_deps.GetDexFileDeps(*primary_dex_file_);
-    bool found = false;
-    for (const auto& entry : deps->fields_) {
-      if (entry.IsResolved()) {
-        deps->fields_.insert(VerifierDeps::FieldResolution(entry.GetDexFieldIndex(),
-                                                           VerifierDeps::kUnresolvedMarker,
-                                                           entry.GetDeclaringClassIndex()));
-        found = true;
-        break;
-      }
-    }
-    ASSERT_TRUE(found);
-    new_class_loader.Assign(soa.Decode<mirror::ClassLoader>(LoadDex("VerifierDeps")));
-    ASSERT_FALSE(decoded_deps.ValidateDependencies(new_class_loader, soa.Self()));
-  }
-
-  {
-    VerifierDeps decoded_deps(dex_files_, ArrayRef<const uint8_t>(buffer));
-    VerifierDeps::DexFileDeps* deps = decoded_deps.GetDexFileDeps(*primary_dex_file_);
-    bool found = false;
-    for (const auto& entry : deps->fields_) {
-      if (!entry.IsResolved()) {
-        constexpr dex::StringIndex kStringIndexZero(0);  // We know there is a class there.
-        deps->fields_.insert(VerifierDeps::FieldResolution(0 /* we know there is a field there */,
-                                                           VerifierDeps::kUnresolvedMarker - 1,
-                                                           kStringIndexZero));
-        found = true;
-        break;
-      }
-    }
-    ASSERT_TRUE(found);
-    new_class_loader.Assign(soa.Decode<mirror::ClassLoader>(LoadDex("VerifierDeps")));
-    ASSERT_FALSE(decoded_deps.ValidateDependencies(new_class_loader, soa.Self()));
-  }
-
-  {
-    VerifierDeps decoded_deps(dex_files_, ArrayRef<const uint8_t>(buffer));
-    VerifierDeps::DexFileDeps* deps = decoded_deps.GetDexFileDeps(*primary_dex_file_);
-    bool found = false;
-    for (const auto& entry : deps->fields_) {
-      if (entry.IsResolved()) {
-        deps->fields_.insert(VerifierDeps::FieldResolution(entry.GetDexFieldIndex(),
-                                                           entry.GetAccessFlags() - 1,
-                                                           entry.GetDeclaringClassIndex()));
-        found = true;
-        break;
-      }
-    }
-    ASSERT_TRUE(found);
-    new_class_loader.Assign(soa.Decode<mirror::ClassLoader>(LoadDex("VerifierDeps")));
-    ASSERT_FALSE(decoded_deps.ValidateDependencies(new_class_loader, soa.Self()));
-  }
-
-  {
-    VerifierDeps decoded_deps(dex_files_, ArrayRef<const uint8_t>(buffer));
-    VerifierDeps::DexFileDeps* deps = decoded_deps.GetDexFileDeps(*primary_dex_file_);
-    bool found = false;
-    for (const auto& entry : deps->fields_) {
-      constexpr dex::StringIndex kNewTypeIndex(0);
-      if (entry.GetDeclaringClassIndex() != kNewTypeIndex) {
-        deps->fields_.insert(VerifierDeps::FieldResolution(entry.GetDexFieldIndex(),
-                                                           entry.GetAccessFlags(),
-                                                           kNewTypeIndex));
-        found = true;
-        break;
-      }
-    }
-    ASSERT_TRUE(found);
-    new_class_loader.Assign(soa.Decode<mirror::ClassLoader>(LoadDex("VerifierDeps")));
-    ASSERT_FALSE(decoded_deps.ValidateDependencies(new_class_loader, soa.Self()));
-  }
+  // Check that dependencies are satisfied after decoding `buffer`.
+  ASSERT_TRUE(RunValidation([](VerifierDeps::DexFileDeps&) {}, buffer, &error_msg))
+      << error_msg;
 
-  // Mess up with methods.
-  {
-    VerifierDeps decoded_deps(dex_files_, ArrayRef<const uint8_t>(buffer));
-    VerifierDeps::DexFileDeps* deps = decoded_deps.GetDexFileDeps(*primary_dex_file_);
-    bool found = false;
-    std::set<VerifierDeps::MethodResolution>* methods = &deps->methods_;
-    for (const auto& entry : *methods) {
-      if (entry.IsResolved()) {
-        methods->insert(VerifierDeps::MethodResolution(entry.GetDexMethodIndex(),
-                                                       VerifierDeps::kUnresolvedMarker,
-                                                       entry.GetDeclaringClassIndex()));
-        found = true;
-        break;
-      }
-    }
-    ASSERT_TRUE(found);
-    new_class_loader.Assign(soa.Decode<mirror::ClassLoader>(LoadDex("VerifierDeps")));
-    ASSERT_FALSE(decoded_deps.ValidateDependencies(new_class_loader, soa.Self()));
-  }
+  // Mess with the dependencies to make sure we catch any change and fail to verify.
+  ASSERT_FALSE(RunValidation([](VerifierDeps::DexFileDeps& deps) {
+        deps.assignable_types_.insert(*deps.unassignable_types_.begin());
+      }, buffer, &error_msg));
 
-  {
-    VerifierDeps decoded_deps(dex_files_, ArrayRef<const uint8_t>(buffer));
-    VerifierDeps::DexFileDeps* deps = decoded_deps.GetDexFileDeps(*primary_dex_file_);
-    bool found = false;
-    std::set<VerifierDeps::MethodResolution>* methods = &deps->methods_;
-    for (const auto& entry : *methods) {
-      if (!entry.IsResolved()) {
-        constexpr dex::StringIndex kStringIndexZero(0);  // We know there is a class there.
-        methods->insert(VerifierDeps::MethodResolution(0 /* we know there is a method there */,
-                                                       VerifierDeps::kUnresolvedMarker - 1,
-                                                       kStringIndexZero));
-        found = true;
-        break;
-      }
-    }
-    ASSERT_TRUE(found);
-    new_class_loader.Assign(soa.Decode<mirror::ClassLoader>(LoadDex("VerifierDeps")));
-    ASSERT_FALSE(decoded_deps.ValidateDependencies(new_class_loader, soa.Self()));
-  }
+  // Mess with the unassignable_types.
+  ASSERT_FALSE(RunValidation([](VerifierDeps::DexFileDeps& deps) {
+        deps.unassignable_types_.insert(*deps.assignable_types_.begin());
+      }, buffer, &error_msg));
 
-  {
-    VerifierDeps decoded_deps(dex_files_, ArrayRef<const uint8_t>(buffer));
-    VerifierDeps::DexFileDeps* deps = decoded_deps.GetDexFileDeps(*primary_dex_file_);
-    bool found = false;
-    std::set<VerifierDeps::MethodResolution>* methods = &deps->methods_;
-    for (const auto& entry : *methods) {
-      if (entry.IsResolved()) {
-        methods->insert(VerifierDeps::MethodResolution(entry.GetDexMethodIndex(),
-                                                       entry.GetAccessFlags() - 1,
-                                                       entry.GetDeclaringClassIndex()));
-        found = true;
-        break;
-      }
-    }
-    ASSERT_TRUE(found);
-    new_class_loader.Assign(soa.Decode<mirror::ClassLoader>(LoadDex("VerifierDeps")));
-    ASSERT_FALSE(decoded_deps.ValidateDependencies(new_class_loader, soa.Self()));
-  }
+  // Mess with classes.
+  ASSERT_FALSE(RunValidation([](VerifierDeps::DexFileDeps& deps) {
+        for (const auto& entry : deps.classes_) {
+          if (entry.IsResolved()) {
+            deps.classes_.insert(VerifierDeps::ClassResolution(
+                entry.GetDexTypeIndex(), VerifierDeps::kUnresolvedMarker));
+            return;
+          }
+        }
+        LOG(FATAL) << "Could not find any resolved classes";
+        UNREACHABLE();
+      }, buffer, &error_msg));
+  ASSERT_FALSE(RunValidation([](VerifierDeps::DexFileDeps& deps) {
+        for (const auto& entry : deps.classes_) {
+          if (!entry.IsResolved()) {
+            deps.classes_.insert(VerifierDeps::ClassResolution(
+                entry.GetDexTypeIndex(), VerifierDeps::kUnresolvedMarker - 1));
+            return;
+          }
+        }
+        LOG(FATAL) << "Could not find any unresolved classes";
+        UNREACHABLE();
+      }, buffer, &error_msg));
+  ASSERT_FALSE(RunValidation([](VerifierDeps::DexFileDeps& deps) {
+        for (const auto& entry : deps.classes_) {
+          if (entry.IsResolved()) {
+            deps.classes_.insert(VerifierDeps::ClassResolution(
+                entry.GetDexTypeIndex(), entry.GetAccessFlags() - 1));
+            return;
+          }
+        }
+        LOG(FATAL) << "Could not find any resolved classes";
+        UNREACHABLE();
+      }, buffer, &error_msg));
 
-  {
-    VerifierDeps decoded_deps(dex_files_, ArrayRef<const uint8_t>(buffer));
-    VerifierDeps::DexFileDeps* deps = decoded_deps.GetDexFileDeps(*primary_dex_file_);
-    bool found = false;
-    std::set<VerifierDeps::MethodResolution>* methods = &deps->methods_;
-    for (const auto& entry : *methods) {
-      constexpr dex::StringIndex kNewTypeIndex(0);
-      if (entry.IsResolved() && entry.GetDeclaringClassIndex() != kNewTypeIndex) {
-        methods->insert(VerifierDeps::MethodResolution(entry.GetDexMethodIndex(),
-                                                       entry.GetAccessFlags(),
-                                                       kNewTypeIndex));
-        found = true;
-        break;
-      }
-    }
-    ASSERT_TRUE(found);
-    new_class_loader.Assign(soa.Decode<mirror::ClassLoader>(LoadDex("VerifierDeps")));
-    ASSERT_FALSE(decoded_deps.ValidateDependencies(new_class_loader, soa.Self()));
-  }
+  // Mess with fields.
+  ASSERT_FALSE(RunValidation([](VerifierDeps::DexFileDeps& deps) {
+        for (const auto& entry : deps.fields_) {
+          if (entry.IsResolved()) {
+            deps.fields_.insert(VerifierDeps::FieldResolution(entry.GetDexFieldIndex(),
+                                                              VerifierDeps::kUnresolvedMarker,
+                                                              entry.GetDeclaringClassIndex()));
+            return;
+          }
+        }
+        LOG(FATAL) << "Could not find any resolved fields";
+        UNREACHABLE();
+      }, buffer, &error_msg));
+  ASSERT_FALSE(RunValidation([](VerifierDeps::DexFileDeps& deps) {
+        for (const auto& entry : deps.fields_) {
+          if (!entry.IsResolved()) {
+            constexpr dex::StringIndex kStringIndexZero(0);  // We know there is a class there.
+            deps.fields_.insert(VerifierDeps::FieldResolution(0 /* we know there is a field there */,
+                                                              VerifierDeps::kUnresolvedMarker - 1,
+                                                              kStringIndexZero));
+            return;
+          }
+        }
+        LOG(FATAL) << "Could not find any unresolved fields";
+        UNREACHABLE();
+      }, buffer, &error_msg));
+  ASSERT_FALSE(RunValidation([](VerifierDeps::DexFileDeps& deps) {
+        for (const auto& entry : deps.fields_) {
+          if (entry.IsResolved()) {
+            deps.fields_.insert(VerifierDeps::FieldResolution(entry.GetDexFieldIndex(),
+                                                              entry.GetAccessFlags() - 1,
+                                                              entry.GetDeclaringClassIndex()));
+            return;
+          }
+        }
+        LOG(FATAL) << "Could not find any resolved fields";
+        UNREACHABLE();
+      }, buffer, &error_msg));
+  ASSERT_FALSE(RunValidation([](VerifierDeps::DexFileDeps& deps) {
+        for (const auto& entry : deps.fields_) {
+          constexpr dex::StringIndex kNewTypeIndex(0);
+          if (entry.GetDeclaringClassIndex() != kNewTypeIndex) {
+            deps.fields_.insert(VerifierDeps::FieldResolution(entry.GetDexFieldIndex(),
+                                                              entry.GetAccessFlags(),
+                                                              kNewTypeIndex));
+            return;
+          }
+        }
+        LOG(FATAL) << "Could not find any suitable fields";
+        UNREACHABLE();
+      }, buffer, &error_msg));
+
+  // Mess with methods.
+  ASSERT_FALSE(RunValidation([](VerifierDeps::DexFileDeps& deps) {
+        std::set<VerifierDeps::MethodResolution>* methods = &deps.methods_;
+        for (const auto& entry : *methods) {
+          if (entry.IsResolved()) {
+            methods->insert(VerifierDeps::MethodResolution(entry.GetDexMethodIndex(),
+                                                          VerifierDeps::kUnresolvedMarker,
+                                                          entry.GetDeclaringClassIndex()));
+            return;
+          }
+        }
+        LOG(FATAL) << "Could not find any resolved methods";
+        UNREACHABLE();
+      }, buffer, &error_msg));
+  ASSERT_FALSE(RunValidation([](VerifierDeps::DexFileDeps& deps) {
+        std::set<VerifierDeps::MethodResolution>* methods = &deps.methods_;
+        for (const auto& entry : *methods) {
+          if (!entry.IsResolved()) {
+            constexpr dex::StringIndex kStringIndexZero(0);  // We know there is a class there.
+            methods->insert(VerifierDeps::MethodResolution(0 /* we know there is a method there */,
+                                                          VerifierDeps::kUnresolvedMarker - 1,
+                                                          kStringIndexZero));
+            return;
+          }
+        }
+        LOG(FATAL) << "Could not find any unresolved methods";
+        UNREACHABLE();
+      }, buffer, &error_msg));
+  ASSERT_FALSE(RunValidation([](VerifierDeps::DexFileDeps& deps) {
+        std::set<VerifierDeps::MethodResolution>* methods = &deps.methods_;
+        for (const auto& entry : *methods) {
+          if (entry.IsResolved()) {
+            methods->insert(VerifierDeps::MethodResolution(entry.GetDexMethodIndex(),
+                                                          entry.GetAccessFlags() - 1,
+                                                          entry.GetDeclaringClassIndex()));
+            return;
+          }
+        }
+        LOG(FATAL) << "Could not find any resolved methods";
+        UNREACHABLE();
+      }, buffer, &error_msg));
+  ASSERT_FALSE(RunValidation([](VerifierDeps::DexFileDeps& deps) {
+        std::set<VerifierDeps::MethodResolution>* methods = &deps.methods_;
+        for (const auto& entry : *methods) {
+          constexpr dex::StringIndex kNewTypeIndex(0);
+          if (entry.IsResolved() && entry.GetDeclaringClassIndex() != kNewTypeIndex) {
+            methods->insert(VerifierDeps::MethodResolution(entry.GetDexMethodIndex(),
+                                                          entry.GetAccessFlags(),
+                                                          kNewTypeIndex));
+            return;
+          }
+        }
+        LOG(FATAL) << "Could not find any suitable methods";
+        UNREACHABLE();
+      }, buffer, &error_msg));
 }
 
 TEST_F(VerifierDepsTest, CompilerDriver) {
diff --git a/runtime/verifier/verifier_deps.cc b/runtime/verifier/verifier_deps.cc
index bdcadd9fa6..8b1321a91c 100644
--- a/runtime/verifier/verifier_deps.cc
+++ b/runtime/verifier/verifier_deps.cc
@@ -17,6 +17,7 @@
 #include "verifier_deps.h"
 
 #include <cstring>
+#include <sstream>
 
 #include "art_field-inl.h"
 #include "art_method-inl.h"
@@ -25,6 +26,7 @@
 #include "base/mutex-inl.h"
 #include "base/stl_util.h"
 #include "compiler_callbacks.h"
+#include "dex/class_accessor-inl.h"
 #include "dex/dex_file-inl.h"
 #include "mirror/class-inl.h"
 #include "mirror/class_loader.h"
@@ -690,6 +692,12 @@ static inline void DecodeStringVector(const uint8_t** in,
   }
 }
 
+static inline std::string ToHex(uint32_t value) {
+  std::stringstream ss;
+  ss << std::hex << value << std::dec;
+  return ss.str();
+}
+
 }  // namespace
 
 void VerifierDeps::Encode(const std::vector<const DexFile*>& dex_files,
@@ -849,9 +857,10 @@ void VerifierDeps::Dump(VariableIndentationOutputStream* vios) const {
 }
 
 bool VerifierDeps::ValidateDependencies(Handle<mirror::ClassLoader> class_loader,
-                                        Thread* self) const {
+                                        Thread* self,
+                                        /* out */ std::string* error_msg) const {
   for (const auto& entry : dex_deps_) {
-    if (!VerifyDexFile(class_loader, *entry.first, *entry.second, self)) {
+    if (!VerifyDexFile(class_loader, *entry.first, *entry.second, self, error_msg)) {
       return false;
     }
   }
@@ -862,10 +871,10 @@ bool VerifierDeps::ValidateDependencies(Handle<mirror::ClassLoader> class_loader
 // the same lookup pattern.
 static ObjPtr<mirror::Class> FindClassAndClearException(ClassLinker* class_linker,
                                                         Thread* self,
-                                                        const char* name,
+                                                        const std::string& name,
                                                         Handle<mirror::ClassLoader> class_loader)
     REQUIRES_SHARED(Locks::mutator_lock_) {
-  ObjPtr<mirror::Class> result = class_linker->FindClass(self, name, class_loader);
+  ObjPtr<mirror::Class> result = class_linker->FindClass(self, name.c_str(), class_loader);
   if (result == nullptr) {
     DCHECK(self->IsExceptionPending());
     self->ClearException();
@@ -877,7 +886,8 @@ bool VerifierDeps::VerifyAssignability(Handle<mirror::ClassLoader> class_loader,
                                        const DexFile& dex_file,
                                        const std::set<TypeAssignability>& assignables,
                                        bool expected_assignability,
-                                       Thread* self) const {
+                                       Thread* self,
+                                       /* out */ std::string* error_msg) const {
   StackHandleScope<2> hs(self);
   ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
   MutableHandle<mirror::Class> source(hs.NewHandle<mirror::Class>(nullptr));
@@ -892,22 +902,19 @@ bool VerifierDeps::VerifyAssignability(Handle<mirror::ClassLoader> class_loader,
         FindClassAndClearException(class_linker, self, source_desc.c_str(), class_loader));
 
     if (destination == nullptr) {
-      LOG(INFO) << "VerifiersDeps: Could not resolve class " << destination_desc;
+      *error_msg = "Could not resolve class " + destination_desc;
       return false;
     }
 
     if (source == nullptr) {
-      LOG(INFO) << "VerifierDeps: Could not resolve class " << source_desc;
+      *error_msg = "Could not resolve class " + source_desc;
       return false;
     }
 
     DCHECK(destination->IsResolved() && source->IsResolved());
     if (destination->IsAssignableFrom(source.Get()) != expected_assignability) {
-      LOG(INFO) << "VerifierDeps: Class "
-                << destination_desc
-                << (expected_assignability ? " not " : " ")
-                << "assignable from "
-                << source_desc;
+      *error_msg = "Class " + destination_desc + (expected_assignability ? " not " : " ") +
+          "assignable from " + source_desc;
       return false;
     }
   }
@@ -917,31 +924,27 @@ bool VerifierDeps::VerifyAssignability(Handle<mirror::ClassLoader> class_loader,
 bool VerifierDeps::VerifyClasses(Handle<mirror::ClassLoader> class_loader,
                                  const DexFile& dex_file,
                                  const std::set<ClassResolution>& classes,
-                                 Thread* self) const {
+                                 Thread* self,
+                                 /* out */ std::string* error_msg) const {
   StackHandleScope<1> hs(self);
   ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
   MutableHandle<mirror::Class> cls(hs.NewHandle<mirror::Class>(nullptr));
   for (const auto& entry : classes) {
-    const char* descriptor = dex_file.StringByTypeIdx(entry.GetDexTypeIndex());
+    std::string descriptor = dex_file.StringByTypeIdx(entry.GetDexTypeIndex());
     cls.Assign(FindClassAndClearException(class_linker, self, descriptor, class_loader));
 
     if (entry.IsResolved()) {
       if (cls == nullptr) {
-        LOG(INFO) << "VerifierDeps: Could not resolve class " << descriptor;
+        *error_msg = "Could not resolve class " + descriptor;
         return false;
       } else if (entry.GetAccessFlags() != GetAccessFlags(cls.Get())) {
-        LOG(INFO) << "VerifierDeps: Unexpected access flags on class "
-                  << descriptor
-                  << std::hex
-                  << " (expected="
-                  << entry.GetAccessFlags()
-                  << ", actual="
-                  << GetAccessFlags(cls.Get()) << ")"
-                  << std::dec;
+        *error_msg = "Unexpected access flags on class " + descriptor
+            + " (expected=" + ToHex(entry.GetAccessFlags())
+            + ", actual=" + ToHex(GetAccessFlags(cls.Get())) + ")";
         return false;
       }
     } else if (cls != nullptr) {
-      LOG(INFO) << "VerifierDeps: Unexpected successful resolution of class " << descriptor;
+      *error_msg = "Unexpected successful resolution of class " + descriptor;
       return false;
     }
   }
@@ -960,7 +963,8 @@ static std::string GetFieldDescription(const DexFile& dex_file, uint32_t index)
 bool VerifierDeps::VerifyFields(Handle<mirror::ClassLoader> class_loader,
                                 const DexFile& dex_file,
                                 const std::set<FieldResolution>& fields,
-                                Thread* self) const {
+                                Thread* self,
+                                /* out */ std::string* error_msg) const {
   // Check recorded fields are resolved the same way, have the same recorded class,
   // and have the same recorded flags.
   ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
@@ -976,7 +980,7 @@ bool VerifierDeps::VerifyFields(Handle<mirror::ClassLoader> class_loader,
     ObjPtr<mirror::Class> cls = FindClassAndClearException(
         class_linker, self, expected_decl_klass.c_str(), class_loader);
     if (cls == nullptr) {
-      LOG(INFO) << "VerifierDeps: Could not resolve class " << expected_decl_klass;
+      *error_msg = "Could not resolve class " + expected_decl_klass;
       return false;
     }
     DCHECK(cls->IsResolved());
@@ -985,25 +989,25 @@ bool VerifierDeps::VerifyFields(Handle<mirror::ClassLoader> class_loader,
     if (entry.IsResolved()) {
       std::string temp;
       if (field == nullptr) {
-        LOG(INFO) << "VerifierDeps: Could not resolve field "
-                  << GetFieldDescription(dex_file, entry.GetDexFieldIndex());
+        *error_msg = "Could not resolve field " +
+            GetFieldDescription(dex_file, entry.GetDexFieldIndex());
         return false;
       } else if (expected_decl_klass != field->GetDeclaringClass()->GetDescriptor(&temp)) {
-        LOG(INFO) << "VerifierDeps: Unexpected declaring class for field resolution "
-                  << GetFieldDescription(dex_file, entry.GetDexFieldIndex())
-                  << " (expected=" << expected_decl_klass
-                  << ", actual=" << field->GetDeclaringClass()->GetDescriptor(&temp) << ")";
+        *error_msg = "Unexpected declaring class for field resolution "
+            + GetFieldDescription(dex_file, entry.GetDexFieldIndex())
+            + " (expected=" + expected_decl_klass
+            + ", actual=" + field->GetDeclaringClass()->GetDescriptor(&temp) + ")";
         return false;
       } else if (entry.GetAccessFlags() != GetAccessFlags(field)) {
-        LOG(INFO) << "VerifierDeps: Unexpected access flags for resolved field "
-                  << GetFieldDescription(dex_file, entry.GetDexFieldIndex())
-                  << std::hex << " (expected=" << entry.GetAccessFlags()
-                  << ", actual=" << GetAccessFlags(field) << ")" << std::dec;
+        *error_msg = "Unexpected access flags for resolved field "
+            + GetFieldDescription(dex_file, entry.GetDexFieldIndex())
+            + " (expected=" + ToHex(entry.GetAccessFlags())
+            + ", actual=" + ToHex(GetAccessFlags(field)) + ")";
         return false;
       }
     } else if (field != nullptr) {
-      LOG(INFO) << "VerifierDeps: Unexpected successful resolution of field "
-                << GetFieldDescription(dex_file, entry.GetDexFieldIndex());
+      *error_msg = "Unexpected successful resolution of field "
+          + GetFieldDescription(dex_file, entry.GetDexFieldIndex());
       return false;
     }
   }
@@ -1021,7 +1025,8 @@ static std::string GetMethodDescription(const DexFile& dex_file, uint32_t index)
 bool VerifierDeps::VerifyMethods(Handle<mirror::ClassLoader> class_loader,
                                  const DexFile& dex_file,
                                  const std::set<MethodResolution>& methods,
-                                 Thread* self) const {
+                                 Thread* self,
+                                 /* out */ std::string* error_msg) const {
   ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
   PointerSize pointer_size = class_linker->GetImagePointerSize();
 
@@ -1039,7 +1044,7 @@ bool VerifierDeps::VerifyMethods(Handle<mirror::ClassLoader> class_loader,
     ObjPtr<mirror::Class> cls = FindClassAndClearException(
         class_linker, self, expected_decl_klass.c_str(), class_loader);
     if (cls == nullptr) {
-      LOG(INFO) << "VerifierDeps: Could not resolve class " << expected_decl_klass;
+      *error_msg = "Could not resolve class " + expected_decl_klass;
       return false;
     }
     DCHECK(cls->IsResolved());
@@ -1053,53 +1058,94 @@ bool VerifierDeps::VerifyMethods(Handle<mirror::ClassLoader> class_loader,
     if (entry.IsResolved()) {
       std::string temp;
       if (method == nullptr) {
-        LOG(INFO) << "VerifierDeps: Could not resolve method "
-                  << GetMethodDescription(dex_file, entry.GetDexMethodIndex());
+        *error_msg = "Could not resolve method "
+            + GetMethodDescription(dex_file, entry.GetDexMethodIndex());
         return false;
       } else if (expected_decl_klass != method->GetDeclaringClass()->GetDescriptor(&temp)) {
-        LOG(INFO) << "VerifierDeps: Unexpected declaring class for method resolution "
-                  << GetMethodDescription(dex_file, entry.GetDexMethodIndex())
-                  << " (expected="
-                  << expected_decl_klass
-                  << ", actual="
-                  << method->GetDeclaringClass()->GetDescriptor(&temp)
-                  << ")";
+        *error_msg = "Unexpected declaring class for method resolution "
+            + GetMethodDescription(dex_file, entry.GetDexMethodIndex())
+            + " (expected=" + expected_decl_klass
+            + ", actual=" + method->GetDeclaringClass()->GetDescriptor(&temp) + ")";
         return false;
       } else if (entry.GetAccessFlags() != GetAccessFlags(method)) {
-        LOG(INFO) << "VerifierDeps: Unexpected access flags for resolved method resolution "
-                  << GetMethodDescription(dex_file, entry.GetDexMethodIndex())
-                  << std::hex
-                  << " (expected="
-                  << entry.GetAccessFlags()
-                  << ", actual="
-                  << GetAccessFlags(method) << ")"
-                  << std::dec;
+        *error_msg = "Unexpected access flags for resolved method resolution "
+            + GetMethodDescription(dex_file, entry.GetDexMethodIndex())
+            + " (expected=" + ToHex(entry.GetAccessFlags())
+            + ", actual=" + ToHex(GetAccessFlags(method)) + ")";
         return false;
       }
     } else if (method != nullptr) {
-      LOG(INFO) << "VerifierDeps: Unexpected successful resolution of method "
-                << GetMethodDescription(dex_file, entry.GetDexMethodIndex());
+      *error_msg = "Unexpected successful resolution of method "
+          + GetMethodDescription(dex_file, entry.GetDexMethodIndex());
       return false;
     }
   }
   return true;
 }
 
-bool VerifierDeps::VerifyDexFile(Handle<mirror::ClassLoader> class_loader,
-                                 const DexFile& dex_file,
-                                 const DexFileDeps& deps,
-                                 Thread* self) const {
-  bool result = VerifyAssignability(
-      class_loader, dex_file, deps.assignable_types_, /* expected_assignability= */ true, self);
-  result = result && VerifyAssignability(
-      class_loader, dex_file, deps.unassignable_types_, /* expected_assignability= */ false, self);
+bool VerifierDeps::VerifyInternalClasses(Handle<mirror::ClassLoader> class_loader,
+                                         const DexFile& dex_file,
+                                         const std::set<dex::TypeIndex>& unverified_classes,
+                                         Thread* self,
+                                         /* out */ std::string* error_msg) const {
+  ClassLinker* const class_linker = Runtime::Current()->GetClassLinker();
+
+  for (ClassAccessor accessor : dex_file.GetClasses()) {
+    std::string descriptor = accessor.GetDescriptor();
+    ObjPtr<mirror::Class> cls = FindClassAndClearException(class_linker,
+                                                           self,
+                                                           descriptor,
+                                                           class_loader);
+    if (UNLIKELY(cls == nullptr)) {
+      // Could not resolve class from the currently verified dex file.
+      // This can happen when the class fails to link. Check if this
+      // expected by looking in the `unverified_classes` set.
+      if (unverified_classes.find(accessor.GetClassDef().class_idx_) == unverified_classes.end()) {
+        *error_msg = "Failed to resolve internal class " + descriptor;
+        return false;
+      }
+      continue;
+    }
 
-  result = result && VerifyClasses(class_loader, dex_file, deps.classes_, self);
-  result = result && VerifyFields(class_loader, dex_file, deps.fields_, self);
+    // Check that the class resolved into the same dex file. Otherwise there is
+    // a different class with the same descriptor somewhere in one of the parent
+    // class loaders.
+    if (&cls->GetDexFile() != &dex_file) {
+      *error_msg = "Class " + descriptor + " redefines a class in a parent class loader "
+          + "(dexFile expected=" + accessor.GetDexFile().GetLocation()
+          + ", actual=" + cls->GetDexFile().GetLocation() + ")";
+      return false;
+    }
+  }
 
-  result = result && VerifyMethods(class_loader, dex_file, deps.methods_, self);
+  return true;
+}
 
-  return result;
+bool VerifierDeps::VerifyDexFile(Handle<mirror::ClassLoader> class_loader,
+                                 const DexFile& dex_file,
+                                 const DexFileDeps& deps,
+                                 Thread* self,
+                                 /* out */ std::string* error_msg) const {
+  return VerifyInternalClasses(class_loader,
+                               dex_file,
+                               deps.unverified_classes_,
+                               self,
+                               error_msg) &&
+         VerifyAssignability(class_loader,
+                             dex_file,
+                             deps.assignable_types_,
+                             /* expected_assignability= */ true,
+                             self,
+                             error_msg) &&
+         VerifyAssignability(class_loader,
+                             dex_file,
+                             deps.unassignable_types_,
+                             /* expected_assignability= */ false,
+                             self,
+                             error_msg) &&
+         VerifyClasses(class_loader, dex_file, deps.classes_, self, error_msg) &&
+         VerifyFields(class_loader, dex_file, deps.fields_, self, error_msg) &&
+         VerifyMethods(class_loader, dex_file, deps.methods_, self, error_msg);
 }
 
 }  // namespace verifier
diff --git a/runtime/verifier/verifier_deps.h b/runtime/verifier/verifier_deps.h
index dfd4a5c4fb..7c43a3b9c8 100644
--- a/runtime/verifier/verifier_deps.h
+++ b/runtime/verifier/verifier_deps.h
@@ -114,7 +114,9 @@ class VerifierDeps {
   void Dump(VariableIndentationOutputStream* vios) const;
 
   // Verify the encoded dependencies of this `VerifierDeps` are still valid.
-  bool ValidateDependencies(Handle<mirror::ClassLoader> class_loader, Thread* self) const
+  bool ValidateDependencies(Handle<mirror::ClassLoader> class_loader,
+                            Thread* self,
+                            /* out */ std::string* error_msg) const
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   const std::set<dex::TypeIndex>& GetUnverifiedClasses(const DexFile& dex_file) const {
@@ -287,14 +289,31 @@ class VerifierDeps {
   bool VerifyDexFile(Handle<mirror::ClassLoader> class_loader,
                      const DexFile& dex_file,
                      const DexFileDeps& deps,
-                     Thread* self) const
+                     Thread* self,
+                     /* out */ std::string* error_msg) const
+      REQUIRES_SHARED(Locks::mutator_lock_);
+
+  // Check that classes which are to be verified using these dependencies
+  // are not eclipsed by classes in parent class loaders, e.g. when vdex was
+  // created against SDK stubs and the app redefines a non-public class on
+  // boot classpath, or simply if a class is added during an OTA. In such cases,
+  // dependencies do not include the dependencies on the presumed-internal class
+  // and verification must fail.
+  // TODO(dbrazdil): Encode a set of redefined classes during full verification.
+  // If such class is found to be redefined at runtime, dependencies remain valid.
+  bool VerifyInternalClasses(Handle<mirror::ClassLoader> class_loader,
+                             const DexFile& dex_file,
+                             const std::set<dex::TypeIndex>& unverified_classes,
+                             Thread* self,
+                             /* out */ std::string* error_msg) const
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   bool VerifyAssignability(Handle<mirror::ClassLoader> class_loader,
                            const DexFile& dex_file,
                            const std::set<TypeAssignability>& assignables,
                            bool expected_assignability,
-                           Thread* self) const
+                           Thread* self,
+                           /* out */ std::string* error_msg) const
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Verify that the set of resolved classes at the point of creation
@@ -302,7 +321,8 @@ class VerifierDeps {
   bool VerifyClasses(Handle<mirror::ClassLoader> class_loader,
                      const DexFile& dex_file,
                      const std::set<ClassResolution>& classes,
-                     Thread* self) const
+                     Thread* self,
+                     /* out */ std::string* error_msg) const
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Verify that the set of resolved fields at the point of creation
@@ -311,7 +331,8 @@ class VerifierDeps {
   bool VerifyFields(Handle<mirror::ClassLoader> class_loader,
                     const DexFile& dex_file,
                     const std::set<FieldResolution>& classes,
-                    Thread* self) const
+                    Thread* self,
+                    /* out */ std::string* error_msg) const
       REQUIRES_SHARED(Locks::mutator_lock_)
       REQUIRES(!Locks::verifier_deps_lock_);
 
@@ -321,7 +342,8 @@ class VerifierDeps {
   bool VerifyMethods(Handle<mirror::ClassLoader> class_loader,
                      const DexFile& dex_file,
                      const std::set<MethodResolution>& methods,
-                     Thread* self) const
+                     Thread* self,
+                     /* out */ std::string* error_msg) const
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Map from DexFiles into dependencies collected from verification of their methods.
diff --git a/test/719-dm-verify-redefinition/check b/test/719-dm-verify-redefinition/check
index b5003bda2c..9845eee123 100644
--- a/test/719-dm-verify-redefinition/check
+++ b/test/719-dm-verify-redefinition/check
@@ -15,7 +15,7 @@
 # limitations under the License.
 
 # Search for the redefinition line and remove unnecessary tags.
-sed -e 's/^dex2oat[d]\?\(\|32\|64\)\ W.*\] Found redefinition of boot classes\. Not doing fast verification\./Found redefinition of boot classes\. Not doing fast verification\./g' "$2" > "$2.tmp1"
+sed -e 's/^dex2oat[d]\?\(\|32\|64\)\ W.*\] \(Fast verification failed: Class L[^;]*; redefines a class in a parent class loader\).*/\2/g' "$2" > "$2.tmp1"
 # Remove all other dex2oat/dalvikvm log lines.
 grep -v dex2oat "$2.tmp1" | grep -v dalvikvm >> "$2.tmp2"
 
diff --git a/test/719-dm-verify-redefinition/expected.txt b/test/719-dm-verify-redefinition/expected.txt
index 64fb4ea7ea..e1ab7d1e56 100644
--- a/test/719-dm-verify-redefinition/expected.txt
+++ b/test/719-dm-verify-redefinition/expected.txt
@@ -1,3 +1,3 @@
-Found redefinition of boot classes. Not doing fast verification.
+Fast verification failed: Class Ljava/util/BitSet; redefines a class in a parent class loader
 Hello, world!
 Correct resolution of boot class.
diff --git a/test/VerifierDeps/Iface.smali b/test/VerifierDeps/Iface.smali
index 8607307093..1ee2358f78 100644
--- a/test/VerifierDeps/Iface.smali
+++ b/test/VerifierDeps/Iface.smali
@@ -1,18 +1,16 @@
-# /*
-#  * Copyright (C) 2017 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.
-#  */
+# Copyright (C) 2017 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.
 
 .class public abstract interface LIface;
 .super Ljava/lang/Object;