Merge pull request #799 from apache/hll-set-hardening HLL: harden checks of coupon hash set images; document stringArrHash
diff --git a/src/main/java/org/apache/datasketches/hll/DirectCouponList.java b/src/main/java/org/apache/datasketches/hll/DirectCouponList.java index 90a19a6..aa09b72 100644 --- a/src/main/java/org/apache/datasketches/hll/DirectCouponList.java +++ b/src/main/java/org/apache/datasketches/hll/DirectCouponList.java
@@ -238,7 +238,7 @@ final MemorySegment wseg = src.wseg; //get the data from the current MemorySegment - HllUtil.checkPreamble(wseg); //sanity check + HllUtil.checkPreamble(wseg, false); //sanity check, mid-promotion final int lgConfigK = src.lgConfigK; final TgtHllType tgtHllType = src.tgtHllType; final int srcOffset = LIST_INT_ARR_START; @@ -273,7 +273,7 @@ final MemorySegment wseg = src.wseg; //get the data from the current list or set MemorySegment - HllUtil.checkPreamble(wseg); //sanity check + HllUtil.checkPreamble(wseg, false); //sanity check, mid-promotion final int lgConfigK = src.lgConfigK; final TgtHllType tgtHllType = src.tgtHllType; final int srcSegDataStart = src.getSegDataStart();
diff --git a/src/main/java/org/apache/datasketches/hll/HllUtil.java b/src/main/java/org/apache/datasketches/hll/HllUtil.java index 7213822..1ac603e 100644 --- a/src/main/java/org/apache/datasketches/hll/HllUtil.java +++ b/src/main/java/org/apache/datasketches/hll/HllUtil.java
@@ -20,13 +20,17 @@ package org.apache.datasketches.hll; import static org.apache.datasketches.common.Util.checkBounds; +import static org.apache.datasketches.hll.PreambleUtil.HASH_SET_INT_ARR_START; 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.computeLgArr; import static org.apache.datasketches.hll.PreambleUtil.extractAuxCount; +import static org.apache.datasketches.hll.PreambleUtil.extractCompactFlag; 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.extractInt; import static org.apache.datasketches.hll.PreambleUtil.extractLgArr; import static org.apache.datasketches.hll.PreambleUtil.extractLgK; import static org.apache.datasketches.hll.PreambleUtil.extractListCount; @@ -99,6 +103,17 @@ } static CurMode checkPreamble(final MemorySegment seg) { + return checkPreamble(seg, true); + } + + /** + * Checks the preamble of an image. + * @param seg the image + * @param checkSetLimits true for an image from outside. False only for the sketch's own segment + * while it is being promoted, when a coupon list or set is one coupon past its limit. + * @return the current mode of the image + */ + static CurMode checkPreamble(final MemorySegment seg, final boolean checkSetLimits) { checkBounds(0, 8, seg.byteSize()); //need min 8 bytes final int preInts = extractPreInts(seg); checkBounds(0, (long)preInts * Integer.BYTES, seg.byteSize()); @@ -116,7 +131,7 @@ throw new SketchesArgumentException("Possible Corruption, Invalid Preamble:" + PreambleUtil.toString(seg)); } - checkSizes(seg, curMode); + checkSizes(seg, curMode, checkSetLimits); return curMode; } @@ -126,8 +141,10 @@ * 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 + * @param checkSetLimits if true, also check a coupon hash set image with checkSet() */ - private static void checkSizes(final MemorySegment seg, final CurMode curMode) { + private static void checkSizes(final MemorySegment seg, final CurMode curMode, + final boolean checkSetLimits) { final int lgK = extractLgK(seg); checkLgK(lgK); if (curMode == CurMode.LIST) { @@ -141,6 +158,7 @@ if ((count < 0) || (count > (1 << lgK)) || (lgArr > lgK)) { throw new SketchesArgumentException("Possible Corruption: set count " + count + ", lgArr " + lgArr); } + if (checkSetLimits) { checkSet(seg, lgK, count, lgArr); } } else { //HLL final int auxCount = extractAuxCount(seg); final int lgArr = extractLgArr(seg); @@ -150,6 +168,48 @@ } } + /** + * Checks a coupon hash set image against the limits a valid sketch keeps. + * A sketch uses a hash set only when lgK is at least 8. The table starts at 2^LG_INIT_SET_SIZE + * ints, grows up to 2^(lgK - 3) ints, and is never more than 3/4 full; the sketch is promoted to + * HLL mode before that would be exceeded. In an updatable image the count must equal the number + * of non-empty slots in the table. + * @param seg the image + * @param lgK the checked lgK of the image + * @param count the coupon count of the image, already checked to be in [0, K] + * @param lgArr the lgArr field of the image, already checked to be at most lgK + */ + private static void checkSet(final MemorySegment seg, final int lgK, final int count, final int lgArr) { + if (lgK < (LG_INIT_SET_SIZE + 3)) { + throw new SketchesArgumentException("Possible Corruption: set mode with lgK " + lgK); + } + final int maxLgArr = lgK - 3; + if (extractCompactFlag(seg)) { + if ((RESIZE_DENOM * (long) count) > (RESIZE_NUMER * (1L << maxLgArr))) { + throw new SketchesArgumentException("Possible Corruption: set count " + count + " for lgK " + lgK); + } + checkBounds(0, HASH_SET_INT_ARR_START + ((long) count << 2), seg.byteSize()); + return; + } + //updatable: early images may not have the lgArr field, then it is computed from the count + final int effLgArr = (lgArr < LG_INIT_SET_SIZE) ? computeLgArr(seg, count, lgK) : lgArr; + if ((effLgArr < LG_INIT_SET_SIZE) || (effLgArr > maxLgArr) + || ((RESIZE_DENOM * (long) count) > (RESIZE_NUMER * (1L << effLgArr)))) { + throw new SketchesArgumentException("Possible Corruption: set count " + count + ", lgArr " + effLgArr + + " for lgK " + lgK); + } + final int arrInts = 1 << effLgArr; + checkBounds(0, HASH_SET_INT_ARR_START + ((long) arrInts << 2), seg.byteSize()); + int nonEmpty = 0; + for (int i = 0; i < arrInts; i++) { + if (extractInt(seg, HASH_SET_INT_ARR_START + (i << 2)) != EMPTY) { nonEmpty++; } + } + if (nonEmpty != count) { + throw new SketchesArgumentException("Possible Corruption: set count " + count + ", non-empty slots " + + nonEmpty); + } + } + //Exceptions static void noWriteAccess() { throw new SketchesReadOnlyException(
diff --git a/src/main/java/org/apache/datasketches/tuple/Util.java b/src/main/java/org/apache/datasketches/tuple/Util.java index 6051c94..5804b1c 100644 --- a/src/main/java/org/apache/datasketches/tuple/Util.java +++ b/src/main/java/org/apache/datasketches/tuple/Util.java
@@ -130,7 +130,19 @@ } /** - * Returns the hash of the concatenated strings + * Returns the hash of the concatenated strings. + * + * <p>This is the key hash used by the Array of Strings tuple sketch. Another implementation + * must compute it exactly as follows to produce the same keys:</p> + * <ul> + * <li>The elements are joined with a single comma (",") between them, as by + * {@link #stringConcat(String[])}. Nothing is escaped, so {"a,b"} and {"a", "b"} produce the same + * string and the same hash. A <i>null</i> element contributes the four characters "null".</li> + * <li>The joined string is hashed as its UTF-16 code units in little-endian byte order + * (UTF-16LE), with no byte-order mark. It is not encoded as UTF-8.</li> + * <li>The hash function is XXH64 with the seed 0x7A3CCA71.</li> + * </ul> + * * @param strArray array of Strings * @return the hash of concatenated strings. */
diff --git a/src/test/java/org/apache/datasketches/hll/HllCorruptImageTest.java b/src/test/java/org/apache/datasketches/hll/HllCorruptImageTest.java index 6f32b3d..cb8970e 100644 --- a/src/test/java/org/apache/datasketches/hll/HllCorruptImageTest.java +++ b/src/test/java/org/apache/datasketches/hll/HllCorruptImageTest.java
@@ -40,6 +40,7 @@ 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 final int SET_ARR_START = 12; private static HllSketch sketch(final TgtHllType type, final int n) { final HllSketch sk = new HllSketch(12, type); @@ -111,4 +112,98 @@ lgArr[LG_ARR_BYTE] = 28; checkAllPaths(lgArr); } + + //lgK 12: the set table grows to at most 2^9 ints and holds at most 3/4 of that, 384 coupons + private static final int MAX_SET_LG_ARR = 9; + private static final int MAX_SET_COUNT = 384; + + private static byte[] setImage(final boolean compact) { + final HllSketch sk = sketch(TgtHllType.HLL_8, 200); + assertEquals(sk.getCurMode(), CurMode.SET); + return compact ? sk.toCompactByteArray() : sk.toUpdatableByteArray(); + } + + @Test + public void checkValidSetImagesAcrossLgK() { + for (int lgK = 8; lgK <= 14; lgK++) { + final int maxCount = (3 << (lgK - 3)) / 4; + for (final int n : new int[] {9, maxCount / 2, maxCount}) { + final HllSketch heap = new HllSketch(lgK, TgtHllType.HLL_8); + final MemorySegment wseg = MemorySegment.ofArray( + new byte[HllSketch.getMaxUpdatableSerializationBytes(lgK, TgtHllType.HLL_8)]); + final HllSketch direct = new HllSketch(lgK, TgtHllType.HLL_8, wseg); + for (int i = 0; i < n; i++) { heap.update(i); direct.update(i); } + for (final HllSketch sk : new HllSketch[] {heap, direct}) { + if (sk.getCurMode() != CurMode.SET) { continue; } //a few hash collisions can leave it a list + 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()); + } + final byte[] upd = sk.toUpdatableByteArray(); + final byte[] full = new byte[HllSketch.getMaxUpdatableSerializationBytes(lgK, TgtHllType.HLL_8)]; + System.arraycopy(upd, 0, full, 0, upd.length); + assertEquals(HllSketch.writableWrap(MemorySegment.ofArray(full)).getEstimate(), sk.getEstimate()); + } + } + } + } + + @Test + public void checkCompactSetCountAboveLimit() { + final byte[] image = setImage(true); + final byte[] bytes = new byte[image.length + (4 * MAX_SET_COUNT)]; //room for the declared coupons + System.arraycopy(image, 0, bytes, 0, image.length); + ByteArrayUtil.putIntLE(bytes, HASH_SET_COUNT_INT, MAX_SET_COUNT + 1); + checkAllPaths(bytes); + } + + @Test + public void checkCompactSetTruncated() { + final byte[] image = setImage(true); + final byte[] bytes = new byte[image.length - 4]; + System.arraycopy(image, 0, bytes, 0, bytes.length); + checkAllPaths(bytes); + } + + @Test + public void checkUpdatableSetLgArrRange() { + for (final int lgArr : new int[] {MAX_SET_LG_ARR + 1, 12}) { + final byte[] image = setImage(false); + final byte[] bytes = new byte[image.length + (4 << lgArr)]; //room for the declared table + System.arraycopy(image, 0, bytes, 0, image.length); + bytes[LG_ARR_BYTE] = (byte) lgArr; + checkAllPaths(bytes); + } + } + + @Test + public void checkUpdatableSetCountMatchesSlots() { + for (final int delta : new int[] {-1, 1, 100}) { + final byte[] bytes = setImage(false); + ByteArrayUtil.putIntLE(bytes, HASH_SET_COUNT_INT, ByteArrayUtil.getIntLE(bytes, HASH_SET_COUNT_INT) + delta); + checkAllPaths(bytes); + } + } + + @Test + public void checkUpdatableSetOverfull() { + //every slot filled and the count to match: valid writers grow or promote long before this + final byte[] bytes = setImage(false); + final int arrInts = 1 << bytes[LG_ARR_BYTE]; + for (int i = 0; i < arrInts; i++) { ByteArrayUtil.putIntLE(bytes, SET_ARR_START + (4 * i), i + 1); } + ByteArrayUtil.putIntLE(bytes, HASH_SET_COUNT_INT, arrInts); + checkAllPaths(bytes); + } + + @Test + public void checkSetModeNeedsLgK8() { + final HllSketch sk = new HllSketch(8, TgtHllType.HLL_8); + for (int i = 0; i < 20; i++) { sk.update(i); } + assertEquals(sk.getCurMode(), CurMode.SET); //table of 2^5 ints, the only size lgK 8 allows + for (final boolean compact : new boolean[] {true, false}) { + final byte[] bytes = compact ? sk.toCompactByteArray() : sk.toUpdatableByteArray(); + bytes[LG_K_BYTE] = 7; + checkAllPaths(bytes); + } + } }
diff --git a/src/test/java/org/apache/datasketches/tuple/StringArrHashTest.java b/src/test/java/org/apache/datasketches/tuple/StringArrHashTest.java new file mode 100644 index 0000000..a0e913f --- /dev/null +++ b/src/test/java/org/apache/datasketches/tuple/StringArrHashTest.java
@@ -0,0 +1,60 @@ +/* + * 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 java.nio.charset.StandardCharsets.UTF_16LE; +import static org.testng.Assert.assertEquals; + +import org.apache.datasketches.hash.XxHash64; +import org.testng.annotations.Test; + +/** + * Checks the key hash of the Array of Strings tuple sketch against the definition in the javadoc of + * {@link Util#stringArrHash(String[])}. + */ +public class StringArrHashTest { + private static final long SEED = 0x7A3CCA71L; + + private static long expected(final String joined) { + final byte[] bytes = joined.getBytes(UTF_16LE); // no byte-order mark + return XxHash64.hashBytes(bytes, 0, bytes.length, SEED); + } + + @Test + public void hashesCommaJoinedUtf16LittleEndian() { + assertEquals(Util.stringArrHash(new String[] { "a" }), expected("a")); + assertEquals(Util.stringArrHash(new String[] { "a", "b", "c" }), expected("a,b,c")); + assertEquals(Util.stringArrHash(new String[] { "" }), expected("")); + assertEquals(Util.stringArrHash(new String[] { }), expected("")); + assertEquals(Util.stringArrHash(new String[] { "é", "日本", "😀" }), + expected("é,日本,😀")); + } + + @Test + public void commasAreNotEscaped() { + assertEquals(Util.stringArrHash(new String[] { "a,b" }), Util.stringArrHash(new String[] { "a", "b" })); + } + + @Test + public void nullElementIsHashedAsTheWordNull() { + assertEquals(Util.stringArrHash(new String[] { "a", null }), expected("a,null")); + } +}