[FileSystem Forensics] Indexes

NTFS sử các cấu trúc dữ liệu index trong nhiều hoàn cảnh, và phần này mô tả chúng. Một index trong NTFS là một tập hợp các attributes mà được sắp xếp theo một thứ tự. Ứng dụng phổ biến nhất của một index là trong một directory bởi vì các directories chứa các $FILE_NAME attributes.

Trước phiên bản 3.0 của NTFS (trong Windows 2000), chỉ $FILE_NAME attribute nằm trong một index, nhưng bây giờ có một vài phiên bản  khác sử dụng các indexes và chúng chứa các attributes khác nhau. Ví dụ như security information được lưu trong một index, như là một quota information. Phần này cho ta thấy một index trông như thế nào và cách nó được implement.

B-Trees
Một NTFS sắp xếp các attributes theo một cây, nhất là một B-tree. Một cây là một nhóm các cấu trúc dữ liệu được gọi là các nodes mà được liên kết cùng với nhau như vậy có một head node và nó được rẽ nhánh ra các nodes khác. Xét hình 11.13(A) , ở đó ta thấy node A nằm trên đỉnh và nó liên kết tới các nodes B và C. Node B liên kết tới Node D và E. Một parent node là một node liên kết tới các nodes khác, một child node là một node được liên kết tới. Ví dụ, A là parent node của B và C, những nodes là child node của node A. Một leaf node là một node mà không có các links từ nó. các nodes C, D, và E là các leaves.

Các trees hữu dụng bởi vì chúng có thể được sử dụng dễ dàng để sắp xếp và tìm dữ liệu. Hình 11.13 (B) hiển thị cùng một tree như là tree phía bên tay trái, nhưng bây giờ là với các giá trị được gán cho mỗi node. Nếu bạn đang cố gắng từ kiếm một giá trị, bạn nên so sánh nó với root node. Nếu root node lớn hơn, chúng ta nên tìm kiếm child node phía bên tay trái. Nếu root node nhỏ hơn, chúng ta tìm kiếm child node phía bên tay phải. Ví dụ, nếu muốn tìm giá trị 6 , chúng ta so sánh nó với root node, có giá trị là 7. Node này lớn hơn, vì vậy chúng ta đi tới các child phía bên trái và so sánh với giá trị của nó, là 5. Node này nhỏ hơn nên ta đi tới child phía bên tay phải và ta đã tìm được giá trị cần tìm. Chúng ta đã tìm được giá trị với chỉ 3 phép so sánh. Chúng ta có thể tìm được giá trị 9 chỉ trong 2 phép so sánh thay vì 5 nếu giá trị được lưu trong một list.

NTFS sử dụng B-trees, tương tự với binary tree mà chúng ta mới thấy, nhưng có thể nhiều 2 children trên một node. Thông thường, số lượng children mà một node có dựa trên bao nhiêu giá trị mỗi node có thể lưu. Ví dụ, trong binary tree chúng ta lưu một giá trị trong mỗi node và có 2 children. Nếu chúng ta có thể lưu 5 giá trị trong mỗi node, chúng ta có thể có 6 children.

có nhiều biến thể của B-trees, và có các rules mà tôi sẽ mô tả ở đây bởi vì mục đích của phần này là để mô tả các concepts của chúng, không nhắm tới việc mô tả cách bạn có thể tạo một B-tree.

Trong Hình 11.14 hiển trị một B-tree với các names thay cho các số. Node A chứa 3 giá trị và 4 children. Nếu bạn đang muốn tìm kiếm file ggg.txt, bạn có thể nhìn vào các giá trị trong root node và xác định name theo alphabe nằm trong khoảng giữa eee.txt và lll.txt. Do đó, chúng ta xử lý node C và nhìn vào các giá trị của nó. Chúng tìm thấy file name trong node này.

Nào hãy phức tạp hóa vấn đề lên bằng cách nhìn vào cách các giá trị được thêm vào và xóa đi. Đó là một khái niệm quan trọng bởi vì nó giải thích tại sao các file names bị xóa rất khó để tìm thấy trong NTFS. Chúng tôi giả sử chúng ta chỉ có thể fit 3 file names trên node, và file jjj.txt được thêm vào. Thoạt nghe có vẻ dễ, nhưng bạn sẽ nhìn thấy kết quả là việc 2 nodes bị xóa đi và 5 nodes mới được tạo ra. Khi chúng ta locate nơi jjj.txt nên fit, chúng ta nhận diện được nó nên nằm tại cuối node C, theo sau iii.txt name. Hình 11.15 phía trên đỉnh cho ta thấy tình huống này, nhưng không may mắn thay, có 4 names trong node này, và nó chỉ có thể fit được 3. Do đó chúng ta chia đôi node C, di chuyển ggg.txt lên một cấp độ , và tạo các nodes F và G với các resulting names từ node C. Bạn có thể thấy hình 11.15 phía dưới.

Không may mắn thay, node A có 4 giá trị trong nó. Vì vậy chúng ta chia đôi nó và di chuyển ggg.txt tới node trên đỉnh. Kết quả cuối cùng có thể thấy trong Hình 11.16. Thêm một node làm cho di chuyển các nodes A và C và thêm vào các nodes F, G, H, I và J. Bất cứ dữ liệu còn lại nào trong các nodes A và C từ các files bị xóa phía trước đều đi mất.

Bây giờ xóa đi zzz.txt file. Hành động này remove name từ node E và không yêu cầu bất cứ thay đổi nào khác. Phụ thuộc vào việc triển khai, các chi tiết của zzz.txt vẫn có thể tồn tại trong node và có thể được phục hồi.

Để làm cho sự việc càng khó khăn hơn, xét xem nếu fff.txt bị xóa đi. Node F trở thành trống rỗng, và chúng ta cần fill vào nó. Chúng ta move eee.txt từ node I tới node F và move bbb.txt từ node B tới node I. Điều này tạo một tree mà vẫn cân bằng nơi tất cả các leaves vẫn có cùng một khoảng cách từ node H. Kết quả các bạn có thể thấy trong Figure 11.17.

Node B sẽ chứa bbb.txt trong không gian không được cấp phát (unallocated space) của nó bởi vì bbb.txt được move tới node I. Công cụ phân tích của chúng ta có thể hiển thị bbb.txt bị xóa, nhưng thực sự không phải như vậy. Nó đơn giản là bị moved bởi vì fff.txt bị xóa.

Quá trình thêm và xóa các giá trị từ tree cho ta thấy sự phức tạp của nó.