Monkey.m   [plain text]

//
// Monkey.m
// Security
//
// Created by Ben Williamson on 6/1/17.
//
//

#import "Monkey.h"
#import "Config.h"
#import "Keychain.h"

#import <stdio.h>
#import <stdlib.h>

@interface Monkey ()

@property (nonatomic, strong) Config *config;

// Names that we could choose from when adding a new item.
// When we add an item its name is moved to usedNames.
@property (nonatomic, strong) NSMutableArray<NSString *> *freeNames;

// Names and persistent references of the items we have written, which we can update or delete.
// When we delete an item its name is moved to freeNames.
@property (nonatomic, strong) NSMutableArray<NSMutableArray *> *usedNames;

@end

@implementation Monkey

- (instancetype)initWithConfig:(Config *)config
{
if (self = [super init]) {
_config = config;
_freeNames = [NSMutableArray arrayWithCapacity:config.distinctNames];
_usedNames = [NSMutableArray arrayWithCapacity:config.distinctNames];
for (unsigned i = 0; i < config.distinctNames; i++) {
if (config.name) {
[_freeNames addObject:[NSString stringWithFormat:@"item-%@-%u", config.name, i]];
} else {
[_freeNames addObject:[NSString stringWithFormat:@"item-%u", i]];
}
}
}
return self;
}

- (void)advanceOneStep
{
static const int tryLimit = 1000;
for (int tries = 0; tries < tryLimit; tries++) {
if ([self tryAdvanceOneStep]) {
self.step++;
return;
}
}
printf("Chose %d random actions but none of them made sense, giving up!\n", tryLimit);
printf("This is an internal failure of the manifeststresstest tool, not the system under test.\n");
NSLog(@"Chose %d random actions but none of them made sense, giving up!", tryLimit);
exit(1);
}

// return YES if it actually took a step, NO if the randomly chosen action was invalid
- (BOOL)tryAdvanceOneStep
{
unsigned totalWeight =
self.config.addItemWeight +
self.config.updateNameWeight +
self.config.updateDataWeight +
self.config.updateNameAndDataWeight +
self.config.deleteItemWeight;

if (totalWeight == 0) {
printf("Invalid manifeststresstest configuration:\n"
"At least one weight must be nonzero, or else we cannot choose any action.\n");
exit(1);
}
if (totalWeight > RAND_MAX) {
printf("Invalid manifeststresstest configuration:\n"
"The total of the weights must not exceed RAND_MAX == %d.\n", RAND_MAX);
exit(1);
}
unsigned r = random() % totalWeight;

if (r < self.config.addItemWeight) {
return [self addItem];
}
r -= self.config.addItemWeight;

if (r < self.config.updateNameWeight) {
return [self updateNameAndValue:NO];
}
r -= self.config.updateNameWeight;

if (r < self.config.updateDataWeight) {
return [self updateValue];
}
r -= self.config.updateDataWeight;

if (r < self.config.updateNameAndDataWeight) {
return [self updateNameAndValue:YES];
}
r -= self.config.updateNameAndDataWeight;

if (r < self.config.deleteItemWeight) {
return [self deleteItem];
}
NSAssert(false, @"Chosen random number was beyond totalWeight?!?");
return NO;
}

- (NSString *)randomValue
{
if (0 == self.config.distinctValues) {
printf("Invalid manifeststresstest configuration:\n"
"Must allow a nonzero number of distinct values.\n");
exit(1);
}
unsigned n = random() % self.config.distinctValues;
return [NSString stringWithFormat:@"data-%u", n];
}

- (NSString *)prefix
{
return [NSString stringWithFormat:@"[step:%d items:%d dup:%d gone:%d]",
self.step,
self.itemCount,
self.addDuplicateCounter,
self.notFoundCounter];
}

- (void)unexpectedError:(OSStatus)status
{
NSLog(@"Unexpected error %d at step %d", (int)status, self.step);
exit(1);
}

