FAT Concepts and Analysis

File Name Category

The file name category of data includes the data that assigns human readable names to inodes and other metadata. This section describes where UFS stores the data and how we can analyze them.

Overview

UFS1 and UFS2 use the same file name data structure that ExtX does, so this section is only a review of the key ideas that were already described in the "File Name Category" section of Chapter 14. The directory entry data structure stores the file's name, inode address, and type value. The length of the structure is based on the name length, which has a maximum file length of 255 characters. The name is stored in ASCII and is null terminated, although an ExtX name is not null terminated.

The directory entry structures are located in the blocks allocated to a directory. Directories are like normal files except that their type is set to directory in the mode field. The first two entries in a directory should be for the '.' and '..' directories. Each entry has a length value that points to the next entry, and the length of the final entry points to the end of the block. When a file is deleted, the length of the previous entry is increased so that it points to the entry after the deleted entry. Refer to Chapter 14 for diagrams of this. The root directory is always located in inode 2. Chapter 17 contains the directory entry data structure and an example from a file system image. Here is the output of running fls on our example file system image that is processed in the next chapter.

# fls -f openbsd a openbsd.dd 1921 d/d 1921: . d/d 2: .. r/r 1932: file1.txt r/r 1933: file8.txt r/r 1934: file7.txt r/- * 1935: file6.txt [REMOVED]

The entry with a "*" next to it is a deleted file. The first column contains the file type as reported in the directory entry and then in the inode. We can see that UFS clears the file type value in the inode because the deleted file name does not have a type in its inode column.

UFS supports both hard and soft links so that multiple names can be used for a single file or directory. Hard links are a second name for a file or directory in the same file system. When a hard link is created, a new directory entry is allocated, and it points to the inode of the original file. The link count in the inode is incremented to account for the new name. Soft links are created using symbolic links. A symbolic link stores the path of the destination file in either a fragment or in the 60 bytes usually used for block pointers. UFS2 has 64-bit pointers instead of 32-bit pointers, so it has 120 bytes in which to store the path. Chapter 14 has figures of hard and soft links.

Note that directories in Unix are used as both a place to store file names and as mounting points for other file systems. Refer to Chapter 14 for examples where you might not find a name you are looking for in a directory because there was another volume mounted there. Although not enabled by default, many BSD systems support a union mount, where the files in the directory that are being used as a mounting point will still be visible. The OS merges the files from the mount directory and the root directory of the volume so that they appear as one.

Allocation Algorithms

With BSD and Solaris systems, directory entries are allocated on a first available strategy. The OS scans each of the directory entries and compares the reported entry length with the length that is actually needed based on the file name length. If the reported length is larger and the new file can fit inside that space, it is placed there. The directory blocks are wiped with zeros when they are allocated. Directory entry structures will not cross a block boundary.

When a file is deleted, the reported length of the previous entry is increased to point to the entry after the deleted file. BSD systems do not wipe the type or inode fields, although Solaris does. This means that you can get temporal data about the file name from a BSD system, but its direct block pointers will likely have been wiped. Other OSes could choose other techniques and wipe the name.

Analysis Techniques

Analysis of the file name category involves listing the files and subdirectories in a given directory and looking for some pattern and specific name. To do this, we generally need to first locate the root directory. The root directory is always located at inode 2, so we can locate its content using the same techniques that we saw in the section titled, "Metadata Category." After the contents of a directory have been located, we need to process them as a list of directory entries.

When processing the directory contents, the next allocated entry can be found by using the pointer in the current entry. To find deleted entries, the space in between the end of the file name of the one allocated entry and the start of the next allocated entry is examined. If any data there meets the format of a directory entry, it was probably there from a deleted file. When we locate a file or directory that we are interested in, we can get more details about it by identifying its corresponding inode address and processing it. Many tools do this automatically and list the time information with the name information. Refer to Chapter 14 for a figure and scenario on how the sequence of file deletions might be determined.

When a directory is deleted, the link between its inode and blocks will likely be deleted. To search for the contents of a deleted directory, we can look for the . and .. entries. Directory entries do not cross block segments, and therefore each block should start with a new entry.

Analysis Considerations

The design of the directory entry and the implementation in most systems allows deleted file names to be easily located, and the inode value is not cleared in BSD systems so the file metadata can also be found. Solaris wipes this value, so no additional data can be found. If a deleted directory entry is found and its inode value exists, it can be difficult to determine if the inode contents correspond to the file name or if the inode was reallocated and the contents correspond to a different file. A basic test for this is to determine if the inode is currently allocated. If it is, the inode could have been reallocated or the file could have been moved within the same file system and you are looking at the original location. Many OSes clear the mode field in a UFS inode, so the file type cannot be compared with the type in the directory entry.

It could be possible for data to be hidden in directory entry structures. The space between the last directory entry and the end of the block is unused and could contain data. However, this is a dangerous hiding technique because the OS could overwrite it when a new file name is created.