ntfs_core/
index.rs

1//! Directory index B-tree: `$INDEX_ROOT` (resident) and the `INDX` buffers of
2//! `$INDEX_ALLOCATION` (non-resident).
3//!
4//! A directory's children are kept in a B-tree of *index entries*, each holding
5//! a file reference and an embedded `$FILE_NAME`. Small directories fit entirely
6//! in the resident `$INDEX_ROOT`; larger ones spill into fixed-size `INDX`
7//! buffers (each `INDX`-signed and protected by the same update-sequence fixup
8//! as an MFT record).
9//!
10//! Entry, node, and stream bounds are all validated against the buffer; a
11//! crafted index cannot drive an out-of-bounds read or a non-terminating walk.
12
13use forensicnomicon::ntfs::SIGNATURE_INDX as INDX_SIGNATURE;
14
15use crate::error::{NtfsError, Result};
16use crate::file_name::{FileName, FileReference};
17use crate::record::apply_fixup;
18
19/// Index-header field offsets (relative to the index header start).
20mod ih {
21    pub const FIRST_ENTRY: usize = 0x00;
22    pub const TOTAL_SIZE: usize = 0x04;
23    pub const FLAGS: usize = 0x0C;
24}
25/// Index-header flag: this index has an `$INDEX_ALLOCATION` (it is "large").
26const IH_FLAG_LARGE: u32 = 0x01;
27/// Bytes of the fixed index header.
28const INDEX_HEADER_LEN: usize = 0x10;
29
30/// Index-entry field offsets.
31mod ie {
32    pub const FILE_REFERENCE: usize = 0x00;
33    pub const ENTRY_LENGTH: usize = 0x08;
34    pub const STREAM_LENGTH: usize = 0x0A;
35    pub const FLAGS: usize = 0x0C;
36    pub const STREAM: usize = 0x10;
37}
38/// Entry flag: the entry points to a child node (its last 8 bytes are a VCN).
39const IE_FLAG_SUBNODE: u8 = 0x01;
40/// Entry flag: this is the final entry in the node.
41const IE_FLAG_LAST: u8 = 0x02;
42/// Minimum entry size (the fixed entry header).
43const ENTRY_MIN: usize = 0x10;
44/// `$INDEX_ROOT` fixed header before its index header.
45const ROOT_HEADER_LEN: usize = 0x10;
46/// `INDX` buffer fixed header before its index header.
47const INDX_HEADER_LEN: usize = 0x18;
48/// Loop cap on entries per node.
49const MAX_ENTRIES: usize = 1 << 20;
50
51/// One directory index entry.
52#[derive(Debug, Clone, PartialEq, Eq)]
53pub struct IndexEntry {
54    /// File reference of the entry's target (0 for the terminal entry).
55    pub file_reference: FileReference,
56    /// The embedded `$FILE_NAME`, or `None` for the terminal entry.
57    pub file_name: Option<FileName>,
58    /// VCN of the child index buffer, if this entry has a sub-node.
59    pub child_vcn: Option<u64>,
60}
61
62/// A parsed `$INDEX_ROOT`.
63#[derive(Debug, Clone, PartialEq, Eq)]
64pub struct IndexRoot {
65    /// The attribute type this index is keyed on (usually `$FILE_NAME` = 0x30).
66    pub indexed_type: u32,
67    /// `true` if the directory also has an `$INDEX_ALLOCATION`.
68    pub is_large: bool,
69    /// The entries held directly in the root node.
70    pub entries: Vec<IndexEntry>,
71}
72
73impl IndexRoot {
74    /// Parse an `$INDEX_ROOT` attribute value.
75    ///
76    /// # Errors
77    ///
78    /// [`NtfsError::TooShort`] / [`NtfsError::BadIndex`] on malformed input.
79    pub fn parse(content: &[u8]) -> Result<IndexRoot> {
80        if content.len() < ROOT_HEADER_LEN + INDEX_HEADER_LEN {
81            return Err(NtfsError::TooShort {
82                what: "$INDEX_ROOT",
83                need: ROOT_HEADER_LEN + INDEX_HEADER_LEN,
84                got: content.len(),
85            });
86        }
87        let indexed_type = u32::from_le_bytes(content[0x00..0x04].try_into().unwrap());
88        let (entries, is_large) = parse_index_header(content, ROOT_HEADER_LEN)?;
89        Ok(IndexRoot {
90            indexed_type,
91            is_large,
92            entries,
93        })
94    }
95}
96
97/// Parse the index header at `base` and the entries it points to.
98/// Returns the entries and the "large index" flag.
99fn parse_index_header(node: &[u8], base: usize) -> Result<(Vec<IndexEntry>, bool)> {
100    let header_end = base
101        .checked_add(INDEX_HEADER_LEN)
102        .ok_or(NtfsError::BadIndex("index header overflow"))?;
103    if header_end > node.len() {
104        return Err(NtfsError::BadIndex("index header past buffer"));
105    }
106    let u32at = |o: usize| u32::from_le_bytes(node[base + o..base + o + 4].try_into().unwrap());
107    let first_entry = u32at(ih::FIRST_ENTRY) as usize;
108    let total_size = u32at(ih::TOTAL_SIZE) as usize;
109    let is_large = u32at(ih::FLAGS) & IH_FLAG_LARGE != 0;
110
111    let start = base
112        .checked_add(first_entry)
113        .ok_or(NtfsError::BadIndex("first-entry offset overflow"))?;
114    let end = base
115        .checked_add(total_size)
116        .ok_or(NtfsError::BadIndex("total-size overflow"))?;
117    if start < header_end || end > node.len() || start > end {
118        return Err(NtfsError::BadIndex("index entry region out of bounds"));
119    }
120    let entries = parse_entries(node, start, end)?;
121    Ok((entries, is_large))
122}
123
124/// Parse the entries in the byte range `[start, end)` of `node`.
125///
126/// # Errors
127///
128/// [`NtfsError::BadIndex`] for an undersized / non-advancing entry, or a stream
129/// or sub-node VCN that would read outside the entry.
130pub fn parse_entries(node: &[u8], start: usize, end: usize) -> Result<Vec<IndexEntry>> {
131    if end > node.len() || start > end {
132        return Err(NtfsError::BadIndex("entry region out of bounds"));
133    }
134    let mut entries = Vec::new();
135    let mut pos = start;
136
137    for _ in 0..MAX_ENTRIES {
138        if pos + ENTRY_MIN > end {
139            break; // no room for another entry header
140        }
141        let entry_length = u16::from_le_bytes(
142            node[pos + ie::ENTRY_LENGTH..pos + ie::ENTRY_LENGTH + 2]
143                .try_into()
144                .unwrap(),
145        ) as usize;
146        if entry_length < ENTRY_MIN {
147            return Err(NtfsError::BadIndex("entry length below minimum"));
148        }
149        let entry_end = pos
150            .checked_add(entry_length)
151            .ok_or(NtfsError::BadIndex("entry length overflow"))?;
152        if entry_end > end {
153            return Err(NtfsError::BadIndex("entry extends past node"));
154        }
155
156        let flags = node[pos + ie::FLAGS];
157        let is_last = flags & IE_FLAG_LAST != 0;
158        let file_reference = FileReference::from_u64(u64::from_le_bytes(
159            node[pos + ie::FILE_REFERENCE..pos + ie::FILE_REFERENCE + 8]
160                .try_into()
161                .unwrap(),
162        ));
163
164        let child_vcn = if flags & IE_FLAG_SUBNODE != 0 {
165            if entry_end < pos + ENTRY_MIN + 8 {
166                return Err(NtfsError::BadIndex("sub-node VCN does not fit in entry"));
167            }
168            let vcn_pos = entry_end - 8;
169            Some(u64::from_le_bytes(
170                node[vcn_pos..vcn_pos + 8].try_into().unwrap(),
171            ))
172        } else {
173            None
174        };
175
176        let file_name = if is_last {
177            None
178        } else {
179            let stream_length = u16::from_le_bytes(
180                node[pos + ie::STREAM_LENGTH..pos + ie::STREAM_LENGTH + 2]
181                    .try_into()
182                    .unwrap(),
183            ) as usize;
184            let s_start = pos + ie::STREAM;
185            let s_end = s_start
186                .checked_add(stream_length)
187                .ok_or(NtfsError::BadIndex("stream length overflow"))?;
188            if s_end > entry_end {
189                return Err(NtfsError::BadIndex("stream extends past entry"));
190            }
191            Some(FileName::parse(&node[s_start..s_end])?)
192        };
193
194        entries.push(IndexEntry {
195            file_reference,
196            file_name,
197            child_vcn,
198        });
199
200        if is_last {
201            break;
202        }
203        pos = entry_end;
204    }
205
206    Ok(entries)
207}
208
209/// Parse one `INDX` index buffer: validate the signature, apply the
210/// update-sequence fixup in place, and return its entries.
211///
212/// # Errors
213///
214/// [`NtfsError::TooShort`], [`NtfsError::BadIndex`] (bad signature), or a fixup
215/// / entry error.
216pub fn parse_index_buffer(
217    buffer: &mut [u8],
218    index_record_size: usize,
219    sector_size: usize,
220) -> Result<Vec<IndexEntry>> {
221    if buffer.len() < index_record_size || index_record_size < INDX_HEADER_LEN + INDEX_HEADER_LEN {
222        return Err(NtfsError::TooShort {
223            what: "INDX buffer",
224            need: index_record_size.max(INDX_HEADER_LEN + INDEX_HEADER_LEN),
225            got: buffer.len(),
226        });
227    }
228    let buf = &mut buffer[..index_record_size];
229    if buf[0..4] != INDX_SIGNATURE {
230        return Err(NtfsError::BadIndex("INDX signature missing"));
231    }
232    apply_fixup(buf, sector_size)?;
233    let (entries, _is_large) = parse_index_header(buf, INDX_HEADER_LEN)?;
234    Ok(entries)
235}
236
237#[cfg(test)]
238mod tests {
239    use super::*;
240    use forensicnomicon::ntfs::filename_namespace;
241
242    fn fname(parent: u64, name: &str) -> Vec<u8> {
243        let units: Vec<u16> = name.encode_utf16().collect();
244        let mut c = vec![0u8; 0x42 + units.len() * 2];
245        c[0..8].copy_from_slice(&parent.to_le_bytes());
246        c[0x40] = units.len() as u8;
247        c[0x41] = filename_namespace::WIN32;
248        for (i, u) in units.iter().enumerate() {
249            c[0x42 + i * 2..0x42 + i * 2 + 2].copy_from_slice(&u.to_le_bytes());
250        }
251        c
252    }
253
254    fn entry(file_ref: u64, name: &str) -> Vec<u8> {
255        let fnc = fname(5, name);
256        let len = (ie::STREAM + fnc.len() + 7) & !7;
257        let mut e = vec![0u8; len];
258        e[ie::FILE_REFERENCE..ie::FILE_REFERENCE + 8].copy_from_slice(&file_ref.to_le_bytes());
259        e[ie::ENTRY_LENGTH..ie::ENTRY_LENGTH + 2].copy_from_slice(&(len as u16).to_le_bytes());
260        e[ie::STREAM_LENGTH..ie::STREAM_LENGTH + 2]
261            .copy_from_slice(&(fnc.len() as u16).to_le_bytes());
262        e[ie::FLAGS] = 0;
263        e[ie::STREAM..ie::STREAM + fnc.len()].copy_from_slice(&fnc);
264        e
265    }
266
267    fn end_entry() -> Vec<u8> {
268        let mut e = vec![0u8; ENTRY_MIN];
269        e[ie::ENTRY_LENGTH..ie::ENTRY_LENGTH + 2]
270            .copy_from_slice(&(ENTRY_MIN as u16).to_le_bytes());
271        e[ie::FLAGS] = IE_FLAG_LAST;
272        e
273    }
274
275    fn make_root(is_large: bool, entries: &[Vec<u8>]) -> Vec<u8> {
276        let blob: Vec<u8> = entries.concat();
277        let total = (INDEX_HEADER_LEN + blob.len()) as u32;
278        let mut c = vec![0u8; ROOT_HEADER_LEN + INDEX_HEADER_LEN + blob.len()];
279        c[0x00..0x04].copy_from_slice(&0x30u32.to_le_bytes()); // indexed type = $FILE_NAME
280        let base = ROOT_HEADER_LEN;
281        c[base + ih::FIRST_ENTRY..base + ih::FIRST_ENTRY + 4]
282            .copy_from_slice(&(INDEX_HEADER_LEN as u32).to_le_bytes());
283        c[base + ih::TOTAL_SIZE..base + ih::TOTAL_SIZE + 4].copy_from_slice(&total.to_le_bytes());
284        c[base + ih::FLAGS..base + ih::FLAGS + 4]
285            .copy_from_slice(&(if is_large { IH_FLAG_LARGE } else { 0 }).to_le_bytes());
286        c[base + INDEX_HEADER_LEN..].copy_from_slice(&blob);
287        c
288    }
289
290    #[test]
291    fn parses_entries_until_last() {
292        let node = [entry(11, "alpha.txt"), entry(12, "beta.txt"), end_entry()].concat();
293        let es = parse_entries(&node, 0, node.len()).unwrap();
294        assert_eq!(es.len(), 3);
295        assert_eq!(es[0].file_reference.record_number, 11);
296        assert_eq!(es[0].file_name.as_ref().unwrap().name, "alpha.txt");
297        assert_eq!(es[1].file_name.as_ref().unwrap().name, "beta.txt");
298        assert!(es[2].file_name.is_none()); // terminal entry
299    }
300
301    #[test]
302    fn parses_small_index_root() {
303        let root = make_root(false, &[entry(20, "report.docx"), end_entry()]);
304        let ir = IndexRoot::parse(&root).unwrap();
305        assert_eq!(ir.indexed_type, 0x30);
306        assert!(!ir.is_large);
307        assert_eq!(ir.entries.len(), 2);
308        assert_eq!(
309            ir.entries[0].file_name.as_ref().unwrap().name,
310            "report.docx"
311        );
312    }
313
314    #[test]
315    fn large_index_root_flag_detected() {
316        let root = make_root(true, &[end_entry()]);
317        assert!(IndexRoot::parse(&root).unwrap().is_large);
318    }
319
320    #[test]
321    fn subnode_vcn_is_read() {
322        // A sub-node entry reserves 8 extra bytes after the $FILE_NAME stream
323        // for the child VCN (the stream length is unchanged).
324        let mut e = entry(30, "dir");
325        let new_len = e.len() + 8;
326        e.resize(new_len, 0);
327        e[ie::ENTRY_LENGTH..ie::ENTRY_LENGTH + 2].copy_from_slice(&(new_len as u16).to_le_bytes());
328        e[ie::FLAGS] = IE_FLAG_SUBNODE;
329        e[new_len - 8..new_len].copy_from_slice(&7u64.to_le_bytes());
330        let node = [e, end_entry()].concat();
331        let es = parse_entries(&node, 0, node.len()).unwrap();
332        assert_eq!(es[0].child_vcn, Some(7));
333        assert_eq!(es[0].file_name.as_ref().unwrap().name, "dir");
334    }
335
336    #[test]
337    fn parses_indx_buffer_with_fixup() {
338        // 512-byte INDX buffer (one sector), entries after the USA.
339        let record_size = 512usize;
340        let mut b = vec![0u8; record_size];
341        b[0..4].copy_from_slice(b"INDX");
342        let usa_offset = 0x28u16;
343        let usa_count = 2u16; // 1 USN + 1 sector
344        b[0x04..0x06].copy_from_slice(&usa_offset.to_le_bytes());
345        b[0x06..0x08].copy_from_slice(&usa_count.to_le_bytes());
346        // index header at 0x18; entries start at 0x40 (past the USA).
347        let base = INDX_HEADER_LEN;
348        let first_entry = 0x40 - base; // 0x28
349        let blob = [entry(40, "child.bin"), end_entry()].concat();
350        let total = (first_entry + blob.len()) as u32;
351        b[base + ih::FIRST_ENTRY..base + ih::FIRST_ENTRY + 4]
352            .copy_from_slice(&(first_entry as u32).to_le_bytes());
353        b[base + ih::TOTAL_SIZE..base + ih::TOTAL_SIZE + 4].copy_from_slice(&total.to_le_bytes());
354        b[0x40..0x40 + blob.len()].copy_from_slice(&blob);
355        // USA: USN sentinel at the sector tail (510), original 0 in the USA.
356        let usn = 0x0001u16;
357        b[usa_offset as usize..usa_offset as usize + 2].copy_from_slice(&usn.to_le_bytes());
358        b[510..512].copy_from_slice(&usn.to_le_bytes());
359
360        let es = parse_index_buffer(&mut b, record_size, 512).unwrap();
361        assert_eq!(es[0].file_name.as_ref().unwrap().name, "child.bin");
362    }
363
364    // ── Hardening ─────────────────────────────────────────────────────────────
365
366    #[test]
367    fn rejects_undersized_entry() {
368        let mut node = vec![0u8; 0x20];
369        node[ie::ENTRY_LENGTH..ie::ENTRY_LENGTH + 2].copy_from_slice(&4u16.to_le_bytes()); // < ENTRY_MIN
370        assert!(matches!(
371            parse_entries(&node, 0, node.len()),
372            Err(NtfsError::BadIndex(_))
373        ));
374    }
375
376    #[test]
377    fn rejects_entry_past_node_end() {
378        let mut node = vec![0u8; 0x20];
379        node[ie::ENTRY_LENGTH..ie::ENTRY_LENGTH + 2].copy_from_slice(&0x100u16.to_le_bytes());
380        assert!(matches!(
381            parse_entries(&node, 0, node.len()),
382            Err(NtfsError::BadIndex(_))
383        ));
384    }
385
386    #[test]
387    fn rejects_indx_bad_signature() {
388        let mut b = vec![0u8; 512];
389        b[0..4].copy_from_slice(b"BADX");
390        assert!(matches!(
391            parse_index_buffer(&mut b, 512, 512),
392            Err(NtfsError::BadIndex(_))
393        ));
394    }
395
396    #[test]
397    fn index_root_rejects_too_short() {
398        assert!(matches!(
399            IndexRoot::parse(&[0u8; 4]),
400            Err(NtfsError::TooShort { .. })
401        ));
402    }
403
404    #[test]
405    fn index_header_rejects_past_buffer() {
406        // Fewer bytes remain than an index header needs.
407        assert!(matches!(
408            parse_index_header(&[0u8; 4], 0),
409            Err(NtfsError::BadIndex(_))
410        ));
411    }
412
413    #[test]
414    fn index_header_rejects_entry_region_out_of_bounds() {
415        let mut node = vec![0u8; INDEX_HEADER_LEN];
416        node[ih::TOTAL_SIZE..ih::TOTAL_SIZE + 4].copy_from_slice(&0xFFFFu32.to_le_bytes());
417        assert!(matches!(
418            parse_index_header(&node, 0),
419            Err(NtfsError::BadIndex(_))
420        ));
421    }
422
423    #[test]
424    fn parse_entries_rejects_region_out_of_bounds() {
425        let node = vec![0u8; 0x20];
426        assert!(matches!(
427            parse_entries(&node, 0, node.len() + 1),
428            Err(NtfsError::BadIndex(_))
429        ));
430    }
431
432    #[test]
433    fn parse_entries_stops_when_no_header_room() {
434        // Empty range: no entry header fits, so it returns empty without panic.
435        assert!(parse_entries(&[], 0, 0).unwrap().is_empty());
436    }
437
438    #[test]
439    fn rejects_subnode_vcn_not_fitting() {
440        // SUBNODE flag set but the entry is too small to hold the 8-byte VCN.
441        let mut e = end_entry();
442        e[ie::FLAGS] = IE_FLAG_SUBNODE;
443        assert!(matches!(
444            parse_entries(&e, 0, e.len()),
445            Err(NtfsError::BadIndex(_))
446        ));
447    }
448
449    #[test]
450    fn rejects_stream_extending_past_entry() {
451        let mut e = entry(11, "x.txt");
452        let big = e.len() as u16 + 0x100;
453        e[ie::STREAM_LENGTH..ie::STREAM_LENGTH + 2].copy_from_slice(&big.to_le_bytes());
454        assert!(matches!(
455            parse_entries(&e, 0, e.len()),
456            Err(NtfsError::BadIndex(_))
457        ));
458    }
459
460    #[test]
461    fn index_buffer_rejects_too_short() {
462        let mut b = vec![0u8; 16];
463        assert!(matches!(
464            parse_index_buffer(&mut b, 512, 512),
465            Err(NtfsError::TooShort { .. })
466        ));
467    }
468}
ntfs_core/index.rs

ntfs_core/
index.rs
