Peach.mutator

1 2 ''' 3 Mutator base classes and interfaces. 4 5 A Mutator implements a method of mutating data/state for a Peach 2 6 fuzzer. For example a mutator might change the state flow defined 7 by a Peach fuzzer. Another mutator might mutate data based on 8 known relationships. Another mutator might perform numerical type 9 tests against fields. 10 11 @author: Michael Eddington 12 @version: $Id: mutator.py 1052 2008-07-17 06:46:50Z meddingt $ 13 ''' 14 15 # 16 # Copyright (c) 2008 Michael Eddington 17 # 18 # Permission is hereby granted, free of charge, to any person obtaining a copy 19 # of this software and associated documentation files (the "Software"), to deal 20 # in the Software without restriction, including without limitation the rights 21 # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 22 # copies of the Software, and to permit persons to whom the Software is 23 # furnished to do so, subject to the following conditions: 24 # 25 # The above copyright notice and this permission notice shall be included in 26 # all copies or substantial portions of the Software. 27 # 28 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 29 # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 30 # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 31 # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 32 # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 33 # OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 34 # SOFTWARE. 35 # 36 37 # Authors: 38 # Michael Eddington (mike@phed.org) 39 40 # $Id: mutator.py 1052 2008-07-17 06:46:50Z meddingt $ 41 42 import random, threading 43 import pickle, types 44 from Peach.Engine.dom import * 45

46 -class Mutator:

47 ''' 48 A Mutator implements a method of mutating data/state for a Peach 2 49 fuzzer. For example a mutator might change the state flow defined 50 by a Peach fuzzer. Another mutator might mutate data based on 51 known relationships. Another mutator might perform numerical type 52 tests against fields. 53 ''' 54 55 elementType = "mutator" 56 dataTypes = ['template', 'string', 'number', 'flags', 'choice', 'sequence', 'blob', 'block'] 57

58 - def __init__(self):

59 self.name = "Mutator" 60 self._count = -1 61 pass

62

63 - def _getElementByName(self, node, name):

64 ''' 65 DEPRICATED! SHould say: node.findDataElementByName(name) 66 ''' 67 return node.findDataElementByName(name)

68

69 - def isFinite(self):

70 ''' 71 Some mutators could contine forever, this 72 should indicate. 73 ''' 74 return True

75

76 - def reset(self):

77 ''' 78 Reset mutator 79 ''' 80 pass

81

82 - def next(self):

83 ''' 84 Goto next mutation. When this is called 85 the state machine is updated as needed. 86 ''' 87 pass

88

89 - def getState(self):

90 ''' 91 Return a binary string that contains 92 any information about current state of 93 Mutator. This state information should be 94 enough to let the same mutator "restart" 95 and continue when setState() is called. 96 ''' 97 pass

98

99 - def setState(self, state):

100 ''' 101 Set the state of this object. Should put us 102 back in the same place as when we said 103 "getState()". 104 ''' 105 pass

106

107 - def getCount(self):

108 ''' 109 If mutator is finite than the total test count 110 can be calculated. This calculation cannot 111 occur until after the state machine has been run 112 the first time. Once the state machine has been 113 run the count can be calculated. This typically 114 occurs in a separate thread as it can take some 115 time to calculate. 116 117 This method will return -1 until a the correct 118 value has been calculated. 119 ''' 120 return self._count

121

122 - def calculateCount(self):

123 ''' 124 This method should calculate the count of this 125 mutator in a thread safe mannor. Typically 126 this method is called from a different thread. 127 It will never be called until the state machine 128 has run the first time through. 129 ''' 130 return -1

131 132 ##################################################### 133 # Callbacks when Action needs a value 134

135 - def getActionValue(self, action):

136 pass

137

138 - def getActionParamValue(self, action):

139 pass

140

141 - def getActionChangeStateValue(self, action, value):

142 pass

143 144 ##################################################### 145 # Event callbacks for state machine 146

147 - def onStateStart(self, state):

148 pass

149

150 - def onStateComplete(self, state):

151 pass

152

153 - def onActionStart(self, action):

154 pass

155

156 - def onActionComplete(self, action):

157 pass

158

