Subject: Re: Coverity: HUF_buildCTableFromTree(): Memory - corruptions

From: Nick Terrell <[email-masked]>
Date: Thu, 27 Oct 2022 23:07:42 +0000

> On Oct 26, 2022, at 5:05 PM, coverity-bot <[email-masked]> wrote:
> 
> !-------------------------------------------------------------------|
>  This Message Is From an External Sender
> 
> |-------------------------------------------------------------------!
> 
> Hello!
> 
> This is an experimental semi-automated report about issues detected by
> Coverity from a scan of next-20221026 as part of the linux-next scan project:
> https://scan.coverity.com/projects/linux-next-weekly-scan  
> 
> You're getting this email because you were associated with the identified
> lines of code (noted below) that were touched by commits:
> 
>  Mon Oct 24 12:12:32 2022 -0700
>    2aa14b1ab2c4 ("zstd: import usptream v1.5.2")
> 
> Coverity reported the following:
> 
> *** CID 1525550:  Memory - corruptions  (OVERRUN)
> /lib/zstd/compress/huf_compress.c: 673 in HUF_buildCTableFromTree()
> 667                 min += nbPerRank[n];
> 668                 min >>= 1;
> 669         }   }
> 670         for (n=0; n<alphabetSize; n++)
> 671             HUF_setNbBits(ct + huffNode[n].byte, huffNode[n].nbBits);   /* push nbBits per symbol, symbol order */
> 672         for (n=0; n<alphabetSize; n++)
> vvv     CID 1525550:  Memory - corruptions  (OVERRUN)
> vvv     Overrunning array "valPerRank" of 13 2-byte elements at element index 255 (byte offset 511) using index "HUF_getNbBits(ct[n])" (which evaluates to 255).
> 673             HUF_setValue(ct + n, valPerRank[HUF_getNbBits(ct[n])]++);   /* assign value within rank, symbol order */
> 674         CTable[0] = maxNbBits;
> 675     }
> 676
> 677     size_t HUF_buildCTable_wksp (HUF_CElt* CTable, const unsigned* count, U32 maxSymbolValue, U32 maxNbBits, void* workSpace, size_t wkspSize)
> 678     {
> 
> 
> *** CID 1525549:  Memory - illegal accesses  (OVERRUN)
> /lib/zstd/compress/huf_compress.c: 187 in HUF_writeCTable_wksp()
> 181
> 182         /* convert to weight */
> 183         wksp->bitsToWeight[0] = 0;
> 184         for (n=1; n<huffLog+1; n++)
> 185             wksp->bitsToWeight[n] = (BYTE)(huffLog + 1 - n);
> 186         for (n=0; n<maxSymbolValue; n++)
> vvv     CID 1525549:  Memory - illegal accesses  (OVERRUN)
> vvv     Overrunning array "wksp->bitsToWeight" of 13 bytes at byte offset 255 using index "HUF_getNbBits(ct[n])" (which evaluates to 255).
> 187             wksp->huffWeight[n] = wksp->bitsToWeight[HUF_getNbBits(ct[n])];
> 188
> 189         /* attempt weights compression by FSE */
> 190         if (maxDstSize < 1) return ERROR(dstSize_tooSmall);
> 191         {   CHECK_V_F(hSize, HUF_compressWeights(op+1, maxDstSize-1, wksp->huffWeight, maxSymbolValue, &wksp->wksp, sizeof(wksp->wksp)) );
> 192             if ((hSize>1) & (hSize < maxSymbolValue/2)) {   /* FSE compressed */
> 
> 
> *** CID 1525501:  Memory - corruptions  (OVERRUN)
> /lib/zstd/compress/huf_compress.c: 253 in HUF_readCTable()
> 247                 HUF_setNbBits(ct + n, (BYTE)(tableLog + 1 - w) & -(w != 0));
> 248         }   }
> 249
> 250         /* fill val */
> 251         {   U16 nbPerRank[HUF_TABLELOG_MAX+2]  = {0};  /* support w=0=>n=tableLog+1 */
> 252             U16 valPerRank[HUF_TABLELOG_MAX+2] = {0};
> vvv     CID 1525501:  Memory - corruptions  (OVERRUN)
> vvv     Overrunning array "nbPerRank" of 14 2-byte elements at element index 255 (byte offset 511) using index "HUF_getNbBits(ct[n])" (which evaluates to 255).
> 253             { U32 n; for (n=0; n<nbSymbols; n++) nbPerRank[HUF_getNbBits(ct[n])]++; }
> 254             /* determine stating value per rank */
> 255             valPerRank[tableLog+1] = 0;   /* for w==0 */
> 256             {   U16 min = 0;
> 257                 U32 n; for (n=tableLog; n>0; n--) {  /* start at n=tablelog <-> w=1 */
> 258                     valPerRank[n] = min;     /* get starting value within each rank */
> 
> 
> *** CID 1525481:  Memory - corruptions  (OVERRUN)
> /lib/zstd/compress/huf_compress.c: 263 in HUF_readCTable()
> 257                 U32 n; for (n=tableLog; n>0; n--) {  /* start at n=tablelog <-> w=1 */
> 258                     valPerRank[n] = min;     /* get starting value within each rank */
> 259                     min += nbPerRank[n];
> 260                     min >>= 1;
> 261             }   }
> 262             /* assign value within rank, symbol order */
> vvv     CID 1525481:  Memory - corruptions  (OVERRUN)
> vvv     Overrunning array "valPerRank" of 14 2-byte elements at element index 255 (byte offset 511) using index "HUF_getNbBits(ct[n])" (which evaluates to 255).
> 263             { U32 n; for (n=0; n<nbSymbols; n++) HUF_setValue(ct + n, valPerRank[HUF_getNbBits(ct[n])]++); }
> 264         }
> 265
> 266         *maxSymbolValuePtr = nbSymbols - 1;
> 267         return readSize;
> 268     }

As Jann pointed out these are false positives because the number of bits returned
by HUF_getNbBits() is pre-validated to be within valid.

> *** CID 1505962:    (UNINIT)
> /lib/zstd/compress/zstd_compress.c: 2436 in ZSTD_buildSequencesStatistics()
> 2430                     prevEntropy->offcodeCTable,
> 2431                     sizeof(prevEntropy->offcodeCTable),
> 2432                     entropyWorkspace, entropyWkspSize);
> 2433                 if (ZSTD_isError(countSize)) {
> 2434                     DEBUGLOG(3, "ZSTD_buildCTable for Offsets failed");
> 2435                     stats.size = countSize;
> vvv     CID 1505962:    (UNINIT)
> vvv     Using uninitialized value "stats". Field "stats.MLtype" is uninitialized.
> 2436                     return stats;
> 2437                 }
> 2438                 if (stats.Offtype == set_compressed)
> 2439                     stats.lastCountSize = countSize;
> 2440                 op += countSize;
> 2441                 assert(op <= oend);
> /lib/zstd/compress/zstd_compress.c: 2404 in ZSTD_buildSequencesStatistics()
> 2398                     prevEntropy->litlengthCTable,
> 2399                     sizeof(prevEntropy->litlengthCTable),
> 2400                     entropyWorkspace, entropyWkspSize);
> 2401                 if (ZSTD_isError(countSize)) {
> 2402                     DEBUGLOG(3, "ZSTD_buildCTable for LitLens failed");
> 2403                     stats.size = countSize;
> vvv     CID 1505962:    (UNINIT)
> vvv     Using uninitialized value "stats". Field "stats.Offtype" is uninitialized.
> 2404                     return stats;
> 2405                 }
> 2406                 if (stats.LLtype == set_compressed)
> 2407                     stats.lastCountSize = countSize;
> 2408                 op += countSize;
> 2409                 assert(op <= oend);

