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]
