1 /*
2  * Copyright (C) 2022 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.adservices.service.measurement.noising;
18 
19 import com.android.adservices.service.measurement.TriggerSpecs;
20 import com.android.internal.annotations.VisibleForTesting;
21 
22 import java.util.ArrayList;
23 import java.util.List;
24 import java.util.concurrent.ThreadLocalRandom;
25 
26 /**
27  * Util class for generating impression noise
28  */
29 public final class ImpressionNoiseUtil {
30 
ImpressionNoiseUtil()31     private ImpressionNoiseUtil() {}
32 
33     /**
34      * Randomly generate report configs based on noise params
35      *
36      * @param noiseParams Noise parameters to use for state generation
37      * @param rand random number generator
38      * @return list of reporting configs
39      */
selectRandomStateAndGenerateReportConfigs( ImpressionNoiseParams noiseParams, ThreadLocalRandom rand)40     public static List<int[]> selectRandomStateAndGenerateReportConfigs(
41             ImpressionNoiseParams noiseParams, ThreadLocalRandom rand) {
42         // Get total possible combinations
43         long numCombinations =
44                 Combinatorics.getNumberOfStarsAndBarsSequences(
45                         /*numStars=*/ noiseParams.getReportCount(),
46                         /*numBars=*/ noiseParams.getTriggerDataCardinality()
47                                 * noiseParams.getReportingWindowCount()
48                                 * noiseParams.getDestinationTypeMultiplier());
49         // Choose a sequence index
50         long sequenceIndex = nextLong(rand, numCombinations);
51         return getReportConfigsForSequenceIndex(noiseParams, sequenceIndex);
52     }
53 
54     @VisibleForTesting
getReportConfigsForSequenceIndex( ImpressionNoiseParams noiseParams, long sequenceIndex)55     static List<int[]> getReportConfigsForSequenceIndex(
56             ImpressionNoiseParams noiseParams, long sequenceIndex) {
57         List<int[]> reportConfigs = new ArrayList<>();
58         // Get the configuration for the sequenceIndex
59         long[] starIndices = Combinatorics.getStarIndices(
60                 /*numStars=*/noiseParams.getReportCount(),
61                 /*sequenceIndex=*/sequenceIndex);
62         long[] barsPrecedingEachStar = Combinatorics.getBarsPrecedingEachStar(starIndices);
63         // Generate fake reports
64         // Stars: number of reports
65         // Bars: (Number of windows) * (Trigger data cardinality) * (Destination multiplier)
66         for (long numBars : barsPrecedingEachStar) {
67             if (numBars == 0L) {
68                 continue;
69             }
70 
71             // Extract bits for trigger data, destination type and windowIndex from encoded numBars
72             int[] reportConfig = createReportingConfig(numBars, noiseParams);
73             reportConfigs.add(reportConfig);
74         }
75         return reportConfigs;
76     }
77 
78     /**
79      * Extract bits for trigger data, destination type and windowIndex from encoded numBars.
80      *
81      * @param numBars data encoding triggerData, destinationType and window index
82      * @param noiseParams noise params
83      * @return array having triggerData, destinationType and windowIndex
84      */
createReportingConfig(long numBars, ImpressionNoiseParams noiseParams)85     private static int[] createReportingConfig(long numBars, ImpressionNoiseParams noiseParams) {
86         long triggerData = (numBars - 1L) % ((long) noiseParams.getTriggerDataCardinality());
87         long remainingData = (numBars - 1L) / ((long) noiseParams.getTriggerDataCardinality());
88 
89         int reportingWindowIndex = ((int) remainingData) % noiseParams.getReportingWindowCount();
90         int destinationTypeIndex = ((int) remainingData) / noiseParams.getReportingWindowCount();
91         return new int[] {(int) triggerData, reportingWindowIndex, destinationTypeIndex};
92     }
93 
94     /**
95      * Randomly generate report configs based on noise params
96      *
97      * @param triggerSpecs trigger specs to use for state generation
98      * @param destinationMultiplier destination multiplier
99      * @param rand random number generator
100      * @return list of reporting configs
101      */
selectFlexEventReportRandomStateAndGenerateReportConfigs( TriggerSpecs triggerSpecs, int destinationMultiplier, ThreadLocalRandom rand)102     public static List<int[]> selectFlexEventReportRandomStateAndGenerateReportConfigs(
103             TriggerSpecs triggerSpecs, int destinationMultiplier, ThreadLocalRandom rand) {
104 
105         // Assumes trigger specs already built privacy parameters.
106         int[][] params = triggerSpecs.getPrivacyParamsForComputation();
107         // Doubling the window cap for each trigger data type correlates with counting report states
108         // that treat having a web destination as different from an app destination.
109         int[] updatedPerTypeNumWindowList = new int[params[1].length];
110         for (int i = 0; i < params[1].length; i++) {
111             updatedPerTypeNumWindowList[i] = params[1][i] * destinationMultiplier;
112         }
113         long numStates =
114                 Combinatorics.getNumStatesFlexApi(
115                         params[0][0], updatedPerTypeNumWindowList, params[2], Long.MAX_VALUE);
116         long sequenceIndex = nextLong(rand, numStates);
117         List<Combinatorics.AtomReportState> rawFakeReports =
118                 Combinatorics.getReportSetBasedOnRank(
119                         params[0][0],
120                         updatedPerTypeNumWindowList,
121                         params[2],
122                         sequenceIndex);
123         List<int[]> fakeReportConfigs = new ArrayList<>();
124         for (Combinatorics.AtomReportState rawFakeReport : rawFakeReports) {
125             int[] fakeReportConfig = new int[3];
126             fakeReportConfig[0] = rawFakeReport.getTriggerDataType();
127             fakeReportConfig[1] = (rawFakeReport.getWindowIndex()) / destinationMultiplier;
128             fakeReportConfig[2] = (rawFakeReport.getWindowIndex()) % destinationMultiplier;
129             fakeReportConfigs.add(fakeReportConfig);
130         }
131         return fakeReportConfigs;
132     }
133 
134     /** Wrapper for calls to ThreadLocalRandom. Bound must be positive. */
135     @VisibleForTesting
nextLong(ThreadLocalRandom rand, long bound)136     public static long nextLong(ThreadLocalRandom rand, long bound) {
137         return rand.nextLong(bound);
138     }
139 }
140