[MDEV-17783]  AddressSanitizer: stack-buffer-overflow in table_cond_selectivity with optimizer_use_condition_selectivity > 1, join_cache_level >2 Created: 2018-11-20  Updated: 2021-07-20  Resolved: 2021-07-03

Status: Closed
Project: MariaDB Server
Component/s: Optimizer
Affects Version/s: 10.0, 10.1, 10.2, 10.3, 10.4, 10.5
Fix Version/s: 10.2.40, 10.3.31, 10.4.21, 10.5.12, 10.6.4

Type: Bug Priority: Critical
Reporter: Alice Sherepa Assignee: Sergei Petrunia
Resolution: Fixed Votes: 0
Labels: None

Issue Links:
Blocks
blocks MDEV-23937 SIGSEGV in looped best_extension_by_l... Closed
Relates
relates to MDEV-23707 Fix condition selectivity computation... Stalled
relates to MDEV-25013 SIGSEGV in best_extension_by_limited_... Closed
relates to MDEV-26190 Stack smashing SIGSEGV in optimized b... Closed
relates to MDEV-23937 SIGSEGV in looped best_extension_by_l... Closed

 Description    

--source include/have_innodb.inc
 
set join_cache_level=3;
 
set optimizer_use_condition_selectivity=2;
 
 
 
CREATE TABLE t1 (c1 int, c2 int, c3 int, c4 int, c5 int, c6 int, c7 int, c8 int, c9 int, c10 int, c11 int, c12 int, c13 int, c14 int, c15 int, c16 int, c17 int, c18 int, c19 int, c20 int, c21 int, c22 int, c23 int, c24 int, c25 int, c26 int, c27 int, c28 int, c29 int, c30 int, c31 int, c32 int, c33 int, c34 int) ENGINE=InnoDB;
 
 
 
SELECT * FROM t1 WHERE (c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12, c13, c14, c15, c16, c17, c18, c19, c20, c21, c22, c23, c24, c25, c26, c27, c28, c29, c30, c31, c32, c33, c34) IN (SELECT * FROM t1) ;
 
 
 
#cleanup
 
drop table t1;

built as 

cmake . -DCMAKE_BUILD_TYPE=Debug -DWITHOUT_TOKUDB=1 -DWITH_SSL=bundled -DCONC_WITH_{UNITTEST,SSL}=OFF -DWITH_ASAN=ON

10.0 d0d0f88f2cd4da23c2c

 
Version: '10.0.38-MariaDB-debug'  socket: '/git/10.0/mysql-test/var/tmp/mysqld.1.sock'  port: 16000  Source distribution
 
=================================================================
 
==25866==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7f643c86816e at pc 0x00000072319b bp 0x7f643c868050 sp 0x7f643c868040
 
