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 f8f41cd283ffba8e6aba2d10ddb2cdcb51fc8da0 Author: Lee Rhodes <[email protected]> AuthorDate: Thu Oct 29 14:51:24 2026 -0700 HLL: check lgK and declared sizes checkPreamble(), which heapify, wrap, writableWrap and HllUnion.heapify all call, now also checks: - that lgK is in its documented range of [4, 21]; - that a list count is no more than the list capacity; - that a set count is between 0 and K and set lgArr is at most lgK; - that an aux count is between 0 and K and aux lgArr is at most lgK. writableWrap() now validates the preamble before using lgK. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- .../org/apache/datasketches/hll/HllSketch.java | 2 +- .../java/org/apache/datasketches/hll/HllUtil.java | 36 +++++++ .../datasketches/hll/HllCorruptImageTest.java | 114 +++++++++++++++++++++ 3 files changed, 151 insertions(+), 1 deletion(-) diff --git a/src/main/java/org/apache/datasketches/hll/HllSketch.java b/src/main/java/org/apache/datasketches/hll/HllSketch.java index b1e958651..b49474464 100644 --- a/src/main/java/org/apache/datasketches/hll/HllSketch.java +++ b/src/main/java/org/apache/datasketches/hll/HllSketch.java @@ -254,12 +254,12 @@ public class HllSketch extends BaseHllSketch { "Cannot perform a writableWrap of a sketch image that is in compact form. " + "Compact sketches are by definition immutable."); } + final CurMode curMode = checkPreamble(srcWseg); //checks lgK before it is used final int lgConfigK = extractLgK(srcWseg); final TgtHllType tgtHllType = extractTgtHllType(srcWseg); final long minBytes = getMaxUpdatableSerializationBytes(lgConfigK, tgtHllType); final long capBytes = srcWseg.byteSize(); HllUtil.checkSegSize(minBytes, capBytes); - final CurMode curMode = checkPreamble(srcWseg); final HllSketch directSketch; if (curMode == CurMode.HLL) { if (tgtHllType == TgtHllType.HLL_4) { diff --git a/src/main/java/org/apache/datasketches/hll/HllUtil.java b/src/main/java/org/apache/datasketches/hll/HllUtil.java index b87b4e2d2..721382200 100644 --- a/src/main/java/org/apache/datasketches/hll/HllUtil.java +++ b/src/main/java/org/apache/datasketches/hll/HllUtil.java @@ -23,8 +23,13 @@ import static org.apache.datasketches.common.Util.checkBounds; import static org.apache.datasketches.hll.PreambleUtil.HASH_SET_PREINTS; import static org.apache.datasketches.hll.PreambleUtil.HLL_PREINTS; import static org.apache.datasketches.hll.PreambleUtil.LIST_PREINTS; +import static org.apache.datasketches.hll.PreambleUtil.extractAuxCount; import static org.apache.datasketches.hll.PreambleUtil.extractCurMode; import static org.apache.datasketches.hll.PreambleUtil.extractFamilyId; +import static org.apache.datasketches.hll.PreambleUtil.extractHashSetCount; +import static org.apache.datasketches.hll.PreambleUtil.extractLgArr; +import static org.apache.datasketches.hll.PreambleUtil.extractLgK; +import static org.apache.datasketches.hll.PreambleUtil.extractListCount; import static org.apache.datasketches.hll.PreambleUtil.extractPreInts; import static org.apache.datasketches.hll.PreambleUtil.extractSerVer; @@ -111,9 +116,40 @@ final class HllUtil { throw new SketchesArgumentException("Possible Corruption, Invalid Preamble:" + PreambleUtil.toString(seg)); } + checkSizes(seg, curMode); return curMode; } + /** + * Checks lgK and the sizes declared by the image. + * LgK must be in the documented range. The coupon hash set and the auxiliary (exception) hash map + * are never larger than K, and a coupon list never holds more than its initial capacity. + * @param seg the image + * @param curMode the current mode of the image + */ + private static void checkSizes(final MemorySegment seg, final CurMode curMode) { + final int lgK = extractLgK(seg); + checkLgK(lgK); + if (curMode == CurMode.LIST) { + final int count = extractListCount(seg); + if (count > (1 << LG_INIT_LIST_SIZE)) { + throw new SketchesArgumentException("Possible Corruption: list count " + count); + } + } else if (curMode == CurMode.SET) { + final int count = extractHashSetCount(seg); + final int lgArr = extractLgArr(seg); + if ((count < 0) || (count > (1 << lgK)) || (lgArr > lgK)) { + throw new SketchesArgumentException("Possible Corruption: set count " + count + ", lgArr " + lgArr); + } + } else { //HLL + final int auxCount = extractAuxCount(seg); + final int lgArr = extractLgArr(seg); + if ((auxCount < 0) || (auxCount > (1 << lgK)) || ((auxCount > 0) && (lgArr > lgK))) { + throw new SketchesArgumentException("Possible Corruption: aux count " + auxCount + ", lgArr " + lgArr); + } + } + } + //Exceptions static void noWriteAccess() { throw new SketchesReadOnlyException( diff --git a/src/test/java/org/apache/datasketches/hll/HllCorruptImageTest.java b/src/test/java/org/apache/datasketches/hll/HllCorruptImageTest.java new file mode 100644 index 000000000..6f32b3d8f --- /dev/null +++ b/src/test/java/org/apache/datasketches/hll/HllCorruptImageTest.java @@ -0,0 +1,114 @@ +/* + * 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.hll; + +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 HLL images are rejected without large allocations. + */ +public class HllCorruptImageTest { + private static final int LG_K_BYTE = 3; + private static final int LG_ARR_BYTE = 4; + private static final int LIST_COUNT_BYTE = 6; + private static final int HASH_SET_COUNT_INT = 8; + private static final int AUX_COUNT_INT = 36; + + private static HllSketch sketch(final TgtHllType type, final int n) { + final HllSketch sk = new HllSketch(12, type); + 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))); + } + + private static void checkAllPaths(final byte[] bytes) { + checkRejected(bytes, HllSketch::heapify); + checkRejected(bytes, HllSketch::wrap); + checkRejected(bytes, HllSketch::writableWrap); + checkRejected(bytes, HllUnion::heapify); + } + + @Test + public void checkValidImagesStillWork() { + for (final TgtHllType type : TgtHllType.values()) { + for (final int n : new int[] {0, 5, 200, 10_000}) { + final HllSketch sk = sketch(type, n); + for (final byte[] b : new byte[][] {sk.toCompactByteArray(), sk.toUpdatableByteArray()}) { + assertEquals(HllSketch.heapify(MemorySegment.ofArray(b)).getEstimate(), sk.getEstimate()); + assertEquals(HllSketch.wrap(MemorySegment.ofArray(b)).getEstimate(), sk.getEstimate()); + } + } + } + } + + @Test + public void checkLgKTooLarge() { + for (final TgtHllType type : TgtHllType.values()) { + for (final int n : new int[] {5, 200, 10_000}) { //list, set and HLL modes + final byte[] bytes = sketch(type, n).toUpdatableByteArray(); + bytes[LG_K_BYTE] = 30; + checkAllPaths(bytes); + } + } + } + + @Test + public void checkListCount() { + final byte[] bytes = sketch(TgtHllType.HLL_8, 5).toUpdatableByteArray(); + bytes[LIST_COUNT_BYTE] = (byte) 200; + checkAllPaths(bytes); + } + + @Test + public void checkSetSizes() { + final byte[] lgArr = sketch(TgtHllType.HLL_8, 200).toUpdatableByteArray(); + lgArr[LG_ARR_BYTE] = 28; + checkAllPaths(lgArr); + final byte[] count = sketch(TgtHllType.HLL_8, 200).toCompactByteArray(); + ByteArrayUtil.putIntLE(count, HASH_SET_COUNT_INT, 1 << 28); + checkAllPaths(count); + } + + @Test + public void checkAuxSizes() { + final byte[] bytes = sketch(TgtHllType.HLL_4, 10_000).toUpdatableByteArray(); + ByteArrayUtil.putIntLE(bytes, AUX_COUNT_INT, 1 << 28); + checkAllPaths(bytes); + final byte[] lgArr = sketch(TgtHllType.HLL_4, 10_000).toUpdatableByteArray(); + if (ByteArrayUtil.getIntLE(lgArr, AUX_COUNT_INT) == 0) { ByteArrayUtil.putIntLE(lgArr, AUX_COUNT_INT, 1); } + lgArr[LG_ARR_BYTE] = 28; + checkAllPaths(lgArr); + } +} --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
