diff --git a/compiler/verifier_deps_test.cc b/compiler/verifier_deps_test.cc
index e716cdb..4f06a91 100644
--- a/compiler/verifier_deps_test.cc
+++ b/compiler/verifier_deps_test.cc
@@ -524,7 +524,7 @@
                                          /* src */ "LMyThreadSet;",
                                          /* is_strict */ true,
                                          /* is_assignable */ true));
-  ASSERT_TRUE(HasAssignable("Ljava/util/Collection;", "LMyThreadSet;", true));
+  ASSERT_TRUE(HasAssignable("Ljava/util/Collection;", "Ljava/util/Set;", true));
 }
 
 TEST_F(VerifierDepsTest, Assignable_BothArrays_Resolved) {
@@ -539,26 +539,6 @@
   ASSERT_TRUE(HasAssignable("Ljava/util/TimeZone;", "Ljava/util/SimpleTimeZone;", true));
 }
 
-// We test that VerifierDeps does not try to optimize by storing assignability
-// of the component types. This is due to the fact that the component type may
-// be an erroneous class, even though the array type has resolved status.
-
-TEST_F(VerifierDepsTest, Assignable_ArrayToInterface1) {
-  ASSERT_TRUE(TestAssignabilityRecording(/* dst */ "Ljava/io/Serializable;",
-                                         /* src */ "[Ljava/util/TimeZone;",
-                                         /* is_strict */ true,
-                                         /* is_assignable */ true));
-  ASSERT_TRUE(HasAssignable("Ljava/io/Serializable;", "[Ljava/util/TimeZone;", true));
-}
-
-TEST_F(VerifierDepsTest, Assignable_ArrayToInterface2) {
-  ASSERT_TRUE(TestAssignabilityRecording(/* dst */ "Ljava/io/Serializable;",
-                                         /* src */ "[LMyThreadSet;",
-                                         /* is_strict */ true,
-                                         /* is_assignable */ true));
-  ASSERT_TRUE(HasAssignable("Ljava/io/Serializable;", "[LMyThreadSet;", true));
-}
-
 TEST_F(VerifierDepsTest, NotAssignable_BothInBoot) {
   ASSERT_TRUE(TestAssignabilityRecording(/* dst */ "Ljava/lang/Exception;",
                                          /* src */ "Ljava/util/SimpleTimeZone;",
@@ -1083,7 +1063,7 @@
 TEST_F(VerifierDepsTest, InvokeSuper_ThisAssignable) {
   ASSERT_TRUE(VerifyMethod("InvokeSuper_ThisAssignable"));
   ASSERT_TRUE(HasClass("Ljava/lang/Runnable;", true, "public abstract interface"));
-  ASSERT_TRUE(HasAssignable("Ljava/lang/Runnable;", "LMain;", true));
+  ASSERT_TRUE(HasAssignable("Ljava/lang/Runnable;", "Ljava/lang/Thread;", true));
   ASSERT_TRUE(HasMethod("interface",
                         "Ljava/lang/Runnable;",
                         "run",
diff --git a/runtime/verifier/verifier_deps.cc b/runtime/verifier/verifier_deps.cc
index c4058d6..15cc566 100644
--- a/runtime/verifier/verifier_deps.cc
+++ b/runtime/verifier/verifier_deps.cc
@@ -335,6 +335,60 @@
   }
 }
 
+mirror::Class* VerifierDeps::FindOneClassPathBoundaryForInterface(mirror::Class* destination,
+                                                                  mirror::Class* source) const {
+  DCHECK(destination->IsInterface());
+  DCHECK(IsInClassPath(destination));
+  Thread* thread = Thread::Current();
+  mirror::Class* current = source;
+  // Record the classes that are at the boundary between the compiled DEX files and
+  // the classpath. We will check those classes later to find one class that inherits
+  // `destination`.
+  std::vector<ObjPtr<mirror::Class>> boundaries;
+  // If the destination is a direct interface of a class defined in the DEX files being
+  // compiled, no need to record it.
+  while (!IsInClassPath(current)) {
+    for (size_t i = 0; i < current->NumDirectInterfaces(); ++i) {
+      ObjPtr<mirror::Class> direct = mirror::Class::GetDirectInterface(thread, current, i);
+      if (direct == destination) {
+        return nullptr;
+      } else if (IsInClassPath(direct)) {
+        boundaries.push_back(direct);
+      }
+    }
+    current = current->GetSuperClass();
+  }
+  DCHECK(current != nullptr);
+  boundaries.push_back(current);
+
+  // Check if we have an interface defined in the DEX files being compiled, direclty
+  // inheriting `destination`.
+  int32_t iftable_count = source->GetIfTableCount();
+  ObjPtr<mirror::IfTable> iftable = source->GetIfTable();
+  for (int32_t i = 0; i < iftable_count; ++i) {
+    mirror::Class* itf = iftable->GetInterface(i);
+    if (!IsInClassPath(itf)) {
+      for (size_t j = 0; j < itf->NumDirectInterfaces(); ++j) {
+        ObjPtr<mirror::Class> direct = mirror::Class::GetDirectInterface(thread, itf, j);
+        if (direct == destination) {
+          return nullptr;
+        } else if (IsInClassPath(direct)) {
+          boundaries.push_back(direct);
+        }
+      }
+    }
+  }
+
+  // Find a boundary making `source` inherit from `destination`. We must find one.
+  for (const ObjPtr<mirror::Class>& boundary : boundaries) {
+    if (destination->IsAssignableFrom(boundary)) {
+      return boundary.Ptr();
+    }
+  }
+  LOG(FATAL) << "Should have found a classpath boundary";
+  UNREACHABLE();
+}
+
 void VerifierDeps::AddAssignability(const DexFile& dex_file,
                                     mirror::Class* destination,
                                     mirror::Class* source,
@@ -403,17 +457,26 @@
     return;
   }
 
-  if (!IsInClassPath(source) && !source->IsInterface() && !destination->IsInterface()) {
-    // Find the super class at the classpath boundary. Only that class
-    // can change the assignability.
-    // TODO: also chase the boundary for interfaces.
-    do {
-      source = source->GetSuperClass();
-    } while (!IsInClassPath(source));
+  if (!IsInClassPath(source)) {
+    if (!destination->IsInterface()) {
+      DCHECK(!source->IsInterface());
+      // Find the super class at the classpath boundary. Only that class
+      // can change the assignability.
+      do {
+        source = source->GetSuperClass();
+      } while (!IsInClassPath(source));
 
-    // If that class is the actual destination, no need to record it.
-    if (source == destination) {
-      return;
+      // If that class is the actual destination, no need to record it.
+      if (source == destination) {
+        return;
+      }
+    } else if (is_assignable) {
+      source = FindOneClassPathBoundaryForInterface(destination, source);
+      if (source == nullptr) {
+        // There was no classpath boundary, no need to record.
+        return;
+      }
+      DCHECK(IsInClassPath(source));
     }
   }
 
diff --git a/runtime/verifier/verifier_deps.h b/runtime/verifier/verifier_deps.h
index 4b8206f..11750fd 100644
--- a/runtime/verifier/verifier_deps.h
+++ b/runtime/verifier/verifier_deps.h
@@ -204,6 +204,13 @@
   bool IsInClassPath(ObjPtr<mirror::Class> klass) const
       REQUIRES_SHARED(Locks::mutator_lock_);
 
+  // Finds the class in the classpath that makes `source` inherit` from `destination`.
+  // Returns null if a class defined in the compiled DEX files, and assignable to
+  // `source`, direclty inherits from `destination`.
+  mirror::Class* FindOneClassPathBoundaryForInterface(mirror::Class* destination,
+                                                      mirror::Class* source) const
+      REQUIRES_SHARED(Locks::mutator_lock_);
+
   // Returns the index of `str`. If it is defined in `dex_file_`, this is the dex
   // string ID. If not, an ID is assigned to the string and cached in `strings_`
   // of the corresponding DexFileDeps structure (either provided or inferred from