diff --git a/android/apex.go b/android/apex.go
index d3c0710..5118a0a 100644
--- a/android/apex.go
+++ b/android/apex.go
@@ -77,6 +77,10 @@
 
 	// Tests if this module is available for the specified APEX or ":platform"
 	AvailableFor(what string) bool
+
+	// DepIsInSameApex tests if the other module 'dep' is installed to the same
+	// APEX as this module
+	DepIsInSameApex(ctx BaseModuleContext, dep Module) bool
 }
 
 type ApexProperties struct {
@@ -154,6 +158,13 @@
 	return CheckAvailableForApex(what, m.ApexProperties.Apex_available)
 }
 
+func (m *ApexModuleBase) DepIsInSameApex(ctx BaseModuleContext, dep Module) bool {
+	// By default, if there is a dependency from A to B, we try to include both in the same APEX,
+	// unless B is explicitly from outside of the APEX (i.e. a stubs lib). Thus, returning true.
+	// This is overridden by some module types like apex.ApexBundle, cc.Module, java.Module, etc.
+	return true
+}
+
 func (m *ApexModuleBase) checkApexAvailableProperty(mctx BaseModuleContext) {
 	for _, n := range m.ApexProperties.Apex_available {
 		if n == availableToPlatform || n == availableToAnyApex {
diff --git a/android/sdk.go b/android/sdk.go
index 616fbe1..8e1e106 100644
--- a/android/sdk.go
+++ b/android/sdk.go
@@ -44,6 +44,17 @@
 	return s.Version == ""
 }
 
+// String returns string representation of this SdkRef for debugging purpose
+func (s SdkRef) String() string {
+	if s.Name == "" {
+		return "(No Sdk)"
+	}
+	if s.Unversioned() {
+		return s.Name
+	}
+	return s.Name + string(SdkVersionSeparator) + s.Version
+}
+
 // SdkVersionSeparator is a character used to separate an sdk name and its version
 const SdkVersionSeparator = '@'
 
diff --git a/apex/apex.go b/apex/apex.go
index 9382c19..3c32004 100644
--- a/apex/apex.go
+++ b/apex/apex.go
@@ -791,6 +791,11 @@
 	}
 }
 
+func (a *apexBundle) DepIsInSameApex(ctx android.BaseModuleContext, dep android.Module) bool {
+	// direct deps of an APEX bundle are all part of the APEX bundle
+	return true
+}
+
 func (a *apexBundle) getCertString(ctx android.BaseModuleContext) string {
 	certificate, overridden := ctx.DeviceConfig().OverrideCertificateFor(ctx.ModuleName())
 	if overridden {
diff --git a/cc/cc.go b/cc/cc.go
index f6f8abb..ef8906a 100644
--- a/cc/cc.go
+++ b/cc/cc.go
@@ -2182,6 +2182,16 @@
 	}
 }
 
+func (c *Module) DepIsInSameApex(ctx android.BaseModuleContext, dep android.Module) bool {
+	if depTag, ok := ctx.OtherModuleDependencyTag(dep).(dependencyTag); ok {
+		if cc, ok := dep.(*Module); ok && cc.IsStubs() && depTag.shared {
+			// dynamic dep to a stubs lib crosses APEX boundary
+			return false
+		}
+	}
+	return true
+}
+
 //
 // Defaults
 //
diff --git a/cc/testing.go b/cc/testing.go
index 11a5e3b..6fa6ea7 100644
--- a/cc/testing.go
+++ b/cc/testing.go
@@ -190,6 +190,7 @@
 			name: "crtbegin_so",
 			recovery_available: true,
 			vendor_available: true,
+			stl: "none",
 		}
 
 		cc_object {
@@ -208,6 +209,7 @@
 			name: "crtend_so",
 			recovery_available: true,
 			vendor_available: true,
+			stl: "none",
 		}
 
 		cc_object {
diff --git a/java/java.go b/java/java.go
index 52f3c11..d39c0d2 100644
--- a/java/java.go
+++ b/java/java.go
@@ -1567,6 +1567,12 @@
 	return len(srcFiles) > 0 || len(ctx.GetDirectDepsWithTag(staticLibTag)) > 0
 }
 
+func (j *Module) DepIsInSameApex(ctx android.BaseModuleContext, dep android.Module) bool {
+	depTag := ctx.OtherModuleDependencyTag(dep)
+	// dependencies other than the static linkage are all considered crossing APEX boundary
+	return depTag == staticLibTag
+}
+
 //
 // Java libraries (.jar file)
 //
