1 /* 2 * Copyright (C) 2020 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.parser; 18 19 import static com.android.server.integrity.model.IndexingFileConstants.END_INDEXING_KEY; 20 import static com.android.server.integrity.model.IndexingFileConstants.START_INDEXING_KEY; 21 import static com.android.server.integrity.parser.BinaryFileOperations.getIntValue; 22 import static com.android.server.integrity.parser.BinaryFileOperations.getStringValue; 23 24 import android.content.integrity.AppInstallMetadata; 25 26 import com.android.server.integrity.model.BitInputStream; 27 28 import java.io.IOException; 29 import java.io.InputStream; 30 import java.util.ArrayList; 31 import java.util.Arrays; 32 import java.util.LinkedHashMap; 33 import java.util.List; 34 import java.util.stream.Collectors; 35 36 /** Helper class to identify the necessary indexes that needs to be read. */ 37 public class RuleIndexingController { 38 39 private static LinkedHashMap<String, Integer> sPackageNameBasedIndexes; 40 private static LinkedHashMap<String, Integer> sAppCertificateBasedIndexes; 41 private static LinkedHashMap<String, Integer> sUnindexedRuleIndexes; 42 43 /** 44 * Provide the indexing file to read and the object will be constructed by reading and 45 * identifying the indexes. 46 */ RuleIndexingController(InputStream inputStream)47 public RuleIndexingController(InputStream inputStream) throws IOException { 48 BitInputStream bitInputStream = new BitInputStream(inputStream); 49 sPackageNameBasedIndexes = getNextIndexGroup(bitInputStream); 50 sAppCertificateBasedIndexes = getNextIndexGroup(bitInputStream); 51 sUnindexedRuleIndexes = getNextIndexGroup(bitInputStream); 52 } 53 54 /** 55 * Returns a list of integers with the starting and ending bytes of the rules that needs to be 56 * read and evaluated. 57 */ identifyRulesToEvaluate(AppInstallMetadata appInstallMetadata)58 public List<RuleIndexRange> identifyRulesToEvaluate(AppInstallMetadata appInstallMetadata) { 59 List<RuleIndexRange> indexRanges = new ArrayList<>(); 60 61 // Add the range for package name indexes rules. 62 indexRanges.add( 63 searchIndexingKeysRangeContainingKey( 64 sPackageNameBasedIndexes, appInstallMetadata.getPackageName())); 65 66 // Add the range for app certificate indexes rules of all certificates. 67 for (String appCertificate : appInstallMetadata.getAppCertificates()) { 68 indexRanges.add( 69 searchIndexingKeysRangeContainingKey( 70 sAppCertificateBasedIndexes, appCertificate)); 71 } 72 73 // Add the range for unindexed rules. 74 indexRanges.add( 75 new RuleIndexRange( 76 sUnindexedRuleIndexes.get(START_INDEXING_KEY), 77 sUnindexedRuleIndexes.get(END_INDEXING_KEY))); 78 79 return indexRanges; 80 } 81 getNextIndexGroup(BitInputStream bitInputStream)82 private LinkedHashMap<String, Integer> getNextIndexGroup(BitInputStream bitInputStream) 83 throws IOException { 84 LinkedHashMap<String, Integer> keyToIndexMap = new LinkedHashMap<>(); 85 while (bitInputStream.hasNext()) { 86 String key = getStringValue(bitInputStream); 87 int value = getIntValue(bitInputStream); 88 89 keyToIndexMap.put(key, value); 90 91 if (key.matches(END_INDEXING_KEY)) { 92 break; 93 } 94 } 95 if (keyToIndexMap.size() < 2) { 96 throw new IllegalStateException("Indexing file is corrupt."); 97 } 98 return keyToIndexMap; 99 } 100 searchIndexingKeysRangeContainingKey( LinkedHashMap<String, Integer> indexMap, String searchedKey)101 private static RuleIndexRange searchIndexingKeysRangeContainingKey( 102 LinkedHashMap<String, Integer> indexMap, String searchedKey) { 103 List<String> keys = indexMap.keySet().stream().collect(Collectors.toList()); 104 List<String> identifiedKeyRange = 105 searchKeysRangeContainingKey(keys, searchedKey, 0, keys.size() - 1); 106 return new RuleIndexRange( 107 indexMap.get(identifiedKeyRange.get(0)), indexMap.get(identifiedKeyRange.get(1))); 108 } 109 searchKeysRangeContainingKey( List<String> sortedKeyList, String key, int startIndex, int endIndex)110 private static List<String> searchKeysRangeContainingKey( 111 List<String> sortedKeyList, String key, int startIndex, int endIndex) { 112 if (endIndex <= startIndex) { 113 throw new IllegalStateException("Indexing file is corrupt."); 114 } 115 if (endIndex - startIndex == 1) { 116 return Arrays.asList(sortedKeyList.get(startIndex), sortedKeyList.get(endIndex)); 117 } 118 119 int midKeyIndex = startIndex + ((endIndex - startIndex) / 2); 120 String midKey = sortedKeyList.get(midKeyIndex); 121 122 if (key.compareTo(midKey) >= 0) { 123 return searchKeysRangeContainingKey(sortedKeyList, key, midKeyIndex, endIndex); 124 } else { 125 return searchKeysRangeContainingKey(sortedKeyList, key, startIndex, midKeyIndex); 126 } 127 } 128 } 129