Header Delta-Compression for HTTP/2.0
draft-rpeon-httpbis-header-compression-02

Abstract

This document describes a mechanism for compressing streams of groups of key-value pairs, often known as Headers in an HTTP session. See RFC 2616 [RFC2616] or successors for more information about headers.

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at http://datatracker.ietf.org/drafts/current/.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on September 14, 2013.

Copyright Notice

Copyright (c) 2013 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.

Table of Contents

• 1. Overview
• 2. How it works
• 3. Definitions
• 4. Header pre-processing
• 4.1. Mapping the first-line
• 4.2. Mapping HTTP key-values
• 5. Compressor and Decompressor State
• 6. Header Block Wire Format
• 7. String Encoding
• 8. Operations
• 9. Decompressor algorithm
• 10. Compression
• 11. Example
• 11.1. Background
• 11.2. Example Serialization
• 12. Unfinished components
• 13. Security Considerations
• 14. Requirements Notation
• 15. Acknowledgements
• 16. Appendix A
• 17. Appendix B
• 18. Appendix C
• 19. Normative References
• Author's Address

1. Overview

There have been several problems pointed out with the use of the gzip compressor in SPDY [SPDY]. The biggest of these problems is that it is possible for a smart attacker to inject content into the compressor, and then to test hypotheses about the prior contents of the compressor by examining the output size after each such content injection. The other issue is that gzip often consumes more CPU than many would like, especially in situations where one is doing forward or reverse proxying. The compressor proposed here intends to solve the first issue and significantly mitigate the second, while providing compression that is not too much worse than gzip.

2. How it works

The 'delta' compressor works by examining the difference between what it is told to compress and the state that it has stored about what it knows about the past. The previous state is encoded in two separate pieces: An LRU of key-value pairs which the compressor 'saw' in the past (including a static group of key-value pairs which every compressor is assumed to have seen), and a set of references into the LRU which is called a header-group, which the compressor uses to determine what has changed between the current input and the past input.
It then encodes this difference by changing the header-group by adding references to stored key-values, and it removes references to key-values which should no longer be part of the output. If a key-value exists in the to-be-compressed data, but is not present in the LRU, then the LRU is modified by having new data added. When new data is added, a reference to that new data is added to the header-group. The mechanism of adding new data takes two forms: Adding an entire new key-value, or by referring to the key part of a stored key-value, and providing a new value.
When the LRU has reached its size limit, The oldest elements are popped off the end, and, any reference to that element is removed.
All keys are assumed to have been lowercased, and if not, will be.

3. Definitions

user-agent:

The program or device which a human interacts with directly and which typically initiates the transport layer connection or session

client:

Synonym for user-agent

server:

The computer or device which typically accepts a connection, stores, and serves data

proxy:

An entity acting as a server for the client, and a client for the server

header:

A complete set of key-value pairs, either request-headers, or response-headers as defined in RFC2616 [RFC2616] section 5.3 or 6.2, respectively

4. Header pre-processing

4.1. Mapping the first-line

Before the data is input into the compressor (which works only on key-value pairs), the first line of the HTTP message must be made into key-value pairs.

Requests are mapped as follows:
"METHOD PATH VERSION" becomes:

Responses are mapped as follows:
"VERSION STATUS-CODE PHRASE" becomes:

4.2. Mapping HTTP key-values

The rest of the HTTP key-values are simply added to the key-values as mapped from the first-line, with the keys made to be all lowercase, and with cookies split into crumbs by breaking apart the cookie string on semicolons and treating each as if it were a separate header-line.

As an example, the following key-value pairs:

5. Compressor and Decompressor State

The header delta de/compression scheme consists of a state machine which executes opcodes, emits output, and modifies internal, persistent, state. The de/compressor state consists of:

6. Header Block Wire Format

The decompressor is fed a header-block which may span multiple HEADERs frames by the HTTP/2 framing layer, the format of which follows:

7. String Encoding

Strings are huffman encoded [HUFF] using a canonical huffman coding [CANON]. In the future, the opcode byte will be permuted to allow alternate encodings, such as raw text, binary, or perhaps other options.

The huffman code is constructed by taking the frequency-tables in Appendix B, adding 1 to all entries, then generating a canonical huffman coding. If/while this results in a code with a max-length of greater than 32 bits, divide all frequencies by two, capping the minimum frequency at '1', and regenerate until the max code-length is 32 bits or less. The EOF symbol, when decoded, is represented as 256, which allows for any 8-bit value to be encoded and decoded.

8. Operations

For all operations below, the 's' prefix stands for 'State modifying', whereas the 'e' prefix stands for 'Ephemeral', and does not modify state.

The *kvsto family of opcodes encode a new key-value entirely by providing a new string for key and a new string for val.

The *clone family of opcodes encode a backreference to the key part of a pre-existing key-value from either the static-entries or the lru, and a new string value.

The *toggl family of opcodes encode a backreference to an entire key-value from either the static-entries, or the lru.

The *trang family of opcodes is the same as the toggle family, except that it encodes a range of indices instead of a single index

With four families of opcodes, and two variations (ephemeral vs state-changing) per family, we have eight valid opcodes:

9. Decompressor algorithm

The pseudo-code below provides a definition of how the header-block is executed by the decompressor.

10. Compression

The compressor generates a sequence of instructions which the decompressor executes. There are various ways by which the compressor can determine how to construct these operations. Pseudo-code follows showing one approach. group_id is defined by the sender, but must always be less than the maximum allowed number. A reasonable implementation might assign the same group_id to a set of headers which are likely to be similar, for instance those which go to the same hostname or the same hostname suffix.

If the resulting output buffer is larger than the maximum allowed frame size, then the buffer shall be split into maximum-allowed-payload-size or smaller sections, and sent in separate HEADERS frames, with only the last indicating that the frame is finished by asserting the FRAME_FINISHED flag.

11. Example

11.1. Background

Here is a simple example showing an input, the changing part of the compressor state, and an ascii-ified version of what would be serialized on the wire.

The first stage of processing is to break the first line into key-value pairs. The first line becomes:

This gets integrated with the rest of the headers, becoming:

The compressor now goes through each key-value, determining if it is already present in the header-group, in the LRU or static state, and determines what it needs to emit.

11.2. Example Serialization

This is sample output from a program which implements the compression specification above. It prints out the stream ID, then the group ID, then the instructions that the encoder created, then the serialized form of these instructions, followed last by the decompressed output.

12. Unfinished components

These are components that must be added in the future.

13. Security Considerations

The compressor algorithm described here is expected to be immune to the current attacks against encrypted stream-based compressors such as TLS+gzip, but more scrutiny is warranted. The reason that it is believed that the algorithm(s) expressed here is immune is that any backreference to a header key or value always requires a whole-text match, and thus any probe of the compression context confirms no hypothesis unless the attacker has guessed the entire plaintext key and value simultaneously.

14. Requirements Notation

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119].

15. Acknowledgements

16. Appendix A

17. Appendix B

Appendix B huffman code-table for requests

18. Appendix C

Appendix C huffman code-table for responses

19. Normative References

Author's Address