WRITE of size 2 at 0x7f643c86816e thread T21
 
    #0 0x72319a in table_cond_selectivity /git/10.0/sql/sql_select.cc:7521
 
    #1 0x73f40c in best_extension_by_limited_search /git/10.0/sql/sql_select.cc:7824
 
    #2 0x73f515 in best_extension_by_limited_search /git/10.0/sql/sql_select.cc:7831
 
    #3 0x7405ee in greedy_search /git/10.0/sql/sql_select.cc:6994
 
    #4 0x7405ee in choose_plan(JOIN*, unsigned long long) /git/10.0/sql/sql_select.cc:6571
 
    #5 0x7a1432 in make_join_statistics /git/10.0/sql/sql_select.cc:4078
 
    #6 0x7a1432 in JOIN::optimize_inner() /git/10.0/sql/sql_select.cc:1372
 
    #7 0x7a7233 in JOIN::optimize() /git/10.0/sql/sql_select.cc:1041
 
    #8 0x7a90b9 in mysql_select(THD*, Item***, TABLE_LIST*, unsigned int, List<Item>&, Item*, unsigned int, st_order*, st_order*, Item*, st_order*, unsigned long long, select_result*, st_select_lex_unit*, st_select_lex*) /git/10.0/sql/sql_select.cc:3334
 
    #9 0x7a98ad in handle_select(THD*, LEX*, select_result*, unsigned long) /git/10.0/sql/sql_select.cc:377
 
    #10 0x698ae8 in execute_sqlcom_select /git/10.0/sql/sql_parse.cc:5308
 
    #11 0x6afa53 in mysql_execute_command(THD*) /git/10.0/sql/sql_parse.cc:2558
 
    #12 0x6c5317 in mysql_parse(THD*, char*, unsigned int, Parser_state*) /git/10.0/sql/sql_parse.cc:6644
 
    #13 0x6c8998 in dispatch_command(enum_server_command, THD*, char*, unsigned int) /git/10.0/sql/sql_parse.cc:1301
 
    #14 0x6cd1b2 in do_command(THD*) /git/10.0/sql/sql_parse.cc:1003
 
    #15 0x9351c7 in do_handle_one_connection(THD*) /git/10.0/sql/sql_connect.cc:1377
 
    #16 0x935436 in handle_one_connection /git/10.0/sql/sql_connect.cc:1292
 
    #17 0x16945b5 in pfs_spawn_thread /git/10.0/storage/perfschema/pfs.cc:1861
 
    #18 0x7f644f9576b9 in start_thread (/lib/x86_64-linux-gnu/libpthread.so.0+0x76b9)
 
    #19 0x7f644f00241c in clone (/lib/x86_64-linux-gnu/libc.so.6+0x10741c)
 
 
 
Address 0x7f643c86816e is located in stack of thread T21 at offset 94 in frame
 
    #0 0x72289a in table_cond_selectivity /git/10.0/sql/sql_select.cc:7387
 
 
 
  This frame has 1 object(s):
 
    [32, 94) 'ref_keyuse_steps' <== Memory access at offset 94 overflows this variable
 
HINT: this may be a false positive if your program uses some custom stack unwind mechanism or swapcontext
 
      (longjmp and C++ exceptions *are* supported)
 
Thread T21 created by T0 here:
 
    #0 0x7f64503fb253 in pthread_create (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x36253)
 
    #1 0x169f01a in spawn_thread_v1 /git/10.0/storage/perfschema/pfs.cc:1911
 
 
 
SUMMARY: AddressSanitizer: stack-buffer-overflow /git/10.0/sql/sql_select.cc:7521 table_cond_selectivity
 
Shadow bytes around the buggy address:
 
  0x0fed07904fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 
  0x0fed07904fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 
  0x0fed07904ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 
  0x0fed07905000: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 
  0x0fed07905010: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 
=>0x0fed07905020: 00 00 f1 f1 f1 f1 00 00 00 00 00 00 00[06]f3 f3
 
  0x0fed07905030: f3 f3 f3 f3 f3 f3 00 00 00 00 00 00 00 00 00 00
 
  0x0fed07905040: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 
  0x0fed07905050: 00 00 00 00 00 00 f1 f1 f1 f1 00 f4 f4 f4 f2 f2
 
  0x0fed07905060: f2 f2 00 f4 f4 f4 f2 f2 f2 f2 00 00 00 00 f2 f2
 
  0x0fed07905070: f2 f2 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 
Shadow byte legend (one shadow byte represents 8 application bytes):
 
  Addressable:           00
 
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
 
  Heap right redzone:      fb
 
  Freed heap region:       fd
 
  Stack left redzone:      f1
 
  Stack mid redzone:       f2
 
  Stack right redzone:     f3
 
  Stack partial redzone:   f4
 
  Stack after return:      f5
 
  Stack use after scope:   f8
 
  Global redzone:          f9
 
  Global init order:       f6
 
  Poisoned by user:        f7
 
  Container overflow:      fc
 
  Array cookie:            ac
 
  Intra object redzone:    bb
 
  ASan internal:           fe
 
