diff --git a/cc/fuzz.go b/cc/fuzz.go
index ef7db79..15eafc8 100644
--- a/cc/fuzz.go
+++ b/cc/fuzz.go
@@ -123,19 +123,23 @@
 	// Enumerate the first level of dependencies, as we discard all non-library
 	// modules in the BFS loop below.
 	ctx.VisitDirectDeps(module, func(dep android.Module) {
-		fringe = append(fringe, dep)
+		if isValidSharedDependency(dep, sharedDeps) {
+			fringe = append(fringe, dep)
+		}
 	})
 
 	for i := 0; i < len(fringe); i++ {
 		module := fringe[i]
-		if !isValidSharedDependency(module, sharedDeps) {
+		if _, exists := sharedDeps[module.Name()]; exists {
 			continue
 		}
 
 		ccModule := module.(*Module)
 		sharedDeps[ccModule.Name()] = ccModule.UnstrippedOutputFile()
 		ctx.VisitDirectDeps(module, func(dep android.Module) {
-			fringe = append(fringe, dep)
+			if isValidSharedDependency(dep, sharedDeps) {
+				fringe = append(fringe, dep)
+			}
 		})
 	}
 }
@@ -155,10 +159,21 @@
 	if linkable, ok := dependency.(LinkableInterface); !ok || // Discard non-linkables.
 		!linkable.CcLibraryInterface() || !linkable.Shared() || // Discard static libs.
 		linkable.UseVndk() || // Discard vendor linked libraries.
-		!linkable.CcLibrary() || linkable.BuildStubs() { // Discard stubs libs (only CCLibrary variants).
+		// Discard stubs libs (only CCLibrary variants). Prebuilt libraries should not
+		// be excluded on the basis of they're not CCLibrary()'s.
+		(linkable.CcLibrary() && linkable.BuildStubs()) {
 		return false
 	}
 
+	// We discarded module stubs libraries above, but the LLNDK prebuilts stubs
+	// libraries must be handled differently - by looking for the stubDecorator.
+	// Discard LLNDK prebuilts stubs as well.
+	if ccLibrary, isCcLibrary := dependency.(*Module); isCcLibrary {
+		if _, isLLndkStubLibrary := ccLibrary.linker.(*stubDecorator); isLLndkStubLibrary {
+			return false
+		}
+	}
+
 	// If this library has already been traversed, we don't need to do any more work.
 	if _, exists := sharedDeps[dependency.Name()]; exists {
 		return false