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