a bug in grep command has been discovered recently: suppose a root user use this command to search the file of a low level user in an attempt to find malicious codes
grep ".xx\(\)\|" file
if the number of bytes in the file is more than than the maximum size_t can hold, grep will try to index through the file with size_t and cause a integer overflow. which became a bad pointer, and thats how low level user can get root to execute any command.
now assume size_t bug is fixed, but we still want to attack with grep command. here is how: we launch a denial of service attack by generating large files with random bytes, grep command will eventually do a core dump when it takes too long to search through the file.
the downside of this is that we have to give up part of disk space. alternatively, we can achieve same thing with special files while using almost no disk space at all. all we need to do is create a file with last data block actually been allocated:
all the space we used to create this file is an inode and 3 datablocks(indrect one block, direct block, actual data block).
this is called a holey file, when root try to grep a holey file, it will go through all ealier data blocks, find that they dont actually exist before it gets to last block. which achieves same purpose as a big file contain random bytes.
here's how to create a holey file:
$echo x|dd > holey bs = 1MiB seek = 2048
there are a few fix for problems with shreddingholey file:
1. we can treat data block pointers that points to nowhere as new lines and just ignore them
2. or a even faster way by using ls command below which returns actual size and page size of the file
$ls -ls holey if sizes dont match, it's a holey file and we can just completely ignore it
bottom layer to top layer
1) disk sectors - 512 bytes per sector ( a linear array sort of )
2) blocks - typically multiples of disk sectors ( e.g. 8192 bytes )
3) partitions - contain all blocks, it include a partition map at beginning and several partitions follow that
4) file systems - reside in each partition, in each file system there's super block, bit map, inodes, and actual data blocks
5) inodes - contain meta info of the file and pointers to the actual data
6) file name components - name of the directory entry ( e.g. foo )
7) file name - name of directory entry and whole path ( e.g. a/b/c/foo )
8) symbolic links - files that contain file name
i. ways to implement symbolic link:
there are several ways to implement symbolic link
A) store it in an inode point to one data block, this way the file name can be as long as 8192 bytes determined by size of the data block. but we used an entire data block to store one symbolic link, if file name is not long enough, all the space will be wasted.
B) or we can limit it in one single inode, but some file names are in fact longer than a single inode can hold, so we can also used indirect block for longer file names.
C) third way to implement this is that symbolic links dont get inodes at all, they are merely directory entries. and we add a flag in directory entry to indicate weather its an file or symbolic link. in some file systems directory entry can have different length to hold file names
in linux file system ext3 version 2 directory entry has varying length, which is used to store symbolic links.
it includes:
32-bit inode pointer 16-bit directory entry length 8-bit name length 8-bit file type N-byte file name
all directory entriesproblems with shredding are in a linear array, you can change it by simply changing directry entry length and file name. remove a directory entry would mean unlinking the entry to the inode.
problem with this implementation is that if you try to remove all files in a directory by a special order say,
$rm -rftakes N square iterations, it goes through entire array N times, each time it finds correct entry, and try to unlink it, in some cases directory entries are stored in a balanced tree or hash table to achieve faster time.
when you clean up a directory you are actually unlinking the entries to the inodes, inode itself and data blocks are still sitting on you disk, and is recoverable. In some cases people want to make sure that datas on the disk is completely destroyed.
one way to do it is by writing your file with random generated bits before unlinking.
$dd if = /dev/random of = file
$rm file
where /dev/random is a operating system program for generating random bits which is kinda slow, so use
$dd if = /dev/urandom of = file
$rm file
because urandom runs much faster than random, but generates 'make up' random bits which is not completely random, or you could simply write zeroes to the file
$dd if = /dev/zero of = file
$rm file
in all of those cases file is completely written before unlink, but there are still traces of previous data on the disk that can be recovered using special techniques. instead we should use 'shread' command which uses its own random # generater and write multiple times to the file before unlinking:
$shred file
also turn off disk caching because some disk controllers tell you write is done when it's actually sitting inside disk cache.
now you might think after a file is shreded data can no longer be recovered. but that's not true
SSD:
solid state drive writes are done on random blocks instead of replacing original data. they do it to utilize all of its data blocks evenly. so if you want to make sure data on SSD is destroyed, you have to shred whole disk to prevent recovery from other blocks where your data previously reside.
Normal Harddrive:
data blocks in magnetic hard drives go bad some time, and disk controllers prevent data loss by detecting data blocks that's gonna go bad and move data on the block to a good one. and they do it without telling you. so after shreding a file, it did not erase data on those bad blocks. bad guys can still get to it with special devices.
SUMMARY:
afterall the most secure way to destroy your data is to throw your disk into lava, but now imagine this scenario, terrorist broke into embassy trying to get data on embassy's computer, you might not find lava nearby and shredding the whole disk is too slow. what do you do?
the answer is to encrypt the data and destroy the key in case of emergency, weather the key a small program or in your head.
going back to file system implementation, why do we have symbolic link when we can just use hard links? the reason being that hard links are necessary for linking a file, whereas symbolic links adds one more levele of indirection which can be used to do more advanced tricks.
hard links: directory entry that points to inode directly
symbolic links: inode that contain file name within same directory
1)symbolic links can dangle, hard links can't
2)symbolic links is relative to containing directory
3)symbolic links can loop, hard links can't
here's code for creating a symbolic link and a hard link:
ln -s d/a e/b //b is the symbolic link contain "d/a"
ln d/a e/b //b is the hard link points to inode which d/a points to
example how symbolic link and hard link work
ln -s foo d/x
ln d/x e/y
cat d/x // equal to cat d/foo
cat e/y // equal to cat e/foo
simple loops created by symbolic link
ln -s a b
ln -s b a // a point to b and b point to a
ln -s x x // self loop
how we detect symbolic link loops is that we allow a certain number of symbolic linkings before popping error, so even if symbolic links doesn't loop, if it links up to that number it won't work.
the reason that hard links dont loop is that it cannot point to a directory, it has to point to a file or a symbolic link
-------------------------------------------------------------------------
website based on Nguyen's lecture 9 scribe note