==25866==ABORTING
 
----------SERVER LOG END-------------



 Comments   
Comment by Varun Gupta (Inactive) [ 2019-02-04 ]

Patch
http://lists.askmonty.org/pipermail/commits/2019-February/013368.html

Comment by Sergei Petrunia [ 2019-02-05 ]

varun, to rule out out subqueries in way that would be obvious for everyone, please construct a testcase that uses a join, not a semi-join.

Comment by Varun Gupta (Inactive) [ 2019-02-06 ]

As requested a test case without subqueries

--source include/have_innodb.inc
 
set join_cache_level=3;
 
set optimizer_use_condition_selectivity=2;
 
 
 
CREATE TABLE t1 (c1 int, c2 int, c3 int, c4 int, c5 int, c6 int, c7 int, c8 int, c9 int, c10 int, c11 int, c12 int, c13 int, c14 int, c15 int, c16 int, c17 int, c18 int, c19 int, c20 int, c21 int, c22 int, c23 int, c24 int, c25 int, c26 int, c27 int, c28 int, c29 int, c30 int, c31 int, c32 int, c33 int, c34 int);
 
 
 
insert into t1 values 
(0, 1, 2, 3, 4, 5, 6, 7, 8, 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),(0, 1, 2, 3, 4, 5, 6, 7, 8, 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);
 
 
 
select * from t1, t1 t where t1.c1 = t.c1 and t1.c2 = t.c2 and t1.c3 = t.c3 and t1.c4 = t.c4 and t1.c5 = t.c5 and t1.c6 = t.c6 and t1.c7 = t.c7 and t1.c8 = t.c8 and t1.c9 = t.c9 and t1.c10 = t.c10 and t1.c11 = t.c11 and t1.c12 = t.c12 and t1.c13 = t.c13 and t1.c14 = t.c14 and t1.c15 = t.c15 and t1.c16 = t.c16 and t1.c17 = t.c17 and t1.c18 = t.c18 and t1.c19 = t.c19 and t1.c20 = t.c20 and t1.c21 = t.c21 and t1.c22 = t.c22 and t1.c23 = t.c23 and t1.c24 = t.c24 and t1.c25 = t.c25 and t1.c26 = t.c26 and t1.c27 = t.c27 and t1.c28 = t.c28 and t1.c29 = t.c29 and t1.c30 = t.c30 and t1.c31 = t.c31 and t1.c32 = t.c32 and t1.c33 = t.c33 and t1.c34 = t.c34;
 
 
 
drop table t1;

Comment by Varun Gupta (Inactive) [ 2019-03-07 ]

New patch
http://lists.askmonty.org/pipermail/commits/2019-March/013507.html

Comment by Elena Stepanova [ 2020-07-15 ]

psergey,

