Re: Proposal: drop QPACK encoder stream framing

Kazuho Oku <kazuhooku@gmail.com> Sat, 09 June 2018 22:56 UTC

Return-Path: <kazuhooku@gmail.com>
X-Original-To: quic@ietfa.amsl.com
Delivered-To: quic@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 0114A130FB8 for <quic@ietfa.amsl.com>; Sat, 9 Jun 2018 15:56:57 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.099
X-Spam-Level:
X-Spam-Status: No, score=-0.099 tagged_above=-999 required=5 tests=[DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id nXYMO50CBAWH for <quic@ietfa.amsl.com>; Sat, 9 Jun 2018 15:56:55 -0700 (PDT)
Received: from mail-pf0-x232.google.com (mail-pf0-x232.google.com [IPv6:2607:f8b0:400e:c00::232]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C835C130F24 for <quic@ietf.org>; Sat, 9 Jun 2018 15:56:55 -0700 (PDT)
Received: by mail-pf0-x232.google.com with SMTP id b74-v6so8348840pfl.5 for <quic@ietf.org>; Sat, 09 Jun 2018 15:56:55 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=i0LIx8BaWs2rBLtjD1kp71rwdo/EcoIO+ACW4TPsYqQ=; b=P0HNC8SHn2Y5uyYi0/6JcwJ1NbOdR6DSE0trgrNcDumwFuowXCxZ/nrp6ZWGSndpWQ KMQyzAd3oVTVLYR06PHUv4adLMlApL73wV0iee6/jOSwJE/05/RAaAxUzjD/1mEgKrEN tRB2h1HhovWLIHR1+aUapmhCfZq6i7+9RkZj7hajdqPxn9Fr9RIudl5i7T4HFPBF7hQH VMgIwxHgSPLxJLT8t+R7O4eWSvZhv1OZV43rZSbz3CXzOiVq7TdZT1nrYf+ZNACweqig j7KkE0F72jfixqlZIOCsQDANN+R9Ad0mY7vrMddRPydThPbsGBwvB2ieDlRg0rZhW1Lm wirQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=i0LIx8BaWs2rBLtjD1kp71rwdo/EcoIO+ACW4TPsYqQ=; b=WCi8mEbytgBFiKdF+GdGRlq9nVse9C1PnFH1P2R1tw/QgtKzfNa2wkXWaJ2HOMF7wI GDr9yllj+ew7us9bDT63kJvIb6znm6EiAM2C+Sj9iEWXeoYOGuJ4Ie0c/lyUOdsA+7sQ L3l45iqpcWTJZW2iXYrrcTTS/YAYG2kpZzD9VjDgjbI40LLyrbB5GHuN8MKsC0+qRmzo acnhvu3yIh9jjv6QytSPadDJo8AkKSIwit0RmjCo4pl4YKBeI8dXuvzZWXZ4FZ7p+l/O +NENp2IHUUCTM5y1yWluSOQmaZz8DgJW8iQqwPK2jX+x6ZZ34XR2DOfU7KsUlLff2D7V gKcw==
X-Gm-Message-State: APt69E1C/VGs3S4Onm/k7m+zKdmWNYlsrT0QKSAFbtxsdjNoCwD8nlCx eftUi05+2hSlx8ziVK0ey7MFQtPDjqOkq9wHUu8=
X-Google-Smtp-Source: ADUXVKLtH29y4tkfcXv8t0H7XQccEPhcWKTq7E94C5E5lkh1nsJ3hXppYXP2BT+pAA3ATXqTK9LiR0+xDKGVuUz2NRY=
X-Received: by 2002:a63:ba02:: with SMTP id k2-v6mr9936630pgf.179.1528585015247; Sat, 09 Jun 2018 15:56:55 -0700 (PDT)
MIME-Version: 1.0
Received: by 2002:a17:90a:1181:0:0:0:0 with HTTP; Sat, 9 Jun 2018 15:56:54 -0700 (PDT)
In-Reply-To: <8616263A-31EF-4803-BEEF-1FE3FAEB23DB@fb.com>
References: <20180607151112.GA28823@ubuntu-dmitri> <CABkgnnXbfkVbq6vCvud100h6wr3+9ir3iO7dD6-qaykOmK3JBQ@mail.gmail.com> <CANatvzzzXF8WCXgDCahTa_7JWZ1c1i-9rU_c8c9QWk5_O5u4Ow@mail.gmail.com> <F04D1BA6-8EC6-43EB-ABEC-34C4B30352AB@fb.com> <CANatvzwr6fSER-tq+xLz_e9rOw+mj5RpdS5eb679Ds_3m=PnoA@mail.gmail.com> <8616263A-31EF-4803-BEEF-1FE3FAEB23DB@fb.com>
From: Kazuho Oku <kazuhooku@gmail.com>
Date: Sun, 10 Jun 2018 01:56:54 +0300
Message-ID: <CANatvzyHXnDCKPfpgf7-gZzDODRJ85Xz-diZ3ioBB-O=F2fvpg@mail.gmail.com>
Subject: Re: Proposal: drop QPACK encoder stream framing
To: Alan Frindell <afrind@fb.com>
Cc: Martin Thomson <martin.thomson@gmail.com>, QUIC WG <quic@ietf.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/c2OkrZVeDfEhmRKpvW7EXzI3YOQ>
X-BeenThere: quic@ietf.org
X-Mailman-Version: 2.1.26
Precedence: list
List-Id: Main mailing list of the IETF QUIC working group <quic.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/quic>, <mailto:quic-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/quic/>
List-Post: <mailto:quic@ietf.org>
List-Help: <mailto:quic-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/quic>, <mailto:quic-request@ietf.org?subject=subscribe>
X-List-Received-Date: Sat, 09 Jun 2018 22:56:57 -0000

2018-06-09 8:26 GMT+09:00 Alan Frindell <afrind@fb.com>om>:
>     Because I think reparsing is the best strategy here, let me argue that
>     the worst case is not O(N^2).
>
>     Of course, in theory it is O(N^2), because there is no upper bound for
>     the integer representation. But the reality is that implementations
>     are required to have an upper bound. I'd assume that they would
>     typically only permit values that fit in a 32-bit (u)int (16-bit is
>     another option for some).
>
> The O(N^2) work I was thinking of was something like this:
>
> The encoder sends a very long Huffman encoded header name followed by a long value, but they send the value one byte at a time.  If the decoder naively reparses the entire Insert instruction every time a byte arrives, it will end up Huffman decoding the header name on every new byte of the value.  The name can be skipped over to re-parse the value length, and verify if the full value is present.  However, even skipping over it may be a linear operation in a zero-copy implementation that maintains a linked list of data buffers.

Thank you for the clarification. That sounds like an interesting
attack vector that we need to be aware of.

OTOH, I am not sure if we need to consider the possibility of
streaming Huffman decoding in this discussion, considering the fact
that the compressed strings remain length-prefixed.

Even if we remove the framing of the QCACK instructions,
implementations will continue to have the freedom to buffer a complete
Huffman-encoded string (the length of the string being identified by
the length octets.

> -Alan
>
>



-- 
Kazuho Oku