diff --git a/services/core/java/com/android/server/integrity/IntegrityFileManager.java b/services/core/java/com/android/server/integrity/IntegrityFileManager.java
index 30cafaa..46daf12 100644
--- a/services/core/java/com/android/server/integrity/IntegrityFileManager.java
+++ b/services/core/java/com/android/server/integrity/IntegrityFileManager.java
@@ -44,12 +44,9 @@
 public class IntegrityFileManager {
     private static final String TAG = "IntegrityFileManager";
 
-    // TODO: this is a prototype implementation of this class. Thus no tests are included.
-    //  Implementing rule indexing will likely overhaul this class and more tests should be included
-    //  then.
-
     private static final String METADATA_FILE = "metadata";
     private static final String RULES_FILE = "rules";
+    private static final String INDEXING_FILE = "indexing";
     private static final Object RULES_LOCK = new Object();
 
     private static IntegrityFileManager sInstance = null;
@@ -125,9 +122,12 @@
             // We don't consider this fatal so we continue execution.
         }
 
-        try (FileOutputStream fileOutputStream =
-                new FileOutputStream(new File(mStagingDir, RULES_FILE))) {
-            mRuleSerializer.serialize(rules, Optional.empty(), fileOutputStream);
+        try (FileOutputStream ruleFileOutputStream =
+                     new FileOutputStream(new File(mStagingDir, RULES_FILE));
+             FileOutputStream indexingFileOutputStream =
+                     new FileOutputStream(new File(mStagingDir, INDEXING_FILE))) {
+            mRuleSerializer.serialize(
+                    rules, Optional.empty(), ruleFileOutputStream, indexingFileOutputStream);
         }
 
         switchStagingRulesDir();
@@ -143,7 +143,7 @@
         // TODO: select rules by index
         synchronized (RULES_LOCK) {
             try (FileInputStream inputStream =
-                    new FileInputStream(new File(mRulesDir, RULES_FILE))) {
+                         new FileInputStream(new File(mRulesDir, RULES_FILE))) {
                 List<Rule> rules = mRuleParser.parse(inputStream);
                 return rules;
             }
diff --git a/services/core/java/com/android/server/integrity/serializer/ByteTrackedOutputStream.java b/services/core/java/com/android/server/integrity/serializer/ByteTrackedOutputStream.java
index c8d318f..62815a9 100644
--- a/services/core/java/com/android/server/integrity/serializer/ByteTrackedOutputStream.java
+++ b/services/core/java/com/android/server/integrity/serializer/ByteTrackedOutputStream.java
@@ -27,7 +27,7 @@
  */
 public class ByteTrackedOutputStream {
 
-    private static long sWrittenBytesCount;
+    private static int sWrittenBytesCount;
     private static OutputStream sOutputStream;
 
     public ByteTrackedOutputStream(OutputStream outputStream) {
@@ -47,7 +47,7 @@
     /**
      * Returns the total number of bytes written into the output stream at the requested time.
      */
-    public long getWrittenBytesCount() {
+    public int getWrittenBytesCount() {
         return sWrittenBytesCount;
     }
 }
diff --git a/services/core/java/com/android/server/integrity/serializer/RuleBinarySerializer.java b/services/core/java/com/android/server/integrity/serializer/RuleBinarySerializer.java
index 22af085..35e673f 100644
--- a/services/core/java/com/android/server/integrity/serializer/RuleBinarySerializer.java
+++ b/services/core/java/com/android/server/integrity/serializer/RuleBinarySerializer.java
@@ -52,20 +52,21 @@
 /** A helper class to serialize rules from the {@link Rule} model to Binary representation. */
 public class RuleBinarySerializer implements RuleSerializer {
 
-    // The parsing time seems acceptable for 100 rules based on the tests in go/ic-rule-file-format.
-    private static final int INDEXING_BLOCK_SIZE = 100;
+    // The parsing time seems acceptable for this block size based on the tests in
+    // go/ic-rule-file-format.
+    public static final int INDEXING_BLOCK_SIZE = 100;
 
-    private static final String START_INDEXING_KEY = "START_KEY";
-    private static final String END_INDEXING_KEY = "END_KEY";
+    public static final String START_INDEXING_KEY = "START_KEY";
+    public static final String END_INDEXING_KEY = "END_KEY";
 
     // Get the byte representation for a list of rules.
     @Override
     public byte[] serialize(List<Rule> rules, Optional<Integer> formatVersion)
             throws RuleSerializeException {
         try {
-            ByteArrayOutputStream byteArrayOutputStream = new ByteArrayOutputStream();
-            serialize(rules, formatVersion, byteArrayOutputStream);
-            return byteArrayOutputStream.toByteArray();
+            ByteArrayOutputStream rulesOutputStream = new ByteArrayOutputStream();
+            serialize(rules, formatVersion, rulesOutputStream, new ByteArrayOutputStream());
+            return rulesOutputStream.toByteArray();
         } catch (Exception e) {
             throw new RuleSerializeException(e.getMessage(), e);
         }
@@ -74,27 +75,38 @@
     // Get the byte representation for a list of rules, and write them to an output stream.
     @Override
     public void serialize(
-            List<Rule> rules, Optional<Integer> formatVersion, OutputStream originalOutputStream)
+            List<Rule> rules,
+            Optional<Integer> formatVersion,
+            OutputStream rulesFileOutputStream,
+            OutputStream indexingFileOutputStream)
             throws RuleSerializeException {
         try {
             // Determine the indexing groups and the order of the rules within each indexed group.
             Map<Integer, TreeMap<String, List<Rule>>> indexedRules =
                     RuleIndexingDetailsIdentifier.splitRulesIntoIndexBuckets(rules);
 
-            ByteTrackedOutputStream outputStream =
-                    new ByteTrackedOutputStream(originalOutputStream);
+            ByteTrackedOutputStream ruleFileByteTrackedOutputStream =
+                    new ByteTrackedOutputStream(rulesFileOutputStream);
 
-            serializeRuleFileMetadata(formatVersion, outputStream);
+            serializeRuleFileMetadata(formatVersion, ruleFileByteTrackedOutputStream);
 
-            Map<String, Long> packageNameIndexes =
-                    serializeRuleList(indexedRules.get(PACKAGE_NAME_INDEXED), outputStream);
-            Map<String, Long> appCertificateIndexes =
-                    serializeRuleList(indexedRules.get(APP_CERTIFICATE_INDEXED), outputStream);
-            Map<String, Long> unindexedRulesIndex =
-                    serializeRuleList(indexedRules.get(NOT_INDEXED), outputStream);
+            Map<String, Integer> packageNameIndexes =
+                    serializeRuleList(indexedRules.get(PACKAGE_NAME_INDEXED),
+                            ruleFileByteTrackedOutputStream);
+            indexingFileOutputStream.write(
+                    serializeIndexes(packageNameIndexes, /* isIndexed= */true));
 
-            // TODO(b/145493956): Write these indexes into a index file provided by integrity file
-            //  manager.
+            Map<String, Integer> appCertificateIndexes =
+                    serializeRuleList(indexedRules.get(APP_CERTIFICATE_INDEXED),
+                            ruleFileByteTrackedOutputStream);
+            indexingFileOutputStream.write(
+                    serializeIndexes(appCertificateIndexes, /* isIndexed= */true));
+
+            Map<String, Integer> unindexedRulesIndexes =
+                    serializeRuleList(indexedRules.get(NOT_INDEXED),
+                            ruleFileByteTrackedOutputStream);
+            indexingFileOutputStream.write(
+                    serializeIndexes(unindexedRulesIndexes, /* isIndexed= */false));
         } catch (Exception e) {
             throw new RuleSerializeException(e.getMessage(), e);
         }
@@ -109,15 +121,15 @@
         outputStream.write(bitOutputStream.toByteArray());
     }
 
-    private Map<String, Long> serializeRuleList(TreeMap<String, List<Rule>> rulesMap,
+    private Map<String, Integer> serializeRuleList(TreeMap<String, List<Rule>> rulesMap,
             ByteTrackedOutputStream outputStream)
             throws IOException {
         Preconditions.checkArgument(rulesMap != null,
                 "serializeRuleList should never be called with null rule list.");
 
         BitOutputStream bitOutputStream = new BitOutputStream();
-        Map<String, Long> indexMapping = new TreeMap();
-        long indexTracker = 0;
+        Map<String, Integer> indexMapping = new TreeMap();
+        int indexTracker = 0;
 
         indexMapping.put(START_INDEXING_KEY, outputStream.getWrittenBytesCount());
         for (Map.Entry<String, List<Rule>> entry : rulesMap.entrySet()) {
@@ -210,6 +222,33 @@
         }
     }
 
+    private byte[] serializeIndexes(Map<String, Integer> indexes, boolean isIndexed) {
+        BitOutputStream bitOutputStream = new BitOutputStream();
+
+        // Output the starting location of this indexing group.
+        serializeStringValue(START_INDEXING_KEY, /* isHashedValue= */false,
+                bitOutputStream);
+        serializeIntValue(indexes.get(START_INDEXING_KEY), bitOutputStream);
+
+        // If the group is indexed, output the locations of the indexes.
+        if (isIndexed) {
+            for (Map.Entry<String, Integer> entry : indexes.entrySet()) {
+                if (!entry.getKey().equals(START_INDEXING_KEY)
+                        && !entry.getKey().equals(END_INDEXING_KEY)) {
+                    serializeStringValue(entry.getKey(), /* isHashedValue= */false,
+                            bitOutputStream);
+                    serializeIntValue(entry.getValue(), bitOutputStream);
+                }
+            }
+        }
+
+        // Output the end location of this indexing group.
+        serializeStringValue(END_INDEXING_KEY, /*isHashedValue= */ false, bitOutputStream);
+        serializeIntValue(indexes.get(END_INDEXING_KEY), bitOutputStream);
+
+        return bitOutputStream.toByteArray();
+    }
+
     private void serializeStringValue(
             String value, boolean isHashedValue, BitOutputStream bitOutputStream) {
         if (value == null) {
diff --git a/services/core/java/com/android/server/integrity/serializer/RuleSerializer.java b/services/core/java/com/android/server/integrity/serializer/RuleSerializer.java
index 4fcff65..2941856 100644
--- a/services/core/java/com/android/server/integrity/serializer/RuleSerializer.java
+++ b/services/core/java/com/android/server/integrity/serializer/RuleSerializer.java
@@ -26,10 +26,14 @@
 public interface RuleSerializer {
 
     /** Serialize rules to an output stream */
-    void serialize(List<Rule> rules, Optional<Integer> formatVersion, OutputStream outputStream)
+    void serialize(
+            List<Rule> rules,
+            Optional<Integer> formatVersion,
+            OutputStream ruleFileOutputStream,
+            OutputStream indexingFileOutputStream)
             throws RuleSerializeException;
 
     /** Serialize rules to a ByteArray. */
-    byte[] serialize(List<Rule> rule, Optional<Integer> formatVersion)
+    byte[] serialize(List<Rule> rules, Optional<Integer> formatVersion)
             throws RuleSerializeException;
 }
diff --git a/services/core/java/com/android/server/integrity/serializer/RuleXmlSerializer.java b/services/core/java/com/android/server/integrity/serializer/RuleXmlSerializer.java
index 4c04dbc..4194432 100644
--- a/services/core/java/com/android/server/integrity/serializer/RuleXmlSerializer.java
+++ b/services/core/java/com/android/server/integrity/serializer/RuleXmlSerializer.java
@@ -56,12 +56,17 @@
 
     @Override
     public void serialize(
-            List<Rule> rules, Optional<Integer> formatVersion, OutputStream outputStream)
+            List<Rule> rules,
+            Optional<Integer> formatVersion,
+            OutputStream outputStream,
+            OutputStream indexingOutputStream)
             throws RuleSerializeException {
         try {
             XmlSerializer xmlSerializer = Xml.newSerializer();
             xmlSerializer.setOutput(outputStream, StandardCharsets.UTF_8.name());
             serializeRules(rules, xmlSerializer);
+
+            // TODO(b/145493956): Implement the indexing logic.
         } catch (Exception e) {
             throw new RuleSerializeException(e.getMessage(), e);
         }
diff --git a/services/tests/servicestests/src/com/android/server/integrity/serializer/RuleBinarySerializerTest.java b/services/tests/servicestests/src/com/android/server/integrity/serializer/RuleBinarySerializerTest.java
index 981db6a..97aa310 100644
--- a/services/tests/servicestests/src/com/android/server/integrity/serializer/RuleBinarySerializerTest.java
+++ b/services/tests/servicestests/src/com/android/server/integrity/serializer/RuleBinarySerializerTest.java
@@ -27,6 +27,9 @@
 import static com.android.server.integrity.model.ComponentBitSize.OPERATOR_BITS;
 import static com.android.server.integrity.model.ComponentBitSize.SEPARATOR_BITS;
 import static com.android.server.integrity.model.ComponentBitSize.VALUE_SIZE_BITS;
+import static com.android.server.integrity.serializer.RuleBinarySerializer.END_INDEXING_KEY;
+import static com.android.server.integrity.serializer.RuleBinarySerializer.INDEXING_BLOCK_SIZE;
+import static com.android.server.integrity.serializer.RuleBinarySerializer.START_INDEXING_KEY;
 import static com.android.server.integrity.utils.TestUtils.getBits;
 import static com.android.server.integrity.utils.TestUtils.getBytes;
 import static com.android.server.integrity.utils.TestUtils.getValueBits;
@@ -94,6 +97,15 @@
     private static final byte[] DEFAULT_FORMAT_VERSION_BYTES =
             getBytes(getBits(DEFAULT_FORMAT_VERSION, FORMAT_VERSION_BITS));
 
+    private static final String SERIALIZED_START_INDEXING_KEY =
+            IS_NOT_HASHED
+                    + getBits(START_INDEXING_KEY.length(), VALUE_SIZE_BITS)
+                    + getValueBits(START_INDEXING_KEY);
+    private static final String SERIALIZED_END_INDEXING_KEY =
+            IS_NOT_HASHED
+                    + getBits(END_INDEXING_KEY.length(), VALUE_SIZE_BITS)
+                    + getValueBits(END_INDEXING_KEY);
+
     @Test
     public void testBinaryString_serializeNullRules() {
         RuleSerializer binarySerializer = new RuleBinarySerializer();
@@ -107,15 +119,34 @@
 
     @Test
     public void testBinaryString_emptyRules() throws Exception {
-        ByteArrayOutputStream expectedArrayOutputStream = new ByteArrayOutputStream();
-        expectedArrayOutputStream.write(DEFAULT_FORMAT_VERSION_BYTES);
-
-        ByteArrayOutputStream outputStream = new ByteArrayOutputStream();
+        ByteArrayOutputStream ruleOutputStream = new ByteArrayOutputStream();
+        ByteArrayOutputStream indexingOutputStream = new ByteArrayOutputStream();
         RuleSerializer binarySerializer = new RuleBinarySerializer();
-        binarySerializer.serialize(
-                Collections.emptyList(), /* formatVersion= */ Optional.empty(), outputStream);
 
-        assertThat(outputStream.toByteArray()).isEqualTo(expectedArrayOutputStream.toByteArray());
+        binarySerializer.serialize(
+                Collections.emptyList(),
+                /* formatVersion= */ Optional.empty(),
+                ruleOutputStream,
+                indexingOutputStream);
+
+        ByteArrayOutputStream expectedRuleOutputStream = new ByteArrayOutputStream();
+        expectedRuleOutputStream.write(DEFAULT_FORMAT_VERSION_BYTES);
+        assertThat(ruleOutputStream.toByteArray())
+                .isEqualTo(expectedRuleOutputStream.toByteArray());
+
+        ByteArrayOutputStream expectedIndexingOutputStream = new ByteArrayOutputStream();
+        byte[] expectedIndexingBytes =
+                getBytes(
+                        SERIALIZED_START_INDEXING_KEY
+                                + getBits(DEFAULT_FORMAT_VERSION_BYTES.length, /* numOfBits= */ 32)
+                                + SERIALIZED_END_INDEXING_KEY
+                                + getBits(DEFAULT_FORMAT_VERSION_BYTES.length, /* numOfBits= */
+                                32));
+        expectedIndexingOutputStream.write(expectedIndexingBytes);
+        expectedIndexingOutputStream.write(expectedIndexingBytes);
+        expectedIndexingOutputStream.write(expectedIndexingBytes);
+        assertThat(indexingOutputStream.toByteArray())
+                .isEqualTo(expectedIndexingOutputStream.toByteArray());
     }
 
     @Test
@@ -131,8 +162,16 @@
                                                 packageName,
                                                 /* isHashedValue= */ false))),
                         Rule.DENY);
+
+        ByteArrayOutputStream ruleOutputStream = new ByteArrayOutputStream();
+        ByteArrayOutputStream indexingOutputStream = new ByteArrayOutputStream();
         RuleSerializer binarySerializer = new RuleBinarySerializer();
-        ByteArrayOutputStream outputStream = new ByteArrayOutputStream();
+        binarySerializer.serialize(
+                Collections.singletonList(rule),
+                /* formatVersion= */ Optional.empty(),
+                ruleOutputStream,
+                indexingOutputStream);
+
         String expectedBits =
                 START_BIT
                         + COMPOUND_FORMULA_START_BITS
@@ -146,18 +185,29 @@
                         + COMPOUND_FORMULA_END_BITS
                         + DENY
                         + END_BIT;
-        ByteArrayOutputStream byteArrayOutputStream = new ByteArrayOutputStream();
-        byteArrayOutputStream.write(DEFAULT_FORMAT_VERSION_BYTES);
-        byteArrayOutputStream.write(getBytes(expectedBits));
-        byte[] expectedRules = byteArrayOutputStream.toByteArray();
+        ByteArrayOutputStream expectedRuleOutputStream = new ByteArrayOutputStream();
+        expectedRuleOutputStream.write(DEFAULT_FORMAT_VERSION_BYTES);
+        expectedRuleOutputStream.write(getBytes(expectedBits));
+        assertThat(ruleOutputStream.toByteArray())
+                .isEqualTo(expectedRuleOutputStream.toByteArray());
 
-        binarySerializer.serialize(
-                Collections.singletonList(rule),
-                /* formatVersion= */ Optional.empty(),
-                outputStream);
-
-        byte[] actualRules = outputStream.toByteArray();
-        assertThat(actualRules).isEqualTo(expectedRules);
+        ByteArrayOutputStream expectedIndexingOutputStream = new ByteArrayOutputStream();
+        String expectedIndexingBitsForIndexed =
+                SERIALIZED_START_INDEXING_KEY
+                        + getBits(DEFAULT_FORMAT_VERSION_BYTES.length, /* numOfBits= */ 32)
+                        + SERIALIZED_END_INDEXING_KEY
+                        + getBits(DEFAULT_FORMAT_VERSION_BYTES.length, /* numOfBits= */ 32);
+        expectedIndexingOutputStream.write(getBytes(expectedIndexingBitsForIndexed));
+        expectedIndexingOutputStream.write(getBytes(expectedIndexingBitsForIndexed));
+        String expectedIndexingBitsForUnindexed =
+                SERIALIZED_START_INDEXING_KEY
+                        + getBits(DEFAULT_FORMAT_VERSION_BYTES.length, /* numOfBits= */ 32)
+                        + SERIALIZED_END_INDEXING_KEY
+                        + getBits(DEFAULT_FORMAT_VERSION_BYTES.length + getBytes(
+                        expectedBits).length, /* numOfBits= */ 32);
+        expectedIndexingOutputStream.write(getBytes(expectedIndexingBitsForUnindexed));
+        assertThat(indexingOutputStream.toByteArray())
+                .isEqualTo(expectedIndexingOutputStream.toByteArray());
     }
 
     @Test
@@ -453,91 +503,113 @@
     }
 
     @Test
-    public void testBinaryString_serializeComplexCompoundFormula_indexingOrderValid()
-            throws Exception {
-        String packageNameA = "aaa";
-        String packageNameB = "bbb";
-        String packageNameC = "ccc";
-        String appCert1 = "cert1";
-        String appCert2 = "cert2";
-        String appCert3 = "cert3";
-        Rule installerRule =
-                new Rule(
-                        new CompoundFormula(
-                                CompoundFormula.AND,
-                                Arrays.asList(
-                                        new AtomicFormula.StringAtomicFormula(
-                                                AtomicFormula.INSTALLER_NAME,
-                                                SAMPLE_INSTALLER_NAME,
-                                                /* isHashedValue= */ false),
-                                        new AtomicFormula.StringAtomicFormula(
-                                                AtomicFormula.INSTALLER_CERTIFICATE,
-                                                SAMPLE_INSTALLER_CERT,
-                                                /* isHashedValue= */ false))),
-                        Rule.DENY);
+    public void testBinaryString_verifyManyRulesAreIndexedCorrectly() throws Exception {
+        int ruleCount = 225;
+        String packagePrefix = "package.name.";
+        String appCertificatePrefix = "app.cert.";
+        String installerNamePrefix = "installer.";
 
-        RuleSerializer binarySerializer = new RuleBinarySerializer();
+        // Create the rule set with 225 package name based rules, 225 app certificate indexed rules,
+        // and 225 non-indexed rules..
         List<Rule> ruleList = new ArrayList();
-        ruleList.add(getRuleWithAppCertificateAndSampleInstallerName(appCert3));
-        ruleList.add(getRuleWithAppCertificateAndSampleInstallerName(appCert2));
-        ruleList.add(getRuleWithAppCertificateAndSampleInstallerName(appCert1));
-        ruleList.add(getRuleWithPackageNameAndSampleInstallerName(packageNameB));
-        ruleList.add(getRuleWithPackageNameAndSampleInstallerName(packageNameC));
-        ruleList.add(getRuleWithPackageNameAndSampleInstallerName(packageNameA));
-        ruleList.add(installerRule);
-        byte[] actualRules =
-                binarySerializer.serialize(ruleList, /* formatVersion= */ Optional.empty());
+        for (int count = 0; count < ruleCount; count++) {
+            ruleList.add(getRuleWithPackageNameAndSampleInstallerName(
+                    String.format("%s%04d", packagePrefix, count)));
+        }
+        for (int count = 0; count < ruleCount; count++) {
+            ruleList.add(getRuleWithAppCertificateAndSampleInstallerName(
+                    String.format("%s%04d", appCertificatePrefix, count)));
+        }
+        for (int count = 0; count < ruleCount; count++) {
+            ruleList.add(getNonIndexedRuleWithInstallerName(
+                    String.format("%s%04d", installerNamePrefix, count)));
+        }
 
-        // Note that ordering is important here and the test verifies that the rules are written
-        // in this sorted order.
-        ByteArrayOutputStream expectedArrayOutputStream = new ByteArrayOutputStream();
-        expectedArrayOutputStream.write(DEFAULT_FORMAT_VERSION_BYTES);
-        expectedArrayOutputStream.write(
-                getBytes(
-                        getSerializedCompoundRuleWithPackageNameAndSampleInstallerName(
-                                packageNameA)));
-        expectedArrayOutputStream.write(
-                getBytes(
-                        getSerializedCompoundRuleWithPackageNameAndSampleInstallerName(
-                                packageNameB)));
-        expectedArrayOutputStream.write(
-                getBytes(
-                        getSerializedCompoundRuleWithPackageNameAndSampleInstallerName(
-                                packageNameC)));
-        expectedArrayOutputStream.write(
-                getBytes(
-                        getSerializedCompoundRuleWithCertificateNameAndSampleInstallerName(
-                                appCert1)));
-        expectedArrayOutputStream.write(
-                getBytes(
-                        getSerializedCompoundRuleWithCertificateNameAndSampleInstallerName(
-                                appCert2)));
-        expectedArrayOutputStream.write(
-                getBytes(
-                        getSerializedCompoundRuleWithCertificateNameAndSampleInstallerName(
-                                appCert3)));
-        String expectedBitsForInstallerRule =
-                START_BIT
-                        + COMPOUND_FORMULA_START_BITS
-                        + AND
-                        + ATOMIC_FORMULA_START_BITS
-                        + INSTALLER_NAME
-                        + EQ
-                        + IS_NOT_HASHED
-                        + getBits(SAMPLE_INSTALLER_NAME.length(), VALUE_SIZE_BITS)
-                        + getValueBits(SAMPLE_INSTALLER_NAME)
-                        + ATOMIC_FORMULA_START_BITS
-                        + INSTALLER_CERTIFICATE
-                        + EQ
-                        + IS_NOT_HASHED
-                        + getBits(SAMPLE_INSTALLER_CERT.length(), VALUE_SIZE_BITS)
-                        + getValueBits(SAMPLE_INSTALLER_CERT)
-                        + COMPOUND_FORMULA_END_BITS
-                        + DENY
-                        + END_BIT;
-        expectedArrayOutputStream.write(getBytes(expectedBitsForInstallerRule));
+        // Serialize the rules.
+        ByteArrayOutputStream ruleOutputStream = new ByteArrayOutputStream();
+        ByteArrayOutputStream indexingOutputStream = new ByteArrayOutputStream();
+        RuleSerializer binarySerializer = new RuleBinarySerializer();
+        binarySerializer.serialize(
+                ruleList,
+                /* formatVersion= */ Optional.empty(),
+                ruleOutputStream,
+                indexingOutputStream);
 
-        assertThat(actualRules).isEqualTo(expectedArrayOutputStream.toByteArray());
+        // Verify the rules file and index files.
+        ByteArrayOutputStream expectedOrderedRuleOutputStream = new ByteArrayOutputStream();
+        ByteArrayOutputStream expectedIndexingOutputStream = new ByteArrayOutputStream();
+
+        expectedOrderedRuleOutputStream.write(DEFAULT_FORMAT_VERSION_BYTES);
+        int totalBytesWritten = DEFAULT_FORMAT_VERSION_BYTES.length;
+
+        String expectedIndexingBytesForPackageNameIndexed =
+                SERIALIZED_START_INDEXING_KEY
+                        + getBits(totalBytesWritten, /* numOfBits= */ 32);
+        for (int count = 0; count < ruleCount; count++) {
+            String packageName = String.format("%s%04d", packagePrefix, count);
+            if (count > 0 && count % INDEXING_BLOCK_SIZE == 0) {
+                expectedIndexingBytesForPackageNameIndexed +=
+                        IS_NOT_HASHED
+                                + getBits(packageName.length(), VALUE_SIZE_BITS)
+                                + getValueBits(packageName)
+                                + getBits(totalBytesWritten, /* numOfBits= */ 32);
+            }
+
+            byte[] bytesForPackage =
+                    getBytes(getSerializedCompoundRuleWithPackageNameAndSampleInstallerName(
+                            packageName));
+            expectedOrderedRuleOutputStream.write(bytesForPackage);
+            totalBytesWritten += bytesForPackage.length;
+        }
+        expectedIndexingBytesForPackageNameIndexed +=
+                SERIALIZED_END_INDEXING_KEY
+                        + getBits(totalBytesWritten, /* numOfBits= */ 32);
+        expectedIndexingOutputStream.write(getBytes(expectedIndexingBytesForPackageNameIndexed));
+
+        String expectedIndexingBytesForAppCertificateIndexed =
+                SERIALIZED_START_INDEXING_KEY
+                        + getBits(totalBytesWritten, /* numOfBits= */ 32);
+        for (int count = 0; count < ruleCount; count++) {
+            String appCertificate = String.format("%s%04d", appCertificatePrefix, count);
+            if (count > 0 && count % INDEXING_BLOCK_SIZE == 0) {
+                expectedIndexingBytesForAppCertificateIndexed +=
+                        IS_NOT_HASHED
+                                + getBits(appCertificate.length(), VALUE_SIZE_BITS)
+                                + getValueBits(appCertificate)
+                                + getBits(totalBytesWritten, /* numOfBits= */ 32);
+            }
+
+            byte[] bytesForPackage =
+                    getBytes(getSerializedCompoundRuleWithCertificateNameAndSampleInstallerName(
+                            appCertificate));
+            expectedOrderedRuleOutputStream.write(bytesForPackage);
+            totalBytesWritten += bytesForPackage.length;
+        }
+        expectedIndexingBytesForAppCertificateIndexed +=
+                SERIALIZED_END_INDEXING_KEY
+                        + getBits(totalBytesWritten, /* numOfBits= */ 32);
+        expectedIndexingOutputStream.write(getBytes(expectedIndexingBytesForAppCertificateIndexed));
+
+        String expectedIndexingBytesForUnindexed =
+                SERIALIZED_START_INDEXING_KEY
+                        + getBits(totalBytesWritten, /* numOfBits= */ 32);
+        for (int count = 0; count < ruleCount; count++) {
+            byte[] bytesForPackage =
+                    getBytes(getSerializedCompoundRuleWithInstallerNameAndInstallerCert(
+                            String.format("%s%04d", installerNamePrefix, count)));
+            expectedOrderedRuleOutputStream.write(bytesForPackage);
+            totalBytesWritten += bytesForPackage.length;
+        }
+        expectedIndexingBytesForUnindexed +=
+                SERIALIZED_END_INDEXING_KEY
+                        + getBits(totalBytesWritten, /* numOfBits= */ 32);
+        expectedIndexingOutputStream.write(getBytes(expectedIndexingBytesForUnindexed));
+
+
+        assertThat(ruleOutputStream.toByteArray())
+                .isEqualTo(expectedOrderedRuleOutputStream.toByteArray());
+        assertThat(indexingOutputStream.toByteArray())
+                .isEqualTo(expectedIndexingOutputStream.toByteArray());
     }
 
     private Rule getRuleWithPackageNameAndSampleInstallerName(String packageName) {
@@ -616,6 +688,44 @@
                 + END_BIT;
     }
 
+    private Rule getNonIndexedRuleWithInstallerName(String installerName) {
+        return new Rule(
+                new CompoundFormula(
+                        CompoundFormula.AND,
+                        Arrays.asList(
+                                new AtomicFormula.StringAtomicFormula(
+                                        AtomicFormula.INSTALLER_NAME,
+                                        installerName,
+                                        /* isHashedValue= */ false),
+                                new AtomicFormula.StringAtomicFormula(
+                                        AtomicFormula.INSTALLER_CERTIFICATE,
+                                        SAMPLE_INSTALLER_CERT,
+                                        /* isHashedValue= */ false))),
+                Rule.DENY);
+    }
+
+    private String getSerializedCompoundRuleWithInstallerNameAndInstallerCert(
+            String installerName) {
+        return START_BIT
+                + COMPOUND_FORMULA_START_BITS
+                + AND
+                + ATOMIC_FORMULA_START_BITS
+                + INSTALLER_NAME
+                + EQ
+                + IS_NOT_HASHED
+                + getBits(installerName.length(), VALUE_SIZE_BITS)
+                + getValueBits(installerName)
+                + ATOMIC_FORMULA_START_BITS
+                + INSTALLER_CERTIFICATE
+                + EQ
+                + IS_NOT_HASHED
+                + getBits(SAMPLE_INSTALLER_CERT.length(), VALUE_SIZE_BITS)
+                + getValueBits(SAMPLE_INSTALLER_CERT)
+                + COMPOUND_FORMULA_END_BITS
+                + DENY
+                + END_BIT;
+    }
+
     private static Formula getInvalidFormula() {
         return new Formula() {
             @Override
diff --git a/services/tests/servicestests/src/com/android/server/integrity/serializer/RuleXmlSerializerTest.java b/services/tests/servicestests/src/com/android/server/integrity/serializer/RuleXmlSerializerTest.java
index 0bb2d44..ff7722c 100644
--- a/services/tests/servicestests/src/com/android/server/integrity/serializer/RuleXmlSerializerTest.java
+++ b/services/tests/servicestests/src/com/android/server/integrity/serializer/RuleXmlSerializerTest.java
@@ -145,7 +145,8 @@
         xmlSerializer.serialize(
                 Collections.singletonList(rule),
                 /* formatVersion= */ Optional.empty(),
-                outputStream);
+                outputStream,
+                new ByteArrayOutputStream());
 
         byte[] actualRules = outputStream.toString().getBytes(StandardCharsets.UTF_8);
         assertEquals(expectedRules, new String(actualRules, StandardCharsets.UTF_8));