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 55d9b770e1c0914ef218ac83b072961c29284bf6
Author: Lee Rhodes <[email protected]>
AuthorDate: Thu Oct 29 14:43:52 2026 -0700

    AoD: validate sketch and union images
    
    - Compact images (heapify and wrap): check that numValues is positive, the
      count is non-negative, and the image holds count keys and
      count * numValues values.
    - QuickSelect images (heapify and wrap, and the union, which contains one):
      check that numValues is positive, 0 <= lgNomEntries <= 26,
      lgCurrentCapacity <= max(lgNomEntries + 1, 5) (the table never starts 
below
      32 slots; unions accept nominal entries below 16), 0 <= count <= capacity,
      and that the image holds the whole table, which the serialized form always
      includes.
    
    Co-Authored-By: Claude Opus 5.5 <[email protected]>
---
 .../ArrayOfDoublesCompactSketch.java               |  31 +++++
 .../ArrayOfDoublesQuickSelectSketch.java           |  29 ++++
 .../DirectArrayOfDoublesCompactSketch.java         |   1 +
 .../DirectArrayOfDoublesQuickSelectSketch.java     |   1 +
 .../HeapArrayOfDoublesCompactSketch.java           |   1 +
 .../HeapArrayOfDoublesQuickSelectSketch.java       |   1 +
 .../tuple/arrayofdoubles/AodCorruptImageTest.java  | 154 +++++++++++++++++++++
 7 files changed, 218 insertions(+)

diff --git 
a/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/ArrayOfDoublesCompactSketch.java
 
b/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/ArrayOfDoublesCompactSketch.java
index 1cf3ac040..fb217a7c2 100644
--- 
a/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/ArrayOfDoublesCompactSketch.java
+++ 
b/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/ArrayOfDoublesCompactSketch.java
@@ -19,6 +19,14 @@
 
 package org.apache.datasketches.tuple.arrayofdoubles;
 
