1 /* 2 ** 2018-11-01 3 ** 4 ** The author disclaims copyright to this source code. In place of 5 ** a legal notice, here is a blessing: 6 ** 7 ** May you do good and not evil. 8 ** May you find forgiveness for yourself and forgive others. 9 ** May you share freely, never taking more than you give. 10 ** 11 ************************************************************************* 12 ** This file contains code to implement the "changesetfuzz" command 13 ** line utility for fuzzing changeset blobs without corrupting them. 14 */ 15 16 17 /************************************************************************ 18 ** USAGE: 19 ** 20 ** This program may be invoked in two ways: 21 ** 22 ** changesetfuzz INPUT 23 ** changesetfuzz INPUT SEED N 24 ** 25 ** Argument INPUT must be the name of a file containing a binary changeset. 26 ** In the first form above, this program outputs a human-readable version 27 ** of the same changeset. This is chiefly for debugging. 28 ** 29 ** In the second form, arguments SEED and N must both be integers. In this 30 ** case, this program writes N binary changesets to disk. Each output 31 ** changeset is a slightly modified - "fuzzed" - version of the input. 32 ** The output changesets are written to files name "INPUT-$n", where $n is 33 ** an integer between 0 and N-1, inclusive. Output changesets are always 34 ** well-formed. Parameter SEED is used to seed the PRNG - any two 35 ** invocations of this program with the same SEED and input changeset create 36 ** the same N output changesets. 37 ** 38 ** The ways in which an input changeset may be fuzzed are as follows: 39 ** 40 ** 1. Any two values within the changeset may be exchanged. 41 ** 42 ** 2. Any TEXT, BLOB, INTEGER or REAL value within the changeset 43 ** may have a single bit of its content flipped. 44 ** 45 ** 3. Any value within a changeset may be replaced by a pseudo-randomly 46 ** generated value. 47 ** 48 ** The above operations never set a PRIMARY KEY column to NULL. Nor do they 49 ** set any value to "undefined", or replace any "undefined" value with 50 ** another. Any such operation risks producing a changeset that is not 51 ** well-formed. 52 ** 53 ** 4. A single change may be duplicated. 54 ** 55 ** 5. A single change may be removed, so long as this does not mean that 56 ** there are zero changes following a table-header within the changeset. 57 ** 58 ** 6. A single change may have its type (INSERT, DELETE, UPDATE) changed. 59 ** If an INSERT is changed to a DELETE (or vice versa), the type is 60 ** simply changed - no other modifications are required. If an INSERT 61 ** or DELETE is changed to an UPDATE, then the single record is duplicated 62 ** (as both the old.* and new.* records of the new UPDATE change). If an 63 ** UPDATE is changed to a DELETE or INSERT, the new.* record is discarded 64 ** and any "undefined" fields replaced with pseudo-randomly generated 65 ** values. 66 ** 67 ** 7. An UPDATE change that modifies N table columns may be modified so 68 ** that it updates N-1 columns, so long as (N>1). 69 ** 70 ** 8. The "indirect" flag may be toggled for any change. 71 ** 72 ** Entire group of changes may also be operated on: 73 ** 74 ** 9. Duplicate an existing group. 75 ** 76 ** 10. Remove an existing group. 77 ** 78 ** 11. The positions of two groups may be exchanged. 79 ** 80 ** There are also schema changes: 81 ** 82 ** 12. A non-PK column may be added to a table. In this case a NULL 83 ** value is appended to all records. 84 ** 85 ** 13. A PK column may be added to a table. In this case a non-NULL 86 ** value is appended to all INSERT, DELETE and UPDATE old.* records. 87 ** An "undefined" is appended to new.* UPDATE records. 88 ** 89 ** 14. A column may be removed from a table, provided that it is not the 90 ** only PRIMARY KEY column in the table. In this case the corresponding 91 ** field is removed from all records. In cases where this leaves an UPDATE 92 ** with no non-PK, non-undefined fields, the entire change is removed. 93 ** 94 ** PATCHSETS 95 ** 96 ** As well as changesets, this program can also dump and fuzz patchsets. 97 */ 98 99 #include "sqlite3.h" 100 #include <stdio.h> 101 #include <stdlib.h> 102 #include <string.h> 103 #include <assert.h> 104 #include <ctype.h> 105 106 #define FUZZ_VALUE_SUB 1 /* Replace one value with a copy of another */ 107 #define FUZZ_VALUE_MOD 2 /* Modify content by 1 bit */ 108 #define FUZZ_VALUE_RND 3 /* Replace with pseudo-random value */ 109 110 #define FUZZ_CHANGE_DUP 4 /* Duplicate an existing change */ 111 #define FUZZ_CHANGE_DEL 5 /* Completely remove one change */ 112 #define FUZZ_CHANGE_TYPE 6 /* Change the type of one change */ 113 #define FUZZ_CHANGE_FIELD 7 /* Change an UPDATE to modify fewer columns */ 114 #define FUZZ_CHANGE_INDIRECT 8 /* Toggle the "indirect" flag of a change */ 115 116 #define FUZZ_GROUP_DUP 9 /* Duplicate a change group */ 117 #define FUZZ_GROUP_DEL 10 /* Delete an entire change group */ 118 #define FUZZ_GROUP_SWAP 11 /* Exchange the position of two groups */ 119 120 #define FUZZ_COLUMN_ADD 12 /* Add column to table definition */ 121 #define FUZZ_COLUMN_ADDPK 13 /* Add PK column to table definition */ 122 #define FUZZ_COLUMN_DEL 14 /* Remove column from table definition */ 123 124 125 126 typedef unsigned char u8; 127 typedef sqlite3_uint64 u64; 128 typedef sqlite3_int64 i64; 129 typedef unsigned int u32; 130 131 /* 132 ** Show a usage message on stderr then quit. 133 */ 134 static void usage(const char *argv0){ 135 fprintf(stderr, "Usage: %s FILENAME ?SEED N?\n", argv0); 136 exit(1); 137 } 138 139 /* 140 ** Read the content of a disk file into an in-memory buffer 141 */ 142 static void fuzzReadFile(const char *zFilename, int *pSz, void **ppBuf){ 143 FILE *f; 144 int sz; 145 void *pBuf; 146 f = fopen(zFilename, "rb"); 147 if( f==0 ){ 148 fprintf(stderr, "cannot open \"%s\" for reading\n", zFilename); 149 exit(1); 150 } 151 fseek(f, 0, SEEK_END); 152 sz = (int)ftell(f); 153 rewind(f); 154 pBuf = sqlite3_malloc( sz ? sz : 1 ); 155 if( pBuf==0 ){ 156 fprintf(stderr, "cannot allocate %d to hold content of \"%s\"\n", 157 sz, zFilename); 158 exit(1); 159 } 160 if( sz>0 ){ 161 if( fread(pBuf, sz, 1, f)!=1 ){ 162 fprintf(stderr, "cannot read all %d bytes of \"%s\"\n", sz, zFilename); 163 exit(1); 164 } 165 fclose(f); 166 } 167 *pSz = sz; 168 *ppBuf = pBuf; 169 } 170 171 /* 172 ** Write the contents of buffer pBuf, size nBuf bytes, into file zFilename 173 ** on disk. zFilename, if it already exists, is clobbered. 174 */ 175 static void fuzzWriteFile(const char *zFilename, void *pBuf, int nBuf){ 176 FILE *f; 177 f = fopen(zFilename, "wb"); 178 if( f==0 ){ 179 fprintf(stderr, "cannot open \"%s\" for writing\n", zFilename); 180 exit(1); 181 } 182 if( fwrite(pBuf, nBuf, 1, f)!=1 ){ 183 fprintf(stderr, "cannot write to \"%s\"\n", zFilename); 184 exit(1); 185 } 186 fclose(f); 187 } 188 189 static int fuzzCorrupt(){ 190 return SQLITE_CORRUPT; 191 } 192 193 /************************************************************************* 194 ** The following block is a copy of the implementation of SQLite function 195 ** sqlite3_randomness. This version has two important differences: 196 ** 197 ** 1. It always uses the same seed. So the sequence of random data output 198 ** is the same for every run of the program. 199 ** 200 ** 2. It is not threadsafe. 201 */ 202 static struct sqlite3PrngType { 203 unsigned char i, j; /* State variables */ 204 unsigned char s[256]; /* State variables */ 205 } sqlite3Prng = { 206 0xAF, 0x28, 207 { 208 0x71, 0xF5, 0xB4, 0x6E, 0x80, 0xAB, 0x1D, 0xB8, 209 0xFB, 0xB7, 0x49, 0xBF, 0xFF, 0x72, 0x2D, 0x14, 210 0x79, 0x09, 0xE3, 0x78, 0x76, 0xB0, 0x2C, 0x0A, 211 0x8E, 0x23, 0xEE, 0xDF, 0xE0, 0x9A, 0x2F, 0x67, 212 0xE1, 0xBE, 0x0E, 0xA7, 0x08, 0x97, 0xEB, 0x77, 213 0x78, 0xBA, 0x9D, 0xCA, 0x49, 0x4C, 0x60, 0x9A, 214 0xF6, 0xBD, 0xDA, 0x7F, 0xBC, 0x48, 0x58, 0x52, 215 0xE5, 0xCD, 0x83, 0x72, 0x23, 0x52, 0xFF, 0x6D, 216 0xEF, 0x0F, 0x82, 0x29, 0xA0, 0x83, 0x3F, 0x7D, 217 0xA4, 0x88, 0x31, 0xE7, 0x88, 0x92, 0x3B, 0x9B, 218 0x3B, 0x2C, 0xC2, 0x4C, 0x71, 0xA2, 0xB0, 0xEA, 219 0x36, 0xD0, 0x00, 0xF1, 0xD3, 0x39, 0x17, 0x5D, 220 0x2A, 0x7A, 0xE4, 0xAD, 0xE1, 0x64, 0xCE, 0x0F, 221 0x9C, 0xD9, 0xF5, 0xED, 0xB0, 0x22, 0x5E, 0x62, 222 0x97, 0x02, 0xA3, 0x8C, 0x67, 0x80, 0xFC, 0x88, 223 0x14, 0x0B, 0x15, 0x10, 0x0F, 0xC7, 0x40, 0xD4, 224 0xF1, 0xF9, 0x0E, 0x1A, 0xCE, 0xB9, 0x1E, 0xA1, 225 0x72, 0x8E, 0xD7, 0x78, 0x39, 0xCD, 0xF4, 0x5D, 226 0x2A, 0x59, 0x26, 0x34, 0xF2, 0x73, 0x0B, 0xA0, 227 0x02, 0x51, 0x2C, 0x03, 0xA3, 0xA7, 0x43, 0x13, 228 0xE8, 0x98, 0x2B, 0xD2, 0x53, 0xF8, 0xEE, 0x91, 229 0x7D, 0xE7, 0xE3, 0xDA, 0xD5, 0xBB, 0xC0, 0x92, 230 0x9D, 0x98, 0x01, 0x2C, 0xF9, 0xB9, 0xA0, 0xEB, 231 0xCF, 0x32, 0xFA, 0x01, 0x49, 0xA5, 0x1D, 0x9A, 232 0x76, 0x86, 0x3F, 0x40, 0xD4, 0x89, 0x8F, 0x9C, 233 0xE2, 0xE3, 0x11, 0x31, 0x37, 0xB2, 0x49, 0x28, 234 0x35, 0xC0, 0x99, 0xB6, 0xD0, 0xBC, 0x66, 0x35, 235 0xF7, 0x83, 0x5B, 0xD7, 0x37, 0x1A, 0x2B, 0x18, 236 0xA6, 0xFF, 0x8D, 0x7C, 0x81, 0xA8, 0xFC, 0x9E, 237 0xC4, 0xEC, 0x80, 0xD0, 0x98, 0xA7, 0x76, 0xCC, 238 0x9C, 0x2F, 0x7B, 0xFF, 0x8E, 0x0E, 0xBB, 0x90, 239 0xAE, 0x13, 0x06, 0xF5, 0x1C, 0x4E, 0x52, 0xF7 240 } 241 }; 242 243 /* 244 ** Generate and return single random byte 245 */ 246 static unsigned char fuzzRandomByte(void){ 247 unsigned char t; 248 sqlite3Prng.i++; 249 t = sqlite3Prng.s[sqlite3Prng.i]; 250 sqlite3Prng.j += t; 251 sqlite3Prng.s[sqlite3Prng.i] = sqlite3Prng.s[sqlite3Prng.j]; 252 sqlite3Prng.s[sqlite3Prng.j] = t; 253 t += sqlite3Prng.s[sqlite3Prng.i]; 254 return sqlite3Prng.s[t]; 255 } 256 257 /* 258 ** Return N random bytes. 259 */ 260 static void fuzzRandomBlob(int nBuf, unsigned char *zBuf){ 261 int i; 262 for(i=0; i<nBuf; i++){ 263 zBuf[i] = fuzzRandomByte(); 264 } 265 } 266 267 /* 268 ** Return a random integer between 0 and nRange (not inclusive). 269 */ 270 static unsigned int fuzzRandomInt(unsigned int nRange){ 271 unsigned int ret; 272 assert( nRange>0 ); 273 fuzzRandomBlob(sizeof(ret), (unsigned char*)&ret); 274 return (ret % nRange); 275 } 276 277 static u64 fuzzRandomU64(){ 278 u64 ret; 279 fuzzRandomBlob(sizeof(ret), (unsigned char*)&ret); 280 return ret; 281 } 282 283 static void fuzzRandomSeed(unsigned int iSeed){ 284 int i; 285 for(i=0; i<256; i+=4){ 286 sqlite3Prng.s[i] ^= ((iSeed >> 24) & 0xFF); 287 sqlite3Prng.s[i+1] ^= ((iSeed >> 16) & 0xFF); 288 sqlite3Prng.s[i+2] ^= ((iSeed >> 8) & 0xFF); 289 sqlite3Prng.s[i+3] ^= ((iSeed >> 0) & 0xFF); 290 } 291 } 292 /* 293 ** End of code for generating pseudo-random values. 294 *************************************************************************/ 295 296 typedef struct FuzzChangeset FuzzChangeset; 297 typedef struct FuzzChangesetGroup FuzzChangesetGroup; 298 typedef struct FuzzChange FuzzChange; 299 300 /* 301 ** Object containing partially parsed changeset. 302 */ 303 struct FuzzChangeset { 304 int bPatchset; /* True for a patchset */ 305 FuzzChangesetGroup **apGroup; /* Array of groups in changeset */ 306 int nGroup; /* Number of items in list pGroup */ 307 u8 **apVal; /* Array of all values in changeset */ 308 int nVal; /* Number of used slots in apVal[] */ 309 int nChange; /* Number of changes in changeset */ 310 int nUpdate; /* Number of UPDATE changes in changeset */ 311 }; 312 313 /* 314 ** There is one object of this type for each change-group (table header) 315 ** in the input changeset. 316 */ 317 struct FuzzChangesetGroup { 318 const char *zTab; /* Name of table */ 319 int nCol; /* Number of columns in table */ 320 u8 *aPK; /* PK array for this table */ 321 u8 *aChange; /* Buffer containing array of changes */ 322 int szChange; /* Size of buffer aChange[] in bytes */ 323 int nChange; /* Number of changes in buffer aChange[] */ 324 }; 325 326 /* 327 ** Description of a fuzz change to be applied to a changeset. 328 */ 329 struct FuzzChange { 330 int eType; /* One of the FUZZ_* constants above */ 331 int iChange; /* Change or UPDATE to modify */ 332 int iGroup; /* Group to modify */ 333 int iDelete; /* Field to remove (FUZZ_COLUMN_DEL) */ 334 u8 *pSub1; /* Replace this value with pSub2 */ 335 u8 *pSub2; /* And this one with pSub1 */ 336 u8 aSub[128]; /* Buffer for substitute value */ 337 int iCurrent; /* Current change number */ 338 }; 339 340 /* 341 ** Allocate and return nByte bytes of zeroed memory. 342 */ 343 static void *fuzzMalloc(int nByte){ 344 void *pRet = sqlite3_malloc(nByte); 345 if( pRet ){ 346 memset(pRet, 0, nByte); 347 } 348 return pRet; 349 } 350 351 /* 352 ** Free the buffer indicated by the first argument. This function is used 353 ** to free buffers allocated by fuzzMalloc(). 354 */ 355 static void fuzzFree(void *p){ 356 sqlite3_free(p); 357 } 358 359 /* 360 ** Argument p points to a buffer containing an SQLite varint that, assuming the 361 ** input is not corrupt, may be between 0 and 0x7FFFFFFF, inclusive. Before 362 ** returning, this function sets (*pnVal) to the value of that varint, and 363 ** returns the number of bytes of space that it takes up. 364 */ 365 static int fuzzGetVarint(u8 *p, int *pnVal){ 366 int i; 367 sqlite3_uint64 nVal = 0; 368 for(i=0; i<9; i++){ 369 nVal = (nVal<<7) + (p[i] & 0x7F); 370 if( (p[i] & 0x80)==0 ){ 371 i++; 372 break; 373 } 374 } 375 *pnVal = (int)nVal; 376 return i; 377 } 378 379 /* 380 ** Write value nVal into the buffer indicated by argument p as an SQLite 381 ** varint. nVal is guaranteed to be between 0 and (2^21-1), inclusive. 382 ** Return the number of bytes written to buffer p. 383 */ 384 static int fuzzPutVarint(u8 *p, int nVal){ 385 assert( nVal>0 && nVal<2097152 ); 386 if( nVal<128 ){ 387 p[0] = nVal; 388 return 1; 389 } 390 if( nVal<16384 ){ 391 p[0] = ((nVal >> 7) & 0x7F) | 0x80; 392 p[1] = (nVal & 0x7F); 393 return 2; 394 } 395 396 p[0] = ((nVal >> 14) & 0x7F) | 0x80; 397 p[1] = ((nVal >> 7) & 0x7F) | 0x80; 398 p[2] = (nVal & 0x7F); 399 return 3; 400 } 401 402 /* 403 ** Read a 64-bit big-endian integer value from buffer aRec[]. Return 404 ** the value read. 405 */ 406 static i64 fuzzGetI64(u8 *aRec){ 407 return (i64)( 408 (((u64)aRec[0]) << 56) 409 + (((u64)aRec[1]) << 48) 410 + (((u64)aRec[2]) << 40) 411 + (((u64)aRec[3]) << 32) 412 + (((u64)aRec[4]) << 24) 413 + (((u64)aRec[5]) << 16) 414 + (((u64)aRec[6]) << 8) 415 + (((u64)aRec[7]) << 0) 416 ); 417 } 418 419 /* 420 ** Write value iVal to buffer aRec[] as an unsigned 64-bit big-endian integer. 421 */ 422 static void fuzzPutU64(u8 *aRec, u64 iVal){ 423 aRec[0] = (iVal>>56) & 0xFF; 424 aRec[1] = (iVal>>48) & 0xFF; 425 aRec[2] = (iVal>>40) & 0xFF; 426 aRec[3] = (iVal>>32) & 0xFF; 427 aRec[4] = (iVal>>24) & 0xFF; 428 aRec[5] = (iVal>>16) & 0xFF; 429 aRec[6] = (iVal>> 8) & 0xFF; 430 aRec[7] = (iVal) & 0xFF; 431 } 432 433 static int fuzzParseHeader( 434 FuzzChangeset *pParse, 435 u8 **ppHdr, 436 u8 *pEnd, 437 FuzzChangesetGroup **ppGrp 438 ){ 439 int rc = SQLITE_OK; 440 FuzzChangesetGroup *pGrp; 441 u8 cHdr = (pParse->bPatchset ? 'P' : 'T'); 442 443 assert( pEnd>(*ppHdr) ); 444 pGrp = (FuzzChangesetGroup*)fuzzMalloc(sizeof(FuzzChangesetGroup)); 445 if( !pGrp ){ 446 rc = SQLITE_NOMEM; 447 }else{ 448 u8 *p = *ppHdr; 449 if( p[0]!=cHdr ){ 450 rc = fuzzCorrupt(); 451 }else{ 452 p++; 453 p += fuzzGetVarint(p, &pGrp->nCol); 454 pGrp->aPK = p; 455 p += pGrp->nCol; 456 pGrp->zTab = (const char*)p; 457 p = &p[strlen(p)+1]; 458 459 if( p>=pEnd ){ 460 rc = fuzzCorrupt(); 461 } 462 } 463 *ppHdr = p; 464 } 465 466 if( rc!=SQLITE_OK ){ 467 fuzzFree(pGrp); 468 pGrp = 0; 469 } 470 471 *ppGrp = pGrp; 472 return rc; 473 } 474 475 static int fuzzChangeSize(u8 *p, int *pSz){ 476 u8 eType = p[0]; 477 switch( eType ){ 478 case 0x00: /* undefined */ 479 case 0x05: /* null */ 480 *pSz = 1; 481 break; 482 483 case 0x01: /* integer */ 484 case 0x02: /* real */ 485 *pSz = 9; 486 break; 487 488 case 0x03: /* text */ 489 case 0x04: { /* blob */ 490 int nTxt; 491 int sz; 492 sz = fuzzGetVarint(&p[1], &nTxt); 493 *pSz = 1 + sz + nTxt; 494 break; 495 } 496 497 default: 498 return fuzzCorrupt(); 499 } 500 return SQLITE_OK; 501 } 502 503 static int fuzzParseRecord( 504 u8 **ppRec, /* IN/OUT: Iterator */ 505 u8 *pEnd, /* One byte after end of input data */ 506 FuzzChangeset *pParse, 507 int bPkOnly 508 ){ 509 int rc = SQLITE_OK; 510 FuzzChangesetGroup *pGrp = pParse->apGroup[pParse->nGroup-1]; 511 int i; 512 u8 *p = *ppRec; 513 514 for(i=0; rc==SQLITE_OK && i<pGrp->nCol && p<pEnd; i++){ 515 if( bPkOnly==0 || pGrp->aPK[i] ){ 516 int sz; 517 if( (pParse->nVal & (pParse->nVal-1))==0 ){ 518 int nNew = pParse->nVal ? pParse->nVal*2 : 4; 519 u8 **apNew = (u8**)sqlite3_realloc(pParse->apVal, nNew*sizeof(u8*)); 520 if( apNew==0 ) return SQLITE_NOMEM; 521 pParse->apVal = apNew; 522 } 523 pParse->apVal[pParse->nVal++] = p; 524 rc = fuzzChangeSize(p, &sz); 525 p += sz; 526 } 527 } 528 529 if( rc==SQLITE_OK && i<pGrp->nCol ){ 530 rc = fuzzCorrupt(); 531 } 532 533 *ppRec = p; 534 return rc; 535 } 536 537 static int fuzzParseChanges(u8 **ppData, u8 *pEnd, FuzzChangeset *pParse){ 538 u8 cHdr = (pParse->bPatchset ? 'P' : 'T'); 539 FuzzChangesetGroup *pGrp = pParse->apGroup[pParse->nGroup-1]; 540 int rc = SQLITE_OK; 541 u8 *p = *ppData; 542 543 pGrp->aChange = p; 544 while( rc==SQLITE_OK && p<pEnd && p[0]!=cHdr ){ 545 u8 eOp = p[0]; 546 u8 bIndirect = p[1]; 547 548 p += 2; 549 if( eOp==SQLITE_UPDATE ){ 550 pParse->nUpdate++; 551 if( pParse->bPatchset==0 ){ 552 rc = fuzzParseRecord(&p, pEnd, pParse, 0); 553 } 554 }else if( eOp!=SQLITE_INSERT && eOp!=SQLITE_DELETE ){ 555 rc = fuzzCorrupt(); 556 } 557 if( rc==SQLITE_OK ){ 558 int bPkOnly = (eOp==SQLITE_DELETE && pParse->bPatchset); 559 rc = fuzzParseRecord(&p, pEnd, pParse, bPkOnly); 560 } 561 pGrp->nChange++; 562 pParse->nChange++; 563 } 564 pGrp->szChange = p - pGrp->aChange; 565 566 *ppData = p; 567 return rc; 568 } 569 570 static int fuzzParseChangeset( 571 u8 *pChangeset, /* Buffer containing changeset */ 572 int nChangeset, /* Size of buffer in bytes */ 573 FuzzChangeset *pParse /* OUT: Results of parse */ 574 ){ 575 u8 *pEnd = &pChangeset[nChangeset]; 576 u8 *p = pChangeset; 577 int rc = SQLITE_OK; 578 579 memset(pParse, 0, sizeof(FuzzChangeset)); 580 if( nChangeset>0 ){ 581 pParse->bPatchset = (pChangeset[0]=='P'); 582 } 583 584 while( rc==SQLITE_OK && p<pEnd ){ 585 FuzzChangesetGroup *pGrp = 0; 586 587 /* Read a table-header from the changeset */ 588 rc = fuzzParseHeader(pParse, &p, pEnd, &pGrp); 589 assert( (rc==SQLITE_OK)==(pGrp!=0) ); 590 591 /* If the table-header was successfully parsed, add the new change-group 592 ** to the array and parse the associated changes. */ 593 if( rc==SQLITE_OK ){ 594 FuzzChangesetGroup **apNew = (FuzzChangesetGroup**)sqlite3_realloc( 595 pParse->apGroup, sizeof(FuzzChangesetGroup*)*(pParse->nGroup+1) 596 ); 597 if( apNew==0 ){ 598 rc = SQLITE_NOMEM; 599 }else{ 600 apNew[pParse->nGroup] = pGrp; 601 pParse->apGroup = apNew; 602 pParse->nGroup++; 603 } 604 rc = fuzzParseChanges(&p, pEnd, pParse); 605 } 606 } 607 608 return rc; 609 } 610 611 static int fuzzPrintRecord(FuzzChangesetGroup *pGrp, u8 **ppRec, int bPKOnly){ 612 int rc = SQLITE_OK; 613 u8 *p = *ppRec; 614 int i; 615 const char *zPre = " ("; 616 617 for(i=0; i<pGrp->nCol; i++){ 618 if( bPKOnly==0 || pGrp->aPK[i] ){ 619 u8 eType = p++[0]; 620 switch( eType ){ 621 case 0x00: /* undefined */ 622 printf("%sn/a", zPre); 623 break; 624 625 case 0x01: { /* integer */ 626 sqlite3_int64 iVal = 0; 627 iVal = fuzzGetI64(p); 628 printf("%s%lld", zPre, iVal); 629 p += 8; 630 break; 631 } 632 633 case 0x02: { /* real */ 634 sqlite3_int64 iVal = 0; 635 double fVal = 0.0; 636 iVal = fuzzGetI64(p); 637 memcpy(&fVal, &iVal, 8); 638 printf("%s%f", zPre, fVal); 639 p += 8; 640 break; 641 } 642 643 case 0x03: /* text */ 644 case 0x04: { /* blob */ 645 int nTxt; 646 int sz; 647 int i; 648 p += fuzzGetVarint(p, &nTxt); 649 printf("%s%s", zPre, eType==0x03 ? "'" : "X'"); 650 for(i=0; i<nTxt; i++){ 651 if( eType==0x03 ){ 652 printf("%c", p[i]); 653 }else{ 654 char aHex[16] = {'0', '1', '2', '3', '4', '5', '6', '7', 655 '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' 656 }; 657 printf("%c", aHex[ p[i]>>4 ]); 658 printf("%c", aHex[ p[i] & 0x0F ]); 659 } 660 } 661 printf("'"); 662 p += nTxt; 663 break; 664 } 665 666 case 0x05: /* null */ 667 printf("%sNULL", zPre); 668 break; 669 } 670 zPre = ", "; 671 } 672 } 673 printf(")"); 674 675 *ppRec = p; 676 return rc; 677 } 678 679 static int fuzzPrintGroup(FuzzChangeset *pParse, FuzzChangesetGroup *pGrp){ 680 int i; 681 u8 *p; 682 683 /* The table header */ 684 printf("TABLE: %s nCol=%d aPK=", pGrp->zTab, pGrp->nCol); 685 for(i=0; i<pGrp->nCol; i++){ 686 printf("%d", (int)pGrp->aPK[i]); 687 } 688 printf("\n"); 689 690 /* The array of changes */ 691 p = pGrp->aChange; 692 for(i=0; i<pGrp->nChange; i++){ 693 u8 eType = p[0]; 694 u8 bIndirect = p[1]; 695 printf("%s (ind=%d):", 696 (eType==SQLITE_INSERT) ? "INSERT" : 697 (eType==SQLITE_DELETE ? "DELETE" : "UPDATE"), 698 bIndirect 699 ); 700 p += 2; 701 702 if( pParse->bPatchset==0 && eType==SQLITE_UPDATE ){ 703 fuzzPrintRecord(pGrp, &p, 0); 704 } 705 fuzzPrintRecord(pGrp, &p, eType==SQLITE_DELETE && pParse->bPatchset); 706 printf("\n"); 707 } 708 } 709 710 static int fuzzSelectChange(FuzzChangeset *pParse, FuzzChange *pChange){ 711 int iSub; 712 713 memset(pChange, 0, sizeof(FuzzChange)); 714 pChange->eType = fuzzRandomInt(FUZZ_COLUMN_DEL) + 1; 715 716 assert( pChange->eType==FUZZ_VALUE_SUB 717 || pChange->eType==FUZZ_VALUE_MOD 718 || pChange->eType==FUZZ_VALUE_RND 719 || pChange->eType==FUZZ_CHANGE_DUP 720 || pChange->eType==FUZZ_CHANGE_DEL 721 || pChange->eType==FUZZ_CHANGE_TYPE 722 || pChange->eType==FUZZ_CHANGE_FIELD 723 || pChange->eType==FUZZ_CHANGE_INDIRECT 724 || pChange->eType==FUZZ_GROUP_DUP 725 || pChange->eType==FUZZ_GROUP_DEL 726 || pChange->eType==FUZZ_GROUP_SWAP 727 || pChange->eType==FUZZ_COLUMN_ADD 728 || pChange->eType==FUZZ_COLUMN_ADDPK 729 || pChange->eType==FUZZ_COLUMN_DEL 730 ); 731 732 pChange->iGroup = fuzzRandomInt(pParse->nGroup); 733 pChange->iChange = fuzzRandomInt(pParse->nChange); 734 if( pChange->eType==FUZZ_CHANGE_FIELD ){ 735 if( pParse->nUpdate==0 ) return -1; 736 pChange->iChange = fuzzRandomInt(pParse->nUpdate); 737 } 738 739 pChange->iDelete = -1; 740 if( pChange->eType==FUZZ_COLUMN_DEL ){ 741 FuzzChangesetGroup *pGrp = pParse->apGroup[pChange->iGroup]; 742 int i; 743 pChange->iDelete = fuzzRandomInt(pGrp->nCol); 744 for(i=pGrp->nCol-1; i>=0; i--){ 745 if( pGrp->aPK[i] && pChange->iDelete!=i ) break; 746 } 747 if( i<0 ) return -1; 748 } 749 750 if( pChange->eType==FUZZ_GROUP_SWAP ){ 751 FuzzChangesetGroup *pGrp; 752 int iGrp = pChange->iGroup; 753 if( pParse->nGroup==1 ) return -1; 754 while( iGrp==pChange->iGroup ){ 755 iGrp = fuzzRandomInt(pParse->nGroup); 756 } 757 pGrp = pParse->apGroup[pChange->iGroup]; 758 pParse->apGroup[pChange->iGroup] = pParse->apGroup[iGrp]; 759 pParse->apGroup[iGrp] = pGrp; 760 } 761 762 if( pChange->eType==FUZZ_VALUE_SUB 763 || pChange->eType==FUZZ_VALUE_MOD 764 || pChange->eType==FUZZ_VALUE_RND 765 ){ 766 iSub = fuzzRandomInt(pParse->nVal); 767 pChange->pSub1 = pParse->apVal[iSub]; 768 if( pChange->eType==FUZZ_VALUE_SUB ){ 769 iSub = fuzzRandomInt(pParse->nVal); 770 pChange->pSub2 = pParse->apVal[iSub]; 771 }else{ 772 pChange->pSub2 = pChange->aSub; 773 } 774 775 if( pChange->eType==FUZZ_VALUE_RND ){ 776 pChange->aSub[0] = (u8)(fuzzRandomInt(5) + 1); 777 switch( pChange->aSub[0] ){ 778 case 0x01: { /* integer */ 779 u64 iVal = fuzzRandomU64(); 780 fuzzPutU64(&pChange->aSub[1], iVal); 781 break; 782 } 783 784 case 0x02: { /* real */ 785 u64 iVal1 = fuzzRandomU64(); 786 u64 iVal2 = fuzzRandomU64(); 787 double d = (double)iVal1 / (double)iVal2; 788 memcpy(&iVal1, &d, sizeof(iVal1)); 789 fuzzPutU64(&pChange->aSub[1], iVal1); 790 break; 791 } 792 793 case 0x03: /* text */ 794 case 0x04: { /* blob */ 795 int nByte = fuzzRandomInt(48); 796 pChange->aSub[1] = nByte; 797 fuzzRandomBlob(nByte, &pChange->aSub[2]); 798 if( pChange->aSub[0]==0x03 ){ 799 int i; 800 for(i=0; i<nByte; i++){ 801 pChange->aSub[2+i] &= 0x7F; 802 } 803 } 804 break; 805 } 806 } 807 } 808 if( pChange->eType==FUZZ_VALUE_MOD ){ 809 int sz; 810 int iMod = -1; 811 fuzzChangeSize(pChange->pSub1, &sz); 812 memcpy(pChange->aSub, pChange->pSub1, sz); 813 switch( pChange->aSub[0] ){ 814 case 0x01: 815 case 0x02: 816 iMod = fuzzRandomInt(8) + 1; 817 break; 818 819 case 0x03: /* text */ 820 case 0x04: { /* blob */ 821 int nByte; 822 int iFirst = 1 + fuzzGetVarint(&pChange->aSub[1], &nByte); 823 if( nByte>0 ){ 824 iMod = fuzzRandomInt(nByte) + iFirst; 825 } 826 break; 827 } 828 } 829 830 if( iMod>=0 ){ 831 u8 mask = (1 << fuzzRandomInt(8 - (pChange->aSub[0]==0x03))); 832 pChange->aSub[iMod] ^= mask; 833 } 834 } 835 } 836 837 return SQLITE_OK; 838 } 839 840 static int fuzzCopyChange( 841 FuzzChangeset *pParse, 842 int iGrp, 843 FuzzChange *pFuzz, 844 u8 **pp, u8 **ppOut /* IN/OUT: Input and output pointers */ 845 ){ 846 int bPS = pParse->bPatchset; 847 FuzzChangesetGroup *pGrp = pParse->apGroup[iGrp]; 848 u8 *p = *pp; 849 u8 *pOut = *ppOut; 850 u8 eType = p++[0]; 851 int iRec; 852 int nRec = ((eType==SQLITE_UPDATE && !bPS) ? 2 : 1); 853 int iUndef = -1; 854 int nUpdate = 0; 855 856 u8 eNew = eType; 857 if( pFuzz->iCurrent==pFuzz->iChange && pFuzz->eType==FUZZ_CHANGE_TYPE ){ 858 switch( eType ){ 859 case SQLITE_INSERT: 860 eNew = SQLITE_DELETE; 861 break; 862 case SQLITE_DELETE: 863 eNew = SQLITE_UPDATE; 864 break; 865 case SQLITE_UPDATE: 866 eNew = SQLITE_INSERT; 867 break; 868 } 869 } 870 871 if( pFuzz->iCurrent==pFuzz->iChange 872 && pFuzz->eType==FUZZ_CHANGE_FIELD && eType==SQLITE_UPDATE 873 ){ 874 int sz; 875 int i; 876 int nDef = 0; 877 u8 *pCsr = p+1; 878 for(i=0; i<pGrp->nCol; i++){ 879 if( pCsr[0] && pGrp->aPK[i]==0 ) nDef++; 880 fuzzChangeSize(pCsr, &sz); 881 pCsr += sz; 882 } 883 if( nDef<=1 ) return -1; 884 nDef = fuzzRandomInt(nDef); 885 pCsr = p+1; 886 for(i=0; i<pGrp->nCol; i++){ 887 if( pCsr[0] && pGrp->aPK[i]==0 ){ 888 if( nDef==0 ) iUndef = i; 889 nDef--; 890 } 891 fuzzChangeSize(pCsr, &sz); 892 pCsr += sz; 893 } 894 } 895 896 /* Copy the change type and indirect flag. If the fuzz mode is 897 ** FUZZ_CHANGE_INDIRECT, and the current change is the one selected for 898 ** fuzzing, invert the indirect flag. */ 899 *(pOut++) = eNew; 900 if( pFuzz->eType==FUZZ_CHANGE_INDIRECT && pFuzz->iCurrent==pFuzz->iChange ){ 901 *(pOut++) = !(*(p++)); 902 }else{ 903 *(pOut++) = *(p++); 904 } 905 906 for(iRec=0; iRec<nRec; iRec++){ 907 int i; 908 909 /* Copy the next record from the output to the input. 910 */ 911 for(i=0; i<pGrp->nCol; i++){ 912 int sz; 913 u8 *pCopy = p; 914 915 /* If this is a patchset, and the input is a DELETE, then the only 916 ** fields present are the PK fields. So, if this is not a PK, skip to 917 ** the next column. If the current fuzz is FUZZ_CHANGE_TYPE, then 918 ** write a randomly selected value to the output. */ 919 if( bPS && eType==SQLITE_DELETE && pGrp->aPK[i]==0 ){ 920 if( eType!=eNew ){ 921 assert( eNew==SQLITE_UPDATE ); 922 do { 923 pCopy = pParse->apVal[fuzzRandomInt(pParse->nVal)]; 924 }while( pCopy[0]==0x00 ); 925 fuzzChangeSize(pCopy, &sz); 926 memcpy(pOut, pCopy, sz); 927 pOut += sz; 928 } 929 continue; 930 } 931 932 if( p==pFuzz->pSub1 ){ 933 pCopy = pFuzz->pSub2; 934 }else if( p==pFuzz->pSub2 ){ 935 pCopy = pFuzz->pSub1; 936 }else if( i==iUndef ){ 937 pCopy = "\0"; 938 } 939 940 if( pCopy[0]==0x00 && eNew!=eType && eType==SQLITE_UPDATE && iRec==0 ){ 941 while( pCopy[0]==0x00 ){ 942 pCopy = pParse->apVal[fuzzRandomInt(pParse->nVal)]; 943 } 944 }else if( p[0]==0x00 && pCopy[0]!=0x00 ){ 945 return -1; 946 }else{ 947 if( pGrp->aPK[i]>0 && pCopy[0]==0x05 ) return -1; 948 } 949 950 if( (pFuzz->iGroup!=iGrp || i!=pFuzz->iDelete) 951 && (eNew==eType || eType!=SQLITE_UPDATE || iRec==0) 952 && (eNew==eType || eNew!=SQLITE_DELETE || !bPS || pGrp->aPK[i]) 953 ){ 954 fuzzChangeSize(pCopy, &sz); 955 memcpy(pOut, pCopy, sz); 956 pOut += sz; 957 nUpdate += (pGrp->aPK[i]==0 && pCopy[0]!=0x00); 958 } 959 960 fuzzChangeSize(p, &sz); 961 p += sz; 962 } 963 964 if( iGrp==pFuzz->iGroup ){ 965 if( pFuzz->eType==FUZZ_COLUMN_ADD ){ 966 if( !bPS || eType!=SQLITE_DELETE ) *(pOut++) = 0x05; 967 }else if( pFuzz->eType==FUZZ_COLUMN_ADDPK ){ 968 if( iRec==1 ){ 969 *(pOut++) = 0x00; 970 }else{ 971 u8 *pNew; 972 int szNew; 973 do { 974 pNew = pParse->apVal[fuzzRandomInt(pParse->nVal)]; 975 }while( pNew[0]==0x00 || pNew[0]==0x05 ); 976 fuzzChangeSize(pNew, &szNew); 977 memcpy(pOut, pNew, szNew); 978 pOut += szNew; 979 } 980 } 981 } 982 } 983 984 if( pFuzz->iCurrent==pFuzz->iChange ){ 985 if( pFuzz->eType==FUZZ_CHANGE_DUP ){ 986 int nByte = pOut - (*ppOut); 987 memcpy(pOut, *ppOut, nByte); 988 pOut += nByte; 989 } 990 991 if( pFuzz->eType==FUZZ_CHANGE_DEL ){ 992 pOut = *ppOut; 993 } 994 if( eNew!=eType && eNew==SQLITE_UPDATE && !bPS ){ 995 int i; 996 u8 *pCsr = (*ppOut) + 2; 997 for(i=0; i<pGrp->nCol; i++){ 998 int sz; 999 u8 *pCopy = pCsr; 1000 if( pGrp->aPK[i] ) pCopy = "\0"; 1001 fuzzChangeSize(pCopy, &sz); 1002 memcpy(pOut, pCopy, sz); 1003 pOut += sz; 1004 fuzzChangeSize(pCsr, &sz); 1005 pCsr += sz; 1006 } 1007 } 1008 } 1009 1010 /* If a column is being deleted from this group, and this change was an 1011 ** UPDATE, and there are now no non-PK, non-undefined columns in the 1012 ** change, remove it altogether. */ 1013 if( pFuzz->eType==FUZZ_COLUMN_DEL && pFuzz->iGroup==iGrp 1014 && eType==SQLITE_UPDATE && nUpdate==0 1015 ){ 1016 pOut = *ppOut; 1017 } 1018 1019 *pp = p; 1020 *ppOut = pOut; 1021 pFuzz->iCurrent += (eType==SQLITE_UPDATE || pFuzz->eType!=FUZZ_CHANGE_FIELD); 1022 return SQLITE_OK; 1023 } 1024 1025 static int fuzzDoOneFuzz( 1026 const char *zOut, /* Filename to write modified changeset to */ 1027 u8 *pBuf, /* Buffer to use for modified changeset */ 1028 FuzzChangeset *pParse /* Parse of input changeset */ 1029 ){ 1030 FuzzChange change; 1031 int iGrp; 1032 int rc = -1; 1033 1034 while( rc<0 ){ 1035 u8 *pOut = pBuf; 1036 rc = fuzzSelectChange(pParse, &change); 1037 for(iGrp=0; rc==SQLITE_OK && iGrp<pParse->nGroup; iGrp++){ 1038 FuzzChangesetGroup *pGrp = pParse->apGroup[iGrp]; 1039 int nTab = strlen(pGrp->zTab) + 1; 1040 int j; 1041 int nRep = 1; 1042 1043 /* If this is the group to delete for a FUZZ_GROUP_DEL change, jump to 1044 ** the next group. Unless this is the only group in the changeset - in 1045 ** that case this change cannot be applied. 1046 ** 1047 ** Or, if this is a FUZZ_GROUP_DUP, set nRep to 2 to output two 1048 ** copies of the group. */ 1049 if( change.iGroup==iGrp ){ 1050 if( change.eType==FUZZ_GROUP_DEL ){ 1051 if( pParse->nGroup==1 ) rc = -1; 1052 continue; 1053 } 1054 else if( change.eType==FUZZ_GROUP_DUP ){ 1055 nRep = 2; 1056 } 1057 } 1058 1059 for(j=0; j<nRep; j++){ 1060 int i; 1061 u8 *pSaved; 1062 u8 *p = pGrp->aChange; 1063 int nCol = pGrp->nCol; 1064 int iPKDel = 0; 1065 if( iGrp==change.iGroup ){ 1066 if( change.eType==FUZZ_COLUMN_ADD 1067 || change.eType==FUZZ_COLUMN_ADDPK 1068 ){ 1069 nCol++; 1070 }else if( change.eType==FUZZ_COLUMN_DEL ){ 1071 nCol--; 1072 iPKDel = pGrp->aPK[change.iDelete]; 1073 } 1074 } 1075 1076 /* Output a table header */ 1077 pOut++[0] = pParse->bPatchset ? 'P' : 'T'; 1078 pOut += fuzzPutVarint(pOut, nCol); 1079 1080 for(i=0; i<pGrp->nCol; i++){ 1081 if( iGrp!=change.iGroup || i!=change.iDelete ){ 1082 u8 v = pGrp->aPK[i]; 1083 if( iPKDel && v>iPKDel ) v--; 1084 *(pOut++) = v; 1085 } 1086 } 1087 if( nCol>pGrp->nCol ){ 1088 if( change.eType==FUZZ_COLUMN_ADD ){ 1089 *(pOut++) = 0x00; 1090 }else{ 1091 u8 max = 0; 1092 for(i=0; i<pGrp->nCol; i++){ 1093 if( pGrp->aPK[i]>max ) max = pGrp->aPK[i]; 1094 } 1095 *(pOut++) = max+1; 1096 } 1097 } 1098 memcpy(pOut, pGrp->zTab, nTab); 1099 pOut += nTab; 1100 1101 /* Output the change array. */ 1102 pSaved = pOut; 1103 for(i=0; rc==SQLITE_OK && i<pGrp->nChange; i++){ 1104 rc = fuzzCopyChange(pParse, iGrp, &change, &p, &pOut); 1105 } 1106 if( pOut==pSaved ) rc = -1; 1107 } 1108 } 1109 if( rc==SQLITE_OK ){ 1110 fuzzWriteFile(zOut, pBuf, pOut-pBuf); 1111 } 1112 } 1113 1114 return rc; 1115 } 1116 1117 int main(int argc, char **argv){ 1118 int nRepeat = 0; /* Number of output files */ 1119 int iSeed = 0; /* Value of PRNG seed */ 1120 const char *zInput; /* Name of input file */ 1121 void *pChangeset = 0; /* Input changeset */ 1122 int nChangeset = 0; /* Size of input changeset in bytes */ 1123 int i; /* Current output file */ 1124 FuzzChangeset changeset; /* Partially parsed changeset */ 1125 int rc; 1126 u8 *pBuf = 0; 1127 1128 if( argc!=4 && argc!=2 ) usage(argv[0]); 1129 zInput = argv[1]; 1130 1131 fuzzReadFile(zInput, &nChangeset, &pChangeset); 1132 rc = fuzzParseChangeset(pChangeset, nChangeset, &changeset); 1133 1134 if( rc==SQLITE_OK ){ 1135 if( argc==2 ){ 1136 for(i=0; i<changeset.nGroup; i++){ 1137 fuzzPrintGroup(&changeset, changeset.apGroup[i]); 1138 } 1139 }else{ 1140 pBuf = (u8*)fuzzMalloc(nChangeset*2 + 1024); 1141 if( pBuf==0 ){ 1142 rc = SQLITE_NOMEM; 1143 }else{ 1144 iSeed = atoi(argv[2]); 1145 nRepeat = atoi(argv[3]); 1146 fuzzRandomSeed((unsigned int)iSeed); 1147 for(i=0; rc==SQLITE_OK && i<nRepeat; i++){ 1148 char *zOut = sqlite3_mprintf("%s-%d", zInput, i); 1149 rc = fuzzDoOneFuzz(zOut, pBuf, &changeset); 1150 sqlite3_free(zOut); 1151 } 1152 fuzzFree(pBuf); 1153 } 1154 } 1155 } 1156 1157 if( rc!=SQLITE_OK ){ 1158 fprintf(stderr, "error while processing changeset: %d\n", rc); 1159 } 1160 1161 return rc; 1162 } 1163 1164