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]

Reply via email to