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