Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_jdat/src/bdat/limits.rs

16.3 KiB, 21 runs

created by r1870400018:13535, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Limits applied while decoding a daticle from an untrusted source, in either encoding.
2//!
3//! Neither encoding is self-limiting: a few bytes can describe a list nested a million deep, and a
4//! decoder that trusts them will recurse until its stack is gone. A reader that did not create the
5//! input it is reading should therefore decode through
6//! [`Dat::from_bytes_limited`](crate::Dat::from_bytes_limited) for BDAT, or
7//! [`Dat::decode_string_limited`](crate::Dat::decode_string_limited) for JDAT text, both of which
8//! refuse input that is too long, and refuse to descend past a stated depth.
9
10use oxedyne_fe2o3_core::prelude::*;
11
12
13/// The bounds a BDAT decoder enforces on untrusted input.
14///
15/// `max_depth` counts nested values, with the root value at depth 1. A scalar at the root reaches
16/// depth 1, a list holding a scalar reaches depth 2, and a list holding a list holding a scalar
17/// reaches depth 3. `max_bytes` bounds the length of the buffer handed to the decoder, not the
18/// length of the value decoded from it, since a value may be followed by bytes that are none of the
19/// decoder's business.
20#[derive(Clone, Copy, Debug, Eq, PartialEq)]
21pub struct DecodeLimits {
22 /// Greatest nesting depth the decoder will descend to, with the root value at depth 1.
23 pub max_depth: usize,
24 /// Greatest length, in bytes, of a buffer the decoder will accept.
25 pub max_bytes: usize,
26}
27
28impl Default for DecodeLimits {
29 fn default() -> Self {
30 Self {
31 max_depth: Self::DEFAULT_MAX_DEPTH,
32 max_bytes: Self::DEFAULT_MAX_BYTES,
33 }
34 }
35}
36
37impl DecodeLimits {
38
39 /// Default nesting depth, deep enough for any document a human wrote and shallow enough to
40 /// leave the stack intact.
41 pub const DEFAULT_MAX_DEPTH: usize = 64;
42 /// Default nesting depth for the text decoder, measured rather than chosen.
43 ///
44 /// The text decoder costs 2.5 KiB of stack per level of nesting in an unoptimised build, and
45 /// 0.9 KiB in an optimised one, so a 2 MiB stack, which is what Rust gives a spawned thread,
46 /// is exhausted at depth 789 in the worst case. A limit of 512 levels spends 1.25 MiB of that
47 /// stack, leaving 800 KiB spare in the worst case and four times the room in an optimised
48 /// build, so a document at the limit cannot abort the process, which is the only thing the
49 /// limit is for. It is not an opinion about how deep a document should be: a caller wanting a
50 /// stricter bound passes one.
51 ///
52 /// The limit is generous because text depth runs well ahead of value depth. Every bracket,
53 /// brace and kindicle costs a level, so a format layered on JDAT may spend several levels on
54 /// one of its own nodes, and a document nesting a hundred such nodes still decodes.
55 pub const DEFAULT_MAX_TEXT_DEPTH: usize = 512;
56 /// Default buffer length, in bytes.
57 pub const DEFAULT_MAX_BYTES: usize = 64 * 1024 * 1024;
58
59 /// No limits at all, as trusted by [`Dat::from_bytes`](crate::Dat::from_bytes), whose behaviour
60 /// predates this type.
61 pub const UNLIMITED: Self = Self {
62 max_depth: usize::MAX,
63 max_bytes: usize::MAX,
64 };
65
66 /// Creates limits with the given maximum depth and buffer length.
67 pub fn new(
68 max_depth: usize,
69 max_bytes: usize,
70 )
71 -> Self
72 {
73 Self {
74 max_depth,
75 max_bytes,
76 }
77 }
78
79 /// Returns the limits with the maximum depth replaced.
80 pub fn with_max_depth(mut self, max_depth: usize) -> Self {
81 self.max_depth = max_depth;
82 self
83 }
84
85 /// Returns the limits with the maximum buffer length replaced.
86 pub fn with_max_bytes(mut self, max_bytes: usize) -> Self {
87 self.max_bytes = max_bytes;
88 self
89 }
90
91 /// Rejects a buffer longer than the maximum length.
92 pub fn check_len(&self, len: usize) -> Outcome<()> {
93 if len > self.max_bytes {
94 return Err(err!(
95 "Decoding input of {} bytes at byte offset 0 exceeds the maximum of {} bytes.",
96 len, self.max_bytes;
97 Input, Invalid, Excessive, Size));
98 }
99 Ok(())
100 }
101
102 /// Returns the default limits for the text decoder, whose depth runs ahead of value depth.
103 pub fn text() -> Self {
104 Self {
105 max_depth: Self::DEFAULT_MAX_TEXT_DEPTH,
106 max_bytes: Self::DEFAULT_MAX_BYTES,
107 }
108 }
109
110 /// Rejects a value nested deeper than the maximum depth, naming the offset of its first
111 /// character.
112 pub fn check_char_depth(
113 &self,
114 depth: usize,
115 pos: usize,
116 )
117 -> Outcome<()>
118 {
119 if depth > self.max_depth {
120 return Err(err!(
121 "Decoding a value at nesting depth {} at character offset {} exceeds the maximum \
122 depth of {}.",
123 depth, pos, self.max_depth;
124 Input, Invalid, Excessive, Size));
125 }
126 Ok(())
127 }
128
129 /// Rejects a value nested deeper than the maximum depth, naming the offset of its first byte.
130 pub fn check_depth(
131 &self,
132 depth: usize,
133 pos: usize,
134 )
135 -> Outcome<()>
136 {
137 if depth > self.max_depth {
138 return Err(err!(
139 "Decoding a value at nesting depth {} at byte offset {} exceeds the maximum \
140 depth of {}.",
141 depth, pos, self.max_depth;
142 Input, Invalid, Excessive, Size));
143 }
144 Ok(())
145 }
146
147}
148
149#[cfg(test)]
150mod tests {
151 use super::*;
152
153 use crate::prelude::*;
154
155 use oxedyne_fe2o3_core::byte::{
156 FromBytes,
157 ToBytes,
158 };
159
160 use std::io::Cursor;
161
162 /// Wraps a leaf in `levels` nested lists, so that the leaf sits at depth `levels + 1`.
163 fn nest(levels: usize) -> Dat {
164 let mut dat = Dat::Empty;
165 for _ in 0..levels {
166 dat = Dat::List(vec![dat]);
167 }
168 dat
169 }
170
171 /// Encodes `levels` nested lists around an empty leaf, from the inside out.
172 ///
173 /// The bytes are built rather than encoded, since the encoder recurses as the decoder does, and
174 /// an attacker is under no obligation to use it. This is the bomb: a few hundred kilobytes
175 /// describing a nesting deep enough to exhaust the stack of whoever decodes it.
176 fn nested_list_bytes(levels: usize) -> Outcome<Vec<u8>> {
177 let mut buf = vec![Dat::EMPTY_CODE];
178 for _ in 0..levels {
179 let payload_len = buf.len();
180 let mut outer = vec![Dat::LIST_CODE];
181 outer = res!(Dat::C64(payload_len as u64).to_bytes(outer));
182 outer.append(&mut buf);
183 buf = outer;
184 }
185 Ok(buf)
186 }
187
188 #[test]
189 fn test_depth_limit_accepts_at_the_limit() -> Outcome<()> {
190 const LEVELS: usize = 16;
191 let dat = nest(LEVELS);
192 let buf = res!(dat.to_bytes(Vec::new()));
193 // The leaf sits one deeper than the deepest list.
194 let lims = DecodeLimits::default().with_max_depth(LEVELS + 1);
195 let (dat2, n) = res!(Dat::from_bytes_limited(&buf, &lims));
196 assert_eq!(dat, dat2);
197 assert_eq!(n, buf.len());
198 Ok(())
199 }
200
201 #[test]
202 fn test_depth_limit_refuses_past_the_limit() -> Outcome<()> {
203 const LEVELS: usize = 16;
204 let buf = res!(nest(LEVELS).to_bytes(Vec::new()));
205 let lims = DecodeLimits::default().with_max_depth(LEVELS);
206 match Dat::from_bytes_limited(&buf, &lims) {
207 Ok((dat, _)) => Err(err!(
208 "Expected a depth limit error, but decoded {:?}.", dat;
209 Test, Invalid)),
210 Err(e) => {
211 let msg = e.to_string();
212 assert!(msg.contains("depth"), "Error should name the depth limit: {}", msg);
213 assert!(msg.contains("offset"), "Error should name the byte offset: {}", msg);
214 Ok(())
215 }
216 }
217 }
218
219 #[test]
220 fn test_hand_built_bytes_decode_as_the_encoder_would() -> Outcome<()> {
221 // The bomb builder must agree with the encoder, or it proves nothing.
222 const LEVELS: usize = 12;
223 let built = res!(nested_list_bytes(LEVELS));
224 let encoded = res!(nest(LEVELS).to_bytes(Vec::new()));
225 assert_eq!(built, encoded);
226 Ok(())
227 }
228
229 #[test]
230 fn test_depth_bomb_is_refused() -> Outcome<()> {
231 // A hostile file: 100,000 nested lists, which would exhaust the stack of a decoder that
232 // trusted it, in a buffer small enough to arrive over a socket without comment.
233 let buf = res!(nested_list_bytes(100_000));
234 match Dat::from_bytes_limited(&buf, &DecodeLimits::default()) {
235 Ok(_) => Err(err!(
236 "A nesting of 100,000 lists should be refused by the default limits.";
237 Test, Invalid)),
238 Err(e) => {
239 let msg = e.to_string();
240 assert!(msg.contains("depth"), "Error should name the depth limit: {}", msg);
241 Ok(())
242 }
243 }
244 }
245
246 #[test]
247 fn test_byte_limit_refuses_an_oversized_input() -> Outcome<()> {
248 let buf = res!(dat!("a string long enough to overrun a tiny limit").to_bytes(Vec::new()));
249 let lims = DecodeLimits::default().with_max_bytes(8);
250 match Dat::from_bytes_limited(&buf, &lims) {
251 Ok((dat, _)) => Err(err!(
252 "Expected a byte limit error, but decoded {:?}.", dat;
253 Test, Invalid)),
254 Err(e) => {
255 let msg = e.to_string();
256 assert!(msg.contains("8 bytes"), "Error should name the byte limit: {}", msg);
257 Ok(())
258 }
259 }
260 }
261
262 #[test]
263 fn test_limited_round_trip_matches_unlimited() -> Outcome<()> {
264 let dat = listdat![
265 dat!("hello"),
266 dat!(42u8),
267 mapdat!{
268 dat!("k") => listdat![dat!(1i32), dat!(2i32)],
269 dat!("n") => Dat::Opt(Box::new(Some(dat!(7u16)))),
270 },
271 Dat::Box(Box::new(dat!(true))),
272 ];
273 let buf = res!(dat.to_bytes(Vec::new()));
274
275 let (limited, n1) = res!(Dat::from_bytes_limited(&buf, &DecodeLimits::default()));
276 let (plain, n2) = res!(Dat::from_bytes(&buf));
277
278 assert_eq!(limited, dat);
279 assert_eq!(plain, dat);
280 assert_eq!(n1, buf.len());
281 assert_eq!(n2, buf.len());
282 Ok(())
283 }
284
285 #[test]
286 fn test_trailing_bytes_are_left_alone() -> Outcome<()> {
287 // A limited decode reads one value and reports its length, ignoring what follows.
288 let mut buf = res!(dat!(42u8).to_bytes(Vec::new()));
289 buf.extend_from_slice(&[0xff, 0xff, 0xff]);
290 let (dat, n) = res!(Dat::from_bytes_limited(&buf, &DecodeLimits::default()));
291 assert_eq!(dat, dat!(42u8));
292 assert_eq!(n, 2);
293 Ok(())
294 }
295
296 // The three cases below are truncated encodings that a hostile sender can hand to a decoder.
297 // Each once indexed past the end of the buffer and panicked; the decoder must now refuse them
298 // with an error, never abort the process. A decoder that panics on any byte sequence is a
299 // denial-of-service on every service that reads bytes it did not write.
300
301 #[test]
302 fn test_usr_truncated_before_option_code() -> Outcome<()> {
303 // A usr daticle: kind byte, then the two-byte kind code, and nothing more. The option code
304 // the decoder must read next is off the end of the buffer.
305 let buf = vec![Dat::USR_CODE, 0x00, 0x05];
306 assert!(Dat::from_bytes_limited(&buf, &DecodeLimits::default()).is_err());
307 Ok(())
308 }
309
310 #[test]
311 fn test_abox_truncated_after_inner_value() -> Outcome<()> {
312 // An abox: kind byte, an empty NoteConfig byte, an empty inner value, and nothing more. The
313 // trailing annotation length the decoder must read next is off the end of the buffer.
314 let buf = vec![Dat::ABOX_CODE, Dat::EMPTY_CODE, Dat::EMPTY_CODE];
315 assert!(Dat::from_bytes_limited(&buf, &DecodeLimits::default()).is_err());
316 Ok(())
317 }
318
319 #[test]
320 fn test_list_payload_length_near_usize_max() -> Outcome<()> {
321 // A list whose declared payload length is an eight-byte c64 of all ones, close to
322 // usize::MAX. Adding it to the buffer position once overflowed usize; it must be refused as
323 // more bytes than the buffer holds.
324 let mut buf = vec![Dat::LIST_CODE, Dat::C64_CODE_START + 8];
325 buf.extend_from_slice(&[0xff; 8]);
326 assert!(Dat::from_bytes_limited(&buf, &DecodeLimits::default()).is_err());
327 // The same encoding as a map, which shares the length arithmetic.
328 let mut buf = vec![Dat::MAP_CODE, Dat::C64_CODE_START + 8];
329 buf.extend_from_slice(&[0xff; 8]);
330 assert!(Dat::from_bytes_limited(&buf, &DecodeLimits::default()).is_err());
331 Ok(())
332 }
333
334 // The streaming loader `Dat::load_bytes` is a separate decoder from the slice decoder above:
335 // it reads from any `io::Read`, and o3db walks a data file through it to rebuild an index. A
336 // crash leaves a torn tail whose length header decodes to a garbage payload length, and the
337 // loader once did `vec![0; vlen]` on it, aborting the process (a capacity overflow above
338 // `isize::MAX`, a failed multi-exabyte allocation below it) before the rebuild's own error
339 // handling could truncate the tail. The loader must return an error on an implausible length,
340 // never abort, for every variable-length code.
341
342 #[test]
343 fn test_streaming_loader_refuses_bu64_length_above_isize_max() -> Outcome<()> {
344 // A BU64 whose eight-byte length is all ones: far above isize::MAX, once a capacity
345 // overflow. Only three payload bytes follow.
346 let mut buf = vec![Dat::BU64_CODE];
347 buf.extend_from_slice(&[0xff; 8]);
348 buf.extend_from_slice(&[0x01, 0x02, 0x03]);
349 assert!(Dat::load_bytes(&mut Cursor::new(buf)).is_err());
350 Ok(())
351 }
352
353 #[test]
354 fn test_streaming_loader_refuses_bu64_length_below_isize_max() -> Outcome<()> {
355 // A BU64 length below isize::MAX but still enormous (roughly 72 PiB), once a failed
356 // allocation that aborts rather than unwinds. Only three payload bytes follow.
357 let mut buf = vec![Dat::BU64_CODE];
358 buf.extend_from_slice(&[0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]);
359 buf.extend_from_slice(&[0x01, 0x02, 0x03]);
360 assert!(Dat::load_bytes(&mut Cursor::new(buf)).is_err());
361 Ok(())
362 }
363
364 #[test]
365 fn test_streaming_loader_refuses_bu32_length_past_the_buffer() -> Outcome<()> {
366 // A BU32 length of four gigabytes with three payload bytes: not an abort, but a four-gigabyte
367 // allocation from three bytes of input is a denial of service in its own right. Assert the
368 // specific bounded-loader error, not merely that it errors: a reintroduced pre-allocating
369 // read would also meet the end of the reader and error, so only the torn-length message has
370 // teeth against a regression at this site.
371 let mut buf = vec![Dat::BU32_CODE];
372 buf.extend_from_slice(&[0xff; 4]);
373 buf.extend_from_slice(&[0x01, 0x02, 0x03]);
374 let res = Dat::load_bytes(&mut Cursor::new(buf));
375 let shown = match &res {
376 Ok(_) => String::from("a decoded value"),
377 Err(e) => e.to_string(),
378 };
379 assert!(
380 shown.contains("torn or corrupt length header"),
381 "BU32 hostile length must produce the bounded torn-length error, got: {}", shown,
382 );
383 Ok(())
384 }
385
386 #[test]
387 fn test_streaming_loader_refuses_variable_c64_length_near_usize_max() -> Outcome<()> {
388 // The c64-prefixed variable case (a string here) with an eight-byte length of all ones and
389 // three payload bytes.
390 let mut buf = vec![Dat::STR_CODE, Dat::C64_CODE_START + 8];
391 buf.extend_from_slice(&[0xff; 8]);
392 buf.extend_from_slice(&[0x01, 0x02, 0x03]);
393 assert!(Dat::load_bytes(&mut Cursor::new(buf)).is_err());
394 Ok(())
395 }
396
397 #[test]
398 fn test_streaming_loader_round_trips_a_genuine_byte_payload() -> Outcome<()> {
399 // The guard must not reject a valid variable-length payload: a BU-encoded byte vector still
400 // loads back byte for byte.
401 let original = Dat::BU8(vec![9u8, 8, 7, 6, 5, 4, 3, 2, 1, 0]);
402 let buf = res!(original.to_bytes(Vec::new()));
403 let loaded = res!(Dat::load_bytes(&mut Cursor::new(buf.clone())));
404 assert_eq!(loaded, buf);
405 Ok(())
406 }
407}