- (BOOL)addItem
{
if ([self.usedNames count] >= self.config.maxItems) {
return NO;
}
NSUInteger freeCount = [self.freeNames count];
if (freeCount == 0) {
return NO;
}
NSUInteger index = random() % freeCount;
NSString *name = self.freeNames[index];
NSString *value = [self randomValue];

NSLog(@"%@ addItem in %@ %@ = %@", [self prefix], self.config.view, name, value);
NSArray *itemRef = nil;
OSStatus status = [self.keychain addItem:name value:value view:self.config.view pRef:&itemRef];
switch (status) {
case errSecSuccess:
[self.freeNames removeObjectAtIndex:index];
[self.usedNames addObject:[NSMutableArray arrayWithArray:@[name, itemRef]]];

unsigned usedCount = (unsigned)[self.usedNames count];
if (self.peakItems < usedCount) {
self.peakItems = usedCount;
}
break;
case errSecDuplicateItem:
self.addDuplicateCounter++;
break;
default:
[self unexpectedError:status];
}
return YES;
}

- (BOOL)updateNameAndValue:(BOOL)updateValue
{
NSUInteger freeCount = [self.freeNames count];
NSUInteger usedCount = [self.usedNames count];
if (usedCount == 0 || freeCount == 0) {
return NO;
}
NSUInteger usedIndex = random() % usedCount;
NSUInteger freeIndex = random() % freeCount;
NSMutableArray *oldItem = self.usedNames[usedIndex];
NSArray *oldRef = oldItem[1];
NSString *oldName = oldItem[0];
NSString *newName = self.freeNames[freeIndex];

OSStatus status;
if (updateValue) {
NSString *value = [self randomValue];
NSLog(@"%@ updateNameAndValue %@(%@) -> %@ = %@\n", [self prefix], oldName, oldRef, newName, value);
status = [self.keychain updateItem:oldRef newName:newName newValue:value];
} else {
NSLog(@"%@ updateName %@(%@) -> %@\n", [self prefix], oldName, oldRef, newName);
status = [self.keychain updateItem:oldRef newName:newName];
}
switch (status) {
case errSecSuccess:
/* Update tracking arrays */
[self.freeNames removeObject:newName];
[self.freeNames addObject:oldName];
self.usedNames[usedIndex][0] = newName;
break;
case errSecItemNotFound:
/* Update tracking arrays (someone else deleted this item) */
[self.usedNames removeObject:oldItem];
[self.freeNames addObject:oldName];
self.notFoundCounter++;
break;
case errSecDuplicateItem:
self.addDuplicateCounter++;
// newName already exists, which means our attempted updateItem operation
// did not rename oldName to newName, so the item still has oldName.
// No action required.
break;
default:
[self unexpectedError:status];
}
return YES;
}

- (BOOL)updateValue
{
NSUInteger usedCount = [self.usedNames count];
if (usedCount == 0) {
return NO;
}
NSUInteger usedIndex = random() % usedCount;
NSArray *item = self.usedNames[usedIndex];

NSString *value = [self randomValue];

NSLog(@"%@ updateValue %@(%@) = %@", [self prefix], item[0], item[1], value);
OSStatus status = [self.keychain updateItem:item[1] newValue:value];
switch (status) {
case errSecSuccess:
break;
case errSecItemNotFound:
self.notFoundCounter++;
break;
default:
[self unexpectedError:status];
}
return YES;
}

- (BOOL)deleteItem
{
NSUInteger usedCount = [self.usedNames count];
if (usedCount == 0) {
return NO;
}
NSUInteger usedIndex = random() % usedCount;
NSArray *item = self.usedNames[usedIndex];

NSLog(@"%@ deleteItem %@(%@)", [self prefix], item[0], item[1]);
OSStatus status = [self.keychain deleteItem:item[1]];
switch (status) {
case errSecItemNotFound:
/* someone else deleted this item */
self.notFoundCounter++;
/* fall through */
case errSecSuccess:
[self.usedNames removeObjectAtIndex:usedIndex];
[self.freeNames addObject:item[0]];
break;
default:
[self unexpectedError:status];
}
return YES;
}

- (unsigned)itemCount
{
return (unsigned)[self.usedNames count];
}

- (void)cleanup
{
for (NSArray *item in self.usedNames) {
NSLog(@"cleanup deleting %@(%@)", item[0], item[1]);
[self.keychain deleteItem:item[1]];
}
}

@end