diff --git a/apex/apex_test.go b/apex/apex_test.go
index 988c1ce..54c1fac 100644
--- a/apex/apex_test.go
+++ b/apex/apex_test.go
@@ -20,6 +20,7 @@
 	"path/filepath"
 	"reflect"
 	"regexp"
+	"slices"
 	"sort"
 	"strconv"
 	"strings"
@@ -28,6 +29,7 @@
 	"android/soong/aconfig/codegen"
 
 	"github.com/google/blueprint"
+	"github.com/google/blueprint/bpmodify"
 	"github.com/google/blueprint/proptools"
 
 	"android/soong/android"
@@ -225,6 +227,10 @@
 	"system/sepolicy/apex/myapex-file_contexts": nil,
 })
 
+var prepareForTestWithOtherapex = android.FixtureMergeMockFs(android.MockFS{
+	"system/sepolicy/apex/otherapex-file_contexts": nil,
+})
+
 // ensure that 'result' equals 'expected'
 func ensureEquals(t *testing.T, result string, expected string) {
 	t.Helper()
@@ -12114,3 +12120,398 @@
 	fileList := android.ContentFromFileRuleForTests(t, result, partition.Output("fileList"))
 	android.AssertDeepEquals(t, "filesystem with apex", "apex/myapex.apex\n", fileList)
 }
