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 */
fuzz_invariant(sqlite3 * db,sqlite3_stmt * pStmt,int iCnt,int iRow,int nRow,int * pbCorrupt,int eVerbosity)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 #%d:\n%s\n", 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
119 /* This is not a fault if the database file is corrupt, because anything
120 ** can happen with a corrupt database file */
121 rc = sqlite3_prepare_v2(db, "PRAGMA integrity_check", -1, &pCk, 0);
122 if( rc ){
123 sqlite3_finalize(pCk);
124 sqlite3_finalize(pTestStmt);
125 return rc;
126 }
127 rc = sqlite3_step(pCk);
128 if( rc!=SQLITE_ROW
129 || sqlite3_column_text(pCk, 0)==0
130 || strcmp((const char*)sqlite3_column_text(pCk,0),"ok")!=0
131 ){
132 *pbCorrupt = 1;
133 sqlite3_finalize(pCk);
134 sqlite3_finalize(pTestStmt);
135 return SQLITE_CORRUPT;
136 }
137 sqlite3_finalize(pCk);
138
139 if( sqlite3_strlike("%group%by%order%by%desc%",sqlite3_sql(pStmt),0)==0 ){
140 /* dbsqlfuzz crash-647c162051c9b23ce091b7bbbe5125ce5f00e922
141 ** Original statement is:
142 **
143 ** SELECT a,c,d,b,'' FROM t1 GROUP BY 1 HAVING d<>345 ORDER BY a DESC;
144 **
145 ** The values of c, d, and b are indeterminate and change when the
146 ** enclosed in the test query because the DESC is dropped.
147 **
148 ** SELECT * FROM (...) WHERE "a"==0
149 */
150 goto not_a_fault;
151 }
152
153 if( sqlite3_strlike("%limit%)%order%by%", sqlite3_sql(pTestStmt),0)==0 ){
154 /* crash-89bd6a6f8c6166e9a4c5f47b3e70b225f69b76c6
155 ** Original statement is:
156 **
157 ** SELECT a,b,c* FROM t1 LIMIT 1%5<4
158 **
159 ** When running:
160 **
161 ** SELECT * FROM (...) ORDER BY 1
162 **
163 ** A different subset of the rows come out
164 */
165 goto not_a_fault;
166 }
167
168 /* The original sameValue() comparison assumed a collating sequence
169 ** of "binary". It can sometimes get an incorrect result for different
170 ** collating sequences. So rerun the test with no assumptions about
171 ** collations.
172 */
173 rc = sqlite3_prepare_v2(db,
174 "SELECT ?1=?2 OR ?1=?2 COLLATE nocase OR ?1=?2 COLLATE rtrim",
175 -1, &pCk, 0);
176 if( rc==SQLITE_OK ){
177 sqlite3_reset(pTestStmt);
178 while( (rc = sqlite3_step(pTestStmt))==SQLITE_ROW ){
179 for(i=0; i<nCol; i++){
180 if( !sameValue(pStmt, i, pTestStmt, i, pCk) ) break;
181 }
182 if( i>=nCol ){
183 sqlite3_finalize(pCk);
184 goto not_a_fault;
185 }
186 }
187 }
188 sqlite3_finalize(pCk);
189
190 /* Invariants do not necessarily work if there are virtual tables
191 ** involved in the query */
192 rc = sqlite3_prepare_v2(db,
193 "SELECT 1 FROM bytecode(?1) WHERE opcode='VOpen'", -1, &pCk, 0);
194 if( rc==SQLITE_OK ){
195 sqlite3_bind_pointer(pCk, 1, pStmt, "stmt-pointer", 0);
196 rc = sqlite3_step(pCk);
197 }
198 sqlite3_finalize(pCk);
199 if( rc==SQLITE_DONE ){
200 reportInvariantFailed(pStmt, pTestStmt, iRow);
201 return SQLITE_INTERNAL;
202 }else if( eVerbosity>0 ){
203 printf("invariant-error ignored due to the use of virtual tables\n");
204 }
205 }
206 not_a_fault:
207 sqlite3_finalize(pTestStmt);
208 return SQLITE_OK;
209 }
210
211
212 /*
213 ** Generate SQL used to test a statement invariant.
214 **
215 ** Return 0 if the iCnt is out of range.
216 **
217 ** iCnt meanings:
218 **
219 ** 0 SELECT * FROM (<query>)
220 ** 1 SELECT DISTINCT * FROM (<query>)
221 ** 2 SELECT * FROM (<query>) WHERE ORDER BY 1
222 ** 3 SELECT DISTINCT * FROM (<query>) ORDER BY 1
223 ** 4 SELECT * FROM (<query>) WHERE <all-columns>=<all-values>
224 ** 5 SELECT DISTINCT * FROM (<query>) WHERE <all-columns=<all-values
225 ** 6 SELECT * FROM (<query>) WHERE <all-column>=<all-value> ORDER BY 1
226 ** 7 SELECT DISTINCT * FROM (<query>) WHERE <all-column>=<all-value>
227 ** ORDER BY 1
228 ** N+0 SELECT * FROM (<query>) WHERE <nth-column>=<value>
229 ** N+1 SELECT DISTINCT * FROM (<query>) WHERE <Nth-column>=<value>
230 ** N+2 SELECT * FROM (<query>) WHERE <Nth-column>=<value> ORDER BY 1
231 ** N+3 SELECT DISTINCT * FROM (<query>) WHERE <Nth-column>=<value>
232 ** ORDER BY N
233 **
234 */
fuzz_invariant_sql(sqlite3_stmt * pStmt,int iCnt)235 static char *fuzz_invariant_sql(sqlite3_stmt *pStmt, int iCnt){
236 const char *zIn;
237 size_t nIn;
238 const char *zAnd = "WHERE";
239 int i;
240 sqlite3_str *pTest;
241 sqlite3_stmt *pBase = 0;
242 sqlite3 *db = sqlite3_db_handle(pStmt);
243 int rc;
244 int nCol = sqlite3_column_count(pStmt);
245 int mxCnt;
246 int bDistinct = 0;
247 int bOrderBy = 0;
248 int nParam = sqlite3_bind_parameter_count(pStmt);
249
250 switch( iCnt % 4 ){
251 case 1: bDistinct = 1; break;
252 case 2: bOrderBy = 1; break;
253 case 3: bDistinct = bOrderBy = 1; break;
254 }
255 iCnt /= 4;
256 mxCnt = nCol;
257 if( iCnt<0 || iCnt>mxCnt ) return 0;
258 zIn = sqlite3_sql(pStmt);
259 if( zIn==0 ) return 0;
260 nIn = strlen(zIn);
261 while( nIn>0 && (isspace(zIn[nIn-1]) || zIn[nIn-1]==';') ) nIn--;
262 if( strchr(zIn, '?') ) return 0;
263 pTest = sqlite3_str_new(0);
264 sqlite3_str_appendf(pTest, "SELECT %s* FROM (",
265 bDistinct ? "DISTINCT " : "");
266 sqlite3_str_append(pTest, zIn, (int)nIn);
267 sqlite3_str_append(pTest, ")", 1);
268 rc = sqlite3_prepare_v2(db, sqlite3_str_value(pTest), -1, &pBase, 0);
269 if( rc ){
270 sqlite3_finalize(pBase);
271 pBase = pStmt;
272 }
273 for(i=0; i<sqlite3_column_count(pStmt); i++){
274 const char *zColName = sqlite3_column_name(pBase,i);
275 const char *zSuffix = zColName ? strrchr(zColName, ':') : 0;
276 if( zSuffix
277 && isdigit(zSuffix[1])
278 && (zSuffix[1]>'3' || isdigit(zSuffix[2]))
279 ){
280 /* This is a randomized column name and so cannot be used in the
281 ** WHERE clause. */
282 continue;
283 }
284 if( iCnt==0 ) continue;
285 if( iCnt>1 && i+2!=iCnt ) continue;
286 if( zColName==0 ) continue;
287 if( sqlite3_column_type(pStmt, i)==SQLITE_NULL ){
288 sqlite3_str_appendf(pTest, " %s \"%w\" ISNULL", zAnd, zColName);
289 }else{
290 sqlite3_str_appendf(pTest, " %s \"%w\"=?%d", zAnd, zColName,
291 i+1+nParam);
292 }
293 zAnd = "AND";
294 }
295 if( pBase!=pStmt ) sqlite3_finalize(pBase);
296 if( bOrderBy ){
297 sqlite3_str_appendf(pTest, " ORDER BY %d", iCnt>2 ? iCnt-1 : 1);
298 }
299 return sqlite3_str_finish(pTest);
300 }
301
302 /*
303 ** Return true if and only if v1 and is the same as v2.
304 */
sameValue(sqlite3_stmt * pS1,int i1,sqlite3_stmt * pS2,int i2,sqlite3_stmt * pTestCompare)305 static int sameValue(
306 sqlite3_stmt *pS1, int i1, /* Value to text on the left */
307 sqlite3_stmt *pS2, int i2, /* Value to test on the right */
308 sqlite3_stmt *pTestCompare /* COLLATE comparison statement or NULL */
309 ){
310 int x = 1;
311 int t1 = sqlite3_column_type(pS1,i1);
312 int t2 = sqlite3_column_type(pS2,i2);
313 if( t1!=t2 ){
314 if( (t1==SQLITE_INTEGER && t2==SQLITE_FLOAT)
315 || (t1==SQLITE_FLOAT && t2==SQLITE_INTEGER)
316 ){
317 /* Comparison of numerics is ok */
318 }else{
319 return 0;
320 }
321 }
322 switch( sqlite3_column_type(pS1,i1) ){
323 case SQLITE_INTEGER: {
324 x = sqlite3_column_int64(pS1,i1)==sqlite3_column_int64(pS2,i2);
325 break;
326 }
327 case SQLITE_FLOAT: {
328 x = sqlite3_column_double(pS1,i1)==sqlite3_column_double(pS2,i2);
329 break;
330 }
331 case SQLITE_TEXT: {
332 int e1 = sqlite3_value_encoding(sqlite3_column_value(pS1,i1));
333 int e2 = sqlite3_value_encoding(sqlite3_column_value(pS2,i2));
334 if( e1!=e2 ){
335 const char *z1 = (const char*)sqlite3_column_text(pS1,i1);
336 const char *z2 = (const char*)sqlite3_column_text(pS2,i2);
337 x = ((z1==0 && z2==0) || (z1!=0 && z2!=0 && strcmp(z1,z1)==0));
338 printf("Encodings differ. %d on left and %d on right\n", e1, e2);
339 abort();
340 }
341 if( pTestCompare ){
342 sqlite3_bind_value(pTestCompare, 1, sqlite3_column_value(pS1,i1));
343 sqlite3_bind_value(pTestCompare, 2, sqlite3_column_value(pS2,i2));
344 x = sqlite3_step(pTestCompare)==SQLITE_ROW
345 && sqlite3_column_int(pTestCompare,0)!=0;
346 sqlite3_reset(pTestCompare);
347 break;
348 }
349 if( e1!=SQLITE_UTF8 ){
350 int len1 = sqlite3_column_bytes16(pS1,i1);
351 const unsigned char *b1 = sqlite3_column_blob(pS1,i1);
352 int len2 = sqlite3_column_bytes16(pS2,i2);
353 const unsigned char *b2 = sqlite3_column_blob(pS2,i2);
354 if( len1!=len2 ){
355 x = 0;
356 }else if( len1==0 ){
357 x = 1;
358 }else{
359 x = (b1!=0 && b2!=0 && memcmp(b1,b2,len1)==0);
360 }
361 break;
362 }
363 /* Fall through into the SQLITE_BLOB case */
364 }
365 case SQLITE_BLOB: {
366 int len1 = sqlite3_column_bytes(pS1,i1);
367 const unsigned char *b1 = sqlite3_column_blob(pS1,i1);
368 int len2 = sqlite3_column_bytes(pS2,i2);
369 const unsigned char *b2 = sqlite3_column_blob(pS2,i2);
370 if( len1!=len2 ){
371 x = 0;
372 }else if( len1==0 ){
373 x = 1;
374 }else{
375 x = (b1!=0 && b2!=0 && memcmp(b1,b2,len1)==0);
376 }
377 break;
378 }
379 }
380 return x;
381 }
382
383 /*
384 ** Print binary data as hex
385 */
printHex(const unsigned char * a,int n,int mx)386 static void printHex(const unsigned char *a, int n, int mx){
387 int j;
388 for(j=0; j<mx && j<n; j++){
389 printf("%02x", a[j]);
390 }
391 if( j<n ) printf("...");
392 }
393
394 /*
395 ** Print a single row from the prepared statement
396 */
printRow(sqlite3_stmt * pStmt,int iRow)397 static void printRow(sqlite3_stmt *pStmt, int iRow){
398 int i, n, nCol;
399 unsigned const char *data;
400 nCol = sqlite3_column_count(pStmt);
401 for(i=0; i<nCol; i++){
402 printf("row%d.col%d = ", iRow, i);
403 switch( sqlite3_column_type(pStmt, i) ){
404 case SQLITE_NULL: {
405 printf("NULL\n");
406 break;
407 }
408 case SQLITE_INTEGER: {
409 printf("(integer) %lld\n", sqlite3_column_int64(pStmt, i));
410 break;
411 }
412 case SQLITE_FLOAT: {
413 printf("(float) %f\n", sqlite3_column_double(pStmt, i));
414 break;
415 }
416 case SQLITE_TEXT: {
417 switch( sqlite3_value_encoding(sqlite3_column_value(pStmt,i)) ){
418 case SQLITE_UTF8: {
419 printf("(utf8) x'");
420 n = sqlite3_column_bytes(pStmt, i);
421 data = sqlite3_column_blob(pStmt, i);
422 printHex(data, n, 35);
423 printf("'\n");
424 break;
425 }
426 case SQLITE_UTF16BE: {
427 printf("(utf16be) x'");
428 n = sqlite3_column_bytes16(pStmt, i);
429 data = sqlite3_column_blob(pStmt, i);
430 printHex(data, n, 35);
431 printf("'\n");
432 break;
433 }
434 case SQLITE_UTF16LE: {
435 printf("(utf16le) x'");
436 n = sqlite3_column_bytes16(pStmt, i);
437 data = sqlite3_column_blob(pStmt, i);
438 printHex(data, n, 35);
439 printf("'\n");
440 break;
441 }
442 default: {
443 printf("Illegal return from sqlite3_value_encoding(): %d\n",
444 sqlite3_value_encoding(sqlite3_column_value(pStmt,i)));
445 abort();
446 }
447 }
448 break;
449 }
450 case SQLITE_BLOB: {
451 n = sqlite3_column_bytes(pStmt, i);
452 data = sqlite3_column_blob(pStmt, i);
453 printf("(blob %d bytes) x'", n);
454 printHex(data, n, 35);
455 printf("'\n");
456 break;
457 }
458 }
459 }
460 }
461
462 /*
463 ** Report a failure of the invariant: The current output row of pOrig
464 ** does not appear in any row of the output from pTest.
465 */
reportInvariantFailed(sqlite3_stmt * pOrig,sqlite3_stmt * pTest,int iRow)466 static void reportInvariantFailed(
467 sqlite3_stmt *pOrig, /* The original query */
468 sqlite3_stmt *pTest, /* The alternative test query with a missing row */
469 int iRow /* Row number in pOrig */
470 ){
471 int iTestRow = 0;
472 printf("Invariant check failed on row %d.\n", iRow);
473 printf("Original query --------------------------------------------------\n");
474 printf("%s\n", sqlite3_expanded_sql(pOrig));
475 printf("Alternative query -----------------------------------------------\n");
476 printf("%s\n", sqlite3_expanded_sql(pTest));
477 printf("Result row that is missing from the alternative -----------------\n");
478 printRow(pOrig, iRow);
479 printf("Complete results from the alternative query ---------------------\n");
480 sqlite3_reset(pTest);
481 while( sqlite3_step(pTest)==SQLITE_ROW ){
482 iTestRow++;
483 printRow(pTest, iTestRow);
484 }
485 sqlite3_finalize(pTest);
486 abort();
487 }
488