KeychainSyncingOverIDSProxy/KeychainSyncingOverIDSProxy+Throttle.m

   1 /*
   2  * Copyright (c) 2012-2016 Apple Inc. All Rights Reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23
  24
  25 #import <Foundation/NSArray.h>
  26 #import <Foundation/Foundation.h>
  27
  28 #import <Security/SecBasePriv.h>
  29 #import <Security/SecItemPriv.h>
  30 #import <utilities/debugging.h>
  31 #import <notify.h>
  32
  33 #include <Security/CKBridge/SOSCloudKeychainConstants.h>
  34 #include <Security/SecureObjectSync/SOSARCDefines.h>
  35 #include <Security/SecureObjectSync/SOSCloudCircle.h>
  36 #include <Security/SecureObjectSync/SOSCloudCircleInternal.h>
  37
  38 #import <IDS/IDS.h>
  39 #import <os/activity.h>
  40
  41 #include <utilities/SecAKSWrappers.h>
  42 #include <utilities/SecCFRelease.h>
  43 #include <AssertMacros.h>
  44
  45 #import "IDSPersistentState.h"
  46 #import "KeychainSyncingOverIDSProxy+SendMessage.h"
  47 #import "KeychainSyncingOverIDSProxy+Throttle.h"
  48 #import <utilities/SecADWrapper.h>
  49
  50
  51 static NSString *kExportUnhandledMessages = @"UnhandledMessages";
  52 static NSString *kMonitorState = @"MonitorState";
  53
  54 static NSString *kMonitorPenaltyBoxKey = @"Penalty";
  55 static NSString *kMonitorMessageKey = @"Message";
  56 static NSString *kMonitorConsecutiveWrites = @"ConsecutiveWrites";
  57 static NSString *kMonitorLastWriteTimestamp = @"LastWriteTimestamp";
  58 static NSString *kMonitorMessageQueue = @"MessageQueue";
  59 static NSString *kMonitorPenaltyTimer = @"PenaltyTimer";
  60 static NSString *kMonitorDidWriteDuringPenalty = @"DidWriteDuringPenalty";
  61
  62 static NSString *kMonitorTimeTable = @"TimeTable";
  63 static NSString *kMonitorFirstMinute = @"AFirstMinute";
  64 static NSString *kMonitorSecondMinute = @"BSecondMinute";
  65 static NSString *kMonitorThirdMinute = @"CThirdMinute";
  66 static NSString *kMonitorFourthMinute = @"DFourthMinute";
  67 static NSString *kMonitorFifthMinute = @"EFifthMinute";
  68 static NSString *kMonitorWroteInTimeSlice = @"TimeSlice";
  69
  70 static int max_penalty_timeout = 32;
  71 static int seconds_per_minute = 60;
  72 static int queue_depth = 1;
  73
  74 CFStringRef const IDSPAggdIncreaseThrottlingKey = CFSTR("com.apple.security.idsproxy.increasethrottle");
  75 CFStringRef const IDSPAggdDecreaseThrottlingKey = CFSTR("com.apple.security.idsproxy.decreasethrottle");
  76
  77 static const int64_t kRetryTimerLeeway = (NSEC_PER_MSEC * 250);      // 250ms leeway for handling unhandled messages.
  78
  79 @implementation KeychainSyncingOverIDSProxy (Throttle)
  80
  81 -(dispatch_source_t)setNewTimer:(int)timeout key:(NSString*)key deviceName:(NSString*)deviceName peerID:(NSString*)peerID
  82 {
  83
  84     __block dispatch_source_t timer = dispatch_source_create(DISPATCH_SOURCE_TYPE_TIMER, 0, 0, dispatch_get_main_queue());
  85     dispatch_source_set_timer(timer, dispatch_time(DISPATCH_TIME_NOW, timeout * NSEC_PER_SEC * seconds_per_minute), DISPATCH_TIME_FOREVER, kRetryTimerLeeway);
  86     dispatch_source_set_event_handler(timer, ^{
  87         [self penaltyTimerFired:key deviceName:deviceName peerID:peerID];
  88     });
  89     dispatch_resume(timer);
  90     return timer;
  91 }
  92
  93 -(void) increasePenalty:(NSNumber*)currentPenalty key:(NSString*)key keyEntry:(NSMutableDictionary**)keyEntry deviceName:(NSString*)deviceName peerID:(NSString*)peerID
  94 {
  95     SecADAddValueForScalarKey((IDSPAggdIncreaseThrottlingKey), 1);
  96
  97     secnotice("backoff", "increasing penalty!");
  98     int newPenalty = 0;
  99
 100     if ([currentPenalty intValue] <= 0)
 101         newPenalty = 1;
 102     else
 103         newPenalty = fmin([currentPenalty intValue]*2, max_penalty_timeout);
 104
 105     secnotice("backoff", "key %@, waiting %d minutes long to send next messages", key, newPenalty);
 106
 107     NSNumber* penalty_timeout = [[NSNumber alloc]initWithInt:newPenalty];
 108     dispatch_source_t existingTimer = [*keyEntry objectForKey:kMonitorPenaltyTimer];
 109
 110     if(existingTimer != nil){
 111         [*keyEntry removeObjectForKey:kMonitorPenaltyTimer];
 112         dispatch_suspend(existingTimer);
 113         dispatch_source_set_timer(existingTimer,dispatch_time(DISPATCH_TIME_NOW, newPenalty * NSEC_PER_SEC * seconds_per_minute), DISPATCH_TIME_FOREVER, kRetryTimerLeeway);
 114         dispatch_resume(existingTimer);
 115         [*keyEntry setObject:existingTimer forKey:kMonitorPenaltyTimer];
 116     }
 117     else{
 118         dispatch_source_t timer = [self setNewTimer:newPenalty key:key deviceName:deviceName peerID:peerID];
 119         [*keyEntry setObject:timer forKey:kMonitorPenaltyTimer];
 120     }
 121
 122     [*keyEntry setObject:penalty_timeout forKey:kMonitorPenaltyBoxKey];
 123     [[KeychainSyncingOverIDSProxy idsProxy].monitor setObject:*keyEntry forKey:key];
 124 }
 125
 126 -(void) decreasePenalty:(NSNumber*)currentPenalty key:(NSString*)key keyEntry:(NSMutableDictionary**)keyEntry deviceName:(NSString*)deviceName peerID:(NSString*)peerID
 127 {
 128     SecADAddValueForScalarKey((IDSPAggdDecreaseThrottlingKey), 1);
 129
 130     int newPenalty = 0;
 131     secnotice("backoff","decreasing penalty!");
 132     if([currentPenalty intValue] == 0 || [currentPenalty intValue] == 1)
 133         newPenalty = 0;
 134     else
 135         newPenalty = [currentPenalty intValue]/2;
 136
 137     secnotice("backoff","key %@, waiting %d minutes long to send next messages", key, newPenalty);
 138
 139     NSNumber* penalty_timeout = [[NSNumber alloc]initWithInt:newPenalty];
 140
 141     dispatch_source_t existingTimer = [*keyEntry objectForKey:kMonitorPenaltyTimer];
 142     if(existingTimer != nil){
 143         [*keyEntry removeObjectForKey:kMonitorPenaltyTimer];
 144         dispatch_suspend(existingTimer);
 145         if(newPenalty != 0){
 146             dispatch_source_set_timer(existingTimer,dispatch_time(DISPATCH_TIME_NOW, newPenalty * NSEC_PER_SEC * seconds_per_minute), DISPATCH_TIME_FOREVER, kRetryTimerLeeway);
 147             dispatch_resume(existingTimer);
 148             [*keyEntry setObject:existingTimer forKey:kMonitorPenaltyTimer];
 149         }
 150         else{
 151             dispatch_resume(existingTimer);
 152             dispatch_source_cancel(existingTimer);
 153         }
 154     }
 155     else{
 156         if(newPenalty != 0){
 157             dispatch_source_t timer = [self setNewTimer:newPenalty key:key deviceName:deviceName peerID:peerID];
 158             [*keyEntry setObject:timer forKey:kMonitorPenaltyTimer];
 159         }
 160     }
 161
 162     [*keyEntry setObject:penalty_timeout forKey:kMonitorPenaltyBoxKey];
 163     [[KeychainSyncingOverIDSProxy idsProxy].monitor setObject:*keyEntry forKey:key];
 164
 165 }
 166
 167 - (void)penaltyTimerFired:(NSString*)key deviceName:(NSString*)deviceName peerID:(NSString*)peerID
 168 {
 169     secnotice("backoff", "key: %@, !!!!!!!!!!!!!!!!penalty timeout is up!!!!!!!!!!!!", key);
 170     NSMutableDictionary *keyEntry = [[KeychainSyncingOverIDSProxy idsProxy].monitor objectForKey:key];
 171     if(!keyEntry){
 172         [self initializeKeyEntry:key];
 173         keyEntry = [[KeychainSyncingOverIDSProxy idsProxy].monitor objectForKey:key];
 174     }
 175     NSMutableArray *queuedMessages = [[KeychainSyncingOverIDSProxy idsProxy].monitor objectForKey:kMonitorMessageQueue];
 176     secnotice("backoff","key: %@, queuedMessages: %@", key, queuedMessages);
 177     if(queuedMessages && [queuedMessages count] != 0){
 178         secnotice("backoff","key: %@, message queue not empty, writing to IDS!", key);
 179         [queuedMessages enumerateObjectsUsingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
 180             NSError* error = nil;
 181             NSDictionary* message = (NSDictionary*) obj;
 182             [self sendFragmentedIDSMessages:message name:deviceName peer:peerID error:&error];
 183         }];
 184
 185         [[KeychainSyncingOverIDSProxy idsProxy].monitor  setObject:[NSMutableArray array] forKey:kMonitorMessageQueue];
 186     }
 187     //decrease timeout since we successfully wrote messages out
 188     NSNumber *penalty_timeout = [keyEntry objectForKey:kMonitorPenaltyBoxKey];
 189     secnotice("backoff", "key: %@, current penalty timeout: %@", key, penalty_timeout);
 190
 191     NSString* didWriteDuringTimeout = [keyEntry objectForKey:kMonitorDidWriteDuringPenalty];
 192     if( didWriteDuringTimeout && [didWriteDuringTimeout isEqualToString:@"YES"] )
 193     {
 194         //increase timeout since we wrote during out penalty timeout
 195         [self increasePenalty:penalty_timeout key:key keyEntry:&keyEntry deviceName:deviceName peerID:peerID];
 196     }
 197     else{
 198         //decrease timeout since we successfully wrote messages out
 199         [self decreasePenalty:penalty_timeout key:key keyEntry:&keyEntry deviceName:deviceName peerID:peerID];
 200     }
 201
 202     //resetting the check
 203     [keyEntry setObject: @"NO" forKey:kMonitorDidWriteDuringPenalty];
 204
 205     //recompute the timetable and number of consecutive writes to IDS
 206     NSMutableDictionary *timetableForKey = [keyEntry objectForKey:kMonitorTimeTable];
 207     if(timetableForKey == nil){
 208         timetableForKey = [self initializeTimeTable:key];
 209     }
 210     NSNumber *consecutiveWrites = [keyEntry objectForKey:kMonitorConsecutiveWrites];
 211     if(consecutiveWrites == nil){
 212         consecutiveWrites = [[NSNumber alloc] initWithInt:0];
 213     }
 214     [self recordTimestampForAppropriateInterval:&timetableForKey key:key consecutiveWrites:&consecutiveWrites];
 215
 216     [keyEntry setObject:consecutiveWrites forKey:kMonitorConsecutiveWrites];
 217     [keyEntry setObject:timetableForKey forKey:kMonitorTimeTable];
 218     [[KeychainSyncingOverIDSProxy idsProxy].monitor setObject:keyEntry forKey:key];
 219
 220 }
 221
 222 -(NSMutableDictionary*)initializeTimeTable:(NSString*)key
 223 {
 224     NSDate *currentTime = [NSDate date];
 225     NSMutableDictionary *firstMinute = [NSMutableDictionary dictionaryWithObjectsAndKeys:[currentTime dateByAddingTimeInterval: seconds_per_minute], kMonitorFirstMinute, @"YES", kMonitorWroteInTimeSlice, nil];
 226     NSMutableDictionary *secondMinute = [NSMutableDictionary dictionaryWithObjectsAndKeys:[currentTime dateByAddingTimeInterval: seconds_per_minute * 2],kMonitorSecondMinute, @"NO", kMonitorWroteInTimeSlice, nil];
 227     NSMutableDictionary *thirdMinute = [NSMutableDictionary dictionaryWithObjectsAndKeys:[currentTime dateByAddingTimeInterval: seconds_per_minute * 3], kMonitorThirdMinute, @"NO",kMonitorWroteInTimeSlice, nil];
 228     NSMutableDictionary *fourthMinute = [NSMutableDictionary dictionaryWithObjectsAndKeys:[currentTime dateByAddingTimeInterval: seconds_per_minute * 4],kMonitorFourthMinute, @"NO", kMonitorWroteInTimeSlice, nil];
 229     NSMutableDictionary *fifthMinute = [NSMutableDictionary dictionaryWithObjectsAndKeys:[currentTime dateByAddingTimeInterval: seconds_per_minute * 5], kMonitorFifthMinute, @"NO", kMonitorWroteInTimeSlice, nil];
 230
 231     NSMutableDictionary *timeTable = [NSMutableDictionary dictionaryWithObjectsAndKeys: firstMinute, kMonitorFirstMinute,
 232                                       secondMinute, kMonitorSecondMinute,
 233                                       thirdMinute, kMonitorThirdMinute,
 234                                       fourthMinute, kMonitorFourthMinute,
 235                                       fifthMinute, kMonitorFifthMinute, nil];
 236     return timeTable;
 237 }
 238
 239 - (void)initializeKeyEntry:(NSString*)key
 240 {
 241     NSMutableDictionary *timeTable = [[KeychainSyncingOverIDSProxy idsProxy] initializeTimeTable:key];
 242     NSDate *currentTime = [NSDate date];
 243
 244     NSMutableDictionary *keyEntry = [NSMutableDictionary dictionaryWithObjectsAndKeys: key, kMonitorMessageKey, @0, kMonitorConsecutiveWrites, currentTime, kMonitorLastWriteTimestamp, @0, kMonitorPenaltyBoxKey, timeTable, kMonitorTimeTable,[NSMutableArray array], kMonitorMessageQueue, nil];
 245
 246     [[KeychainSyncingOverIDSProxy idsProxy].monitor setObject:keyEntry forKey:key];
 247
 248 }
 249
 250 - (void)recordTimestampForAppropriateInterval:(NSMutableDictionary**)timeTable key:(NSString*)key consecutiveWrites:(NSNumber**)consecutiveWrites
 251 {
 252     NSDate *currentTime = [NSDate date];
 253     __block int cWrites = [*consecutiveWrites intValue];
 254     __block BOOL foundTimeSlot = NO;
 255     __block NSMutableDictionary *previousTable = nil;
 256
 257     NSArray *sortedTimestampKeys = [[*timeTable allKeys] sortedArrayUsingSelector:@selector(compare:)];
 258     NSMutableDictionary* timeTableStrong = *timeTable;
 259
 260     [sortedTimestampKeys enumerateObjectsUsingBlock:^(id arrayObject, NSUInteger idx, BOOL *stop)
 261      {
 262          if(foundTimeSlot == YES)
 263              return;
 264
 265          NSString *sortedKey = (NSString*)arrayObject;
 266
 267          //grab the dictionary containing write information
 268          //(date, boolean to check if a write occured in the timeslice,
 269          NSMutableDictionary *minutesTable = [timeTableStrong objectForKey: sortedKey];
 270          if(minutesTable == nil)
 271              minutesTable = [[KeychainSyncingOverIDSProxy idsProxy] initializeTimeTable:key];
 272
 273          NSString *minuteKey = (NSString*)sortedKey;
 274          NSDate *timeStampForSlice = [minutesTable objectForKey:minuteKey];
 275
 276          if(timeStampForSlice && [timeStampForSlice compare:currentTime] == NSOrderedDescending){
 277              foundTimeSlot = YES;
 278              NSString* written = [minutesTable objectForKey:kMonitorWroteInTimeSlice];
 279              //figure out if we have previously recorded a write in this time slice
 280              if([written isEqualToString:@"NO"]){
 281                  [minutesTable setObject:@"YES" forKey:kMonitorWroteInTimeSlice];
 282                  if(previousTable != nil){
 283                      //if we wrote in the previous time slice count the current time as in the consecutive write count
 284                      written = [previousTable objectForKey:kMonitorWroteInTimeSlice];
 285                      if([written isEqualToString:@"YES"]){
 286                          cWrites++;
 287                      }
 288                      else if ([written isEqualToString:@"NO"]){
 289                          cWrites = 0;
 290                      }
 291                  }
 292              }
 293              return;
 294          }
 295          previousTable = minutesTable;
 296      }];
 297
 298     if(foundTimeSlot == NO){
 299         //reset the time table
 300         secnotice("backoff","didn't find a time slot, resetting the table");
 301
 302         //record if a write occured between the last time slice of
 303         //the time table entries and now.
 304         NSMutableDictionary *lastTable = [*timeTable objectForKey:kMonitorFifthMinute];
 305         NSDate *lastDate = [lastTable objectForKey:kMonitorFifthMinute];
 306
 307         if(lastDate && ((double)[currentTime timeIntervalSinceDate: lastDate] >= seconds_per_minute)){
 308             *consecutiveWrites = [[NSNumber alloc]initWithInt:0];
 309         }
 310         else{
 311             NSString* written = [lastTable objectForKey:kMonitorWroteInTimeSlice];
 312             if(written && [written isEqualToString:@"YES"]){
 313                 cWrites++;
 314                 *consecutiveWrites = [[NSNumber alloc]initWithInt:cWrites];
 315             }
 316             else{
 317                 *consecutiveWrites = [[NSNumber alloc]initWithInt:0];
 318             }
 319         }
 320
 321         *timeTable  = [[KeychainSyncingOverIDSProxy idsProxy] initializeTimeTable:key];
 322         return;
 323     }
 324     *consecutiveWrites = [[NSNumber alloc]initWithInt:cWrites];
 325 }
 326 - (void)recordTimestampOfWriteToIDS:(NSDictionary *)values deviceName:(NSString*)name peerID:(NSString*)peerid
 327 {
 328     if([[KeychainSyncingOverIDSProxy idsProxy].monitor count] == 0){
 329         [values enumerateKeysAndObjectsUsingBlock: ^(id key, id obj, BOOL *stop)
 330          {
 331              [self initializeKeyEntry: key];
 332          }];
 333     }
 334     else{
 335         [values enumerateKeysAndObjectsUsingBlock: ^(id key, id obj, BOOL *stop)
 336          {
 337              NSMutableDictionary *keyEntry = [[KeychainSyncingOverIDSProxy idsProxy].monitor objectForKey:key];
 338              if(keyEntry == nil){
 339                  [self initializeKeyEntry: key];
 340              }
 341              else{
 342                  NSNumber *penalty_timeout = [keyEntry objectForKey:kMonitorPenaltyBoxKey];
 343                  NSDate *lastWriteTimestamp = [keyEntry objectForKey:kMonitorLastWriteTimestamp];
 344                  NSMutableDictionary *timeTable = [keyEntry objectForKey: kMonitorTimeTable];
 345                  NSNumber *existingWrites = [keyEntry objectForKey: kMonitorConsecutiveWrites];
 346                  NSDate *currentTime = [NSDate date];
 347
 348                  //record the write happened in our timetable structure
 349                  [self recordTimestampForAppropriateInterval:&timeTable key:key consecutiveWrites:&existingWrites];
 350
 351                  int consecutiveWrites = [existingWrites intValue];
 352                  secnotice("backoff","consecutive writes: %d", consecutiveWrites);
 353                  [keyEntry setObject:existingWrites forKey:kMonitorConsecutiveWrites];
 354                  [keyEntry setObject:timeTable forKey:kMonitorTimeTable];
 355                  [keyEntry setObject:currentTime forKey:kMonitorLastWriteTimestamp];
 356                  [[KeychainSyncingOverIDSProxy idsProxy].monitor setObject:keyEntry forKey:key];
 357
 358                  if( (penalty_timeout && [penalty_timeout intValue] != 0 ) || ((double)[currentTime timeIntervalSinceDate: lastWriteTimestamp] <= 60 && consecutiveWrites >= 5)){
 359
 360                      if( (penalty_timeout == nil || [penalty_timeout intValue] == 0) && consecutiveWrites == 5){
 361                          secnotice("backoff","written for 5 consecutive minutes, time to start throttling");
 362                         [self increasePenalty:penalty_timeout key:key keyEntry:&keyEntry deviceName:name peerID:peerid];
 363                      }
 364                      else
 365                          secnotice("backoff","monitor: keys have been written for 5 or more minutes, recording we wrote during timeout");
 366
 367                      //record we wrote during a timeout
 368                      [keyEntry setObject: @"YES" forKey:kMonitorDidWriteDuringPenalty];
 369                  }
 370                  else if((double)[currentTime timeIntervalSinceDate: lastWriteTimestamp] <= 60 && consecutiveWrites < 5){
 371                      //for debugging purposes
 372                      secnotice("backoff","monitor: still writing freely");
 373                      [keyEntry setObject: @"NO" forKey:kMonitorDidWriteDuringPenalty];
 374                  }
 375                  else if([penalty_timeout intValue] != 0 && ((double)[currentTime timeIntervalSinceDate: lastWriteTimestamp] > 60 && consecutiveWrites > 5) ){
 376
 377                      //encountered a write even though we're in throttle mode
 378                      [keyEntry setObject: @"YES" forKey:kMonitorDidWriteDuringPenalty];
 379                  }
 380              }
 381          }];
 382     }
 383 }
 384
 385 - (NSDictionary*)filterForWritableValues:(NSDictionary *)values
 386 {
 387     secnotice("backoff", "filterForWritableValues: %@", values);
 388     NSMutableDictionary *keyEntry_operationType = [[KeychainSyncingOverIDSProxy idsProxy].monitor objectForKey:@"IDSMessageOperation"];
 389
 390     secnotice("backoff", "keyEntry_operationType: %@", keyEntry_operationType);
 391
 392     NSNumber *penalty = [keyEntry_operationType objectForKey:kMonitorPenaltyBoxKey];
 393
 394     if(penalty && [penalty intValue] != 0){
 395
 396         NSMutableArray *queuedMessage = [[KeychainSyncingOverIDSProxy idsProxy].monitor objectForKey:kMonitorMessageQueue];
 397         if(queuedMessage == nil)
 398             queuedMessage = [[NSMutableArray alloc] initWithCapacity:queue_depth];
 399
 400         secnotice("backoff", "writing to queuedMessages: %@", queuedMessage);
 401
 402         if([queuedMessage count] == 0)
 403             [queuedMessage addObject:values];
 404         else
 405             [queuedMessage replaceObjectAtIndex:(queue_depth-1) withObject: values];
 406
 407         [[KeychainSyncingOverIDSProxy idsProxy].monitor setObject:queuedMessage forKey:kMonitorMessageQueue];
 408         return NULL;
 409     }
 410
 411     return values;
 412 }
 413
 414 @end