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 sLogger.v("Epoch length is %d", epochJobPeriodsMs); 395 return (long) Math.floor((currentTimeStamp - origin) / (double) epochJobPeriodsMs); 396 } 397 398 // Return a Map from Topic to set of App or Sdk that can learn about that topic. 399 // This is similar to the table Can Learn Topic in the explainer. 400 // Return Map<Topic, Set<Caller>> where Caller = App or Sdk. 401 @VisibleForTesting 402 @NonNull computeCallersCanLearnMap( @onNull Map<String, List<String>> appSdksUsageMap, @NonNull Map<String, List<Topic>> appClassificationTopicsMap)403 static Map<Topic, Set<String>> computeCallersCanLearnMap( 404 @NonNull Map<String, List<String>> appSdksUsageMap, 405 @NonNull Map<String, List<Topic>> appClassificationTopicsMap) { 406 Objects.requireNonNull(appSdksUsageMap); 407 Objects.requireNonNull(appClassificationTopicsMap); 408 409 // Map from Topic to set of App or Sdk that can learn about that topic. 410 // This is similar to the table Can Learn Topic in the explainer. 411 // Map<Topic, Set<Caller>> where Caller = App or Sdk. 412 Map<Topic, Set<String>> callersCanLearnMap = new HashMap<>(); 413 414 for (Map.Entry<String, List<Topic>> entry : appClassificationTopicsMap.entrySet()) { 415 String app = entry.getKey(); 416 List<Topic> appTopics = entry.getValue(); 417 if (appTopics == null) { 418 sLogger.e("Can't find the Classification Topics for app = " + app); 419 continue; 420 } 421 422 for (Topic topic : appTopics) { 423 if (!callersCanLearnMap.containsKey(topic)) { 424 callersCanLearnMap.put(topic, new HashSet<>()); 425 } 426 427 // All SDKs in the app can learn this topic too. 428 for (String sdk : appSdksUsageMap.get(app)) { 429 if (TextUtils.isEmpty(sdk)) { 430 // Empty sdk means the app called the Topics API directly. 431 // Caller = app 432 // Then the app can learn its topic. 433 callersCanLearnMap.get(topic).add(app); 434 } else { 435 // Caller = sdk 436 callersCanLearnMap.get(topic).add(sdk); 437 } 438 } 439 } 440 } 441 442 return callersCanLearnMap; 443 } 444 445 // Encrypts Topic to corresponding EncryptedTopic. 446 // Map<Pair<App, Sdk>, EncryptedTopic> encryptTopicsMap( Map<Pair<String, String>, Topic> unencryptedMap)447 private Map<Pair<String, String>, EncryptedTopic> encryptTopicsMap( 448 Map<Pair<String, String>, Topic> unencryptedMap) { 449 Map<Pair<String, String>, EncryptedTopic> encryptedTopicMap = new HashMap<>(); 450 for (Map.Entry<Pair<String, String>, Topic> entry : unencryptedMap.entrySet()) { 451 Optional<EncryptedTopic> optionalEncryptedTopic = 452 mEncryptionManager.encryptTopic( 453 /* Topic */ entry.getValue(), /* sdkName */ entry.getKey().second); 454 if (optionalEncryptedTopic.isPresent()) { 455 encryptedTopicMap.put(entry.getKey(), optionalEncryptedTopic.get()); 456 } else { 457 ErrorLogUtil.e( 458 AdServicesStatsLog 459 .AD_SERVICES_ERROR_REPORTED__ERROR_CODE__TOPICS_ENCRYPTION_FAILURE, 460 AdServicesStatsLog.AD_SERVICES_ERROR_REPORTED__PPAPI_NAME__TOPICS); 461 sLogger.d( 462 "Failed to encrypt %s for (%s, %s) caller.", 463 entry.getValue(), entry.getKey().first, entry.getKey().second); 464 } 465 } 466 return encryptedTopicMap; 467 } 468 469 // Inputs: 470 // callersCanLearnMap = Map<Topic, Set<Caller>> map from topic to set of callers that can learn 471 // about the topic. Caller = App or Sdk. 472 // appSdksUsageMap = Map<App, List<SDK>> has the app and its SDKs that called Topics API 473 // in the current Epoch. 474 // topTopics = List<Topic> list of top 5 topics and 1 random topic. 475 // 476 // Return returnedAppSdkTopics = Map<Pair<App, Sdk>, Topic> 477 @VisibleForTesting 478 @NonNull computeReturnedAppSdkTopics( @onNull Map<Topic, Set<String>> callersCanLearnMap, @NonNull Map<String, List<String>> appSdksUsageMap, @NonNull List<Topic> topTopics)479 Map<Pair<String, String>, Topic> computeReturnedAppSdkTopics( 480 @NonNull Map<Topic, Set<String>> callersCanLearnMap, 481 @NonNull Map<String, List<String>> appSdksUsageMap, 482 @NonNull List<Topic> topTopics) { 483 Map<Pair<String, String>, Topic> returnedAppSdkTopics = new HashMap<>(); 484 485 for (Map.Entry<String, List<String>> appSdks : appSdksUsageMap.entrySet()) { 486 Topic returnedTopic = selectRandomTopic(topTopics); 487 if(mFlags.getEnableLoggedTopic() 488 && mTopicsDao.supportsLoggedTopicInReturnedTopicTable()) { 489 returnedTopic = 490 Topic.create( 491 returnedTopic.getTopic(), 492 returnedTopic.getTaxonomyVersion(), 493 returnedTopic.getModelVersion(), 494 getTopicIdForLogging(returnedTopic)); 495 } 496 497 String app = appSdks.getKey(); 498 499 // Check if the app can learn this topic. 500 if (isTopicLearnableByCaller( 501 returnedTopic, 502 app, 503 callersCanLearnMap, 504 topTopics, 505 mFlags.getTopicsNumberOfTopTopics())) { 506 // The app calls Topics API directly. In this case, we set the sdk == empty string. 507 returnedAppSdkTopics.put(Pair.create(app, /* empty Sdk */ ""), returnedTopic); 508 // TODO(b/223159123): Do we need to filter out this log in prod build? 509 sLogger.v( 510 "CacheManager.computeReturnedAppSdkTopics. Topic %s is returned for" 511 + " %s", 512 returnedTopic, app); 513 } 514 515 // Then check all SDKs of the app. 516 for (String sdk : appSdks.getValue()) { 517 if (isTopicLearnableByCaller( 518 returnedTopic, 519 sdk, 520 callersCanLearnMap, 521 topTopics, 522 mFlags.getTopicsNumberOfTopTopics())) { 523 returnedAppSdkTopics.put(Pair.create(app, sdk), returnedTopic); 524 // TODO(b/223159123): Do we need to filter out this log in prod build? 525 sLogger.v( 526 "CacheManager.computeReturnedAppSdkTopics. Topic %s is returned" 527 + " for %s, %s", 528 returnedTopic, app, sdk); 529 } 530 } 531 } 532 533 return returnedAppSdkTopics; 534 } 535 536 // Return a random topics from the Top Topics. 537 // The Top Topics include the Top 5 Topics and one random topic from the Taxonomy. 538 @VisibleForTesting 539 @NonNull selectRandomTopic(List<Topic> topTopics)540 Topic selectRandomTopic(List<Topic> topTopics) { 541 Preconditions.checkArgument( 542 topTopics.size() 543 == mFlags.getTopicsNumberOfTopTopics() 544 + mFlags.getTopicsNumberOfRandomTopics()); 545 int random = mRandom.nextInt(100); 546 547 // First random topic would be after numberOfTopTopics. 548 int randomTopicIndex = mFlags.getTopicsNumberOfTopTopics(); 549 // For 5%, get the random topic. 550 if (random < mFlags.getTopicsPercentageForRandomTopic()) { 551 // The random topic is the last one on the list. 552 return topTopics.get(randomTopicIndex); 553 } 554 555 // For 95%, pick randomly one out of first n top topics. 556 return topTopics.get(random % randomTopicIndex); 557 } 558 559 // To garbage collect data for old epochs. 560 @VisibleForTesting garbageCollectOutdatedEpochData(long currentEpochID)561 void garbageCollectOutdatedEpochData(long currentEpochID) { 562 int epochLookBackNumberForGarbageCollection = mFlags.getNumberOfEpochsToKeepInHistory(); 563 // Assume current Epoch is T, and the earliest epoch should be kept is T-3 564 // Then any epoch data older than T-3-1 = T-4, including T-4 should be deleted. 565 long epochToDeleteFrom = currentEpochID - epochLookBackNumberForGarbageCollection - 1; 566 // To do garbage collection for each table 567 for (Pair<String, String> tableColumnPair : TABLE_INFO_FOR_EPOCH_GARBAGE_COLLECTION) { 568 mTopicsDao.deleteDataOfOldEpochs( 569 tableColumnPair.first, tableColumnPair.second, epochToDeleteFrom); 570 } 571 572 if (mFlags.getEnableDatabaseSchemaVersion9()) { 573 // Delete data from ReturnedEncryptedTopic table. 574 mTopicsDao.deleteDataOfOldEpochs( 575 TopicsTables.ReturnedEncryptedTopicContract.TABLE, 576 TopicsTables.ReturnedEncryptedTopicContract.EPOCH_ID, 577 epochToDeleteFrom); 578 } 579 580 // In app installation, we need to assign topics to newly installed app-sdk caller. In order 581 // to check topic learnability of the sdk, CallerCanLearnTopicsContract needs to persist 582 // numberOfLookBackEpochs more epochs. For example, assume current epoch is T. In app 583 // installation, topics will be assigned to T-1, T-2 and T-3. In order to check learnability 584 // at Epoch T-3, we need to check CallerCanLearnTopicsContract of epoch T-4, T-5 and T-6. 585 long epochToDeleteFromForCallerCanLearn = 586 currentEpochID - epochLookBackNumberForGarbageCollection * 2L - 1; 587 mTopicsDao.deleteDataOfOldEpochs( 588 TopicsTables.CallerCanLearnTopicsContract.TABLE, 589 TopicsTables.CallerCanLearnTopicsContract.EPOCH_ID, 590 epochToDeleteFromForCallerCanLearn); 591 } 592 593 // Compute the mapping of topic to its contributor apps. In an epoch, an app is a contributor to 594 // a topic if the app has called Topics API in this epoch and is classified to the topic. Only 595 // computed for top topics. 596 @VisibleForTesting computeTopTopicsToContributorsMap( @onNull Map<String, List<Topic>> appClassificationTopicsMap, @NonNull List<Topic> topTopics)597 Map<Integer, Set<String>> computeTopTopicsToContributorsMap( 598 @NonNull Map<String, List<Topic>> appClassificationTopicsMap, 599 @NonNull List<Topic> topTopics) { 600 Map<Integer, Set<String>> topicToContributorMap = new HashMap<>(); 601 602 for (Map.Entry<String, List<Topic>> appTopics : appClassificationTopicsMap.entrySet()) { 603 String app = appTopics.getKey(); 604 605 for (Topic topic : appTopics.getValue()) { 606 // Only compute for top topics. 607 if (topTopics.contains(topic)) { 608 int topicId = topic.getTopic(); 609 topicToContributorMap.putIfAbsent(topicId, new HashSet<>()); 610 topicToContributorMap.get(topicId).add(app); 611 } 612 } 613 } 614 615 // At last, check whether there is any top topics without contributors. If so, annotate it 616 // with PADDED_TOP_TOPICS_STRING in the map. See PADDED_TOP_TOPICS_STRING for more details. 617 for (int i = 0; i < mFlags.getTopicsNumberOfTopTopics(); i++) { 618 Topic topTopic = topTopics.get(i); 619 topicToContributorMap.putIfAbsent( 620 topTopic.getTopic(), Set.of(PADDED_TOP_TOPICS_STRING)); 621 } 622 623 return topicToContributorMap; 624 } 625 dump(@onNull PrintWriter writer, @Nullable String[] args)626 public void dump(@NonNull PrintWriter writer, @Nullable String[] args) { 627 writer.println("==== EpochManager Dump ===="); 628 long epochId = getCurrentEpochId(); 629 writer.println(String.format("Current epochId is %d", epochId)); 630 } 631 632 // Gets a topic ID for logging from the given topic using randomized response mechanism. 633 @VisibleForTesting getTopicIdForLogging(Topic topic)634 int getTopicIdForLogging(Topic topic) { 635 List<Integer> topicsTaxonomy = mClassifierManager.getTopicsTaxonomy(); 636 637 // Probability of logging real vs. random topic: 638 // Real topic: e^privacyBudget / (e^privacyBudget + taxonomySize - 1) 639 // Random topic: (taxonomySize - 1) / (e^privacyBudget + taxonomySize - 1) 640 double expPrivacyBudget = Math.exp(mFlags.getTopicsPrivacyBudgetForTopicIdDistribution()); 641 int taxonomySize = topicsTaxonomy.size(); 642 double pRandomization = 643 expPrivacyBudget == Double.POSITIVE_INFINITY 644 ? 0d 645 : (taxonomySize - 1d) / (expPrivacyBudget + taxonomySize - 1d); 646 647 int topicId = topic.getTopic(); 648 649 // In order to prevent select a random topic from being stuck in a loop, 650 // return the topic directly if taxonomy size is 0 or 1. 651 if (taxonomySize <= 1) { 652 return topicId; 653 } 654 655 if (mRandom.nextDouble() < pRandomization) { 656 // Log a random topic ID other than the real one. 657 int randomTopicId = topicId; 658 659 // Set a maximum attempts to prevent select a random topic from being stuck in the loop. 660 int maxAttempts = 5; 661 662 while (randomTopicId == topicId && maxAttempts-- > 0) { 663 randomTopicId = topicsTaxonomy.get(mRandom.nextInt(taxonomySize)); 664 } 665 666 return randomTopicId; 667 } else { 668 return topicId; 669 } 670 } 671 } 672