diff --git a/cc/system_library.bzl b/cc/system_library.bzl
index 7a55eb7..41f286e 100644
--- a/cc/system_library.bzl
+++ b/cc/system_library.bzl
@@ -7,11 +7,11 @@
 ENV_VAR_SEPARATOR = ","
 ENV_VAR_ASSIGNMENT = "="
 
-def _make_flags(array_of_strings, prefix):
+def _make_flags(flag_values, flag):
     flags = []
-    if array_of_strings:
-        for s in array_of_strings:
-            flags.append(prefix + s)
+    if flag_values:
+        for s in flag_values:
+            flags.append(flag + s)
     return " ".join(flags)
 
 def _split_env_var(repo_ctx, var_name):
@@ -39,7 +39,7 @@
     return _split_env_var(repo_ctx, var_name).get(key, default = [])
 
 def _execute_bash(repo_ctx, cmd):
-    return repo_ctx.execute(["/bin/bash", "-c", cmd]).stdout.replace("\n", "")
+    return repo_ctx.execute(["/bin/bash", "-c", cmd]).stdout.strip("\n")
 
 def _find_linker(repo_ctx):
     ld = _execute_bash(repo_ctx, "which ld")
@@ -93,7 +93,7 @@
         path = _execute_bash(repo_ctx, cmd)
         if path:
             return (archive_name, path)
-    return ("", "")
+    return (None, None)
 
 def _find_header_path(repo_ctx, lib_name, header_name, includes):
     override_paths = _get_list_from_env_var(
@@ -107,33 +107,25 @@
         lib_name,
     )
 
-    # See https://gcc.gnu.org/onlinedocs/gcc/Directory-Options.html
-    override_include_flags = _make_flags(override_paths, "-I")
-    standard_include_flags = _make_flags(includes, "-isystem")
-    additional_include_flags = _make_flags(additional_paths, "-idirafter")
-
     compiler = _find_compiler(repo_ctx)
-
-    # Taken from https://stackoverflow.com/a/63052918/922404
     cmd = """
-          f=\"{}\"; \\
-          echo | \\
-          {} -E {} {} {} -Wp,-v - 2>&1 | \\
-          sed '\\~^ /~!d; s/ //' | \\
-          while IFS= read -r path; \\
-              do if [[ -e \"$path/$f\" ]]; \\
-                  then echo \"$path/$f\";  \\
-                  break; \\
-              fi; \\
-          done
-          """.format(
-        header_name,
-        compiler,
-        override_include_flags,
-        standard_include_flags,
-        additional_include_flags,
-    )
-    return _execute_bash(repo_ctx, cmd)
+          print | \\
+          {} -Wp,-v -x c++ - -fsyntax-only 2>&1 | \\
+          sed -n -e '/^\s\+/p' | \\
+          sed -e 's/^[ \t]*//'
+          """.format(compiler)
+    system_includes = _execute_bash(repo_ctx, cmd).split("\n")
+    all_includes = (override_paths + includes +
+        system_includes + additional_paths)
+
+    for directory in all_includes:
+        cmd = """
+              test -f "{dir}/{hdr}" && echo "{dir}/{hdr}"
+              """.format(dir = directory, hdr = header_name)
+        result = _execute_bash(repo_ctx, cmd)
+        if result:
+            return result
+    return None
 
 def _system_library_impl(repo_ctx):
     repo_name = repo_ctx.attr.name
diff --git a/tests/system_library/system_library_test.sh b/tests/system_library/system_library_test.sh
index 018bae7..b8d52b3 100755
--- a/tests/system_library/system_library_test.sh
+++ b/tests/system_library/system_library_test.sh
@@ -23,8 +23,8 @@
 source "$(rlocation rules_cc/tests/system_library/unittest.bash)" \
   || { echo "Could not rules_cc/source tests/system_library/unittest.bash" >&2; exit 1; }
 
-#### TESTS #############################################################
-function test_system_library() {
+
+function setup_system_library() {
   mkdir -p systemlib
 
   cat << EOF > systemlib/foo.cc
@@ -95,6 +95,12 @@
     deps = ["@foo_hardcoded_path"],
     linkstatic = True
 )
+
+cc_binary(
+    name = "fake_rbe",
+    srcs = ["test.cc"],
+    deps = ["@foo_hardcoded_path"]
+)
 EOF
 
   cat << EOF > test.cc
@@ -104,8 +110,13 @@
   return 42 - bar();
 }
 EOF
+}
+#### TESTS #############################################################
 
-  # Make sure it fails with a correct message when no library is found
+# Make sure it fails with a correct message when no library is found
+function test_system_library_not_found() {
+  setup_system_library
+
   bazel run //:test \
   --experimental_starlark_cc_import \
   --experimental_repo_remote_exec \
@@ -119,8 +130,11 @@
   &> $TEST_log \
   || true
   expect_log "Library foo could not be found"
+  }
 
-  # Test override paths
+function test_override_paths() {
+  setup_system_library
+
   bazel run //:test \
   --experimental_starlark_cc_import \
   --experimental_repo_remote_exec \
@@ -134,8 +148,11 @@
   --action_env=BAZEL_LIB_OVERRIDE_PATHS=foo="${PWD}"/systemlib \
   --action_env=BAZEL_INCLUDE_OVERRIDE_PATHS=foo="${PWD}"/systemlib \
   || fail "Expected test_static to run successfully"
+}
 
-  # Test additional paths
+function test_additional_paths() {
+  setup_system_library
+
   bazel run //:test \
   --experimental_starlark_cc_import \
   --experimental_repo_remote_exec \
@@ -149,8 +166,11 @@
   --action_env=BAZEL_LIB_ADDITIONAL_PATHS=foo="${PWD}"/systemlib \
   --action_env=BAZEL_INCLUDE_ADDITIONAL_PATHS=foo="${PWD}"/systemlib \
   || fail "Expected test_static to run successfully"
+}
 
-  # Test hardcoded paths
+function test_hardcoded_paths() {
+  setup_system_library
+
   bazel run //:test_hardcoded_path \
   --experimental_starlark_cc_import \
   --experimental_repo_remote_exec \