1 /* 2 * Copyright (C) 2023 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.cobalt.observations; 18 19 import static java.lang.Math.max; 20 import static java.lang.Math.min; 21 22 import com.android.cobalt.data.EventVector; 23 24 import com.google.cobalt.MetricDefinition; 25 import com.google.cobalt.MetricDefinition.MetricDimension; 26 import com.google.cobalt.ReportDefinition; 27 28 import java.security.SecureRandom; 29 import java.util.Arrays; 30 import java.util.List; 31 import java.util.Set; 32 33 /** Functions for calculating private indices for privacy-enabled report. */ 34 final class PrivateIndexCalculations { PrivateIndexCalculations()35 private PrivateIndexCalculations() {} 36 37 /** 38 * Encodes a double value into an index. 39 * 40 * <p>Given a `value`, returns an index in the range [0, `numIndexPoints` - 1] using randomized 41 * fixed-point encoding. 42 * 43 * <p>The `value` is snapped to one of the `numIndexPoints` boundary points of the equal 44 * subsegments of the range [`minValue`, `maxValue`]. If `value` is not equal to a boundary 45 * point, then `value` is snapped to one of the two nearest boundary points, with probability 46 * proportional to its distance from each of those points. 47 * 48 * @param value the value to convert; it must be in the range [`minValue`, `maxValue`] 49 * @param minValue the minimum of `value` 50 * @param maxValue the maximum of `value` 51 * @param numIndexPoints the number of index points 52 * @param secureRandom the random number generator to use 53 * @return the index for the given `value` 54 */ doubleToIndex( double value, double minValue, double maxValue, int numIndexPoints, SecureRandom secureRandom)55 static int doubleToIndex( 56 double value, 57 double minValue, 58 double maxValue, 59 int numIndexPoints, 60 SecureRandom secureRandom) { 61 double intervalSize = (maxValue - minValue) / (double) (numIndexPoints - 1); 62 double approxIndex = (value - minValue) / intervalSize; 63 double lowerIndex = Math.floor(approxIndex); 64 double distanceToIndex = approxIndex - lowerIndex; 65 66 return ((int) lowerIndex) + indexOffset(distanceToIndex, secureRandom); 67 } 68 69 /** 70 * Encodes a long to an index. 71 * 72 * <p>See {@link doubleToIndex} for a description of the encoding scheme. 73 * 74 * @param value the value to convert; it must be in the range [`minValue`, `maxValue`] 75 * @param minValue the minimum of `value` 76 * @param maxValue the maximum of `value` 77 * @param numIndexPoints the number of index points 78 * @param secureRandom the random number generator to use 79 * @return the index for the given `value` 80 */ longToIndex( long value, long minValue, long maxValue, int numIndexPoints, SecureRandom secureRandom)81 static int longToIndex( 82 long value, 83 long minValue, 84 long maxValue, 85 int numIndexPoints, 86 SecureRandom secureRandom) { 87 return doubleToIndex( 88 (double) value, (double) minValue, (double) maxValue, numIndexPoints, secureRandom); 89 } 90 91 /** 92 * Provides an index offset based on the distance to the index. 93 * 94 * <p>When a numerical value is converted to an index, an approximate index is calculated for 95 * where that value falls between two indexes. The distance from the floor of that estimate is 96 * then used to randomly determine whether to use the lower or upper index. The larger the 97 * distance, the higher the probability of returning an offset of 1. 98 * 99 * @param distance the distance an approximate index is from the floor index. This should be in 100 * the range [0.0, 1.0) 101 * @param secureRandom the random number generator to use 102 * @return the offset value (either 0 or 1) to use for the given distance 103 */ indexOffset(double distance, SecureRandom secureRandom)104 static int indexOffset(double distance, SecureRandom secureRandom) { 105 if (secureRandom.nextDouble() > distance) { 106 return 0; 107 } 108 return 1; 109 } 110 111 /** Clips a value between the min and max values of a report */ clipValue(long value, ReportDefinition report)112 static long clipValue(long value, ReportDefinition report) { 113 return min(report.getMaxValue(), max(report.getMinValue(), value)); 114 } 115 116 /** 117 * Calculate the total number of possible event vectors for a metric. 118 * 119 * @param metricDimensions the metric's dimensions 120 * @return the total number of possible event vectors 121 */ getNumEventVectors(List<MetricDimension> metricDimensions)122 static int getNumEventVectors(List<MetricDimension> metricDimensions) { 123 int numEventVectors = 1; 124 for (MetricDimension dimension : metricDimensions) { 125 numEventVectors *= getNumEventCodes(dimension); 126 } 127 return numEventVectors; 128 } 129 130 /** 131 * Convert an event vector to a private index for a metric. 132 * 133 * @param eventVector the event vector to convert 134 * @param metric the metric that the event vector is for 135 * @return the private index 136 */ eventVectorToIndex(EventVector eventVector, MetricDefinition metric)137 static int eventVectorToIndex(EventVector eventVector, MetricDefinition metric) { 138 int multiplier = 1; 139 int result = 0; 140 for (int i = 0; i < eventVector.eventCodes().size(); i++) { 141 int eventCode = eventVector.eventCodes().get(i); 142 MetricDimension dimension = metric.getMetricDimensions(i); 143 int index = eventCodeToIndexForDimension(eventCode, dimension); 144 result += index * multiplier; 145 multiplier *= getNumEventCodes(dimension); 146 } 147 return result; 148 } 149 150 /** 151 * Uniquely map a `valueIndex`, `eventVectorIndex` pair to a single index. 152 * 153 * <p>If `valueIndex` is the result of a call to doubleToIndex() with numIndexPoints = 154 * `numIndexPoints`, then the returned index is in the range [0, ((`maxEventVectorIndex` + 1) * 155 * `numIndexPoints`) - 1]. 156 * 157 * @param valueIndex the value's index to encode 158 * @param eventVectorIndex the event vector's index to encode 159 * @param maxEventVectorIndex the maximum event vector index 160 * @return a single index 161 */ valueAndEventVectorIndicesToIndex( int valueIndex, int eventVectorIndex, int maxEventVectorIndex)162 static int valueAndEventVectorIndicesToIndex( 163 int valueIndex, int eventVectorIndex, int maxEventVectorIndex) { 164 return valueIndex * (maxEventVectorIndex + 1) + eventVectorIndex; 165 } 166 eventCodeToIndexForDimension(int eventCode, MetricDimension dimension)167 private static int eventCodeToIndexForDimension(int eventCode, MetricDimension dimension) { 168 // If dimension has a max_event_code, just use the eventCode. 169 if (dimension.getMaxEventCode() != 0) { 170 if (eventCode > dimension.getMaxEventCode()) { 171 throw new PrivacyGenerationException( 172 String.format( 173 "event_code %s is larger than max_event_code %s", 174 eventCode, dimension.getMaxEventCode())); 175 } 176 return eventCode; 177 } 178 // Otherwise, find the index of eventCode in the sorted list of enumerated event codes. 179 int[] dimensionEventCodes = getSortedEnumeratedEventCodes(dimension); 180 for (int i = 0; i < dimensionEventCodes.length; i++) { 181 if (eventCode == dimensionEventCodes[i]) { 182 return i; 183 } 184 } 185 throw new PrivacyGenerationException( 186 String.format( 187 "event_code %s was not found in the dimension's event codes", eventCode)); 188 } 189 getSortedEnumeratedEventCodes(MetricDimension dimension)190 private static int[] getSortedEnumeratedEventCodes(MetricDimension dimension) { 191 Set<Integer> eventCodesSet = dimension.getEventCodesMap().keySet(); 192 int[] eventCodes = new int[eventCodesSet.size()]; 193 194 int index = 0; 195 for (Integer eventCode : eventCodesSet) { 196 eventCodes[index++] = eventCode; 197 } 198 199 Arrays.sort(eventCodes); 200 return eventCodes; 201 } 202 getNumEventCodes(MetricDimension dimension)203 private static int getNumEventCodes(MetricDimension dimension) { 204 if (dimension.getMaxEventCode() != 0) { 205 return dimension.getMaxEventCode() + 1; 206 } 207 return dimension.getEventCodesCount(); 208 } 209 } 210