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