CVE-2023-4863 (C, published 2023-09-12T15:15Z)
Description: value: Heap buffer overflow in libwebp in Google Chrome prior to 116.0.5845.187 and libwebp 1.3.2 allowed a remote attacker to perform an out of bounds memory write via a crafted HTML page. (Chromium security severity: Critical)
Severity: nan (CVSS v3 base score: 8.8)
Weakness: CWE-787 \u2014 Out-of-bounds Write
The product writes data past the end, or before the beginning, of the intended buffer.
Repository: https://github.com/webmproject/libwebp
Files changed:
src/dec/vp8l_dec.c
src/dec/vp8li_dec.h
src/utils/huffman_utils.c
src/utils/huffman_utils.h
Commit message: Fix OOB write in BuildHuffmanTable.

First, BuildHuffmanTable is called to check if the data is valid.
If it is and the table is not big enough, more memory is allocated.

This will make sure that valid (but unoptimized because of unbalanced
codes) streams are still decodable.

Bug: chromium:1479274
Change-Id: I31c36dbf3aa78d35ecf38706b50464fd3d375741


Vulnerable code:
  HuffmanCode table[1 << LENGTHS_TABLE_BITS];
  if (!VP8LBuildHuffmanTable(table, LENGTHS_TABLE_BITS,
                             code_length_code_lengths,
                             NUM_CODE_LENGTH_CODES)) {
    p = &table[VP8LPrefetchBits(br) & LENGTHS_TABLE_MASK];
                           int* const code_lengths, HuffmanCode* const table) {
  HuffmanCode* huffman_tables = NULL;
  HuffmanCode* huffman_table = NULL;
  huffman_tables = (HuffmanCode*)WebPSafeMalloc(num_htree_groups * table_size,
                                                sizeof(*huffman_tables));
  if (htree_groups == NULL || code_lengths == NULL || huffman_tables == NULL) {
  huffman_table = huffman_tables;
        htrees[j] = huffman_table;
        size = ReadHuffmanCode(alphabet_size, dec, code_lengths, huffman_table);
          is_trivial_literal = (huffman_table->bits == 0);
        total_size += huffman_table->bits;
        huffman_table += size;
  hdr->huffman_tables_ = huffman_tables;
    WebPSafeFree(huffman_tables);
  WebPSafeFree(hdr->huffman_tables_);
  assert(dec->hdr_.huffman_tables_ != NULL);
  HuffmanCode*    huffman_tables_;
      if (root_table == NULL) continue;
          table += table_size;
          root_table[low].bits = (uint8_t)(table_bits + root_bits);
          root_table[low].value = (uint16_t)((table - root_table) - low);
        code.bits = (uint8_t)(len - root_bits);
        code.value = (uint16_t)sorted[symbol++];
        ReplicateValue(&table[key >> root_bits], step, table_size, code);
int VP8LBuildHuffmanTable(HuffmanCode* const root_table, int root_bits,
  int total_size;
  if (root_table == NULL) {
    total_size = BuildHuffmanTable(NULL, root_bits,
                                   code_lengths, code_lengths_size, NULL);
  } else if (code_lengths_size <= SORTED_SIZE_CUTOFF) {
    total_size = BuildHuffmanTable(root_table, root_bits,
                                   code_lengths, code_lengths_size, sorted);
  } else {   // rare case. Use heap allocation.
    total_size = BuildHuffmanTable(root_table, root_bits,
                                   code_lengths, code_lengths_size, sorted);
// If root_table is NULL, it returns 0 if a lookup cannot be built, something
// > 0 otherwise (but not the table size).
int VP8LBuildHuffmanTable(HuffmanCode* const root_table, int root_bits,

Fixed code:
  HuffmanTables tables;
  if (!VP8LHuffmanTablesAllocate(1 << LENGTHS_TABLE_BITS, &tables) ||
      !VP8LBuildHuffmanTable(&tables, LENGTHS_TABLE_BITS,
                             code_length_code_lengths, NUM_CODE_LENGTH_CODES)) {
    p = &tables.curr_segment->start[VP8LPrefetchBits(br) & LENGTHS_TABLE_MASK];
  VP8LHuffmanTablesDeallocate(&tables);
                           int* const code_lengths,
                           HuffmanTables* const table) {
  HuffmanTables* huffman_tables = &hdr->huffman_tables_;
  // Check the table has been 0 initialized (through InitMetadata).
  assert(huffman_tables->root.start == NULL);
  assert(huffman_tables->curr_segment == NULL);

  if (htree_groups == NULL || code_lengths == NULL ||
      !VP8LHuffmanTablesAllocate(num_htree_groups * table_size,
                                 huffman_tables)) {
        size =
            ReadHuffmanCode(alphabet_size, dec, code_lengths, huffman_tables);
        htrees[j] = huffman_tables->curr_segment->curr_table;
          is_trivial_literal = (htrees[j]->bits == 0);
        total_size += htrees[j]->bits;
        huffman_tables->curr_segment->curr_table += size;
    VP8LHuffmanTablesDeallocate(huffman_tables);
  VP8LHuffmanTablesDeallocate(&hdr->huffman_tables_);
  assert(dec->hdr_.huffman_tables_.root.start != NULL);
  HuffmanTables   huffman_tables_;
          if (root_table != NULL) table += table_size;
          if (root_table != NULL) {
            root_table[low].bits = (uint8_t)(table_bits + root_bits);
            root_table[low].value = (uint16_t)((table - root_table) - low);
          }
        }
        if (root_table != NULL) {
          code.bits = (uint8_t)(len - root_bits);
          code.value = (uint16_t)sorted[symbol++];
          ReplicateValue(&table[key >> root_bits], step, table_size, code);
int VP8LBuildHuffmanTable(HuffmanTables* const root_table, int root_bits,
  const int total_size =
      BuildHuffmanTable(NULL, root_bits, code_lengths, code_lengths_size, NULL);
  if (total_size == 0 || root_table == NULL) return total_size;

  if (root_table->curr_segment->curr_table + total_size >=
      root_table->curr_segment->start + root_table->curr_segment->size) {
    // If 'root_table' does not have enough memory, allocate a new segment.
    // The available part of root_table->curr_segment is left unused because we
    // need a contiguous buffer.
    const int segment_size = root_table->curr_segment->size;
    struct HuffmanTablesSegment* next =
        (HuffmanTablesSegment*)WebPSafeMalloc(1, sizeof(*next));
    if (next == NULL) return 0;
    // Fill the new segment.
    // We need at least 'total_size' but if that value is small, it is better to
    // allocate a big chunk to prevent more allocations later. 'segment_size' is
    // therefore chosen (any other arbitrary value could be chosen).
    next->size = total_size > segment_size ? total_size : segment_size;
    next->start =
        (HuffmanCode*)WebPSafeMalloc(next->size, sizeof(*next->start));
    if (next->start == NULL) {
      WebPSafeFree(next);
      return 0;
    }
    next->curr_table = next->start;
    next->next = NULL;
    // Point to the new segment.
    root_table->curr_segment->next = next;
    root_table->curr_segment = next;
  }
  if (code_lengths_size <= SORTED_SIZE_CUTOFF) {
    BuildHuffmanTable(root_table->curr_segment->curr_table, root_bits,
                      code_lengths, code_lengths_size, sorted);
  } else {  // rare case. Use heap allocation.
    BuildHuffmanTable(root_table->curr_segment->curr_table, root_bits,
                      code_lengths, code_lengths_size, sorted);

int VP8LHuffmanTablesAllocate(int size, HuffmanTables* huffman_tables) {
  // Have 'segment' point to the first segment for now, 'root'.
  HuffmanTablesSegment* const root = &huffman_tables->root;
  huffman_tables->curr_segment = root;
  // Allocate root.
  root->start = (HuffmanCode*)WebPSafeMalloc(size, sizeof(*root->start));
  if (root->start == NULL) return 0;
  root->curr_table = root->start;
  root->next = NULL;
  root->size = size;
  return 1;
}

void VP8LHuffmanTablesDeallocate(HuffmanTables* const huffman_tables) {
  HuffmanTablesSegment *current, *next;
  if (huffman_tables == NULL) return;
  // Free the root node.
  current = &huffman_tables->root;
  next = current->next;
  WebPSafeFree(current->start);
  current->start = NULL;
  current->next = NULL;
  current = next;
  // Free the following nodes.
  while (current != NULL) {
    next = current->next;
    WebPSafeFree(current->start);
    WebPSafeFree(current);
    current = next;
  }
}
// Contiguous memory segment of HuffmanCodes.
typedef struct HuffmanTablesSegment {
  HuffmanCode* start;
  // Pointer to where we are writing into the segment. Starts at 'start' and
  // cannot go beyond 'start' + 'size'.
  HuffmanCode* curr_table;
  // Pointer to the next segment in the chain.
  struct HuffmanTablesSegment* next;
  int size;
} HuffmanTablesSegment;

// Chained memory segments of HuffmanCodes.
typedef struct HuffmanTables {
  HuffmanTablesSegment root;
  // Currently processed segment. At first, this is 'root'.
  HuffmanTablesSegment* curr_segment;
} HuffmanTables;

// Allocates a HuffmanTables with 'size' contiguous HuffmanCodes. Returns 0 on
// memory allocation error, 1 otherwise.
int VP8LHuffmanTablesAllocate(int size, HuffmanTables* huffman_tables);
void VP8LHuffmanTablesDeallocate(HuffmanTables* const huffman_tables);

int VP8LBuildHuffmanTable(HuffmanTables* const root_table, int root_bits,