HTTP3: Clang reports heap-use-after-free in ngx_http_v3_insert src/http/v3/ngx_http_v3_table.c:231

[bullerdu@…]

==4234==ERROR: AddressSanitizer: heap-use-after-free on address 0x61e00004a4a0 at pc 0x0000004e9d7f bp 0x7ffedf26fdd0 sp 0x7ffedf26f580
READ of size 6 at 0x61e00004a4a0 thread T0

#0 0x4e9d7e in interceptor_memcpy.part.41 (nginx +0x4e9d7e)
#1 0x82b1af in ngx_http_v3_insert src/http/v3/ngx_http_v3_table.c:231
#2 0x82cd6f in ngx_http_v3_duplicate src/http/v3/ngx_http_v3_table.c:421
#3 0x829a78 in ngx_http_v3_parse_encoder src/http/v3/ngx_http_v3_parse.c:1519
#4 0x829a78 in ngx_http_v3_parse_uni src/http/v3/ngx_http_v3_parse.c:2001
#5 0x82e506 in ngx_http_v3_uni_read_handler src/http/v3/ngx_http_v3_uni.c:225
#6 0x5ed9ae in ngx_event_handler_elapsed src/event/ngx_event.c:1755
#7 0x5ee5b8 in ngx_event_process_posted src/event/ngx_event_posted.c:35
#8 0x5ed302 in ngx_process_events_and_timers src/event/ngx_event.c:422
#9 0x60e8d2 in ngx_worker_process_cycle src/os/unix/ngx_process_cycle.c:841
#10 0x605a8f in ngx_spawn_process src/os/unix/ngx_process.c:200
#11 0x60fbbf in ngx_reap_children src/os/unix/ngx_process_cycle.c:645
#12 0x60fbbf in ngx_master_process_cycle src/os/unix/ngx_process_cycle.c:195
#13 0x5864fc in main src/core/nginx.c:448
#14 0x7fe4638fd444 in libc_start_main (/lib64/libc.so.6+0x22444)
#15 0x4ac228 (nginx +0x4ac228)

freed by thread T0 here:

#0 0x54e7e0 in free (nginx+0x54e7e0)
#1 0x82aded in ngx_http_v3_evict src/http/v3/ngx_http_v3_table.c:381
#2 0x82afec in ngx_http_v3_insert src/http/v3/ngx_http_v3_table.c:210
#3 0x82cd6f in ngx_http_v3_duplicate src/http/v3/ngx_http_v3_table.c:421
#4 0x829a78 in ngx_http_v3_parse_encoder src/http/v3/ngx_http_v3_parse.c:1519
#5 0x829a78 in ngx_http_v3_parse_uni src/http/v3/ngx_http_v3_parse.c:2001
#6 0x82e506 in ngx_http_v3_uni_read_handler src/http/v3/ngx_http_v3_uni.c:225
#7 0x5ed9ae in ngx_event_handler_elapsed src/event/ngx_event.c:1755
#8 0x5ee5b8 in ngx_event_process_posted src/event/ngx_event_posted.c:35
#9 0x5ed302 in ngx_process_events_and_timers src/event/ngx_event.c:422
#10 0x60e8d2 in ngx_worker_process_cycle src/os/unix/ngx_process_cycle.c:841
#11 0x605a8f in ngx_spawn_process src/os/unix/ngx_process.c:200
#12 0x60fbbf in ngx_reap_children src/os/unix/ngx_process_cycle.c:645
#13 0x60fbbf in ngx_master_process_cycle src/os/unix/ngx_process_cycle.c:195
#14 0x5864fc in main src/core/nginx.c:448
#15 0x7fe4638fd444 in libc_start_main (/lib64/libc.so.6+0x22444)

previously allocated by thread T0 here:

