9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
|
-
+
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
+
+
+
-
+
+
+
+
+
+
-
+
-
-
+
+
-
-
+
+
+
+
+
+
+
+
+
+
-
+
+
+
+
+
+
+
+
+
+
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
|
#
#***********************************************************************
# This file implements regression tests for SQLite library. The
# focus of this file is generating semi-random strings of SQL
# (a.k.a. "fuzz") and sending it into the parser to try to generate
# errors.
#
# $Id: fuzz.test,v 1.5 2007/05/11 07:08:29 danielk1977 Exp $
# $Id: fuzz.test,v 1.6 2007/05/11 10:10:33 danielk1977 Exp $
set testdir [file dirname $argv0]
source $testdir/tester.tcl
proc fuzz {TemplateList} {
set n [llength $TemplateList]
set i [expr {int(rand()*$n)}]
return [subst -novar [lindex $TemplateList $i]]
return [uplevel 1 subst -novar [list [lindex $TemplateList $i]]]
}
# Fuzzy generation primitives:
#
# Literal
# UnaryOp
# BinaryOp
# Expr
# Table
# Select
# Insert
#
# Returns a string representing an SQL literal.
#
proc Literal {} {
set TemplateList {
456 0 -456 1 -1
2147483648 2147483647 2147483649 -2147483647 -2147483648 -2147483649
'The' 'first' 'experiments' 'in' 'hardware' 'fault' 'injection'
zeroblob(1000)
NULL
56.1 -56.1
123456789.1234567899
}
fuzz $TemplateList
}
# Returns a string containing an SQL unary operator (e.g. "+" or "NOT").
#
proc UnaryOp {} {
set TemplateList {+ - NOT}
set TemplateList {+ - NOT ~}
fuzz $TemplateList
}
# Returns a string containing an SQL binary operator (e.g. "*" or "/").
#
proc BinaryOp {} {
set TemplateList {+ - % * / AND OR LIKE GLOB}
set TemplateList {
|| * / % + - << >> & | < <= > >= = == != <> AND OR
LIKE GLOB {NOT LIKE}
}
fuzz $TemplateList
}
# Return the complete text of an SQL expression.
#
set ::ExprDepth 0
proc Expr {} {
proc Expr { {c {}} } {
incr ::ExprDepth
set TemplateList {[Literal]}
if {$::ExprDepth < 100} {
set TemplateList [concat $c {[Literal]}]
if {$::ExprDepth < 25} {
lappend TemplateList \
{[Expr] [BinaryOp] [Expr]} \
{[UnaryOp] [Expr]}
{[Expr $c] [BinaryOp] [Expr $c]} \
{[UnaryOp] [Expr $c]} \
{[Expr $c] ISNULL} \
{[Expr $c] NOTNULL} \
{CAST([Expr $c] AS blob)} \
{CAST([Expr $c] AS text)} \
{CAST([Expr $c] AS integer)} \
{CAST([Expr $c] AS real)} \
{CASE WHEN [Expr $c] THEN [Expr $c] ELSE [Expr $c] END} \
{[Literal]} {[Literal]} {[Literal]}
}
if {$::SelectDepth < 10} {
lappend TemplateList {([Select 1])}
lappend TemplateList \
{([Select 1])} \
{[Expr $c] IN ([Select 1])} \
{[Expr $c] NOT IN ([Select 1])} \
{EXISTS ([Select 1])} \
}
set res [fuzz $TemplateList]
incr ::ExprDepth -1
return $res
}
# Return a valid table name.
#
set ::TableList [list]
proc Table {} {
set TemplateList [concat sqlite_master $::TableList]
fuzz $TemplateList
}
# Return a SELECT statement.
#
set ::SelectDepth 0
proc Select {{isExpr 0}} {
incr ::SelectDepth
set TemplateList {
{SELECT [Expr]}
{SELECT [Literal]}
}
if {$::SelectDepth < 5} {
lappend TemplateList \
{SELECT [Expr] FROM ([Select])} \
{SELECT [Expr] FROM [Table]}
{SELECT [Expr] FROM [Table]} \
if {0 == $isExpr} {
lappend TemplateList \
{SELECT [Expr], [Expr] FROM ([Select]) ORDER BY [Expr]} \
{SELECT * FROM ([Select]) ORDER BY [Expr]} \
{SELECT * FROM [Table]} \
{SELECT * FROM [Table] WHERE [Expr]} \
}
}
set res [fuzz $TemplateList]
incr ::SelectDepth -1
set res
}
# Generate and return a fuzzy INSERT statement.
#
proc Insert {} {
set TemplateList {
{INSERT INTO [Table] VALUES([Expr], [Expr], [Expr]);}
{INSERT INTO [Table] VALUES([Expr], [Expr], [Expr], [Expr]);}
{INSERT INTO [Table] VALUES([Expr], [Expr]);}
}
fuzz $TemplateList
}
########################################################################
set ::log [open fuzzy.log w]
#
# Usage: do_fuzzy_test <testname> ?<options>?
#
# -template
# -errorlist
#
proc do_fuzzy_test {testname args} {
set ::fuzzyopts(-errorlist) [list]
array set ::fuzzyopts $args
lappend ::fuzzyopts(-errorlist) {parser stack overflow} {ORDER BY column}
for {set ii 0} {$ii < 2000} {incr ii} {
do_test ${testname}.$ii {
set ::sql [subst $::fuzzyopts(-template)]
puts $::log $::sql
flush $::log
set rc [catch {execsql $::sql} msg]
set e 1
if {$rc} {
set e 0
foreach error $::fuzzyopts(-errorlist) {
if {0 == [string first $error $msg]} {
set e 1
break
}
}
}
if {$e == 0} {
puts ""
puts $::sql
puts $msg
}
set e
} {1}
}
}
#----------------------------------------------------------------
# These tests caused errors that were first caught by the tests
# in this file. They are still here.
do_test fuzz-1.1 {
execsql {
SELECT 'abc' LIKE X'ABCD';
|
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
|
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
|
+
+
+
+
+
+
-
-
+
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
-
+
+
+
-
-
+
+
+
+
+
+
-
-
+
-
-
-
+
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
|
do_test fuzz-1.7 {
execsql {
SELECT ( SELECT zeroblob(1000) FROM (
SELECT * FROM (SELECT 'first') ORDER BY NOT 'in')
)
}
} [execsql {SELECT zeroblob(1000)}]
do_test fuzz-1.8 {
execsql {
SELECT CAST(zeroblob(1000) AS text);
}
} {{}}
#----------------------------------------------------------------
# Test some fuzzily generated expressions.
#
for {set ii 0} {$ii < 2000} {incr ii} {
do_test fuzz-2.1.$ii {
do_fuzzy_test fuzz-2 -template { SELECT [Expr] }
set ::expr [Expr]
set rc [catch {execsql "SELECT $::expr"} msg]
set e [expr {
$rc == 0 ||
$msg eq "parser stack overflow" ||
0 == [string first "ORDER BY column number" $msg]
}]
if {$e == 0} {
puts ""
puts "SELECT $::expr"
puts $msg
}
set e
} {1}
}
do_test fuzz-3.1 {
execsql {
CREATE TABLE abc(a, b, c);
CREATE TABLE def(d, e, f);
CREATE TABLE ghi(g, h, i);
CREATE TABLE def(a, b, c);
CREATE TABLE ghi(a, b, c);
}
} {}
set ::TableList [list abc def ghi]
set ::TableList [list abc def ghi]
set ::ColumnList [list a b c]
#----------------------------------------------------------------
# Test some fuzzily generated SELECT statements.
#
do_fuzzy_test fuzz-3.2 -template {[Select]}
for {set ii 0} {$ii < 2000} {incr ii} {
do_test fuzz-2.2.$ii {
#----------------------------------------------------------------
# Insert a small amount of data into the database and then run
# some more generated SELECT statements.
#
do_test fuzz-4.1 {
set ::select [Select]
set rc [catch {execsql $::select} msg]
execsql {
set e [expr {$rc == 0 || $msg eq "parser stack overflow"}]
set e [expr {
$rc == 0 ||
INSERT INTO abc VALUES(1, 2, 3);
$msg eq "parser stack overflow" ||
0 == [string first "ORDER BY column number" $msg]
}]
if {$e == 0} {
puts ""
puts $::select
puts $msg
}
INSERT INTO abc VALUES(4, 5, 6);
INSERT INTO abc VALUES(7, 8, 9);
INSERT INTO def VALUES(1, 2, 3);
INSERT INTO def VALUES(4, 5, 6);
INSERT INTO def VALUES(7, 8, 9);
INSERT INTO ghi VALUES(1, 2, 3);
INSERT INTO ghi VALUES(4, 5, 6);
INSERT INTO ghi VALUES(7, 8, 9);
CREATE INDEX abc_i ON abc(a, b, c);
CREATE INDEX def_i ON def(c, a, b);
CREATE INDEX ghi_i ON ghi(b, c, a);
}
set e
} {1}
}
} {}
do_fuzzy_test fuzz-4.2 -template {[Select]}
#----------------------------------------------------------------
# Test some fuzzy INSERT statements:
#
do_test fuzz-5.1 {execsql BEGIN} {}
do_fuzzy_test fuzz-5.2 -template {[Insert]} -errorlist table
integrity_check fuzz-5.2.integrity
do_test fuzz-5.3 {execsql COMMIT} {}
integrity_check fuzz-5.4.integrity
do_fuzzy_test fuzz-6.1 -template {[Select]}
close $::log
finish_test
|