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 024dc74e051a6ad194687598d78bdeb6f347d7a7 Author: Lee Rhodes <[email protected]> AuthorDate: Thu Oct 29 15:03:00 2026 -0700 REQ: validate compactor fields - Check that k is even and in [4, 1024] before reading the compactors. - Check that 1 <= sectionSize <= k, numSections >= 1, and sectionSize * numSections <= k * k. Simulating the section growth rule for every legal k gives at most 0.96 * k * k. - Check that the count is non-negative and that the image holds the items. - Size each reconstructed buffer to the items it holds. The buffer grows by delta as needed, as it does after compaction. ReqCompactorTest compared the rebuilt buffer's capacity and backing array. It now compares the count, the sorted flag and the items. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- .../java/org/apache/datasketches/req/ReqSerDe.java | 25 ++++-- .../apache/datasketches/req/ReqCompactorTest.java | 18 ++-- .../datasketches/req/ReqCorruptImageTest.java | 96 ++++++++++++++++++++++ 3 files changed, 127 insertions(+), 12 deletions(-) diff --git a/src/main/java/org/apache/datasketches/req/ReqSerDe.java b/src/main/java/org/apache/datasketches/req/ReqSerDe.java index c1f038bdd..89a65e345 100644 --- a/src/main/java/org/apache/datasketches/req/ReqSerDe.java +++ b/src/main/java/org/apache/datasketches/req/ReqSerDe.java @@ -147,6 +147,10 @@ class ReqSerDe { final int k = posSeg.getShort() & 0xFFFF; final int numCompactors = posSeg.getByte() & 0xFF; final int numRawItems = posSeg.getByte() & 0xFF; + if (((k & 1) > 0) || (k < ReqSketch.MIN_K) || (k > 1024)) { + throw new SketchesArgumentException( + "Possible corruption: K must be even and in the range [4, 1024]: " + k); + } // extract different serialization formats final SerDeFormat deserFormat = getDeserFormat(empty, rawItems, numCompactors); switch (deserFormat) { @@ -162,7 +166,7 @@ class ReqSerDe { } case EXACT: { assert preInts == 2; - final Compactor compactor = extractCompactor(posSeg, lvl0Sorted, hra); + final Compactor compactor = extractCompactor(posSeg, k, lvl0Sorted, hra); checkLgWeight(compactor, 0); //Construct sketch final long totalN = compactor.count; @@ -184,7 +188,7 @@ class ReqSerDe { final List<ReqCompactor> compactors = new ArrayList<>(); for (int i = 0; i < numCompactors; i++) { final boolean level0sorted = i == 0 ? lvl0Sorted : true; - final Compactor compactor = extractCompactor(posSeg, level0sorted, hra); + final Compactor compactor = extractCompactor(posSeg, k, level0sorted, hra); checkLgWeight(compactor, i); compactors.add(compactor.reqCompactor); } @@ -206,7 +210,7 @@ class ReqSerDe { } } - static final Compactor extractCompactor(final PositionalSegment posSeg, final boolean lvl0Sorted, + static final Compactor extractCompactor(final PositionalSegment posSeg, final int k, final boolean lvl0Sorted, final boolean hra) { final long state = posSeg.getLong(); final float sectionSizeFlt = posSeg.getFloat(); @@ -215,6 +219,17 @@ class ReqSerDe { final byte numSections = posSeg.getByte(); posSeg.incrementPosition(2); final int count = posSeg.getInt(); + // The section size starts at k and only shrinks, and as the number of sections doubles the section size + // shrinks by sqrt(2) to no less than MIN_K, so sectionSize * numSections stays below k * k. + if ((sectionSize < 1) || (sectionSize > k) || (numSections < 1) + || (((long) sectionSize * numSections) > ((long) k * k))) { + throw new SketchesArgumentException("Possible corruption: sectionSize: " + sectionSize + + ", numSections: " + numSections + ", k: " + k); + } + if ((count < 0) || (((long) count * Float.BYTES) > posSeg.getRemaining())) { + throw new SketchesArgumentException("Possible corruption: compactor count " + count + + " does not fit in the remaining " + posSeg.getRemaining() + " bytes"); + } final float[] arr = new float[count]; posSeg.getFloatArray(arr, 0, count); float minItem = Float.POSITIVE_INFINITY; @@ -224,8 +239,8 @@ class ReqSerDe { maxItem = max(maxItem, arr[i]); } final int delta = 2 * sectionSize * numSections; - final int nomCap = 2 * delta; - final int cap = max(count, nomCap); + // The buffer grows as needed, so it only has to hold the items in the image. + final int cap = count; final FloatBuffer fltBuf = FloatBuffer.reconstruct(arr, count, cap, delta, lvl0Sorted, hra); final ReqCompactor reqCompactor = new ReqCompactor(lgWt, hra, state, sectionSizeFlt, numSections, fltBuf); diff --git a/src/test/java/org/apache/datasketches/req/ReqCompactorTest.java b/src/test/java/org/apache/datasketches/req/ReqCompactorTest.java index 95f35831a..59e874272 100644 --- a/src/test/java/org/apache/datasketches/req/ReqCompactorTest.java +++ b/src/test/java/org/apache/datasketches/req/ReqCompactorTest.java @@ -62,7 +62,6 @@ public class ReqCompactorTest { private static void checkSerDeImpl(final int k, final boolean hra) { final ReqCompactor c1 = new ReqCompactor((byte)0, hra, k, null); final int nomCap = 2 * 3 * k; - final int cap = 2 * nomCap; final int delta = nomCap; final FloatBuffer fbuf = c1.getBuffer(); @@ -81,7 +80,7 @@ public class ReqCompactorTest { final byte[] c1ser = c1.toByteArray(); //now deserialize final PositionalSegment posSeg = PositionalSegment.wrap(MemorySegment.ofArray(c1ser)); - final Compactor compactor = ReqSerDe.extractCompactor(posSeg, sorted, c1hra); + final Compactor compactor = ReqSerDe.extractCompactor(posSeg, k, sorted, c1hra); final ReqCompactor c2 = compactor.reqCompactor; assertEquals(compactor.minItem, minV); assertEquals(compactor.maxItem, maxV); @@ -93,9 +92,14 @@ public class ReqCompactorTest { assertEquals(c2.getLgWeight(), lgWeight); assertEquals(c2.isHighRankAccuracy(), c1hra); final FloatBuffer fbuf2 = c2.getBuffer(); - assertEquals(fbuf2.getCapacity(), cap); + //deserialization sizes the buffer to the items it holds; the buffer grows as needed + assertTrue(fbuf2.getCapacity() >= compactor.count); assertEquals(fbuf2.getDelta(), delta); - assertTrue(fbuf.isEqualTo(fbuf2)); + assertEquals(fbuf2.getCount(), fbuf.getCount()); + assertEquals(fbuf2.isSorted(), fbuf.isSorted()); + for (int i = 0; i < fbuf.getCount(); i++) { + assertEquals(fbuf2.getItem(i), fbuf.getItem(i)); + } } @Test @@ -114,7 +118,7 @@ public class ReqCompactorTest { } final byte[] c1ser = c1.toByteArray(); final PositionalSegment posSeg = PositionalSegment.wrap(MemorySegment.ofArray(c1ser)); - final Compactor compactor = ReqSerDe.extractCompactor(posSeg, fbuf.isSorted(), hra); + final Compactor compactor = ReqSerDe.extractCompactor(posSeg, k, fbuf.isSorted(), hra); assertEquals(compactor.minItem, -nomCap); assertEquals(compactor.maxItem, -1f); } @@ -136,7 +140,7 @@ public class ReqCompactorTest { } final byte[] c1ser = c1.toByteArray(); final PositionalSegment posSeg = PositionalSegment.wrap(MemorySegment.ofArray(c1ser)); - final Compactor compactor = ReqSerDe.extractCompactor(posSeg, fbuf.isSorted(), hra); + final Compactor compactor = ReqSerDe.extractCompactor(posSeg, k, fbuf.isSorted(), hra); assertEquals(compactor.minItem, (float) -half); assertEquals(compactor.maxItem, (float) (half - 1)); } @@ -158,7 +162,7 @@ public class ReqCompactorTest { final byte[] c1ser = c1.toByteArray(); final PositionalSegment posSeg = PositionalSegment.wrap(MemorySegment.ofArray(c1ser)); - final Compactor compactor = ReqSerDe.extractCompactor(posSeg, fbuf.isSorted(), hra); + final Compactor compactor = ReqSerDe.extractCompactor(posSeg, k, fbuf.isSorted(), hra); assertEquals(compactor.minItem, Float.NEGATIVE_INFINITY); assertEquals(compactor.maxItem, Float.POSITIVE_INFINITY); } diff --git a/src/test/java/org/apache/datasketches/req/ReqCorruptImageTest.java b/src/test/java/org/apache/datasketches/req/ReqCorruptImageTest.java new file mode 100644 index 000000000..c8f7ca939 --- /dev/null +++ b/src/test/java/org/apache/datasketches/req/ReqCorruptImageTest.java @@ -0,0 +1,96 @@ +/* + * 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.req; + +import static org.testng.Assert.assertEquals; +import static org.testng.Assert.assertTrue; +import static org.testng.Assert.expectThrows; + +import java.lang.foreign.MemorySegment; + +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 ReqSketch images are rejected without large allocations. + */ +public class ReqCorruptImageTest { + private static final int EST_SECTION_SIZE_FLOAT = 32; //first compactor, estimation mode + private static final int EST_NUM_SECTIONS_BYTE = 37; + private static final int EST_COUNT_INT = 40; + private static final int EXACT_COUNT_INT = 24; //the only compactor, exact mode + + private static byte[] image(final int n) { + final ReqSketch sk = ReqSketch.builder().setK(12).build(); + for (int i = 0; i < n; i++) { sk.update(i); } + return sk.toByteArray(); + } + + private static void checkRejected(final byte[] bytes) { + final long allocated = AllocationTracker.allocatedBytes(() -> ReqSketch.heapify(MemorySegment.ofArray(bytes))); + assertTrue(allocated < (1 << 20), "allocated " + allocated); + expectThrows(SketchesArgumentException.class, () -> ReqSketch.heapify(MemorySegment.ofArray(bytes))); + } + + @Test + public void checkValidImagesStillWork() { + for (final int n : new int[] {0, 5, 50, 10_000, 1_000_000}) { + final ReqSketch sk = ReqSketch.heapify(MemorySegment.ofArray(image(n))); + assertEquals(sk.getN(), n); + if (n > 0) { + sk.update(-1f); //the reconstructed buffers grow as needed + assertEquals(sk.getN(), n + 1); + } + } + } + + @Test + public void checkCountBeyondImage() { + final byte[] est = image(10_000); + ByteArrayUtil.putIntLE(est, EST_COUNT_INT, 1 << 28); + checkRejected(est); + final byte[] exact = image(50); + ByteArrayUtil.putIntLE(exact, EXACT_COUNT_INT, 1 << 28); + checkRejected(exact); + } + + @Test + public void checkSectionsTooLarge() { + final byte[] size = image(10_000); + ByteArrayUtil.putFloatLE(size, EST_SECTION_SIZE_FLOAT, 1e8f); + checkRejected(size); + final byte[] sections = image(10_000); + sections[EST_NUM_SECTIONS_BYTE] = 127; + ByteArrayUtil.putFloatLE(sections, EST_SECTION_SIZE_FLOAT, 12f); + checkRejected(sections); + final byte[] negative = image(10_000); + negative[EST_NUM_SECTIONS_BYTE] = -1; + checkRejected(negative); + } + + @Test + public void checkInvalidK() { + final byte[] bytes = image(10_000); + ByteArrayUtil.putShortLE(bytes, 4, (short) 60_000); + checkRejected(bytes); + } +} --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
