Dia cung - 16 - NTFS - Indexes

(tiếp theo của Dia cung 15)



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