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.serializer.RuleIndexingDetails.APP_CERTIFICATE_INDEXED; 20 import static com.android.server.integrity.serializer.RuleIndexingDetails.NOT_INDEXED; 21 import static com.android.server.integrity.serializer.RuleIndexingDetails.PACKAGE_NAME_INDEXED; 22 23 import android.content.integrity.AtomicFormula; 24 import android.content.integrity.CompoundFormula; 25 import android.content.integrity.IntegrityFormula; 26 import android.content.integrity.Rule; 27 28 import java.util.ArrayList; 29 import java.util.HashMap; 30 import java.util.List; 31 import java.util.Map; 32 import java.util.Optional; 33 34 /** A helper class for identifying the indexing type and key of a given rule. */ 35 class RuleIndexingDetailsIdentifier { 36 37 /** 38 * Splits a given rule list into three indexing categories. Each rule category is returned as a 39 * TreeMap that is sorted by their indexing keys -- where keys correspond to package name for 40 * PACKAGE_NAME_INDEXED rules, app certificate for APP_CERTIFICATE_INDEXED rules and N/A for 41 * NOT_INDEXED rules. 42 */ splitRulesIntoIndexBuckets( List<Rule> rules)43 public static Map<Integer, Map<String, List<Rule>>> splitRulesIntoIndexBuckets( 44 List<Rule> rules) { 45 if (rules == null) { 46 throw new IllegalArgumentException( 47 "Index buckets cannot be created for null rule list."); 48 } 49 50 Map<Integer, Map<String, List<Rule>>> typeOrganizedRuleMap = new HashMap(); 51 typeOrganizedRuleMap.put(NOT_INDEXED, new HashMap()); 52 typeOrganizedRuleMap.put(PACKAGE_NAME_INDEXED, new HashMap<>()); 53 typeOrganizedRuleMap.put(APP_CERTIFICATE_INDEXED, new HashMap<>()); 54 55 // Split the rules into the appropriate indexed pattern. The Tree Maps help us to keep the 56 // entries sorted by their index key. 57 for (Rule rule : rules) { 58 RuleIndexingDetails indexingDetails; 59 try { 60 indexingDetails = getIndexingDetails(rule.getFormula()); 61 } catch (Exception e) { 62 throw new IllegalArgumentException( 63 String.format("Malformed rule identified. [%s]", rule.toString())); 64 } 65 66 int ruleIndexType = indexingDetails.getIndexType(); 67 String ruleKey = indexingDetails.getRuleKey(); 68 69 if (!typeOrganizedRuleMap.get(ruleIndexType).containsKey(ruleKey)) { 70 typeOrganizedRuleMap.get(ruleIndexType).put(ruleKey, new ArrayList()); 71 } 72 73 typeOrganizedRuleMap.get(ruleIndexType).get(ruleKey).add(rule); 74 } 75 76 return typeOrganizedRuleMap; 77 } 78 getIndexingDetails(IntegrityFormula formula)79 private static RuleIndexingDetails getIndexingDetails(IntegrityFormula formula) { 80 switch (formula.getTag()) { 81 case IntegrityFormula.COMPOUND_FORMULA_TAG: 82 return getIndexingDetailsForCompoundFormula((CompoundFormula) formula); 83 case IntegrityFormula.STRING_ATOMIC_FORMULA_TAG: 84 return getIndexingDetailsForStringAtomicFormula( 85 (AtomicFormula.StringAtomicFormula) formula); 86 case IntegrityFormula.LONG_ATOMIC_FORMULA_TAG: 87 case IntegrityFormula.INSTALLER_ALLOWED_BY_MANIFEST_FORMULA_TAG: 88 case IntegrityFormula.BOOLEAN_ATOMIC_FORMULA_TAG: 89 // Package name and app certificate related formulas are string atomic formulas. 90 return new RuleIndexingDetails(NOT_INDEXED); 91 default: 92 throw new IllegalArgumentException( 93 String.format("Invalid formula tag type: %s", formula.getTag())); 94 } 95 } 96 getIndexingDetailsForCompoundFormula( CompoundFormula compoundFormula)97 private static RuleIndexingDetails getIndexingDetailsForCompoundFormula( 98 CompoundFormula compoundFormula) { 99 int connector = compoundFormula.getConnector(); 100 List<IntegrityFormula> formulas = compoundFormula.getFormulas(); 101 102 switch (connector) { 103 case CompoundFormula.AND: 104 case CompoundFormula.OR: 105 // If there is a package name related atomic rule, return package name indexed. 106 Optional<RuleIndexingDetails> packageNameRule = 107 formulas.stream() 108 .map(formula -> getIndexingDetails(formula)) 109 .filter(ruleIndexingDetails -> ruleIndexingDetails.getIndexType() 110 == PACKAGE_NAME_INDEXED) 111 .findAny(); 112 if (packageNameRule.isPresent()) { 113 return packageNameRule.get(); 114 } 115 116 // If there is an app certificate related atomic rule but no package name related 117 // atomic rule, return app certificate indexed. 118 Optional<RuleIndexingDetails> appCertificateRule = 119 formulas.stream() 120 .map(formula -> getIndexingDetails(formula)) 121 .filter(ruleIndexingDetails -> ruleIndexingDetails.getIndexType() 122 == APP_CERTIFICATE_INDEXED) 123 .findAny(); 124 if (appCertificateRule.isPresent()) { 125 return appCertificateRule.get(); 126 } 127 128 // Do not index when there is not package name or app certificate indexing. 129 return new RuleIndexingDetails(NOT_INDEXED); 130 default: 131 // Having a NOT operator in the indexing messes up the indexing; e.g., deny 132 // installation if app certificate is NOT X (should not be indexed with app cert 133 // X). We will not keep these rules indexed. 134 // Also any other type of unknown operators will not be indexed. 135 return new RuleIndexingDetails(NOT_INDEXED); 136 } 137 } 138 getIndexingDetailsForStringAtomicFormula( AtomicFormula.StringAtomicFormula atomicFormula)139 private static RuleIndexingDetails getIndexingDetailsForStringAtomicFormula( 140 AtomicFormula.StringAtomicFormula atomicFormula) { 141 switch (atomicFormula.getKey()) { 142 case AtomicFormula.PACKAGE_NAME: 143 return new RuleIndexingDetails(PACKAGE_NAME_INDEXED, atomicFormula.getValue()); 144 case AtomicFormula.APP_CERTIFICATE: 145 return new RuleIndexingDetails(APP_CERTIFICATE_INDEXED, atomicFormula.getValue()); 146 default: 147 return new RuleIndexingDetails(NOT_INDEXED); 148 } 149 } 150 } 151 152