RegressionTests/manifeststresstest/Monkey.m

   1 //
   2 //  Monkey.m
   3 //  Security
   4 //
   5 //  Created by Ben Williamson on 6/1/17.
   6 //
   7 //
   8
   9 #import "Monkey.h"
  10 #import "Config.h"
  11 #import "Keychain.h"
  12
  13 #import <stdio.h>
  14 #import <stdlib.h>
  15
  16
  17 @interface Monkey ()
  18
  19 @property (nonatomic, strong) Config *config;
  20
  21 // Names that we could choose from when adding a new item.
  22 // When we add an item its name is moved to usedNames.
  23 @property (nonatomic, strong) NSMutableArray<NSString *> *freeNames;
  24
  25 // Names and persistent references of the items we have written, which we can update or delete.
  26 // When we delete an item its name is moved to freeNames.
  27 @property (nonatomic, strong) NSMutableArray<NSMutableArray *> *usedNames;
  28
  29 @end
  30
  31
  32 @implementation Monkey
  33
  34 - (instancetype)initWithConfig:(Config *)config
  35 {
  36     if (self = [super init]) {
  37         _config = config;
  38         _freeNames = [NSMutableArray arrayWithCapacity:config.distinctNames];
  39         _usedNames = [NSMutableArray arrayWithCapacity:config.distinctNames];
  40         for (unsigned i = 0; i < config.distinctNames; i++) {
  41             if (config.name) {
  42                 [_freeNames addObject:[NSString stringWithFormat:@"item-%@-%u", config.name, i]];
  43             } else {
  44                 [_freeNames addObject:[NSString stringWithFormat:@"item-%u", i]];
  45             }
  46         }
  47     }
  48     return self;
  49 }
  50
  51 - (void)advanceOneStep
  52 {
  53     static const int tryLimit = 1000;
  54     for (int tries = 0; tries < tryLimit; tries++) {
  55         if ([self tryAdvanceOneStep]) {
  56             self.step++;
  57             return;
  58         }
  59     }
  60     printf("Chose %d random actions but none of them made sense, giving up!\n", tryLimit);
  61     printf("This is an internal failure of the manifeststresstest tool, not the system under test.\n");
  62     NSLog(@"Chose %d random actions but none of them made sense, giving up!", tryLimit);
  63     exit(1);
  64 }
  65
  66 // return YES if it actually took a step, NO if the randomly chosen action was invalid
  67 - (BOOL)tryAdvanceOneStep
  68 {
  69     unsigned totalWeight =
  70         self.config.addItemWeight +
  71         self.config.updateNameWeight +
  72         self.config.updateDataWeight +
  73         self.config.updateNameAndDataWeight +
  74         self.config.deleteItemWeight;
  75
  76     if (totalWeight == 0) {
  77         printf("Invalid manifeststresstest configuration:\n"
  78                "At least one weight must be nonzero, or else we cannot choose any action.\n");
  79         exit(1);
  80     }
  81     if (totalWeight > RAND_MAX) {
  82         printf("Invalid manifeststresstest configuration:\n"
  83                "The total of the weights must not exceed RAND_MAX == %d.\n", RAND_MAX);
  84         exit(1);
  85     }
  86     unsigned r = random() % totalWeight;
  87
  88     if (r < self.config.addItemWeight) {
  89         return [self addItem];
  90     }
  91     r -= self.config.addItemWeight;
  92
  93     if (r < self.config.updateNameWeight) {
  94         return [self updateNameAndValue:NO];
  95     }
  96     r -= self.config.updateNameWeight;
  97
  98     if (r < self.config.updateDataWeight) {
  99         return [self updateValue];
 100     }
 101     r -= self.config.updateDataWeight;
 102
 103     if (r < self.config.updateNameAndDataWeight) {
 104         return [self updateNameAndValue:YES];
 105     }
 106     r -= self.config.updateNameAndDataWeight;
 107
 108     if (r < self.config.deleteItemWeight) {
 109         return [self deleteItem];
 110     }
 111     NSAssert(false, @"Chosen random number was beyond totalWeight?!?");
 112     return NO;
 113 }
 114
 115 - (NSString *)randomValue
 116 {
 117     if (0 == self.config.distinctValues) {
 118         printf("Invalid manifeststresstest configuration:\n"
 119                "Must allow a nonzero number of distinct values.\n");
 120         exit(1);
 121     }
 122     unsigned n = random() % self.config.distinctValues;
 123     return [NSString stringWithFormat:@"data-%u", n];
 124 }
 125
 126 - (NSString *)prefix
 127 {
 128     return [NSString stringWithFormat:@"[step:%d items:%d dup:%d gone:%d]",
 129             self.step,
 130             self.itemCount,
 131             self.addDuplicateCounter,
 132             self.notFoundCounter];
 133 }
 134
 135 - (void)unexpectedError:(OSStatus)status
 136 {
 137     NSLog(@"Unexpected error %d at step %d", (int)status, self.step);
 138     exit(1);
 139 }
 140
 141 - (BOOL)addItem
 142 {
 143     if ([self.usedNames count] >= self.config.maxItems) {
 144         return NO;
 145     }
 146     NSUInteger freeCount = [self.freeNames count];
 147     if (freeCount == 0) {
 148         return NO;
 149     }
 150     NSUInteger index = random() % freeCount;
 151     NSString *name = self.freeNames[index];
 152     NSString *value = [self randomValue];
 153
 154     NSLog(@"%@ addItem in %@ %@ = %@", [self prefix], self.config.view, name, value);
 155     NSArray *itemRef = nil;
 156     OSStatus status = [self.keychain addItem:name value:value view:self.config.view pRef:&itemRef];
 157     switch (status) {
 158         case errSecSuccess:
 159             [self.freeNames removeObjectAtIndex:index];
 160             [self.usedNames addObject:[NSMutableArray arrayWithArray:@[name, itemRef]]];
 161
 162             unsigned usedCount = (unsigned)[self.usedNames count];
 163             if (self.peakItems < usedCount) {
 164                 self.peakItems = usedCount;
 165             }
 166             break;
 167         case errSecDuplicateItem:
 168             self.addDuplicateCounter++;
 169             break;
 170         default:
 171             [self unexpectedError:status];
 172     }
 173     return YES;
 174 }
 175
 176 - (BOOL)updateNameAndValue:(BOOL)updateValue
 177 {
 178     NSUInteger freeCount = [self.freeNames count];
 179     NSUInteger usedCount = [self.usedNames count];
 180     if (usedCount == 0 || freeCount == 0) {
 181         return NO;
 182     }
 183     NSUInteger usedIndex = random() % usedCount;
 184     NSUInteger freeIndex = random() % freeCount;
 185     NSMutableArray *oldItem = self.usedNames[usedIndex];
 186     NSArray *oldRef = oldItem[1];
 187     NSString *oldName = oldItem[0];
 188     NSString *newName = self.freeNames[freeIndex];
 189
 190     OSStatus status;
 191     if (updateValue) {
 192         NSString *value = [self randomValue];
 193         NSLog(@"%@ updateNameAndValue %@(%@) -> %@ = %@\n", [self prefix], oldName, oldRef, newName, value);
 194         status = [self.keychain updateItem:oldRef newName:newName newValue:value];
 195     } else {
 196         NSLog(@"%@ updateName %@(%@) -> %@\n", [self prefix], oldName, oldRef, newName);
 197         status = [self.keychain updateItem:oldRef newName:newName];
 198     }
 199     switch (status) {
 200         case errSecSuccess:
 201             /* Update tracking arrays */
 202             [self.freeNames removeObject:newName];
 203             [self.freeNames addObject:oldName];
 204             self.usedNames[usedIndex][0] = newName;
 205             break;
 206         case errSecItemNotFound:
 207             /* Update tracking arrays (someone else deleted this item) */
 208             [self.usedNames removeObject:oldItem];
 209             [self.freeNames addObject:oldName];
 210             self.notFoundCounter++;
 211             break;
 212         case errSecDuplicateItem:
 213             self.addDuplicateCounter++;
 214             // newName already exists, which means our attempted updateItem operation
 215             // did not rename oldName to newName, so the item still has oldName.
 216             // No action required.
 217             break;
 218         default:
 219             [self unexpectedError:status];
 220     }
 221     return YES;
 222 }
 223
 224 - (BOOL)updateValue
 225 {
 226     NSUInteger usedCount = [self.usedNames count];
 227     if (usedCount == 0) {
 228         return NO;
 229     }
 230     NSUInteger usedIndex = random() % usedCount;
 231     NSArray *item = self.usedNames[usedIndex];
 232
 233     NSString *value = [self randomValue];
 234
 235     NSLog(@"%@ updateValue %@(%@) = %@", [self prefix], item[0], item[1], value);
 236     OSStatus status = [self.keychain updateItem:item[1] newValue:value];
 237     switch (status) {
 238         case errSecSuccess:
 239             break;
 240         case errSecItemNotFound:
 241             self.notFoundCounter++;
 242             break;
 243         default:
 244             [self unexpectedError:status];
 245     }
 246     return YES;
 247 }
 248
 249 - (BOOL)deleteItem
 250 {
 251     NSUInteger usedCount = [self.usedNames count];
 252     if (usedCount == 0) {
 253         return NO;
 254     }
 255     NSUInteger usedIndex = random() % usedCount;
 256     NSArray *item = self.usedNames[usedIndex];
 257
 258     NSLog(@"%@ deleteItem %@(%@)", [self prefix], item[0], item[1]);
 259     OSStatus status = [self.keychain deleteItem:item[1]];
 260     switch (status) {
 261         case errSecItemNotFound:
 262             /* someone else deleted this item */
 263             self.notFoundCounter++;
 264             /* fall through */
 265         case errSecSuccess:
 266             [self.usedNames removeObjectAtIndex:usedIndex];
 267             [self.freeNames addObject:item[0]];
 268             break;
 269         default:
 270             [self unexpectedError:status];
 271     }
 272     return YES;
 273 }
 274
 275 - (unsigned)itemCount
 276 {
 277     return (unsigned)[self.usedNames count];
 278 }
 279
 280 - (void)cleanup
 281 {
 282     for (NSArray *item in self.usedNames) {
 283         NSLog(@"cleanup deleting %@(%@)", item[0], item[1]);
 284         [self.keychain deleteItem:item[1]];
 285     }
 286 }
 287
 288 @end