These are false positives because the fields are only uninitialized on errors.
And they aren't read if an error is returned.

> *** CID 1505959:  Memory - corruptions  (OVERRUN)
> /lib/zstd/compress/zstd_compress.c: 3220 in ZSTD_estimateBlockSize_sequences()
> 3214                                                       const ZSTD_fseCTablesMetadata_t* fseMetadata,
> 3215                                                       void* workspace, size_t wkspSize,
> 3216                                                       int writeEntropy)
> 3217     {
> 3218         size_t sequencesSectionHeaderSize = 1 /* seqHead */ + 1 /* min seqSize size */ + (nbSeq >= 128) + (nbSeq >= LONGNBSEQ);
> 3219         size_t cSeqSizeEstimate = 0;
> vvv     CID 1505959:  Memory - corruptions  (OVERRUN)
> vvv     Overrunning array "OF_defaultNorm" of 29 2-byte elements by passing it to a function which accesses it at element index 31 (byte offset 63) using argument "31U".
> 3220         cSeqSizeEstimate += ZSTD_estimateBlockSize_symbolType(fseMetadata->ofType, ofCodeTable, nbSeq, MaxOff,
> 3221                                              fseTables->offcodeCTable, NULL,
> 3222                                              OF_defaultNorm, OF_defaultNormLog, DefaultMaxOff,
> 3223                                              workspace, wkspSize);
> 3224         cSeqSizeEstimate += ZSTD_estimateBlockSize_symbolType(fseMetadata->llType, llCodeTable, nbSeq, MaxLL,
> 3225                                              fseTables->litlengthCTable, LL_bits,

This is a false positive because OF_defaultNorm is only read if we've already validated
that the max value is smaller than DefaultMaxOff == 29.

> If these are false positives, please let us know so we can mark it as
> such, or teach the Coverity rules to be smarter. If not, please make sure
> fixes get into linux-next. :) For patches fixing this, please include
> these lines (but double-check the "Fixes" first):

These are all false positives.

> Reported-by: coverity-bot <[email-masked]>
> Addresses-Coverity-ID: 1525550 ("Memory - corruptions")
> Fixes: 2aa14b1ab2c4 ("zstd: import usptream v1.5.2")
> 
> Thanks for your attention!
> 
> -- 
> Coverity-bot