#0 0x54eaf8 in malloc (nginx+0x54eaf8)
#1 0x5fc3a3 in ngx_alloc src/os/unix/ngx_alloc.c:22
#2 0x82b12d in ngx_http_v3_insert src/http/v3/ngx_http_v3_table.c:221
#3 0x82c91a in ngx_http_v3_ref_insert src/http/v3/ngx_http_v3_table.c:195
#4 0x829f52 in ngx_http_v3_parse_field_inr src/http/v3/ngx_http_v3_parse.c:1624
#5 0x829f52 in ngx_http_v3_parse_encoder src/http/v3/ngx_http_v3_parse.c:1479
#6 0x829f52 in ngx_http_v3_parse_uni src/http/v3/ngx_http_v3_parse.c:2001
#7 0x82e506 in ngx_http_v3_uni_read_handler src/http/v3/ngx_http_v3_uni.c:225
#8 0x5ed9ae in ngx_event_handler_elapsed src/event/ngx_event.c:1755
#9 0x5ee5b8 in ngx_event_process_posted src/event/ngx_event_posted.c:35
#10 0x5ed302 in ngx_process_events_and_timers src/event/ngx_event.c:422
#11 0x60e8d2 in ngx_worker_process_cycle src/os/unix/ngx_process_cycle.c:841
#12 0x605a8f in ngx_spawn_process src/os/unix/ngx_process.c:200
#13 0x60fbbf in ngx_reap_children src/os/unix/ngx_process_cycle.c:645
#14 0x60fbbf in ngx_master_process_cycle src/os/unix/ngx_process_cycle.c:195
#15 0x5864fc in main src/core/nginx.c:448
#16 0x7fe4638fd444 in libc_start_main (/lib64/libc.so.6+0x22444)

SUMMARY: AddressSanitizer: heap-use-after-free (nginx+0x4e9d7e) in interceptor_memcpy.part.41
Shadow bytes around the buggy address:

0x0c3c80001440: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
0x0c3c80001450: fd fd fd fd fd fd fd fd fd fa fa fa fa fa fa fa
0x0c3c80001460: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c3c80001470: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c3c80001480: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa

=>0x0c3c80001490: fd fd fd fd[fd]fd fd fd fd fd fd fd fd fd fd fd

0x0c3c800014a0: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
0x0c3c800014b0: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
0x0c3c800014c0: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
0x0c3c800014d0: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
0x0c3c800014e0: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd

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
Left alloca redzone: ca
Right alloca redzone: cb

==4234==ABORTING

[Sergey Kandaurov]

Looks like this is a result of processing insert instructions referencing a dynamic table entry, which needs to be evicted to free up some space in the table.
I didn't find any hints that such instruction is valid and if it should be processed "insert then evict", rather the opposite, so tend to think this should go the error path.

Please try this patch:

# HG changeset patch
# User Sergey Kandaurov <pluknet@nginx.com>
# Date 1672413167 -14400
#      Fri Dec 30 19:12:47 2022 +0400
# Branch quic
# Node ID 83b529aa74a81cbed57953cbdbb06c32b20bc434
# Parent  77131b5f43f7cddae9430cf5ff052fc4c484f486
HTTP/3: handled insertion reference to a going to be evicted entry.

As per RFC 9204, section 3.2.2, before a new entry is added to the dynamic
table, entries are evicted as needed.  Additionally, per section 2.2.3, if
the decoder encounters a reference in an encoder instruction to a dynamic
table entry that has already been evicted, this is a connection error of
type QPACK_ENCODER_STREAM_ERROR.

