| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <2B7F32C0-2068-4191-AB35-8BA6C3B94935@fb.com>
Date: Thu, 27 Oct 2022 23:07:42 +0000
From: Nick Terrell <terrelln@...a.com>
To: coverity-bot <keescook@...omium.org>
CC: "Gustavo A. R. Silva" <gustavo@...eddedor.com>,
"linux-next@...r.kernel.org" <linux-next@...r.kernel.org>,
"linux-hardening@...r.kernel.org" <linux-hardening@...r.kernel.org>
Subject: Re: Coverity: HUF_buildCTableFromTree(): Memory - corruptions
> On Oct 26, 2022, at 5:05 PM, coverity-bot <keescook@...omium.org> 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 <keescook+coverity-bot@...omium.org>
> Addresses-Coverity-ID: 1525550 ("Memory - corruptions")
> Fixes: 2aa14b1ab2c4 ("zstd: import usptream v1.5.2")
>
> Thanks for your attention!
>
> --
> Coverity-bot
Powered by blists - more mailing lists