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 8c2e28864f8a581ee381e007fdc808f5330bcae7 Author: Lee Rhodes <[email protected]> AuthorDate: Thu Oct 29 14:40:31 2026 -0700 Tuple: validate updatable and compact images Updatable (QuickSelectSketch) image: - Check 0 <= lgNomEntries <= 26 (lgK has the same maximum as Theta), lgCurrentCapacity <= max(lgNomEntries + 1, 5) (the table grows to at most twice the nominal entries, but never starts below 32 slots), and 0 <= lgResizeFactor <= 3. - Check that the count is non-negative, smaller than the table, and that the image holds at least 8 bytes per entry. - Check that the table is plausible for the count: either the starting size or at most 32 times the count. This keeps the exact table size of valid images. Compact image (current and legacy forms): - Check that the image holds the preamble, and that the count is non-negative and fits in the image at 8 bytes per entry. Constructors: the QuickSelectSketch constructors now reject nominal entries that are not positive or are above 2^26, as the builder and Theta already do. Before, UpdatableTupleSketch, TupleUnion and the Double, Integer and ArrayOfStrings sketches accepted them. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- .../datasketches/tuple/CompactTupleSketch.java | 18 +++ .../datasketches/tuple/QuickSelectSketch.java | 47 ++++++- .../datasketches/tuple/TupleCorruptImageTest.java | 146 +++++++++++++++++++++ 3 files changed, 209 insertions(+), 2 deletions(-) diff --git a/src/main/java/org/apache/datasketches/tuple/CompactTupleSketch.java b/src/main/java/org/apache/datasketches/tuple/CompactTupleSketch.java index ab5f06de5..f02da0a21 100644 --- a/src/main/java/org/apache/datasketches/tuple/CompactTupleSketch.java +++ b/src/main/java/org/apache/datasketches/tuple/CompactTupleSketch.java @@ -23,6 +23,7 @@ import static java.lang.foreign.ValueLayout.JAVA_BYTE; import static java.lang.foreign.ValueLayout.JAVA_INT_UNALIGNED; import static java.lang.foreign.ValueLayout.JAVA_LONG_UNALIGNED; import static java.lang.foreign.ValueLayout.JAVA_SHORT_UNALIGNED; +import static org.apache.datasketches.common.Util.checkBounds; import static org.apache.datasketches.common.Util.checkSeedHashes; import static org.apache.datasketches.common.Util.computeSeedHash; import static org.apache.datasketches.tuple.PreambleUtil.COMPACT_FLAGS_BYTE; @@ -118,11 +119,13 @@ public final class CompactTupleSketch<S extends Summary> extends TupleSketch<S> if (version == COMPACT_SER_VER_WITH_CLASS_NAME) { classNameLength = seg.get(JAVA_BYTE, offset++); } + checkBounds(offset, Integer.BYTES, seg.byteSize()); final int count = seg.get(JAVA_INT_UNALIGNED, offset); offset += Integer.BYTES; if (version == COMPACT_SER_VER_WITH_CLASS_NAME) { offset += classNameLength; } + checkCount(count, offset, seg); hashArr_ = new long[count]; for (int i = 0; i < count; i++) { @@ -137,6 +140,7 @@ public final class CompactTupleSketch<S extends Summary> extends TupleSketch<S> summaryArr_ = null; } } else { // current serial format + checkBounds(0, (long) preambleLongs * Long.BYTES, seg.byteSize()); final byte flags = seg.get(JAVA_BYTE, COMPACT_FLAGS_BYTE); final short seedHash = seg.get(JAVA_SHORT_UNALIGNED, SEED_HASH_SHORT); empty_ = (flags & (1 << Flags.IS_EMPTY.ordinal())) > 0; @@ -154,6 +158,7 @@ public final class CompactTupleSketch<S extends Summary> extends TupleSketch<S> } } int offset = preambleLongs * Long.BYTES; // the entries start after the preamble + checkCount(count, offset, seg); hashArr_ = new long[count]; for (int i = 0; i < count; i++) { @@ -164,6 +169,19 @@ public final class CompactTupleSketch<S extends Summary> extends TupleSketch<S> } } + /** + * Checks the retained entries count read from an image. Each entry is at least an 8-byte hash, + * so the remaining bytes of the image bound the count. + * @param count the retained entries count + * @param offset the offset of the first entry + * @param seg the image + */ + private static void checkCount(final int count, final int offset, final MemorySegment seg) { + if ((count < 0) || (((long) count * Long.BYTES) > (seg.byteSize() - offset))) { + throw new SketchesArgumentException("Possible corruption: invalid retained entries count: " + count); + } + } + @SuppressWarnings({"unchecked"}) private int readSummary(final MemorySegment seg, final int offset, final int i, final int count, final SummaryDeserializer<S> deserializer) { diff --git a/src/main/java/org/apache/datasketches/tuple/QuickSelectSketch.java b/src/main/java/org/apache/datasketches/tuple/QuickSelectSketch.java index 5f3777f33..ce62e817e 100644 --- a/src/main/java/org/apache/datasketches/tuple/QuickSelectSketch.java +++ b/src/main/java/org/apache/datasketches/tuple/QuickSelectSketch.java @@ -140,6 +140,10 @@ class QuickSelectSketch<S extends Summary> extends TupleSketch<S> { final float samplingProbability, final SummaryFactory<S> summaryFactory, final short seedHash) { + if ((nomEntries <= 0) || (nomEntries > (1 << ThetaUtil.MAX_LG_NOM_LONGS))) { + throw new SketchesArgumentException("Nominal Entries must be > 0 and <= " + + (1 << ThetaUtil.MAX_LG_NOM_LONGS) + ": " + nomEntries); + } this( nomEntries, lgResizeFactor, @@ -264,9 +268,17 @@ class QuickSelectSketch<S extends Summary> extends TupleSketch<S> { SerializerDeserializer.validateType(seg.get(JAVA_BYTE, SKETCH_TYPE_BYTE), SerializerDeserializer.SketchType.QuickSelectSketch); final byte flags = seg.get(JAVA_BYTE, LEGACY_FLAGS_BYTE); - myNomEntries = 1 << seg.get(JAVA_BYTE, LG_NOM_ENTRIES_BYTE); - myLgCurrentCapacity = seg.get(JAVA_BYTE, LG_CUR_CAPACITY_BYTE); + final int lgNomEntries = seg.get(JAVA_BYTE, LG_NOM_ENTRIES_BYTE); + final int lgCurCapacity = seg.get(JAVA_BYTE, LG_CUR_CAPACITY_BYTE); myLgResizeFactor = seg.get(JAVA_BYTE, LG_RESIZE_FACTOR_BYTE); + // lgK is at most 26, as for Theta. The hash table grows to at most twice the nominal entries, + // but is never smaller than the minimum table size. + if ((lgNomEntries < 0) || (lgNomEntries > ThetaUtil.MAX_LG_NOM_LONGS) || (lgCurCapacity < 0) + || (lgCurCapacity > Math.max(lgNomEntries + 1, ThetaUtil.MIN_LG_ARR_LONGS))) { + throw new SketchesArgumentException("Possible corruption: lgNomEntries: " + lgNomEntries + + ", lgCurrentCapacity: " + lgCurCapacity); + } + myNomEntries = 1 << lgNomEntries; int offset = QS_VARIABLE_START; // the remaining fields are packed and optional checkBounds(0, preambleLongs * 8L, seg.byteSize()); @@ -287,9 +299,17 @@ class QuickSelectSketch<S extends Summary> extends TupleSketch<S> { int count = 0; final boolean hasEntries = (flags & (1 << Flags.HAS_ENTRIES.ordinal())) > 0; if (hasEntries) { + checkBounds(offset, Integer.BYTES, seg.byteSize()); count = seg.get(JAVA_INT_UNALIGNED, offset); offset += Integer.BYTES; } + // each entry is at least an 8-byte hash, so the image bounds the count + if ((count < 0) || (count >= (1L << lgCurCapacity)) + || (((long) count * Long.BYTES) > (seg.byteSize() - offset))) { + throw new SketchesArgumentException("Possible corruption: invalid retained entries count: " + count); + } + checkLgCurrentCapacity(lgCurCapacity, count, lgNomEntries, myLgResizeFactor); + myLgCurrentCapacity = lgCurCapacity; final int currentCapacity = 1 << myLgCurrentCapacity; myHashTable = new long[currentCapacity]; for (int i = 0; i < count; i++) { @@ -315,6 +335,29 @@ class QuickSelectSketch<S extends Summary> extends TupleSketch<S> { } //end class Validate + /** + * Checks that the hash table size declared by an image is plausible for the number of entries it holds. + * A table only grows when its entries reach a threshold, so its size is either the starting size or + * at most about 16 times the number of entries, just after a resize with the largest resize factor. + * This bounds the allocation by the size of the image. + * @param lgCurCapacity log2 of the current table size declared by the image + * @param count the number of entries in the image + * @param lgNomEntries log2 of the nominal entries + * @param lgResizeFactor log2 of the resize factor + */ + private static void checkLgCurrentCapacity(final int lgCurCapacity, final int count, final int lgNomEntries, + final int lgResizeFactor) { + if ((lgResizeFactor < 0) || (lgResizeFactor > ResizeFactor.X8.lg())) { + throw new SketchesArgumentException("Possible corruption: lgResizeFactor: " + lgResizeFactor); + } + final int lgStart = ThetaUtil.startingSubMultiple(lgNomEntries + 1, lgResizeFactor, ThetaUtil.MIN_LG_ARR_LONGS); + final int lgCount = (count <= 1) ? 0 : 32 - Integer.numberOfLeadingZeros(count - 1); //ceiling log2 + if (lgCurCapacity > Math.max(lgStart, lgCount + 5)) { + throw new SketchesArgumentException("Possible corruption: lgCurrentCapacity " + lgCurCapacity + + " is too large for " + count + " retained entries"); + } + } + /** * @return a deep copy of this sketch */ diff --git a/src/test/java/org/apache/datasketches/tuple/TupleCorruptImageTest.java b/src/test/java/org/apache/datasketches/tuple/TupleCorruptImageTest.java new file mode 100644 index 000000000..853a001f5 --- /dev/null +++ b/src/test/java/org/apache/datasketches/tuple/TupleCorruptImageTest.java @@ -0,0 +1,146 @@ +/* + * 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.tuple; + +import static org.testng.Assert.assertEquals; +import static org.testng.Assert.assertTrue; +import static org.testng.Assert.expectThrows; + +import java.lang.foreign.MemorySegment; + +import org.apache.datasketches.common.AllocationTracker; +import org.apache.datasketches.common.ByteArrayUtil; +import org.apache.datasketches.common.SketchesArgumentException; +import org.apache.datasketches.tuple.adouble.DoubleSummary; +import org.apache.datasketches.tuple.adouble.DoubleSummaryDeserializer; +import org.apache.datasketches.tuple.adouble.DoubleSummaryFactory; +import org.apache.datasketches.tuple.adouble.DoubleTupleSketch; +import org.testng.annotations.Test; + +/** + * Checks that corrupt tuple sketch images are rejected without large allocations. + */ +@SuppressWarnings("deprecation") +public class TupleCorruptImageTest { + private static final int LG_NOM_BYTE = 5; + private static final int LG_CUR_BYTE = 6; + private static final int COMPACT_COUNT_INT = 8; + private final DoubleSummaryDeserializer deser = new DoubleSummaryDeserializer(); + + private static UpdatableTupleSketch<Double, DoubleSummary> sketch(final int n) { + final UpdatableTupleSketch<Double, DoubleSummary> sk = + new UpdatableTupleSketchBuilder<>(new DoubleSummaryFactory(DoubleSummary.Mode.Sum)).build(); + for (int i = 0; i < n; i++) { sk.update(i, 1.0); } + return sk; + } + + private void checkRejected(final byte[] bytes) { + final MemorySegment seg = MemorySegment.ofArray(bytes); + final long allocated = AllocationTracker.allocatedBytes(() -> TupleSketch.heapifySketch(seg, deser)); + assertTrue(allocated < (1 << 20), "allocated " + allocated); + expectThrows(SketchesArgumentException.class, () -> TupleSketch.heapifySketch(seg, deser)); + } + + @Test + public void checkValidImagesStillWork() { + for (final int n : new int[] {0, 1, 10, 100, 10_000}) { + final UpdatableTupleSketch<Double, DoubleSummary> sk = sketch(n); + assertEquals(TupleSketch.heapifySketch(MemorySegment.ofArray(sk.toByteArray()), deser).getRetainedEntries(), + sk.getRetainedEntries()); + assertEquals(TupleSketch.heapifySketch(MemorySegment.ofArray(sk.compact().toByteArray()), deser) + .getRetainedEntries(), sk.getRetainedEntries()); + } + } + + @Test + public void checkUpdatableLargeTable() { + final byte[] bytes = sketch(10).toByteArray(); + bytes[LG_NOM_BYTE] = 25; + bytes[LG_CUR_BYTE] = 26; //far too large for 10 entries + checkRejected(bytes); + } + + @Test + public void checkSmallNominalEntriesStillWork() { + //for nominal entries below 16 the table starts at the minimum size, which is more than twice nominal + for (int lgK = 0; lgK <= 5; lgK++) { + for (int lgRF = 0; lgRF <= 3; lgRF++) { + for (final int n : new int[] {0, 1, 3, 100}) { + final DoubleTupleSketch sk = new DoubleTupleSketch(lgK, lgRF, 1.0F, DoubleSummary.Mode.Sum); + for (int i = 0; i < n; i++) { sk.update(i, 1.0); } + final byte[] bytes = sk.toByteArray(); + assertEquals(TupleSketch.heapifySketch(MemorySegment.ofArray(bytes), deser).getRetainedEntries(), + sk.getRetainedEntries()); + assertEquals(new DoubleTupleSketch(MemorySegment.ofArray(bytes), DoubleSummary.Mode.Sum) + .getRetainedEntries(), sk.getRetainedEntries()); + } + } + } + } + + @Test + public void checkUpdatableTableLargerThanNominal() { + final byte[] bytes = sketch(10).toByteArray(); + bytes[LG_CUR_BYTE] = (byte) (bytes[LG_NOM_BYTE] + 2); + checkRejected(bytes); + final byte[] bytes2 = sketch(10).toByteArray(); + bytes2[LG_NOM_BYTE] = 30; + checkRejected(bytes2); + final byte[] bytes3 = sketch(10).toByteArray(); + bytes3[LG_NOM_BYTE] = 27; //lgK above the Theta maximum of 26 + checkRejected(bytes3); + } + + @Test + public void checkConstructorNominalEntriesLimit() { + final DoubleSummaryFactory factory = new DoubleSummaryFactory(DoubleSummary.Mode.Sum); + assertEquals(new UpdatableTupleSketch<Double, DoubleSummary>(1 << 26, 3, 1f, factory).getNominalEntries(), 1 << 26); + expectThrows(SketchesArgumentException.class, + () -> new UpdatableTupleSketch<Double, DoubleSummary>((1 << 26) + 1, 3, 1f, factory)); + expectThrows(SketchesArgumentException.class, + () -> new UpdatableTupleSketch<Double, DoubleSummary>(0, 3, 1f, factory)); + expectThrows(SketchesArgumentException.class, () -> new TupleUnion<DoubleSummary>(1 << 27, null)); + expectThrows(SketchesArgumentException.class, + () -> new DoubleTupleSketch(27, 3, 1f, DoubleSummary.Mode.Sum)); + } + + @Test + public void checkUpdatableCountBeyondImage() { + final byte[] bytes = sketch(10).toByteArray(); + ByteArrayUtil.putIntLE(bytes, 8, 1 << 28); //count: no sampling and no theta, so it is at byte 8 + checkRejected(bytes); + } + + @Test + public void checkCompactCountBeyondImage() { + final byte[] bytes = sketch(10).compact().toByteArray(); + ByteArrayUtil.putIntLE(bytes, COMPACT_COUNT_INT, 1 << 28); + checkRejected(bytes); + final byte[] negative = sketch(10).compact().toByteArray(); + ByteArrayUtil.putIntLE(negative, COMPACT_COUNT_INT, -1); + checkRejected(negative); + } + + @Test + public void checkCompactTruncatedPreamble() { + final byte[] bytes = java.util.Arrays.copyOf(sketch(10).compact().toByteArray(), 12); + checkRejected(bytes); + } +} --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
