Modify the RuleBinarySerializer to output the rules in the ordered fashion that is suitable for indexing.

Bug: 145488708
Test: atest FrameworksServicesTests:RuleBinarySerializerTest
Change-Id: I3f086ea087d7a7cf56f763912e0e3162f2b8c7c9

4 files changed, 235 insertions, 28 deletions

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 fdbb7d9df293..73a815ad032b 100644
--- a/services/core/java/com/android/server/integrity/serializer/RuleBinarySerializer.java
+++ b/services/core/java/com/android/server/integrity/serializer/RuleBinarySerializer.java
@@ -27,6 +27,9 @@ import static com.android.server.integrity.model.ComponentBitSize.KEY_BITS;
 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.RuleIndexingDetails.APP_CERTIFICATE_INDEXED;
+import static com.android.server.integrity.serializer.RuleIndexingDetails.NOT_INDEXED;
+import static com.android.server.integrity.serializer.RuleIndexingDetails.PACKAGE_NAME_INDEXED;
 
 import android.content.integrity.AtomicFormula;
 import android.content.integrity.CompoundFormula;
@@ -36,49 +39,68 @@ import android.content.integrity.Rule;
 import com.android.server.integrity.model.BitOutputStream;
 
 import java.io.ByteArrayOutputStream;
+import java.io.IOException;
 import java.io.OutputStream;
 import java.nio.charset.StandardCharsets;
 import java.util.List;
