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.topics; 18 19 import android.annotation.NonNull; 20 import android.database.sqlite.SQLiteDatabase; 21 import android.os.Build; 22 import android.text.TextUtils; 23 import android.util.Pair; 24 25 import androidx.annotation.Nullable; 26 import androidx.annotation.RequiresApi; 27 28 import com.android.adservices.LoggerFactory; 29 import com.android.adservices.data.DbHelper; 30 import com.android.adservices.data.topics.EncryptedTopic; 31 import com.android.adservices.data.topics.Topic; 32 import com.android.adservices.data.topics.TopicsDao; 33 import com.android.adservices.data.topics.TopicsTables; 34 import com.android.adservices.errorlogging.ErrorLogUtil; 35 import com.android.adservices.service.Flags; 36 import com.android.adservices.service.FlagsFactory; 37 import com.android.adservices.service.stats.AdServicesLogger; 38 import com.android.adservices.service.stats.AdServicesLoggerImpl; 39 import com.android.adservices.service.stats.AdServicesStatsLog; 40 import com.android.adservices.service.stats.TopicsEncryptionEpochComputationReportedStats; 41 import com.android.adservices.service.topics.classifier.Classifier; 42 import com.android.adservices.service.topics.classifier.ClassifierManager; 43 import com.android.adservices.shared.util.Clock; 44 import com.android.internal.annotations.GuardedBy; 45 import com.android.internal.annotations.VisibleForTesting; 46 import com.android.internal.util.Preconditions; 47 48 import java.io.PrintWriter; 49 import java.time.Instant; 50 import java.util.HashMap; 51 import java.util.HashSet; 52 import java.util.List; 53 import java.util.Map; 54 import java.util.Objects; 55 import java.util.Optional; 56 import java.util.Random; 57 import java.util.Set; 58 59 /** A class to manage Epoch computation. */ 60 @RequiresApi(Build.VERSION_CODES.S) 61 public class EpochManager { 62 private static final LoggerFactory.Logger sLogger = LoggerFactory.getTopicsLogger(); 63 // The tables to do garbage collection for old epochs 64 // and its corresponding epoch_id column name. 65 // Pair<Table Name, Column Name> 66 private static final Pair<String, String>[] TABLE_INFO_FOR_EPOCH_GARBAGE_COLLECTION = 67 new Pair[] { 68 Pair.create( 69 TopicsTables.AppClassificationTopicsContract.TABLE, 70 TopicsTables.AppClassificationTopicsContract.EPOCH_ID), 71 Pair.create( 72 TopicsTables.TopTopicsContract.TABLE, 73 TopicsTables.TopTopicsContract.EPOCH_ID), 74 Pair.create( 75 TopicsTables.ReturnedTopicContract.TABLE, 76 TopicsTables.ReturnedTopicContract.EPOCH_ID), 77 Pair.create( 78 TopicsTables.UsageHistoryContract.TABLE, 79 TopicsTables.UsageHistoryContract.EPOCH_ID), 80 Pair.create( 81 TopicsTables.AppUsageHistoryContract.TABLE, 82 TopicsTables.AppUsageHistoryContract.EPOCH_ID), 83 Pair.create( 84 TopicsTables.TopicContributorsContract.TABLE, 85 TopicsTables.TopicContributorsContract.EPOCH_ID) 86 }; 87 88 /** 89 * The string to annotate that the topic is a padded topic in {@code TopicContributors} table. 90 * After the computation of {@code TopicContributors} table, if there is a top topic without 91 * contributors, it must be a padded topic. Persist {@code Entry{Topic, 92 * PADDED_TOP_TOPICS_STRING}} into {@code TopicContributors} table. 93 * 94 * <p>The reason to persist {@code Entry{Topic, PADDED_TOP_TOPICS_STRING}} is because topics 95 * need to be assigned to newly installed app. Moreover, non-random top topics without 96 * contributors, due to app uninstallations, are filtered out as candidate topics to assign 97 * with. Generally, a padded topic should have no contributors, but it should NOT be filtered 98 * out as a non-random top topics without contributors. Based on these facts, {@code 99 * Entry{Topic, PADDED_TOP_TOPICS_STRING}} is persisted to annotate that do NOT remove this 100 * padded topic though it has no contributors. 101 * 102 * <p>Put a "!" at last to avoid a spoof app to name itself with {@code 103 * PADDED_TOP_TOPICS_STRING}. Refer to 104 * https://developer.android.com/studio/build/configure-app-module, application name can only 105 * contain [a-zA-Z0-9_]. 106 */ 107 @VisibleForTesting 108 public static final String PADDED_TOP_TOPICS_STRING = "no_contributors_due_to_padding!"; 109 110 private static final Object SINGLETON_LOCK = new Object(); 111 112 @GuardedBy("SINGLETON_LOCK") 113 private static EpochManager sSingleton; 114 115 private final TopicsDao mTopicsDao; 116 private final DbHelper mDbHelper; 117 private final Random mRandom; 118 private final Classifier mClassifier; 119 private final Flags mFlags; 120 // Use Clock.getInstance() except in unit tests, which pass in a local instance of Clock to 121 // mock. 122 private final Clock mClock; 123 private final ClassifierManager mClassifierManager; 124 private final EncryptionManager mEncryptionManager; 125 private final AdServicesLogger mAdServicesLogger; 126 127 @VisibleForTesting EpochManager( @onNull TopicsDao topicsDao, @NonNull DbHelper dbHelper, @NonNull Random random, @NonNull Classifier classifier, Flags flags, @NonNull Clock clock, @NonNull ClassifierManager classifierManager, @NonNull EncryptionManager encryptionManager, @NonNull AdServicesLogger adServicesLogger)128 EpochManager( 129 @NonNull TopicsDao topicsDao, 130 @NonNull DbHelper dbHelper, 131 @NonNull Random random, 132 @NonNull Classifier classifier, 133 Flags flags, 134 @NonNull Clock clock, 135 @NonNull ClassifierManager classifierManager, 136 @NonNull EncryptionManager encryptionManager, 137 @NonNull AdServicesLogger adServicesLogger) { 138 mTopicsDao = topicsDao; 139 mDbHelper = dbHelper; 140 mRandom = random; 141 mClassifier = classifier; 142 mFlags = flags; 143 mClock = clock; 144 mClassifierManager = classifierManager; 145 mEncryptionManager = encryptionManager; 146 mAdServicesLogger = adServicesLogger; 147 } 148 149 /** Returns an instance of the EpochManager given a context. */ 150 @NonNull getInstance()151 public static EpochManager getInstance() { 152 synchronized (SINGLETON_LOCK) { 153 if (sSingleton == null) { 154 sSingleton = 155 new EpochManager( 156 TopicsDao.getInstance(), 157 DbHelper.getInstance(), 158 new Random(), 159 ClassifierManager.getInstance(), 160 FlagsFactory.getFlags(), 161 Clock.getInstance(), 162 ClassifierManager.getInstance(), 163 EncryptionManager.getInstance(), 164 AdServicesLoggerImpl.getInstance()); 165 } 166 return sSingleton; 167 } 168 } 169 170 /** Offline Epoch Processing. For more details, see go/rb-topics-epoch-computation */ processEpoch()171 public void processEpoch() { 172 SQLiteDatabase db = mDbHelper.safeGetWritableDatabase(); 173 if (db == null) { 174 return; 175 } 176 177 // This cross db and java boundaries multiple times, so we need to have a db transaction. 178 sLogger.d("Start of Epoch Computation"); 179 db.beginTransaction(); 180 181 long currentEpochId = getCurrentEpochId(); 182 sLogger.d("EpochManager.processEpoch for the current epochId %d", currentEpochId); 183 184 try { 185 // Step 0: erase outdated epoch's data, i.e. epoch earlier than 186 // (currentEpoch - numberOfLookBackEpochs) (inclusive) 187 garbageCollectOutdatedEpochData(currentEpochId); 188 189 // Step 1: Compute the UsageMap from the UsageHistory table. 190 // appSdksUsageMap = Map<App, List<SDK>> has the app and its SDKs that called Topics API 191 // in the current Epoch. 192 Map<String, List<String>> appSdksUsageMap = 193 mTopicsDao.retrieveAppSdksUsageMap(currentEpochId); 194 sLogger.v("appSdksUsageMap size is %d", appSdksUsageMap.size()); 195 196 // Step 2: Compute the Map from App to its classification topics. 197 // Only produce for apps that called the Topics API in the current Epoch. 198 // appClassificationTopicsMap = Map<App, List<Topics>> 199 Map<String, List<Topic>> appClassificationTopicsMap = 200 mClassifier.classify(appSdksUsageMap.keySet()); 201 sLogger.v("appClassificationTopicsMap size is %d", appClassificationTopicsMap.size()); 202 203 // Then save app-topics Map into DB 204 mTopicsDao.persistAppClassificationTopics(currentEpochId, appClassificationTopicsMap); 205 206 // Step 3: Compute the Callers can learn map for this epoch. 207 // This is similar to the Callers Can Learn table in the explainer. 208 Map<Topic, Set<String>> callersCanLearnThisEpochMap = 209 computeCallersCanLearnMap(appSdksUsageMap, appClassificationTopicsMap); 210 sLogger.v( 211 "callersCanLearnThisEpochMap size is %d", callersCanLearnThisEpochMap.size()); 212 213 // And then save this CallersCanLearnMap to DB. 214 mTopicsDao.persistCallerCanLearnTopics(currentEpochId, callersCanLearnThisEpochMap); 215 216 // Step 4: For each topic, retrieve the callers (App or SDK) that can learn about that 217 // topic. We look at last 3 epochs. More specifically, epochs in 218 // [currentEpochId - 2, currentEpochId]. (inclusive) 219 // Return callersCanLearnMap = Map<Topic, Set<Caller>> where Caller = App or Sdk. 220 Map<Topic, Set<String>> callersCanLearnMap = 221 mTopicsDao.retrieveCallerCanLearnTopicsMap( 222 currentEpochId, mFlags.getTopicsNumberOfLookBackEpochs()); 223 sLogger.v("callersCanLearnMap size is %d", callersCanLearnMap.size()); 224 225 // Step 5: Retrieve the Top Topics. This will return a list of 5 top topics and 226 // the 6th topic which is selected randomly. We can refer this 6th topic as the 227 // random-topic. 228 List<Topic> topTopics = 229 mClassifier.getTopTopics( 230 appClassificationTopicsMap, 231 mFlags.getTopicsNumberOfTopTopics(), 232 mFlags.getTopicsNumberOfRandomTopics()); 233 // Abort the computation if empty list of top topics is returned from classifier. 234 // This could happen if there is no usage of the Topics API in the last epoch. 235 if (topTopics.isEmpty()) { 236 sLogger.w( 237 "Empty list of top topics is returned from classifier. Aborting the" 238 + " computation!"); 239 db.setTransactionSuccessful(); 240 return; 241 } 242 sLogger.v("topTopics are %s", topTopics.toString()); 243 244 // Then save Top Topics into DB 245 mTopicsDao.persistTopTopics(currentEpochId, topTopics); 246 247 // Compute TopicToContributors mapping for top topics. In an epoch, an app is a 248 // contributor to a topic if the app has called Topics API in this epoch and is 249 // classified to the topic. 250 // Do this only when feature is enabled. 251 Map<Integer, Set<String>> topTopicsToContributorsMap = 252 computeTopTopicsToContributorsMap(appClassificationTopicsMap, topTopics); 253 // Then save Topic Contributors into DB 254 mTopicsDao.persistTopicContributors(currentEpochId, topTopicsToContributorsMap); 255 256 // Step 6: Assign topics to apps and SDK from the global top topics. 257 // Currently, hard-code the taxonomyVersion and the modelVersion. 258 // Return returnedAppSdkTopics = Map<Pair<App, Sdk>, Topic> 259 Map<Pair<String, String>, Topic> returnedAppSdkTopics = 260 computeReturnedAppSdkTopics(callersCanLearnMap, appSdksUsageMap, topTopics); 261 int countOfTopicsBeforeEncryption = returnedAppSdkTopics.size(); 262 sLogger.v("returnedAppSdkTopics size is %d", countOfTopicsBeforeEncryption); 263 264 // And persist the map to DB so that we can reuse later. 265 mTopicsDao.persistReturnedAppTopicsMap(currentEpochId, returnedAppSdkTopics); 266 267 int countOfEncryptedTopics = 0; 268 int latencyOfWholeEncryptionProcessMs = 0; 269 int latencyOfPersistingEncryptedTopicsToDbMs = 0; 270 // Encrypt and store encrypted topics if the feature is enabled and the version 9 db 271 // is available. 272 if (mFlags.getTopicsEncryptionEnabled() && mFlags.getEnableDatabaseSchemaVersion9()) { 273 long topicsEncryptionStartTimestamp = mClock.currentTimeMillis(); 274 // encryptedTopicMapTopics = Map<Pair<App, Sdk>, EncryptedTopic> 275 Map<Pair<String, String>, EncryptedTopic> encryptedTopicMapTopics = 276 encryptTopicsMap(returnedAppSdkTopics); 277 if (mFlags.getTopicsEncryptionMetricsEnabled()) { 278 latencyOfWholeEncryptionProcessMs = 279 (int) (mClock.currentTimeMillis() - topicsEncryptionStartTimestamp); 280 } 281 countOfEncryptedTopics = encryptedTopicMapTopics.size(); 282 sLogger.v("encryptedTopicMapTopics size is %d", countOfEncryptedTopics); 283 284 long persistEncryptedTopicsToDbStartTimestamp = mClock.currentTimeMillis(); 285 mTopicsDao.persistReturnedAppEncryptedTopicsMap( 286 currentEpochId, encryptedTopicMapTopics); 287 if (mFlags.getTopicsEncryptionMetricsEnabled()) { 288 latencyOfPersistingEncryptedTopicsToDbMs = 289 (int) (mClock.currentTimeMillis() 290 - persistEncryptedTopicsToDbStartTimestamp); 291 } 292 } 293 294 if (mFlags.getTopicsEncryptionMetricsEnabled()) { 295 int latencyOfEncryptionPerTopicMs = 296 countOfTopicsBeforeEncryption == 0 297 ? 0 298 : latencyOfWholeEncryptionProcessMs / countOfTopicsBeforeEncryption; 299 mAdServicesLogger.logTopicsEncryptionEpochComputationReportedStats( 300 TopicsEncryptionEpochComputationReportedStats.builder() 301 .setCountOfTopicsBeforeEncryption(countOfTopicsBeforeEncryption) 302 .setCountOfEmptyEncryptedTopics( 303 countOfTopicsBeforeEncryption - countOfEncryptedTopics) 304 .setCountOfEncryptedTopics(countOfEncryptedTopics) 305 .setLatencyOfWholeEncryptionProcessMs( 306 latencyOfWholeEncryptionProcessMs) 307 .setLatencyOfEncryptionPerTopicMs(latencyOfEncryptionPerTopicMs) 308 .setLatencyOfPersistingEncryptedTopicsToDbMs( 309 latencyOfPersistingEncryptedTopicsToDbMs) 310 .build() 311 ); 312 } 313 314 // Mark the transaction successful. 315 db.setTransactionSuccessful(); 316 } finally { 317 db.endTransaction(); 318 sLogger.d("End of Epoch Computation"); 319 } 320 } 321 322 /** 323 * Record the call from App and Sdk to usage history. This UsageHistory will be used to 324 * determine if a caller (app or sdk) has observed a topic before. 325 * 326 * @param app the app 327 * @param sdk the sdk of the app. In case the app calls the Topics API directly, the sdk == 328 * empty string. 329 */ recordUsageHistory(String app, String sdk)330 public void recordUsageHistory(String app, String sdk) { 331 long epochId = getCurrentEpochId(); 332 // TODO(b/223159123): Do we need to filter out this log in prod build? 333 sLogger.v( 334 "EpochManager.recordUsageHistory for current EpochId = %d for %s, %s", 335 epochId, app, sdk); 336 mTopicsDao.recordUsageHistory(epochId, app, sdk); 337 mTopicsDao.recordAppUsageHistory(epochId, app); 338 } 339 340 /** 341 * Determine the learn-ability of a topic to a certain caller. 342 * 343 * @param topic the topic to check the learn-ability 344 * @param caller the caller to check whether it can learn the given topic 345 * @param callersCanLearnMap the map that stores topic->caller mapping which shows a topic can 346 * be learnt by a caller 347 * @param topTopics a {@link List} of top topics 348 * @param numberOfTopTopics number of regular topics in top topics 349 * @return a {@code boolean} that indicates if the caller can learn the topic 350 */ 351 // TODO(b/236834213): Create a class for Top Topics isTopicLearnableByCaller( @onNull Topic topic, @NonNull String caller, @NonNull Map<Topic, Set<String>> callersCanLearnMap, @NonNull List<Topic> topTopics, int numberOfTopTopics)352 public static boolean isTopicLearnableByCaller( 353 @NonNull Topic topic, 354 @NonNull String caller, 355 @NonNull Map<Topic, Set<String>> callersCanLearnMap, 356 @NonNull List<Topic> topTopics, 357 int numberOfTopTopics) { 358 // If a topic is the random topic in top topic list, it can be learnt by any caller. 359 int index = topTopics.lastIndexOf(topic); 360 // Regular top topics are placed in the front of the list. Topics after are random topics. 361 if (index >= numberOfTopTopics) { 362 return true; 363 } 364 365 return callersCanLearnMap.containsKey(topic) 366 && callersCanLearnMap.get(topic).contains(caller); 367 } 368 369 /** 370 * Get the ID of current epoch. 371 * 372 * <p>The origin's timestamp is saved in the database. If the origin doesn't exist, it means the 373 * user never calls Topics API and the origin will be returned with -1. In this case, set 374 * current time as origin and persist it into database. 375 * 376 * @return a non-negative epoch ID of current epoch. 377 */ 378 // TODO(b/237119788): Cache origin in cache manager. 379 // TODO(b/237119790): Set origin to sometime after midnight to get better maintenance timing. getCurrentEpochId()380 public long getCurrentEpochId() { 381 long origin = mTopicsDao.retrieveEpochOrigin(); 382 long currentTimeStamp = mClock.currentTimeMillis(); 383 long epochJobPeriodsMs = mFlags.getTopicsEpochJobPeriodMs(); 384 385 // If origin doesn't exist in database, set current timestamp as origin. 386 if (origin == -1) { 387 origin = currentTimeStamp; 388 mTopicsDao.persistEpochOrigin(origin); 389 sLogger.d( 390 "Origin isn't found! Set current time %s as origin.", 391 Instant.ofEpochMilli(origin).toString()); 392 } 393 394 long currentEpochId = 395 (long) Math.floor((currentTimeStamp - origin) / (double) epochJobPeriodsMs); 396 sLogger.v( 397 "Current Epoch ID is %d, Epoch length is %d, retrieved Epoch origin as %d", 398 currentEpochId, epochJobPeriodsMs, origin); 399 return currentEpochId; 400 } 401 402 // Return a Map from Topic to set of App or Sdk that can learn about that topic. 403 // This is similar to the table Can Learn Topic in the explainer. 404 // Return Map<Topic, Set<Caller>> where Caller = App or Sdk. 405 @VisibleForTesting 406 @NonNull computeCallersCanLearnMap( @onNull Map<String, List<String>> appSdksUsageMap, @NonNull Map<String, List<Topic>> appClassificationTopicsMap)407 static Map<Topic, Set<String>> computeCallersCanLearnMap( 408 @NonNull Map<String, List<String>> appSdksUsageMap, 409 @NonNull Map<String, List<Topic>> appClassificationTopicsMap) { 410 Objects.requireNonNull(appSdksUsageMap); 411 Objects.requireNonNull(appClassificationTopicsMap); 412 413 // Map from Topic to set of App or Sdk that can learn about that topic. 414 // This is similar to the table Can Learn Topic in the explainer. 415 // Map<Topic, Set<Caller>> where Caller = App or Sdk. 416 Map<Topic, Set<String>> callersCanLearnMap = new HashMap<>(); 417 418 for (Map.Entry<String, List<Topic>> entry : appClassificationTopicsMap.entrySet()) { 419 String app = entry.getKey(); 420 List<Topic> appTopics = entry.getValue(); 421 if (appTopics == null) { 422 sLogger.e("Can't find the Classification Topics for app = " + app); 423 continue; 424 } 425 426 for (Topic topic : appTopics) { 427 if (!callersCanLearnMap.containsKey(topic)) { 428 callersCanLearnMap.put(topic, new HashSet<>()); 429 } 430 431 // All SDKs in the app can learn this topic too. 432 for (String sdk : appSdksUsageMap.get(app)) { 433 if (TextUtils.isEmpty(sdk)) { 434 // Empty sdk means the app called the Topics API directly. 435 // Caller = app 436 // Then the app can learn its topic. 437 callersCanLearnMap.get(topic).add(app); 438 } else { 439 // Caller = sdk 440 callersCanLearnMap.get(topic).add(sdk); 441 } 442 } 443 } 444 } 445 446 return callersCanLearnMap; 447 } 448 449 // Encrypts Topic to corresponding EncryptedTopic. 450 // Map<Pair<App, Sdk>, EncryptedTopic> encryptTopicsMap( Map<Pair<String, String>, Topic> unencryptedMap)451 private Map<Pair<String, String>, EncryptedTopic> encryptTopicsMap( 452 Map<Pair<String, String>, Topic> unencryptedMap) { 453 Map<Pair<String, String>, EncryptedTopic> encryptedTopicMap = new HashMap<>(); 454 for (Map.Entry<Pair<String, String>, Topic> entry : unencryptedMap.entrySet()) { 455 Optional<EncryptedTopic> optionalEncryptedTopic = 456 mEncryptionManager.encryptTopic( 457 /* Topic */ entry.getValue(), /* sdkName */ entry.getKey().second); 458 if (optionalEncryptedTopic.isPresent()) { 459 encryptedTopicMap.put(entry.getKey(), optionalEncryptedTopic.get()); 460 } else { 461 ErrorLogUtil.e( 462 AdServicesStatsLog 463 .AD_SERVICES_ERROR_REPORTED__ERROR_CODE__TOPICS_ENCRYPTION_FAILURE, 464 AdServicesStatsLog.AD_SERVICES_ERROR_REPORTED__PPAPI_NAME__TOPICS); 465 sLogger.d( 466 "Failed to encrypt %s for (%s, %s) caller.", 467 entry.getValue(), entry.getKey().first, entry.getKey().second); 468 } 469 } 470 return encryptedTopicMap; 471 } 472 473 // Inputs: 474 // callersCanLearnMap = Map<Topic, Set<Caller>> map from topic to set of callers that can learn 475 // about the topic. Caller = App or Sdk. 476 // appSdksUsageMap = Map<App, List<SDK>> has the app and its SDKs that called Topics API 477 // in the current Epoch. 478 // topTopics = List<Topic> list of top 5 topics and 1 random topic. 479 // 480 // Return returnedAppSdkTopics = Map<Pair<App, Sdk>, Topic> 481 @VisibleForTesting 482 @NonNull computeReturnedAppSdkTopics( @onNull Map<Topic, Set<String>> callersCanLearnMap, @NonNull Map<String, List<String>> appSdksUsageMap, @NonNull List<Topic> topTopics)483 Map<Pair<String, String>, Topic> computeReturnedAppSdkTopics( 484 @NonNull Map<Topic, Set<String>> callersCanLearnMap, 485 @NonNull Map<String, List<String>> appSdksUsageMap, 486 @NonNull List<Topic> topTopics) { 487 Map<Pair<String, String>, Topic> returnedAppSdkTopics = new HashMap<>(); 488 489 for (Map.Entry<String, List<String>> appSdks : appSdksUsageMap.entrySet()) { 490 Topic returnedTopic = selectRandomTopic(topTopics); 491 if(mFlags.getEnableLoggedTopic() 492 && mTopicsDao.supportsLoggedTopicInReturnedTopicTable()) { 493 returnedTopic = 494 Topic.create( 495 returnedTopic.getTopic(), 496 returnedTopic.getTaxonomyVersion(), 497 returnedTopic.getModelVersion(), 498 getTopicIdForLogging(returnedTopic)); 499 } 500 501 String app = appSdks.getKey(); 502 503 // Check if the app can learn this topic. 504 if (isTopicLearnableByCaller( 505 returnedTopic, 506 app, 507 callersCanLearnMap, 508 topTopics, 509 mFlags.getTopicsNumberOfTopTopics())) { 510 // The app calls Topics API directly. In this case, we set the sdk == empty string. 511 returnedAppSdkTopics.put(Pair.create(app, /* empty Sdk */ ""), returnedTopic); 512 // TODO(b/223159123): Do we need to filter out this log in prod build? 513 sLogger.v( 514 "CacheManager.computeReturnedAppSdkTopics. Topic %s is returned for" 515 + " %s", 516 returnedTopic, app); 517 } 518 519 // Then check all SDKs of the app. 520 for (String sdk : appSdks.getValue()) { 521 if (isTopicLearnableByCaller( 522 returnedTopic, 523 sdk, 524 callersCanLearnMap, 525 topTopics, 526 mFlags.getTopicsNumberOfTopTopics())) { 527 returnedAppSdkTopics.put(Pair.create(app, sdk), returnedTopic); 528 // TODO(b/223159123): Do we need to filter out this log in prod build? 529 sLogger.v( 530 "CacheManager.computeReturnedAppSdkTopics. Topic %s is returned" 531 + " for %s, %s", 532 returnedTopic, app, sdk); 533 } 534 } 535 } 536 537 return returnedAppSdkTopics; 538 } 539 540 // Return a random topics from the Top Topics. 541 // The Top Topics include the Top 5 Topics and one random topic from the Taxonomy. 542 @VisibleForTesting 543 @NonNull selectRandomTopic(List<Topic> topTopics)544 Topic selectRandomTopic(List<Topic> topTopics) { 545 Preconditions.checkArgument( 546 topTopics.size() 547 == mFlags.getTopicsNumberOfTopTopics() 548 + mFlags.getTopicsNumberOfRandomTopics()); 549 int random = mRandom.nextInt(100); 550 551 // First random topic would be after numberOfTopTopics. 552 int randomTopicIndex = mFlags.getTopicsNumberOfTopTopics(); 553 // For 5%, get the random topic. 554 if (random < mFlags.getTopicsPercentageForRandomTopic()) { 555 // The random topic is the last one on the list. 556 return topTopics.get(randomTopicIndex); 557 } 558 559 // For 95%, pick randomly one out of first n top topics. 560 return topTopics.get(random % randomTopicIndex); 561 } 562 563 // To garbage collect data for old epochs. 564 @VisibleForTesting garbageCollectOutdatedEpochData(long currentEpochID)565 void garbageCollectOutdatedEpochData(long currentEpochID) { 566 int epochLookBackNumberForGarbageCollection = mFlags.getNumberOfEpochsToKeepInHistory(); 567 // Assume current Epoch is T, and the earliest epoch should be kept is T-3 568 // Then any epoch data older than T-3-1 = T-4, including T-4 should be deleted. 569 long epochToDeleteFrom = currentEpochID - epochLookBackNumberForGarbageCollection - 1; 570 // To do garbage collection for each table 571 for (Pair<String, String> tableColumnPair : TABLE_INFO_FOR_EPOCH_GARBAGE_COLLECTION) { 572 mTopicsDao.deleteDataOfOldEpochs( 573 tableColumnPair.first, tableColumnPair.second, epochToDeleteFrom); 574 } 575 576 if (mFlags.getEnableDatabaseSchemaVersion9()) { 577 // Delete data from ReturnedEncryptedTopic table. 578 mTopicsDao.deleteDataOfOldEpochs( 579 TopicsTables.ReturnedEncryptedTopicContract.TABLE, 580 TopicsTables.ReturnedEncryptedTopicContract.EPOCH_ID, 581 epochToDeleteFrom); 582 } 583 584 // In app installation, we need to assign topics to newly installed app-sdk caller. In order 585 // to check topic learnability of the sdk, CallerCanLearnTopicsContract needs to persist 586 // numberOfLookBackEpochs more epochs. For example, assume current epoch is T. In app 587 // installation, topics will be assigned to T-1, T-2 and T-3. In order to check learnability 588 // at Epoch T-3, we need to check CallerCanLearnTopicsContract of epoch T-4, T-5 and T-6. 589 long epochToDeleteFromForCallerCanLearn = 590 currentEpochID - epochLookBackNumberForGarbageCollection * 2L - 1; 591 mTopicsDao.deleteDataOfOldEpochs( 592 TopicsTables.CallerCanLearnTopicsContract.TABLE, 593 TopicsTables.CallerCanLearnTopicsContract.EPOCH_ID, 594 epochToDeleteFromForCallerCanLearn); 595 } 596 597 // Compute the mapping of topic to its contributor apps. In an epoch, an app is a contributor to 598 // a topic if the app has called Topics API in this epoch and is classified to the topic. Only 599 // computed for top topics. 600 @VisibleForTesting computeTopTopicsToContributorsMap( @onNull Map<String, List<Topic>> appClassificationTopicsMap, @NonNull List<Topic> topTopics)601 Map<Integer, Set<String>> computeTopTopicsToContributorsMap( 602 @NonNull Map<String, List<Topic>> appClassificationTopicsMap, 603 @NonNull List<Topic> topTopics) { 604 Map<Integer, Set<String>> topicToContributorMap = new HashMap<>(); 605 606 for (Map.Entry<String, List<Topic>> appTopics : appClassificationTopicsMap.entrySet()) { 607 String app = appTopics.getKey(); 608 609 for (Topic topic : appTopics.getValue()) { 610 // Only compute for top topics. 611 if (topTopics.contains(topic)) { 612 int topicId = topic.getTopic(); 613 topicToContributorMap.putIfAbsent(topicId, new HashSet<>()); 614 topicToContributorMap.get(topicId).add(app); 615 } 616 } 617 } 618 619 // At last, check whether there is any top topics without contributors. If so, annotate it 620 // with PADDED_TOP_TOPICS_STRING in the map. See PADDED_TOP_TOPICS_STRING for more details. 621 for (int i = 0; i < mFlags.getTopicsNumberOfTopTopics(); i++) { 622 Topic topTopic = topTopics.get(i); 623 topicToContributorMap.putIfAbsent( 624 topTopic.getTopic(), Set.of(PADDED_TOP_TOPICS_STRING)); 625 } 626 627 return topicToContributorMap; 628 } 629 dump(@onNull PrintWriter writer, @Nullable String[] args)630 public void dump(@NonNull PrintWriter writer, @Nullable String[] args) { 631 writer.println("==== EpochManager Dump ===="); 632 long epochId = getCurrentEpochId(); 633 writer.println(String.format("Current epochId is %d", epochId)); 634 } 635 636 // Gets a topic ID for logging from the given topic using randomized response mechanism. 637 @VisibleForTesting getTopicIdForLogging(Topic topic)638 int getTopicIdForLogging(Topic topic) { 639 List<Integer> topicsTaxonomy = mClassifierManager.getTopicsTaxonomy(); 640 641 // Probability of logging real vs. random topic: 642 // Real topic: e^privacyBudget / (e^privacyBudget + taxonomySize - 1) 643 // Random topic: (taxonomySize - 1) / (e^privacyBudget + taxonomySize - 1) 644 double expPrivacyBudget = Math.exp(mFlags.getTopicsPrivacyBudgetForTopicIdDistribution()); 645 int taxonomySize = topicsTaxonomy.size(); 646 double pRandomization = 647 expPrivacyBudget == Double.POSITIVE_INFINITY 648 ? 0d 649 : (taxonomySize - 1d) / (expPrivacyBudget + taxonomySize - 1d); 650 651 int topicId = topic.getTopic(); 652 653 // In order to prevent select a random topic from being stuck in a loop, 654 // return the topic directly if taxonomy size is 0 or 1. 655 if (taxonomySize <= 1) { 656 return topicId; 657 } 658 659 if (mRandom.nextDouble() < pRandomization) { 660 // Log a random topic ID other than the real one. 661 int randomTopicId = topicId; 662 663 // Set a maximum attempts to prevent select a random topic from being stuck in the loop. 664 int maxAttempts = 5; 665 666 while (randomTopicId == topicId && maxAttempts-- > 0) { 667 randomTopicId = topicsTaxonomy.get(mRandom.nextInt(taxonomySize)); 668 } 669 670 return randomTopicId; 671 } else { 672 return topicId; 673 } 674 } 675 } 676