159 - def onStateMachineStart(self, stateMachine):

160 pass

161

162 - def onStateMachineComplete(self, stateMachine):

163 pass

164

165 -class _MutatorCollectionState:

166 ''' 167 This class contains the needed state to seed a MutatorCollection. 168 ''' 169

170 - def __init__(self, curFinite, finiteMutatorStates, infiniteMutatorStates):

171 ''' 172 curFinite is index into finiteMutators we are at. 173 mutatorState is array of binary strings representing 174 the state of each mutator we are running. 175 ''' 176 self.curFinite = curFinite 177 self.finiteMutatorStates = finiteMutatorStates 178 self.infiniteMutatorStates = infiniteMutatorStates

179

180 -class MutatorCollection:

181 ''' 182 Aggrigated collection of mutators. 183 ''' 184

185 - def __init__(self, mutators):

186 self.name = "MutatorCollection" 187 188 # Have we cycled all finite mutators yet? 189 self._cycledAll = False 190 # Current finite cycle position 191 self._cyclePos = 0 192 193 self._mutators = mutators 194 self._finiteMutators = [] 195 self._infiniteMutators = [] 196 self._mutator = None 197 198 self._masterCount = 0 199 self._stateMasterCount = -1 200 201 for m in self._mutators: 202 if m.isFinite(): 203 self._finiteMutators.append(m) 204 else: 205 self._infiniteMutators.append(m) 206 207 # Current finite potition 208 self._curFinite = 0 209 self._maxFinite = len(self._finiteMutators) 210 self._maxInfinite = len(self._infiniteMutators) 211 212 if self._maxFinite > 0: 213 self._mutator = self._finiteMutators[0] 214 215 elif self._maxInfinite > 0: 216 self._cycledAll = True 217 self._mutator = self._getRandomInfiniteMutator() 218 219 else: 220 raise Exception("MutatorCollection: No mutators!")

221

222 - def currentMutator(self):

223 return self._mutator

224

225 - def isFinite(self):

226 ''' 227 Some mutators could contine forever, this 228 should indicate. 229 ''' 230 231 return len(self._infiniteMutators) == 0

232

233 - def reset(self):

234 ''' 235 Reset mutator 236 ''' 237 238 self._cycledAll = False 239 self._cyclePos = 0 240 self._curFinite = 0 241 242 for m in self._mutators: 243 m.reset() 244 245 if self._maxFinite > 0: 246 self._mutator = self._finiteMutators[0] 247 248 elif self._maxInfinite > 0: 249 self._cycledAll = True 250 self._mutator = self._getRandomInfiniteMutator()

251

252 - def next(self):

253 ''' 254 Goto next mutation. When this is called 255 the state machine is updated as needed. 256 ''' 257 try: 258 # Increment current mutator 259 self._mutator.next() 260 261 # If we have not cycled through all finite mutators 262 # lets do that first. This is to make sure they can 263 # all start calculating there total tests for us. 264 # 265 # Note: In the case of no finite mutators we have 266 # already set self._cycledAll to True up in the 267 # constructor and also reset() 268 if not self._cycledAll: 269 self._cyclePos += 1 270 271 if self._cyclePos >= self._maxFinite: 272 self._cycledAll = True 273 self._mutator = self._finiteMutators[self._curFinite] 274 275 else: 276 self._mutator = self._finiteMutators[self._cyclePos] 277 278 # Otherwise do the normal stuff 279 else: 280 281 # If we are out of finite mutators grab a random 282 # infinte mutator. 283 if self._curFinite >= self._maxFinite: 284 self._mutator = self._getRandomInfiniteMutator() 285 286 except MutatorCompleted: 287 288 # If we have not cycled through all finite mutators 289 # lets do that first. This is to make sure they can 290 # all start calculating there total tests for us. 291 # 292 # Note: In the case of no finite mutators we have 293 # already set self._cycledAll to True up in the 294 # constructor and also reset() 295 # 296 # We sometimes end up here if the mutator only perfomrs 297 # a single round. This will happen for things like the 298 # Null mutator or mutators that find nothing to operate 299 # on like the XmlW3CMutator which keys of <Hint>'s 300 if not self._cycledAll: 301 302 self._cyclePos += 1 303 if self._cyclePos >= self._maxFinite: 304 self._cycledAll = True 305 self._mutator = self._finiteMutators[self._curFinite] 306 307 else: 308 self._mutator = self._finiteMutators[self._cyclePos] 309 310 # Otherwise we will do the normal crazy stuff that we do :) 311 else: 312 313 # Goto next finite mutator 314 self._curFinite += 1 315 316 # See if we are are really done 317 if self._curFinite >= self._maxFinite and self._maxInfinite == 0: 318 raise MutatorCompleted() 319 320 # Grab a random infinite mutator 321 elif self._curFinite >= self._maxFinite: 322 self._mutator = self._getRandomInfiniteMutator() 323 324 # Get the new finite mutator 325 else: 326 self._mutator = self._finiteMutators[self._curFinite] 327 328 self._masterCount += 1

