Hpack 閱讀筆記
抽象
該規(guī)范定義了HPACK，HPACK的壓縮格式 有效地表示要在HTTP / 2中使用的HTTP標頭字段。
解決問題
該規(guī)范定義了HPACK，這是一種新型壓縮機，它消除了冗余標頭字段，將漏洞限制為已知安全性攻擊，并且在受限條件下使用時具有有限的內(nèi)存要求環(huán)境。
關(guān)鍵術(shù)語
標頭字段：名稱/值對。名稱和值都是視為八位字節(jié)的不透明序列。 動態(tài)表：動態(tài)表是一個表，將存儲的標頭字段與索引值相關(guān)聯(lián)。這個桌子是動態(tài)且特定于編碼或解碼上下文。 靜態(tài)表：靜態(tài)表是一個表，靜態(tài)地將經(jīng)常出現(xiàn)的標頭字段與索引值。該表是有序的，只讀的，始終可以訪問，并且可以在所有編碼或解碼之間共享上下文。 標頭列表：標頭列表是標頭字段的有序集合聯(lián)合編碼，并且可以包含重復的標頭字段。HTTP / 2標頭中包含的標頭字段的完整列表塊是標題列表。 標頭字段表示形式：標頭字段可以表示為編碼形式，可以是文字形式或索引形式。 標頭塊：標頭字段表示形式的有序列表，解碼時會產(chǎn)生完整的標頭列表。
索引表
HPACK使用兩個表將標頭字段與索引相關(guān)聯(lián)。的靜態(tài)表是預定義的，并且包含通用表標頭字段（其中大多數(shù)帶有空值）。動態(tài)表是動態(tài)的，編碼器可以使用它來在編碼的標題列表中重復的索引標題字段。 這兩個表合并為一個地址空間，用于定義索引值。
索引地址空間
索引嚴格大于靜態(tài)表的長度動態(tài)表中的元素的長度減去靜態(tài)表以找到動態(tài)表中的索引。 索引嚴格大于兩個表的長度之和必須視為解碼錯誤。
頭字段表示處理
定義了獲取報頭列表的頭塊的處理過程在這一部分。以確保解碼成功生成一個報頭列表時，解碼器必須遵守以下規(guī)則。
頭塊中包含的所有頭字段表示都是按照它們出現(xiàn)的順序進行處理。
indexed表示形式需要執(zhí)行以下操作： 對應(yīng)于任一項中所引用條目的標題字段靜態(tài)表或動態(tài)表被附加到解碼后標頭列表。 動態(tài)表中未添加的文字表示形式需要采取以下措施： 頭字段被附加到解碼后的標頭列表中。 動態(tài)表的文字表示形式需要執(zhí)行以下操作： 標頭字段被附加到解碼后的標頭列表中。 頭字段插入到動態(tài)內(nèi)容的開頭表。此插入可能導致驅(qū)逐先前的動態(tài)表中的條目。
計算表大小
動態(tài)表的大小是其表項大小的總和。 條目的大小是其名稱長度的總和（以八位字節(jié)為單位），其值的長度（以八位字節(jié)為單位）和32。 條目的大小是使用其名稱的長度和值，不應(yīng)用任何霍夫曼編碼。
動態(tài)表大小更改時的逐出
每當減小動態(tài)表的最大大小時，條目從動態(tài)表的末尾逐出，直到動態(tài)表小于或等于最大大小。
添加新條目時將條目逐出
在將新條目添加到動態(tài)表之前，逐出條目從動態(tài)表的末尾到動態(tài)表的大小小于或等于（最大大小-新條目大?。┗蛑钡奖硎强盏?。如果新條目的大小小于或等于最大大小，該條目將添加表中。這不是錯誤嘗試添加一個大于最大大小的條目；一個嘗試添加大于最大大小的條目導致表清空所有現(xiàn)有條目并生成一個空表。 新條目可以引用動態(tài)表中的條目名稱將此新條目添加到動態(tài)廣告素材中時將被逐出表。請注意實現(xiàn)，以免刪除如果引用條目已從動態(tài)表中逐出，則引用名稱表，然后插入新條目。
整數(shù)表示
整數(shù)用于表示名稱索引，標頭字段索引或字符串長度。整數(shù)表示可以從一個八位位組。為了優(yōu)化處理，整數(shù)表示總是在八位字節(jié)的末尾結(jié)束。 整數(shù)分為兩部分：前綴填充當前八位位組和可選的八位位組列表，如果整數(shù)值不適合前綴的位數(shù)前綴（稱為N）是整數(shù)表示的參數(shù)。 如果整數(shù)值足夠小，即嚴格小于2 ^ N-1，它被編碼在N位前綴內(nèi)。
否則，將前綴的所有位設(shè)置為1，并將值設(shè)置為使用一個或多個八位位組的列表對減少了2 ^ N-1的位進行編碼。每個八位位組的最高有效位用作延續(xù) 標志：除列表中的最后一個八位字節(jié)外，其值均設(shè)置為1。八位位組的其余位用于編碼減少的值。
代碼示例：
字符串文字表示
頭字段名稱和頭字段值可以表示為字符串文字。字符串文字被編碼為直接編碼字符串文字的八位字節(jié)或使用霍夫曼代碼。
字符串文字表示形式包含以下字段： H：一位標志H，指示是否字符串是霍夫曼編碼的。 字符串長度：用于編碼字符串的八位字節(jié)數(shù)文字，編碼為帶有7位前綴的整數(shù)。 字符串數(shù)據(jù)：字符串文字的編碼數(shù)據(jù)。如果H為0，那么編碼后的數(shù)據(jù)就是字符串文字的原始八位位組。如果H為'1'，則編碼數(shù)據(jù)為Huffman編碼字符串字面量。 使用霍夫曼編碼的字符串文字使用霍夫曼代碼。編碼后的數(shù)據(jù)是對應(yīng)于的每個八位位組的代碼的按位串聯(lián)字符串文字。 由于霍夫曼編碼的數(shù)據(jù)并不總是以八位字節(jié)為邊界，在其后插入一些填充，直到下一個八位位組邊界。至防止將此填充誤解為字符串的一部分文字，代碼的最高有效位對應(yīng)于使用EOS（字符串結(jié)尾）符號。 解碼時，編碼數(shù)據(jù)末尾的不完整代碼為被視為填充和丟棄。填充嚴格更長超過7位必須視為解碼錯誤。填充不對應(yīng)于EOS代碼的最高有效位 符號必須被視為解碼錯誤?；舴蚵幋a的字符串包含EOS符號的文字必須被視為解碼錯誤。
文字標題字段表示
文字標頭字段表示形式包含文字標頭字段值。標頭字段名稱以文字形式或通過以下方式提供從靜態(tài)表或現(xiàn)有表中引用現(xiàn)有表項動態(tài)表。 本規(guī)范定義了文字頭字段的三種形式表示形式：有索引，無索引，從不索引。
帶增量索引的文字標題字段
具有增量索引表示的文字標頭字段結(jié)果是將頭字段附加到解碼的頭列表中，并且將其作為新條目插入動態(tài)表。
具有增量索引表示的文字標頭字段從“ 01” 2位模式開始。
沒有索引的文字標題字段
沒有索引表示的文字標頭字段會導致將標題字段附加到已解碼的標題列表，而無需更改動態(tài)表。
沒有索引表示形式的文字標頭字段以'0000'4位模式。
文字頭字段從不索引
文字標頭字段永不索引表示形式導致將標題字段附加到已解碼的標題列表，而無需更改動態(tài)表。
文字標頭字段永不索引的表示形式以'0001'4位模式。
動態(tài)表大小更新
動態(tài)表格大小更新從“ 001” 3位模式開始，然后是新的最大尺寸，以整數(shù)表示，帶有5位前綴。 新的最大尺寸必須小于或等于限制由協(xié)議使用HPACK確定。超過此值限制必須視為解碼錯誤。在HTTP / 2中，此限制為SETTINGS_HEADER_TABLE_SIZE參數(shù)的最后一個值（請參見從解碼器收到并確認的通過編碼器。 減小動態(tài)表的最大大小可能會導致條目被驅(qū)逐。
適用于HPACK和HTTP
HPACK可以緩解但不能完全阻止仿照通過強制猜測以匹配整個標頭字段來實現(xiàn)CRIME [ CRIME ]值而不是單個字符。攻擊者只能學習猜測是否正確，因此將其簡化為蠻力 猜測標題字段的值。 因此，恢復特定標頭字段值的可行性取決于值的熵。結(jié)果，具有高價值的不太可能成功恢復。但是，價值低的參數(shù)仍然脆弱。 這種性質(zhì)的攻擊有可能在任何兩個相互之間的時間不信任的實體控制放置的請求或響應(yīng)到單個HTTP / 2連接上。如果共享HPACK壓縮器允許一個實體向動態(tài)表中添加條目，而另一個實體訪問這些條目，則可以了解表的狀態(tài)。 來自互不信任實體的請求或響應(yīng)發(fā)生以下情況時，中介者： 在單個連接上將來自多個客戶端的請求發(fā)送到原始服務(wù)器，或從多個原始服務(wù)器獲取響應(yīng)并將其放置在與客戶端的共享連接。 Web瀏覽器還需要假設(shè)請求是在相同的不同Web來源的連接是相互建立的不信任的實體。
twitter hpack
關(guān)鍵代碼：
Encoder.java
/**
* Encode the header field into the header block.
*/
public void encodeHeader(OutputStream out, byte[] name, byte[] value, boolean sensitive) throws IOException {
// If the header value is sensitive then it must never be indexed
if (sensitive) {
int nameIndex = getNameIndex(name);
encodeLiteral(out, name, value, IndexType.NEVER, nameIndex);
return;
}
// If the peer will only use the static table
if (capacity == 0) {
int staticTableIndex = StaticTable.getIndex(name, value);
if (staticTableIndex == -1) {
int nameIndex = StaticTable.getIndex(name);
encodeLiteral(out, name, value, IndexType.NONE, nameIndex);
} else {
encodeInteger(out, 0x80, 7, staticTableIndex);
}
return;
}
int headerSize = HeaderField.sizeOf(name, value);
// If the headerSize is greater than the max table size then it must be encoded literally
if (headerSize > capacity) {
int nameIndex = getNameIndex(name);
encodeLiteral(out, name, value, IndexType.NONE, nameIndex);
return;
}
HeaderEntry headerField = getEntry(name, value);
if (headerField != null) {
int index = getIndex(headerField.index) + StaticTable.length;
// Section 6.1\. Indexed Header Field Representation
encodeInteger(out, 0x80, 7, index);
} else {
int staticTableIndex = StaticTable.getIndex(name, value);
if (staticTableIndex != -1) {
// Section 6.1\. Indexed Header Field Representation
encodeInteger(out, 0x80, 7, staticTableIndex);
} else {
int nameIndex = getNameIndex(name);
if (useIndexing) {
ensureCapacity(headerSize);
}
IndexType indexType = useIndexing ? IndexType.INCREMENTAL : IndexType.NONE;
encodeLiteral(out, name, value, indexType, nameIndex);
if (useIndexing) {
add(name, value);
}
}
}
}
Decode.java
/**
* Decode the header block into header fields.
*/
public void decode(InputStream in, HeaderListener headerListener) throws IOException {
while (in.available() > 0) {
switch (state) {
case READ_HEADER_REPRESENTATION:
byte b = (byte) in.read();
if (maxDynamicTableSizeChangeRequired && (b & 0xE0) != 0x20) {
// Encoder MUST signal maximum dynamic table size change
throw MAX_DYNAMIC_TABLE_SIZE_CHANGE_REQUIRED;
}
if (b < 0) {
// Indexed Header Field
index = b & 0x7F;
if (index == 0) {
throw ILLEGAL_INDEX_VALUE;
} else if (index == 0x7F) {
state = State.READ_INDEXED_HEADER;
} else {
indexHeader(index, headerListener);
}
} else if ((b & 0x40) == 0x40) {
// Literal Header Field with Incremental Indexing
indexType = IndexType.INCREMENTAL;
index = b & 0x3F;
if (index == 0) {
state = State.READ_LITERAL_HEADER_NAME_LENGTH_PREFIX;
} else if (index == 0x3F) {
state = State.READ_INDEXED_HEADER_NAME;
} else {
// Index was stored as the prefix
readName(index);
state = State.READ_LITERAL_HEADER_VALUE_LENGTH_PREFIX;
}
} else if ((b & 0x20) == 0x20) {
// Dynamic Table Size Update
index = b & 0x1F;
if (index == 0x1F) {
state = State.READ_MAX_DYNAMIC_TABLE_SIZE;
} else {
setDynamicTableSize(index);
state = State.READ_HEADER_REPRESENTATION;
}
} else {
// Literal Header Field without Indexing / never Indexed
indexType = ((b & 0x10) == 0x10) ? IndexType.NEVER : IndexType.NONE;
index = b & 0x0F;
if (index == 0) {
state = State.READ_LITERAL_HEADER_NAME_LENGTH_PREFIX;
} else if (index == 0x0F) {
state = State.READ_INDEXED_HEADER_NAME;
} else {
// Index was stored as the prefix
readName(index);
state = State.READ_LITERAL_HEADER_VALUE_LENGTH_PREFIX;
}
}
break;
case READ_MAX_DYNAMIC_TABLE_SIZE:
int maxSize = decodeULE128(in);
if (maxSize == -1) {
return;
}
// Check for numerical overflow
if (maxSize > Integer.MAX_VALUE - index) {
throw DECOMPRESSION_EXCEPTION;
}
setDynamicTableSize(index + maxSize);
state = State.READ_HEADER_REPRESENTATION;
break;
case READ_INDEXED_HEADER:
int headerIndex = decodeULE128(in);
if (headerIndex == -1) {
return;
}
// Check for numerical overflow
if (headerIndex > Integer.MAX_VALUE - index) {
throw DECOMPRESSION_EXCEPTION;
}
indexHeader(index + headerIndex, headerListener);
state = State.READ_HEADER_REPRESENTATION;
break;
case READ_INDEXED_HEADER_NAME:
// Header Name matches an entry in the Header Table
int nameIndex = decodeULE128(in);
if (nameIndex == -1) {
return;
}
// Check for numerical overflow
if (nameIndex > Integer.MAX_VALUE - index) {
throw DECOMPRESSION_EXCEPTION;
}
readName(index + nameIndex);
state = State.READ_LITERAL_HEADER_VALUE_LENGTH_PREFIX;
break;
case READ_LITERAL_HEADER_NAME_LENGTH_PREFIX:
b = (byte) in.read();
huffmanEncoded = (b & 0x80) == 0x80;
index = b & 0x7F;
if (index == 0x7f) {
state = State.READ_LITERAL_HEADER_NAME_LENGTH;
} else {
nameLength = index;
// Disallow empty names -- they cannot be represented in HTTP/1.x
if (nameLength == 0) {
throw DECOMPRESSION_EXCEPTION;
}
// Check name length against max header size
if (exceedsMaxHeaderSize(nameLength)) {
if (indexType == IndexType.NONE) {
// Name is unused so skip bytes
name = EMPTY;
skipLength = nameLength;
state = State.SKIP_LITERAL_HEADER_NAME;
break;
}
// Check name length against max dynamic table size
if (nameLength + HEADER_ENTRY_OVERHEAD > dynamicTable.capacity()) {
dynamicTable.clear();
name = EMPTY;
skipLength = nameLength;
state = State.SKIP_LITERAL_HEADER_NAME;
break;
}
}
state = State.READ_LITERAL_HEADER_NAME;
}
break;
case READ_LITERAL_HEADER_NAME_LENGTH:
// Header Name is a Literal String
nameLength = decodeULE128(in);
if (nameLength == -1) {
return;
}
// Check for numerical overflow
if (nameLength > Integer.MAX_VALUE - index) {
throw DECOMPRESSION_EXCEPTION;
}
nameLength += index;
// Check name length against max header size
if (exceedsMaxHeaderSize(nameLength)) {
if (indexType == IndexType.NONE) {
// Name is unused so skip bytes
name = EMPTY;
skipLength = nameLength;
state = State.SKIP_LITERAL_HEADER_NAME;
break;
}
// Check name length against max dynamic table size
if (nameLength + HEADER_ENTRY_OVERHEAD > dynamicTable.capacity()) {
dynamicTable.clear();
name = EMPTY;
skipLength = nameLength;
state = State.SKIP_LITERAL_HEADER_NAME;
break;
}
}
state = State.READ_LITERAL_HEADER_NAME;
break;
case READ_LITERAL_HEADER_NAME:
// Wait until entire name is readable
if (in.available() < nameLength) {
return;
}
name = readStringLiteral(in, nameLength);
state = State.READ_LITERAL_HEADER_VALUE_LENGTH_PREFIX;
break;
case SKIP_LITERAL_HEADER_NAME:
skipLength -= in.skip(skipLength);
if (skipLength == 0) {
state = State.READ_LITERAL_HEADER_VALUE_LENGTH_PREFIX;
}
break;
case READ_LITERAL_HEADER_VALUE_LENGTH_PREFIX:
b = (byte) in.read();
huffmanEncoded = (b & 0x80) == 0x80;
index = b & 0x7F;
if (index == 0x7f) {
state = State.READ_LITERAL_HEADER_VALUE_LENGTH;
} else {
valueLength = index;
// Check new header size against max header size
long newHeaderSize = (long) nameLength + (long) valueLength;
if (exceedsMaxHeaderSize(newHeaderSize)) {
// truncation will be reported during endHeaderBlock
headerSize = maxHeaderSize + 1;
if (indexType == IndexType.NONE) {
// Value is unused so skip bytes
state = State.SKIP_LITERAL_HEADER_VALUE;
break;
}
// Check new header size against max dynamic table size
if (newHeaderSize + HEADER_ENTRY_OVERHEAD > dynamicTable.capacity()) {
dynamicTable.clear();
state = State.SKIP_LITERAL_HEADER_VALUE;
break;
}
}
if (valueLength == 0) {
insertHeader(headerListener, name, EMPTY, indexType);
state = State.READ_HEADER_REPRESENTATION;
} else {
state = State.READ_LITERAL_HEADER_VALUE;
}
}
break;
case READ_LITERAL_HEADER_VALUE_LENGTH:
// Header Value is a Literal String
valueLength = decodeULE128(in);
if (valueLength == -1) {
return;
}
// Check for numerical overflow
if (valueLength > Integer.MAX_VALUE - index) {
throw DECOMPRESSION_EXCEPTION;
}
valueLength += index;
// Check new header size against max header size
long newHeaderSize = (long) nameLength + (long) valueLength;
if (newHeaderSize + headerSize > maxHeaderSize) {
// truncation will be reported during endHeaderBlock
headerSize = maxHeaderSize + 1;
if (indexType == IndexType.NONE) {
// Value is unused so skip bytes
state = State.SKIP_LITERAL_HEADER_VALUE;
break;
}
// Check new header size against max dynamic table size
if (newHeaderSize + HEADER_ENTRY_OVERHEAD > dynamicTable.capacity()) {
dynamicTable.clear();
state = State.SKIP_LITERAL_HEADER_VALUE;
break;
}
}
state = State.READ_LITERAL_HEADER_VALUE;
break;
case READ_LITERAL_HEADER_VALUE:
// Wait until entire value is readable
if (in.available() < valueLength) {
return;
}
byte[] value = readStringLiteral(in, valueLength);
insertHeader(headerListener, name, value, indexType);
state = State.READ_HEADER_REPRESENTATION;
break;
case SKIP_LITERAL_HEADER_VALUE:
valueLength -= in.skip(valueLength);
if (valueLength == 0) {
state = State.READ_HEADER_REPRESENTATION;
}
break;
default:
throw new IllegalStateException("should not reach here");
}
}
}
HuffmanEncoder.java
/**
* Compresses the input string literal using the Huffman coding.
*
* @param out the output stream for the compressed data
* @param data the string literal to be Huffman encoded
* @param off the start offset in the data
* @param len the number of bytes to encode
* @throws IOException if an I/O error occurs. In particular,
* an <code>IOException</code> may be thrown if the
* output stream has been closed.
*/
public void encode(OutputStream out, byte[] data, int off, int len) throws IOException {
if (out == null) {
throw new NullPointerException("out");
} else if (data == null) {
throw new NullPointerException("data");
} else if (off < 0 || len < 0 || (off + len) < 0 || off > data.length || (off + len) > data.length) {
throw new IndexOutOfBoundsException();
} else if (len == 0) {
return;
}
long current = 0;
int n = 0;
for (int i = 0; i < len; i++) {
int b = data[off + i] & 0xFF;
int code = codes[b];
int nbits = lengths[b];
current <<= nbits;
current |= code;
n += nbits;
while (n >= 8) {
n -= 8;
out.write(((int) (current >> n)));
}
}
if (n > 0) {
current <<= (8 - n);
current |= (0xFF >>> n); // this should be EOS symbol
out.write((int) current);
}
}
/**
* Returns the number of bytes required to Huffman encode the input string literal.
*
* @param data the string literal to be Huffman encoded
* @return the number of bytes required to Huffman encode <code>data</code>
*/
public int getEncodedLength(byte[] data) {
if (data == null) {
throw new NullPointerException("data");
}
long len = 0;
for (byte b : data) {
len += lengths[b & 0xFF];
}
return (int) ((len + 7) >> 3);
}
HuffmanDecoder.java
/**
* Decompresses the given Huffman coded string literal.
*
* @param buf the string literal to be decoded
* @return the output stream for the compressed data
* @throws IOException if an I/O error occurs. In particular,
* an <code>IOException</code> may be thrown if the
* output stream has been closed.
*/
public byte[] decode(byte[] buf) throws IOException {
ByteArrayOutputStream baos = new ByteArrayOutputStream();
Node node = root;
int current = 0;
int bits = 0;
for (int i = 0; i < buf.length; i++) {
int b = buf[i] & 0xFF;
current = (current << 8) | b;
bits += 8;
while (bits >= 8) {
int c = (current >>> (bits - 8)) & 0xFF;
node = node.children[c];
bits -= node.bits;
if (node.isTerminal()) {
if (node.symbol == HpackUtil.HUFFMAN_EOS) {
throw EOS_DECODED;
}
baos.write(node.symbol);
node = root;
}
}
}
while (bits > 0) {
int c = (current << (8 - bits)) & 0xFF;
node = node.children[c];
if (node.isTerminal() && node.bits <= bits) {
bits -= node.bits;
baos.write(node.symbol);
node = root;
} else {
break;
}
}
// Section 5.2\. String Literal Representation
// Padding not corresponding to the most significant bits of the code
// for the EOS symbol (0xFF) MUST be treated as a decoding error.
int mask = (1 << bits) - 1;
if ((current & mask) != mask) {
throw INVALID_PADDING;
}
return baos.toByteArray();
}
private static void insert(Node root, int symbol, int code, byte length) {
// traverse tree using the most significant bytes of code
Node current = root;
while (length > 8) {
if (current.isTerminal()) {
throw new IllegalStateException("invalid Huffman code: prefix not unique");
}
length -= 8;
int i = (code >>> length) & 0xFF;
if (current.children[i] == null) {
current.children[i] = new Node();
}
current = current.children[I];
}
Node terminal = new Node(symbol, length);
int shift = 8 - length;
int start = (code << shift) & 0xFF;
int end = 1 << shift;
for (int i = start; i < start + end; i++) {
current.children[i] = terminal;
}
}
附錄
靜態(tài)表定義
靜態(tài)表包含一個預定義的標頭字段的固定列表。 靜態(tài)表是根據(jù)最常見的標題字段創(chuàng)建的由流行的網(wǎng)站使用，另外還有特定于HTTP / 2的信息偽頭字段。對于標題具有一些頻繁值的字段，為每個字段添加了一個條目這些頻繁的價值觀對于其他標題字段，添加了一個條目具有空值。 表列出了構(gòu)成靜態(tài)對象的預定義頭字段表并給出每個條目的索引。
Huffman Code
表中的每一行均定義用于表示符號的代碼： sym：要表示的符號。它是一個十進制值八位位組，可能以ASCII表示形式開頭。一個特定符號“ EOS”用于指示字符串的結(jié)尾文字。 位編碼：符號的霍夫曼編碼，表示為以2為基的整數(shù)，在最高有效位（MSB）上對齊。 十六進制代碼：符號的霍夫曼代碼，表示為十六進制整數(shù)，在最低有效位（LSB）上對齊。 len：代表符號的代碼的位數(shù)。
