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