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