To the issue of problematic stack traces generated under certain circumstances, these test cases (both the original one and Varun's one above) produce particularly bad ones, at least on my non-ASAN debug builds, all of 10.1-10.5:

10.5 debug 30e7a0a8 built with gcc 6.3.0-18+deb9u1, error log

 
Attempting backtrace. You can use the following information to find out
 
where mysqld died. If you see no messages after this, something went
 
terribly wrong...
 
stack_bottom = 0x7f0b1ce08e28 thread_stack 0x49000
 
/data/bld/10.5-debug/bin/mariadbd(my_print_stacktrace+0x40)[0x5573ff874a86]
 
mysys/stacktrace.c:306(my_print_stacktrace)[0x5573fef30a75]
 
??:0(__restore_rt)[0x7f0b258160e0]
 
/data/bld/10.5-debug/bin/mariadbd(+0x95efdb)[0x5573fec3ffdb]
 
 
 
Trying to get some variables.
 
Some pointers may be invalid and cause the dump to abort.
 
Query (0x7f0ae80138d0): select * from t1, t1 t where t1.c1 = t.c1 and t1.c2 = t.c2 and t1.c3 = t.c3 and t1.c4 = t.c4 and t1.c5 = t.c5 and t1.c6 = t.c6 and t1.c7 = t.c7 and t1.c8 = t.c8 and t1.c9 = t.c9 and t1.c10 = t.c10 and t1.c11 = t.c11 and t1.c12 = t.c12 and t1.c13 = t.c13 and t1.c14 = t.c14 and t1.c15 = t.c15 and t1.c16 = t.c16 and t1.c17 = t.c17 and t1.c18 = t.c18 and t1.c19 = t.c19 and t1.c20 = t.c20 and t1.c21 = t.c21 and t1.c22 = t.c22 and t1.c23 = t.c23 and t1.c24 = t.c24 and t1.c25 = t.c25 and t1.c26 = t.c26 and t1.c27 = t.c27 and t1.c28 = t.c28 and t1.c29 = t.c29 and t1.c30 = t.c30 and t1.c31 = t.c31 and t1.c32 = t.c32 and t1.c33 = t.c33 and t1.c34 = t.c34
 
Connection ID (thread ID): 4
 
Status: NOT_KILLED

Same crash, gdb

 
[Current thread is 1 (Thread 0x7f0b1ce09700 (LWP 31306))]
 
(gdb) bt
 
#0  __pthread_kill (threadid=<optimized out>, signo=11) at ../sysdeps/unix/sysv/linux/pthread_kill.c:57
 
#1  0x00005573ff874b78 in my_write_core (sig=11) at /data/src/10.5/mysys/stacktrace.c:518
 
#2  0x00005573fef30dbc in handle_fatal_signal (sig=11) at /data/src/10.5/sql/signal_handler.cc:330
 
#3  <signal handler called>
 
#4  0x00005573fec3ffdb in best_extension_by_limited_search (join=0xf000000000000000, remaining_tables=11745388373829541886, idx=85, record_count=-1.2882375283477099e-231, 
    read_time=131087.88042616847, search_depth=1946140403, prune_level=1610612736, use_cond_selectivity=0) at /data/src/10.5/sql/sql_select.cc:9614
 
#5  0x0000000000000000 in ?? ()
 
(gdb)

Comment by Elena Stepanova [ 2020-07-15 ]

Here is also another test case which causes the same ASAN failure on 10.4+, and a very different but equally ugly stack trace on a non-ASAN debug build.

CREATE TABLE t1 (
 
 f1 tinytext,
 
 f2 mediumint,
 
 f3 int,
 
 f4 tinytext,
 
 f5 date,
 
 f6 char(1),
 
 f7 int,
 
 f8 mediumtext,
 
 f9 mediumtext,
 
 f10 bigint unsigned,
 
 f11 timestamp NULL DEFAULT 0,
 
 f12 datetime,
 
 f13 bit,
 
 f14 varchar(257),
 
 f15 mediumint unsigned,
 
 f16 mediumtext,
 
 f17 float,
 
 f18 longtext,
 
 f19 double unsigned,
 
 f20 float unsigned,
 
 f21 bigint,
 
 f22 longtext,
 
 f23 varchar(257),
 
 f24 tinytext,
 
 f25 longtext,
 
 f26 tinyint,
 
 f27 varchar(10),
 
 f28 char(10),
 
 f29 varchar(1),
 
 f30 bit(64),
 
 f31 text,
 
 f32 double,
 
 f33 smallint,
 
 f34 char(1),
 
 f35 int,
 
 f36 int,
 
 f37 char(10),
 
 f38 varchar(1),
 
 f39 text,
 
 f40 varchar(257),
 
 f41 int,
 
 f42 varchar(1),
 
 f43 int,
 
 f44 varchar(10),
 
 f45 smallint unsigned
 
) ENGINE=MyISAM;
 
 
 
