Chỉ mục (Indexes)
NTFS sử dụng rất nhiều cấu trúc dữ liệu chỉ mục. Trong NTFS,
chỉ mục là một tập hợp các attribute được xếp thứ tự. Ví dụ: lập chỉ mục các
attribute $FILE_NAME trong mỗi thư mục.
Phần này sẽ trình bày kiến thức cơ bản liên quan đến chỉ mục
và ứng dụng của chỉ mục trong NTFS.
B-Tree
NTFS sử dụng B-tree để sắp xếp các attribute.
Cây (tree): là một cấu trúc dữ liệu được sử dụng rộng rãi
gồm một tập hợp các nút (tiếng Anh: node) được liên kết với nhau theo
quan hệ cha-con. (theo wikipedia). Ví dụ hình (A) dưới đây, cây gồm nút A liên
kết với hai nút B và C, nút B liên kết với nút D và E. Nút cha là nút nối tới
nút khác, nút được nối tới gọi là nút con (nút A là nút cha của hai nút con B
và C). Nút lá là nút không được nối tới nút con nào khác (C, D, E là những nút
lá). Cây nhị phân là cây mà mỗi nút có nhiều nhất hai nút con.
Biểu diễn dữ liệu
theo cấu trúc cây giúp việc sắp xếp và tìm kiếm dữ liệu dễ dàng và hiệu quả. Ví
dụ ở hình trên, cây (B) đã được gán giá trị cho mỗi nút, giả sử muốn tìm kiếm
một giá trị, thực hiện so sánh giá trị cần tìm với nút gốc, nếu nhỏ hơn nút
gốc, việc tìm kiếm sẽ được thực hiện ở nhánh bên trái của cây; ngược lại nếu
lớn hơn nút gốc, việc tìm kiếm sẽ được thực hiện ở nhánh bên phải của cây. Ví
dụ, cần tìm nút có giá trị 6, do 6 nhỏ hơn 7 nên tìm kiếm nhánh bên trái, do 6
lớn hơn 5 nên tìm kiếm nhánh bên phải, tìm được nút có giá trị 6 sau ba lần so
sánh.
Hệ thống NTFS sử dụng B-tree. B-tree cũng tương tự như cây
nhị phân, chỉ khác là số nút con của mỗi nút trong (không phải nút lá) có thể
lớn hơn hai. Thực tế, số nút con của mỗi nút trong phụ thuộc vào số giá trị tại
mỗi nút; cụ thể, luôn nhỏ hơn hoặc bằng số giá trị tại mỗi nút + 1. Ví dụ:
trong cây nhị phân, mỗi nút chỉ lưu một giá trị nên có hai nút con. Nếu một nút
lưu được năm giá trị, sẽ có sáu nút con.
Hình sau thể hiện một B-tree.
Ở hình trên, giá trị tại mỗi nút là tên của các tập tin. Nút
A có ba giá trị nên có bốn nút con. Giả sử cần tìm kiếm tập tin ggg.txt, duyệt
trong nút gốc (A), theo thứ tự bảng chữ cái, sẽ xác định được ggg.txt nằm giữa
eee.txt và lll.txt. Do vậy, sẽ thực hiện tìm kiếm tập tin ggg.txt trong nút C.
Thêm và xóa một giá
trị trên B-tree
Phần này sẽ giải thích tại sao lại rất khó tìm được tên của
một tập tin đã bị đánh dấu xóa trong hệ thống NTFS.
Giả sử mỗi nút chỉ cho phép chứa ba tên tập tin, thực hiện
thêm tập tin jjj.txt vào B-tree ở ví dụ trên. Công việc tưởng như đơn giản,
nhưng thực tế để thêm tập tin jjj.txt, hệ thống đã phải thực hiện xóa hai nút
và tạo mới năm nút trên B-tree.
Theo thứ tự bảng chữ cái, vị trí thích hợp của jjj.txt là
cuối nút C, theo sau tập tin iii.txt. Như hình dưới đây.
Tuy nhiên, nút C lại có tới bốn tập tin (quy định chỉ cho
phép ba tập tin). Do đó, phải tách nút C làm hai, chuyển ggg.txt lên mức trên,
tạo ra hai nút F và G thay thế cho nút C. Hình minh họa dưới đây.
Bây giờ, đến lượt nút A lại có tới bốn giá trị (bốn tập
tin). Bởi vậy, lại phải chia nút A làm hai, tạo thêm một nút ở mức trên cùng để
lưu ggg.txt. Hình minh họa sau.
Như vậy, để thêm jjj.txt, hệ thống đã phải xóa đi hai nút A
và C, thêm vào các nút F, G, H, I và J. Các tập tin đã bị đánh dấu xóa nằm
trong nút A hoặc C sẽ bị mất, vì rất khó để tìm lại.
Bây giờ thực hiện xóa tập tin zzz.txt. Hệ thống chỉ cần gỡ
bỏ tên của tập tin khỏi nút E và không cần thực hiện thêm bất kì thay đổi nào
khác. Tùy thuộc từng hệ thống, phần thông tin chi tiết của tập tin zzz.txt có
thể vẫn tồn tại trong nút E và có thể thực hiện khôi phục lại được.
Xem xét tình huống phức tạp hơn, thực hiện xóa tập tin
fff.txt. Xóa fff.txt làm nút F bị trống. Theo tính chất của B-tree: số nút con
của mỗi nút trong luôn bằng số giá trị của mỗi nút + 1. Vì vậy, cần chèn giá
trị vào nút F. Chuyển eee.txt từ nút I vào nút F, chuyển bbb.txt từ nút B tới nút I.
Kết quả được thể hiện ở hình bên dưới.
Lưu ý: một số công cụ phân tích/khôi phục dữ liệu sẽ tìm
thấy giá trị bbb.txt vẫn còn tồn tại trong nút B, và kết luận bbb.txt đã bị xóa,
thực tế bbb.txt chỉ bị chuyển từ nút B sang nút I. Do vậy, trong phân tích và
khôi phục dữ liệu cho hệ thống NTFS, rất khó đoán trước kết quả.
---------------------------
Tham khảo
[1] Brian Carrie, File
System Forensic Analysis, Addison Wesley Professional, 2005
----------------------
Cập nhật: 2013/10/11