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