CREATE TABLE t2 (
 
 f1 tinytext,
 
 f2 mediumint,
 
 f3 int,
 
 f4 tinytext,
 
 f5 date,
 
 f6 char(1),
 
 f7 int,
 
 f8 mediumtext,
 
 f9 mediumtext,
 
 f10 bigint unsigned,
 
 f11 timestamp NULL DEFAULT 0,
 
 f12 datetime,
 
 f13 bit,
 
 f14 varchar(257),
 
 f15 mediumint unsigned,
 
 f16 mediumtext,
 
 f17 float,
 
 f18 longtext,
 
 f19 double unsigned,
 
 f20 float unsigned,
 
 f21 bigint,
 
 f22 longtext,
 
 f23 varchar(257),
 
 f24 tinytext,
 
 f25 longtext,
 
 f26 tinyint,
 
 f27 varchar(10),
 
 f28 char(10),
 
 f29 varchar(1),
 
 f30 bit(64),
 
 f31 text,
 
 f32 double,
 
 f33 smallint,
 
 f34 char(1),
 
 f35 int,
 
 f36 int,
 
 f37 char(10),
 
 f38 varchar(1),
 
 f39 text,
 
 f40 varchar(257),
 
 f41 int,
 
 f42 varchar(1),
 
 f43 int,
 
 f44 varchar(10),
 
 f45 smallint unsigned
 
) ENGINE=MyISAM;
 
 
 
INSERT INTO t1 VALUES
 
  (NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL),
 
  (NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL);
 
 
 
INSERT INTO t2 VALUES
 
  (NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL),
 
  (NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL);
 
 
 
SET SESSION JOIN_CACHE_LEVEL= 5;
 
 
 
SELECT t1.* FROM t1 NATURAL JOIN t2 B;

10.4 de208723

 
#5  <signal handler called>
 
#6  0x0000562c0fa3133e in table_cond_selectivity (join=0x7f4fd4015698, idx=1, s=0x0, rem_tables=0) at /data/src/10.4/sql/sql_select.cc:9306
 
#7  0x0001000100010001 in ?? ()
 
#8  0x0001000100010001 in ?? ()
 
#9  0x4000000000000000 in ?? ()
 
#10 0x0000000100000004 in ?? ()
 
#11 0x4003573333333333 in ?? ()
 
#12 0x4000000000000000 in ?? ()
 
#13 0x000000010000003d in ?? ()
 
#14 0x0000000000000002 in ?? ()
 
#15 0x00007f4fd4015698 in ?? ()
 
#16 0x00000000d41b9e98 in ?? ()
 
#17 0x4010000000000000 in ?? ()
 
#18 0x4014f0cccccccccc in ?? ()
 
#19 0x4010000000000000 in ?? ()
 
#20 0x4014f0cccccccccc in ?? ()
 
#21 0xffffffffffffffff in ?? ()
 
#22 0x00007f4fd41bb8f0 in ?? ()
 
#23 0x3ff0000000000000 in ?? ()
 
#24 0x00007f4fd4000af0 in ?? ()
 
#25 0x00007f4fd41bb358 in ?? ()
 
#26 0x0000000000000002 in ?? ()
 
#27 0x00007f4fd41bba50 in ?? ()
 
#28 0x0000000000000000 in ?? ()

Comment by Varun Gupta (Inactive) [ 2020-10-28 ]

Please make sure to test the testcase in MDEV-23937 too (preferably add it to the test suite too)

Comment by Varun Gupta (Inactive) [ 2020-11-03 ]

Patch
http://lists.askmonty.org/pipermail/commits/2020-November/014348.html

Comment by Roel Van de Paar [ 2021-05-17 ]

psergey Is Varun's patch from November good to implement?

Comment by Sergei Petrunia [ 2021-05-20 ]

A more "conservative" fix that touches only table_cond_selectivity(): http://lists.askmonty.org/pipermail/commits/2021-May/014624.html

The fix also fixes MDEV-23937, commit adding the testcase: http://lists.askmonty.org/pipermail/commits/2021-May/014625.html

Generated at Thu Feb 08 08:39:04 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.