diff --git a/sdk/sdk.go b/sdk/sdk.go
index d122cda..7668d91 100644
--- a/sdk/sdk.go
+++ b/sdk/sdk.go
@@ -122,6 +122,7 @@
 	// should have been mutated for the apex before the SDK requirements are set.
 	ctx.TopDown("SdkDepsMutator", sdkDepsMutator).Parallel()
 	ctx.BottomUp("SdkDepsReplaceMutator", sdkDepsReplaceMutator).Parallel()
+	ctx.TopDown("SdkRequirementCheck", sdkRequirementsMutator).Parallel()
 }
 
 type dependencyTag struct {
@@ -229,3 +230,31 @@
 		}
 	}
 }
+
+// Step 6: ensure that the dependencies from outside of the APEX are all from the required SDKs
+func sdkRequirementsMutator(mctx android.TopDownMutatorContext) {
+	if m, ok := mctx.Module().(interface {
+		DepIsInSameApex(ctx android.BaseModuleContext, dep android.Module) bool
+		RequiredSdks() android.SdkRefs
+	}); ok {
+		requiredSdks := m.RequiredSdks()
+		if len(requiredSdks) == 0 {
+			return
+		}
+		mctx.VisitDirectDeps(func(dep android.Module) {
+			if mctx.OtherModuleDependencyTag(dep) == android.DefaultsDepTag {
+				// dependency to defaults is always okay
+				return
+			}
+
+			// If the dep is from outside of the APEX, but is not in any of the
+			// required SDKs, we know that the dep is a violation.
+			if sa, ok := dep.(android.SdkAware); ok {
+				if !m.DepIsInSameApex(mctx, dep) && !requiredSdks.Contains(sa.ContainingSdk()) {
+					mctx.ModuleErrorf("depends on %q (in SDK %q) that isn't part of the required SDKs: %v",
+						sa.Name(), sa.ContainingSdk(), requiredSdks)
+				}
+			}
+		})
+	}
+}
diff --git a/sdk/sdk_test.go b/sdk/sdk_test.go
index 942556a..664bb7c 100644
--- a/sdk/sdk_test.go
+++ b/sdk/sdk_test.go
@@ -115,6 +115,23 @@
 	return ctx, config
 }
 
+func testSdkError(t *testing.T, pattern, bp string) {
+	t.Helper()
+	ctx, config := testSdkContext(t, bp)
+	_, errs := ctx.ParseFileList(".", []string{"Android.bp"})
+	if len(errs) > 0 {
+		android.FailIfNoMatchingErrors(t, pattern, errs)
+		return
+	}
+	_, errs = ctx.PrepareBuildActions(config)
+	if len(errs) > 0 {
+		android.FailIfNoMatchingErrors(t, pattern, errs)
+		return
+	}
+
+	t.Fatalf("missing expected error %q (0 errors are returned)", pattern)
+}
+
 // ensure that 'result' contains 'expected'
 func ensureContains(t *testing.T, result string, expected string) {
 	t.Helper()
@@ -303,6 +320,63 @@
 	ensureListContains(t, pathsToStrings(cpplibForMyApex2.Rule("ld").Implicits), sdkMemberV2.String())
 }
 
+func TestDepNotInRequiredSdks(t *testing.T) {
+	testSdkError(t, `module "myjavalib".*depends on "otherlib".*that isn't part of the required SDKs:.*`, `
+		sdk {
+			name: "mysdk",
+			java_libs: ["sdkmember"],
+		}
+
+		sdk_snapshot {
+			name: "mysdk@1",
+			java_libs: ["sdkmember_mysdk_1"],
+		}
+
+		java_import {
+			name: "sdkmember",
+			prefer: false,
+			host_supported: true,
+		}
+
+		java_import {
+			name: "sdkmember_mysdk_1",
+			sdk_member_name: "sdkmember",
+			host_supported: true,
+		}
+
+		java_library {
+			name: "myjavalib",
+			srcs: ["Test.java"],
+			libs: [
+				"sdkmember",
+				"otherlib",
+			],
+			system_modules: "none",
+			sdk_version: "none",
+			compile_dex: true,
+			host_supported: true,
+		}
+
+		// this lib is no in mysdk
+		java_library {
+			name: "otherlib",
+			srcs: ["Test.java"],
+			system_modules: "none",
+			sdk_version: "none",
+			compile_dex: true,
+			host_supported: true,
+		}
+
+		apex {
+			name: "myapex",
+			java_libs: ["myjavalib"],
+			uses_sdks: ["mysdk@1"],
+			key: "myapex.key",
+			certificate: ":myapex.cert",
+		}
+	`)
+}
+
 var buildDir string
 
 func setUp() {