diff --git a/examples/experimental_cc_shared_library.bzl b/examples/experimental_cc_shared_library.bzl
index 7d7fc37..ed3124c 100644
--- a/examples/experimental_cc_shared_library.bzl
+++ b/examples/experimental_cc_shared_library.bzl
@@ -15,18 +15,14 @@
 # used sparingly after making sure it's safe to use.
 LINKABLE_MORE_THAN_ONCE = "LINKABLE_MORE_THAN_ONCE"
 
-_EXPORTED_BY_TAG_BEGINNING = "exported_by="
-
-def exported_by(labels):
-    str_builder = []
-    for label in labels:
-        str_builder.append(label)
-    return _EXPORTED_BY_TAG_BEGINNING + ",".join(str_builder)
-
+CcSharedLibraryPermissionsInfo = provider(
+    fields = {
+        "targets": "Matches targets that can be exported.",
+    },
+)
 GraphNodeInfo = provider(
     fields = {
         "children": "Other GraphNodeInfo from dependencies of this target",
-        "exported_by": "Labels of targets that can export the library of this node",
         "label": "Label of the target visited",
         "linkable_more_than_once": "Linkable into more than a single cc_shared_library",
     },
@@ -161,6 +157,47 @@
 
     return pattern.package == value.package and pattern.name == value.name
 
+def _check_if_target_can_be_exported(target, current_label, permissions):
+    if (target.workspace_name != current_label.workspace_name or
+        _same_package_or_above(current_label, target)):
+        return True
+
+    matched_by_target = False
+    for permission in permissions:
+        for permission_target in permission[CcSharedLibraryPermissionsInfo].targets:
+            if _check_if_target_under_path(target, permission_target):
+                return True
+
+    return False
+
+def _check_if_target_should_be_exported_without_filter(target, current_label, permissions):
+    return _check_if_target_should_be_exported_with_filter(target, current_label, None, permissions)
+
+def _check_if_target_should_be_exported_with_filter(target, current_label, exports_filter, permissions):
+    should_be_exported = False
+    if exports_filter == None:
+        should_be_exported = True
+    else:
+        for export_filter in exports_filter:
+            export_filter_label = current_label.relative(export_filter)
+            if _check_if_target_under_path(target, export_filter_label):
+                should_be_exported = True
+                break
+
+    if should_be_exported:
+        if _check_if_target_can_be_exported(target, current_label, permissions):
+            return True
+        else:
+            matched_by_filter_text = ""
+            if exports_filter:
+                matched_by_filter_text = " (matched by filter) "
+            fail(str(target) + matched_by_filter_text +
+                 " cannot be exported from " + str(current_label) +
+                 " because it's not in the same package/subpackage and the library " +
+                 "doesn't have the necessary permissions. Use cc_shared_library_permissions.")
+
+    return False
+
 def _filter_inputs(
         ctx,
         feature_configuration,
@@ -174,7 +211,7 @@
     graph_structure_aspect_nodes = []
     dependency_linker_inputs = []
     direct_exports = {}
-    for export in ctx.attr.exports:
+    for export in ctx.attr.roots:
         direct_exports[str(export.label)] = True
         dependency_linker_inputs.extend(export[CcInfo].linking_context.linker_inputs.to_list())
         graph_structure_aspect_nodes.append(export[GraphNodeInfo])
@@ -191,6 +228,7 @@
         preloaded_deps_direct_labels,
     )
 
+    exports = {}
     owners_seen = {}
     for linker_input in dependency_linker_inputs:
         owner = str(linker_input.owner)
@@ -221,10 +259,19 @@
 
                 for static_dep_path in ctx.attr.static_deps:
                     static_dep_path_label = ctx.label.relative(static_dep_path)
-                    owner_label = linker_input.owner
                     if _check_if_target_under_path(linker_input.owner, static_dep_path_label):
                         can_be_linked_statically = True
                         break
+
+                if _check_if_target_should_be_exported_with_filter(
+                    linker_input.owner,
+                    ctx.label,
+                    ctx.attr.exports_filter,
+                    ctx.attr.permissions,
+                ):
+                    exports[owner] = True
+                    can_be_linked_statically = True
+
                 if can_be_linked_statically:
                     if not link_statically_labels[owner]:
                         link_once_static_libs.append(owner)
@@ -233,7 +280,7 @@
                     fail("We can't link " +
                          str(owner) + " either statically or dynamically")
 
-    return (linker_inputs, link_once_static_libs)
+    return (exports, linker_inputs, link_once_static_libs)
 
 def _same_package_or_above(label_a, label_b):
     if label_a.workspace_name != label_b.workspace_name:
@@ -262,23 +309,12 @@
 
     merged_cc_shared_library_info = _merge_cc_shared_library_infos(ctx)
     exports_map = _build_exports_map_from_only_dynamic_deps(merged_cc_shared_library_info)
-    for export in ctx.attr.exports:
+    for export in ctx.attr.roots:
         if str(export.label) in exports_map:
             fail("Trying to export a library already exported by a different shared library: " +
                  str(export.label))
 
-        can_be_exported = _same_package_or_above(ctx.label, export.label)
-
-        if not can_be_exported:
-            for exported_by in export[GraphNodeInfo].exported_by:
-                exported_by_label = Label(exported_by)
-                if _check_if_target_under_path(ctx.label, exported_by_label):
-                    can_be_exported = True
-                    break
-        if not can_be_exported:
-            fail(str(export.label) + " cannot be exported from " + str(ctx.label) +
-                 " because it's not in the same package/subpackage or the library " +
-                 "to be exported doesn't have this cc_shared_library in the exported_by tag.")
+        _check_if_target_should_be_exported_without_filter(export.label, ctx.label, ctx.attr.permissions)
 
     preloaded_deps_direct_labels = {}
     preloaded_dep_merged_cc_info = None
@@ -292,7 +328,7 @@
 
     link_once_static_libs_map = _build_link_once_static_libs_map(merged_cc_shared_library_info)
 
-    (linker_inputs, link_once_static_libs) = _filter_inputs(
+    (exports, linker_inputs, link_once_static_libs) = _filter_inputs(
         ctx,
         feature_configuration,
         cc_toolchain,
@@ -324,9 +360,8 @@
     for dep in ctx.attr.dynamic_deps:
         runfiles = runfiles.merge(dep[DefaultInfo].data_runfiles)
 
-    exports = []
-    for export in ctx.attr.exports:
-        exports.append(str(export.label))
+    for export in ctx.attr.roots:
+        exports[str(export.label)] = True
 
     return [
         DefaultInfo(
@@ -335,7 +370,7 @@
         ),
         CcSharedLibraryInfo(
             dynamic_deps = merged_cc_shared_library_info,
-            exports = exports,
+            exports = exports.keys(),
             link_once_static_libs = link_once_static_libs,
             linker_input = cc_common.create_linker_input(
                 owner = ctx.label,
@@ -353,42 +388,54 @@
             if GraphNodeInfo in dep:
                 children.append(dep[GraphNodeInfo])
 
-    exported_by = []
+    # TODO(bazel-team): Add flag to Bazel that can toggle the initialization of
+    # linkable_more_than_once.
     linkable_more_than_once = False
     if hasattr(ctx.rule.attr, "tags"):
         for tag in ctx.rule.attr.tags:
-            if tag.startswith(_EXPORTED_BY_TAG_BEGINNING) and len(tag) > len(_EXPORTED_BY_TAG_BEGINNING):
-                for target in tag[len(_EXPORTED_BY_TAG_BEGINNING):].split(","):
-                    # Only absolute labels allowed. Targets in same package
-                    # or subpackage can be exported anyway.
-                    if not target.startswith("//") and not target.startswith("@"):
-                        fail("Labels in exported_by of " + str(target) +
-                             " must be absolute.")
-
-                    Label(target)  # Checking synthax is ok.
-                exported_by.append(target)
-            elif tag == LINKABLE_MORE_THAN_ONCE:
+            if tag == LINKABLE_MORE_THAN_ONCE:
                 linkable_more_than_once = True
 
     return [GraphNodeInfo(
         label = ctx.label,
         children = children,
-        exported_by = exported_by,
         linkable_more_than_once = linkable_more_than_once,
     )]
 
+def _cc_shared_library_permissions_impl(ctx):
+    targets = []
+    for target_filter in ctx.attr.targets:
+        target_filter_label = ctx.label.relative(target_filter)
+        if not _check_if_target_under_path(target_filter_label, ctx.label.relative(":__subpackages__")):
+            fail("A cc_shared_library_permissions rule can only list " +
+                 "targets that are in the same package or a sub-package")
+        targets.append(target_filter_label)
+
+    return [CcSharedLibraryPermissionsInfo(
+        targets = targets,
+    )]
+
 graph_structure_aspect = aspect(
     attr_aspects = ["*"],
     implementation = _graph_structure_aspect_impl,
 )
 
+cc_shared_library_permissions = rule(
+    implementation = _cc_shared_library_permissions_impl,
+    attrs = {
+        "targets": attr.string_list(),
+    },
+)
+
 cc_shared_library = rule(
     implementation = _cc_shared_library_impl,
     attrs = {
         "additional_linker_inputs": attr.label_list(allow_files = True),
         "dynamic_deps": attr.label_list(providers = [CcSharedLibraryInfo]),
-        "exports": attr.label_list(providers = [CcInfo], aspects = [graph_structure_aspect]),
+        "exports_filter": attr.string_list(),
+        "permissions": attr.label_list(providers = [CcSharedLibraryPermissionsInfo]),
         "preloaded_deps": attr.label_list(providers = [CcInfo]),
+        "roots": attr.label_list(providers = [CcInfo], aspects = [graph_structure_aspect]),
         "static_deps": attr.string_list(),
         "user_link_flags": attr.string_list(),
         "_cc_toolchain": attr.label(default = "@bazel_tools//tools/cpp:current_cc_toolchain"),
diff --git a/examples/test_cc_shared_library/BUILD b/examples/test_cc_shared_library/BUILD
index 141b1aa..027717c 100644
--- a/examples/test_cc_shared_library/BUILD
+++ b/examples/test_cc_shared_library/BUILD
@@ -1,6 +1,6 @@
 load("//cc:defs.bzl", "cc_binary", "cc_library", "cc_test")
 load("//examples:experimental_cc_shared_library.bzl", "LINKABLE_MORE_THAN_ONCE", "cc_shared_library")
-load(":starlark_tests.bzl", "additional_inputs_test", "link_once_repeated_test", "linking_suffix_test", "paths_test")
+load(":starlark_tests.bzl", "additional_inputs_test", "build_failure_test", "linking_suffix_test", "paths_test")
 
 package(
     default_visibility = ["//examples/test_cc_shared_library:__subpackages__"],
@@ -28,6 +28,11 @@
     ],
     dynamic_deps = ["bar_so"],
     preloaded_deps = ["preloaded_dep"],
+    roots = [
+        "baz",
+        "foo",
+        "a_suffix",
+    ],
     static_deps = [
         "//examples/test_cc_shared_library:qux",
         "//examples/test_cc_shared_library:qux2",
@@ -37,24 +42,6 @@
         "-Wl,--version-script=$(location :foo.lds)",
         "-Wl,--script=$(location :additional_script.txt)",
     ],
-    exports = [
-        "foo",
-        # Not a problem to export "baz" which is depended on by foo
-        "baz",
-        # Case1
-        # This is fine. bar3 can be exported by "foo_so"
-        # even though bar3 is linked statically by bar_so, since bar_so
-        # doesn't export bar3 this is fine.
-        "bar3",
-        # Case2
-        # This is fine. foo depends on bar4. Even though bar is
-        # linked dynamically, when bar is pruned, we still have a dependency
-        # edge to bar4 from foo. Also bar_so doesn't export bar4.
-        #
-        # Note that even though the target claims to export bar4. Unless the version script is
-        # changed, the symbols from bar4 won't be exported.
-        "bar4",
-    ],
 )
 
 cc_library(
@@ -78,9 +65,16 @@
 )
 
 cc_library(
+    name = "a_suffix",
+    srcs = ["a_suffix.cc"],
+    hdrs = ["a_suffix.h"],
+)
+
+cc_library(
     name = "baz",
     srcs = ["baz.cc"],
     hdrs = ["baz.h"],
+    deps = ["bar3"],
 )
 
 cc_library(
@@ -101,6 +95,18 @@
     additional_linker_inputs = [
         ":bar.lds",
     ],
+    exports_filter = [
+        "bar3",  # Exported transitive dependency
+        "//examples/test_cc_shared_library3:bar",
+    ],
+    permissions = [
+        "//examples/test_cc_shared_library3:permissions",
+    ],
+    roots = [
+        "bar",
+        "bar2",
+        "@test_repo//:bar",
+    ],
     static_deps = [
         "//examples/test_cc_shared_library:barX",
         "@test_repo//:bar",
@@ -109,11 +115,6 @@
     user_link_flags = [
         "-Wl,--version-script=$(location :bar.lds)",
     ],
-    exports = [
-        "bar",
-        "bar2",
-        "@test_repo//:bar",
-    ],
 )
 
 cc_library(
@@ -139,18 +140,16 @@
     name = "bar2",
     srcs = ["bar2.cc"],
     hdrs = ["bar2.h"],
+    deps = ["bar3"],
 )
 
 cc_library(
     name = "bar3",
     srcs = ["bar3.cc"],
     hdrs = ["bar3.h"],
-)
-
-cc_library(
-    name = "bar4",
-    srcs = ["bar4.cc"],
-    hdrs = ["bar4.h"],
+    deps = [
+        "//examples/test_cc_shared_library3:bar",
+    ],
 )
 
 sh_test(
@@ -174,11 +173,25 @@
     target_under_test = ":foo_so",
 )
 
-link_once_repeated_test(
+build_failure_test(
     name = "link_once_repeated_test",
+    message = "already linked statically in " +
+              "//examples/test_cc_shared_library:foo_so but not exported.",
     target_under_test = "//examples/test_cc_shared_library/failing_targets:should_fail_binary",
 )
 
 paths_test(
     name = "path_matching_test",
 )
+
+build_failure_test(
+    name = "export_without_permissions_test",
+    message = "doesn't have the necessary permissions",
+    target_under_test = "//examples/test_cc_shared_library/failing_targets:permissions_fail_so",
+)
+
+build_failure_test(
+    name = "forbidden_target_permissions_test",
+    message = "can only list targets that are in the same package or a sub-package",
+    target_under_test = "//examples/test_cc_shared_library/failing_targets:permissions_fail",
+)
diff --git a/examples/test_cc_shared_library/a_suffix.cc b/examples/test_cc_shared_library/a_suffix.cc
new file mode 100644
index 0000000..df9ccd2
--- /dev/null
+++ b/examples/test_cc_shared_library/a_suffix.cc
@@ -0,0 +1,3 @@
+#include "examples/test_cc_shared_library/a_suffix.h"
+
+int a_suffix() { return 42; }
diff --git a/examples/test_cc_shared_library/a_suffix.h b/examples/test_cc_shared_library/a_suffix.h
new file mode 100644
index 0000000..888be29
--- /dev/null
+++ b/examples/test_cc_shared_library/a_suffix.h
@@ -0,0 +1,6 @@
+#ifndef EXAMPLES_TEST_CC_SHARED_LIBRARY_A_SUFFIX_H_
+#define EXAMPLES_TEST_CC_SHARED_LIBRARY_A_SUFFIX_H_
+
+int a_suffix();
+
+#endif  // EXAMPLES_TEST_CC_SHARED_LIBRARY_A_SUFFIX_H_
diff --git a/examples/test_cc_shared_library/bar4.cc b/examples/test_cc_shared_library/bar4.cc
deleted file mode 100644
index ad2a110..0000000
--- a/examples/test_cc_shared_library/bar4.cc
+++ /dev/null
@@ -1,3 +0,0 @@
-#include "examples/test_cc_shared_library/bar4.h"
-
-int bar4() { return 42; }
diff --git a/examples/test_cc_shared_library/bar4.h b/examples/test_cc_shared_library/bar4.h
deleted file mode 100644
index e60ffff..0000000
--- a/examples/test_cc_shared_library/bar4.h
+++ /dev/null
@@ -1,6 +0,0 @@
-#ifndef EXAMPLES_TEST_CC_SHARED_LIBRARY_BAR_4_H_
-#define EXAMPLES_TEST_CC_SHARED_LIBRARY_BAR_4_H_
-
-int bar4();
-
-#endif  // EXAMPLES_TEST_CC_SHARED_LIBRARY_BAR_4_H_
diff --git a/examples/test_cc_shared_library/failing_targets/BUILD b/examples/test_cc_shared_library/failing_targets/BUILD
index c2901e7..16e4b47 100644
--- a/examples/test_cc_shared_library/failing_targets/BUILD
+++ b/examples/test_cc_shared_library/failing_targets/BUILD
@@ -1,18 +1,37 @@
 load("//cc:defs.bzl", "cc_binary")
+load("//examples:experimental_cc_shared_library.bzl", "cc_shared_library", "cc_shared_library_permissions")
 
 package(
     default_visibility = ["//examples/test_cc_shared_library:__pkg__"],
 )
 
+TAGS = [
+    "manual",
+    "nobuilder",
+]
+
 cc_binary(
     name = "should_fail_binary",
     dynamic_deps = ["//examples/test_cc_shared_library:foo_so"],
-    tags = [
-        "manual",
-        "nobuilder",
-    ],
+    tags = TAGS,
     deps = [
         "//examples/test_cc_shared_library:foo",
         "//examples/test_cc_shared_library:qux",
     ],
 )
+
+cc_shared_library(
+    name = "permissions_fail_so",
+    roots = [
+        "//examples/test_cc_shared_library3:bar",
+    ],
+    tags = TAGS,
+)
+
+cc_shared_library_permissions(
+    name = "permissions_fail",
+    tags = TAGS,
+    targets = [
+        "//examples/test_cc_shared_library:foo",
+    ],
+)
diff --git a/examples/test_cc_shared_library/starlark_tests.bzl b/examples/test_cc_shared_library/starlark_tests.bzl
index 76a9e00..950b08d 100644
--- a/examples/test_cc_shared_library/starlark_tests.bzl
+++ b/examples/test_cc_shared_library/starlark_tests.bzl
@@ -11,7 +11,7 @@
 
     for arg in reversed(actions[1].argv):
         if arg.find(".a") != -1 or arg.find("-l") != -1:
-            asserts.equals(env, "libbar4.a", arg[arg.rindex("/") + 1:])
+            asserts.equals(env, "liba_suffix.a", arg[arg.rindex("/") + 1:])
             break
 
     return analysistest.end(env)
@@ -36,14 +36,18 @@
 
 additional_inputs_test = analysistest.make(_additional_inputs_test_impl)
 
-def _link_once_repeated_test_impl(ctx):
+def _build_failure_test_impl(ctx):
     env = analysistest.begin(ctx)
 
-    asserts.expect_failure(env, "already linked statically")
+    asserts.expect_failure(env, ctx.attr.message)
 
     return analysistest.end(env)
 
-link_once_repeated_test = analysistest.make(_link_once_repeated_test_impl, expect_failure = True)
+build_failure_test = analysistest.make(
+    _build_failure_test_impl,
+    expect_failure = True,
+    attrs = {"message": attr.string()},
+)
 
 def _paths_test_impl(ctx):
     env = unittest.begin(ctx)
diff --git a/examples/test_cc_shared_library2/BUILD b/examples/test_cc_shared_library2/BUILD
index 9c07def..802d60f 100644
--- a/examples/test_cc_shared_library2/BUILD
+++ b/examples/test_cc_shared_library2/BUILD
@@ -1,10 +1,8 @@
 load("@rules_cc//cc:defs.bzl", "cc_library")
-load("@rules_cc//examples:experimental_cc_shared_library.bzl", "exported_by")
 
 cc_library(
     name = "bar",
     srcs = ["bar.cc"],
     hdrs = ["bar.h"],
-    tags = [exported_by(["@rules_cc//examples/test_cc_shared_library:bar_so"])],
     visibility = ["//visibility:public"],
 )
diff --git a/examples/test_cc_shared_library3/BUILD b/examples/test_cc_shared_library3/BUILD
new file mode 100644
index 0000000..685071c
--- /dev/null
+++ b/examples/test_cc_shared_library3/BUILD
@@ -0,0 +1,17 @@
+load("@rules_cc//cc:defs.bzl", "cc_library")
+load("//examples:experimental_cc_shared_library.bzl", "cc_shared_library_permissions")
+
+cc_library(
+    name = "bar",
+    srcs = ["bar.cc"],
+    hdrs = ["bar.h"],
+    visibility = ["//visibility:public"],
+)
+
+cc_shared_library_permissions(
+    name = "permissions",
+    targets = [
+        "//examples/test_cc_shared_library3:bar",
+    ],
+    visibility = ["//examples/test_cc_shared_library:__pkg__"],
+)
diff --git a/examples/test_cc_shared_library3/bar.cc b/examples/test_cc_shared_library3/bar.cc
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/examples/test_cc_shared_library3/bar.cc
diff --git a/examples/test_cc_shared_library3/bar.h b/examples/test_cc_shared_library3/bar.h
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/examples/test_cc_shared_library3/bar.h