Skip to content

Commit 891c01a

Browse files
authored
fix(alp): bounds-check ALP-RD stored metadata and left-parts codes (#10760)
## Summary - Tracking Issue: #10756 ALP-RD's `deserialize` and decode paths trust stored metadata, so a corrupt or crafted file can panic a read instead of returning an error. This covers the ALP-RD items from the issue that #10755 does not: `deserialize` now bounds-checks the stored `dict_len` against the stored dictionary, and `validate` rejects a dictionary longer than `MAX_DICT_SIZE` and a `right_bit_width` at or above the float's bit width, which is the bound the decode shift requires. Left-parts codes are checked on first use: `alp_rd_decode` scans the codes once before decoding, and `scalar_at` uses a checked lookup, because both decode paths index (or mask into) the dictionary with each code. The `left_parts_ptype` and RLE items from the issue look like they belong to #10755, so they are not touched here. Partially addresses #10756. --------- Signed-off-by: devtechedge <[email protected]> Signed-off-by: Robert Kruszewski <[email protected]>
1 parent 1a09eb4 commit 891c01a

3 files changed

Lines changed: 340 additions & 9 deletions

File tree

‎encodings/alp/src/alp_rd/array.rs‎

Lines changed: 218 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,7 @@ use std::fmt::Formatter;
77
use std::hash::Hash;
88
use std::hash::Hasher;
99

10+
use ::alp::MAX_DICT_SIZE;
1011
use itertools::Itertools;
1112
use prost::Message;
1213
use vortex_array::Array;
@@ -46,12 +47,14 @@ use vortex_buffer::Buffer;
4647
use vortex_error::VortexExpect;
4748
use vortex_error::VortexResult;
4849
use vortex_error::vortex_bail;
50+
use vortex_error::vortex_ensure;
4951
use vortex_error::vortex_ensure_eq;
5052
use vortex_error::vortex_err;
5153
use vortex_error::vortex_panic;
5254
use vortex_session::VortexSession;
5355
use vortex_session::registry::CachedId;
5456

57+
use crate::alp_rd::check_left_parts_codes;
5558
use crate::alp_rd::rules::RULES;
5659
use crate::alp_rd_decode;
5760

@@ -120,6 +123,7 @@ impl VTable for ALPRD {
120123
) -> VortexResult<()> {
121124
let alprd_slots = ALPRDSlotsView::from_slots(slots);
122125
validate_parts(
126+
data,
123127
dtype,
124128
len,
125129
alprd_slots.left_parts,
@@ -191,6 +195,15 @@ impl VTable for ALPRD {
191195
);
192196
}
193197

198+
// Stored metadata is untrusted: dict_len must stay within the stored entries.
199+
if metadata.dict_len as usize > metadata.dict.len() {
200+
vortex_bail!(
201+
"ALP-RD dictionary length {} exceeds the {} stored entries",
202+
metadata.dict_len,
203+
metadata.dict.len()
204+
);
205+
}
206+
194207
let left_parts_dtype = DType::Primitive(left_parts_ptype, dtype.nullability());
195208
let left_parts = children.get(0, &left_parts_dtype, len)?;
196209
let left_parts_dictionary: Buffer<u16> = metadata.dict.as_slice()
@@ -291,10 +304,13 @@ impl VTable for ALPRD {
291304
.validity()?
292305
.execute_mask(left_parts.as_ref().len(), ctx)?;
293306

307+
let mut left_parts = left_parts.into_buffer_mut::<u16>();
308+
check_left_parts_codes(left_parts.as_mut_slice(), &validity, left_parts_dict.len())?;
309+
294310
let decoded_array = if ptype == PType::F32 {
295311
PrimitiveArray::new(
296312
alp_rd_decode::<f32>(
297-
left_parts.into_buffer_mut::<u16>(),
313+
left_parts,
298314
&left_parts_dict,
299315
right_bit_width,
300316
right_parts.into_buffer_mut::<u32>(),
@@ -306,7 +322,7 @@ impl VTable for ALPRD {
306322
} else {
307323
PrimitiveArray::new(
308324
alp_rd_decode::<f64>(
309-
left_parts.into_buffer_mut::<u16>(),
325+
left_parts,
310326
&left_parts_dict,
311327
right_bit_width,
312328
right_parts.into_buffer_mut::<u64>(),
@@ -482,6 +498,7 @@ fn patches_from_slots(
482498

483499
#[allow(clippy::disallowed_methods)]
484500
fn validate_parts(
501+
data: &ALPRDData,
485502
dtype: &DType,
486503
len: usize,
487504
left_parts: &ArrayRef,
@@ -495,8 +512,8 @@ fn validate_parts(
495512
vortex_ensure_eq!(left_parts.len(), len);
496513
vortex_ensure_eq!(right_parts.len(), len);
497514

498-
if !left_parts.dtype().is_unsigned_int() {
499-
vortex_bail!("left_parts dtype must be uint");
515+
if !matches!(left_parts.dtype(), DType::Primitive(PType::U16, _)) {
516+
vortex_bail!("left_parts dtype must be u16, got {}", left_parts.dtype());
500517
}
501518
if dtype.is_nullable() != left_parts.dtype().is_nullable() {
502519
vortex_bail!(
@@ -506,13 +523,55 @@ fn validate_parts(
506523
);
507524
}
508525

509-
let expected_right_parts_dtype = match dtype {
510-
DType::Primitive(PType::F32, _) => DType::Primitive(PType::U32, Nullability::NonNullable),
511-
DType::Primitive(PType::F64, _) => DType::Primitive(PType::U64, Nullability::NonNullable),
526+
let (expected_right_parts_dtype, float_bit_width) = match dtype {
527+
DType::Primitive(PType::F32, _) => (
528+
DType::Primitive(PType::U32, Nullability::NonNullable),
529+
u32::BITS,
530+
),
531+
DType::Primitive(PType::F64, _) => (
532+
DType::Primitive(PType::U64, Nullability::NonNullable),
533+
u64::BITS,
534+
),
512535
_ => vortex_bail!("Expected f32 or f64 dtype, got {:?}", dtype),
513536
};
514537
vortex_ensure_eq!(right_parts.dtype(), &expected_right_parts_dtype);
515538

539+
// Stored metadata is untrusted: the alp decoder masks codes into an at-most-MAX_DICT_SIZE
540+
// dictionary, and the decode shift overflows the float's bit pattern once right_bit_width
541+
// reaches the width of the float.
542+
vortex_ensure!(
543+
data.left_parts_dictionary().len() <= MAX_DICT_SIZE as usize,
544+
"ALP-RD dictionary holds {} entries, more than MAX_DICT_SIZE ({})",
545+
data.left_parts_dictionary().len(),
546+
MAX_DICT_SIZE
547+
);
548+
vortex_ensure!(
549+
u32::from(data.right_bit_width()) < float_bit_width,
550+
"ALP-RD right_bit_width {} must be below the {}-bit float width",
551+
data.right_bit_width(),
552+
float_bit_width
553+
);
554+
555+
// The left part must fit in a u16, and each dictionary entry must fit in the left part.
556+
let left_bit_width = float_bit_width - u32::from(data.right_bit_width());
557+
vortex_ensure!(
558+
left_bit_width <= u16::BITS,
559+
"ALP-RD right_bit_width {} leaves more than {} bits for the left part of a {}-bit float",
560+
data.right_bit_width(),
561+
u16::BITS,
562+
float_bit_width
563+
);
564+
if let Some(entry) = data
565+
.left_parts_dictionary()
566+
.iter()
567+
.copied()
568+
.find(|&entry| u32::from(entry) >> left_bit_width != 0)
569+
{
570+
vortex_bail!(
571+
"ALP-RD dictionary entry {entry} does not fit in the {left_bit_width}-bit left part"
572+
);
573+
}
574+
516575
if let Some(patches) = left_parts_patches {
517576
vortex_ensure_eq!(patches.array_len(), len);
518577
// Left-parts exceptions are always all-valid and are stored as the non-nullable left-parts
@@ -577,7 +636,9 @@ mod test {
577636

578637
use prost::Message;
579638
use rstest::rstest;
639+
use vortex_array::ArrayDeserialization;
580640
use vortex_array::ArrayRef;
641+
use vortex_array::IntoArray;
581642
use vortex_array::VortexSessionExecute;
582643
use vortex_array::arrays::PrimitiveArray;
583644
use vortex_array::assert_arrays_eq;
@@ -588,6 +649,7 @@ mod test {
588649
use vortex_array::patches::PatchesMetadata;
589650
use vortex_array::test_harness::check_metadata;
590651
use vortex_array::vtable::VTable;
652+
use vortex_buffer::buffer;
591653
use vortex_error::VortexResult;
592654
use vortex_session::VortexSession;
593655

@@ -681,4 +743,153 @@ mod test {
681743

682744
Ok(())
683745
}
746+
747+
/// Deserialize ALP-RD parts the way a file read does, through the plugin door, so both
748+
/// deserialize-time and validate-time rejections surface as errors.
749+
fn deserialize_alprd(
750+
dtype: &DType,
751+
len: usize,
752+
metadata: &ALPRDMetadata,
753+
children: Vec<ArrayRef>,
754+
) -> VortexResult<ArrayRef> {
755+
vortex_array::ArrayPlugin::deserialize(
756+
&ALPRD,
757+
ArrayDeserialization::new(
758+
ALPRD.id(),
759+
dtype,
760+
len,
761+
&metadata.encode_to_vec(),
762+
&[],
763+
&children,
764+
),
765+
&SESSION,
766+
)
767+
}
768+
769+
/// The stored dictionary is untrusted, so `dict_len` past the end of the stored entries
770+
/// must be a deserialize error, not a slice panic (#10756).
771+
#[test]
772+
fn test_deserialize_rejects_dict_len_past_the_stored_dictionary() {
773+
let dtype = DType::Primitive(PType::F32, Nullability::NonNullable);
774+
let metadata = ALPRDMetadata {
775+
right_bit_width: 16,
776+
dict_len: 8,
777+
dict: vec![0, 1],
778+
left_parts_ptype: PType::U16 as i32,
779+
patches: None,
780+
};
781+
let children = vec![buffer![0u16].into_array(), buffer![0u32].into_array()];
782+
783+
let error = deserialize_alprd(&dtype, 1, &metadata, children)
784+
.expect_err("dict_len past the stored dictionary must be rejected");
785+
assert!(error.to_string().contains("dictionary"));
786+
}
787+
788+
/// The `alp` decoder's lane lookup masks codes into an at-most-`MAX_DICT_SIZE` dictionary,
789+
/// so a longer stored dictionary must be rejected rather than panicking at decode time.
790+
#[test]
791+
fn test_deserialize_rejects_dictionary_larger_than_max_dict_size() {
792+
let dtype = DType::Primitive(PType::F32, Nullability::NonNullable);
793+
let metadata = ALPRDMetadata {
794+
right_bit_width: 16,
795+
dict_len: 9,
796+
dict: vec![0, 1, 2, 3, 4, 5, 6, 7, 8],
797+
left_parts_ptype: PType::U16 as i32,
798+
patches: None,
799+
};
800+
let children = vec![buffer![0u16].into_array(), buffer![0u32].into_array()];
801+
802+
let error = deserialize_alprd(&dtype, 1, &metadata, children)
803+
.expect_err("a dictionary larger than MAX_DICT_SIZE must be rejected");
804+
assert!(error.to_string().contains("MAX_DICT_SIZE"));
805+
}
806+
807+
/// `right_bit_width` must leave between 1 and 16 bits for the left part.
808+
#[rstest]
809+
#[case::f32_at_float_width(PType::F32, 32, "must be below")]
810+
#[case::f64_at_float_width(PType::F64, 64, "must be below")]
811+
#[case::f32_left_part_too_wide(PType::F32, 15, "leaves more than")]
812+
#[case::f64_left_part_too_wide(PType::F64, 47, "leaves more than")]
813+
fn test_deserialize_rejects_right_bit_width_out_of_range(
814+
#[case] float_ptype: PType,
815+
#[case] right_bit_width: u32,
816+
#[case] expected_error: &str,
817+
) {
818+
let dtype = DType::Primitive(float_ptype, Nullability::NonNullable);
819+
let metadata = ALPRDMetadata {
820+
right_bit_width,
821+
dict_len: 2,
822+
dict: vec![0, 1],
823+
left_parts_ptype: PType::U16 as i32,
824+
patches: None,
825+
};
826+
let right_parts = match float_ptype {
827+
PType::F32 => buffer![0u32].into_array(),
828+
_ => buffer![0u64].into_array(),
829+
};
830+
let children = vec![buffer![0u16].into_array(), right_parts];
831+
832+
let error = deserialize_alprd(&dtype, 1, &metadata, children)
833+
.expect_err("right_bit_width out of range must be rejected");
834+
assert!(error.to_string().contains(expected_error));
835+
}
836+
837+
#[test]
838+
fn test_deserialize_rejects_dictionary_entry_wider_than_the_left_part() {
839+
let dtype = DType::Primitive(PType::F32, Nullability::NonNullable);
840+
let metadata = ALPRDMetadata {
841+
right_bit_width: 24,
842+
dict_len: 2,
843+
dict: vec![0, 256],
844+
left_parts_ptype: PType::U16 as i32,
845+
patches: None,
846+
};
847+
let children = vec![buffer![0u16].into_array(), buffer![0u32].into_array()];
848+
849+
let error = deserialize_alprd(&dtype, 1, &metadata, children)
850+
.expect_err("a dictionary entry wider than the left part must be rejected");
851+
assert!(error.to_string().contains("dictionary entry 256"));
852+
}
853+
854+
#[test]
855+
fn test_deserialize_rejects_left_parts_ptype_other_than_u16() {
856+
let dtype = DType::Primitive(PType::F32, Nullability::NonNullable);
857+
let metadata = ALPRDMetadata {
858+
right_bit_width: 16,
859+
dict_len: 2,
860+
dict: vec![0, 1],
861+
left_parts_ptype: PType::U32 as i32,
862+
patches: None,
863+
};
864+
let children = vec![buffer![0u32].into_array(), buffer![0u32].into_array()];
865+
866+
let error = deserialize_alprd(&dtype, 1, &metadata, children)
867+
.expect_err("left parts that are not u16 must be rejected");
868+
assert!(error.to_string().contains("must be u16"));
869+
}
870+
871+
/// Metadata inside the format's bounds still deserializes and decodes: code 1 maps through
872+
/// the dictionary and the shift stays below the f32 width.
873+
#[test]
874+
fn test_deserialize_accepts_metadata_within_bounds() -> VortexResult<()> {
875+
let mut ctx = SESSION.create_execution_ctx();
876+
let dtype = DType::Primitive(PType::F32, Nullability::NonNullable);
877+
let metadata = ALPRDMetadata {
878+
right_bit_width: 16,
879+
dict_len: 2,
880+
dict: vec![10, 20],
881+
left_parts_ptype: PType::U16 as i32,
882+
patches: None,
883+
};
884+
let children = vec![buffer![1u16].into_array(), buffer![0u32].into_array()];
885+
886+
let deserialized = deserialize_alprd(&dtype, 1, &metadata, children)?;
887+
let decoded = deserialized.execute::<PrimitiveArray>(&mut ctx)?;
888+
assert_arrays_eq!(
889+
decoded,
890+
PrimitiveArray::from_iter([f32::from_bits(20u32 << 16)]),
891+
&mut ctx
892+
);
893+
Ok(())
894+
}
684895
}

‎encodings/alp/src/alp_rd/mod.rs‎

Lines changed: 43 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -25,10 +25,14 @@ use vortex_array::patches::Patches;
2525
use vortex_array::validity::Validity;
2626
use vortex_buffer::Buffer;
2727
use vortex_buffer::BufferMut;
28+
use vortex_error::VortexError;
2829
use vortex_error::VortexExpect;
2930
use vortex_error::VortexResult;
31+
use vortex_error::vortex_err;
3032
use vortex_error::vortex_panic;
3133
use vortex_fastlanes::bitpack_compress::bitpack_encode_unchecked;
34+
use vortex_mask::AllOr;
35+
use vortex_mask::Mask;
3236
use vortex_session::VortexSession;
3337

3438
use crate::match_each_alp_float_ptype;
@@ -135,9 +139,16 @@ where
135139
/// The decoded values are written over `right_parts`, which shares its layout with the floats they
136140
/// decode to.
137141
///
142+
/// The caller must check that each code is in `left_parts_dict`.
143+
///
144+
/// # Errors
145+
///
146+
/// Returns an error if the patches fail to execute.
147+
///
138148
/// # Panics
139149
///
140-
/// Panics if `left_parts` and `right_parts` differ in length.
150+
/// Panics if `left_parts` and `right_parts` differ in length, or if patches are set and a code is
151+
/// not in `left_parts_dict`.
141152
pub fn alp_rd_decode<T: ALPRDFloat + NativePType>(
142153
mut left_parts: BufferMut<u16>,
143154
left_parts_dict: &[u16],
@@ -190,6 +201,37 @@ where
190201
Ok(unsafe { right_parts.transmute::<T>() }.freeze())
191202
}
192203

204+
/// Checks that each valid code is in the dictionary, and sets the codes in null slots to zero,
205+
/// because the patched decode path looks up every code.
206+
fn check_left_parts_codes(codes: &mut [u16], validity: &Mask, dict_len: usize) -> VortexResult<()> {
207+
let max_valid_code = match validity.bit_buffer() {
208+
AllOr::All => codes.iter().copied().max(),
209+
AllOr::None => {
210+
codes.fill(0);
211+
None
212+
}
213+
AllOr::Some(valid) => codes
214+
.iter_mut()
215+
.zip(valid.iter())
216+
.map(|(code, is_valid)| {
217+
if !is_valid {
218+
*code = 0;
219+
}
220+
*code
221+
})
222+
.max(),
223+
};
224+
225+
match max_valid_code {
226+
Some(code) if usize::from(code) >= dict_len => Err(code_not_in_dictionary(code, dict_len)),
227+
_ => Ok(()),
228+
}
229+
}
230+
231+
fn code_not_in_dictionary(code: u16, dict_len: usize) -> VortexError {
232+
vortex_err!("ALP-RD left-parts code {code} is not in the {dict_len}-entry dictionary")
233+
}
234+
193235
#[cfg(test)]
194236
mod tests {
195237
use vortex_array::arrays::PrimitiveArray;

0 commit comments

Comments
 (0)