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

ntfs_core/
index.rs
