WO2012167392A2 - Procédé et dispositifs de suppression sécurisée de données dans un système de fichiers journalisé - Google Patents

Procédé et dispositifs de suppression sécurisée de données dans un système de fichiers journalisé Download PDF

Info

Publication number
WO2012167392A2
WO2012167392A2 PCT/CH2012/000123 CH2012000123W WO2012167392A2 WO 2012167392 A2 WO2012167392 A2 WO 2012167392A2 CH 2012000123 W CH2012000123 W CH 2012000123W WO 2012167392 A2 WO2012167392 A2 WO 2012167392A2
Authority
WO
WIPO (PCT)
Prior art keywords
data
memory
file system
file
block
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/CH2012/000123
Other languages
English (en)
Other versions
WO2012167392A3 (fr
Inventor
Srdjan Capkun
David BASIN
Joel REARDON
Claudio MARFORIO
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Eidgenoessische Technische Hochschule Zurich ETHZ
Original Assignee
Eidgenoessische Technische Hochschule Zurich ETHZ
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Eidgenoessische Technische Hochschule Zurich ETHZ filed Critical Eidgenoessische Technische Hochschule Zurich ETHZ
Publication of WO2012167392A2 publication Critical patent/WO2012167392A2/fr
Publication of WO2012167392A3 publication Critical patent/WO2012167392A3/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/10—File systems; File servers
    • G06F16/16—File or folder operations, e.g. details of user interfaces specifically adapted to file systems
    • G06F16/162—Delete operations

Definitions

  • the present invention relates to a method and devices for secure deletion of data in a log structured file system. Particularly, the present invention relates to a method and devices for secure deletion of data stored by a log structured file system in flash memory.
  • Deleting a file from a storage medium has two main purposes: it reclaims storage and ensures that any sensitive information contained in the file is no longer accessible. When done for the latter purpose, it is critical that the file is securely deleted, meaning that its content does not persist on the storage media after its deletion.
  • deletion is implemented as a rapid operation where a file is unlinked, meaning its metadata states that it is no longer present while the contents of the file remain in storage until overwritten by new data [4]. While many users expect that deleting messages will delete them, clearing the browser's history will clear it, and changing their location will overwrite their previous location, in reality this information remains on their devices without any guarantees of actual deletion from memory. Surveys of repurposed hard drives found that many contained private financial or medical data that could be recovered with trivial forensic cost and effort [4].
  • secure deletion is not only important when media is repurposed; it also enables users to protect the confidentiality of their data, if their devices are compromised, stolen, or confiscated under a subpoena.
  • the user may also be forced to disclose all passwords, keys, or other credentials that enable access to the data stored on the device; in such a scenario, the users can only use secure deletion to protect their data before the device is seized.
  • Log-structured file systems differ from a traditional block-based file system, e.g. FAT or ext2, in that the entire file system is stored as a chronological record of changes from the initial empty state. As files are written, new fixed-size chunks are appended to the log indicating the resulting change; a chunk can store either the file headers or the files' data, and is always added to the end of the log. The file system maintains in RAM the information regarding which chunks are valid, which have been superseded since writing, and where the headers for each file can be found. Log-structured file systems complicate secure deletion because the traditional approach of overwriting a file with new content simply appends a second version of the file, while the first still remains in the log's history.
  • FAT block-based file system
  • YAFFS "Yet Another Flash File System”
  • YAFFS is a log-structured file system developed specifically for flash memory storage.
  • the flash-based log-structured file system is notably used for the internal memory of Android mobile phones.
  • YAFFS allocates memory by selecting an unused erase block and. allocating sequentially the numbered chunks in that block. When the block contains no more empty chunks, a new block is selected for allocation by searching for an empty block.
  • YAFFS searches sequentially, wrapping cyclically when necessary, by the erase block number as defined by the physical layout of memory on the storage medium.
  • Garbage collection in YAFFS is either initiated by a timer thread that performs system maintenance, or takes place after write operations. Usually, only a few chunks are copied at a time, whereby the work to copy a block is amortized over many write operations. If the file system contains too few free blocks then a more aggressive garbage collection is performed, in this case, blocks with less deleted space will be collected, and the procedure will continue until the entire block can be reclaimed.
  • Figure 1 shows the lifetime for stored data. After being allocated at time t 0 , a block is reallocated at time t 2 , when all deleted data it contained becomes securely deleted.
  • deletion latency (t 2 -t, ). This is always less than the block reallocation period - defined as the time between two subsequent allocations of the same block (t 2 -t 0 ).
  • Flash Memory Flash memory is a non-volatile storage medium consisting of an array of electrical components that store information. The contents of flash memory cannot be altered in place, but rather an erase procedure must be first performed on a larger granularity than reading or writing. Erasure on flash memory is costly: the increased power requirements of erasure eventually wear out the medium, and erasure blocks can only handle a finite number of erasure operations - roughly 1 04 to 105 [ 1 3] - before becoming unusable.
  • Flash file systems are typically log-structured for two reasons. First, the large erase granularity of flash memory maps exactly to the garbage collector's erase blocks in a log- structured file system. Second, log-structured file systems do not require in-place updates; new data is always appended to the end of the log.
  • log-structured file systems provide no temporal guarantees on data deletion; deleted data persists for around 44 hours with average phone use and indefinitely, if the phone is not used after the deletion.
  • mechanisms such as file overwriting or encryption of individual files, proposed for data deletion in block-structured file systems [ 1 1 , 5] do not ensure data deletion in log-structured file systems such as YAFFS. Namely, overwriting a file in log-structured file systems simply writes a new version of a file, but does not remove the original copy.
  • the above-mentioned objects are particularly achieved in that, for secure deletion of data in a log structured file system, the deletion latency between deletion of the data by a user and secure deletion of the data from memory, e.g. flash memory, is shortened by an application (module) writing and deleting junk files to expedite reallocation of memory.
  • memory e.g. flash memory
  • the application determines periodically a number of free chunks of memory, deletes a junk file for cases where the number of free chunks is below a defined lower memory threshold, and writes a junk file for cases where the number of free chunks is above a defined upper memory threshold.
  • the junk files are set to a defined number of one or more memory erase blocks including junk data, a memory erase block comprising a plurality of memory chunks, and the defined lower memory threshold and the defined upper memory threshold are set to obtain a minimum amount of available memory in a range of 1 0 to 250 memory erase blocks.
  • the application deletes from memory older junk files prior to newer junk files.
  • the log structured file system is implemented on a computerized device, particularly a communication terminal, and the application is assigned permission to run on the communication terminal while the communication terminal is in a locked state.
  • the application upon user deletion of sensitive data, the application fills the available memory with junk data.
  • the present invention also relates to a computer program product comprising a (tangible, non-transitory) computer readable medium having stored thereon computer program code which directs a computerized device, e.g. a communication terminal, having a data memory, e.g. flash memory, and a log structured file system, to execute the method for secure deletion of data in the log structured file system.
  • a computerized device e.g. a communication terminal
  • a data memory e.g. flash memory
  • log structured file system e.g.
  • the invention in another aspect, relates to a method and a device for deleting data in a log structured file system associated with flash memory of a communication terminal, whereby, upon deletion of a chunk of memory by the file system, a kernel function of the communication terminal overwrites the entire deleted chunk with zeros.
  • the invention relates to a method for secure deletion on a file system, comprising the steps: deleting the data from the device through normal means; writing new data until the capacity of the device is full, thereby ensuring that all available space has since been repurposed for new data; and deleting the new file to reclaim the space it consumes.
  • the invention in a fourth aspect, relates to a method for the encryption and secu re deletion of data, using a storage medium capable of partitioning , where data storage comprises the steps: partitioning the device into an encryption key area and a storage area; associating each file in the storage area with an encryption key in the key area; encrypting any data written to a file with its corresponding key; and where data deletion compromises the steps: deleting the file from the storage area; deleting the key for the file from the key area; applying the third aspect to the capacity of storage space.
  • the invention relates to a method for achieving improvements to the expected latency on log-structured file systems without requiring special privileges, comprising the following steps: crating one or more u nneeded file( s) whenever the file system has free space above a threshold; deleting an unneeded file whenever the file system has free space below a threshold; and periodically checking the file system's free space and managing the unneeded files.
  • the invention relates to a method for secure deletion involving a remapping layer, such that any file system mounted on top of the rema pping layer can implement an equivalent system as the thi rd aspect, where instead of filling the entire storage capacity of the device, the remapping layer withholds blocks from the file system, consisting of the following steps: the remapping layer is informed that a secu re deletion operation is occurring; the user writes unneeded data to a single file; during this process, whenever a block is erased, the remapping layer uses block metadata to prevent its reallocation; the unneeded file is then deleted and the remapping layer is told that; the secure deletion operation has completed; and the block remapping layer uses metadata to again allow allocation of erased blocks.
  • a first realization is applied to the UBI block remapping layer and any flash file system, including YAFFS and YAFFS2.
  • a second realization uses the bad block flag as metadata to prevent the file system from allocating a block.
  • a hybrid system combines these first and second realizations.
  • the invention relates to a method for secure deletion involving a remapping layer, such that any file system mounted on top of it can implement an equivalent system as the fifth aspect, where instead of filling unneeded files, the remapping layer withholds blocks from the file system; this consist of the following steps: the desired free space (cf. the thresholds on free space) is told to the remapping layer; when a block is erased, the remapping layer may indicate via metadata that the file system should not use that block (cf. writing an unneeded file); and the remapping layer uses metadata to also indicate when the file system can again use a block (cf. deleting an unneeded file).
  • the desired free space cf. the thresholds on free space
  • the remapping layer may indicate via metadata that the file system should not use that block (cf. writing an unneeded file)
  • the remapping layer uses metadata to also indicate when the file system can again use a block (cf. deleting an unneeded file
  • a first realization used is the UBI remapping layer and any flash file system, including UBIFS, YAFFS and YAFFS2.
  • a second realization uses the bad block flag as metadata to prevent the file system from allocating a block.
  • a hybrid system combines these first and second realizations.
  • the invention relates to a method for secure deletion making use of a remapping layer that provides atomic update, with a change to any file system that operates on the remapping layer, where secure deletion occurs in a similar way as the fourth aspect, consisting of the following steps: one or more erase block(s) at fixed logical positions is/are dedicated solely to storage of keys; each file is associated with a key; any data written to a file is encrypted with its corresponding key before writing it to storage; when data is deleted, its corresponding key is also deleted; and periodically the block(s) containing keys are atomically updated using the remapping layer's atomic update function to securely remove all old keys, thus securely deleting (in a computationa-l sense) the corresponding data.
  • a realization uses UBI remapping layer and any file system that can function with UBI, including UBIFS, YAFFS and YAFFS2.
  • Figure 1 shows a time diagram illustrating the lifetime for stored data.
  • Figure 2a shows a graph which illustrates a snapshot of block allocation for a browser application.
  • Figure 2b shows a graph which illustrates a snapshot of block allocation for a maps application.
  • Figure 3 shows a graph which illustrates YAFFS' block allocations over time on an
  • Figure 4 shows a flow diagram illustrating an exemplary sequence of steps performed by an application for secure deletion of data in a log structured file system.
  • Figure 6 shows a scatter plot of average block allocations per hour and median secret erasure time in different application simulations with a variety of parameters.
  • Figure 7 shows a graph which illustrates block allocation times on a simulated system not running the application, where, at the end of the simulation, the drive was completely filled to guarantee all deleted data was removed.
  • Figure 8 illustrates the state of an erase block at different times.
  • Figure 9 shows a block diagram illustrating schematically a computerized device having a data memory, a log structured files system and an application for secure deletion of data in the log structured file system.
  • a modified version of the YAFFS Linux kernel module was built that logs data about block allocations and chunk writes. It was logged whenever a new block is allocated, which signals that the block is now empty and that whatever data was previously on the block has been erased (or moved). Also logged was every write operation: both file headers and file data. This made it possible to determine how often writes occur, in which blocks and chunks they occur, and when files are deleted.
  • logged was the system time in microseconds, the unique physical block number (in the present case, ranging from 1 to 1 570), the sequence number of the block, and the number of free chunks and erased blocks according to YAFFS's statistics. Also logged was the device name to demultiplex the data, as the Android phone has multiple YAFF5 partitions.
  • Logging every chunk write gives a fine-grained view of the writing behaviour on a mobile device. Logged was the system time in microseconds, the physical location of the chunk, the operating system's owner of the file, the block on which it is written, the type of data being written (i.e. a file, a folder, a header, etc.), the file id, and where in the file the data is being written.
  • the focus is on a subset of applications that could be used daily on a smart phone to determine how long data, even after deletion, lives on the system when the user uses only such applications. Then the phone is used continuously throughout the daily routine to find out, on average, how long data remains "alive” on the system before being erased. This information will later be used to model the writing behaviour of the Android OS and its applications to simulate a system with a specifically tailored simulator.
  • the system tested is a Nexus One running the latest Android OS ( 2.2.1 ) under what can be considered normal daily use. browsing the web, saving images, taking photographs with the integrated camera, listening to music, writing and receiving SMS messages, and making phone calls.
  • the user surfed the web for approximately 8 minutes, performing various web surfing activities, such as logging into a university website, getting weather forecasts, and searching for images.
  • various web surfing activities such as logging into a university website, getting weather forecasts, and searching for images.
  • the user interacted with the application for approximately 6 minutes, searching for a particular destination, looking at its "street view” and calculating a route to it.
  • the game and gallery examples were ran for approximately 4-5 minutes each, which can be considered normal usage.
  • Table 1 Average reallocation period for different commonly used applications.
  • the test ran for 23 minutes and allocated 304 blocks.
  • the instrumented phone was used daily. The experiment lasted 670 hours, roughly 27.9 days. In total, throughout the experiment, collected were 20345 block allocations made by 73 different writers. A writer could be any application but also the Android OS itself or one of its services (i.e. GPS, DHCP, compass, etc.) . Subsequent analysis of the experiment's logs yielded the result that blocks are reclaimed, on average, every 44.7 hours (the median being 44.5 hours). The worst case for block reallocation time for the experiment is 327.7 hours. This is not surprising, given the YAFFS implementation, but underscores the critical need for secure deletion solutions.
  • reference numeral 1 refers to a computerized device, e.g. a communication terminal such as a mobile radio phone, e.g. an Android phone, or another mobile computerized device such as a laptop, palmtop or PDA computer, for example.
  • computerized device 1 comprises data memory 1 3, preferably flash memory, a log . structured file system 1 2, and an application module 1 1 running on a processor of the computerized device 1 .
  • the data memory 1 3 comprises a plurality of memory erase blocks 130, each memory erase block 1 30 comprising a defined number of one or more memory chunks 1 31 .
  • the application module 1 1 works at the user level and is designed for the scenario where 5 security conscious users of the computing device 1 , e.g. mobile phone users, want to install a secure deletion application from an application marketplace (app store), but are unwilling to install a new operating system on their computing device 1 . This means that only user-level permissions on the storage medium can be provided to the application.
  • a user-level application has limited access to the flash device.
  • the application cannot I D force the file-system to perform block erasures, prioritize garbage collection of particular areas in memory, or even know where on the computing device 1 the user's data is stored.
  • the interface to the file system for such applications consists of the creation, modification, and deletion of the user's own local files.
  • the application module 1 1 keeps the storage medium close to capacity. In a so called 15 "ballooning" process, the application module 1 1 creates and removes insensitive junk files (including meaningless junk data only), resulting in more frequent garbage collection. This reduces the average block reallocation period, thereby speeding up the secure deletion of any sensitive information contained in the blocks.
  • the block reallocation period in a log-structured file system is the expected time that will 0 elapse between allocations of a block in the file system (cf. Figure 1 ). This is based mainly on two factors: the write frequency on the medium, and the expected number of other blocks that will be allocated before the particular block is reallocated.
  • the type of contents on the block also has an effect: blocks containing long-term operating system files will tend not to be reallocated, simply because their contents are never deleted; however, blocks containing data that is not deleted is necessarily not a concern for secure deletion.
  • the cyclic behaviour of block allocations in YAFFS is evident in Figure 3, which shows the sequence of block allocations from the collected data from an Android mobile phone.
  • the X-axis corresponds to the time in hours for the experiment, and the Y-axis shows the numbered erase blocks.
  • a small square in the graph indicates when each erase block was allocated. For clarity, only the allocations for every fifteenth block are shown. While some noise exists, it can be seen that block allocation numbers generally increase over time and wrap cyclically, and so the block reallocation period is dependent on both the number of blocks and the system-wide time between block allocations.
  • the capacity of the file system is reduced with junk content, which reduces the block reallocation period due to fewer blocks being available for allocation, and thus reduces the deletion latency.
  • YAFFS is forced to employ more frequent garbage collection, as the file system will perpetually believe that it is in a state of reduced capacity.
  • the junk files will be deleted when the drive requires more space, and be regenerated whenever there is too much free space.
  • the operation of the application module 1 1 is illustrated in Figure 4.
  • the application module 1 1 runs periodically on the computing device 1 , examining the file system 1 2 (using stat) to determine the number of free chunks.
  • the application module 1 1 requests from the log structured file system 1 2 information about the amount of free space, which is returned by the file system 1 2, in step 52, as a number ( n ) of free memory chunks 1 3 1 .
  • the application module 1 1 either creates or deletes junk files using parameterized thresholds.
  • the application module 1 1 if the number of free chunks 1 31 is below the defined lower memory threshold (n ⁇ min_threshold), in step S3, the application module 1 1 deletes one or more junk files from memory 1 3.
  • the application module 1 1 writes a junk file into memory 1 3.
  • the junk files' exact size is also parameterizable and defined in multiples of erase blocks. Deleting one junk file will free at T O least one erase block for new data.
  • the application module 1 1 always deletes the oldest junk file before more recent ones to ensure that the desired load-balancing of wear on the flash memory is preserved.
  • Long- lived junk files can also be erased, with new ones written, to ensure that their corresponding erase blocks will be used for more active data storage.
  • the new ones are i s preferably written, before deleting the old ones to ensure that they reside on different erase blocks.
  • the application module 1 1 runs and operates within the limits imposed by user-space (i.e. outside the kernel space). To run the application module 1 1 on the computerized device 1 , it is given the permission to run 20 while the device 1 is in a locked state; the application module 1 1 also specifies that it will run as a service, meaning execution occurs even when the application is not in the foreground.
  • the application module 1 1 on the computerized device 1 e.g. the Android phone
  • a discrete event simulator was programmed that writes, overwrites, and deletes files on the phone's storage, which is simply a mounted directory on the simulation computer.
  • a file type is defined by its lifetime, a distribution over the period between opening a file for write, a distribution over the number of chunks to write to a file each time it is opened, and a distribution over the chunks of a file that indicates where writes will occur.
  • Figure 5 shows YAFFS block allocations when using the application module 1 1 . It can be seen that as the range of possible block allocations shrinks considerably, the sequential allocation strategy becomes much more erratic, and the block reallocation period decreases. Erase blocks that are not being allocated (i.e. , the white space) T O correspond to erase blocks that have now been assigned junk files.
  • Parameters for the application module 1 1 include the size of the junk files, and the free space thresholds when junk files are created and destroyed. These variables affect the total expected free space on the partition during execution, which will be in the range defined by the thresholds. This is typically, though not always, between the lower 20 threshold and the size of one junk file. The amount of free space on the drive is what affects both deletion time and the block allocation rate. To get an idea of how these parameters are affected, the simulation was run for different parameters and computed was the median erasure time and block allocation rate. Figure 6 shows the result of this experiment, which is a scatter plot with the median deletion time on the Y-axis and block allocations per hour on the X-axis; each point on the plot shows the results from one of the simulations. It can be observed in Figure 6 that these two quantities are inversely proportional. As the block allocations rate increases - due to less free space and thus more frequent garbage collection - the time decreases during which secrets remain on the device. -
  • Table 1 shows measurements of the deletion time in hours for different amounts of free space (measured in erase blocks), as affected by using different parameters for the application module 1 1 . Each simulation was run eight times; the results were averaged and the 95% confidence intervals were computed. l- ' rec space Percentile Measurements
  • Table 3 Block allocations per hour for different configuration parameters.
  • the ratio column is the proportion with regards to not using the application module 1 1 .
  • the potential drawback of the application module 1 1 is the additional wear that i s increased erasures put on the device 1 , both in terms of damage to the flash memory and power consumption. If this approach significantly reduces the phone's lifetime or battery life, then it would be a concern for adoption. Therefore, experiments were performed to investigate this.
  • the additional wear is directly proportional to the increase in the block allocation rate, 20 and inversely proportional to the lifespan.
  • the block allocation rate was converted into an expected lifetime in years using the conservative estimate of 1 04 erasures per block and 1 571 erase blocks available on the Android's data partition.
  • a typical flash erase block can handle between 104 and 105 erasures [ 1 3]).
  • Table 4 shows the plot of the expected minimum lifespan of an Android phone running continuously at varying block allocation rates. It can be seen that device wear is not a concern even with the conservative estimate of block life time. A computerized device 1 running without the application module 1 1 can expect a lifespan of six decades - well beyond the replacement period of mobile phones. Even running the application module 1 1 with the most aggressive parameters will still result a lifetime of five years. It is observed that there exists a trade off between wear on the device and secure deletion, and so the user is enabled select his/her desired device lifespan and tune the security parameters accordingly.
  • Table 4 Expected minimum device lifetime at various block allocation rates.
  • the power consumption of write operations was checked. Measured was the battery level through the Android API, which gives its current charge as a percentage of its capacity.
  • the experiment consisted of continuously writing data to the flash memory of the phone in a background service while monitoring the battery level in the foreground and measuring how much data must be written to drain ten percent of the total battery capacity. The experiment was run four times and the result was averaged. The resulting mean is within the range of 1 1 .0 ⁇ +/-0.22 GB with a confidence of 95%, corresponding to 90483 full erase blocks worth of data.
  • the application module 1 1 By using the application module 1 1 , it is possible to reduce the number of blocks being actively used for writing data. This means that the set of blocks needing to be erased to achieve immediate deletion will be reduced. Any reduction would be an improvement over garbage collecting every erase block, and so performed was the following experiment to quantify how many blocks would need to be garbage collected when using the application module 1 1 .
  • Table 5 shows the results of this experiment. The average number of additional block allocations that was required to guarantee secure deletion, along with their 95% confidence intervals, is presented. The tests on the Android phone show that this operation occurs in less than a minute, and requires no significant power consumption. Free space Block
  • Table 5 Block allocations required to purge all secrets for different configurations.
  • the results show how many blocks were being actively used to store data at a particular time.
  • the operation of filling the drive generally requires the compaction of every active erase block used by the file system.
  • the application module 1 1 reduces the number of erase blocks being actively used, and thus reduces the overhead to perform this operation.
  • the lack of variance in the large measurements suggests that the number of active blocks well exceeded the total number required by the file system to store data, thus producing a spread of data over all available blocks.
  • the smaller measurements with greater variance suggest that the data was more frequently garbage collected and reorganized - since YAFFS performs no data lifetime analysis to collocate data, the variance is likely a result of the disparity between deletion times.
  • a further solution for secure deletion of data in a log structured file system is implemented at the kernel layer.
  • the kernel-based approach the YAFFS file system was modified to achieve secure deletion. This models the scenario where a user of the computerized device is willing to install a custom kernel for their device and has already gained super-user access to the hardware. Thereby, provided is a simple, easily auditable, and small change to the file system to achieve secure deletion.
  • NAND flash programming The principle behind NAND flash programming is that an erasure sets all bits to the value of binary 1 , and programming simply selects some bit positions to instead have the value of binary 0. It is not possible to program a zero into a one, as this operation requires erasing the corresponding erase block. Reprogramming an area of memory to contain only zeros is possible at a smaller granularity than erase blocks, and so researchers have proposed zero overwriting the flash memory [1 4].
  • the kernel-based approach requires both super-user permissions to install a new YAFFS version, and a non-standard use of flash. This kernel-based approach is attractive because it requires only a small change to YAFFS to enable guaranteed immediate secure deletion without causing any additional wear on the device.
  • Figure 8 shows an example of how zero overwriting can remove sensitive information.
  • YAFFS 1 used zero overwriting to mark an "is deleted flag" in chunks.
  • garbage collection YAFFS 1 reread the reprogrammed chunk to determine if it needed to be copied or it could be deleted.
  • This kernel-based approach may still leak information through advanced forensic techniques, perhaps allowing an observer to determine how recently a gate was set to zero, thus indicating which bits were simultaneously reprogrammed.
  • zero-overwriting guarantees that the data is information theoretically deleted against software forensics.
  • this kernel-based approach requires no block erasures to delete the information. All data is promptly removed when it is no longer needed, and the flash hardware is not required to erase any additional blocks to achieve secure deletion. As such, there is no additional wear on the device itself - except for the minuscule power consumption required to program the chunk to contain only zeros.
  • the change to YAFFS is less than a dozen lines of C code, and is contained mostly in the YAFFS chunk del() function.
  • This function handles the deletion, of a chunk from internal memory structures, and is invoked whenever a chunk is no longer needed by the file system, such as deleting a file, truncating it, or overwriting a part of it.
  • the method was enhanced to overwrite the entire deleted chunk with zeros, using the same technique used to set the deleted flag in the tags - which is also implemented in the same function and used when the device is mounted as a YAFFS 1 drive.
  • the other change is in the flash write function, where a kernel oops was removed - the kernel equivalent of a segmentation fault - that prohibited empty chunk tags.
  • a second version of this function can be created which is called only to perform zero-overwriting, and the kernel oops is kept in place.
  • the kernel-based approach was implemented and its correctness tested by writing information, deleting it, and then searching the raw memory for the information using grep and hexdump.
  • Raw data was collected from the NAND simulator by unmounting /dev/mtdblockO (the device that corresponds to the simulator) and using the program dd to copy the full contents.
  • Raw data was collected from the Android phone by logging in as root, unmounting the flash drive, and copying the raw data using cat from /dev/mtd/mtd5 (the device that corresponds to the phone's data partition) to the phone's external memory. The resulting file was then copied to a PC and examined using grep and hexdump.
  • the deletion tests consisted of creating a file with some sensitive information and then erasing it in different ways. The following items were tested: a deleted file, a file completely overwritten, a file partially overwritten, a file completely truncated, and a file partially truncated. The tests using partial truncation and overwriting always erased the entire sensitive part of the file. Tests were done using block-aligned and block-unaligned overwriting and truncation. The tests were first run using the standard version of YAFFS, ensuring that the data was still recoverable. In each test, the sensitive data is completely erased from the file system, but remains accessible by unmounting it and reading the raw data.
  • FTL flash translation layer
  • the FTL's erase blocks can be partitioned such that some of the erase blocks are assigned to one partition and the remaining erase blocks are assigned to another, then the following solution can achieve more effective secure deletion.
  • the device is first partitioned into a large storage area and a small key area.
  • an encryption key is generated and stored on the smaller partition.
  • the data for the file is encrypted using this key and the resulting encrypted data is stored on the large partition. No data is ever written to the large partition unless it is encrypted.
  • both the file's data and its secret key are deleted.
  • the user can apply the additional step of performing purging on the key partition. Since the key partition is much smaller than the entire storage medium, the operation will be much quicker to perform than purging the entire drive. The resulting wear on the erase blocks assigned to that partition means that this area will likely develop bad blocks earlier. However, by creating a few small partitions, the user can migrate among them after they become unwritable, and set up the device initially with an expected lifetime that is sufficiently large.
  • This system can be implemented as a small change to the FAT file system driver.
  • logical volume managers can be used to amalgamate the two physical partitions into one logical partition, where any writes to the largest addresses on the logical partition will occur in the small key space.
  • the logical partition is then formatted with our modified FAT file system, which is aware of the size and location of the key space.
  • data When data is written to or read from the file system, it will perform the necessary encryption and decryption operations using the correct key from the key partition, and store the data only in the data partition.
  • the file system When the drive is unmounted, or after the expiration of some period of time during which files were deleted, the file system will internally and automatically perform the purging operation by filling the blocks in the logical partition that correspond to the complete set of blocks in the physical key storage area.
  • UBI YAFFS and other flash file systems interact directly with the flash memory controller, through an interface called the Memory Technology Device (MTD) layer.
  • MTD Memory Technology Device
  • This interface exposes functions to read and write areas in an erase block, erase an entire erase block, check if an erase block is bad, and mark an erase block as bad. It is a low-level interface and does not provide wear-levelling or bad block detection on its memory.
  • Unsorted Block Images ( U BI ) is a simple remapping layer above the MTD layer. Logical blocks at the U BI layer are mapped to physical blocks at the MTD layer.
  • U BI exposes the following interface: read and write to a logical erase blocks ( LEB ) , erase an entire LEB, and atomically update the contents of an entire LEB (i.e. , in-place edits at the erase block level) . It also allows dynamic creation of UBI partitions using unallocated LEBs. It is neither possible for an LEB to become bad, nor is wear-levelling a concern for LEBs. UBI permits more organization in the design of flash file systems, as there are no longer wear-levelling and bad block concerns for statically-placed super-blocks with specific file system metadata and the assignment of different regions of the storage medium to different purposes.
  • LEB logical erase blocks
  • Regular flash file systems can be mounted on top of the UBI interface, which will act like an MTD interface with the exception that blocks will not become bad and wear levelling is effortlessly improved.
  • the atomic update feature can also be used by the file system.
  • UBI's admittance of atomic updates allows for a simple means to achieve secure deletion; when data is deleted, the file system atomicaily updates each erase block in which the data was stored so that it no longer contain the deleted data. UBI's implementation of the atomic update mechanism ensures that once the new block is written, the old one is erased in a timely fashion.
  • UBI exposes the ability to dynamically create partitions from unused logical blocks in its block pool. It is theoretically possible for UBI to dynamically grow or shrink the size of a partition-were it to know which blocks are not currently being used by the file system above it, and were the file system to know that its size is volatile.
  • UBIFS The UBI file system
  • UBIFS is a sophisticated file system designed for flash memory accessed through the UBI device abstraction.
  • UBIFS is an improvement over existing flash-based file systems, but was still not designed to provide secure deletion. In this section we examine methods to add secure deletion to UBIFS.
  • One approach is to use a designated key area, which will be updated during the periodic checkpoint operation performed by UBIFS.
  • Each file will be encrypted with a different key, and the file's inode gives the location of the key in the checkpoint area.
  • Keys are only preserved in the checkpoint when their corresponding files have not been deleted; therefore a key for a deleted file that remains in the old checkpoint is not preserved into the new one. Since old checkpoints are immediately considered wasted space, the corresponding erase blocks that contain their data can be quickly reclaimed. This securely deletes the key and thus deletes the data in a computationally-secure manner.
  • Additional cryptographically-secure random data would be stored in the checkpoint, which will be used as keys for files that are created between checkpoint operations. This protects the availability of the data if the device crashes between checkpoints and the contents of RAM are lost— the keys are written to the device before they are used, and during the replay operation the file system can reunite the file with its key.
  • the wear-levelling concerns of this technique are handled automatically by UBI, and this approach leverages the existing checkpoint and replay feature of the file system to easily add secure deletion. Since the checkpoint consists of the data normally stored in RAM, the keys for the files will always remain quickly accessible.
  • Encryption is handled entirely in the file system, so no unencrypted data is ever written to disk. Encryption occurs immediately after UBIFS applies optional compression to the contents of a data node. Similarly, decryption occurs immediately before UBIFS applies the decompression operation.
  • a small part of the file system is dedicated solely to the storage of keys. This data area is itself not encrypted, and so only by securely deleting the data are we assured that it is no longer accessible.
  • the key space is written in advance: a full erase block of random data is written, and the keys are then later assigned out from the random data as they are needed.
  • Such a design requires a bidirectional map: data blocks must be able to find their corresponding encryption keys, and it should be simple to determine if a particular encryption key is being used or not.
  • Each block has index data, which for data blocks indicates the file's inode and the offset in the file where the data is located.
  • UBIFS is designed to support optionally larger index keys---an extra 64 bits---which is ample to use to reference the offset in the key space where the block's key is located.
  • the reverse mapping is a function that, given a stored key, returns whether the key is unassigned, assigned, or should be deleted. It does not need to map to the block that uses it— orphaned keys can be found when doing a consistency check on the index data of each block. Such a map can be stored in memory with two bits for each block; as flash blocks are often 2048 bytes large, this storage is nominal. There are two challenges with implementing the reverse mapping. First, the key data is already written onto the blocks before it is actually used. Each block in the key space can store many keys. We cannot update the key's value after it is assigned or otherwise changes state; the mapping of keys to their states must be stored elsewhere.
  • mapping as a 2-bit map over the space of key positions. Each key is given two bits to record its state, and this mapping is kept in memory and updated as appropriate: when fresh random data is written, then the key is marked as unassigned; when a new data block is written, an unassigned key is assigned to it and marked as assigned; when a block is marked as deleted, then the corresponding key is set to deleted to indicate that it should be purged. If an erase block containing deleted data blocks is erased, then any keys that are marked as deleted can be returned to unassigned as the data that they encrypted has been securely removed and so the entropy can once again be used for new keys.
  • the reverse mapping is written, along with the other in-memory data structures, during the periodic checkpoint operation.
  • the replay mechanism can be used along with the checkpoint to restore the map to its correct state. Each new block that is written will indicate the key position it uses, and blocks that were erased since checkpointing are also determined by replaying the sequence of updates.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Human Computer Interaction (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Storage Device Security (AREA)

Abstract

Selon l'invention, pour assurer une suppression sécurisée de données dans un système de fichiers journalisé (12), la latence de suppression est raccourcie entre la suppression des données par un utilisateur et la suppression sécurisée des données dans la mémoire par une application (11) écrivant (S4) et supprimant (S3) des fichiers inutiles afin d'accélérer la réattribution de mémoire. Pour cela, l'application (11) détermine (S1, S2) périodiquement un certain nombre de segments de mémoire libres, supprime (S3) un fichier inutile dans des cas dans lesquels le nombre de segments libres est inférieur à un seuil de mémoire inférieur défini, et écrit (S4) un fichier inutile dans des cas dans lesquels le nombre de segments libres (131) est supérieur à un seuil de mémoire supérieur défini.
PCT/CH2012/000123 2011-06-06 2012-06-05 Procédé et dispositifs de suppression sécurisée de données dans un système de fichiers journalisé Ceased WO2012167392A2 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
CH9722011 2011-06-06
CH972/11 2011-06-06

Publications (2)

Publication Number Publication Date
WO2012167392A2 true WO2012167392A2 (fr) 2012-12-13
WO2012167392A3 WO2012167392A3 (fr) 2013-02-28

Family

ID=47296535

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CH2012/000123 Ceased WO2012167392A2 (fr) 2011-06-06 2012-06-05 Procédé et dispositifs de suppression sécurisée de données dans un système de fichiers journalisé

Country Status (1)

Country Link
WO (1) WO2012167392A2 (fr)

Cited By (16)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103559276A (zh) * 2013-11-05 2014-02-05 广东欧珀移动通信有限公司 一种清理垃圾文件的方法及其装置
CN105404663A (zh) * 2015-11-10 2016-03-16 广东欧珀移动通信有限公司 一种Android设备文件列表的显示方法及系统
US9430664B2 (en) 2013-05-20 2016-08-30 Microsoft Technology Licensing, Llc Data protection for organizations on computing devices
US9477614B2 (en) 2011-08-30 2016-10-25 Microsoft Technology Licensing, Llc Sector map-based rapid data encryption policy compliance
CN106682043A (zh) * 2015-11-11 2017-05-17 腾讯科技（深圳）有限公司 一种垃圾文件提示方法和装置
US9825945B2 (en) 2014-09-09 2017-11-21 Microsoft Technology Licensing, Llc Preserving data protection with policy
US9853812B2 (en) 2014-09-17 2017-12-26 Microsoft Technology Licensing, Llc Secure key management for roaming protected content
US9853820B2 (en) 2015-06-30 2017-12-26 Microsoft Technology Licensing, Llc Intelligent deletion of revoked data
US9900295B2 (en) 2014-11-05 2018-02-20 Microsoft Technology Licensing, Llc Roaming content wipe actions across devices
US9900325B2 (en) 2015-10-09 2018-02-20 Microsoft Technology Licensing, Llc Passive encryption of organization data
WO2018055171A1 (fr) * 2016-09-23 2018-03-29 Blancco Technology Group IP Oy Procédé et appareil d'effacement de données
CN109493044A (zh) * 2018-11-08 2019-03-19 深圳壹账通智能科技有限公司 区块链区块删除方法、装置以及终端设备
US10615967B2 (en) 2014-03-20 2020-04-07 Microsoft Technology Licensing, Llc Rapid data protection for storage devices
US10791109B2 (en) 2016-02-10 2020-09-29 Red Hat, Inc. Certificate based expiration of file system objects
CN111984601A (zh) * 2020-08-31 2020-11-24 深圳壹账通智能科技有限公司 日志文件删除方法、装置、电子设备及存储介质
CN116955520A (zh) * 2023-06-16 2023-10-27 珠海亿智电子科技有限公司 一种高性能只读文件系统的创建方法及装置

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN106708912B (zh) * 2015-11-18 2021-06-25 中兴通讯股份有限公司 垃圾文件识别及管理方法、识别装置、管理装置和终端

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8117377B2 (en) * 2007-12-27 2012-02-14 Electronics And Telecommunications Research Institute Flash memory device having secure file deletion function and method for securely deleting flash file

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
None

Cited By (21)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9477614B2 (en) 2011-08-30 2016-10-25 Microsoft Technology Licensing, Llc Sector map-based rapid data encryption policy compliance
US9740639B2 (en) 2011-08-30 2017-08-22 Microsoft Technology Licensing, Llc Map-based rapid data encryption policy compliance
US9430664B2 (en) 2013-05-20 2016-08-30 Microsoft Technology Licensing, Llc Data protection for organizations on computing devices
CN103559276A (zh) * 2013-11-05 2014-02-05 广东欧珀移动通信有限公司 一种清理垃圾文件的方法及其装置
US10615967B2 (en) 2014-03-20 2020-04-07 Microsoft Technology Licensing, Llc Rapid data protection for storage devices
US9825945B2 (en) 2014-09-09 2017-11-21 Microsoft Technology Licensing, Llc Preserving data protection with policy
US9853812B2 (en) 2014-09-17 2017-12-26 Microsoft Technology Licensing, Llc Secure key management for roaming protected content
US9900295B2 (en) 2014-11-05 2018-02-20 Microsoft Technology Licensing, Llc Roaming content wipe actions across devices
US9853820B2 (en) 2015-06-30 2017-12-26 Microsoft Technology Licensing, Llc Intelligent deletion of revoked data
US9900325B2 (en) 2015-10-09 2018-02-20 Microsoft Technology Licensing, Llc Passive encryption of organization data
CN105404663A (zh) * 2015-11-10 2016-03-16 广东欧珀移动通信有限公司 一种Android设备文件列表的显示方法及系统
CN106682043A (zh) * 2015-11-11 2017-05-17 腾讯科技（深圳）有限公司 一种垃圾文件提示方法和装置
CN106682043B (zh) * 2015-11-11 2020-08-25 腾讯科技（深圳）有限公司 一种垃圾文件提示方法和装置
US10791109B2 (en) 2016-02-10 2020-09-29 Red Hat, Inc. Certificate based expiration of file system objects
US11777919B2 (en) 2016-02-10 2023-10-03 Red Hat, Inc. Certificate based expiration of file system objects
WO2018055171A1 (fr) * 2016-09-23 2018-03-29 Blancco Technology Group IP Oy Procédé et appareil d'effacement de données
US20190212942A1 (en) * 2016-09-23 2019-07-11 Blancco Technology Group IP Oy Data Erasure Method and Apparatus
US10956080B2 (en) 2016-09-23 2021-03-23 Blancco Technology Group IP Oy Erasure of data from a memory of a data storage apparatus by identifying available free space in the memory and iteratively writing a sequence of files decreasing size to the memory using a file-based protocol
CN109493044A (zh) * 2018-11-08 2019-03-19 深圳壹账通智能科技有限公司 区块链区块删除方法、装置以及终端设备
CN111984601A (zh) * 2020-08-31 2020-11-24 深圳壹账通智能科技有限公司 日志文件删除方法、装置、电子设备及存储介质
CN116955520A (zh) * 2023-06-16 2023-10-27 珠海亿智电子科技有限公司 一种高性能只读文件系统的创建方法及装置

Also Published As

Publication number Publication date
WO2012167392A3 (fr) 2013-02-28

Similar Documents

Publication Publication Date Title
WO2012167392A2 (fr) Procédé et dispositifs de suppression sécurisée de données dans un système de fichiers journalisé
Reardon et al. Data node encrypted file system: Efficient secure deletion for flash memory
US11327886B2 (en) Capturing time-varying storage of data in memory device for data recovery purposes
US9547589B2 (en) Endurance translation layer (ETL) and diversion of temp files for reduced flash wear of a super-endurance solid-state drive
US8954654B2 (en) Virtual memory device (VMD) application/driver with dual-level interception for data-type splitting, meta-page grouping, and diversion of temp files to ramdisks for enhanced flash endurance
US8959280B2 (en) Super-endurance solid-state drive with endurance translation layer (ETL) and diversion of temp files for reduced flash wear
TWI506431B (zh) 虛擬記憶體設備驅動器、用於在主機上執行之虛擬記憶體設備驅動器、刷新快閃記憶體的方法、快閃記憶體刷新的方法、超級增強耐力設備硬碟固體狀態驅動機耐用轉換層之方法、超級增強耐力設備及耐力快閃記憶體檔案系統
Reardon et al. Sok: Secure data deletion
US9489258B2 (en) Green NAND SSD application and driver
US9747202B1 (en) Storage module and method for identifying hot and cold data
Jia et al. Deftl: Implementing plausibly deniable encryption in flash translation layer
US20150106557A1 (en) Virtual Memory Device (VMD) Application/Driver for Enhanced Flash Endurance
Reardon et al. User-level secure deletion on log-structured file systems
CN108038026B (zh) 一种基于闪存的数据快速恢复方法与系统
CN110047546B (zh) 存储器系统中的擦除管理
US20190294345A1 (en) Data-Retention Controller Using Mapping Tables in a Green Solid-State-Drive (GNSD) for Enhanced Flash Endurance
TW201403318A (zh) 具耐用轉換層並能轉移暫存讓記憶體耐磨損的硬碟驅動器
US8650436B2 (en) Systems and methods for recovering information from NAND gates array memory systems
CN105404468B (zh) 绿能与非固态硬盘应用及其驱动器
KR20140038110A (ko) 파일 시스템 관리 방법 및 이를 이용하는 장치
EP3516494B1 (fr) Procédé et appareil d'effacement de données
US20090024810A1 (en) Memory area management method
Reardon et al. Secure deletion on log-structured file systems
Onarlioglu et al. Eraser: Your data won't be back
Reardon UBIFSec: Adding DNEFS to UBIFS

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 12732766

Country of ref document: EP

Kind code of ref document: A2

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 12732766

Country of ref document: EP

Kind code of ref document: A2