Skip to content

Commit 647198f

Browse files
committed
Tighten ALP vector offset validation
Check the first offset before allocating the offset array, and end the array with an entry for the end of the vector data, so every vector, including the last, is checked for both a minimum and a maximum span. The maximum allows every value packed at full width and also stored as an exception. The vector data size is captured once when the page is sliced, so nothing reads the buffer's limit afterwards, and an out-of-range vector index is now an IllegalArgumentException. Packed values are bounds-checked before unpacking rather than after, which also covers the last vector running past the end of the page.
1 parent 2a9a23f commit 647198f

3 files changed

Lines changed: 191 additions & 49 deletions

File tree

‎parquet-column/src/main/java/org/apache/parquet/column/values/alp/AlpValuesReader.java‎

Lines changed: 73 additions & 45 deletions
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,7 @@
2929
import java.nio.ByteBuffer;
3030
import java.nio.ByteOrder;
3131
import org.apache.parquet.bytes.ByteBufferInputStream;
32+
import org.apache.parquet.bytes.BytesUtils;
3233
import org.apache.parquet.column.values.ValuesReader;
3334
import org.apache.parquet.io.ParquetDecodingException;
3435

@@ -54,8 +55,12 @@ abstract class AlpValuesReader extends ValuesReader {
5455
protected int pageValueIndex;
5556
protected int currentVectorIndex;
5657

58+
// One entry per vector plus a trailing entry for the end of the vector data, so the entry after
59+
// any vector's offset is always where that vector ends.
5760
protected int[] vectorOffsets;
5861
protected ByteBuffer vectorsData;
62+
// Captured once when the page is sliced, so nothing later depends on the buffer's position/limit.
63+
protected int vectorDataSize;
5964
protected int offsetArraySize;
6065

6166
// Scratch buffer for exception positions within a vector; shared by both readers (int[] in each).
@@ -86,7 +91,11 @@ public void initFromPage(int valuesCount, ByteBufferInputStream stream)
8691
int minVectorBytes = ALP_INFO_SIZE + forInfoSize();
8792
readOffsetArray(stream, minVectorBytes);
8893
sliceVectorData(stream);
89-
validateVectorOffsets(minVectorBytes);
94+
// The trailing entry is filled here rather than in readOffsetArray because the vector data
95+
// size is only known once the data has been sliced.
96+
vectorOffsets[numVectors] = offsetArraySize + vectorDataSize;
97+
validateVectorOffsets(
98+
vectorOffsets, minVectorBytes, maxVectorBytes(valuesPerVector, minVectorBytes, exceptionValueSize()));
9099

91100
allocateDecodedBuffer(valuesPerVector);
92101
this.excPositionsBuffer = new int[valuesPerVector];
@@ -134,7 +143,10 @@ private void readPageHeader(ByteBufferInputStream stream, int valuesCount) throw
134143
this.currentVectorIndex = -1;
135144
}
136145

