## 3 AndroStep
### MOST: Mobile Storage Analyzer  
Mobile Storage Analyzer (MOST) consists of (i) modified Linux kernel; (ii) a block analyzer which is used to extract the semantic information of a given block; and (iii) block trace utility, blktrace. To obtain correlational information among different attributes of an I/O, _i.e._, file type _vs_. randomness, block type _vs_. synchronization mode, it is mandatory that we acquire comprehensive I/O attributes, _i.e._, process ID, type of a block in the filesystem, type of a file, _etc._, for a given LBA. Modern I/O subsystem consists of a set of layers and each layer communicates with others via very well-defined narrow interface. It is not possible to access the information in the other layers. For example, it is not possible to determine whether a given block belongs to SQLite rollback journal or SQLite database table by examining the logical block address. Figure 4 illustrates the overall organization of MOST. MOST provides three features: (i) finding a file type for a given block; (ii) finding an application which accesses a given block; and (iii) finding a file for a given block even when the file has been deleted. The capability of finding a \"deleted\" file for a given block is essential in studying the I/O characteristics in Android since in \"Delete\" journal mode, SQLite deletes its rollback journal file when the transaction completes. Figure 3: Function of data collection. (**a**) Result screen; (**b**) Ranking. The first feature is block-to-file mapping. MOST can reverse-map the disk block to the respective file to which it belongs. It accepts a logical block number as an input and generates a file name. MOST uses debugfs[25] to reverse-map the block in the EXT4 file system and we developed a module to reverse-map the block for FAT32 filesystem [23]. The second feature is block address to process ID mapping. MOST can identify the original process that issued a given I/O. In Android, mmcgd daemon manages the mmc card device driver and is responsible for issuing all block I/Os. For each block access, blktrace records the process ID for each block. When blktrace is used in Android I/O stack, blktrace designates mmcgd as the process for all I/O accesses. The goal of MOST is to identify the application, app, that has issued a given I/O. For this purpose, we modified the Linux kernel. We added a block address to process ID table in the kernel which maintains a process ID for a given LBA. The entries in the table are \(<\)LBA, process ID\(>\). When the I/O scheduler inserts the I/O request into the queue, MOST inserts the \(<\)LBA, process ID\(>\) information into an entry of the mapping table. MOST examines table posthumously to retrieve ID of the original process that issued a given LBA access. MOST allows retrospective LBA mapping. In Android, we found that many files are short-lived; they are created and quickly deleted by SQLite. This is due to the \"DELETE\" rollback journal mode of SQLite. Although they have short life span, these files are fsync() to NAND storage. When MOST initiates analysis procedure for a given LBA, a temporary file to which the block belonged may have been deleted and cannot be found. To address this issue, MOST maintains a table for logical block address and inode number pair in the Linux kernel. When the I/O scheduler inserts the I/O request to the queue, MOST inserts \(<\)LBA, inode number\(>\) entry to the table. MOST examines this table to obtain the file information for a given logical block address. To reduce the table size, MOST maintains an \(<\)LBA, inode number\(>\) entry only for temporary files, that is, when the file extension is either.db-journal,.db-mjxxxx,.bak, or.tmp. MOST categorizes logical blocks into three types: _metadata_, _journal_, and _data_. In the EXT4 file system, _metadata_ blocks include a superblock, group descriptor, data block bitmap, inode bitmap, and inode table. In the FAT32 file system, _metadata_ blocks include a boot record and File Allocation Table (FAT). _journal_ is a journal block of the EXT4 file system.