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]

Reply via email to