This is an automated email from the ASF dual-hosted git repository. leerho pushed a commit to branch 9.1.X in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 4dc80febf09d093982f38c90f4fd18cfd6b1707a Author: Lee Rhodes <[email protected]> AuthorDate: Thu Oct 29 14:48:30 2026 -0700 Theta: validate sketch, union and intersection images - checkSegIntegrity(), used for updatable, alpha and union images (heapify and wrap): check lgNomLongs <= 26, 0 <= lgArrLongs <= lgNomLongs + 1 and 0 <= curCount <= table size, and compute the required size in long arithmetic. - Compact images (heapify, and wrap of a MemorySegment or byte[]): check that curCount is non-negative and that the image holds the hashes. Images in hash-table form must hold the whole table. - Compressed images (serial version 4): check preLongs, entryBits and numEntriesBytes, and that the image holds numEntries * entryBits bits. - Intersection images (heapify and wrap): check 0 <= lgArrLongs <= 27, -1 <= curCount <= table size (-1 means no result yet), and that the image holds the table when curCount > 0. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- .../datasketches/theta/CompactOperations.java | 7 ++ .../datasketches/theta/CompactThetaSketch.java | 1 + .../theta/DirectCompactCompressedSketch.java | 1 + .../datasketches/theta/DirectCompactSketch.java | 1 + .../apache/datasketches/theta/PreambleUtil.java | 44 +++++++ .../datasketches/theta/ThetaIntersectionImpl.java | 15 +++ .../datasketches/theta/UpdatableThetaSketch.java | 16 ++- .../theta/WrappedCompactCompressedSketch.java | 3 + .../datasketches/theta/WrappedCompactSketch.java | 1 + .../datasketches/theta/ThetaCorruptImageTest.java | 137 +++++++++++++++++++++ 10 files changed, 223 insertions(+), 3 deletions(-) diff --git a/src/main/java/org/apache/datasketches/theta/CompactOperations.java b/src/main/java/org/apache/datasketches/theta/CompactOperations.java index 99d406600..a09d80cac 100644 --- a/src/main/java/org/apache/datasketches/theta/CompactOperations.java +++ b/src/main/java/org/apache/datasketches/theta/CompactOperations.java @@ -52,6 +52,7 @@ import java.util.Arrays; import org.apache.datasketches.common.Family; import org.apache.datasketches.common.SketchesArgumentException; import org.apache.datasketches.common.SketchesStateException; +import org.apache.datasketches.thetacommon.ThetaUtil; /** * @author Lee Rhodes @@ -174,9 +175,15 @@ final class CompactOperations { //extract hashArr > 1 final long[] hashArr; if (srcCompactFlag) { + PreambleUtil.checkCompactImage(srcSeg); hashArr = new long[curCount]; MemorySegment.copy(srcSeg, JAVA_LONG_UNALIGNED, srcPreLongs << 3, hashArr, 0, curCount); } else { //update sketch, thus hashTable form + if ((srcLgArrLongs > (ThetaUtil.MAX_LG_NOM_LONGS + 1)) + || (srcSeg.byteSize() < (((long) srcPreLongs << 3) + (8L << srcLgArrLongs)))) { + throw new SketchesArgumentException("Possible corruption: lgArrLongs " + srcLgArrLongs + + " is too large for the MemorySegment size " + srcSeg.byteSize()); + } final int srcCacheLen = 1 << srcLgArrLongs; final long[] tempHashArr = new long[srcCacheLen]; MemorySegment.copy(srcSeg, JAVA_LONG_UNALIGNED, srcPreLongs << 3, tempHashArr, 0, srcCacheLen); diff --git a/src/main/java/org/apache/datasketches/theta/CompactThetaSketch.java b/src/main/java/org/apache/datasketches/theta/CompactThetaSketch.java index 10f2f4986..94461dfda 100644 --- a/src/main/java/org/apache/datasketches/theta/CompactThetaSketch.java +++ b/src/main/java/org/apache/datasketches/theta/CompactThetaSketch.java @@ -397,6 +397,7 @@ public abstract class CompactThetaSketch extends ThetaSketch { final int numEntriesBytes = extractNumEntriesBytesV4(srcSeg); final short seedHash = (short) extractSeedHash(srcSeg); PreambleUtil.checkSegmentSeedHash(srcSeg, seed); + PreambleUtil.checkCompressedImage(srcSeg); int offsetBytes = 8; long theta = Long.MAX_VALUE; if (preLongs > 1) { diff --git a/src/main/java/org/apache/datasketches/theta/DirectCompactCompressedSketch.java b/src/main/java/org/apache/datasketches/theta/DirectCompactCompressedSketch.java index 9f37241d2..b3c757709 100644 --- a/src/main/java/org/apache/datasketches/theta/DirectCompactCompressedSketch.java +++ b/src/main/java/org/apache/datasketches/theta/DirectCompactCompressedSketch.java @@ -58,6 +58,7 @@ final class DirectCompactCompressedSketch extends DirectCompactSketch { */ static DirectCompactCompressedSketch wrapInstance(final MemorySegment srcSeg, final short seedHash) { Util.checkSeedHashes((short) extractSeedHash(srcSeg), seedHash); + PreambleUtil.checkCompressedImage(srcSeg); return new DirectCompactCompressedSketch(srcSeg); } diff --git a/src/main/java/org/apache/datasketches/theta/DirectCompactSketch.java b/src/main/java/org/apache/datasketches/theta/DirectCompactSketch.java index 6c01d78a9..9a28383a6 100644 --- a/src/main/java/org/apache/datasketches/theta/DirectCompactSketch.java +++ b/src/main/java/org/apache/datasketches/theta/DirectCompactSketch.java @@ -68,6 +68,7 @@ class DirectCompactSketch extends CompactThetaSketch { */ static DirectCompactSketch wrapInstance(final MemorySegment srcSeg, final short seedHash) { Util.checkSeedHashes((short) extractSeedHash(srcSeg), seedHash); + PreambleUtil.checkCompactImage(srcSeg); return new DirectCompactSketch(srcSeg); } diff --git a/src/main/java/org/apache/datasketches/theta/PreambleUtil.java b/src/main/java/org/apache/datasketches/theta/PreambleUtil.java index ec6ad22aa..c135cd952 100644 --- a/src/main/java/org/apache/datasketches/theta/PreambleUtil.java +++ b/src/main/java/org/apache/datasketches/theta/PreambleUtil.java @@ -527,6 +527,50 @@ final class PreambleUtil { } } + /** + * Checks that a serial version 3 compact image, which is not empty and not a single item, holds the + * number of hashes it declares, before anything is allocated or read from it. + * @param seg the compact image + * @throws SketchesArgumentException if the image is too small or the count is invalid + */ + static void checkCompactImage(final MemorySegment seg) { + final int preLongs = checkSegPreambleCap(seg); + final int curCount = (preLongs > 1) ? extractCurCount(seg) : 1; + final long reqBytes = ((long) preLongs << 3) + ((long) curCount << 3); + if ((curCount < 0) || (seg.byteSize() < reqBytes)) { + throw new SketchesArgumentException("Possible corruption: curCount " + curCount + + " needs " + reqBytes + " bytes, MemorySegment has " + seg.byteSize()); + } + } + + /** + * Checks that a serial version 4 (compressed) compact image holds the number of entries it + * declares, before anything is allocated or read from it. + * @param seg the compressed compact image + * @throws SketchesArgumentException if the image is too small or its fields are invalid + */ + static void checkCompressedImage(final MemorySegment seg) { + final int preLongs = checkSegPreambleCap(seg); + final int entryBits = extractEntryBitsV4(seg); + final int numEntriesBytes = extractNumEntriesBytesV4(seg); + if ((preLongs < 1) || (preLongs > 2) || (entryBits < 1) || (entryBits > 63) + || (numEntriesBytes < 1) || (numEntriesBytes > 4)) { + throw new SketchesArgumentException("Possible corruption: preLongs: " + preLongs + + ", entryBits: " + entryBits + ", numEntriesBytes: " + numEntriesBytes); + } + final int offsetBytes = preLongs << 3; + Util.checkBounds(0, offsetBytes + numEntriesBytes, seg.byteSize()); + long numEntries = 0; + for (int i = 0; i < numEntriesBytes; i++) { + numEntries |= (long) Byte.toUnsignedInt(seg.get(JAVA_BYTE, offsetBytes + i)) << (i << 3); + } + if (numEntries > Integer.MAX_VALUE) { + throw new SketchesArgumentException("Possible corruption: numEntries: " + numEntries); + } + final long packedBytes = ((numEntries * entryBits) + 7) >>> 3; + Util.checkBounds(offsetBytes + numEntriesBytes, packedBytes, seg.byteSize()); + } + static short checkSegmentSeedHash(final MemorySegment seg, final long seed) { final short seedHashSeg = (short) extractSeedHash(seg); Util.checkSeedHashes(seedHashSeg, Util.computeSeedHash(seed)); //throws if bad seedHash diff --git a/src/main/java/org/apache/datasketches/theta/ThetaIntersectionImpl.java b/src/main/java/org/apache/datasketches/theta/ThetaIntersectionImpl.java index 3dfdf4fa1..df3a77f71 100644 --- a/src/main/java/org/apache/datasketches/theta/ThetaIntersectionImpl.java +++ b/src/main/java/org/apache/datasketches/theta/ThetaIntersectionImpl.java @@ -641,6 +641,21 @@ final class ThetaIntersectionImpl extends ThetaIntersection { } //empty = true AND curCount_ = 0: OK } //else empty = false, curCount could be anything + //The hash table holds curCount entries and is no larger than for the largest nominal entries. + //A curCount of -1 means the intersection has no result yet. + final int lgArrLongs = extractLgArrLongs(srcSeg); + if ((lgArrLongs < 0) || (lgArrLongs > (ThetaUtil.MAX_LG_NOM_LONGS + 1)) + || (curCount < -1) || (curCount > (1 << lgArrLongs))) { + throw new SketchesArgumentException("Possible corruption: lgArrLongs: " + lgArrLongs + + ", curCount: " + curCount); + } + if (curCount > 0) { //the image must hold the hash table + final long reqBytes = ((long) CONST_PREAMBLE_LONGS << 3) + (8L << lgArrLongs); + if (srcSeg.byteSize() < reqBytes) { + throw new SketchesArgumentException("Possible corruption: MemorySegment size " + srcSeg.byteSize() + + " < required " + reqBytes); + } + } } } diff --git a/src/main/java/org/apache/datasketches/theta/UpdatableThetaSketch.java b/src/main/java/org/apache/datasketches/theta/UpdatableThetaSketch.java index f3b5898c5..cc6bfd322 100644 --- a/src/main/java/org/apache/datasketches/theta/UpdatableThetaSketch.java +++ b/src/main/java/org/apache/datasketches/theta/UpdatableThetaSketch.java @@ -30,13 +30,13 @@ import static org.apache.datasketches.theta.PreambleUtil.READ_ONLY_FLAG_MASK; import static org.apache.datasketches.theta.PreambleUtil.SER_VER; import static org.apache.datasketches.theta.PreambleUtil.checkSegPreambleCap; import static org.apache.datasketches.theta.PreambleUtil.checkSegmentSeedHash; +import static org.apache.datasketches.theta.PreambleUtil.extractCurCount; import static org.apache.datasketches.theta.PreambleUtil.extractFamilyID; import static org.apache.datasketches.theta.PreambleUtil.extractFlags; import static org.apache.datasketches.theta.PreambleUtil.extractLgResizeFactor; import static org.apache.datasketches.theta.PreambleUtil.extractP; import static org.apache.datasketches.theta.PreambleUtil.extractSerVer; import static org.apache.datasketches.theta.PreambleUtil.extractThetaLong; -import static org.apache.datasketches.theta.PreambleUtil.getUpdatableSegBytes; import static org.apache.datasketches.theta.UpdateReturnState.RejectedNullOrEmpty; import java.lang.foreign.MemorySegment; @@ -562,9 +562,19 @@ public abstract class UpdatableThetaSketch extends ThetaSketch { final short seedHash = checkSegmentSeedHash(srcSeg, expectedSeed); //byte 6,7 Util.checkSeedHashes(seedHash, Util.computeSeedHash(expectedSeed)); - //Check seg capacity, lgArrLongs + //Check lgNomLongs, lgArrLongs and curCount. The hash table grows to at most twice the nominal entries. + if ((lgNomLongs > ThetaUtil.MAX_LG_NOM_LONGS) || (lgArrLongs < 0) || (lgArrLongs > (lgNomLongs + 1))) { + throw new SketchesArgumentException("Possible corruption: lgNomLongs: " + lgNomLongs + + ", lgArrLongs: " + lgArrLongs); + } + final int curCount = extractCurCount(srcSeg); + if ((curCount < 0) || (curCount > (1 << lgArrLongs))) { + throw new SketchesArgumentException("Possible corruption: invalid curCount: " + curCount); + } + + //Check seg capacity, computed in long arithmetic so that it cannot overflow final long curCapBytes = srcSeg.byteSize(); - final int minReqBytes = getUpdatableSegBytes(lgArrLongs, preambleLongs); + final long minReqBytes = (8L << lgArrLongs) + ((long) preambleLongs << 3); if (curCapBytes < minReqBytes) { throw new SketchesArgumentException( "Possible corruption: Current MemorySegment size < min required size: " diff --git a/src/main/java/org/apache/datasketches/theta/WrappedCompactCompressedSketch.java b/src/main/java/org/apache/datasketches/theta/WrappedCompactCompressedSketch.java index d709188ed..bcf752690 100644 --- a/src/main/java/org/apache/datasketches/theta/WrappedCompactCompressedSketch.java +++ b/src/main/java/org/apache/datasketches/theta/WrappedCompactCompressedSketch.java @@ -24,6 +24,8 @@ import static org.apache.datasketches.theta.PreambleUtil.NUM_ENTRIES_BYTES_BYTE_ import static org.apache.datasketches.theta.PreambleUtil.PREAMBLE_LONGS_BYTE; import static org.apache.datasketches.theta.PreambleUtil.wholeBytesToHoldBits; +import java.lang.foreign.MemorySegment; + import org.apache.datasketches.common.ByteArrayUtil; import org.apache.datasketches.common.Util; @@ -52,6 +54,7 @@ final class WrappedCompactCompressedSketch extends WrappedCompactSketch { */ static WrappedCompactCompressedSketch wrapInstance(final byte[] bytes, final short seedHash) { Util.checkSeedHashes(ByteArrayUtil.getShortLE(bytes, PreambleUtil.SEED_HASH_SHORT), seedHash); + PreambleUtil.checkCompressedImage(MemorySegment.ofArray(bytes)); return new WrappedCompactCompressedSketch(bytes); } diff --git a/src/main/java/org/apache/datasketches/theta/WrappedCompactSketch.java b/src/main/java/org/apache/datasketches/theta/WrappedCompactSketch.java index 53ef5c176..4697f1ce2 100644 --- a/src/main/java/org/apache/datasketches/theta/WrappedCompactSketch.java +++ b/src/main/java/org/apache/datasketches/theta/WrappedCompactSketch.java @@ -62,6 +62,7 @@ class WrappedCompactSketch extends CompactThetaSketch { */ static WrappedCompactSketch wrapInstance(final byte[] bytes, final short seedHash) { Util.checkSeedHashes(getShortLE(bytes, SEED_HASH_SHORT), seedHash); + PreambleUtil.checkCompactImage(MemorySegment.ofArray(bytes)); return new WrappedCompactSketch(bytes); } diff --git a/src/test/java/org/apache/datasketches/theta/ThetaCorruptImageTest.java b/src/test/java/org/apache/datasketches/theta/ThetaCorruptImageTest.java new file mode 100644 index 000000000..e9374c182 --- /dev/null +++ b/src/test/java/org/apache/datasketches/theta/ThetaCorruptImageTest.java @@ -0,0 +1,137 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +package org.apache.datasketches.theta; + +import static org.testng.Assert.assertEquals; +import static org.testng.Assert.assertTrue; +import static org.testng.Assert.expectThrows; + +import java.lang.foreign.MemorySegment; +import java.util.function.Function; + +import org.apache.datasketches.common.AllocationTracker; +import org.apache.datasketches.common.ByteArrayUtil; +import org.apache.datasketches.common.SketchesArgumentException; +import org.testng.annotations.Test; + +/** + * Checks that corrupt theta sketch, union and intersection images are rejected without large + * allocations, including when the result of a wrap is used later. + */ +public class ThetaCorruptImageTest { + private static final int LG_ARR_BYTE = 4; + private static final int CUR_COUNT_INT = 8; + + private static UpdatableThetaSketch sketch(final int n) { + final UpdatableThetaSketch sk = UpdatableThetaSketch.builder().build(); + for (int i = 0; i < n; i++) { sk.update(i); } + return sk; + } + + private static void checkRejected(final byte[] bytes, final Function<MemorySegment, Object> deser) { + final long allocated = AllocationTracker.allocatedBytes(() -> deser.apply(MemorySegment.ofArray(bytes))); + assertTrue(allocated < (1 << 20), "allocated " + allocated); + expectThrows(SketchesArgumentException.class, () -> deser.apply(MemorySegment.ofArray(bytes))); + } + + @Test + public void checkValidImagesStillWork() { + final UpdatableThetaSketch sk = sketch(1000); + final byte[] c = sk.compact().toByteArray(); + assertEquals(CompactThetaSketch.heapify(MemorySegment.ofArray(c)).getRetainedEntries(), 1000); + assertEquals(CompactThetaSketch.wrap(MemorySegment.ofArray(c)).getRetainedEntries(), 1000); + assertEquals(CompactThetaSketch.wrap(c).getRetainedEntries(), 1000); + final byte[] z = sk.compact().toByteArrayCompressed(); + assertEquals(CompactThetaSketch.heapify(MemorySegment.ofArray(z)).getRetainedEntries(), 1000); + assertEquals(CompactThetaSketch.wrap(MemorySegment.ofArray(z)).getRetainedEntries(), 1000); + assertEquals(CompactThetaSketch.wrap(z).getRetainedEntries(), 1000); + assertEquals(UpdatableThetaSketch.heapify(MemorySegment.ofArray(sk.toByteArray())).getRetainedEntries(), 1000); + final ThetaUnion union = ThetaSetOperation.builder().buildUnion(); + union.union(sk); + assertEquals(((ThetaUnion) ThetaSetOperation.heapify(MemorySegment.ofArray(union.toByteArray()))) + .getResult().getRetainedEntries(), 1000); + final ThetaIntersection inter = ThetaSetOperation.builder().buildIntersection(); + inter.intersect(sk); + assertEquals(((ThetaIntersection) ThetaSetOperation.heapify(MemorySegment.ofArray(inter.toByteArray()))) + .getResult().getRetainedEntries(), 1000); + } + + @Test + public void checkCompactCountBeyondImage() { + final byte[] bytes = sketch(100).compact().toByteArray(); + ByteArrayUtil.putIntLE(bytes, CUR_COUNT_INT, 1 << 28); + checkRejected(bytes, CompactThetaSketch::heapify); + checkRejected(bytes, ThetaSketch::heapify); + checkRejected(bytes, seg -> CompactThetaSketch.wrap(seg).getCache()); + checkRejected(bytes, _ -> CompactThetaSketch.wrap(bytes).getCache()); + final byte[] negative = sketch(100).compact().toByteArray(); + ByteArrayUtil.putIntLE(negative, CUR_COUNT_INT, -1); + checkRejected(negative, CompactThetaSketch::heapify); + } + + @Test + public void checkCompressedCountBeyondImage() { + final byte[] bytes = sketch(100).compact().toByteArrayCompressed(); + final int numEntriesBytes = bytes[PreambleUtil.NUM_ENTRIES_BYTES_BYTE_V4]; + final int offset = (bytes[0] & 0x3F) << 3; + for (int i = 0; i < numEntriesBytes; i++) { bytes[offset + i] = (byte) 0xFF; } + checkRejected(bytes, CompactThetaSketch::heapify); + checkRejected(bytes, seg -> CompactThetaSketch.wrap(seg).getCache()); + checkRejected(bytes, _ -> CompactThetaSketch.wrap(bytes).getCache()); + final byte[] badBits = sketch(100).compact().toByteArrayCompressed(); + badBits[PreambleUtil.ENTRY_BITS_BYTE_V4] = 0; + checkRejected(badBits, CompactThetaSketch::heapify); + } + + @Test + public void checkUpdatableLargeTable() { + final byte[] bytes = sketch(100).toByteArray(); + bytes[LG_ARR_BYTE] = 30; //(8 << 30) overflows int + checkRejected(bytes, UpdatableThetaSketch::heapify); + checkRejected(bytes, ThetaSketch::heapify); + checkRejected(bytes, UpdatableThetaSketch::wrap); + final byte[] count = sketch(100).toByteArray(); + ByteArrayUtil.putIntLE(count, CUR_COUNT_INT, 1 << 28); + checkRejected(count, UpdatableThetaSketch::heapify); + } + + @Test + public void checkUnionLargeTable() { + final ThetaUnion union = ThetaSetOperation.builder().buildUnion(); + union.union(sketch(100)); + final byte[] bytes = union.toByteArray(); + bytes[LG_ARR_BYTE] = 30; + checkRejected(bytes, ThetaSetOperation::heapify); + checkRejected(bytes, seg -> ThetaUnion.wrap(seg).getResult()); + } + + @Test + public void checkIntersectionLargeTable() { + final ThetaIntersection inter = ThetaSetOperation.builder().buildIntersection(); + inter.intersect(sketch(100)); + final byte[] bytes = inter.toByteArray(); + bytes[LG_ARR_BYTE] = 30; + checkRejected(bytes, ThetaSetOperation::heapify); + checkRejected(bytes, seg -> ThetaIntersection.wrap(seg).getResult()); + final byte[] count = inter.toByteArray(); + ByteArrayUtil.putIntLE(count, CUR_COUNT_INT, 1 << 20); //more than the table holds + checkRejected(count, ThetaSetOperation::heapify); + } +} --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