137-
/** Reads the offset array, one entry per vector, after bounding the vector count. */
146+
/**
147+
* Reads the offset array, one entry per vector, after bounding the vector count and checking the
148+
* first offset. Leaves room for the trailing end-of-data entry, which the caller fills in.
149+
*/
138150
private void readOffsetArray(ByteBufferInputStream stream, int minVectorBytes) throws IOException {
139151
// Bound the vector count against the bytes actually present before allocating anything.
140152
// numElements is only capped by valuesCount, which a forged page can set as high as
@@ -154,8 +166,20 @@ private void readOffsetArray(ByteBufferInputStream stream, int minVectorBytes) t
154166

155167
this.offsetArraySize = numVectors * Integer.BYTES;
156168
ByteBuffer offsetBuf = stream.slice(offsetArraySize).order(ByteOrder.LITTLE_ENDIAN);
157-
this.vectorOffsets = new int[numVectors];
158-
for (int v = 0; v < numVectors; v++) {
169+
if (numVectors == 0) {
170+
this.vectorOffsets = new int[1];
171+
return;
172+
}
173+
// Offsets are measured from the start of the offset array, so the first vector must begin
174+
// exactly where the array ends. Check that before allocating and decoding the rest.
175+
int firstOffset = offsetBuf.getInt();
176+
if (firstOffset != offsetArraySize) {
177+
throw new ParquetDecodingException(
178+
"ALP first vector offset " + firstOffset + " must equal the offset array size " + offsetArraySize);
179+
}
180+
this.vectorOffsets = new int[numVectors + 1];
181+
vectorOffsets[0] = firstOffset;
182+
for (int v = 1; v < numVectors; v++) {
159183
vectorOffsets[v] = offsetBuf.getInt();
160184
}
161185
}
@@ -165,48 +189,56 @@ private void readOffsetArray(ByteBufferInputStream stream, int minVectorBytes) t
165189
* absolute {@code get(pos)} reads.
166190
*/
167191
private void sliceVectorData(ByteBufferInputStream stream) throws IOException {
168-
int remainingBytes = (int) stream.available();
169-
ByteBuffer rawSlice = stream.slice(remainingBytes);
192+
this.vectorDataSize = (int) stream.available();
193+
ByteBuffer rawSlice = stream.slice(vectorDataSize);
170194
this.vectorsData = rawSlice.slice().order(ByteOrder.LITTLE_ENDIAN);
171195
}
172196

173197
/**
174-
* Validates the offset array against the page body before any vector is decoded. Offsets are
175-
* relative to the start of the compression body (the offset array itself), so the first vector
176-
* must begin exactly where the offset array ends, offsets must increase by at least one vector's
177-
* fixed headers, and every vector must start early enough to fit those headers. Without this a
178-
* forged offset can point into another vector and silently decode the wrong values.
198+
* Validates the offset array before any vector is decoded. {@code vectorOffsets} holds one entry
199+
* per vector followed by the end of the vector data, all measured from the start of the offset
200+
* array. The first entry is checked when the array is read, so this starts at entry 1: each
201+
* vector, including the last, must span at least its fixed headers and no more than
202+
* {@code maxVectorBytes}. Without this a forged offset can point into another vector and
203+
* silently decode the wrong values.
179204
*/
180-
private void validateVectorOffsets(int minVectorBytes) {
181-
int bodyLimit = offsetArraySize + vectorsData.limit();
182-
for (int v = 0; v < numVectors; v++) {
183-
int offset = vectorOffsets[v];
184-
if (v == 0) {
185-
if (offset != offsetArraySize) {
186-
throw new ParquetDecodingException("ALP first vector offset " + offset
187-
+ " must equal the offset array size " + offsetArraySize);
188-
}
189-
} else if ((long) offset - vectorOffsets[v - 1] < minVectorBytes) {
190-
throw new ParquetDecodingException("ALP vector offsets must increase by at least "
191-
+ minVectorBytes + " bytes, but vector " + v + " starts at " + offset + " after vector "
192-
+ (v - 1) + " at " + vectorOffsets[v - 1]);
205+
static void validateVectorOffsets(int[] vectorOffsets, int minVectorBytes, int maxVectorBytes) {
206+
int numVectors = vectorOffsets.length - 1;
207+
for (int v = 1; v <= numVectors; v++) {
208+
long span = (long) vectorOffsets[v] - vectorOffsets[v - 1];
209+
if (span < minVectorBytes) {
210+
throw new ParquetDecodingException("ALP vector " + (v - 1) + " at offset " + vectorOffsets[v - 1]
211+
+ " spans " + span + " bytes, fewer than the " + minVectorBytes + " its headers need");
193212
}
194-
if (offset > bodyLimit - minVectorBytes) {
195-
throw new ParquetDecodingException("ALP vector " + v + " offset " + offset
196-
+ " leaves no room for its headers before the end of the page body at " + bodyLimit);
213+
if (span > maxVectorBytes) {
214+
throw new ParquetDecodingException("ALP vector " + (v - 1) + " at offset " + vectorOffsets[v - 1]
215+
+ " spans " + span + " bytes, more than the " + maxVectorBytes + " any vector can occupy");
197216
}
198217
}
199218
}
200219

201220
/**
202-
* The position just past the last byte vector {@code vectorIndex} may read, derived from the
203-
* next vector's offset (or the end of the body for the final vector).
221+
* The most bytes one vector can occupy: its fixed headers, every value bit-packed at the full
222+
* width of the type, and every value also stored as an exception. Vector sizes are multiples of
223+
* the 8-value packing group, so the packed section needs no padding allowance.
224+
*/
225+
static int maxVectorBytes(int valuesPerVector, int minVectorBytes, int valueSize) {
226+
int packed = valuesPerVector * valueSize;
227+
int exceptions = valuesPerVector * (Short.BYTES + valueSize);
228+
return minVectorBytes + packed + exceptions;
229+
}
230+
231+
/**
232+
* The position in the vector data just past the last byte vector {@code vectorIndex} may read,
233+
* taken from the next entry of the offset array; the trailing entry makes this valid for the last
234+
* vector too.
204235
*/
205-
private int getVectorEndPosition(int vectorIndex) {
206-
if (!isLast(vectorIndex, numVectors)) {
207-
return vectorOffsets[vectorIndex + 1] - offsetArraySize;
236+
int getVectorEndPosition(int vectorIndex) {
237+
if (vectorIndex < 0 || vectorIndex >= numVectors) {
238+
throw new IllegalArgumentException(
239+
"ALP vector index " + vectorIndex + " is out of range for " + numVectors + " vectors");
208240
}
209-
return vectorsData.limit();
241+
return vectorOffsets[vectorIndex + 1] - offsetArraySize;
210242
}
211243

212244
// Offsets in the page are relative to the compression body (after header),
@@ -278,14 +310,15 @@ protected final void decodeVector(int vectorIndex) {
278310
// Vector header, part two: ForInfo, whose width depends on the value type.
279311
pos = readForInfo(pos, vectorIndex, forInfo);
280312

281-
// Data section, part one: PackedValues.
282-
pos = decodePackedValues(pos, vectorSize, exponent, factor, forInfo);
283-
// The packed values' width comes from this vector's own ForInfo, so confirm they did not run
284-
// past where the next vector begins; otherwise this vector would decode another one's bytes.
285-
if (pos > vectorEnd) {
286-
throw new ParquetDecodingException("ALP vector " + vectorIndex + " packed values end at " + pos
287-
+ ", past the start of the next vector at " + vectorEnd);
313+
// Data section, part one: PackedValues. Their width comes from this vector's own ForInfo, so
314+
// confirm they fit before unpacking; otherwise this vector would decode the next one's bytes,
315+
// or for the last vector read past the end of the page.
316+
int packedEnd = pos + BytesUtils.paddedByteCountFromBits(vectorSize * forInfo.bitWidth);
317+
if (packedEnd > vectorEnd) {
318+
throw new ParquetDecodingException("ALP vector " + vectorIndex + " packed values end at " + packedEnd
319+
+ ", past the end of the vector at " + vectorEnd);
288320
}
321+
pos = decodePackedValues(pos, vectorSize, exponent, factor, forInfo);
289322

290323
// Data section, parts two and three: ExceptionPositions then ExceptionValues.
291324
if (numExceptions > 0) {
@@ -362,9 +395,4 @@ static int readExceptionPositions(ByteBuffer data, int pos, int numExceptions, i
362395
* decoded values.
363396
*/
364397
protected abstract void applyExceptions(int pos, int numExceptions, int vectorSize);
365-
366-
/**
367-
* Reads {@code numExceptions} original values starting at {@code pos} and writes them into the
368-
* decoded buffer at the positions previously read into {@link #excPositionsBuffer}.
369-
*/
370398
}

‎parquet-column/src/test/java/org/apache/parquet/column/values/alp/AlpAdversarialTest.java‎

Lines changed: 52 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -275,7 +275,7 @@ public void rejectsBitWidthTooLargeFloat() throws Exception {
275275
@Test
276276
public void rejectsPackedValuesRunningPastVectorEnd() throws Exception {
277277
// 16 vectors, so the inflated packed body stays inside the page and crosses into the vectors
278-
// that follow rather than simply running off the end, which the buffer bounds would catch.
278+
// that follow; the last-vector case, which would run off the end of the page, is below.
279279
byte[] page = validDoublePage(256, 16);
280280
int v0 = firstVectorOffset(page);
281281
// bitWidth lives after ALP_INFO(4) + frameOfReference(8). 64 is the maximum legal width, so it
@@ -288,6 +288,23 @@ public void rejectsPackedValuesRunningPastVectorEnd() throws Exception {
288288
.hasMessageContaining("packed values end at");
289289
}
290290

291+
/**
292+
* The same forged bit width on the last vector would read past the end of the page. It must be
293+
* rejected as a decoding error before unpacking, not surface as an IndexOutOfBoundsException.
294+
*/
295+
@Test
296+
public void rejectsPackedValuesRunningPastEndOfLastVector() throws Exception {
297+
byte[] page = validDoublePage(20, 8); // 3 vectors, the last holding 4 values
298+
int lastOffset = ByteBuffer.wrap(page).order(ByteOrder.LITTLE_ENDIAN).getInt(7 + 2 * Integer.BYTES);
299+
page[7 + lastOffset + 12] = (byte) 64;
300+
AlpValuesReaderForDouble reader = new AlpValuesReaderForDouble();
301+
reader.initFromPage(20, ByteBufferInputStream.wrap(ByteBuffer.wrap(page)));
302+
reader.skip(16);
303+
assertThatThrownBy(reader::readDouble)
304+
.isInstanceOf(ParquetDecodingException.class)
305+
.hasMessageContaining("ALP vector 2 packed values end at");
306+
}
307+
291308
/**
292309
* An exception count that is legal against the vector size can still declare an exception block
293310
* larger than the vector holds. numExceptions == vectorSize passes the AlpInfo check and then
@@ -323,6 +340,40 @@ public void rejectsExceptionPositionOutOfBounds() {
323340
.hasMessageContaining("ALP exception position 16 out of bounds for vectorSize 16");
324341
}
325342

343+
/** Each vector must span at least its fixed headers, the last one included via the end entry. */
344+
@Test
345+
public void rejectsVectorShorterThanItsHeaders() {
346+
// offset array of 2 entries (8 bytes), then vectors at 8 and 30, data ending at 40.
347+
assertThatThrownBy(() -> AlpValuesReader.validateVectorOffsets(new int[] {8, 30, 40}, 17, 1000))
348+
.isInstanceOf(ParquetDecodingException.class)
349+
.hasMessageContaining("ALP vector 1 at offset 30 spans 10 bytes, fewer than the 17");
350+
}
351+
352+
/** No vector can be longer than every value packed at full width and also stored as an exception. */
353+
@Test
354+
public void rejectsVectorLongerThanAnyVectorCanBe() {
355+
int max = AlpValuesReader.maxVectorBytes(16, 17, Double.BYTES);
356+
assertThat(max).isEqualTo(17 + 16 * 8 + 16 * (2 + 8));
357+
AlpValuesReader.validateVectorOffsets(new int[] {8, 8 + max, 8 + max + 17}, 17, max);
358+
assertThatThrownBy(() -> AlpValuesReader.validateVectorOffsets(new int[] {8, 9 + max, 9 + max + 17}, 17, max))
359+
.isInstanceOf(ParquetDecodingException.class)
360+
.hasMessageContaining("ALP vector 0 at offset 8 spans " + (max + 1) + " bytes, more than the " + max);
361+
}
362+
363+
/** The end entry makes every in-range index valid, and anything else is a caller error. */
364+
@Test
365+
public void vectorEndPositionRejectsOutOfRangeIndex() throws Exception {
366+
byte[] page = validDoublePage(32, 16);
367+
AlpValuesReaderForDouble reader = new AlpValuesReaderForDouble();
368+
reader.initFromPage(32, ByteBufferInputStream.wrap(ByteBuffer.wrap(page)));
369+
assertThat(reader.getVectorEndPosition(1)).isEqualTo(page.length - 7 - 2 * Integer.BYTES);
370+
for (int bad : new int[] {-1, 2, Integer.MAX_VALUE}) {
371+
assertThatThrownBy(() -> reader.getVectorEndPosition(bad))
372+
.isInstanceOf(IllegalArgumentException.class)
373+
.hasMessageContaining("out of range for 2 vectors");
374+
}
375+
}
376+
326377
/** The last vector is partial whenever the value count is not a whole number of vectors. */
327378
@Test
328379
public void vectorSizeAccountsForAPartialLastVector() {

‎parquet-column/src/test/java/org/apache/parquet/column/values/alp/AlpValuesEndToEndTest.java‎

Lines changed: 66 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -342,16 +342,29 @@ public void testForgedVectorOffsetsAreRejected() throws Exception {
342342
.putInt(offsetArrayStart + Integer.BYTES, firstOffset);
343343
assertThatThrownBy(() -> readAllDoubles(nonIncreasing, values.length))
344344
.isInstanceOf(ParquetDecodingException.class)
345-
.hasMessageContaining("ALP vector offsets must increase");
345+
.hasMessageContaining("ALP vector 0 at offset " + firstOffset + " spans 0 bytes, fewer than");
346346

347-
// An offset past the end of the page body must be rejected, not read out of bounds.
347+
// An offset past the end of the page body must be rejected, not read out of bounds. The
348+
// trailing end-of-data entry means the vector before it is then too long or the one after it
349+
// runs backwards; here vector 0 claims more bytes than any vector can occupy.
348350
byte[] pastEnd = valid.clone();
349351
ByteBuffer.wrap(pastEnd)
350352
.order(ByteOrder.LITTLE_ENDIAN)
351353
.putInt(offsetArrayStart + Integer.BYTES, valid.length * 4);
352354
assertThatThrownBy(() -> readAllDoubles(pastEnd, values.length))
353355
.isInstanceOf(ParquetDecodingException.class)
354-
.hasMessageContaining("ALP vector 1 offset");
356+
.hasMessageContaining("ALP vector 0 at offset " + firstOffset + " spans")
357+
.hasMessageContaining("more than the");
358+
359+
// Pointing the last vector just past the end of the data leaves it negative room: the
360+
// trailing entry turns this into a span check instead of an out-of-bounds read.
361+
byte[] lastPastEnd = valid.clone();
362+
int lastEntry = offsetArrayStart + 3 * Integer.BYTES;
363+
int dataEnd = valid.length - offsetArrayStart;
364+
ByteBuffer.wrap(lastPastEnd).order(ByteOrder.LITTLE_ENDIAN).putInt(lastEntry, dataEnd + 1);
365+
assertThatThrownBy(() -> readAllDoubles(lastPastEnd, values.length))
366+
.isInstanceOf(ParquetDecodingException.class)
367+
.hasMessageContaining("ALP vector 3 at offset " + (dataEnd + 1) + " spans -1 bytes");
355368

356369
// Sanity: the untouched page still decodes, so the checks above are not rejecting everything.
357370
assertThat(secondOffset).isGreaterThan(firstOffset);
@@ -421,6 +434,56 @@ public void testSpanBoundAcceptsEveryLegitimatePageShape() throws Exception {
421434
assertThat(shapes).isEqualTo(84);
422435
}
423436

437+
/** The float counterpart of the sweep above: the span bound is computed per value type. */
438+
@Test
439+
public void testFloatSpanBoundAcceptsEveryLegitimatePageShape() throws Exception {
440+
Random rnd = new Random(42);
441+
int shapes = 0;
442+
for (int perVector : new int[] {8, 16, 1024, 4096}) {
443+
for (int count :
444+
new int[] {1, 2, perVector - 1, perVector, perVector + 1, 2 * perVector + 1, 5 * perVector + 3}) {
445+
for (int profile = 0; profile < 3; profile++) {
446+
float[] values = new float[count];
447+
for (int i = 0; i < count; i++) {
448+
if (profile == 0) {
449+
values[i] = i / 8.0f;
450+
} else if (profile == 1) {
451+
values[i] = (i % 2 == 0) ? 2e9f : -2e9f;
452+
} else {
453+
values[i] = Float.intBitsToFloat(rnd.nextInt());
454+
}
455+
}
456+
assertFloatsRoundTripExactly(values, perVector, profile);
457+
shapes++;
458+
}
459+
}
460+
}
461+
assertThat(shapes).isEqualTo(84);
462+
}
463+
464+
private void assertFloatsRoundTripExactly(float[] values, int perVector, int profile) throws Exception {
465+
AlpValuesWriter.FloatAlpValuesWriter writer =
466+
new AlpValuesWriter.FloatAlpValuesWriter(1 << 22, 1 << 22, new DirectByteBufferAllocator(), perVector);
467+
byte[] page;
468+
try {
469+
for (float v : values) {
470+
writer.writeFloat(v);
471+
}
472+
page = writer.getBytes().toByteArray();
473+
} finally {
474+
writer.reset();
475+
writer.close();
476+
}
477+
478+
AlpValuesReaderForFloat reader = new AlpValuesReaderForFloat();
479+
reader.initFromPage(values.length, ByteBufferInputStream.wrap(ByteBuffer.wrap(page)));
480+
for (int i = 0; i < values.length; i++) {
481+
assertThat(Float.floatToRawIntBits(reader.readFloat()))
482+
.as("perVector=%s count=%s profile=%s index=%s", perVector, values.length, profile, i)
483+
.isEqualTo(Float.floatToRawIntBits(values[i]));
484+
}
485+
}
486+
424487
private void assertDoublesRoundTripExactly(double[] values, int perVector, int profile) throws Exception {
425488
AlpValuesWriter.DoubleAlpValuesWriter writer =
426489
new AlpValuesWriter.DoubleAlpValuesWriter(1 << 22, 1 << 22, new DirectByteBufferAllocator(), perVector);

0 commit comments

Comments
 (0)