diff --git a/java/com/google/gerrit/plugins/codeowners/testing/RequiredApprovalSubject.java b/java/com/google/gerrit/plugins/codeowners/testing/RequiredApprovalSubject.java
index 9e17d9a..15a25f3 100644
--- a/java/com/google/gerrit/plugins/codeowners/testing/RequiredApprovalSubject.java
+++ b/java/com/google/gerrit/plugins/codeowners/testing/RequiredApprovalSubject.java
@@ -17,7 +17,7 @@
 import static com.google.common.truth.Truth.assertAbout;
 
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSortedSet;
 import com.google.common.truth.FailureMetadata;
 import com.google.common.truth.IntegerSubject;
 import com.google.common.truth.StringSubject;
@@ -49,14 +49,14 @@
   }
 
   /**
-   * Starts a fluent chain to do assertions on a set of {@link RequiredApproval}s.
+   * Starts a fluent chain to do assertions on a sorted set of {@link RequiredApproval}s.
    *
-   * @param requiredApprovals set of required approvals on which assertions should be done
+   * @param requiredApprovals sorted set of required approvals on which assertions should be done
    * @return the created {@link ListSubject}
    */
   public static ListSubject<RequiredApprovalSubject, RequiredApproval> assertThat(
-      ImmutableSet<RequiredApproval> requiredApprovals) {
-    return ListSubject.assertThat(requiredApprovals.asList(), requiredApprovals());
+      ImmutableSortedSet<RequiredApproval> requiredApprovals) {
+    return assertThat(requiredApprovals.asList());
   }
 
   /**
diff --git a/javatests/com/google/gerrit/plugins/codeowners/acceptance/api/CodeOwnersPluginConfigValidatorIT.java b/javatests/com/google/gerrit/plugins/codeowners/acceptance/api/CodeOwnersPluginConfigValidatorIT.java
index aa269c7..3b1258e 100644
--- a/javatests/com/google/gerrit/plugins/codeowners/acceptance/api/CodeOwnersPluginConfigValidatorIT.java
+++ b/javatests/com/google/gerrit/plugins/codeowners/acceptance/api/CodeOwnersPluginConfigValidatorIT.java
@@ -23,7 +23,7 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSortedSet;
 import com.google.gerrit.acceptance.GitUtil;
 import com.google.gerrit.acceptance.PushOneCommit;
 import com.google.gerrit.acceptance.config.GerritConfig;
@@ -326,7 +326,7 @@
 
     PushResult r = pushRefsMetaConfig();
     assertThat(r.getRemoteUpdate(RefNames.REFS_CONFIG).getStatus()).isEqualTo(Status.OK);
-    ImmutableSet<RequiredApproval> overrideApprovals =
+    ImmutableSortedSet<RequiredApproval> overrideApprovals =
         codeOwnersPluginConfiguration.getProjectConfig(project).getOverrideApprovals();
     assertThat(overrideApprovals).hasSize(1);
     assertThat(overrideApprovals).element(0).hasLabelNameThat().isEqualTo("Code-Review");
@@ -423,7 +423,7 @@
 
     PushResult r = pushRefsMetaConfig();
     assertThat(r.getRemoteUpdate(RefNames.REFS_CONFIG).getStatus()).isEqualTo(Status.OK);
-    ImmutableSet<RequiredApproval> overrideApprovals =
+    ImmutableSortedSet<RequiredApproval> overrideApprovals =
         codeOwnersPluginConfiguration.getProjectConfig(project).getOverrideApprovals();
     assertThat(overrideApprovals).hasSize(1);
     assertThat(overrideApprovals).element(0).hasLabelNameThat().isEqualTo("Owners-Override");
diff --git a/javatests/com/google/gerrit/plugins/codeowners/backend/config/CodeOwnersPluginConfigSnapshotTest.java b/javatests/com/google/gerrit/plugins/codeowners/backend/config/CodeOwnersPluginConfigSnapshotTest.java
index 63679e0..4b65a20 100644
--- a/javatests/com/google/gerrit/plugins/codeowners/backend/config/CodeOwnersPluginConfigSnapshotTest.java
+++ b/javatests/com/google/gerrit/plugins/codeowners/backend/config/CodeOwnersPluginConfigSnapshotTest.java
@@ -1217,7 +1217,7 @@
   @GerritConfig(name = "plugin.code-owners.overrideApproval", value = "Owners-Override+1")
   public void getConfiguredOverrideApproval() throws Exception {
     createOwnersOverrideLabel();
-    ImmutableSet<RequiredApproval> requiredApprovals = cfgSnapshot().getOverrideApprovals();
+    ImmutableSortedSet<RequiredApproval> requiredApprovals = cfgSnapshot().getOverrideApprovals();
     assertThat(requiredApprovals).hasSize(1);
     assertThat(requiredApprovals).element(0).hasLabelNameThat().isEqualTo("Owners-Override");
     assertThat(requiredApprovals).element(0).hasValueThat().isEqualTo(1);
@@ -1247,7 +1247,7 @@
   public void getOverrideApprovalConfiguredOnProjectLevel() throws Exception {
     createOwnersOverrideLabel();
     configureOverrideApproval(project, "Owners-Override+1");
-    ImmutableSet<RequiredApproval> requiredApprovals = cfgSnapshot().getOverrideApprovals();
+    ImmutableSortedSet<RequiredApproval> requiredApprovals = cfgSnapshot().getOverrideApprovals();
     assertThat(requiredApprovals).hasSize(1);
     assertThat(requiredApprovals).element(0).hasLabelNameThat().isEqualTo("Owners-Override");
     assertThat(requiredApprovals).element(0).hasValueThat().isEqualTo(1);
@@ -1296,7 +1296,7 @@
     createOwnersOverrideLabel();
 
     configureOverrideApproval(project, "Owners-Override+1");
-    ImmutableSet<RequiredApproval> requiredApprovals = cfgSnapshot().getOverrideApprovals();
+    ImmutableSortedSet<RequiredApproval> requiredApprovals = cfgSnapshot().getOverrideApprovals();
     assertThat(requiredApprovals).hasSize(1);
     assertThat(requiredApprovals).element(0).hasLabelNameThat().isEqualTo("Owners-Override");
     assertThat(requiredApprovals).element(0).hasValueThat().isEqualTo(1);
@@ -1307,7 +1307,7 @@
     createOwnersOverrideLabel();
 
     configureOverrideApproval(allProjects, "Owners-Override+1");
-    ImmutableSet<RequiredApproval> requiredApprovals = cfgSnapshot().getOverrideApprovals();
+    ImmutableSortedSet<RequiredApproval> requiredApprovals = cfgSnapshot().getOverrideApprovals();
     assertThat(requiredApprovals).hasSize(1);
     assertThat(requiredApprovals).element(0).hasLabelNameThat().isEqualTo("Owners-Override");
     assertThat(requiredApprovals).element(0).hasValueThat().isEqualTo(1);
@@ -1337,7 +1337,7 @@
     createOwnersOverrideLabel();
 
     configureOverrideApproval(allProjects, "Owners-Override+1");
-    ImmutableSet<RequiredApproval> requiredApprovals = cfgSnapshot().getOverrideApprovals();
+    ImmutableSortedSet<RequiredApproval> requiredApprovals = cfgSnapshot().getOverrideApprovals();
     assertThat(requiredApprovals).hasSize(1);
     assertThat(requiredApprovals).element(0).hasLabelNameThat().isEqualTo("Owners-Override");
     assertThat(requiredApprovals).element(0).hasValueThat().isEqualTo(1);
@@ -1366,7 +1366,7 @@
 
     configureOverrideApproval(allProjects, "Owners-Override+1");
     configureOverrideApproval(project, "Owners-Override+1");
-    ImmutableSet<RequiredApproval> requiredApprovals = cfgSnapshot().getOverrideApprovals();
+    ImmutableSortedSet<RequiredApproval> requiredApprovals = cfgSnapshot().getOverrideApprovals();
     assertThat(requiredApprovals).hasSize(1);
     assertThat(requiredApprovals).element(0).hasLabelNameThat().isEqualTo("Owners-Override");
     assertThat(requiredApprovals).element(0).hasValueThat().isEqualTo(1);
@@ -1385,7 +1385,7 @@
     // if the same label is configured multiple times as override approval, only the definition with
     // the lowest value is returned (since all higher values are implicitly considered as overrides
     // as well)
-    ImmutableSet<RequiredApproval> requiredApprovals = cfgSnapshot().getOverrideApprovals();
+    ImmutableSortedSet<RequiredApproval> requiredApprovals = cfgSnapshot().getOverrideApprovals();
     assertThat(requiredApprovals).hasSize(1);
     assertThat(requiredApprovals).element(0).hasLabelNameThat().isEqualTo("Owners-Override");
     assertThat(requiredApprovals).element(0).hasValueThat().isEqualTo(1);
@@ -1431,7 +1431,7 @@
         ImmutableList.of("Code-Review+2", "Code-Review+1", "Code-Review+2"));
 
     // If multiple values are set for a key, the last value wins.
-    ImmutableSet<RequiredApproval> requiredApprovals = cfgSnapshot().getOverrideApprovals();
+    ImmutableSortedSet<RequiredApproval> requiredApprovals = cfgSnapshot().getOverrideApprovals();
     assertThat(requiredApprovals).hasSize(1);
     assertThat(requiredApprovals).element(0).hasLabelNameThat().isEqualTo("Code-Review");
     assertThat(requiredApprovals).element(0).hasValueThat().isEqualTo(1);