CVE-2019-11940 (C++, published 2019-12-04T17:16Z)
Description: value: In the course of decompressing HPACK inside the HTTP2 protocol, an unexpected sequence of header table resize operations can place the header table into a corrupted state, leading to a use-after-free condition and undefined behavior. This issue affects Proxygen from v0.29.0 until v2017.04.03.00.
Severity: HIGH (CVSS v3 base score: 9.8)
Weakness: CWE-416 \u2014 Use After Free
The product reuses or references memory after it has been freed. At some point afterward, the memory may be allocated again and saved in another pointer, while the original pointer references a location somewhere within the new allocation. Any operations using the original pointer are no longer valid because the memory "belongs" to the code that operates on the new pointer.
Repository: https://github.com/facebook/proxygen
Files changed:
proxygen/lib/http/codec/compress/HeaderTable.cpp
proxygen/lib/http/codec/compress/test/HeaderTableTests.cpp
Commit message: Fixing HPACK header table resize issue

Summary: On resizing the header table down and then up again, a resize can be called against the underlying vector that actually sizes it down.  This causes a lot of things to break as the code that does the resizing assumes the underlying vector is only ever resized up.

Reviewed By: afrind

Differential Revision: D4613681

fbshipit-source-id: 35b61cab53d5bc097424d6c779f90b7fdea42002


Vulnerable code:
  if (capacity_ <= oldCapacity) {
    auto oldTail = tail();
    auto oldLength = table_.size();
    table_.resize(newLength);
    if (size_ > 0 && oldTail > head_) {
      // the list wrapped around, need to move oldTail..oldLength to the end of
      // the now-larger table_
      std::copy(table_.begin() + oldTail, table_.begin() + oldLength,
                table_.begin() + newLength - (oldLength - oldTail));
      // Update the names indecies that pointed to the old range
      for (auto& names_it: names_) {
        for (auto& idx: names_it.second) {
          if (idx >= oldTail) {
            DCHECK_LT(idx + (table_.size() - oldLength), table_.size());
            idx += (table_.size() - oldLength);
          } else {
            // remaining indecies in the list were smaller than oldTail, so
            // should be indexed from 0
            break;
TEST_F(HeaderTableTests, set_capacity) {

Fixed code:
  // TODO: ddmello - the below is a little dangerous as we update the
  // capacity right away.  Some properties of the class utilize that variable
  // and so might be better to refactor and update capacity at the end of the
  // method (and update other methods)
  if (capacity_ == oldCapacity) {
    return;
  } else if (capacity_ < oldCapacity) {
    // NOTE: currently no actual resizing is performed...
    // NOTE: due to the above lack of resizing, we must determine whether a
    // resize is actually appropriate (to handle cases where the underlying
    // vector is still >= to the size related to the new capacity requested)
    if (newLength > table_.size()) {
      auto oldTail = tail();
      auto oldLength = table_.size();
      table_.resize(newLength);
      if (size_ > 0 && oldTail > head_) {
        // the list wrapped around, need to move oldTail..oldLength to the end
        // of the now-larger table_
        std::copy(table_.begin() + oldTail, table_.begin() + oldLength,
                  table_.begin() + newLength - (oldLength - oldTail));
        // Update the names indecies that pointed to the old range
        for (auto& names_it: names_) {
          for (auto& idx: names_it.second) {
            if (idx >= oldTail) {
              DCHECK_LT(idx + (table_.size() - oldLength), table_.size());
              idx += (table_.size() - oldLength);
            } else {
              // remaining indecies in the list were smaller than oldTail, so
              // should be indexed from 0
              break;
            }
  void resizeTable(HeaderTable& table, uint32_t newCapacity, uint32_t newMax) {
    table.setCapacity(newCapacity);
    // On resizing the table size (count of headers) remains the same or sizes
    // down; can not size up
    EXPECT_LE(table.size(), newMax);
  }

  void resizeAndFillTable(
      HeaderTable& table, HPACKHeader& header, uint32_t newMax,
      uint32_t fillCount) {
    uint32_t newCapacity = header.bytes() * newMax;
    resizeTable(table, newCapacity, newMax);
    // Fill the table (with one extra) and make sure we haven't violated our
    // size (bytes) limits (expected one entry to be evicted)
    for (size_t i = 0; i <= fillCount; ++i) {
      EXPECT_EQ(table.add(header), true);
    }
    EXPECT_EQ(table.size(), newMax);
    EXPECT_EQ(table.bytes(), newCapacity);
  }

TEST_F(HeaderTableTests, reduce_capacity) {
  EXPECT_GT(table.length(), max);
TEST_F(HeaderTableTests, varyCapacity) {
  HPACKHeader accept("accept-encoding", "gzip");
  uint32_t max = 6;
  uint32_t capacity = accept.bytes() * max;
  HeaderTable table(capacity);

  // Fill the table (extra) and make sure we haven't violated our
  // size (bytes) limits (expected one entry to be evicted)
  for (size_t i = 0; i <= table.length(); ++i) {
    EXPECT_EQ(table.add(accept), true);
  }
  EXPECT_EQ(table.size(), max);

  // Size down the table and verify we are still honoring our size (bytes)
  // limits
  resizeAndFillTable(table, accept, 4, 5);

  // Size up the table (in between previous max and min within test) and verify
  // we are still horing our size (bytes) limits
  resizeAndFillTable(table, accept, 5, 6);

  // Finally reize up one last timestamps
  resizeAndFillTable(table, accept, 8, 9);
}

TEST_F(HeaderTableTests, varyCapacityMalignHeadIndex) {
  // Test checks for a previous bug/crash condition where due to resizing
  // the underlying table to a size lower than a previous max but up from the
  // current size and the position of the head_ index an out of bounds index
  // would occur

  // Initialize header table
  HPACKHeader accept("accept-encoding", "gzip");
  uint32_t max = 6;
  uint32_t capacity = accept.bytes() * max;
  HeaderTable table(capacity);

  // Push head_ to last index in underlying table before potential wrap
  // This is our max table size for the duration of the test
  for (size_t i = 0; i < table.length(); ++i) {
    EXPECT_EQ(table.add(accept), true);
  }
  EXPECT_EQ(table.size(), max);
  EXPECT_EQ(table.bytes(), capacity);

  // Flush underlying table (head_ remains the same at the previous max index)
  // Header guranteed to cause a flush as header itself requires 32 bytes plus
  // the sizes of the name and value anyways (which themselves would cause a
  // flush)
  string strLargerThanTableCapacity = string(capacity + 1, 'a');
  HPACKHeader flush("flush", strLargerThanTableCapacity);
  EXPECT_EQ(table.add(flush), false);
  EXPECT_EQ(table.size(), 0);

  // Now reduce capacity of table (in functional terms table.size() is lowered
  // but currently table.length() remains the same)
  max = 3;
  resizeTable(table, accept.bytes() * max, max);

  // Increase capacity of table (but smaller than all time max; head_ still at
  // previous max index).  Previously (now fixed) this size up resulted in
  // incorrect resizing semantics
  max = 4;
  resizeTable(table, accept.bytes() * max, max);

  // Now try and add headers; there should be no crash with current position of
  // head_ in the underlying table.  Note this is merely one possible way we
  // could force the test to crash as a result of the resize bug this test was
  // added for
  for (size_t i = 0; i <= table.length(); ++i) {
    EXPECT_EQ(table.add(accept), true);
  }
  EXPECT_EQ(table.size(), max);
}