Slashdot Mirror


Denial-of-Service Attack Found In Btrfs File-System

An anonymous reader writes "It's been found that the Btrfs file-system is vulnerable to a Hash-DOS attack, a denial-of-service attack caused by hash collisions within the file-system. Two DOS attack vectors were uncovered by Pascal Junod that he described as causing astonishing and unexpected success. It's hoped that the security vulnerability will be fixed for the next Linux kernel release." The article points out that these exploits require local access.

44 of 210 comments (clear)

  1. Who ported btrfs to DOS? by Nimey · · Score: 4, Funny

    and should we give him a medal or lynch him?

    --
    Hail Eris, full of mischief...

    E pluribus sanguinem
    1. Re:Who ported btrfs to DOS? by macraig · · Score: 5, Funny

      Do I have to choose? Can I hang a medal on him, and then hang him? I'll make the medal 20 pounds to speed up the lynching.

    2. Re:Who ported btrfs to DOS? by maxwell+demon · · Score: 3, Informative

      DOS = Disk Operating System
      DoS = Denial of Service

      --
      The Tao of math: The numbers you can count are not the real numbers.
    3. Re:Who ported btrfs to DOS? by byornski · · Score: 3, Funny
  2. Can we get a real Linux filesystem, please? by Anonymous Coward · · Score: 5, Interesting

    btrfs is a step in the right direction, but even now, Linux does not have production-level deduplication (which even Windows has, for crying out loud), encryption, snapshots, or something even close to supplanting LVM2.

    I just got out of a meeting at my job because we are replacing some old large servers... and because Linux has no stable filesystem with enterprise features, looks like things are either going to Windows, or perhaps Solaris x86 (which is expensive.)

    This doesn't mean to suck Sun's teat for ZFS access... but at least try to come close to what even NTFS or even ReFS offers...

    1. Re:Can we get a real Linux filesystem, please? by Anonymous Coward · · Score: 5, Informative

      ZFS on FreeBSD or FreeNAS is great. Easily saturates gigE with a simple mirror of recent 7200rpm disks. It scales up from there, and FreeBSD is pretty rock solid.

    2. Re:Can we get a real Linux filesystem, please? by Anonymous Coward · · Score: 4, Interesting

      btrfs is a step in the right direction, but even now, Linux does not have production-level deduplication (which even Windows has, for crying out loud), encryption, snapshots, or something even close to supplanting LVM2.

      I just got out of a meeting at my job because we are replacing some old large servers... and because Linux has no stable filesystem with enterprise features, looks like things are either going to Windows, or perhaps Solaris x86 (which is expensive.)

      This doesn't mean to suck Sun's teat for ZFS access... but at least try to come close to what even NTFS or even ReFS offers...

      Hear hear! Backup admin here, just want to add before the unwashed masses of armchair Linux admins show up, one example of an enterprise filesystem feature is the NTFS change journal. It makes the file system scan as part of an incremental backup run in constant time.

      It's sad on other systems with large numbers of files to schedule subdirectories for different times of day to deal with scanning overhead.

    3. Re:Can we get a real Linux filesystem, please? by Tough+Love · · Score: 5, Informative

      NTFS doesn't have snapshots. Instead it relies on volume shadow copies, with known severe performance artifacts caused by needing to move snapshotted data out of the way when new writes come in. Btrfs, like ZFS and Netapp's WAFL, use a far more efficient copy-on-write strategy that avoids the write penalty. The takeaway: I would not go so far as to claim Microsoft has an enterprise-worthy solution either. If you want something with industrial strength dedup, snapshots and fault tolerance, you won't be getting it from Micorosft.

      --
      When all you have is a hammer, every problem starts to look like a thumb.
    4. Re:Can we get a real Linux filesystem, please? by smash · · Score: 2

      Data integrity for one?

      --
      I run: Windows, OS X, Linux, FreeBSD. Just because you have a hammer, doesn't mean everything is a nail.
    5. Re:Can we get a real Linux filesystem, please? by grumbel · · Score: 3, Informative

      I have seen the userlevel ZFS crash multiple times, it's also slow as hell. It's still worth it if you are short on storage and want to reduce the size of your backup, but I wouldn't exactly call it ready for production.

    6. Re:Can we get a real Linux filesystem, please? by Anonymous Coward · · Score: 2, Interesting

      Wouldn't it be cheaper and just as effective to use FreeBSD or FreeNAS for your data? if you're considering either Windows or Solaris then obviously you don't need a specific operating system. I would think FreeBSD (or even ZFS on Linux) would suit your purposed better 9and with less expense) than Windows or Solaris.

    7. Re:Can we get a real Linux filesystem, please? by maz2331 · · Score: 5, Informative

      ZFS on Linux does exist as a kernel module that is pretty stable and works well. http://zfsonlinux.org/ -- it was put out by Lawrence Livermore National Lab, but can't be included with the kernel distros due to GPL / CDDL license compatability issues.

    8. Re:Can we get a real Linux filesystem, please? by dbIII · · Score: 3, Informative

      Kernel level probably is ready, but not on 32bit (big hassles there but probably not a big deal to most) and on 64 bit there are some memory usage problems and performance seems to suck when there's a dozen or so hosts keeping connections to files on ZFS open via NFS at the same time. There's still a way to go before ZFS on linux gets to where it is on FreeBSD but it's still early days, and for many usage patterns it looks like it is ready for production.

    9. Re:Can we get a real Linux filesystem, please? by Anonymous Coward · · Score: 2, Informative

      Linux has production level encryption, snapshots, and LVM2. What are you talking about?

      Unless you have very specific uses, deduplication should be done at your storage array really. It's not a high priority to implement in the filesystem. (No, your anecdote does not make it a high priority).

    10. Re:Can we get a real Linux filesystem, please? by WWJohnBrowningDo · · Score: 2

      Did you guys look at FreeBSD?

    11. Re:Can we get a real Linux filesystem, please? by jamesh · · Score: 4, Insightful

      NTFS doesn't have snapshots. Instead it relies on volume shadow copies, with known severe performance artifacts caused by needing to move snapshotted data out of the way when new writes come in. Btrfs, like ZFS and Netapp's WAFL, use a far more efficient copy-on-write strategy that avoids the write penalty. The takeaway: I would not go so far as to claim Microsoft has an enterprise-worthy solution either. If you want something with industrial strength dedup, snapshots and fault tolerance, you won't be getting it from Micorosft.

      What nonsense. VSS is the snapshot solution for NTFS, and of course it uses copy-on-write. Microsoft VSS backup architecture is years ahead of Linux... LVM is kind of cool but if you have a single database spread across multiple LV's then you can't snapshot them all as an atomic operation so it becomes useless. MS VSS does this, and always has.

      I'm normally a Linux fanboi but when you sprout rubbish like this I have no hesitation in correcting you.

    12. Re:Can we get a real Linux filesystem, please? by Agent+ME · · Score: 2

      If snapshots are handled by the filesystem, then it could be possible to snapshot a specific directory or file rather than a whole partition for example. Snapshots in the filesystem also prevents stuff like changes to space that was free when the snapshot was taken from being unnecessarily remembered.

    13. Re:Can we get a real Linux filesystem, please? by Anonymous Coward · · Score: 3, Informative

      Tried to find some more information on this. First discovery: VSS stands for "Volume Shadow copy Service", not "Visual SourceSafe", as was my first association. :)

      AFAICT he's saying pretty much what Microsoft is saying:

      When a change to the original volume occurs, but before it is written to disk, the block about to be modified is read and then written to a "differences area", which preserves a copy of the data block before it is overwritten with the change. Using the blocks in the differences area and unchanged blocks in the original volume, a shadow copy can be logically constructed that represents the shadow copy at the point in time in which it was created.

      The disadvantage is that in order to fully restore the data, the original data must still be available. Without the original data, the shadow copy is incomplete and cannot be used. Another disadvantage is that the performance of copy-on-write implementations can affect the performance of the original volume.

      Do you have a newer reference?

    14. Re:Can we get a real Linux filesystem, please? by LordLimecat · · Score: 3, Informative

      FAT32 is going to be faster than a LOT of filesystems precisely because it lacks features like dedup, any notion of real ACLs, and, oh, I dont know, data integrity. Thats why if you want a really fast RAMDisk, you dont use NTFS or ReFS, you use FAT16 or FAT32.

    15. Re:Can we get a real Linux filesystem, please? by Tough+Love · · Score: 5, Informative

      VSS is the snapshot solution for NTFS, and of course it uses copy-on-write

      Well. Maybe you better sit down in a comfortable chair and think about this a bit. From Microsoft's site: When a change to the original volume occurs, but before it is written to disk, the block about to be modified is read and then written to a “differences area”, which preserves a copy of the data block before it is overwritten with the change.

      Think about what this means. It is not a "copy-on-write", it is a "copy-before-write". Gross abuse of terminology if anybody tries to call it a "copy-on-write", which has the very specific meaning of "don't modify the destination data". Instead, copy it, then modify the copy. OK, are we clear? VSS does not do copy-on-write, it does copy-before-write.

      Now let's think about the implications of that. First, the write needs to be blocked until the copy-before-write completes, otherwise the copied data is not sure to be on stable storage. The copy-before-write needs to read the data from its original position, write it to some save area, then update some metadata to remember which data was saved where. How many disk seeks is that, if it's a spinning disk? If the save area is on the same spinning disk? If it's flash, how much write multiplication is that? When all of that is finally done, the original write can be unblocked and allowed to proceed. In total, how much slower is that than a simple, linear write? If you said "on the order of an order of magnitude" you would be in the ballpark. In face, it can get way worse than that if you are unlucky. In the best imaginable case, your write performance is going to take a hit by a factor of three. Usually, much much worse.

      OK, did we get this straight? As a final exercise, see if you can figure out who was talking nonsense.

      --
      When all you have is a hammer, every problem starts to look like a thumb.
    16. Re:Can we get a real Linux filesystem, please? by Tough+Love · · Score: 2

      If you keep all old file where in their original sectors and write changes in new places, your files get fragmented to hell.

      Microsoft's "shadow copy" doesn't work at the file level, it works at the block level, so it doesn't know anything about files. Btrfs and its ilk try to leave some empty space distributed across the volume, so copy-on-write can leave the copies in fairly reasonable places. After the copy is committed, the original space can be freed, so the next update won't mess things up too badly either. Snapshots mess this up because the original space doesn't get freed. But then, snapshots are always messed up, there is no such thing as a perfect snapshot strategy with respect to disk seeking. Incidentally, with flash you don't care about that any more, there is no seek time.

      Anyway, yes, with a crappy copy-on-write (like Netapp's) you get horrible read fragmentation. With an intelligent implementation, it isn't so bad. Note that Btrfs is turning in good benchmarks, including read performance in mixed read/write loads.

      --
      When all you have is a hammer, every problem starts to look like a thumb.
    17. Re:Can we get a real Linux filesystem, please? by jamesh · · Score: 4, Insightful

      VSS is the snapshot solution for NTFS, and of course it uses copy-on-write

      Well. Maybe you better sit down in a comfortable chair and think about this a bit. From Microsoft's site: When a change to the original volume occurs, but before it is written to disk, the block about to be modified is read and then written to a “differences area”, which preserves a copy of the data block before it is overwritten with the change.

      Think about what this means. It is not a "copy-on-write", it is a "copy-before-write". Gross abuse of terminology if anybody tries to call it a "copy-on-write", which has the very specific meaning of "don't modify the destination data". Instead, copy it, then modify the copy. OK, are we clear? VSS does not do copy-on-write, it does copy-before-write.

      Now let's think about the implications of that. First, the write needs to be blocked until the copy-before-write completes, otherwise the copied data is not sure to be on stable storage. The copy-before-write needs to read the data from its original position, write it to some save area, then update some metadata to remember which data was saved where. How many disk seeks is that, if it's a spinning disk? If the save area is on the same spinning disk? If it's flash, how much write multiplication is that? When all of that is finally done, the original write can be unblocked and allowed to proceed. In total, how much slower is that than a simple, linear write? If you said "on the order of an order of magnitude" you would be in the ballpark. In face, it can get way worse than that if you are unlucky. In the best imaginable case, your write performance is going to take a hit by a factor of three. Usually, much much worse.

      OK, did we get this straight? As a final exercise, see if you can figure out who was talking nonsense.

      I concede that the terminology used by the MS article is misused. I don't think you're thinking the performance issues through though. You start with a file nicely laid out linearly on disk, and you take a snapshot so you can make a backup. Now you make a modification to the middle of the file and what happens? Suddenly the middle of the file is elsewhere on disk, and in the case of LVM this is invisible to the filesystem so no amount of defragging is going to fix it. This situation persists long after you have taken your backup and thrown the snapshot away. Of course this doesn't matter for flash but we're not all there yet. If BTRFS does snapshots using copy-on-write (correct definition) then this will be a problem too, although if BTRFS is smart enough it should be able to repair the situation once the snapshot is discarded.

      VSS's way leaves the original data in-order on the storage medium. The difference area is likely on a completely different disk anyway so the copy-on-write (MS definition) could not be performed any other way.

    18. Re:Can we get a real Linux filesystem, please? by Tough+Love · · Score: 2, Informative

      Modifications in the middle of files are extremely rare. It's true, running a database on top of a snapshotted spinning disk is probably going to suck. For normal users, keeping regular files mostly linear, and files in the same directory nearby each other is what matters, and yes, Btrfs does a credible job of that.

      I know why shadow copy works the way it does. 1) It's simple, therefore likely to work. 2) It's an easy answer to the "how do you control fragmentation" question. But the write performance issue is so bad that it's a poor solution no matter how you justify it. It's just an attempt to get away with being lazy for a largely uncritical audience that isn't big into benchmarking, or indeed, isn't used to good disk performance.

      --
      When all you have is a hammer, every problem starts to look like a thumb.
    19. Re:Can we get a real Linux filesystem, please? by jamesh · · Score: 2

      I'm still not getting how you can simultaneously snapshot dbdata (optimised for read and write) and logdata (optimised for write) as an atomic operation. "Tough Love (215404)" said "concatenate them together" but I don't get what that means in this context.

      Last time I checked you would still have to snapshot one, then the other, and the resulting snapshots are almost certainly not going to give you a consistent backup because there would have been writes between the first and the second snapshots.

    20. Re:Can we get a real Linux filesystem, please? by LWATCDR · · Score: 2

      Wow, just how many clueless people are on Slashdot posting as ACs?
      "No good deduplication software? Don't put duplicate data on the system in the first place!"
      Okay Sparky you have 5000 users on a server and that all save that email about vacation time or the pictures from the office party. Redundant data. This is a large system with lots of users, it is not for you leet Linux box you have in your mom's basement. Your plays on Microsoft's name are also childish and over done. Now there is a valid argument that deduplication of data should be done at the array level so that it does not need to be filesystem dependant but that is an argument for knowledgeable adults and not for the likes of you.

      You may go now, you bore me. You may come back when you learn enough to be interesting.

      --
      See my blog http://ilovecookes.blogspot.com/ for light hearted technical information.
    21. Re:Can we get a real Linux filesystem, please? by dna_(c)(tm)(r) · · Score: 2

      [...]I just got out of a meeting at my job [...]and because Linux has no stable filesystem with enterprise features [...]

      Sure, AC has some real complex stuff to handle on an enterprise level. That's why all the big boys like Google, Facebook and Twitter are using Windows to host their data...

      You're either a silly moron, a self deluding enterprisy [a-z]+architect or a very capable troll.

    22. Re:Can we get a real Linux filesystem, please? by Zero__Kelvin · · Score: 2

      "I just got out of a meeting at my job because we are replacing some old large servers... and because Linux has no stable filesystem with enterprise features, looks like things are either going to Windows, or perhaps Solaris x86 (which is expensive.)"

      Somebody notify the millions of Enterprise servers that are Linux based, and serving up a major portion of the internet's content every day! Talk about throwing the baby out with the bathwater. Basically, you don't want to take a chance that established filesystems that have been in use in a corporate environment for well over a decade might fail someday, so you are considering going with an OS that is known to be unstable and requires regular reboots just to keep it's security "up to date" (which doesn't mean secure). Bravo! Way to totally foul up a basic system analysis!

      Somebody should invent RAID and regular backups!

      --
      Guns don't kill people; Physics kills people! - John Lithgow as Dick Solomon on Third Rock From The Sun
    23. Re:Can we get a real Linux filesystem, please? by petermgreen · · Score: 2

      Also, ZFS is an insane thing written by people who don't seem to understand that keeping a good separation of concerns can lead to a rather slick set of general tools that can be used on almost any fs.

      Separating stuff into layers has benefits but it also has costs. Sometimes merging layers can make things practical that aren't practical with them separate. Afaict this is what drove the creation of zfs and btrfs.

      Lets first look at RAID. traditional raid provides protection against reads that fail but not against reads that silently return wrong data. Experience has shown that hard drives cannot be trusted not to silently return wrong data. Worse still raid resyncs after power failure may silently overwrite good data with corrupt data. Adding checksums in the raid layer is difficult because there is nowhere good to put them (you can't just make the blocks slightly smaller because filesystems expect power of two block sizes). Putting checksums in the filesystem helps a bit but even if there is an API to request the "other copy" when the filesystem detects corrupt data the aforementioned resync may have already overwritten the good version with the bad one. By moving the responsibility for storing data redundantly into the filesystem we can avoid this problem, when going a consistency check the filesystem can check both copies against the checksum it keeps and ensure it overwrites the bad version with the good one rather than vice-versa

      Also traditional raid requires the whole array to have the same level of redundancy. It's possible to work around this by having multiple arrays but that then means you have to manually allocate space between the arrays. Yes there are ways to grow and shrink arrays but it's extra work and may involve downtime. With redundancy at the filesystem layer you should just be able to tell the filesystem what level of redundancy you want for each directory and let the free space be used for any of them.

      Now lets consider snapshots. Snapshots below the fileystem layer mean that you waste effort snapshotting free space. Worse still if writing to a snapshoted volume works by remapping blocks then it creates fragmentation in the mapping which is likely to stay around forever. This fragmentation happens even if the blocks were previously free (due to the fact we are snapshoting free space) and may stick around even after the file that caused it to happen is long gone. With snapshots at the filesystem level you don't snapshot free space and while you still get fragmentation you only get it when modifying an existing file (not when creating a new file) and it goes away when the file is deleted. Finally having snapshots at the filesystem layer means you don't have to snapshot the whole filesystem, you can snapshot individual directories within it.

      Now lets consider dedupe if you do it below the filesystem layer then to get much benefit from it you have to make your logical devices larger (in aggregate) than your physical devices. That is likely to lead to some very strange errors when you run out of physical blocks but the filesystems still think they have free space. It can also lead to the problem of "garbage" that the dedupe layer thinks needs to be preserved even though it's not actually in use by the filsystem (granted a trim-like API between the filesystem and the dedupe layer could fix this).

      With encyrption having encryption as part of the filesystem allows you to chose what you do and don't want encrypted without having to mess arround with seperate volumes and the administrative overhead threof (see previous comments about raid) though how useful this is and whether it is worth the increased risk (too easy to leave clues behind unencyrpted) depends hugely on your threat model.

      --
      note: i'm known as plugwash most places but i screwd up registering that here somehow in the past and now can't register
  3. Requires local access by Anonymous Coward · · Score: 5, Funny

    no more dangerous than a fork bomb or filling up /tmp or trying to compile open office.

    1. Re:Requires local access by cryptizard · · Score: 5, Informative

      Sort of, but at least you can recover from those attacks by restarting or booting from an external source to clean up your filesystem. The second attack here leaves you with undeletable files because the file system code responsible for deleting cannot handle the multiple hash collisions. There is no way to recover from that until a patch is pushed out that fixes the problem.

    2. Re:Requires local access by blade8086 · · Score: 2

      Which, without the over sensationalized BS that is this story, will probably be in about a week tops.

      And since BTRFS is not in any 'enterprise' Linux Distributions, means that it will pretty much be available
      immediately since everyone running it in critical production environments will probably be running
      pretty bleeding edge linuxen

    3. Re:Requires local access by cryptizard · · Score: 2

      Two files with the same hash is not a problem, it is allowed. This will happen just by chance many times on your filesystem because the hash is relatively short (64 bits). The problem is when you engineer many files to have the same hash and your data structure (hash table) degrades to an array. There is also some other problem in the code here that makes it so the the hash table can't store or for some reason can't process more than a certain number of collisions.

  4. Nice! by gweihir · · Score: 3, Interesting

    "Algorithmic Complexity Attacks" like this one have long been known, but rarely been documented publicly. One good example to point out why hash-randomization is a good idea!

    --
    Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
    1. Re:Nice! by Anonymous Coward · · Score: 3, Funny

      Words, they mean nothing! Take 'rarely' for example, who gives a shit, I'll read it as 'never' same thing.

  5. Nice this was found before BTRFS goes stable by Anonymous Coward · · Score: 5, Insightful

    Hopefully more people start fuzzing btrfs so it is that much better when it is declared stable.

  6. Good god man by tomp · · Score: 2

    "Denial-of-Service Attack Found In Btrfs File-System" didn't happen. A vulnerability was found. That's a big deal, no reason to obscure it.

  7. Attack? by Decameron81 · · Score: 2

    An attack was found in the filesystem? What's that supposed to mean?

    --
    diegoT
  8. No by ArchieBunker · · Score: 2, Interesting

    Instead of picking a filesystem and moving forward people will moan and cry and eventually split into a few different groups with beta level implementations. Sound on Linux is a great example. Two completely different sound drivers that both work half assed. What's the word with XFS these days?

    --
    Only the State obtains its revenue by coercion. - Murray Rothbard
  9. Re:CRC by maxwell+demon · · Score: 2

    Or just use a RB tree instead of a linear list for hash collisions, then you get only O(log n) instead of O(n) worst case search performance.

    To quote Wikipedia:

    Instead of a list, one can use any other data structure that supports the required operations. For example, by using a self-balancing tree, the theoretical worst-case time of common hash table operations (insertion, deletion, lookup) can be brought down to O(log n) rather than O(n). However, this approach is only worth the trouble and extra memory cost if [...] one must guard against many entries hashed to the same slot (e.g.[...] in the case of web sites or other publicly accessible services, which are vulnerable to malicious key distributions in requests).

    While a file system is not generally publicly available (actually it may be, if e.g. used on an FTP server), it is still shared.

    --
    The Tao of math: The numbers you can count are not the real numbers.
  10. Re:Dedupe doesn't belong in a filesystem by LWATCDR · · Score: 3, Informative

    You then turn it off.... And go take your meds.
    I do not think you know what DeDup means. You as a user still see two copies of the file. If you make changes to one copy of the file it will only change that copy of the file. It is not like a link. In other words it is totally transparent to the end user but saves drive space. So if you work in a large organization and someone sends out an email to all 4000 people that email will only take up the space of one email. Even if everyone saves it the imap server.

    In other words you do not know what you are talking about, you probably do not need these functions because you probably do not run a server or servers for a large organization, you seem to have some anger issues, and maybe just a little nuts.

    --
    See my blog http://ilovecookes.blogspot.com/ for light hearted technical information.
  11. Can we get a real editor? by Anonymous Coward · · Score: 2, Insightful

    Editors please! I normally expect even a submitter to know the difference between an attack and a vulnerability. However the editor damn well better know the difference. When I read that an ATTACK had been found in btrfs I went to read about how some malicious code had been placed into the code for btrfs. Maybe this code modified data, erases stuff, sends data to China, or just renames files. But no, this was a simple vulnerability. They didn't find an attack in btrfs, they found the potential for an attack - which is called a vulnerability. Let's at least make an effort here.

    1. Re:Can we get a real editor? by Nimey · · Score: 2

      ed(1) is the standard text editor.

      --
      Hail Eris, full of mischief...

      E pluribus sanguinem
  12. Re:Another crazy white guy goes on a rampage by Zero__Kelvin · · Score: 2

    It is stupid to make this racial, but since you did, when was the last time a black guy opened up on a group of innocent school children?

    --
    Guns don't kill people; Physics kills people! - John Lithgow as Dick Solomon on Third Rock From The Sun
  13. Epic Fail (The joke's on you) by Zero__Kelvin · · Score: 2

    A good joke requires significantly planning.

    --
    Guns don't kill people; Physics kills people! - John Lithgow as Dick Solomon on Third Rock From The Sun