329

330 - def _getRandomInfiniteMutator(self):

331 ''' 332 Get a random infinite mutator. 333 ''' 334 335 idx = random.randint(0, self._maxInfinite) 336 return self._infiniteMutators[idx]

337

338 - def getState(self):

339 ''' 340 Return a binary string that contains 341 any information about current state of 342 Mutator. This state information should be 343 enough to let the same mutator "restart" 344 and continue when setState() is called. 345 ''' 346 347 return str(self._masterCount - 2)

348

349 - def setState(self, statePickle):

350 ''' 351 Set the state of this object. Should put us 352 back in the same place as when we said 353 "getState()". 354 ''' 355 self._stateMasterCount = int(statePickle) 356 try: 357 for i in xrange(self._masterCount, self._stateMasterCount): 358 self.next() 359 except: 360 pass

361

362 - def getCount(self, verbose = False):

363 ''' 364 This count will change as we go through mutators. 365 ''' 366 367 if not self.isFinite(): 368 return -1 369 370 if not self._cycledAll: 371 return -1 372 373 count = 0 374 for m in self._finiteMutators: 375 if m.getCount() > -1: 376 count += m.getCount() 377 else: 378 #print "%s not reporting" % m.name 379 return -1 380 381 if verbose: 382 for m in self._finiteMutators: 383 cnt = m.getCount() 384 print "Mutator %s is reporting %d test cases" % (m.name, cnt) 385 386 return count

387 388 ##################################################### 389 # Callbacks when Action needs a value 390

391 - def getActionValue(self, action):

392 return self._mutator.getActionValue(action)

393

394 - def getActionParamValue(self, action):

395 return self._mutator.getActionParamValue(action)

396

397 - def getActionChangeStateValue(self, action, value):

398 return self._mutator.getActionParamValue(action, value)

399 400 ##################################################### 401 # Event callbacks for state machine 402

403 - def onStateStart(self, state):

404 return self._mutator.onStateStart(state)

405

406 - def onStateComplete(self, state):

407 return self._mutator.onStateComplete(state)

408

409 - def onActionStart(self, action):

410 return self._mutator.onActionStart(action)

411

412 - def onActionComplete(self, action):

413 return self._mutator.onActionComplete(action)

414

415 - def onStateMachineStart(self, stateMachine):

416 return self._mutator.onStateMachineStart(stateMachine)

417

418 - def onStateMachineComplete(self, stateMachine):

419 return self._mutator.onStateMachineComplete(stateMachine)

420

421 -class MutatorCountCalculator(threading.Thread):

422 ''' 423 This class will try and calculate the total number 424 of test cases in another thread. 425 426 When the result is available self.hasCountEvent will 427 be set. 428 ''' 429

430 - def __init__(self, mutator):

431 threading.Thread.__init__(self) 432 self._mutator = mutator 433 self.hasCountEvent = threading.Event() 434 self.count = -1

435

436 - def run(self):

437 self.count = self._mutator.calculateCount() 438 self.hasCountEvent.set()

439 440

441 -class MutatorCompleted(Exception):

442 ''' 443 At end of available mutations 444 ''' 445 pass

446

447 -class MutatorError(Exception):

448 ''' 449 Bad stuff just occured! 450 ''' 451 pass

452 453 # end 454

Source Code for Module Peach.mutator