test/fuzzinvariants.c

   1 /*
   2 ** 2022-06-14
   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 **
  13 ** This library is used by fuzzcheck to test query invariants.
  14 **
  15 ** An sqlite3_stmt is passed in that has just returned SQLITE_ROW.  This
  16 ** routine does:
  17 **
  18 **     *   Record the output of the current row
  19 **     *   Construct an alternative query that should return the same row
  20 **     *   Run the alternative query and verify that it does in fact return
  21 **         the same row
  22 **
  23 */
  24 #include "sqlite3.h"
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <ctype.h>
  29
  30 /* Forward references */
  31 static char *fuzz_invariant_sql(sqlite3_stmt*, int);
  32 static int sameValue(sqlite3_stmt*,int,sqlite3_stmt*,int,sqlite3_stmt*);
  33 static void reportInvariantFailed(
  34   sqlite3_stmt *pOrig,   /* The original query */
  35   sqlite3_stmt *pTest,   /* The alternative test query with a missing row */
  36   int iRow,              /* Row number in pOrig */
  37   unsigned int dbOpt,    /* Optimization flags on pOrig */
  38   int noOpt              /* True if opt flags inverted for pTest */
  39 );
  40
  41 /*
  42 ** Do an invariant check on pStmt.  iCnt determines which invariant check to
  43 ** perform.  The first check is iCnt==0.
  44 **
  45 ** *pbCorrupt is a flag that, if true, indicates that the database file
  46 ** is known to be corrupt.  A value of non-zero means "yes, the database
  47 ** is corrupt".  A zero value means "we do not know whether or not the
  48 ** database is corrupt".  The value might be set prior to entry, or this
  49 ** routine might set the value.
  50 **
  51 ** Return values:
  52 **
  53 **     SQLITE_OK          This check was successful.
  54 **
  55 **     SQLITE_DONE        iCnt is out of range.  The caller typically sets
  56 **                        up a loop on iCnt starting with zero, and increments
  57 **                        iCnt until this code is returned.
  58 **
  59 **     SQLITE_CORRUPT     The invariant failed, but the underlying database
  60 **                        file is indicating that it is corrupt, which might
  61 **                        be the cause of the malfunction.  The *pCorrupt
  62 **                        value will also be set.
  63 **
  64 **     SQLITE_INTERNAL    The invariant failed, and the database file is not
  65 **                        corrupt.  (This never happens because this function
  66 **                        will call abort() following an invariant failure.)
  67 **
  68 **     (other)            Some other kind of error occurred.
  69 */
  70 int fuzz_invariant(
  71   sqlite3 *db,            /* The database connection */
  72   sqlite3_stmt *pStmt,    /* Test statement stopped on an SQLITE_ROW */
  73   int iCnt,               /* Invariant sequence number, starting at 0 */
  74   int iRow,               /* Current row number */
  75   int nRow,               /* Number of output rows from pStmt */
  76   int *pbCorrupt,         /* IN/OUT: Flag indicating a corrupt database file */
  77   int eVerbosity,         /* How much debugging output */
  78   unsigned int dbOpt      /* Default optimization flags */
  79 ){
  80   char *zTest;
  81   sqlite3_stmt *pTestStmt = 0;
  82   int rc;
  83   int i;
  84   int nCol;
  85   int nParam;
  86   int noOpt = (iCnt%3)==0;
  87
  88   if( *pbCorrupt ) return SQLITE_DONE;
  89   nParam = sqlite3_bind_parameter_count(pStmt);
  90   if( nParam>100 ) return SQLITE_DONE;
  91   zTest = fuzz_invariant_sql(pStmt, iCnt);
  92   if( zTest==0 ) return SQLITE_DONE;
  93   if( noOpt ){
  94     sqlite3_test_control(SQLITE_TESTCTRL_OPTIMIZATIONS, db, ~dbOpt);
  95   }
  96   rc = sqlite3_prepare_v2(db, zTest, -1, &pTestStmt, 0);
  97   if( noOpt ){
  98     sqlite3_test_control(SQLITE_TESTCTRL_OPTIMIZATIONS, db, dbOpt);
  99   }
 100   if( rc ){
 101     if( eVerbosity ){
 102       printf("invariant compile failed: %s\n%s\n",
 103              sqlite3_errmsg(db), zTest);
 104     }
 105     sqlite3_free(zTest);
 106     sqlite3_finalize(pTestStmt);
 107     return rc;
 108   }
 109   sqlite3_free(zTest);
 110   nCol = sqlite3_column_count(pStmt);
 111   for(i=0; i<nCol; i++){
 112     rc = sqlite3_bind_value(pTestStmt,i+1+nParam,sqlite3_column_value(pStmt,i));
 113     if( rc!=SQLITE_OK && rc!=SQLITE_RANGE ){
 114       sqlite3_finalize(pTestStmt);
 115       return rc;
 116     }
 117   }
 118   if( eVerbosity>=2 ){
 119     char *zSql = sqlite3_expanded_sql(pTestStmt);
 120     printf("invariant-sql row=%d #%d:\n%s\n", iRow, iCnt, zSql);
 121     sqlite3_free(zSql);
 122   }
 123   while( (rc = sqlite3_step(pTestStmt))==SQLITE_ROW ){
 124     for(i=0; i<nCol; i++){
 125       if( !sameValue(pStmt, i, pTestStmt, i, 0) ) break;
 126     }
 127     if( i>=nCol ) break;
 128   }
 129   if( rc==SQLITE_DONE ){
 130     /* No matching output row found */
 131     sqlite3_stmt *pCk = 0;
 132     int iOrigRSO;
 133
 134
 135     /* This is not a fault if the database file is corrupt, because anything
 136     ** can happen with a corrupt database file */
 137     rc = sqlite3_prepare_v2(db, "PRAGMA integrity_check", -1, &pCk, 0);
 138     if( rc ){
 139       sqlite3_finalize(pCk);
 140       sqlite3_finalize(pTestStmt);
 141       return rc;
 142     }
 143     if( eVerbosity>=2 ){
 144       char *zSql = sqlite3_expanded_sql(pCk);
 145       printf("invariant-validity-check #1:\n%s\n", zSql);
 146       sqlite3_free(zSql);
 147     }
 148
 149     rc = sqlite3_step(pCk);
 150     if( rc!=SQLITE_ROW
 151      || sqlite3_column_text(pCk, 0)==0
 152      || strcmp((const char*)sqlite3_column_text(pCk,0),"ok")!=0
 153     ){
 154       *pbCorrupt = 1;
 155       sqlite3_finalize(pCk);
 156       sqlite3_finalize(pTestStmt);
 157       return SQLITE_CORRUPT;
 158     }
 159     sqlite3_finalize(pCk);
 160
 161     /*
 162     ** If inverting the scan order also results in a miss, assume that the
 163     ** query is ambiguous and do not report a fault.
 164     */
 165     sqlite3_db_config(db, SQLITE_DBCONFIG_REVERSE_SCANORDER, -1, &iOrigRSO);
 166     sqlite3_db_config(db, SQLITE_DBCONFIG_REVERSE_SCANORDER, !iOrigRSO, 0);
 167     sqlite3_prepare_v2(db, sqlite3_sql(pStmt), -1, &pCk, 0);
 168     sqlite3_db_config(db, SQLITE_DBCONFIG_REVERSE_SCANORDER, iOrigRSO, 0);
 169     if( eVerbosity>=2 ){
 170       char *zSql = sqlite3_expanded_sql(pCk);
 171       printf("invariant-validity-check #2:\n%s\n", zSql);
 172       sqlite3_free(zSql);
 173     }
 174     while( (rc = sqlite3_step(pCk))==SQLITE_ROW ){
 175       for(i=0; i<nCol; i++){
 176         if( !sameValue(pStmt, i, pTestStmt, i, 0) ) break;
 177       }
 178       if( i>=nCol ) break;
 179     }
 180     sqlite3_finalize(pCk);
 181     if( rc==SQLITE_DONE ){
 182       sqlite3_finalize(pTestStmt);
 183       return SQLITE_DONE;
 184     }
 185
 186     /* The original sameValue() comparison assumed a collating sequence
 187     ** of "binary".  It can sometimes get an incorrect result for different
 188     ** collating sequences.  So rerun the test with no assumptions about
 189     ** collations.
 190     */
 191     rc = sqlite3_prepare_v2(db,
 192        "SELECT ?1=?2 OR ?1=?2 COLLATE nocase OR ?1=?2 COLLATE rtrim",
 193        -1, &pCk, 0);
 194     if( rc==SQLITE_OK ){
 195       if( eVerbosity>=2 ){
 196         char *zSql = sqlite3_expanded_sql(pCk);
 197         printf("invariant-validity-check #3:\n%s\n", zSql);
 198         sqlite3_free(zSql);
 199       }
 200
 201       sqlite3_reset(pTestStmt);
 202       while( (rc = sqlite3_step(pTestStmt))==SQLITE_ROW ){
 203         for(i=0; i<nCol; i++){
 204           if( !sameValue(pStmt, i, pTestStmt, i, pCk) ) break;
 205         }
 206         if( i>=nCol ){
 207           sqlite3_finalize(pCk);
 208           goto not_a_fault;
 209         }
 210       }
 211     }
 212     sqlite3_finalize(pCk);
 213
 214     /* Invariants do not necessarily work if there are virtual tables
 215     ** involved in the query */
 216     rc = sqlite3_prepare_v2(db,
 217             "SELECT 1 FROM bytecode(?1) WHERE opcode='VOpen'", -1, &pCk, 0);
 218     if( rc==SQLITE_OK ){
 219       if( eVerbosity>=2 ){
 220         char *zSql = sqlite3_expanded_sql(pCk);
 221         printf("invariant-validity-check #4:\n%s\n", zSql);
 222         sqlite3_free(zSql);
 223       }
 224       sqlite3_bind_pointer(pCk, 1, pStmt, "stmt-pointer", 0);
 225       rc = sqlite3_step(pCk);
 226     }
 227     sqlite3_finalize(pCk);
 228     if( rc==SQLITE_DONE ){
 229       reportInvariantFailed(pStmt, pTestStmt, iRow, dbOpt, noOpt);
 230       return SQLITE_INTERNAL;
 231     }else if( eVerbosity>0 ){
 232       printf("invariant-error ignored due to the use of virtual tables\n");
 233     }
 234   }
 235 not_a_fault:
 236   sqlite3_finalize(pTestStmt);
 237   return SQLITE_OK;
 238 }
 239
 240 /*
 241 ** Generate SQL used to test a statement invariant.
 242 **
 243 ** Return 0 if the iCnt is out of range.
 244 **
 245 ** iCnt meanings:
 246 **
 247 **   0     SELECT * FROM (<query>)
 248 **   1     SELECT DISTINCT * FROM (<query>)
 249 **   2     SELECT * FROM (<query>) WHERE ORDER BY 1
 250 **   3     SELECT DISTINCT * FROM (<query>) ORDER BY 1
 251 **   4     SELECT * FROM (<query>) WHERE <all-columns>=<all-values>
 252 **   5     SELECT DISTINCT * FROM (<query>) WHERE <all-columns=<all-values
 253 **   6     SELECT * FROM (<query>) WHERE <all-column>=<all-value> ORDER BY 1
 254 **   7     SELECT DISTINCT * FROM (<query>) WHERE <all-column>=<all-value>
 255 **                           ORDER BY 1
 256 **   N+0   SELECT * FROM (<query>) WHERE <nth-column>=<value>
 257 **   N+1   SELECT DISTINCT * FROM (<query>) WHERE <Nth-column>=<value>
 258 **   N+2   SELECT * FROM (<query>) WHERE <Nth-column>=<value> ORDER BY 1
 259 **   N+3   SELECT DISTINCT * FROM (<query>) WHERE <Nth-column>=<value>
 260 **                           ORDER BY N
 261 **
 262 */
 263 static char *fuzz_invariant_sql(sqlite3_stmt *pStmt, int iCnt){
 264   const char *zIn;
 265   size_t nIn;
 266   const char *zAnd = "WHERE";
 267   int i, j;
 268   sqlite3_str *pTest;
 269   sqlite3_stmt *pBase = 0;
 270   sqlite3 *db = sqlite3_db_handle(pStmt);
 271   int rc;
 272   int nCol = sqlite3_column_count(pStmt);
 273   int mxCnt;
 274   int bDistinct = 0;
 275   int bOrderBy = 0;
 276   int nParam = sqlite3_bind_parameter_count(pStmt);
 277
 278   switch( iCnt % 4 ){
 279     case 1:  bDistinct = 1;              break;
 280     case 2:  bOrderBy = 1;               break;
 281     case 3:  bDistinct = bOrderBy = 1;   break;
 282   }
 283   iCnt /= 4;
 284   mxCnt = nCol;
 285   if( iCnt<0 || iCnt>mxCnt ) return 0;
 286   zIn = sqlite3_sql(pStmt);
 287   if( zIn==0 ) return 0;
 288   nIn = strlen(zIn);
 289   while( nIn>0 && (isspace(zIn[nIn-1]) || zIn[nIn-1]==';') ) nIn--;
 290   if( strchr(zIn, '?') ) return 0;
 291   pTest = sqlite3_str_new(0);
 292   sqlite3_str_appendf(pTest, "SELECT %s* FROM (",
 293                       bDistinct ? "DISTINCT " : "");
 294   sqlite3_str_append(pTest, zIn, (int)nIn);
 295   sqlite3_str_append(pTest, ")", 1);
 296   rc = sqlite3_prepare_v2(db, sqlite3_str_value(pTest), -1, &pBase, 0);
 297   if( rc ){
 298     sqlite3_finalize(pBase);
 299     pBase = pStmt;
 300   }
 301   for(i=0; i<sqlite3_column_count(pStmt); i++){
 302     const char *zColName = sqlite3_column_name(pBase,i);
 303     const char *zSuffix = zColName ? strrchr(zColName, ':') : 0;
 304     if( zSuffix
 305      && isdigit(zSuffix[1])
 306      && (zSuffix[1]>'3' || isdigit(zSuffix[2]))
 307     ){
 308       /* This is a randomized column name and so cannot be used in the
 309       ** WHERE clause. */
 310       continue;
 311     }
 312     for(j=0; j<i; j++){
 313       const char *zPrior = sqlite3_column_name(pBase, j);
 314       if( sqlite3_stricmp(zPrior, zColName)==0 ) break;
 315     }
 316     if( j<i ){
 317       /* Duplicate column name */
 318       continue;
 319     }
 320     if( iCnt==0 ) continue;
 321     if( iCnt>1 && i+2!=iCnt ) continue;
 322     if( zColName==0 ) continue;
 323     if( sqlite3_column_type(pStmt, i)==SQLITE_NULL ){
 324       sqlite3_str_appendf(pTest, " %s \"%w\" ISNULL", zAnd, zColName);
 325     }else{
 326       sqlite3_str_appendf(pTest, " %s \"%w\"=?%d", zAnd, zColName,
 327                           i+1+nParam);
 328     }
 329     zAnd = "AND";
 330   }
 331   if( pBase!=pStmt ) sqlite3_finalize(pBase);
 332   if( bOrderBy ){
 333     sqlite3_str_appendf(pTest, " ORDER BY %d", iCnt>2 ? iCnt-1 : 1);
 334   }
 335   return sqlite3_str_finish(pTest);
 336 }
 337
 338 /*
 339 ** Return true if and only if v1 and is the same as v2.
 340 */
 341 static int sameValue(
 342   sqlite3_stmt *pS1, int i1,       /* Value to text on the left */
 343   sqlite3_stmt *pS2, int i2,       /* Value to test on the right */
 344   sqlite3_stmt *pTestCompare       /* COLLATE comparison statement or NULL */
 345 ){
 346   int x = 1;
 347   int t1 = sqlite3_column_type(pS1,i1);
 348   int t2 = sqlite3_column_type(pS2,i2);
 349   if( t1!=t2 ){
 350     if( (t1==SQLITE_INTEGER && t2==SQLITE_FLOAT)
 351      || (t1==SQLITE_FLOAT && t2==SQLITE_INTEGER)
 352     ){
 353       /* Comparison of numerics is ok */
 354     }else{
 355       return 0;
 356     }
 357   }
 358   switch( sqlite3_column_type(pS1,i1) ){
 359     case SQLITE_INTEGER: {
 360       x =  sqlite3_column_int64(pS1,i1)==sqlite3_column_int64(pS2,i2);
 361       break;
 362     }
 363     case SQLITE_FLOAT: {
 364       x = sqlite3_column_double(pS1,i1)==sqlite3_column_double(pS2,i2);
 365       break;
 366     }
 367     case SQLITE_TEXT: {
 368       int e1 = sqlite3_value_encoding(sqlite3_column_value(pS1,i1));
 369       int e2 = sqlite3_value_encoding(sqlite3_column_value(pS2,i2));
 370       if( e1!=e2 ){
 371         const char *z1 = (const char*)sqlite3_column_text(pS1,i1);
 372         const char *z2 = (const char*)sqlite3_column_text(pS2,i2);
 373         x = ((z1==0 && z2==0) || (z1!=0 && z2!=0 && strcmp(z1,z1)==0));
 374         printf("Encodings differ.  %d on left and %d on right\n", e1, e2);
 375         abort();
 376       }
 377       if( pTestCompare ){
 378         sqlite3_bind_value(pTestCompare, 1, sqlite3_column_value(pS1,i1));
 379         sqlite3_bind_value(pTestCompare, 2, sqlite3_column_value(pS2,i2));
 380         x = sqlite3_step(pTestCompare)==SQLITE_ROW
 381                       && sqlite3_column_int(pTestCompare,0)!=0;
 382         sqlite3_reset(pTestCompare);
 383         break;
 384       }
 385       if( e1!=SQLITE_UTF8 ){
 386         int len1 = sqlite3_column_bytes16(pS1,i1);
 387         const unsigned char *b1 = sqlite3_column_blob(pS1,i1);
 388         int len2 = sqlite3_column_bytes16(pS2,i2);
 389         const unsigned char *b2 = sqlite3_column_blob(pS2,i2);
 390         if( len1!=len2 ){
 391           x = 0;
 392         }else if( len1==0 ){
 393           x = 1;
 394         }else{
 395           x = (b1!=0 && b2!=0 && memcmp(b1,b2,len1)==0);
 396         }
 397         break;
 398       }
 399       /* Fall through into the SQLITE_BLOB case */
 400     }
 401     case SQLITE_BLOB: {
 402       int len1 = sqlite3_column_bytes(pS1,i1);
 403       const unsigned char *b1 = sqlite3_column_blob(pS1,i1);
 404       int len2 = sqlite3_column_bytes(pS2,i2);
 405       const unsigned char *b2 = sqlite3_column_blob(pS2,i2);
 406       if( len1!=len2 ){
 407         x = 0;
 408       }else if( len1==0 ){
 409         x = 1;
 410       }else{
 411         x = (b1!=0 && b2!=0 && memcmp(b1,b2,len1)==0);
 412       }
 413       break;
 414     }
 415   }
 416   return x;
 417 }
 418
 419 /*
 420 ** Print binary data as hex
 421 */
 422 static void printHex(const unsigned char *a, int n, int mx){
 423   int j;
 424   for(j=0; j<mx && j<n; j++){
 425     printf("%02x", a[j]);
 426   }
 427   if( j<n ) printf("...");
 428 }
 429
 430 /*
 431 ** Print a single row from the prepared statement
 432 */
 433 static void printRow(sqlite3_stmt *pStmt, int iRow){
 434   int i, n, nCol;
 435   unsigned const char *data;
 436   nCol = sqlite3_column_count(pStmt);
 437   for(i=0; i<nCol; i++){
 438     printf("row%d.col%d = ", iRow, i);
 439     switch( sqlite3_column_type(pStmt, i) ){
 440       case SQLITE_NULL: {
 441         printf("NULL\n");
 442         break;
 443       }
 444       case SQLITE_INTEGER: {
 445         printf("(integer) %lld\n", sqlite3_column_int64(pStmt, i));
 446         break;
 447       }
 448       case SQLITE_FLOAT: {
 449         printf("(float) %f\n", sqlite3_column_double(pStmt, i));
 450         break;
 451       }
 452       case SQLITE_TEXT: {
 453         switch( sqlite3_value_encoding(sqlite3_column_value(pStmt,i)) ){
 454           case SQLITE_UTF8: {
 455             printf("(utf8) x'");
 456             n = sqlite3_column_bytes(pStmt, i);
 457             data = sqlite3_column_blob(pStmt, i);
 458             printHex(data, n, 35);
 459             printf("'\n");
 460             break;
 461           }
 462           case SQLITE_UTF16BE: {
 463             printf("(utf16be) x'");
 464             n = sqlite3_column_bytes16(pStmt, i);
 465             data = sqlite3_column_blob(pStmt, i);
 466             printHex(data, n, 35);
 467             printf("'\n");
 468             break;
 469           }
 470           case SQLITE_UTF16LE: {
 471             printf("(utf16le) x'");
 472             n = sqlite3_column_bytes16(pStmt, i);
 473             data = sqlite3_column_blob(pStmt, i);
 474             printHex(data, n, 35);
 475             printf("'\n");
 476             break;
 477           }
 478           default: {
 479             printf("Illegal return from sqlite3_value_encoding(): %d\n",
 480                 sqlite3_value_encoding(sqlite3_column_value(pStmt,i)));
 481             abort();
 482           }
 483         }
 484         break;
 485       }
 486       case SQLITE_BLOB: {
 487         n = sqlite3_column_bytes(pStmt, i);
 488         data = sqlite3_column_blob(pStmt, i);
 489         printf("(blob %d bytes) x'", n);
 490         printHex(data, n, 35);
 491         printf("'\n");
 492         break;
 493       }
 494     }
 495   }
 496 }
 497
 498 /*
 499 ** Report a failure of the invariant:  The current output row of pOrig
 500 ** does not appear in any row of the output from pTest.
 501 */
 502 static void reportInvariantFailed(
 503   sqlite3_stmt *pOrig,   /* The original query */
 504   sqlite3_stmt *pTest,   /* The alternative test query with a missing row */
 505   int iRow,              /* Row number in pOrig */
 506   unsigned int dbOpt,    /* Optimization flags on pOrig */
 507   int noOpt              /* True if opt flags inverted for pTest */
 508 ){
 509   int iTestRow = 0;
 510   printf("Invariant check failed on row %d.\n", iRow);
 511   printf("Original query (opt-flags: 0x%08x) --------------------------\n",
 512          dbOpt);
 513   printf("%s\n", sqlite3_expanded_sql(pOrig));
 514   printf("Alternative query (opt-flags: 0x%08x) -----------------------\n",
 515          noOpt ? ~dbOpt : dbOpt);
 516   printf("%s\n", sqlite3_expanded_sql(pTest));
 517   printf("Result row that is missing from the alternative -----------------\n");
 518   printRow(pOrig, iRow);
 519   printf("Complete results from the alternative query ---------------------\n");
 520   sqlite3_reset(pTest);
 521   while( sqlite3_step(pTest)==SQLITE_ROW ){
 522     iTestRow++;
 523     printRow(pTest, iTestRow);
 524   }
 525   sqlite3_finalize(pTest);
 526   abort();
 527 }