+
+func TestApexVerifyNativeImplementationLibs(t *testing.T) {
+	t.Parallel()
+
+	extractDepenencyPathFromErrors := func(errs []error) []string {
+		i := slices.IndexFunc(errs, func(err error) bool {
+			return strings.Contains(err.Error(), "dependency path:")
+		})
+		if i < 0 {
+			return nil
+		}
+		var dependencyPath []string
+		for _, err := range errs[i+1:] {
+			s := err.Error()
+			lastSpace := strings.LastIndexByte(s, ' ')
+			if lastSpace >= 0 {
+				dependencyPath = append(dependencyPath, s[lastSpace+1:])
+			}
+		}
+		return dependencyPath
+	}
+
+	checkErrors := func(wantDependencyPath []string) func(t *testing.T, result *android.TestResult) {
+		return func(t *testing.T, result *android.TestResult) {
+			t.Helper()
+			if len(result.Errs) == 0 {
+				t.Fatalf("expected errors")
+			}
+			t.Log("found errors:")
+			for _, err := range result.Errs {
+				t.Log(err)
+			}
+			if g, w := result.Errs[0].Error(), "library in apex transitively linked against implementation library"; !strings.Contains(g, w) {
+				t.Fatalf("expected error %q, got %q", w, g)
+			}
+			dependencyPath := extractDepenencyPathFromErrors(result.Errs)
+			if g, w := dependencyPath, wantDependencyPath; !slices.Equal(g, w) {
+				t.Errorf("expected dependency path %q, got %q", w, g)
+			}
+		}
+	}
+
+	addToSharedLibs := func(module, lib string) func(bp *bpmodify.Blueprint) {
+		return func(bp *bpmodify.Blueprint) {
+			m := bp.ModulesByName(module)
+			props, err := m.GetOrCreateProperty(bpmodify.List, "shared_libs")
+			if err != nil {
+				panic(err)
+			}
+			props.AddStringToList(lib)
+		}
+	}
+
+	bpTemplate := `
+	apex {
+		name: "myapex",
+		key: "myapex.key",
+		native_shared_libs: ["mylib"],
+		rust_dyn_libs: ["libmyrust"],
+		binaries: ["mybin", "myrustbin"],
+		jni_libs: ["libjni"],
+		apps: ["myapp"],
+		updatable: false,
+	}
+
+	apex {
+		name: "otherapex",
+		key: "myapex.key",
+		native_shared_libs: ["libotherapex"],
+		updatable: false,
+	}
+
+	apex_key {
+		name: "myapex.key",
+		public_key: "testkey.avbpubkey",
+		private_key: "testkey.pem",
+	}
+
+	cc_library {
+		name: "mylib",
+		srcs: ["foo.cpp"],
+		apex_available: ["myapex"],
+	}
+
+	cc_binary {
+		name: "mybin",
+		srcs: ["foo.cpp"],
+		apex_available: ["myapex"],
+	}
+
+	rust_library {
+		name: "libmyrust",
+		crate_name: "myrust",
+		srcs: ["src/lib.rs"],
+		rustlibs: ["libmyrust_transitive_dylib"],
+		rlibs: ["libmyrust_transitive_rlib"],
+		apex_available: ["myapex"],
+	}
+
+	rust_library{
+		name: "libmyrust_transitive_dylib",
+		crate_name: "myrust_transitive_dylib",
+		srcs: ["src/lib.rs"],
+		apex_available: ["myapex"],
+	}
+
+	rust_library {
+		name: "libmyrust_transitive_rlib",
+		crate_name: "myrust_transitive_rlib",
+		srcs: ["src/lib.rs"],
+		apex_available: ["myapex"],
+	}
+
+	rust_binary {
+		name: "myrustbin",
+		srcs: ["src/main.rs"],
+		apex_available: ["myapex"],
+	}
+
+	cc_library {
+		name: "libbar",
+		sdk_version: "current",
+		srcs: ["bar.cpp"],
+		apex_available: ["myapex"],
+		stl: "none",
+	}
+
+	android_app {
+		name: "myapp",
+		jni_libs: ["libembeddedjni"],
+		use_embedded_native_libs: true,
+		sdk_version: "current",
+		apex_available: ["myapex"],
+	}
+
+	cc_library {
+		name: "libembeddedjni",
+		sdk_version: "current",
+		srcs: ["bar.cpp"],
+		apex_available: ["myapex"],
+		stl: "none",
+	}
+
+	cc_library {
+		name: "libjni",
+		sdk_version: "current",
+		srcs: ["bar.cpp"],
+		apex_available: ["myapex"],
+		stl: "none",
+	}
+
+	cc_library {
+		name: "libotherapex",
+		sdk_version: "current",
+		srcs: ["otherapex.cpp"],
+		apex_available: ["otherapex"],
+		stubs: {
+			symbol_file: "libotherapex.map.txt",
+			versions: ["1", "2", "3"],
+		},
+		stl: "none",
+	}
+
+	cc_library {
+		name: "libplatform",
+		sdk_version: "current",
+		srcs: ["libplatform.cpp"],
+		stubs: {
+			symbol_file: "libplatform.map.txt",
+			versions: ["1", "2", "3"],
+		},
+		stl: "none",
+		system_shared_libs: [],
+	}
+	`
+
+	testCases := []struct {
+		name           string
+		bpModifier     func(bp *bpmodify.Blueprint)
+		dependencyPath []string
+	}{
+		{
+			name:           "library dependency in other apex",
+			bpModifier:     addToSharedLibs("mylib", "libotherapex#impl"),
+			dependencyPath: []string{"myapex", "mylib", "libotherapex"},
+		},
+		{
+			name: "transitive library dependency in other apex",
+			bpModifier: func(bp *bpmodify.Blueprint) {
+				addToSharedLibs("mylib", "libbar")(bp)
+				addToSharedLibs("libbar", "libotherapex#impl")(bp)
+			},
+			dependencyPath: []string{"myapex", "mylib", "libbar", "libotherapex"},
+		},
+		{
+			name:           "library dependency in platform",
+			bpModifier:     addToSharedLibs("mylib", "libplatform#impl"),
+			dependencyPath: []string{"myapex", "mylib", "libplatform"},
+		},
+		{
+			name:           "jni library dependency in other apex",
+			bpModifier:     addToSharedLibs("libjni", "libotherapex#impl"),
+			dependencyPath: []string{"myapex", "libjni", "libotherapex"},
+		},
+		{
+			name: "transitive jni library dependency in other apex",
+			bpModifier: func(bp *bpmodify.Blueprint) {
+				addToSharedLibs("libjni", "libbar")(bp)
+				addToSharedLibs("libbar", "libotherapex#impl")(bp)
+			},
+			dependencyPath: []string{"myapex", "libjni", "libbar", "libotherapex"},
+		},
+		{
+			name:           "jni library dependency in platform",
+			bpModifier:     addToSharedLibs("libjni", "libplatform#impl"),
+			dependencyPath: []string{"myapex", "libjni", "libplatform"},
+		},
+		{
+			name: "transitive jni library dependency in platform",
+			bpModifier: func(bp *bpmodify.Blueprint) {
+				addToSharedLibs("libjni", "libbar")(bp)
+				addToSharedLibs("libbar", "libplatform#impl")(bp)
+			},
+			dependencyPath: []string{"myapex", "libjni", "libbar", "libplatform"},
+		},
+		// TODO: embedded JNI in apps should be checked too, but Soong currently just packages the transitive
+		//  JNI libraries even if they came from another apex.
+		//{
+		//	name:           "app jni library dependency in other apex",
+		//	bpModifier:     addToSharedLibs("libembeddedjni", "libotherapex#impl"),
+		//	dependencyPath: []string{"myapex", "myapp", "libembeddedjni", "libotherapex"},
+		//},
+		//{
+		//	name: "transitive app jni library dependency in other apex",
+		//	bpModifier: func(bp *bpmodify.Blueprint) {
+		//		addToSharedLibs("libembeddedjni", "libbar")(bp)
+		//		addToSharedLibs("libbar", "libotherapex#impl")(bp)
+		//	},
+		//	dependencyPath: []string{"myapex", "myapp", "libembeddedjni", "libbar", "libotherapex"},
+		//},
+		//{
+		//	name:           "app jni library dependency in platform",
+		//	bpModifier:     addToSharedLibs("libembeddedjni", "libplatform#impl"),
+		//	dependencyPath: []string{"myapex", "myapp", "libembeddedjni", "libplatform"},
+		//},
+		//{
+		//	name: "transitive app jni library dependency in platform",
+		//	bpModifier: func(bp *bpmodify.Blueprint) {
+		//		addToSharedLibs("libembeddedjni", "libbar")(bp)
+		//		addToSharedLibs("libbar", "libplatform#impl")(bp)
+		//	},
+		//	dependencyPath: []string{"myapex", "myapp", "libembeddedjni", "libbar", "libplatform"},
+		//},
+		{
+			name:           "binary dependency in other apex",
+			bpModifier:     addToSharedLibs("mybin", "libotherapex#impl"),
+			dependencyPath: []string{"myapex", "mybin", "libotherapex"},
+		},
+		{
+			name: "transitive binary dependency in other apex",
+			bpModifier: func(bp *bpmodify.Blueprint) {
+				addToSharedLibs("mybin", "libbar")(bp)
+				addToSharedLibs("libbar", "libotherapex#impl")(bp)
+			},
+			dependencyPath: []string{"myapex", "mybin", "libbar", "libotherapex"},
+		},
+		{
+			name:           "binary dependency in platform",
+			bpModifier:     addToSharedLibs("mybin", "libplatform#impl"),
+			dependencyPath: []string{"myapex", "mybin", "libplatform"},
+		},
+		{
+			name: "transitive binary dependency in platform",
+			bpModifier: func(bp *bpmodify.Blueprint) {
+				addToSharedLibs("mybin", "libbar")(bp)
+				addToSharedLibs("libbar", "libplatform#impl")(bp)
+			},
+			dependencyPath: []string{"myapex", "mybin", "libbar", "libplatform"},
+		},
+
+		{
+			name:           "rust library dependency in other apex",
+			bpModifier:     addToSharedLibs("libmyrust", "libotherapex#impl"),
+			dependencyPath: []string{"myapex", "libmyrust", "libotherapex"},
+		},
+		{
+			name: "transitive rust library dependency in other apex",
+			bpModifier: func(bp *bpmodify.Blueprint) {
+				addToSharedLibs("libmyrust", "libbar")(bp)
+				addToSharedLibs("libbar", "libotherapex#impl")(bp)
+			},
+			dependencyPath: []string{"myapex", "libmyrust", "libbar", "libotherapex"},
+		},
+		{
+			name:           "rust library dependency in platform",
+			bpModifier:     addToSharedLibs("libmyrust", "libplatform#impl"),
+			dependencyPath: []string{"myapex", "libmyrust", "libplatform"},
+		},
+		{
+			name: "transitive rust library dependency in platform",
+			bpModifier: func(bp *bpmodify.Blueprint) {
+				addToSharedLibs("libmyrust", "libbar")(bp)
+				addToSharedLibs("libbar", "libplatform#impl")(bp)
+			},
+			dependencyPath: []string{"myapex", "libmyrust", "libbar", "libplatform"},
+		},
+		{
+			name: "transitive rust library dylib dependency in other apex",
+			bpModifier: func(bp *bpmodify.Blueprint) {
+				addToSharedLibs("libmyrust_transitive_dylib", "libotherapex#impl")(bp)
+			},
+			dependencyPath: []string{"myapex", "libmyrust", "libmyrust_transitive_dylib", "libotherapex"},
+		},
+		{
+			name: "transitive rust library dylib dependency in platform",
+			bpModifier: func(bp *bpmodify.Blueprint) {
+				addToSharedLibs("libmyrust_transitive_dylib", "libplatform#impl")(bp)
+			},
+			dependencyPath: []string{"myapex", "libmyrust", "libmyrust_transitive_dylib", "libplatform"},
+		},
+		{
+			name: "transitive rust library rlib dependency in other apex",
+			bpModifier: func(bp *bpmodify.Blueprint) {
+				addToSharedLibs("libmyrust_transitive_rlib", "libotherapex#impl")(bp)
+			},
+			dependencyPath: []string{"myapex", "libmyrust", "libmyrust_transitive_rlib", "libotherapex"},
+		},
+		{
+			name: "transitive rust library rlib dependency in platform",
+			bpModifier: func(bp *bpmodify.Blueprint) {
+				addToSharedLibs("libmyrust_transitive_rlib", "libplatform#impl")(bp)
+			},
+			dependencyPath: []string{"myapex", "libmyrust", "libmyrust_transitive_rlib", "libplatform"},
+		},
+		{
+			name:           "rust binary dependency in other apex",
+			bpModifier:     addToSharedLibs("myrustbin", "libotherapex#impl"),
+			dependencyPath: []string{"myapex", "myrustbin", "libotherapex"},
+		},
+		{
+			name: "transitive rust binary dependency in other apex",
+			bpModifier: func(bp *bpmodify.Blueprint) {
+				addToSharedLibs("myrustbin", "libbar")(bp)
+				addToSharedLibs("libbar", "libotherapex#impl")(bp)
+			},
+			dependencyPath: []string{"myapex", "myrustbin", "libbar", "libotherapex"},
+		},
+		{
+			name:           "rust binary dependency in platform",
+			bpModifier:     addToSharedLibs("myrustbin", "libplatform#impl"),
+			dependencyPath: []string{"myapex", "myrustbin", "libplatform"},
+		},
+		{
+			name: "transitive rust binary dependency in platform",
+			bpModifier: func(bp *bpmodify.Blueprint) {
+				addToSharedLibs("myrustbin", "libbar")(bp)
+				addToSharedLibs("libbar", "libplatform#impl")(bp)
+			},
+			dependencyPath: []string{"myapex", "myrustbin", "libbar", "libplatform"},
+		},
+	}
+
+	for _, testCase := range testCases {
+		t.Run(testCase.name, func(t *testing.T) {
+			t.Parallel()
+			bp, err := bpmodify.NewBlueprint("", []byte(bpTemplate))
+			if err != nil {
+				t.Fatal(err)
+			}
+			if testCase.bpModifier != nil {
+				func() {
+					defer func() {
+						if r := recover(); r != nil {
+							t.Fatalf("panic in bpModifier: %v", r)
+						}
+					}()
+					testCase.bpModifier(bp)
+				}()
+			}
+			android.GroupFixturePreparers(
+				android.PrepareForTestWithAndroidBuildComponents,
+				cc.PrepareForTestWithCcBuildComponents,
+				java.PrepareForTestWithDexpreopt,
+				rust.PrepareForTestWithRustDefaultModules,
+				PrepareForTestWithApexBuildComponents,
+				prepareForTestWithMyapex,
+				prepareForTestWithOtherapex,
+				android.FixtureModifyProductVariables(func(variables android.FixtureProductVariables) {
+					variables.BuildId = proptools.StringPtr("TEST.BUILD_ID")
+				}),
+			).ExtendWithErrorHandler(android.FixtureCustomErrorHandler(checkErrors(testCase.dependencyPath))).
+				RunTestWithBp(t, bp.String())
+		})
+	}
+}