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 #if TARGET_OS_EMBEDDED && !TARGET_IPHONE_SIMULATOR
  75 CFStringRef const IDSPAggdIncreaseThrottlingKey = CFSTR("com.apple.security.idsproxy.increasethrottle");
  76 CFStringRef const IDSPAggdDecreaseThrottlingKey = CFSTR("com.apple.security.idsproxy.decreasethrottle");
  77 #endif
  78
  79 static const int64_t kRetryTimerLeeway = (NSEC_PER_MSEC * 250);      // 250ms leeway for handling unhandled messages.
  80
  81 @implementation KeychainSyncingOverIDSProxy (Throttle)
  82
  83 -(dispatch_source_t)setNewTimer:(int)timeout key:(NSString*)key deviceName:(NSString*)deviceName peerID:(NSString*)peerID
  84 {
  85
  86     __block dispatch_source_t timer = dispatch_source_create(DISPATCH_SOURCE_TYPE_TIMER, 0, 0, dispatch_get_main_queue());
  87     dispatch_source_set_timer(timer, dispatch_time(DISPATCH_TIME_NOW, timeout * NSEC_PER_SEC * seconds_per_minute), DISPATCH_TIME_FOREVER, kRetryTimerLeeway);
  88     dispatch_source_set_event_handler(timer, ^{
  89         [self penaltyTimerFired:key deviceName:deviceName peerID:peerID];
  90     });
  91     dispatch_resume(timer);
  92     return timer;
  93 }
  94
  95 -(void) increasePenalty:(NSNumber*)currentPenalty key:(NSString*)key keyEntry:(NSMutableDictionary**)keyEntry deviceName:(NSString*)deviceName peerID:(NSString*)peerID
  96 {
  97 #if TARGET_OS_EMBEDDED && !TARGET_IPHONE_SIMULATOR
  98     SecADAddValueForScalarKey((IDSPAggdIncreaseThrottlingKey), 1);
  99 #endif
 100
 101     secnotice("backoff", "increasing penalty!");
 102     int newPenalty = 0;
 103
 104     if ([currentPenalty intValue] <= 0)
 105         newPenalty = 1;
 106     else
 107         newPenalty = fmin([currentPenalty intValue]*2, max_penalty_timeout);
 108
 109     secnotice("backoff", "key %@, waiting %d minutes long to send next messages", key, newPenalty);
 110
 111     NSNumber* penalty_timeout = [[NSNumber alloc]initWithInt:newPenalty];
 112     dispatch_source_t existingTimer = [*keyEntry objectForKey:kMonitorPenaltyTimer];
 113
 114     if(existingTimer != nil){
 115         [*keyEntry removeObjectForKey:kMonitorPenaltyTimer];
 116         dispatch_suspend(existingTimer);
 117         dispatch_source_set_timer(existingTimer,dispatch_time(DISPATCH_TIME_NOW, newPenalty * NSEC_PER_SEC * seconds_per_minute), DISPATCH_TIME_FOREVER, kRetryTimerLeeway);
 118         dispatch_resume(existingTimer);
 119         [*keyEntry setObject:existingTimer forKey:kMonitorPenaltyTimer];
 120     }
 121     else{
 122         dispatch_source_t timer = [self setNewTimer:newPenalty key:key deviceName:deviceName peerID:peerID];
 123         [*keyEntry setObject:timer forKey:kMonitorPenaltyTimer];
 124     }
 125
 126     [*keyEntry setObject:penalty_timeout forKey:kMonitorPenaltyBoxKey];
 127     [[KeychainSyncingOverIDSProxy idsProxy].monitor setObject:*keyEntry forKey:key];
 128 }
 129
 130 -(void) decreasePenalty:(NSNumber*)currentPenalty key:(NSString*)key keyEntry:(NSMutableDictionary**)keyEntry deviceName:(NSString*)deviceName peerID:(NSString*)peerID
 131 {
 132 #if TARGET_OS_EMBEDDED && !TARGET_IPHONE_SIMULATOR
 133     SecADAddValueForScalarKey((IDSPAggdDecreaseThrottlingKey), 1);
 134 #endif
 135     int newPenalty = 0;
 136     secnotice("backoff","decreasing penalty!");
 137     if([currentPenalty intValue] == 0 || [currentPenalty intValue] == 1)
 138         newPenalty = 0;
 139     else
 140         newPenalty = [currentPenalty intValue]/2;
 141
 142     secnotice("backoff","key %@, waiting %d minutes long to send next messages", key, newPenalty);
 143
 144     NSNumber* penalty_timeout = [[NSNumber alloc]initWithInt:newPenalty];
 145
 146     dispatch_source_t existingTimer = [*keyEntry objectForKey:kMonitorPenaltyTimer];
 147     if(existingTimer != nil){
 148         [*keyEntry removeObjectForKey:kMonitorPenaltyTimer];
 149         dispatch_suspend(existingTimer);
 150         if(newPenalty != 0){
 151             dispatch_source_set_timer(existingTimer,dispatch_time(DISPATCH_TIME_NOW, newPenalty * NSEC_PER_SEC * seconds_per_minute), DISPATCH_TIME_FOREVER, kRetryTimerLeeway);
 152             dispatch_resume(existingTimer);
 153             [*keyEntry setObject:existingTimer forKey:kMonitorPenaltyTimer];
 154         }
 155         else{
 156             dispatch_resume(existingTimer);
 157             dispatch_source_cancel(existingTimer);
 158         }
 159     }
 160     else{
 161         if(newPenalty != 0){
 162             dispatch_source_t timer = [self setNewTimer:newPenalty key:key deviceName:deviceName peerID:peerID];
 163             [*keyEntry setObject:timer forKey:kMonitorPenaltyTimer];
 164         }
 165     }
 166
 167     [*keyEntry setObject:penalty_timeout forKey:kMonitorPenaltyBoxKey];
 168     [[KeychainSyncingOverIDSProxy idsProxy].monitor setObject:*keyEntry forKey:key];
 169
 170 }
 171
 172 - (void)penaltyTimerFired:(NSString*)key deviceName:(NSString*)deviceName peerID:(NSString*)peerID
 173 {
 174     secnotice("backoff", "key: %@, !!!!!!!!!!!!!!!!penalty timeout is up!!!!!!!!!!!!", key);
 175     NSMutableDictionary *keyEntry = [[KeychainSyncingOverIDSProxy idsProxy].monitor objectForKey:key];
 176     if(!keyEntry){
 177         [self initializeKeyEntry:key];
 178         keyEntry = [[KeychainSyncingOverIDSProxy idsProxy].monitor objectForKey:key];
 179     }
 180     NSMutableArray *queuedMessages = [[KeychainSyncingOverIDSProxy idsProxy].monitor objectForKey:kMonitorMessageQueue];
 181     secnotice("backoff","key: %@, queuedMessages: %@", key, queuedMessages);
 182     if(queuedMessages && [queuedMessages count] != 0){
 183         secnotice("backoff","key: %@, message queue not empty, writing to IDS!", key);
 184         [queuedMessages enumerateObjectsUsingBlock:^(id  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
 185             NSError* error = nil;
 186             NSDictionary* message = (NSDictionary*) obj;
 187             [self sendFragmentedIDSMessages:message name:deviceName peer:peerID error:&error];
 188         }];
 189
 190         [[KeychainSyncingOverIDSProxy idsProxy].monitor  setObject:[NSMutableArray array] forKey:kMonitorMessageQueue];
 191     }
 192     //decrease timeout since we successfully wrote messages out
 193     NSNumber *penalty_timeout = [keyEntry objectForKey:kMonitorPenaltyBoxKey];
 194     secnotice("backoff", "key: %@, current penalty timeout: %@", key, penalty_timeout);
 195
 196     NSString* didWriteDuringTimeout = [keyEntry objectForKey:kMonitorDidWriteDuringPenalty];
 197     if( didWriteDuringTimeout && [didWriteDuringTimeout isEqualToString:@"YES"] )
 198     {
 199         //increase timeout since we wrote during out penalty timeout
 200         [self increasePenalty:penalty_timeout key:key keyEntry:&keyEntry deviceName:deviceName peerID:peerID];
 201     }
 202     else{
 203         //decrease timeout since we successfully wrote messages out
 204         [self decreasePenalty:penalty_timeout key:key keyEntry:&keyEntry deviceName:deviceName peerID:peerID];
 205     }
 206
 207     //resetting the check
 208     [keyEntry setObject: @"NO" forKey:kMonitorDidWriteDuringPenalty];
 209
 210     //recompute the timetable and number of consecutive writes to IDS
 211     NSMutableDictionary *timetableForKey = [keyEntry objectForKey:kMonitorTimeTable];
 212     if(timetableForKey == nil){
 213         timetableForKey = [self initializeTimeTable:key];
 214     }
 215     NSNumber *consecutiveWrites = [keyEntry objectForKey:kMonitorConsecutiveWrites];
 216     if(consecutiveWrites == nil){
 217         consecutiveWrites = [[NSNumber alloc] initWithInt:0];
 218     }
 219     [self recordTimestampForAppropriateInterval:&timetableForKey key:key consecutiveWrites:&consecutiveWrites];
 220
 221     [keyEntry setObject:consecutiveWrites forKey:kMonitorConsecutiveWrites];
 222     [keyEntry setObject:timetableForKey forKey:kMonitorTimeTable];
 223     [[KeychainSyncingOverIDSProxy idsProxy].monitor setObject:keyEntry forKey:key];
 224
 225 }
 226
 227 -(NSMutableDictionary*)initializeTimeTable:(NSString*)key
 228 {
 229     NSDate *currentTime = [NSDate date];
 230     NSMutableDictionary *firstMinute = [NSMutableDictionary dictionaryWithObjectsAndKeys:[currentTime dateByAddingTimeInterval: seconds_per_minute], kMonitorFirstMinute, @"YES", kMonitorWroteInTimeSlice, nil];
 231     NSMutableDictionary *secondMinute = [NSMutableDictionary dictionaryWithObjectsAndKeys:[currentTime dateByAddingTimeInterval: seconds_per_minute * 2],kMonitorSecondMinute, @"NO", kMonitorWroteInTimeSlice, nil];
 232     NSMutableDictionary *thirdMinute = [NSMutableDictionary dictionaryWithObjectsAndKeys:[currentTime dateByAddingTimeInterval: seconds_per_minute * 3], kMonitorThirdMinute, @"NO",kMonitorWroteInTimeSlice, nil];
 233     NSMutableDictionary *fourthMinute = [NSMutableDictionary dictionaryWithObjectsAndKeys:[currentTime dateByAddingTimeInterval: seconds_per_minute * 4],kMonitorFourthMinute, @"NO", kMonitorWroteInTimeSlice, nil];
 234     NSMutableDictionary *fifthMinute = [NSMutableDictionary dictionaryWithObjectsAndKeys:[currentTime dateByAddingTimeInterval: seconds_per_minute * 5], kMonitorFifthMinute, @"NO", kMonitorWroteInTimeSlice, nil];
 235
 236     NSMutableDictionary *timeTable = [NSMutableDictionary dictionaryWithObjectsAndKeys: firstMinute, kMonitorFirstMinute,
 237                                       secondMinute, kMonitorSecondMinute,
 238                                       thirdMinute, kMonitorThirdMinute,
 239                                       fourthMinute, kMonitorFourthMinute,
 240                                       fifthMinute, kMonitorFifthMinute, nil];
 241     return timeTable;
 242 }
 243
 244 - (void)initializeKeyEntry:(NSString*)key
 245 {
 246     NSMutableDictionary *timeTable = [[KeychainSyncingOverIDSProxy idsProxy] initializeTimeTable:key];
 247     NSDate *currentTime = [NSDate date];
 248
 249     NSMutableDictionary *keyEntry = [NSMutableDictionary dictionaryWithObjectsAndKeys: key, kMonitorMessageKey, @0, kMonitorConsecutiveWrites, currentTime, kMonitorLastWriteTimestamp, @0, kMonitorPenaltyBoxKey, timeTable, kMonitorTimeTable,[NSMutableArray array], kMonitorMessageQueue, nil];
 250
 251     [[KeychainSyncingOverIDSProxy idsProxy].monitor setObject:keyEntry forKey:key];
 252
 253 }
 254
 255 - (void)recordTimestampForAppropriateInterval:(NSMutableDictionary**)timeTable key:(NSString*)key consecutiveWrites:(NSNumber**)consecutiveWrites
 256 {
 257     NSDate *currentTime = [NSDate date];
 258     __block int cWrites = [*consecutiveWrites intValue];
 259     __block BOOL foundTimeSlot = NO;
 260     __block NSMutableDictionary *previousTable = nil;
 261
 262     NSArray *sortedTimestampKeys = [[*timeTable allKeys] sortedArrayUsingSelector:@selector(compare:)];
 263     [sortedTimestampKeys enumerateObjectsUsingBlock:^(id arrayObject, NSUInteger idx, BOOL *stop)
 264      {
 265          if(foundTimeSlot == YES)
 266              return;
 267
 268          NSString *sortedKey = (NSString*)arrayObject;
 269
 270          //grab the dictionary containing write information
 271          //(date, boolean to check if a write occured in the timeslice,
 272          NSMutableDictionary *minutesTable = [*timeTable objectForKey: sortedKey];
 273          if(minutesTable == nil)
 274              minutesTable = [[KeychainSyncingOverIDSProxy idsProxy] initializeTimeTable:key];
 275
 276          NSString *minuteKey = (NSString*)sortedKey;
 277          NSDate *timeStampForSlice = [minutesTable objectForKey:minuteKey];
 278
 279          if(timeStampForSlice && [timeStampForSlice compare:currentTime] == NSOrderedDescending){
 280              foundTimeSlot = YES;
 281              NSString* written = [minutesTable objectForKey:kMonitorWroteInTimeSlice];
 282              //figure out if we have previously recorded a write in this time slice
 283              if([written isEqualToString:@"NO"]){
 284                  [minutesTable setObject:@"YES" forKey:kMonitorWroteInTimeSlice];
 285                  if(previousTable != nil){
 286                      //if we wrote in the previous time slice count the current time as in the consecutive write count
 287                      written = [previousTable objectForKey:kMonitorWroteInTimeSlice];
 288                      if([written isEqualToString:@"YES"]){
 289                          cWrites++;
 290                      }
 291                      else if ([written isEqualToString:@"NO"]){
 292                          cWrites = 0;
 293                      }
 294                  }
 295              }
 296              return;
 297          }
 298          previousTable = minutesTable;
 299      }];
 300
 301     if(foundTimeSlot == NO){
 302         //reset the time table
 303         secnotice("backoff","didn't find a time slot, resetting the table");
 304
 305         //record if a write occured between the last time slice of
 306         //the time table entries and now.
 307         NSMutableDictionary *lastTable = [*timeTable objectForKey:kMonitorFifthMinute];
 308         NSDate *lastDate = [lastTable objectForKey:kMonitorFifthMinute];
 309
 310         if(lastDate && ((double)[currentTime timeIntervalSinceDate: lastDate] >= seconds_per_minute)){
 311             *consecutiveWrites = [[NSNumber alloc]initWithInt:0];
 312         }
 313         else{
 314             NSString* written = [lastTable objectForKey:kMonitorWroteInTimeSlice];
 315             if(written && [written isEqualToString:@"YES"]){
 316                 cWrites++;
 317                 *consecutiveWrites = [[NSNumber alloc]initWithInt:cWrites];
 318             }
 319             else{
 320                 *consecutiveWrites = [[NSNumber alloc]initWithInt:0];
 321             }
 322         }
 323
 324         *timeTable  = [[KeychainSyncingOverIDSProxy idsProxy] initializeTimeTable:key];
 325         return;
 326     }
 327     *consecutiveWrites = [[NSNumber alloc]initWithInt:cWrites];
 328 }
 329 - (void)recordTimestampOfWriteToIDS:(NSDictionary *)values deviceName:(NSString*)name peerID:(NSString*)peerid
 330 {
 331     if([[KeychainSyncingOverIDSProxy idsProxy].monitor count] == 0){
 332         [values enumerateKeysAndObjectsUsingBlock: ^(id key, id obj, BOOL *stop)
 333          {
 334              [self initializeKeyEntry: key];
 335          }];
 336     }
 337     else{
 338         [values enumerateKeysAndObjectsUsingBlock: ^(id key, id obj, BOOL *stop)
 339          {
 340              NSMutableDictionary *keyEntry = [[KeychainSyncingOverIDSProxy idsProxy].monitor objectForKey:key];
 341              if(keyEntry == nil){
 342                  [self initializeKeyEntry: key];
 343              }
 344              else{
 345                  NSNumber *penalty_timeout = [keyEntry objectForKey:kMonitorPenaltyBoxKey];
 346                  NSDate *lastWriteTimestamp = [keyEntry objectForKey:kMonitorLastWriteTimestamp];
 347                  NSMutableDictionary *timeTable = [keyEntry objectForKey: kMonitorTimeTable];
 348                  NSNumber *existingWrites = [keyEntry objectForKey: kMonitorConsecutiveWrites];
 349                  NSDate *currentTime = [NSDate date];
 350
 351                  //record the write happened in our timetable structure
 352                  [self recordTimestampForAppropriateInterval:&timeTable key:key consecutiveWrites:&existingWrites];
 353
 354                  int consecutiveWrites = [existingWrites intValue];
 355                  secnotice("backoff","consecutive writes: %d", consecutiveWrites);
 356                  [keyEntry setObject:existingWrites forKey:kMonitorConsecutiveWrites];
 357                  [keyEntry setObject:timeTable forKey:kMonitorTimeTable];
 358                  [keyEntry setObject:currentTime forKey:kMonitorLastWriteTimestamp];
 359                  [[KeychainSyncingOverIDSProxy idsProxy].monitor setObject:keyEntry forKey:key];
 360
 361                  if( (penalty_timeout && [penalty_timeout intValue] != 0 ) || ((double)[currentTime timeIntervalSinceDate: lastWriteTimestamp] <= 60 && consecutiveWrites >= 5)){
 362
 363                      if( (penalty_timeout == nil || [penalty_timeout intValue] == 0) && consecutiveWrites == 5){
 364                          secnotice("backoff","written for 5 consecutive minutes, time to start throttling");
 365                         [self increasePenalty:penalty_timeout key:key keyEntry:&keyEntry deviceName:name peerID:peerid];
 366                      }
 367                      else
 368                          secnotice("backoff","monitor: keys have been written for 5 or more minutes, recording we wrote during timeout");
 369
 370                      //record we wrote during a timeout
 371                      [keyEntry setObject: @"YES" forKey:kMonitorDidWriteDuringPenalty];
 372                  }
 373                  else if((double)[currentTime timeIntervalSinceDate: lastWriteTimestamp] <= 60 && consecutiveWrites < 5){
 374                      //for debugging purposes
 375                      secnotice("backoff","monitor: still writing freely");
 376                      [keyEntry setObject: @"NO" forKey:kMonitorDidWriteDuringPenalty];
 377                  }
 378                  else if([penalty_timeout intValue] != 0 && ((double)[currentTime timeIntervalSinceDate: lastWriteTimestamp] > 60 && consecutiveWrites > 5) ){
 379
 380                      //encountered a write even though we're in throttle mode
 381                      [keyEntry setObject: @"YES" forKey:kMonitorDidWriteDuringPenalty];
 382                  }
 383              }
 384          }];
 385     }
 386 }
 387
 388 - (NSDictionary*)filterForWritableValues:(NSDictionary *)values
 389 {
 390     secnotice("backoff", "filterForWritableValues: %@", values);
 391     NSMutableDictionary *keyEntry_operationType = [[KeychainSyncingOverIDSProxy idsProxy].monitor objectForKey:@"IDSMessageOperation"];
 392
 393     secnotice("backoff", "keyEntry_operationType: %@", keyEntry_operationType);
 394
 395     NSNumber *penalty = [keyEntry_operationType objectForKey:kMonitorPenaltyBoxKey];
 396
 397     if(penalty && [penalty intValue] != 0){
 398
 399         NSMutableArray *queuedMessage = [[KeychainSyncingOverIDSProxy idsProxy].monitor objectForKey:kMonitorMessageQueue];
 400         if(queuedMessage == nil)
 401             queuedMessage = [[NSMutableArray alloc] initWithCapacity:queue_depth];
 402
 403         secnotice("backoff", "writing to queuedMessages: %@", queuedMessage);
 404
 405         if([queuedMessage count] == 0)
 406             [queuedMessage addObject:values];
 407         else
 408             [queuedMessage replaceObjectAtIndex:(queue_depth-1) withObject: values];
 409
 410         [[KeychainSyncingOverIDSProxy idsProxy].monitor setObject:queuedMessage forKey:kMonitorMessageQueue];
 411         return NULL;
 412     }
 413
 414     return values;
 415 }
 416
 417 @end