keychain/ckks/RateLimiter.m

   1 /*
   2  * Copyright (c) 2017 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 #import "RateLimiter.h"
  25 #import <utilities/debugging.h>
  26 #import "sec_action.h"
  27 #import <CoreFoundation/CFPreferences.h>   // For clarity. Also included in debugging.h
  28
  29 #if !TARGET_OS_BRIDGE
  30 #import <WirelessDiagnostics/WirelessDiagnostics.h>
  31 #import "keychain/analytics/awd/AWDMetricIds_Keychain.h"
  32 #import "keychain/analytics/awd/AWDKeychainCKKSRateLimiterOverload.h"
  33 #import "keychain/analytics/awd/AWDKeychainCKKSRateLimiterTopWriters.h"
  34 #import "keychain/analytics/awd/AWDKeychainCKKSRateLimiterAggregatedScores.h"
  35 #endif
  36
  37 @interface RateLimiter()
  38 @property (readwrite, nonatomic) NSDictionary *config;
  39 @property (nonatomic) NSArray<NSMutableDictionary<NSString *, NSDate *> *> *groups;
  40 @property (nonatomic) NSDate *lastJudgment;
  41 @property (nonatomic) NSDate *overloadUntil;
  42 @property (nonatomic) NSString *assetType;
  43 #if !TARGET_OS_BRIDGE
  44 @property (nonatomic) NSMutableArray<NSNumber *> *badnessData;
  45 @property (nonatomic) AWDServerConnection *awdConnection;
  46 #endif
  47 @end
  48
  49 @implementation RateLimiter
  50
  51 - (instancetype)initWithConfig:(NSDictionary *)config {
  52     self = [super init];
  53     if (self) {
  54         _config = config;
  55         _assetType = nil;
  56         [self reset];
  57         [self setUpAwdMetrics];
  58     }
  59     return self;
  60 }
  61
  62 - (instancetype)initWithPlistFromURL:(NSURL *)url {
  63     self = [super init];
  64     if (self) {
  65         _config = [NSDictionary dictionaryWithContentsOfURL:url];
  66         if (!_config) {
  67             secerror("RateLimiter[?]: could not read config from %@", url);
  68             return nil;
  69         }
  70         _assetType = nil;
  71         [self reset];
  72         [self setUpAwdMetrics];
  73     }
  74     return self;
  75 }
  76
  77 // TODO implement MobileAsset loading
  78 - (instancetype)initWithAssetType:(NSString *)type {
  79     return nil;
  80 }
  81
  82 - (instancetype)initWithCoder:(NSCoder *)coder {
  83     if (!coder) {
  84         return nil;
  85     }
  86     self = [super init];
  87     if (self) {
  88         _groups = [coder decodeObjectOfClasses:[NSSet setWithObjects: [NSArray class],
  89                                                                       [NSMutableDictionary class],
  90                                                                       [NSString class],
  91                                                                       [NSDate class],
  92                                                                       nil]
  93                                         forKey:@"RLgroups"];
  94         _overloadUntil = [coder decodeObjectOfClass:[NSDate class] forKey:@"RLoverLoadedUntil"];
  95         _lastJudgment = [coder decodeObjectOfClass:[NSDate class] forKey:@"RLlastJudgment"];
  96         _assetType = [coder decodeObjectOfClass:[NSString class] forKey:@"RLassetType"];
  97 #if !TARGET_OS_BRIDGE
  98         _badnessData = [coder decodeObjectOfClasses:[NSSet setWithObjects: [NSArray class],
  99                                                                            [NSNumber class],
 100                                                                            nil]
 101                                              forKey:@"RLbadnessData"];
 102 #endif
 103         if (!_assetType) {
 104             // This list of types might be wrong. Be careful.
 105             _config = [coder decodeObjectOfClasses:[NSSet setWithObjects: [NSMutableArray class],
 106                                                                           [NSDictionary class],
 107                                                                           [NSString class],
 108                                                                           [NSNumber class],
 109                                                                           [NSDate class],
 110                                                                           nil]
 111                                             forKey:@"RLconfig"];
 112         }
 113         [self setUpAwdMetrics];
 114     }
 115     return self;
 116 }
 117
 118 - (NSInteger)judge:(id _Nonnull)obj at:(NSDate * _Nonnull)time limitTime:(NSDate * _Nullable __autoreleasing * _Nonnull)limitTime {
 119
 120     //sudo defaults write /Library/Preferences/com.apple.security DisableKeychainRateLimiting -bool YES
 121     NSNumber *disabled = CFBridgingRelease(CFPreferencesCopyValue(CFSTR("DisableKeychainRateLimiting"),
 122                                                                   CFSTR("com.apple.security"),
 123                                                                   kCFPreferencesAnyUser, kCFPreferencesAnyHost));
 124     if ([disabled isKindOfClass:[NSNumber class]] && [disabled boolValue] == YES) {
 125         static dispatch_once_t token;
 126         static sec_action_t action;
 127         dispatch_once(&token, ^{
 128             action = sec_action_create("ratelimiterdisabledlogevent", 60);
 129             sec_action_set_handler(action, ^{
 130                 secnotice("ratelimit", "Rate limiting disabled, returning automatic all-clear");
 131           });
 132         });
 133         sec_action_perform(action);
 134
 135         *limitTime = nil;
 136         return RateLimiterBadnessClear;
 137     }
 138
 139     RateLimiterBadness badness = RateLimiterBadnessClear;
 140
 141     if (self.overloadUntil) {
 142         if ([time timeIntervalSinceDate:self.overloadUntil] >= 0) {
 143             [self trim:time];
 144         }
 145         if (self.overloadUntil) {
 146             *limitTime = self.overloadUntil;
 147             badness = RateLimiterBadnessOverloaded;
 148         }
 149     }
 150
 151     if (badness == RateLimiterBadnessClear &&
 152         ((self.lastJudgment && [time timeIntervalSinceDate:self.lastJudgment] > [self.config[@"general"][@"maxItemAge"] intValue]) ||
 153         [self stateSize] > [self.config[@"general"][@"maxStateSize"] unsignedIntegerValue])) {
 154         [self trim:time];
 155         if (self.overloadUntil) {
 156             *limitTime = self.overloadUntil;
 157             badness = RateLimiterBadnessOverloaded;
 158         }
 159     }
 160
 161     if (badness != RateLimiterBadnessClear) {
 162 #if !TARGET_OS_BRIDGE
 163         self.badnessData[badness] = @(self.badnessData[badness].intValue + 1);
 164 #endif
 165         return badness;
 166     }
 167
 168     NSDate *resultTime = [NSDate distantPast];
 169     for (unsigned long idx = 0; idx < self.groups.count; ++idx) {
 170         NSDictionary *groupConfig = self.config[@"groups"][idx];
 171         NSString *name;
 172         if (idx == 0) {
 173             name = groupConfig[@"property"];    // global bucket, does not correspond to object property
 174         } else {
 175             name = [self getPropertyValue:groupConfig[@"property"] object:obj];
 176         }
 177         // Pretend this property doesn't exist. Should be returning an error instead but currently it's only used with
 178         // approved properties 'accessGroup' and 'uuid' and if the item doesn't have either it's sad times anyway.
 179         // <rdar://problem/33434425> Improve rate limiter error handling
 180         if (!name) {
 181             secerror("RateLimiter[%@]: Got nil instead of property named %@", self.config[@"general"][@"name"], groupConfig[@"property"]);
 182             continue;
 183         }
 184         NSDate *singleTokenTime = [self consumeTokenFromBucket:self.groups[idx]
 185                                                         config:groupConfig
 186                                                           name:name
 187                                                             at:time];
 188         if (singleTokenTime) {
 189             resultTime = [resultTime laterDate:singleTokenTime];
 190             badness = MAX([groupConfig[@"badness"] intValue], badness);
 191         }
 192     }
 193
 194 #if !TARGET_OS_BRIDGE
 195     self.badnessData[badness] = @(self.badnessData[badness].intValue + 1);
 196 #endif
 197     *limitTime = badness == RateLimiterBadnessClear ? nil : resultTime;
 198     self.lastJudgment = time;
 199     return badness;
 200 }
 201
 202 - (NSDate *)consumeTokenFromBucket:(NSMutableDictionary *)group
 203                             config:(NSDictionary *)config
 204                               name:(NSString *)name
 205                                 at:(NSDate *)time {
 206     NSDate *threshold = [time dateByAddingTimeInterval:-([config[@"capacity"] intValue] * [config[@"rate"] intValue])];
 207     NSDate *bucket = group[name];
 208
 209     if (!bucket || [bucket timeIntervalSinceDate:threshold] < 0) {
 210         bucket = threshold;
 211     }
 212
 213     // Implicitly track the number of tokens in the bucket.
 214     // "Would the token I need have been generated in the past or in the future?"
 215     bucket = [bucket dateByAddingTimeInterval:[config[@"rate"] intValue]];
 216     group[name] = bucket;
 217     return ([bucket timeIntervalSinceDate:time] <= 0) ? nil : bucket;
 218 }
 219
 220 - (BOOL)isEqual:(id)object {
 221     if (![object isKindOfClass:[RateLimiter class]]) {
 222         return NO;
 223     }
 224     RateLimiter *other = (RateLimiter *)object;
 225     return ([self.config isEqual:other.config] &&
 226             [self.groups isEqual:other.groups] &&
 227             [self.lastJudgment isEqual:other.lastJudgment] &&
 228             ((self.overloadUntil == nil && other.overloadUntil == nil) || [self.overloadUntil isEqual:other.overloadUntil]) &&
 229             ((self.assetType == nil && other.assetType == nil) || [self.assetType isEqualToString:other.assetType]));
 230 }
 231
 232 - (void)reset {
 233     NSMutableArray *newgroups = [NSMutableArray new];
 234     for (unsigned long idx = 0; idx < [self.config[@"groups"] count]; ++idx) {
 235         [newgroups addObject:[NSMutableDictionary new]];
 236     }
 237     self.groups = newgroups;
 238     self.lastJudgment = [NSDate distantPast];   // will cause extraneous trim on first judgment but on empty groups
 239     self.overloadUntil = nil;
 240 #if !TARGET_OS_BRIDGE
 241     // Corresponds to the number of RateLimiterBadness enum values
 242     self.badnessData = [[NSMutableArray alloc] initWithObjects:@0, @0, @0, @0, @0, nil];
 243 #endif
 244 }
 245
 246 - (void)trim:(NSDate *)time {
 247     int threshold = [self.config[@"general"][@"maxItemAge"] intValue];
 248     for (NSMutableDictionary *group in self.groups) {
 249         NSSet *toRemove = [group keysOfEntriesPassingTest:^BOOL(NSString *key, NSDate *obj, BOOL *stop) {
 250             return [time timeIntervalSinceDate:obj] > threshold;
 251         }];
 252         [group removeObjectsForKeys:[toRemove allObjects]];
 253     }
 254
 255     if ([self stateSize] > [self.config[@"general"][@"maxStateSize"] unsignedIntegerValue]) {
 256         // Trimming did not reduce size (enough), we need to take measures
 257         self.overloadUntil = [time dateByAddingTimeInterval:[self.config[@"general"][@"overloadDuration"] intValue]];
 258         secerror("RateLimiter[%@] state size %lu exceeds max %lu, overloaded until %@",
 259                  self.config[@"general"][@"name"],
 260                  (unsigned long)[self stateSize],
 261                  [self.config[@"general"][@"maxStateSize"] unsignedLongValue],
 262                  self.overloadUntil);
 263 #if !TARGET_OS_BRIDGE
 264         AWDKeychainCKKSRateLimiterOverload *metric = [AWDKeychainCKKSRateLimiterOverload new];
 265         metric.ratelimitertype = self.config[@"general"][@"name"];
 266         AWDPostMetric(AWDComponentId_Keychain, metric);
 267 #endif
 268     } else {
 269         self.overloadUntil = nil;
 270     }
 271 }
 272
 273 - (NSUInteger)stateSize {
 274     NSUInteger size = 0;
 275     for (NSMutableDictionary *group in self.groups) {
 276         size += [group count];
 277     }
 278     return size;
 279 }
 280
 281 - (NSString *)diagnostics {
 282     return [NSString stringWithFormat:@"RateLimiter[%@]\nconfig:%@\ngroups:%@\noverloaded:%@\nlastJudgment:%@",
 283             self.config[@"general"][@"name"],
 284             self.config,
 285             self.groups,
 286             self.overloadUntil,
 287             self.lastJudgment];
 288 }
 289
 290 //This could probably be improved, rdar://problem/33416163
 291 - (NSString *)getPropertyValue:(NSString *)selectorString object:(id)obj {
 292     if ([selectorString isEqualToString:@"accessGroup"] ||
 293         [selectorString isEqualToString:@"uuid"]) {
 294
 295         SEL selector = NSSelectorFromString(selectorString);
 296         IMP imp = [obj methodForSelector:selector];
 297         NSString *(*func)(id, SEL) = (void *)imp;
 298         return func(obj, selector);
 299     } else {
 300         seccritical("RateLimter[%@]: \"%@\" is not an approved selector string", self.config[@"general"][@"name"], selectorString);
 301         return nil;
 302     }
 303 }
 304
 305 - (void)encodeWithCoder:(NSCoder *)coder {
 306     [coder encodeObject:_groups forKey:@"RLgroups"];
 307     [coder encodeObject:_overloadUntil forKey:@"RLoverloadedUntil"];
 308     [coder encodeObject:_lastJudgment forKey:@"RLlastJudgment"];
 309     [coder encodeObject:_assetType forKey:@"RLassetType"];
 310     if (!_assetType) {
 311         [coder encodeObject:_config forKey:@"RLconfig"];
 312     }
 313 #if !TARGET_OS_BRIDGE
 314     [coder encodeObject:_badnessData forKey:@"RLbadnessData"];
 315 #endif
 316 }
 317
 318 + (BOOL)supportsSecureCoding {
 319     return YES;
 320 }
 321
 322 - (NSArray *)topOffenders:(int)num {
 323     NSInteger idx = [self.config[@"general"][@"topOffendersPropertyIndex"] integerValue];
 324     NSDate *now = [NSDate date];
 325     NSSet *contenderkeys = [self.groups[idx] keysOfEntriesPassingTest:^BOOL(NSString *key, NSDate *obj, BOOL *stop) {
 326         return [now timeIntervalSinceDate:obj] > 0 ? YES : NO;
 327     }];
 328     if ([contenderkeys count] == 0) {
 329         return [NSArray new];
 330     }
 331     NSDictionary *contenders = [NSDictionary dictionaryWithObjects:[self.groups[idx] objectsForKeys:[contenderkeys allObjects]
 332                                                                                      notFoundMarker:[NSDate date]]
 333                                                            forKeys:[contenderkeys allObjects]];
 334     return [[[contenders keysSortedByValueUsingSelector:@selector(compare:)] reverseObjectEnumerator] allObjects];
 335 }
 336
 337 - (void)setUpAwdMetrics {
 338 #if !TARGET_OS_BRIDGE
 339     self.awdConnection = [[AWDServerConnection alloc] initWithComponentId:AWDComponentId_Keychain];
 340
 341     [self.awdConnection registerQueriableMetric:AWDMetricId_Keychain_CKKSRateLimiterTopWriters callback:^(UInt32 metricId) {
 342         AWDKeychainCKKSRateLimiterTopWriters *metric = [AWDKeychainCKKSRateLimiterTopWriters new];
 343         NSArray *offenders = [self topOffenders:3];
 344         for (NSString *offender in offenders) {
 345             [metric addWriter:offender];
 346         }
 347         metric.ratelimitertype = self.config[@"general"][@"name"];
 348         AWDPostMetric(metricId, metric);
 349     }];
 350
 351     [self.awdConnection registerQueriableMetric:AWDMetricId_Keychain_CKKSRateLimiterAggregatedScores callback:^(UInt32 metricId) {
 352         AWDKeychainCKKSRateLimiterAggregatedScores *metric = [AWDKeychainCKKSRateLimiterAggregatedScores new];
 353         for (NSNumber *num in self.badnessData) {
 354             [metric addData:[num unsignedIntValue]];
 355         }
 356         metric.ratelimitertype = self.config[@"general"][@"name"];
 357         AWDPostMetric(metricId, metric);
 358         // Corresponds to the number of RateLimiterBadness enum values
 359         self.badnessData = [[NSMutableArray alloc] initWithObjects:@0, @0, @0, @0, @0, nil];
 360     }];
 361 #endif
 362 }
 363
 364 @end