+import static java.lang.foreign.ValueLayout.JAVA_BYTE;
+import static java.lang.foreign.ValueLayout.JAVA_INT_UNALIGNED;
+import static org.apache.datasketches.common.Util.checkBounds;
+
+import java.lang.foreign.MemorySegment;
+
+import org.apache.datasketches.common.SketchesArgumentException;
+
 /**
  * Top level compact tuple sketch of type ArrayOfDoubles. Compact sketches are 
never created
  * directly.  They are created as a result of the compact() method on a 
QuickSelectSketch
@@ -46,6 +54,29 @@ public abstract class ArrayOfDoublesCompactSketch extends 
ArrayOfDoublesSketch {
     super(numValues);
   }
 
+  /**
+   * Checks that the given image is large enough for the number of entries and 
values it declares,
+   * before anything is allocated or read from it.
+   * @param seg the serialized compact sketch
+   * @throws SketchesArgumentException if the image is too small or its counts 
are invalid
+   */
+  static void checkCompactImage(final MemorySegment seg) {
+    checkBounds(0, EMPTY_SIZE, seg.byteSize());
+    final int numValues = seg.get(JAVA_BYTE, NUM_VALUES_BYTE);
+    if (numValues < 1) {
+      throw new SketchesArgumentException("Possible corruption: numValues must 
be positive: " + numValues);
+    }
+    final boolean hasEntries = (seg.get(JAVA_BYTE, FLAGS_BYTE) & (1 << 
Flags.HAS_ENTRIES.ordinal())) != 0;
+    if (!hasEntries) { return; }
+    checkBounds(0, ENTRIES_START, seg.byteSize());
+    final int count = seg.get(JAVA_INT_UNALIGNED, RETAINED_ENTRIES_INT);
+    if (count < 0) {
+      throw new SketchesArgumentException("Possible corruption: negative 
retained entries: " + count);
+    }
+    checkBounds(ENTRIES_START, (long) count * (SIZE_OF_KEY_BYTES + ((long) 
SIZE_OF_VALUE_BYTES * numValues)),
+        seg.byteSize());
+  }
+
   @Override
   public int getCurrentBytes() {
     final int count = getRetainedEntries();
diff --git 
a/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/ArrayOfDoublesQuickSelectSketch.java
 
b/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/ArrayOfDoublesQuickSelectSketch.java
index ddf102451..61febdbcb 100644
--- 
a/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/ArrayOfDoublesQuickSelectSketch.java
+++ 
b/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/ArrayOfDoublesQuickSelectSketch.java
@@ -19,7 +19,10 @@
 
 package org.apache.datasketches.tuple.arrayofdoubles;
 
+import static java.lang.foreign.ValueLayout.JAVA_BYTE;
+import static java.lang.foreign.ValueLayout.JAVA_INT_UNALIGNED;
 import static org.apache.datasketches.common.Util.ceilingPowerOf2;
+import static org.apache.datasketches.common.Util.checkBounds;
 
 import java.lang.foreign.MemorySegment;
 
@@ -54,6 +57,32 @@ abstract class ArrayOfDoublesQuickSelectSketch extends 
ArrayOfDoublesUpdatableSk
 
   static final int DEFAULT_LG_RESIZE_FACTOR = 3;
 
+  /**
+   * Checks that the given image holds the whole hash table it declares, and 
that its counts are valid,
+   * before anything is allocated or read from it. The serialized form always 
includes the whole table.
+   * @param seg the serialized QuickSelect sketch
+   * @throws SketchesArgumentException if the image is too small or its counts 
are invalid
+   */
+  static void checkQuickSelectImage(final MemorySegment seg) {
+    checkBounds(0, ENTRIES_START, seg.byteSize());
+    final int numValues = seg.get(JAVA_BYTE, NUM_VALUES_BYTE);
+    final int lgCurCapacity = seg.get(JAVA_BYTE, LG_CUR_CAPACITY_BYTE);
+    final int lgNomEntries = seg.get(JAVA_BYTE, LG_NOM_ENTRIES_BYTE);
+    //the table grows to at most twice the nominal entries, but is never 
smaller than the minimum table size
+    if ((numValues < 1) || (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: numValues: " + 
numValues
+          + ", lgNomEntries: " + lgNomEntries + ", lgCurrentCapacity: " + 
lgCurCapacity);
+    }
+    final long capacity = 1L << lgCurCapacity;
+    final int count = seg.get(JAVA_INT_UNALIGNED, RETAINED_ENTRIES_INT);
+    if ((count < 0) || (count > capacity)) {
+      throw new SketchesArgumentException("Possible corruption: invalid 
retained entries: " + count);
+    }
+    checkBounds(ENTRIES_START, capacity * (SIZE_OF_KEY_BYTES + ((long) 
SIZE_OF_VALUE_BYTES * numValues)),
+        seg.byteSize());
+  }
+
   // these can be derived from other things, but are kept here for performance
   int rebuildThreshold_; //absolute value relative to current capacity
   int lgCurrentCapacity_;
diff --git 
a/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/DirectArrayOfDoublesCompactSketch.java
 
b/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/DirectArrayOfDoublesCompactSketch.java
index e110a24fa..6342ba717 100644
--- 
a/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/DirectArrayOfDoublesCompactSketch.java
+++ 
b/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/DirectArrayOfDoublesCompactSketch.java
@@ -157,6 +157,7 @@ final class DirectArrayOfDoublesCompactSketch extends 
ArrayOfDoublesCompactSketc
    * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See 
seed</a>
    */
   DirectArrayOfDoublesCompactSketch(final MemorySegment seg, final long seed) {
+    checkCompactImage(seg);
     super(seg.get(JAVA_BYTE, NUM_VALUES_BYTE));
     seg_ = seg;
     SerializerDeserializer.validateFamily(seg.get(JAVA_BYTE, FAMILY_ID_BYTE),
diff --git 
a/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/DirectArrayOfDoublesQuickSelectSketch.java
 
b/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/DirectArrayOfDoublesQuickSelectSketch.java
index f32571d0b..1a7e6585f 100644
--- 
a/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/DirectArrayOfDoublesQuickSelectSketch.java
+++ 
b/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/DirectArrayOfDoublesQuickSelectSketch.java
@@ -126,6 +126,7 @@ class DirectArrayOfDoublesQuickSelectSketch extends 
ArrayOfDoublesQuickSelectSke
       final MemorySegment seg,
       final long seed) {
     checkSerVer(seg);
+    checkQuickSelectImage(seg);
     super(seg.get(JAVA_BYTE, NUM_VALUES_BYTE), seed);
     seg_ = seg;
     SerializerDeserializer.validateFamily(seg.get(JAVA_BYTE, FAMILY_ID_BYTE),
diff --git 
a/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/HeapArrayOfDoublesCompactSketch.java
 
b/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/HeapArrayOfDoublesCompactSketch.java
index 762324543..c52b34cb7 100644
--- 
a/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/HeapArrayOfDoublesCompactSketch.java
+++ 
b/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/HeapArrayOfDoublesCompactSketch.java
@@ -115,6 +115,7 @@ final class HeapArrayOfDoublesCompactSketch extends 
ArrayOfDoublesCompactSketch
    * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See 
seed</a>
    */
   HeapArrayOfDoublesCompactSketch(final MemorySegment seg, final long seed) {
+    checkCompactImage(seg);
     super(seg.get(JAVA_BYTE, NUM_VALUES_BYTE));
     seedHash_ = seg.get(JAVA_SHORT_UNALIGNED, SEED_HASH_SHORT);
     SerializerDeserializer.validateFamily(seg.get(JAVA_BYTE, FAMILY_ID_BYTE),
diff --git 
a/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/HeapArrayOfDoublesQuickSelectSketch.java
 
b/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/HeapArrayOfDoublesQuickSelectSketch.java
index 370d6cb44..4108201b2 100644
--- 
a/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/HeapArrayOfDoublesQuickSelectSketch.java
+++ 
b/src/main/java/org/apache/datasketches/tuple/arrayofdoubles/HeapArrayOfDoublesQuickSelectSketch.java
@@ -89,6 +89,7 @@ final class HeapArrayOfDoublesQuickSelectSketch extends 
ArrayOfDoublesQuickSelec
    * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See 
seed</a>
    */
   HeapArrayOfDoublesQuickSelectSketch(final MemorySegment seg, final long 
seed) {
+    checkQuickSelectImage(seg);
     super(seg.get(JAVA_BYTE, NUM_VALUES_BYTE), seed);
     SerializerDeserializer.validateFamily(seg.get(JAVA_BYTE, FAMILY_ID_BYTE),
         seg.get(JAVA_BYTE, PREAMBLE_LONGS_BYTE));
diff --git 
a/src/test/java/org/apache/datasketches/tuple/arrayofdoubles/AodCorruptImageTest.java
 
b/src/test/java/org/apache/datasketches/tuple/arrayofdoubles/AodCorruptImageTest.java
new file mode 100644
index 000000000..9dfa9b621
--- /dev/null
+++ 
b/src/test/java/org/apache/datasketches/tuple/arrayofdoubles/AodCorruptImageTest.java
@@ -0,0 +1,154 @@
+/*
+ * 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.arrayofdoubles;
+
+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 ArrayOfDoubles sketch and union images are rejected 
without large allocations,
+ * including when the result of a wrap is used later.
+ */
+public class AodCorruptImageTest {
+  private static final int NUM_VALUES_BYTE = 5;
+  private static final int COMPACT_COUNT_INT = 16;
+  private static final int QS_LG_NOM_BYTE = 16;
+  private static final int QS_LG_CUR_BYTE = 17;
+  private static final int QS_COUNT_INT = 24;
+  private static final int UNION_PREAMBLE = 16;
+
+  private static ArrayOfDoublesUpdatableSketch sketch(final int n) {
+    final ArrayOfDoublesUpdatableSketch sk = new 
ArrayOfDoublesUpdatableSketchBuilder().setNumberOfValues(2).build();
+    for (int i = 0; i < n; i++) { sk.update(i, new double[] {1.0, 2.0}); }
+    return sk;
+  }
+
+  private static byte[] unionImage() {
+    final ArrayOfDoublesUnion union = new 
ArrayOfDoublesSetOperationBuilder().setNumberOfValues(2).buildUnion();
+    union.union(sketch(10));
+    return union.toByteArray();
+  }
+
+  private static void checkRejected(final byte[] bytes, final 
Function<MemorySegment, Object> deser) {
+    final MemorySegment seg = MemorySegment.ofArray(bytes);
+    final long allocated = AllocationTracker.allocatedBytes(() -> 
deser.apply(seg));
+    assertTrue(allocated < (1 << 20), "allocated " + allocated);
+    expectThrows(SketchesArgumentException.class, () -> deser.apply(seg));
+  }
+
+  @Test
+  public void checkValidImagesStillWork() {
+    final ArrayOfDoublesUpdatableSketch sk = sketch(100);
+    final byte[] c = sk.compact().toByteArray();
+    
assertEquals(ArrayOfDoublesSketch.heapifySketch(MemorySegment.ofArray(c)).getRetainedEntries(),
 100);
+    
assertEquals(ArrayOfDoublesSketch.wrapSketch(MemorySegment.ofArray(c)).getRetainedEntries(),
 100);
+    final byte[] u = sk.toByteArray();
+    
assertEquals(ArrayOfDoublesSketch.heapifyUpdatableSketch(MemorySegment.ofArray(u)).getRetainedEntries(),
 100);
+    
assertEquals(ArrayOfDoublesSketch.wrapUpdatableSketch(MemorySegment.ofArray(u)).getRetainedEntries(),
 100);
+    
assertEquals(ArrayOfDoublesUnion.heapify(MemorySegment.ofArray(unionImage())).getResult().getRetainedEntries(),
 10);
+    
assertEquals(ArrayOfDoublesUnion.wrap(MemorySegment.ofArray(unionImage())).getResult().getRetainedEntries(),
 10);
+    final byte[] e = sketch(0).compact().toByteArray();
+    
assertTrue(ArrayOfDoublesSketch.heapifySketch(MemorySegment.ofArray(e)).isEmpty());
+  }
+
+  @Test
+  public void checkSmallNominalEntriesStillWork() {
+    //for nominal entries below 16 the table starts at the minimum size, which 
is more than twice nominal.
+    //The set operation builder, unlike the sketch builder, accepts nominal 
entries below 16.
+    for (final int k : new int[] {1, 2, 4, 8, 16, 32}) {
+      for (final int n : new int[] {0, 1, 3, 100}) {
+        final ArrayOfDoublesSetOperationBuilder bldr =
+            new 
ArrayOfDoublesSetOperationBuilder().setNominalEntries(k).setNumberOfValues(2);
+        final ArrayOfDoublesUnion heapUnion = bldr.buildUnion();
+        final ArrayOfDoublesUnion directUnion = 
bldr.buildUnion(MemorySegment.ofArray(new byte[1 << 16]));
+        heapUnion.union(sketch(n));
+        directUnion.union(sketch(n));
+        final int expected = heapUnion.getResult().getRetainedEntries();
+        for (final byte[] u : new byte[][] {heapUnion.toByteArray(), 
directUnion.toByteArray()}) {
+          
assertEquals(ArrayOfDoublesUnion.heapify(MemorySegment.ofArray(u)).getResult().getRetainedEntries(),
 expected);
+          
assertEquals(ArrayOfDoublesUnion.wrap(MemorySegment.ofArray(u)).getResult().getRetainedEntries(),
 expected);
+        }
+      }
+    }
+  }
+
+  @Test
+  public void checkCompactCountBeyondImage() {
+    final byte[] bytes = sketch(10).compact().toByteArray();
+    ByteArrayUtil.putIntLE(bytes, COMPACT_COUNT_INT, 1 << 26);
+    checkRejected(bytes, ArrayOfDoublesSketch::heapifySketch);
+    checkRejected(bytes, seg -> 
ArrayOfDoublesSketch.wrapSketch(seg).getValues());
+    final byte[] negative = sketch(10).compact().toByteArray();
+    ByteArrayUtil.putIntLE(negative, COMPACT_COUNT_INT, -1);
+    checkRejected(negative, ArrayOfDoublesSketch::heapifySketch);
+  }
+
+  @Test
+  public void checkCompactNumValues() {
+    final byte[] bytes = sketch(10).compact().toByteArray();
+    bytes[NUM_VALUES_BYTE] = (byte) 127; //more values than the image holds
+    checkRejected(bytes, ArrayOfDoublesSketch::heapifySketch);
+    bytes[NUM_VALUES_BYTE] = (byte) -1;
+    checkRejected(bytes, ArrayOfDoublesSketch::heapifySketch);
+    checkRejected(bytes, ArrayOfDoublesSketch::wrapSketch);
+  }
+
+  @Test
+  public void checkUpdatableLargeTable() {
+    final byte[] bytes = sketch(10).toByteArray();
+    bytes[QS_LG_NOM_BYTE] = 26;
+    bytes[QS_LG_CUR_BYTE] = 27; //the image does not hold this table
+    checkRejected(bytes, ArrayOfDoublesSketch::heapifyUpdatableSketch);
+    checkRejected(bytes, seg -> 
ArrayOfDoublesSketch.wrapUpdatableSketch(seg).getValues());
+    final byte[] bytes2 = sketch(10).toByteArray();
+    bytes2[QS_LG_CUR_BYTE] = (byte) (bytes2[QS_LG_NOM_BYTE] + 2);
+    checkRejected(bytes2, ArrayOfDoublesSketch::heapifyUpdatableSketch);
+  }
+
+  @Test
+  public void checkUpdatableCount() {
+    final byte[] bytes = sketch(10).toByteArray();
+    ByteArrayUtil.putIntLE(bytes, QS_COUNT_INT, 1 << 26); //more than the 
table holds
+    checkRejected(bytes, ArrayOfDoublesSketch::heapifyUpdatableSketch);
+    checkRejected(bytes, seg -> 
ArrayOfDoublesSketch.wrapUpdatableSketch(seg).getValues());
+  }
+
+  @Test
+  public void checkUnion() {
+    final byte[] bytes = unionImage();
+    bytes[UNION_PREAMBLE + QS_LG_NOM_BYTE] = 26;
+    bytes[UNION_PREAMBLE + QS_LG_CUR_BYTE] = 27;
+    checkRejected(bytes, ArrayOfDoublesUnion::heapify);
+    checkRejected(bytes, seg -> ArrayOfDoublesUnion.wrap(seg).getResult());
+    final byte[] bytes2 = unionImage();
+    ByteArrayUtil.putIntLE(bytes2, UNION_PREAMBLE + QS_COUNT_INT, 1 << 26);
+    checkRejected(bytes2, ArrayOfDoublesUnion::heapify);
+    checkRejected(bytes2, seg -> ArrayOfDoublesUnion.wrap(seg).getResult());
+  }
+}


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to