This change adds such checks for encoder instructions, such as Insert with
Name Reference and Duplicate, that they don't have a stale reference as a
result of eviction, as it would end up in a subsequent use-after-free when
accessing now freed entry fields with a dangling pointer (ticket #2431).

diff --git a/src/http/v3/ngx_http_v3_table.c b/src/http/v3/ngx_http_v3_table.c
--- a/src/http/v3/ngx_http_v3_table.c
+++ b/src/http/v3/ngx_http_v3_table.c
@@ -159,6 +159,7 @@ ngx_int_t
 ngx_http_v3_ref_insert(ngx_connection_t *c, ngx_uint_t dynamic,
     ngx_uint_t index, ngx_str_t *value)
 {
+    size_t                        size;
     ngx_str_t                     name;
     ngx_http_v3_session_t        *h3c;
     ngx_http_v3_dynamic_table_t  *dt;
@@ -180,6 +181,16 @@ ngx_http_v3_ref_insert(ngx_connection_t 
             return NGX_HTTP_V3_ERR_ENCODER_STREAM_ERROR;
         }
 
+        size = ngx_http_v3_table_entry_size(&name, value);
+
+        if (ngx_http_v3_evict(c, size) != NGX_OK) {
+            return NGX_HTTP_V3_ERR_ENCODER_STREAM_ERROR;
+        }
+
+        if (ngx_http_v3_lookup(c, index, NULL, NULL) != NGX_OK) {
+            return NGX_HTTP_V3_ERR_ENCODER_STREAM_ERROR;
+        }
+
     } else {
         ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, 0,
                        "http3 ref insert static[%ui] \"%V\"", index, value);
@@ -390,6 +401,7 @@ ngx_http_v3_evict(ngx_connection_t *c, s
 ngx_int_t
 ngx_http_v3_duplicate(ngx_connection_t *c, ngx_uint_t index)
 {
+    size_t                        size;
     ngx_str_t                     name, value;
     ngx_http_v3_session_t        *h3c;
     ngx_http_v3_dynamic_table_t  *dt;
@@ -409,6 +421,16 @@ ngx_http_v3_duplicate(ngx_connection_t *
         return NGX_HTTP_V3_ERR_ENCODER_STREAM_ERROR;
     }
 
+    size = ngx_http_v3_table_entry_size(&name, &value);
+
+    if (ngx_http_v3_evict(c, size) != NGX_OK) {
+        return NGX_HTTP_V3_ERR_ENCODER_STREAM_ERROR;
+    }
+
+    if (ngx_http_v3_lookup(c, index, NULL, NULL) != NGX_OK) {
+        return NGX_HTTP_V3_ERR_ENCODER_STREAM_ERROR;
+    }
+
     return ngx_http_v3_insert(c, &name, &value);
 }
 

[Sergey Kandaurov]

For the record, tests to reproduce both issues (to apply against ​nginx-tests-quic repo):

diff --git a/h3_headers.t b/h3_headers.t
--- a/h3_headers.t
+++ b/h3_headers.t
@@ -24,7 +24,7 @@ select STDERR; $| = 1;
 select STDOUT; $| = 1;
 
 my $t = Test::Nginx->new()->has(qw/http http_v3 proxy rewrite/)
-	->has_daemon('openssl')->plan(66)
+	->has_daemon('openssl')->plan(68)
 	->write_file_expand('nginx.conf', <<'EOF');
 
 %%TEST_GLOBALS%%
@@ -448,6 +448,24 @@ is($frame->{'val'}, $sid, 'capacity evic
 ($frame) = grep { $_->{type} eq "CONNECTION_CLOSE" } @$frames;
 is($frame->{'phrase'}, 'stream error', 'capacity invalid');
 
+# insert with dynamic reference, table space only for index 0
+
+$s = Test::Nginx::HTTP3->new(undef, capacity => 64);
+$s->insert_literal('x-foo', 'X-Bar');
+$s->insert_reference('x-foo', 'X-Bar', dyn => 1);
+$frames = $s->read(all => [{ type => 'CONNECTION_CLOSE' }]);
+
+($frame) = grep { $_->{type} eq "CONNECTION_CLOSE" } @$frames;
+is($frame->{'error'}, 0x0201, 'insert ref evicted - encoder error');
+
+$s = Test::Nginx::HTTP3->new(undef, capacity => 64);
+$s->insert_literal('x-foo', 'X-Bar');
+$s->duplicate('x-foo');
+$frames = $s->read(all => [{ type => 'CONNECTION_CLOSE' }]);
+
+($frame) = grep { $_->{type} eq "CONNECTION_CLOSE" } @$frames;
+is($frame->{'error'}, 0x0201, 'duplicate evicted - encoder error');
+
 # request header field with multiple values
 
 # 8.1.2.5.  Compressing the Cookie Header Field
diff --git a/lib/Test/Nginx/HTTP3.pm b/lib/Test/Nginx/HTTP3.pm
--- a/lib/Test/Nginx/HTTP3.pm
+++ b/lib/Test/Nginx/HTTP3.pm
@@ -284,6 +289,27 @@ sub insert_literal {
 		. build_int($offset) . build_int($length) . $buf);
 }
 
+# 4.3.4.  Duplicate
+
+sub duplicate {
+	my ($self, $name, $value, %extra) = @_;
+	my $table = $self->{dynamic_encode};
+	my $index = 0;
+
+	++$index until $index > $#$table
+		or $table->[$index][0] eq $name;
+	splice @$table, 0, 0, [ $name, $value ];
+
+	my $buf = pack('B*', '000' . ipack(5, $index));
+
+	my $offset = $self->{encoder_offset};
+	my $length = length($buf);
+
+	$self->{encoder_offset} += $length;
+	$self->raw_write("\x0e\x02"
+		. build_int($offset) . build_int($length) . $buf);
+}
+
 sub new_stream {
 	my ($self, $uri, $stream) = @_;
 	my ($input, $buf);
@@ -1231,11 +1257,16 @@ sub parse_frames {
 			$frame->{token} = substr($buf, $offset, 16);
 			$offset += 16;
 		}
-		if ($type == 29) {
+		if ($type == 28 || $type == 29) {
 			$frame->{type} = 'CONNECTION_CLOSE';
 			my ($len, $val) = parse_int(substr($buf, $offset));
 			$frame->{error} = $val;
 			$offset += $len;
+			if ($type == 28) {
+				($len, $val) = parse_int(substr($buf, $offset));
+				$frame->{frame_type} = $val;
+				$offset += $len;
+			}
 			($len, $val) = parse_int(substr($buf, $offset));
 			$offset += $len;
 			$frame->{phrase} = substr($buf, $offset, $val);

[bullerdu@…]

Replying to Sergey Kandaurov:

Looks like this is a result of processing insert instructions referencing a dynamic table entry, which needs to be evicted to free up some space in the table.
I didn't find any hints that such instruction is valid and if it should be processed "insert then evict", rather the opposite, so tend to think this should go the error path.

Please try this patch:

# HG changeset patch
# User Sergey Kandaurov <pluknet@nginx.com>
# Date 1672413167 -14400
#      Fri Dec 30 19:12:47 2022 +0400
# Branch quic
# Node ID 83b529aa74a81cbed57953cbdbb06c32b20bc434
# Parent  77131b5f43f7cddae9430cf5ff052fc4c484f486
HTTP/3: handled insertion reference to a going to be evicted entry.

As per RFC 9204, section 3.2.2, before a new entry is added to the dynamic
table, entries are evicted as needed.  Additionally, per section 2.2.3, if
the decoder encounters a reference in an encoder instruction to a dynamic
table entry that has already been evicted, this is a connection error of
type QPACK_ENCODER_STREAM_ERROR.

This change adds such checks for encoder instructions, such as Insert with
Name Reference and Duplicate, that they don't have a stale reference as a
result of eviction, as it would end up in a subsequent use-after-free when
accessing now freed entry fields with a dangling pointer (ticket #2431).

diff --git a/src/http/v3/ngx_http_v3_table.c b/src/http/v3/ngx_http_v3_table.c
--- a/src/http/v3/ngx_http_v3_table.c
+++ b/src/http/v3/ngx_http_v3_table.c
@@ -159,6 +159,7 @@ ngx_int_t
 ngx_http_v3_ref_insert(ngx_connection_t *c, ngx_uint_t dynamic,
     ngx_uint_t index, ngx_str_t *value)
 {
+    size_t                        size;
     ngx_str_t                     name;
     ngx_http_v3_session_t        *h3c;
     ngx_http_v3_dynamic_table_t  *dt;
@@ -180,6 +181,16 @@ ngx_http_v3_ref_insert(ngx_connection_t 
             return NGX_HTTP_V3_ERR_ENCODER_STREAM_ERROR;
         }
 
+        size = ngx_http_v3_table_entry_size(&name, value);
+
+        if (ngx_http_v3_evict(c, size) != NGX_OK) {
+            return NGX_HTTP_V3_ERR_ENCODER_STREAM_ERROR;
+        }
+
+        if (ngx_http_v3_lookup(c, index, NULL, NULL) != NGX_OK) {
+            return NGX_HTTP_V3_ERR_ENCODER_STREAM_ERROR;
+        }
+
     } else {
         ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, 0,
                        "http3 ref insert static[%ui] \"%V\"", index, value);
@@ -390,6 +401,7 @@ ngx_http_v3_evict(ngx_connection_t *c, s
 ngx_int_t
 ngx_http_v3_duplicate(ngx_connection_t *c, ngx_uint_t index)
 {
+    size_t                        size;
     ngx_str_t                     name, value;
     ngx_http_v3_session_t        *h3c;
     ngx_http_v3_dynamic_table_t  *dt;
@@ -409,6 +421,16 @@ ngx_http_v3_duplicate(ngx_connection_t *
         return NGX_HTTP_V3_ERR_ENCODER_STREAM_ERROR;
     }
 
+    size = ngx_http_v3_table_entry_size(&name, &value);
+
+    if (ngx_http_v3_evict(c, size) != NGX_OK) {
+        return NGX_HTTP_V3_ERR_ENCODER_STREAM_ERROR;
+    }
+
+    if (ngx_http_v3_lookup(c, index, NULL, NULL) != NGX_OK) {
+        return NGX_HTTP_V3_ERR_ENCODER_STREAM_ERROR;
+    }
+
     return ngx_http_v3_insert(c, &name, &value);
 }
 

ok, i get it. thanks for your patch. i will try it.

[Roman Arutyunyan]

Here's another patch which follows RFC 9204 more strictly. A new entry is allowed to reference the entry being evicted. Tests have been committed to ​http://hg.nginx.org/nginx-tests-quic/.

# HG changeset patch
# User Roman Arutyunyan <arut@nginx.com>
# Date 1672748685 -14400
#      Tue Jan 03 16:24:45 2023 +0400
# Branch quic
# Node ID c2e88661f44ff14631dc546eda2aa5bf41cc585f
# Parent  f29b1f282c29618738bc23d22de84acc1c743e93
HTTP/3: handled insertion reference to a going to be evicted entry.

As per RFC 9204, section 3.2.2, a new entry can reference an entry in the
dynamic table that will be evicted when adding this new entry into the dynamic
table.

Previously, such inserts resulted in use-after-free since the old entry was
evicted before the insertion (ticket #2431).  Now it's evicted after the
insertion.

This change fixes Insert with Name Reference and Duplicate encoder instructions.

diff --git a/src/http/v3/ngx_http_v3_table.c b/src/http/v3/ngx_http_v3_table.c
--- a/src/http/v3/ngx_http_v3_table.c
+++ b/src/http/v3/ngx_http_v3_table.c
@@ -13,7 +13,7 @@
 #define ngx_http_v3_table_entry_size(n, v) ((n)->len + (v)->len + 32)
 
 
-static ngx_int_t ngx_http_v3_evict(ngx_connection_t *c, size_t need);
+static ngx_int_t ngx_http_v3_evict(ngx_connection_t *c, size_t target);
 static void ngx_http_v3_unblock(void *data);
 static ngx_int_t ngx_http_v3_new_entry(ngx_connection_t *c);
 
@@ -204,13 +204,15 @@ ngx_http_v3_insert(ngx_connection_t *c, 
 
     size = ngx_http_v3_table_entry_size(name, value);
 
-    if (ngx_http_v3_evict(c, size) != NGX_OK) {
+    h3c = ngx_http_v3_get_session(c);
+    dt = &h3c->table;
+
+    if (size > dt->capacity) {
+        ngx_log_error(NGX_LOG_ERR, c->log, 0,
+                      "not enough dynamic table capacity");
         return NGX_HTTP_V3_ERR_ENCODER_STREAM_ERROR;
     }
 
-    h3c = ngx_http_v3_get_session(c);
-    dt = &h3c->table;
-
     ngx_log_debug4(NGX_LOG_DEBUG_HTTP, c->log, 0,
                    "http3 insert [%ui] \"%V\":\"%V\", size:%uz",
                    dt->base + dt->nelts, name, value, size);
@@ -234,6 +236,10 @@ ngx_http_v3_insert(ngx_connection_t *c, 
 
     dt->insert_count++;
 
+    if (ngx_http_v3_evict(c, dt->capacity) != NGX_OK) {
+        return NGX_ERROR;
+    }
+
     ngx_post_event(&dt->send_insert_count, &ngx_posted_events);
 
     if (ngx_http_v3_new_entry(c) != NGX_OK) {
@@ -293,14 +299,11 @@ ngx_http_v3_set_capacity(ngx_connection_
         return NGX_HTTP_V3_ERR_ENCODER_STREAM_ERROR;
     }
 
-    dt = &h3c->table;
-
-    if (dt->size > capacity) {
-        if (ngx_http_v3_evict(c, dt->size - capacity) != NGX_OK) {
-            return NGX_HTTP_V3_ERR_ENCODER_STREAM_ERROR;
-        }
+    if (ngx_http_v3_evict(c, capacity) != NGX_OK) {
+        return NGX_HTTP_V3_ERR_ENCODER_STREAM_ERROR;
     }
 
+    dt = &h3c->table;
     max = capacity / 32;
     prev_max = dt->capacity / 32;
 
@@ -345,9 +348,9 @@ ngx_http_v3_cleanup_table(ngx_http_v3_se
 
 
 static ngx_int_t
-ngx_http_v3_evict(ngx_connection_t *c, size_t need)
+ngx_http_v3_evict(ngx_connection_t *c, size_t target)
 {
-    size_t                        size, target;
+    size_t                        size;
     ngx_uint_t                    n;
     ngx_http_v3_field_t          *field;
     ngx_http_v3_session_t        *h3c;
@@ -355,14 +358,6 @@ ngx_http_v3_evict(ngx_connection_t *c, s
 
     h3c = ngx_http_v3_get_session(c);
     dt = &h3c->table;
-
-    if (need > dt->capacity) {
-        ngx_log_error(NGX_LOG_ERR, c->log, 0,
-                      "not enough dynamic table capacity");
-        return NGX_ERROR;
-    }
-
-    target = dt->capacity - need;
     n = 0;
 
     while (dt->size > target) {

[Roman Arutyunyan]

Committed: ​http://hg.nginx.org/nginx-quic/rev/987bee4363d1.

[Roman Arutyunyan <arut@…>]

In 9062:987bee4363d1/nginx:

HTTP/3: handled insertion reference to a going to be evicted entry.

As per RFC 9204, section 3.2.2, a new entry can reference an entry in the
dynamic table that will be evicted when adding this new entry into the dynamic
table.

Previously, such inserts resulted in use-after-free since the old entry was
evicted before the insertion (ticket #2431). Now it's evicted after the
insertion.

This change fixes Insert with Name Reference and Duplicate encoder instructions.