1 /* 2 * Copyright (C) 2019 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.server.integrity.serializer; 18 19 import static com.android.server.integrity.model.ComponentBitSize.ATOMIC_FORMULA_START; 20 import static com.android.server.integrity.model.ComponentBitSize.COMPOUND_FORMULA_END; 21 import static com.android.server.integrity.model.ComponentBitSize.COMPOUND_FORMULA_START; 22 import static com.android.server.integrity.model.ComponentBitSize.CONNECTOR_BITS; 23 import static com.android.server.integrity.model.ComponentBitSize.DEFAULT_FORMAT_VERSION; 24 import static com.android.server.integrity.model.ComponentBitSize.EFFECT_BITS; 25 import static com.android.server.integrity.model.ComponentBitSize.FORMAT_VERSION_BITS; 26 import static com.android.server.integrity.model.ComponentBitSize.INSTALLER_ALLOWED_BY_MANIFEST_START; 27 import static com.android.server.integrity.model.ComponentBitSize.KEY_BITS; 28 import static com.android.server.integrity.model.ComponentBitSize.OPERATOR_BITS; 29 import static com.android.server.integrity.model.ComponentBitSize.SEPARATOR_BITS; 30 import static com.android.server.integrity.model.ComponentBitSize.VALUE_SIZE_BITS; 31 import static com.android.server.integrity.model.IndexingFileConstants.END_INDEXING_KEY; 32 import static com.android.server.integrity.model.IndexingFileConstants.INDEXING_BLOCK_SIZE; 33 import static com.android.server.integrity.model.IndexingFileConstants.START_INDEXING_KEY; 34 import static com.android.server.integrity.serializer.RuleIndexingDetails.APP_CERTIFICATE_INDEXED; 35 import static com.android.server.integrity.serializer.RuleIndexingDetails.NOT_INDEXED; 36 import static com.android.server.integrity.serializer.RuleIndexingDetails.PACKAGE_NAME_INDEXED; 37 38 import android.content.integrity.AtomicFormula; 39 import android.content.integrity.CompoundFormula; 40 import android.content.integrity.InstallerAllowedByManifestFormula; 41 import android.content.integrity.IntegrityFormula; 42 import android.content.integrity.IntegrityUtils; 43 import android.content.integrity.Rule; 44 45 import com.android.internal.util.Preconditions; 46 import com.android.server.integrity.model.BitOutputStream; 47 import com.android.server.integrity.model.ByteTrackedOutputStream; 48 49 import java.io.ByteArrayOutputStream; 50 import java.io.IOException; 51 import java.io.OutputStream; 52 import java.nio.charset.StandardCharsets; 53 import java.util.LinkedHashMap; 54 import java.util.List; 55 import java.util.Map; 56 import java.util.Optional; 57 import java.util.stream.Collectors; 58 59 /** A helper class to serialize rules from the {@link Rule} model to Binary representation. */ 60 public class RuleBinarySerializer implements RuleSerializer { 61 static final int TOTAL_RULE_SIZE_LIMIT = 200000; 62 static final int INDEXED_RULE_SIZE_LIMIT = 100000; 63 static final int NONINDEXED_RULE_SIZE_LIMIT = 1000; 64 65 // Get the byte representation for a list of rules. 66 @Override serialize(List<Rule> rules, Optional<Integer> formatVersion)67 public byte[] serialize(List<Rule> rules, Optional<Integer> formatVersion) 68 throws RuleSerializeException { 69 try { 70 ByteArrayOutputStream rulesOutputStream = new ByteArrayOutputStream(); 71 serialize(rules, formatVersion, rulesOutputStream, new ByteArrayOutputStream()); 72 return rulesOutputStream.toByteArray(); 73 } catch (Exception e) { 74 throw new RuleSerializeException(e.getMessage(), e); 75 } 76 } 77 78 // Get the byte representation for a list of rules, and write them to an output stream. 79 @Override serialize( List<Rule> rules, Optional<Integer> formatVersion, OutputStream rulesFileOutputStream, OutputStream indexingFileOutputStream)80 public void serialize( 81 List<Rule> rules, 82 Optional<Integer> formatVersion, 83 OutputStream rulesFileOutputStream, 84 OutputStream indexingFileOutputStream) 85 throws RuleSerializeException { 86 try { 87 if (rules == null) { 88 throw new IllegalArgumentException("Null rules cannot be serialized."); 89 } 90 91 if (rules.size() > TOTAL_RULE_SIZE_LIMIT) { 92 throw new IllegalArgumentException("Too many rules provided: " + rules.size()); 93 } 94 95 // Determine the indexing groups and the order of the rules within each indexed group. 96 Map<Integer, Map<String, List<Rule>>> indexedRules = 97 RuleIndexingDetailsIdentifier.splitRulesIntoIndexBuckets(rules); 98 99 // Validate the rule blocks are not larger than expected limits. 100 verifySize(indexedRules.get(PACKAGE_NAME_INDEXED), INDEXED_RULE_SIZE_LIMIT); 101 verifySize(indexedRules.get(APP_CERTIFICATE_INDEXED), INDEXED_RULE_SIZE_LIMIT); 102 verifySize(indexedRules.get(NOT_INDEXED), NONINDEXED_RULE_SIZE_LIMIT); 103 104 // Serialize the rules. 105 ByteTrackedOutputStream ruleFileByteTrackedOutputStream = 106 new ByteTrackedOutputStream(rulesFileOutputStream); 107 serializeRuleFileMetadata(formatVersion, ruleFileByteTrackedOutputStream); 108 LinkedHashMap<String, Integer> packageNameIndexes = 109 serializeRuleList( 110 indexedRules.get(PACKAGE_NAME_INDEXED), 111 ruleFileByteTrackedOutputStream); 112 LinkedHashMap<String, Integer> appCertificateIndexes = 113 serializeRuleList( 114 indexedRules.get(APP_CERTIFICATE_INDEXED), 115 ruleFileByteTrackedOutputStream); 116 LinkedHashMap<String, Integer> unindexedRulesIndexes = 117 serializeRuleList( 118 indexedRules.get(NOT_INDEXED), ruleFileByteTrackedOutputStream); 119 120 // Serialize their indexes. 121 BitOutputStream indexingBitOutputStream = new BitOutputStream(indexingFileOutputStream); 122 serializeIndexGroup(packageNameIndexes, indexingBitOutputStream, /* isIndexed= */ true); 123 serializeIndexGroup( 124 appCertificateIndexes, indexingBitOutputStream, /* isIndexed= */ true); 125 serializeIndexGroup( 126 unindexedRulesIndexes, indexingBitOutputStream, /* isIndexed= */ false); 127 indexingBitOutputStream.flush(); 128 } catch (Exception e) { 129 throw new RuleSerializeException(e.getMessage(), e); 130 } 131 } 132 verifySize(Map<String, List<Rule>> ruleListMap, int ruleSizeLimit)133 private void verifySize(Map<String, List<Rule>> ruleListMap, int ruleSizeLimit) { 134 int totalRuleCount = 135 ruleListMap.values().stream() 136 .map(list -> list.size()) 137 .collect(Collectors.summingInt(Integer::intValue)); 138 if (totalRuleCount > ruleSizeLimit) { 139 throw new IllegalArgumentException( 140 "Too many rules provided in the indexing group. Provided " 141 + totalRuleCount 142 + " limit " 143 + ruleSizeLimit); 144 } 145 } 146 serializeRuleFileMetadata( Optional<Integer> formatVersion, ByteTrackedOutputStream outputStream)147 private void serializeRuleFileMetadata( 148 Optional<Integer> formatVersion, ByteTrackedOutputStream outputStream) 149 throws IOException { 150 int formatVersionValue = formatVersion.orElse(DEFAULT_FORMAT_VERSION); 151 152 BitOutputStream bitOutputStream = new BitOutputStream(outputStream); 153 bitOutputStream.setNext(FORMAT_VERSION_BITS, formatVersionValue); 154 bitOutputStream.flush(); 155 } 156 serializeRuleList( Map<String, List<Rule>> rulesMap, ByteTrackedOutputStream outputStream)157 private LinkedHashMap<String, Integer> serializeRuleList( 158 Map<String, List<Rule>> rulesMap, ByteTrackedOutputStream outputStream) 159 throws IOException { 160 Preconditions.checkArgument( 161 rulesMap != null, "serializeRuleList should never be called with null rule list."); 162 163 BitOutputStream bitOutputStream = new BitOutputStream(outputStream); 164 LinkedHashMap<String, Integer> indexMapping = new LinkedHashMap(); 165 indexMapping.put(START_INDEXING_KEY, outputStream.getWrittenBytesCount()); 166 167 List<String> sortedKeys = rulesMap.keySet().stream().sorted().collect(Collectors.toList()); 168 int indexTracker = 0; 169 for (String key : sortedKeys) { 170 if (indexTracker >= INDEXING_BLOCK_SIZE) { 171 indexMapping.put(key, outputStream.getWrittenBytesCount()); 172 indexTracker = 0; 173 } 174 175 for (Rule rule : rulesMap.get(key)) { 176 serializeRule(rule, bitOutputStream); 177 bitOutputStream.flush(); 178 indexTracker++; 179 } 180 } 181 indexMapping.put(END_INDEXING_KEY, outputStream.getWrittenBytesCount()); 182 183 return indexMapping; 184 } 185 serializeRule(Rule rule, BitOutputStream bitOutputStream)186 private void serializeRule(Rule rule, BitOutputStream bitOutputStream) throws IOException { 187 if (rule == null) { 188 throw new IllegalArgumentException("Null rule can not be serialized"); 189 } 190 191 // Start with a '1' bit to mark the start of a rule. 192 bitOutputStream.setNext(); 193 194 serializeFormula(rule.getFormula(), bitOutputStream); 195 bitOutputStream.setNext(EFFECT_BITS, rule.getEffect()); 196 197 // End with a '1' bit to mark the end of a rule. 198 bitOutputStream.setNext(); 199 } 200 serializeFormula(IntegrityFormula formula, BitOutputStream bitOutputStream)201 private void serializeFormula(IntegrityFormula formula, BitOutputStream bitOutputStream) 202 throws IOException { 203 if (formula instanceof AtomicFormula) { 204 serializeAtomicFormula((AtomicFormula) formula, bitOutputStream); 205 } else if (formula instanceof CompoundFormula) { 206 serializeCompoundFormula((CompoundFormula) formula, bitOutputStream); 207 } else if (formula instanceof InstallerAllowedByManifestFormula) { 208 bitOutputStream.setNext(SEPARATOR_BITS, INSTALLER_ALLOWED_BY_MANIFEST_START); 209 } else { 210 throw new IllegalArgumentException( 211 String.format("Invalid formula type: %s", formula.getClass())); 212 } 213 } 214 serializeCompoundFormula( CompoundFormula compoundFormula, BitOutputStream bitOutputStream)215 private void serializeCompoundFormula( 216 CompoundFormula compoundFormula, BitOutputStream bitOutputStream) throws IOException { 217 if (compoundFormula == null) { 218 throw new IllegalArgumentException("Null compound formula can not be serialized"); 219 } 220 221 bitOutputStream.setNext(SEPARATOR_BITS, COMPOUND_FORMULA_START); 222 bitOutputStream.setNext(CONNECTOR_BITS, compoundFormula.getConnector()); 223 for (IntegrityFormula formula : compoundFormula.getFormulas()) { 224 serializeFormula(formula, bitOutputStream); 225 } 226 bitOutputStream.setNext(SEPARATOR_BITS, COMPOUND_FORMULA_END); 227 } 228 serializeAtomicFormula( AtomicFormula atomicFormula, BitOutputStream bitOutputStream)229 private void serializeAtomicFormula( 230 AtomicFormula atomicFormula, BitOutputStream bitOutputStream) throws IOException { 231 if (atomicFormula == null) { 232 throw new IllegalArgumentException("Null atomic formula can not be serialized"); 233 } 234 235 bitOutputStream.setNext(SEPARATOR_BITS, ATOMIC_FORMULA_START); 236 bitOutputStream.setNext(KEY_BITS, atomicFormula.getKey()); 237 if (atomicFormula.getTag() == AtomicFormula.STRING_ATOMIC_FORMULA_TAG) { 238 AtomicFormula.StringAtomicFormula stringAtomicFormula = 239 (AtomicFormula.StringAtomicFormula) atomicFormula; 240 bitOutputStream.setNext(OPERATOR_BITS, AtomicFormula.EQ); 241 serializeStringValue( 242 stringAtomicFormula.getValue(), 243 stringAtomicFormula.getIsHashedValue(), 244 bitOutputStream); 245 } else if (atomicFormula.getTag() == AtomicFormula.LONG_ATOMIC_FORMULA_TAG) { 246 AtomicFormula.LongAtomicFormula longAtomicFormula = 247 (AtomicFormula.LongAtomicFormula) atomicFormula; 248 bitOutputStream.setNext(OPERATOR_BITS, longAtomicFormula.getOperator()); 249 // TODO(b/147880712): Temporary hack until we support long values in bitOutputStream 250 long value = longAtomicFormula.getValue(); 251 serializeIntValue((int) (value >>> 32), bitOutputStream); 252 serializeIntValue((int) value, bitOutputStream); 253 } else if (atomicFormula.getTag() == AtomicFormula.BOOLEAN_ATOMIC_FORMULA_TAG) { 254 AtomicFormula.BooleanAtomicFormula booleanAtomicFormula = 255 (AtomicFormula.BooleanAtomicFormula) atomicFormula; 256 bitOutputStream.setNext(OPERATOR_BITS, AtomicFormula.EQ); 257 serializeBooleanValue(booleanAtomicFormula.getValue(), bitOutputStream); 258 } else { 259 throw new IllegalArgumentException( 260 String.format("Invalid atomic formula type: %s", atomicFormula.getClass())); 261 } 262 } 263 serializeIndexGroup( LinkedHashMap<String, Integer> indexes, BitOutputStream bitOutputStream, boolean isIndexed)264 private void serializeIndexGroup( 265 LinkedHashMap<String, Integer> indexes, 266 BitOutputStream bitOutputStream, 267 boolean isIndexed) 268 throws IOException { 269 // Output the starting location of this indexing group. 270 serializeStringValue(START_INDEXING_KEY, /* isHashedValue= */ false, bitOutputStream); 271 serializeIntValue(indexes.get(START_INDEXING_KEY), bitOutputStream); 272 273 // If the group is indexed, output the locations of the indexes. 274 if (isIndexed) { 275 for (Map.Entry<String, Integer> entry : indexes.entrySet()) { 276 if (!entry.getKey().equals(START_INDEXING_KEY) 277 && !entry.getKey().equals(END_INDEXING_KEY)) { 278 serializeStringValue( 279 entry.getKey(), /* isHashedValue= */ false, bitOutputStream); 280 serializeIntValue(entry.getValue(), bitOutputStream); 281 } 282 } 283 } 284 285 // Output the end location of this indexing group. 286 serializeStringValue(END_INDEXING_KEY, /*isHashedValue= */ false, bitOutputStream); 287 serializeIntValue(indexes.get(END_INDEXING_KEY), bitOutputStream); 288 } 289 serializeStringValue( String value, boolean isHashedValue, BitOutputStream bitOutputStream)290 private void serializeStringValue( 291 String value, boolean isHashedValue, BitOutputStream bitOutputStream) 292 throws IOException { 293 if (value == null) { 294 throw new IllegalArgumentException("String value can not be null."); 295 } 296 byte[] valueBytes = getBytesForString(value, isHashedValue); 297 298 bitOutputStream.setNext(isHashedValue); 299 bitOutputStream.setNext(VALUE_SIZE_BITS, valueBytes.length); 300 for (byte valueByte : valueBytes) { 301 bitOutputStream.setNext(/* numOfBits= */ 8, valueByte); 302 } 303 } 304 serializeIntValue(int value, BitOutputStream bitOutputStream)305 private void serializeIntValue(int value, BitOutputStream bitOutputStream) throws IOException { 306 bitOutputStream.setNext(/* numOfBits= */ 32, value); 307 } 308 serializeBooleanValue(boolean value, BitOutputStream bitOutputStream)309 private void serializeBooleanValue(boolean value, BitOutputStream bitOutputStream) 310 throws IOException { 311 bitOutputStream.setNext(value); 312 } 313 314 // Get the byte array for a value. 315 // If the value is not hashed, use its byte array form directly. 316 // If the value is hashed, get the raw form decoding of the value. All hashed values are 317 // hex-encoded. Serialized values are in raw form. getBytesForString(String value, boolean isHashedValue)318 private static byte[] getBytesForString(String value, boolean isHashedValue) { 319 if (!isHashedValue) { 320 return value.getBytes(StandardCharsets.UTF_8); 321 } 322 return IntegrityUtils.getBytesFromHexDigest(value); 323 } 324 } 325