+import java.util.Map;
 import java.util.Optional;
 
 /** A helper class to serialize rules from the {@link Rule} model to Binary representation. */
 public class RuleBinarySerializer implements RuleSerializer {
 
-    // Get the byte representation for a list of rules, and write them to an output stream.
+    // Get the byte representation for a list of rules.
     @Override
-    public void serialize(
-            List<Rule> rules, Optional<Integer> formatVersion, OutputStream outputStream)
+    public byte[] serialize(List<Rule> rules, Optional<Integer> formatVersion)
             throws RuleSerializeException {
         try {
-            BitOutputStream bitOutputStream = new BitOutputStream();
-
-            int formatVersionValue = formatVersion.orElse(DEFAULT_FORMAT_VERSION);
-            bitOutputStream.setNext(FORMAT_VERSION_BITS, formatVersionValue);
-            outputStream.write(bitOutputStream.toByteArray());
-
-            for (Rule rule : rules) {
-                bitOutputStream.clear();
-                serializeRule(rule, bitOutputStream);
-                outputStream.write(bitOutputStream.toByteArray());
-            }
+            ByteArrayOutputStream byteArrayOutputStream = new ByteArrayOutputStream();
+            serialize(rules, formatVersion, byteArrayOutputStream);
+            return byteArrayOutputStream.toByteArray();
         } catch (Exception e) {
             throw new RuleSerializeException(e.getMessage(), e);
         }
     }
 
-    // Get the byte representation for a list of rules.
+    // Get the byte representation for a list of rules, and write them to an output stream.
     @Override
-    public byte[] serialize(List<Rule> rules, Optional<Integer> formatVersion)
+    public void serialize(
+            List<Rule> rules, Optional<Integer> formatVersion, OutputStream outputStream)
             throws RuleSerializeException {
         try {
-            ByteArrayOutputStream byteArrayOutputStream = new ByteArrayOutputStream();
-            serialize(rules, formatVersion, byteArrayOutputStream);
-            return byteArrayOutputStream.toByteArray();
+            // Determine the indexing groups and the order of the rules within each indexed group.
+            Map<Integer, List<Rule>> indexedRules =
+                    RuleIndexingDetailsIdentifier.splitRulesIntoIndexBuckets(rules);
+
+            serializeRuleFileMetadata(formatVersion, outputStream);
+
+            serializeIndexedRules(indexedRules.get(PACKAGE_NAME_INDEXED), outputStream);
+            serializeIndexedRules(indexedRules.get(APP_CERTIFICATE_INDEXED), outputStream);
+            serializeIndexedRules(indexedRules.get(NOT_INDEXED), outputStream);
         } catch (Exception e) {
             throw new RuleSerializeException(e.getMessage(), e);
         }
     }
 
+    private void serializeRuleFileMetadata(
+            Optional<Integer> formatVersion, OutputStream outputStream) throws IOException {
+        int formatVersionValue = formatVersion.orElse(DEFAULT_FORMAT_VERSION);
+
+        BitOutputStream bitOutputStream = new BitOutputStream();
+        bitOutputStream.setNext(FORMAT_VERSION_BITS, formatVersionValue);
+        outputStream.write(bitOutputStream.toByteArray());
+    }
+
+    private void serializeIndexedRules(List<Rule> rules, OutputStream outputStream)
+            throws IOException {
+        BitOutputStream bitOutputStream = new BitOutputStream();
+        for (Rule rule : rules) {
+            bitOutputStream.clear();
+            serializeRule(rule, bitOutputStream);
+            outputStream.write(bitOutputStream.toByteArray());
+        }
+    }
+
     private void serializeRule(Rule rule, BitOutputStream bitOutputStream) {
         if (rule == null) {
             throw new IllegalArgumentException("Null rule can not be serialized");
diff --git a/services/core/java/com/android/server/integrity/serializer/RuleIndexingDetailsIdentifier.java b/services/core/java/com/android/server/integrity/serializer/RuleIndexingDetailsIdentifier.java
index 7d5e83649373..f9c7912cbee5 100644
--- a/services/core/java/com/android/server/integrity/serializer/RuleIndexingDetailsIdentifier.java
+++ b/services/core/java/com/android/server/integrity/serializer/RuleIndexingDetailsIdentifier.java
@@ -62,7 +62,14 @@ class RuleIndexingDetailsIdentifier {
         // Split the rules into the appropriate indexed pattern. The Tree Maps help us to keep the
         // entries sorted by their index key.
         for (Rule rule : rules) {
-            RuleIndexingDetails indexingDetails = getIndexingDetails(rule.getFormula());
+            RuleIndexingDetails indexingDetails;
+            try {
+                indexingDetails = getIndexingDetails(rule.getFormula());
+            } catch (Exception e) {
+                throw new IllegalArgumentException(
+                        String.format("Malformed rule identified. [%s]", rule.toString()));
+            }
+
             String ruleKey =
                     indexingDetails.getIndexType() != NOT_INDEXED
                             ? indexingDetails.getRuleKey()
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 901277ded5dd..2304bc6dc699 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
@@ -47,13 +47,18 @@ import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
 
 import java.io.ByteArrayOutputStream;
+import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
+import java.util.List;
 import java.util.Optional;
 
 @RunWith(JUnit4.class)
 public class RuleBinarySerializerTest {
 
+    private static final String SAMPLE_INSTALLER_NAME = "com.test.installer";
+    private static final String SAMPLE_INSTALLER_CERT = "installer_cert";
+
     private static final String COMPOUND_FORMULA_START_BITS =
             getBits(COMPOUND_FORMULA_START, SEPARATOR_BITS);
     private static final String COMPOUND_FORMULA_END_BITS =
@@ -67,6 +72,9 @@ public class RuleBinarySerializerTest {
 
     private static final String PACKAGE_NAME = getBits(AtomicFormula.PACKAGE_NAME, KEY_BITS);
     private static final String APP_CERTIFICATE = getBits(AtomicFormula.APP_CERTIFICATE, KEY_BITS);
+    private static final String INSTALLER_NAME = getBits(AtomicFormula.INSTALLER_NAME, KEY_BITS);
+    private static final String INSTALLER_CERTIFICATE =
+            getBits(AtomicFormula.INSTALLER_CERTIFICATE, KEY_BITS);
     private static final String VERSION_CODE = getBits(AtomicFormula.VERSION_CODE, KEY_BITS);
     private static final String PRE_INSTALLED = getBits(AtomicFormula.PRE_INSTALLED, KEY_BITS);
 
@@ -83,17 +91,28 @@ public class RuleBinarySerializerTest {
             getBytes(getBits(DEFAULT_FORMAT_VERSION, FORMAT_VERSION_BITS));
 
     @Test
-    public void testBinaryString_serializeEmptyRule() throws Exception {
-        Rule rule = null;
+    public void testBinaryString_serializeNullRules() {
         RuleSerializer binarySerializer = new RuleBinarySerializer();
 
         assertExpectException(
                 RuleSerializeException.class,
-                /* expectedExceptionMessageRegex= */ "Null rule can not be serialized",
+                /* expectedExceptionMessageRegex= */
+                "Index buckets cannot be created for null rule list.",
                 () ->
-                        binarySerializer.serialize(
-                                Collections.singletonList(rule),
-                                /* formatVersion= */ Optional.empty()));
+                        binarySerializer.serialize(null, /* formatVersion= */ Optional.empty()));
+    }
+
+    @Test
+    public void testBinaryString_emptyRules() throws Exception {
+        ByteArrayOutputStream expectedArrayOutputStream = new ByteArrayOutputStream();
+        expectedArrayOutputStream.write(DEFAULT_FORMAT_VERSION_BYTES);
+
+        ByteArrayOutputStream outputStream = new ByteArrayOutputStream();
+        RuleSerializer binarySerializer = new RuleBinarySerializer();
+        binarySerializer.serialize(
+                Collections.emptyList(), /* formatVersion= */ Optional.empty(), outputStream);
+
+        assertThat(outputStream.toByteArray()).isEqualTo(expectedArrayOutputStream.toByteArray());
     }
 
     @Test
@@ -381,7 +400,7 @@ public class RuleBinarySerializerTest {
 
         assertExpectException(
                 RuleSerializeException.class,
-                /* expectedExceptionMessageRegex= */ "Invalid formula type",
+                /* expectedExceptionMessageRegex= */ "Malformed rule identified.",
                 () ->
                         binarySerializer.serialize(
                                 Collections.singletonList(rule),
@@ -402,6 +421,165 @@ public class RuleBinarySerializerTest {
         assertThat(actualRules).isEqualTo(expectedRules);
     }
 
+    @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);
+
+        RuleSerializer binarySerializer = new RuleBinarySerializer();
+        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());
+
+
+        // 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));
+
+        assertThat(actualRules).isEqualTo(expectedArrayOutputStream.toByteArray());
+    }
+
+    private Rule getRuleWithPackageNameAndSampleInstallerName(String packageName) {
+        return new Rule(
+                new CompoundFormula(
+                        CompoundFormula.AND,
+                        Arrays.asList(
+                                new AtomicFormula.StringAtomicFormula(
+                                        AtomicFormula.PACKAGE_NAME,
+                                        packageName,
+                                        /* isHashedValue= */ false),
+                                new AtomicFormula.StringAtomicFormula(
+                                        AtomicFormula.INSTALLER_NAME,
+                                        SAMPLE_INSTALLER_NAME,
+                                        /* isHashedValue= */ false))),
+                Rule.DENY);
+    }
+
+    private String getSerializedCompoundRuleWithPackageNameAndSampleInstallerName(
+            String packageName) {
+        return START_BIT
+                + COMPOUND_FORMULA_START_BITS
+                + AND
+                + ATOMIC_FORMULA_START_BITS
+                + PACKAGE_NAME
+                + EQ
+                + IS_NOT_HASHED
+                + getBits(packageName.length(), VALUE_SIZE_BITS)
+                + getValueBits(packageName)
+                + ATOMIC_FORMULA_START_BITS
+                + INSTALLER_NAME
+                + EQ
+                + IS_NOT_HASHED
+                + getBits(SAMPLE_INSTALLER_NAME.length(), VALUE_SIZE_BITS)
+                + getValueBits(SAMPLE_INSTALLER_NAME)
+                + COMPOUND_FORMULA_END_BITS
+                + DENY
+                + END_BIT;
+    }
+
+    private Rule getRuleWithAppCertificateAndSampleInstallerName(String certificate) {
+        return new Rule(
+                new CompoundFormula(
+                        CompoundFormula.AND,
+                        Arrays.asList(
+                                new AtomicFormula.StringAtomicFormula(
+                                        AtomicFormula.APP_CERTIFICATE,
+                                        certificate,
+                                        /* isHashedValue= */ false),
+                                new AtomicFormula.StringAtomicFormula(
+                                        AtomicFormula.INSTALLER_NAME,
+                                        SAMPLE_INSTALLER_NAME,
+                                        /* isHashedValue= */ false))),
+                Rule.DENY);
+    }
+
+    private String getSerializedCompoundRuleWithCertificateNameAndSampleInstallerName(
+            String appCertificate) {
+        return START_BIT
+                + COMPOUND_FORMULA_START_BITS
+                + AND
+                + ATOMIC_FORMULA_START_BITS
+                + APP_CERTIFICATE
+                + EQ
+                + IS_NOT_HASHED
+                + getBits(appCertificate.length(), VALUE_SIZE_BITS)
+                + getValueBits(appCertificate)
+                + ATOMIC_FORMULA_START_BITS
+                + INSTALLER_NAME
+                + EQ
+                + IS_NOT_HASHED
+                + getBits(SAMPLE_INSTALLER_NAME.length(), VALUE_SIZE_BITS)
+                + getValueBits(SAMPLE_INSTALLER_NAME)
+                + 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/RuleIndexingDetailsIdentifierTest.java b/services/tests/servicestests/src/com/android/server/integrity/serializer/RuleIndexingDetailsIdentifierTest.java
index 90ec19e06c8c..94e11c68fa9e 100644
--- a/services/tests/servicestests/src/com/android/server/integrity/serializer/RuleIndexingDetailsIdentifierTest.java
+++ b/services/tests/servicestests/src/com/android/server/integrity/serializer/RuleIndexingDetailsIdentifierTest.java
@@ -129,7 +129,7 @@ public class RuleIndexingDetailsIdentifierTest {
 
         assertExpectException(
                 IllegalArgumentException.class,
-                /* expectedExceptionMessageRegex= */ "Invalid formula tag type.",
+                /* expectedExceptionMessageRegex= */ "Malformed rule identified.",
                 () -> splitRulesIntoIndexBuckets(ruleList));
     }