Skip to main content

max / shop

16.6 KB · 438 lines History Blame Raw
1 //! The crate's contract, written as an executable assertion.
2 //!
3 //! A normal public module rather than something behind a `fuzzing` feature,
4 //! because two callers need it and neither is the fuzzer: the committed
5 //! regression replay in `tests/regressions.rs` runs it on stable, and the
6 //! libFuzzer target in `fuzz/` runs it on nightly. A property asserted in one
7 //! and not the other is a property that drifts.
8 //!
9 //! ## What is asserted
10 //!
11 //! 1. **Chunk equivalence.** A payload that arrives in one body and the same
12 //! payload arriving as `m=1` chunks must produce the same bytes. This is the
13 //! property with teeth: `accept_chunked` decodes base64 straight into the
14 //! accumulator through `resize` plus `decode_slice`, which is size
15 //! arithmetic over attacker-controlled lengths, and the host indexes the
16 //! result as pixels.
17 //! 2. **Retained state is bounded by the input.** See
18 //! [`MAX_RETAINED_PER_INPUT_BYTE`], and absolutely, via
19 //! [`MAX_RETAINED_BYTES`]. The second is the one that catches an
20 //! accumulator growing with a transmission nobody finishes, which the
21 //! first cannot see: it grew under 1:1.
22 //! 3. **Every query is answered, and answered to the right client.**
23 //! [`super::query_response`] must be a well-formed APC that carries the id
24 //! the query carried, and must say OK only for a medium the host can
25 //! actually satisfy. Silence, or an OK the terminal cannot honour, both cost
26 //! the asking program its timeout or its picture.
27 //! 4. **A decoded payload is no larger than its base64 could describe.** Cheap,
28 //! and it is the assertion that would fail first if the accumulator's
29 //! `resize` bound and its `truncate` ever disagreed.
30
31 use base64::{Engine, engine::general_purpose::STANDARD as B64};
32
33 use super::{Command, Control, Medium, Parser, query_response};
34
35 /// Bytes the parser may hold per byte of input before the oracle calls it a
36 /// finding.
37 ///
38 /// 4 is set from the worst case the shape allows: an accumulator caught just
39 /// past a doubling holds twice its length, and base64 costs the writer four
40 /// bytes for every three it lands, so the ratio cannot exceed 1.5. The bounds
41 /// that hold it there are [`super::MAX_IN_FLIGHT_TRANSMISSIONS`] and
42 /// [`super::MAX_IN_FLIGHT_BYTES`]. Anything that pushes the ratio back over 4
43 /// is either a new accumulator or a cap that stopped being enforced.
44 pub const MAX_RETAINED_PER_INPUT_BYTE: usize = 4;
45
46 /// Bytes the parser may hold after any input at all, however long.
47 ///
48 /// The ratio ceiling above cannot see an accumulator under a single `i=`: it
49 /// retains under one byte per input byte, so no per-input-byte limit fires,
50 /// while it grows for as long as the writer keeps sending. This is the absolute
51 /// bound that catches that.
52 ///
53 /// Twice the budget rather than the budget, because the accumulators grow by
54 /// doubling: the budget is checked against length, and capacity is what the
55 /// process pays.
56 pub const MAX_RETAINED_BYTES: usize = crate::MAX_IN_FLIGHT_BYTES * 2 + 64 * 1024;
57
58 /// Slack for a parser holding a handful of small transmissions.
59 pub const RETAINED_BASE_BYTES: usize = 4096;
60
61 /// Panics if `control`'s query answer is not one a client can use.
62 ///
63 /// Returns whether the answer claimed OK, for the same reason [`check_body`]
64 /// returns a bool: a body of pure assertions replaced by `()` is invisible to
65 /// every test that passes, so the oracle has to hand back something.
66 ///
67 /// # Panics
68 ///
69 /// By design. It is an oracle, and a panic is how it reports.
70 // The reply is tens of bytes long, so the bytecount crate would be a
71 // dependency bought for nothing.
72 #[allow(clippy::naive_bytecount)]
73 pub fn check_query_response(control: &Control) -> bool {
74 let reply = query_response(control);
75 assert!(
76 reply.starts_with(b"\x1b_G"),
77 "query answer is not an APC: {reply:?}"
78 );
79 assert!(
80 reply.ends_with(b"\x1b\\"),
81 "query answer has no string terminator: {reply:?}"
82 );
83 // Exactly two ESCs, the introducer and the terminator. A third would end
84 // the string early and leave the rest of the answer on the client's screen.
85 assert_eq!(
86 reply.iter().filter(|&&b| b == 0x1b).count(),
87 2,
88 "query answer contains an embedded escape: {reply:?}"
89 );
90 let text = std::str::from_utf8(&reply).expect("query answer is ASCII");
91 let id = control.id.unwrap_or(0);
92 assert!(
93 text.contains(&format!("i={id};")),
94 "query answer is addressed to nobody: {text:?}"
95 );
96 // Direct is the only medium the host can satisfy. An OK for any other
97 // promises a picture that never arrives, and the client stops looking for
98 // another way to send it.
99 let claims_ok = text.contains(";OK");
100 let satisfiable =
101 control.format.is_some() && matches!(control.medium, None | Some(Medium::Direct));
102 assert_eq!(
103 claims_ok, satisfiable,
104 "query answered {text:?} for format {:?} medium {:?}",
105 control.format, control.medium
106 );
107 claims_ok
108 }
109
110 /// Panics if the same payload sent as chunks does not arrive as the same bytes.
111 ///
112 /// Returns how many chunks it took, for the same reason as the rest of this
113 /// module: an oracle that returns nothing cannot be observed to have run.
114 ///
115 /// # Panics
116 ///
117 /// By design.
118 /// How wide a chunk to cut the encoded payload into: roughly a third of it,
119 /// rounded to a whole number of base64 quanta.
120 ///
121 /// Chunk boundaries are multiples of four, which is what the protocol requires
122 /// of a sender: each chunk is decoded on its own, so a boundary inside a quantum
123 /// would not be decodable by any implementation.
124 ///
125 /// The floor of one quantum is load-bearing rather than defensive. The walk
126 /// below consumes `chunk_len` bytes per turn, so a width of zero does not
127 /// terminate, and the arithmetic here is the only thing that could produce one.
128 /// Named and floored, it is a thing a test can state instead of a mutant that
129 /// spends five minutes not answering.
130 fn chunk_len_for(encoded_len: usize) -> usize {
131 let quanta = encoded_len.div_ceil(4);
132 (4 * quanta.div_ceil(3)).max(4)
133 }
134
135 fn check_chunk_equivalence(action: char, payload: &[u8]) -> usize {
136 if payload.is_empty() {
137 return 0;
138 }
139 let encoded = B64.encode(payload);
140 let chunk_len = chunk_len_for(encoded.len());
141
142 let mut p = Parser::new();
143 let mut first = true;
144 let mut rest = encoded.as_str();
145 let mut got = None;
146 let mut chunks = 0;
147 while !rest.is_empty() {
148 chunks += 1;
149 // At least one byte, whatever the width says. The walk's termination
150 // is then a property of the loop rather than of the arithmetic above
151 // it, so a width that comes back wrong is a failed assertion below
152 // instead of a run that never ends.
153 let take = chunk_len.clamp(1, rest.len());
154 let (head, tail) = rest.split_at(take);
155 rest = tail;
156 let more = if rest.is_empty() { "0" } else { "1" };
157 let body = if first {
158 format!("Ga={action},i=4242,m={more};{head}")
159 } else {
160 format!("Gi=4242,m={more};{head}")
161 };
162 first = false;
163 if let Some(cmd) = p.feed(body.as_bytes()) {
164 got = Some(cmd);
165 }
166 }
167
168 let chunked = match got {
169 Some(Command::Transmit { payload, .. } | Command::FrameAppend { payload, .. }) => payload,
170 Some(other) => panic!("chunked {action} came back as {other:?}"),
171 None => panic!(
172 "chunked {action} of {} bytes never completed",
173 payload.len()
174 ),
175 };
176 assert_eq!(
177 chunked.len(),
178 payload.len(),
179 "chunked payload is {} bytes, single-shot was {}",
180 chunked.len(),
181 payload.len()
182 );
183 assert!(
184 chunked == payload,
185 "chunked payload differs from the single-shot one"
186 );
187 assert_eq!(
188 p.pending_transmissions(),
189 0,
190 "a completed transmission was left in flight"
191 );
192 chunks
193 }
194
195 /// Feed one APC body to a fresh parser and hold what comes out to everything
196 /// above.
197 ///
198 /// Returns whether a command was produced, for the same reason
199 /// `git_command::oracle::check_line` returns a bool: without a return value
200 /// nothing can observe this function running at all, and `cargo mutants`
201 /// replacing the body with `()` would leave every test passing.
202 ///
203 /// # Panics
204 ///
205 /// By design, on any violation.
206 /// The base64 characters in `body`: everything after the first `;`.
207 ///
208 /// Named because the bound it feeds is an upper one, and every mutation of this
209 /// arithmetic makes it looser. A looser upper bound is still satisfied by a
210 /// correct decode, so nothing in a passing run disagrees with a mutant here.
211 fn b64_len_of(body: &[u8]) -> usize {
212 body.iter()
213 .position(|&b| b == b';')
214 .map_or(0, |i| body.len() - i - 1)
215 }
216
217 /// The most a parser may retain after `input_len` bytes of input.
218 ///
219 /// Same reason as [`b64_len_of`]: it is a ceiling, so every mutation raises it
220 /// and a well-behaved parser stays under both.
221 fn retained_ceiling(input_len: usize) -> usize {
222 RETAINED_BASE_BYTES + input_len.saturating_mul(MAX_RETAINED_PER_INPUT_BYTE)
223 }
224
225 pub fn check_body(body: &[u8]) -> bool {
226 let mut p = Parser::new();
227 let Some(cmd) = p.feed(body) else {
228 return false;
229 };
230 // A body that produced a command left nothing behind, unless it opened a
231 // chunked transmission, which returns None and never reaches here.
232 assert_eq!(
233 p.pending_transmissions(),
234 0,
235 "a single body both completed and stayed in flight"
236 );
237
238 match &cmd {
239 Command::Query { control } => {
240 check_query_response(control);
241 }
242 Command::Transmit { control, payload } | Command::FrameAppend { control, payload } => {
243 // base64 carries three bytes in every four characters, so a decoded
244 // payload longer than that is the accumulator's own arithmetic
245 // disagreeing with itself.
246 let b64_len = b64_len_of(body);
247 assert!(
248 payload.len() <= b64_len.div_ceil(4) * 3,
249 "decoded {} bytes out of {b64_len} base64 characters",
250 payload.len()
251 );
252 let action = if matches!(cmd, Command::FrameAppend { .. }) {
253 'f'
254 } else {
255 control.action
256 };
257 check_chunk_equivalence(action, payload);
258 }
259 Command::Place { .. } | Command::Delete { .. } | Command::FrameCompose { .. } => {}
260 }
261 true
262 }
263
264 /// Split `input` into APC bodies and run a whole session through one parser.
265 ///
266 /// The split is on ESC, and a leading `_` and trailing `\` are stripped, so a
267 /// captured `\e_G…\e\` stream from a real client is a seed as it stands rather
268 /// than in a format of this harness's invention.
269 ///
270 /// Returns how many bodies were fed. See [`check_body`] for why it returns
271 /// anything at all.
272 ///
273 /// # Panics
274 ///
275 /// By design, on any violation.
276 pub fn check_bodies(input: &[u8]) -> usize {
277 let mut session = Parser::new();
278 let mut fed = 0;
279 for piece in input.split(|&b| b == 0x1b) {
280 let piece = piece.strip_prefix(b"_").unwrap_or(piece);
281 let piece = piece.strip_suffix(b"\\").unwrap_or(piece);
282 if piece.is_empty() {
283 continue;
284 }
285 fed += 1;
286 // The session parser is what carries chunk state between bodies, and
287 // it is the one whose retained state is bounded below.
288 if let Some(Command::Query { control }) = session.feed(piece) {
289 check_query_response(&control);
290 }
291 // Every body is also checked on its own, where a completed command can
292 // be held to the properties that need one.
293 check_body(piece);
294 // Per body, not only at the end. The cap is what keeps the map from
295 // growing with the id space, and a parser that has stopped enforcing
296 // it gets slower with every body it takes: checked once at the end,
297 // the oracle spends the whole input finding that out.
298 assert!(
299 session.pending_transmissions() <= crate::MAX_IN_FLIGHT_TRANSMISSIONS,
300 "{} transmissions in flight after {fed} bodies, over the cap",
301 session.pending_transmissions()
302 );
303 }
304
305 let retained = session.pending_bytes();
306 let ceiling = retained_ceiling(input.len());
307 assert!(
308 retained <= ceiling,
309 "parser holds {retained} bytes after {} bytes of input, over the {ceiling} ceiling",
310 input.len()
311 );
312 assert!(
313 retained <= MAX_RETAINED_BYTES,
314 "parser holds {retained} bytes, over the {MAX_RETAINED_BYTES} absolute ceiling"
315 );
316 assert!(
317 session.pending_transmissions() <= fed.min(crate::MAX_IN_FLIGHT_TRANSMISSIONS),
318 "{} transmissions in flight after {fed} bodies",
319 session.pending_transmissions()
320 );
321 fed
322 }
323
324 #[cfg(test)]
325 mod tests {
326 //! Unit tests for the oracle's own decisions.
327 //!
328 //! The oracle asserts things about the crate; nothing asserted anything
329 //! about the oracle. Every function below is either a ceiling the crate is
330 //! held to, or a piece of arithmetic that decides how much of the input the
331 //! oracle looks at. Neither can be observed through a passing run: a looser
332 //! ceiling is still satisfied by a correct parser, and a narrower walk still
333 //! agrees with everything it did check.
334
335 use super::{
336 MAX_RETAINED_BYTES, RETAINED_BASE_BYTES, b64_len_of, check_body, check_chunk_equivalence,
337 check_query_response, chunk_len_for, retained_ceiling,
338 };
339 use crate::{Control, Format, Medium};
340 use base64::{Engine, engine::general_purpose::STANDARD as B64};
341
342 #[test]
343 fn the_absolute_retention_ceiling_is_two_budgets_and_a_slack() {
344 // Written out, so a mutant rewriting the expression in the source has
345 // nothing here to agree with.
346 assert_eq!(MAX_RETAINED_BYTES, 134_283_264);
347 assert_eq!(RETAINED_BASE_BYTES, 4096);
348 }
349
350 #[test]
351 fn the_per_input_ceiling_is_the_base_plus_four_per_byte() {
352 assert_eq!(retained_ceiling(1000), 8096);
353 assert_eq!(retained_ceiling(0), RETAINED_BASE_BYTES);
354 }
355
356 #[test]
357 fn the_chunk_width_is_a_third_of_the_payload_in_whole_quanta() {
358 // 128 encoded characters is 32 quanta; a third of that, rounded up, is
359 // 11 quanta of four bytes each.
360 assert_eq!(chunk_len_for(128), 44);
361 }
362
363 #[test]
364 fn the_chunk_width_never_falls_below_one_quantum() {
365 // The walk consumes chunk_len bytes a turn, so a zero here does not
366 // terminate. This is the floor that makes that unrepresentable.
367 assert_eq!(chunk_len_for(0), 4);
368 assert_eq!(chunk_len_for(4), 4);
369 assert!(chunk_len_for(3) >= 4);
370 }
371
372 #[test]
373 fn the_base64_length_is_what_follows_the_first_semicolon() {
374 assert_eq!(b64_len_of(b"a=T,f=32;QUJD"), 4);
375 assert_eq!(
376 b64_len_of(b"a=T,f=32"),
377 0,
378 "a body with no payload marker carries no base64"
379 );
380 assert_eq!(
381 b64_len_of(b"a=T;QUJD;RUZH"),
382 9,
383 "the FIRST semicolon is the separator; later ones are payload"
384 );
385 }
386
387 #[test]
388 fn chunk_equivalence_reports_how_many_chunks_it_took() {
389 // 96 bytes encode to 128 characters, which is three chunks of 44.
390 assert_eq!(check_chunk_equivalence('T', &[0x5A; 96]), 3);
391 assert_eq!(
392 check_chunk_equivalence('T', &[]),
393 0,
394 "an empty payload is not chunked at all"
395 );
396 }
397
398 #[test]
399 fn check_body_reports_whether_a_command_came_out() {
400 let body = format!("Ga=T,f=32,s=2,v=2;{}", B64.encode([0x11u8; 16]));
401 assert!(check_body(body.as_bytes()), "a valid transmit yields one");
402 assert!(
403 !check_body(b"Gnot-a-command"),
404 "a body that parses to nothing yields none"
405 );
406 }
407
408 #[test]
409 fn the_query_answer_says_ok_only_for_a_medium_the_host_can_serve() {
410 let direct = Control {
411 action: 'q',
412 format: Some(Format::Rgba),
413 medium: Some(Medium::Direct),
414 id: Some(4242),
415 ..Control::default()
416 };
417 assert!(check_query_response(&direct), "inline base64 is servable");
418
419 let from_file = Control {
420 medium: Some(Medium::File),
421 ..direct.clone()
422 };
423 assert!(
424 !check_query_response(&from_file),
425 "a file transfer must not be answered OK"
426 );
427
428 let no_format = Control {
429 format: None,
430 ..direct
431 };
432 assert!(
433 !check_query_response(&no_format),
434 "a query naming no format is not something to say OK to"
435 );
436 }
437 }
438