CVE-2019-11940: Use After Free (CWE-416)
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.
CWE description: 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.
CVSS v3 base score: 9.8
Published: 2019-12-04T17:16Z
Repository: https://github.com/facebook/proxygen
Language: C++
Files changed: proxygen/lib/http/codec/compress/HeaderTable.cpp, proxygen/lib/http/codec/compress/test/HeaderTableTests.cpp
Commit date: 2017-03-30 15:25:12 -0700
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

Diff: diff --git a/proxygen/lib/http/codec/compress/HeaderTable.cpp b/proxygen/lib/http/codec/compress/HeaderTable.cpp
index 95f63b314..db6032f75 100644
--- a/proxygen/lib/http/codec/compress/HeaderTable.cpp
+++ b/proxygen/lib/http/codec/compress/HeaderTable.cpp
@@ -132,34 +132,46 @@ void HeaderTable::removeLast() {
   bytes_ -= table_[t].bytes();
   --size_;
 }
 
 void HeaderTable::setCapacity(uint32_t capacity) {
+  // 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)
   auto oldCapacity = capacity_;
   capacity_ = capacity;
-  if (capacity_ <= oldCapacity) {
+  if (capacity_ == oldCapacity) {
+    return;
+  } else if (capacity_ < oldCapacity) {
+    // NOTE: currently no actual resizing is performed...
     evict(0);
   } else {
-    auto oldTail = tail();
-    auto oldLength = table_.size();
+    // 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)
     uint32_t newLength = (capacity_ >> 5) + 1;
-    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;
+    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;
+            }
           }
         }
       }
     }
   }
diff --git a/proxygen/lib/http/codec/compress/test/HeaderTableTests.cpp b/proxygen/lib/http/codec/compress/test/HeaderTableTests.cpp
index 1f3904f98..1f2a535eb 100644
--- a/proxygen/lib/http/codec/compress/test/HeaderTableTests.cpp
+++ b/proxygen/lib/http/codec/compress/test/HeaderTableTests.cpp
@@ -23,10 +23,31 @@ class HeaderTableTests : public testing::Test {
   void xcheck(uint32_t internal, uint32_t external) {
     EXPECT_EQ(HeaderTable::toExternal(head_, length_, internal), external);
     EXPECT_EQ(HeaderTable::toInternal(head_, length_, external), internal);
   }
 
+  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);
+  }
+
   uint32_t head_{0};
   uint32_t length_{0};
 };
 
 TEST_F(HeaderTableTests, index_translation) {
@@ -92,15 +113,16 @@ TEST_F(HeaderTableTests, evict) {
   EXPECT_EQ(table.add(bigheader), false);
   EXPECT_EQ(table.size(), 0);
   EXPECT_EQ(table.names().size(), 0);
 }
 
-TEST_F(HeaderTableTests, set_capacity) {
+TEST_F(HeaderTableTests, reduce_capacity) {
   HPACKHeader accept("accept-encoding", "gzip");
   uint32_t max = 10;
   uint32_t capacity = accept.bytes() * max;
   HeaderTable table(capacity);
+  EXPECT_GT(table.length(), max);
 
   // fill the table
   for (size_t i = 0; i < max; i++) {
     EXPECT_EQ(table.add(accept), true);
   }
@@ -165,6 +187,81 @@ TEST_F(HeaderTableTests, increaseCapacity) {
   // external index didn't change
   EXPECT_EQ(table.getIndex(accept), 4);
 
 }
 
+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);
+}
+
 }

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);
}