Out-Of-Bound (OOB) Read Memory Issue in hll.c

[gaoxiangliu]

Overview

While fuzzing hll using AFL++ and AddressSanitizer, I discovered that there is an Out-Of-Bound (OOB) reading memory issue in hll.c. This may lead to data leakage.

Environment

OS: Ubuntu 22.04.5 LTS (x64)
PostgreSQL: 18.0 (./configure --enable-cassert --enable-debug CFLAGS="-fsanitize=address -fno-omit-frame-pointer -g -O1 -fsanitize-recover=address" LDFLAGS="-fsanitize=address" CC=gcc-11 CXX=g++-11), also replicable when compiled with GCC 13.3.0
Extension hll: 0bdacc2 (the new commits didn't change the hll.c file)
Extension compilation: CC=afl-clang-fast COPT=-g -O2 -fgnu89-inline -fgnu89-inline -fsanitize=address -fno-omit-frame-pointer (also replicable when compiled with GCC 13.3.0)
AFL++ version: https://github.com/aflplusplus/aflplusplus bf2eac470804df48a1bca6a78d4dd6c71968a556
PostgreSQL setup:

• compile, install
• initdb -D xxx
• install the extension
• createdb test
• create extension hll (on the test database)
• fuzzing started, feed sqls
  • e.g., SELECT public.hll_union_agg(public.hll_in('',(select oid from pg_proc order by random() limit 1),-1656396078));
  • ...

Affected Code

src/hll.c#1394

1387 static uint8_t
1388 multiset_unpack(multiset_t * o_msp,
1389                 uint8_t const * i_bitp,
1390                 size_t i_size,
1391                 uint8_t * o_encoded_type)
1392 {
1393     // First byte is the version and type header.
1394     uint8_t vers = (i_bitp[0] >> 4) & 0xf;

Possible SQLs that Trigger the Problem

SELECT public.hll_send(public.hll_in('',(select oid from pg_type order by random() limit 1),-2009041878));
SELECT public.hll_regwidth(public.hll_in('',(select oid from pg_amop order by random() limit 1),-407359608));
SELECT public.hll_send(public.hll_in('',(select oid from pg_type order by random() limit 1),-868791912));
SELECT public.hll_union_agg(public.hll_in('',(select oid from pg_am order by random() limit 1),-525017700));
SELECT public.hll_add(public.hll_in('',(select oid from pg_language order by random() limit 1),-624541417),public.hll_hash_text('}s<%>',432407345));
SELECT public.hll_add_rev(public.hll_hashval_in('<a',(select oid from pg_enum order by random() limit 1),1037293195),public.hll_in('',(select oid from pg_type order by random() limit 1),660602891));
SELECT public.hll(public.hll_in('',(select oid from pg_amop order by random() limit 1),-2069428250),964348759,FALSE);
SELECT public.hll_sparseon(public.hll_in('',(select oid from pg_proc order by random() limit 1),962282249));
SELECT public.hll_ne(public.hll_in('',(select oid from pg_proc order by random() limit 1),-899950542),public.hll_in('1EC_RQs',(select oid from pg_trigger order by random() limit 1),-1854566849));
SELECT public.hll_in('',(select oid from pg_constraint order by random() limit 1),-1001292285);

When the first argument of hll_in is is an empty string.

Suggested Fix

Add length check to the i_bitp array.

ASan trace

=================================================================
==999995==ERROR: AddressSanitizer: use-after-poison on address 0x52500005ca04 at pc 0x76b7ef80f49b bp 0x7ffeb34d4480 sp 0x7ffeb34d4470
READ of size 1 at 0x52500005ca04 thread T0
    #0 0x76b7ef80f49a in multiset_unpack /hll/repo/original_prep/src/hll.c:1228
    #1 0x76b7ef80d7bc in hll_in /hll/repo/original_prep/src/hll.c:1680
    #2 0x61cfb3e20127 in ExecInterpExpr /postgresql/src/backend/executor/execExprInterp.c:953
    #3 0x61cfb3e0c137 in ExecInterpExprStillValid /postgresql/src/backend/executor/execExprInterp.c:2299
    #4 0x61cfb3e7fe4f in ExecEvalExprNoReturn ../../../src/include/executor/executor.h:419
    #5 0x61cfb3e7fe4f in ExecEvalExprNoReturnSwitchContext ../../../src/include/executor/executor.h:460
    #6 0x61cfb3e7fe4f in advance_aggregates /postgresql/src/backend/executor/nodeAgg.c:820
    #7 0x61cfb3e86d0d in agg_retrieve_direct /postgresql/src/backend/executor/nodeAgg.c:2540
    #8 0x61cfb3e86d0d in ExecAgg /postgresql/src/backend/executor/nodeAgg.c:2265
    #9 0x61cfb3e4f6d7 in ExecProcNodeFirst /postgresql/src/backend/executor/execProcnode.c:469
    #10 0x61cfb3e3245f in ExecProcNode ../../../src/include/executor/executor.h:315
    #11 0x61cfb3e3245f in ExecutePlan /postgresql/src/backend/executor/execMain.c:1697
    #12 0x61cfb3e3245f in standard_ExecutorRun /postgresql/src/backend/executor/execMain.c:366
    #13 0x61cfb3e327a7 in ExecutorRun /postgresql/src/backend/executor/execMain.c:303
    #14 0x61cfb4469a79 in PortalRunSelect /postgresql/src/backend/tcop/pquery.c:921
    #15 0x61cfb446e1f2 in PortalRun /postgresql/src/backend/tcop/pquery.c:765
    #16 0x61cfb4462bab in exec_simple_query /postgresql/src/backend/tcop/postgres.c:1273
    #17 0x61cfb4464a89 in PostgresMain /postgresql/src/backend/tcop/postgres.c:4766
    #18 0x61cfb4458209 in BackendMain /postgresql/src/backend/tcop/backend_startup.c:124
    #19 0x61cfb42405cd in postmaster_child_launch /postgresql/src/backend/postmaster/launch_backend.c:290
    #20 0x61cfb424909b in BackendStartup /postgresql/src/backend/postmaster/postmaster.c:3587
    #21 0x61cfb424909b in ServerLoop /postgresql/src/backend/postmaster/postmaster.c:1702
    #22 0x61cfb424c159 in PostmasterMain /postgresql/src/backend/postmaster/postmaster.c:1400
    #23 0x61cfb3f7305b in main /postgresql/src/backend/main/main.c:227
    #24 0x76b80ce29d8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #25 0x76b80ce29e3f in __libc_start_main_impl ../csu/libc-start.c:392
    #26 0x61cfb37dcba4 in _start (/pg/server/180_asan/pg180/bin/postgres+0x41eba4)

0x52500005ca04 is located 260 bytes inside of 8192-byte region [0x52500005c900,0x52500005e900)
allocated by thread T0 here:
    #0 0x76b80dab4887 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:145
    #1 0x61cfb489a173 in AllocSetContextCreateInternal /postgresql/src/backend/utils/mmgr/aset.c:444
    #2 0x61cfb3e67adb in CreateExprContextInternal /postgresql/src/backend/executor/execUtils.c:259
    #3 0x61cfb3e68e1e in CreateExprContext /postgresql/src/backend/executor/execUtils.c:309
    #4 0x61cfb3e695b8 in ExecAssignExprContext /postgresql/src/backend/executor/execUtils.c:487
    #5 0x61cfb3effe94 in ExecInitResult /postgresql/src/backend/executor/nodeResult.c:204
    #6 0x61cfb3e4fa0d in ExecInitNode /postgresql/src/backend/executor/execProcnode.c:167
    #7 0x61cfb3e351c9 in InitPlan /postgresql/src/backend/executor/execMain.c:987
    #8 0x61cfb3e351c9 in standard_ExecutorStart /postgresql/src/backend/executor/execMain.c:261
    #9 0x61cfb3e354b9 in ExecutorStart /postgresql/src/backend/executor/execMain.c:137
    #10 0x61cfb446c20d in PortalStart /postgresql/src/backend/tcop/pquery.c:518
    #11 0x61cfb4462aba in exec_simple_query /postgresql/src/backend/tcop/postgres.c:1234
    #12 0x61cfb4464a89 in PostgresMain /postgresql/src/backend/tcop/postgres.c:4766
    #13 0x61cfb4458209 in BackendMain /postgresql/src/backend/tcop/backend_startup.c:124
    #14 0x61cfb42405cd in postmaster_child_launch /postgresql/src/backend/postmaster/launch_backend.c:290
    #15 0x61cfb424909b in BackendStartup /postgresql/src/backend/postmaster/postmaster.c:3587
    #16 0x61cfb424909b in ServerLoop /postgresql/src/backend/postmaster/postmaster.c:1702
    #17 0x61cfb424c159 in PostmasterMain /postgresql/src/backend/postmaster/postmaster.c:1400
    #18 0x61cfb3f7305b in main /postgresql/src/backend/main/main.c:227
    #19 0x76b80ce29d8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58

SUMMARY: AddressSanitizer: use-after-poison /hll/repo/original_prep/src/hll.c:1228 in multiset_unpack
Shadow bytes around the buggy address:
  0x0a4a800038f0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0a4a80003900: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0a4a80003910: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0a4a80003920: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0a4a80003930: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 f7 f7
=>0x0a4a80003940:[04]f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7
  0x0a4a80003950: f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7
  0x0a4a80003960: f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7
  0x0a4a80003970: f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7
  0x0a4a80003980: f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7
  0x0a4a80003990: f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7 f7
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
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  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
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc

Expanded C source file

A preprocessed and macro-expanded version of the code can be found https://github.com/gaoxiangliu/fuzzing-dbms-extensions-logs/blob/main/postgresql/hll/0bdaccpg18/hll.c