13 ms·

Malloc broke Serenity's JPGLoader, or: how to win the lottery

335 points by trashburger 5y ago

deleted 5y ago
[deleted]
RcouF1uZ4gsC 5y ago
Hyrum's Law strikes again: With a sufficient number of users of an API, it does not matter what you promise in the contract: all observable behaviors of your system will be depended on by somebody. https://www.hyrumslaw.com/ https://www.hyrumslaw.com/
- qayxc 5y ago
  Mark my words: Hyrum's Law will strike in full force and introduce a whole new world of pain once more and more software development will be done (or helped-) by machine learning. What happened here is a perfect example of what an optimiser might come up with and resulting systems will be so brittle and delicate that a whole new form of cargo cult might develop around them :D
  - coliveira 5y ago
    Future systems will be like human genome: a small letter change will lead to the system self destroying after 20 days of flawless operation.
    - deleted 5y ago
      [deleted]
    - tryauuum 5y ago
      I wonder if there actually is a possibility of something like that in human genome. Are there any known bugs that can be introduced to human genome and instantly kill a human after, e.g. 18 years of normal operation?
      - a_t48 5y ago
        Aneurysms.
      - NavinF 5y ago
        Do genes associated with cancer count? I can't think of anything that kicks in instantly, but there are plenty of probabilistic bugs
      - masklinn 5y ago
        “Known” probably not because nobody cares but if you can edit the generic code of all cells (not just one) you just need to do a function-affecting substitution of a protein-coding segment for a vital protein. Doesn’t matter which one as long as it’s not solely developmental. It would not quite be instant though, the body would first have to run out of the existing supply then break down as operations stop. If you pick the right protein (e.g. something affecting the muscles or brain) I’d think the timescale would be minutes if not seconds. If you can only edit one cell or a small number if them then probably not, you can definitely cause long-term issues (e.g. cancers) but I would not think instant death an option. I think the GP was talking more about existing genetic defects leading to sudden issues down the line though.
    - masklinn 5y ago
      Surely they’d already the case? There’s tons of latent bugs which are only revealed because the conditions to trigger them have not been encountered yet. Every 4 years code breaks all over in leap days. A program crashing after not crashing is essentially “the system self destroying”.
- Zababa 5y ago
  It's intersting to see that some people add randomness to fight this, for example with maps in Go. It seems like it's the right choice.
  - MaulingMonkey 5y ago
    Inserting randomness can help prevent denial of service attacks as well, by making it harder to manufacture pathological hash collisions (which can turn ~O(1) operations into O(N) operations).
  - ncmncm 5y ago
    Right, like every release of any component should vary some detail that the spec doesn't guarantee. Especially, all hash functions should change on every release -- at least when building in debug mode.
    - vlovich123 5y ago
      Hash functions should use a random seed on every new container instance (or at least once per launch). Those hash tables that need specific properties of the hash should inject it in that way (cryptographic, deterministic, DOS-resistant, etc).
  - jeffbee 5y ago
    Another place to insert randomness that could have uncovered this would be in the allocator size classes. In non-optimized builds, if your allocator has size classes, just pick them randomly. In my experience this uncovered a lot of bugs in programs linked against tcmalloc.
  - yxhuvud 5y ago
    Other people fight it by adding a defined iteration order. That works just as well and don't introduce randomness.
    - wizzwizz4 5y ago
      But prevents optimisation, if that optimisation would lose the iteration order. If you need defined ordering in your type, use it. Otherwise, don't specify it.
- tialaramex 5y ago
  There's even a CPPCon talk about Google's "Swiss" tables with interruptions by Hyrum each time the new code's observable behaviour changes because, at Google, they internally have enough users for Hyrum's law to kick in all the time: https://www.youtube.com/watch?v=JZE3_0qvrMg https://www.youtube.com/watch?v=JZE3_0qvrMg The talk was presumably better live because Hyrum doesn't have a microphone, so his interjections are hard to follow, but it's a good way to illustrate. Some of the examples are much like this story, you design this sophisticated, heavily optimised unordered container for millions of items, and then your users put three items into it, and they depend on the order of those items and you "broke" their code by not having this behaviour you never promised and it made no sense to depend on. And the defence mentioned in this thread (randomise things which aren't guaranteed to have stability) is introduced because these are Google employees, they know about Hyrum, it just isn't enough. Sure the code failed when I tried to store 40 items due to your randomisation, but I found it worked OK with ten items as then the randomisation was defeated, so now I store ten items, and then your latest change broke that... The pathological use of data structure is why stuff like making the constructor for empty strings very cheap has a big effect on some codebases. Rust const-ified String::new() because an empty string doesn't need any heap store. So this means code which loops over a large array setting all the members to the empty string is only about as expensive as looping over an integer array setting all the integers to zero, it doesn't incur a heap allocation, or a function call. Of course modifying these strings now takes on the expense of allocating, but guess how often people who do stuff like this never actually touch the string...
  - rasz 5y ago
    >they depend on the order of those items and you "broke" their code by not having this behaviour you never promised and it made no sense to depend on reminds me of a time my extension started glitching because localStorage stopped returning results in same order they were put in :o) Now that I think about it it happened somewhere around 2017-2018, did google drop it into Chrome at this point?
dvt 5y ago
Great read, and fantastic debugging! Correct me if I'm wrong, but I think this bug would have been caught if a CMYK JPEG would've been tested, assuming that an extra component would break the accidental well-orderedness of the stream.
- trashburger 5y ago
  I'm pretty sure Serenity does not support CMYK colors right now, if I understand this snippet correctly :^) if (context.component_count != 1 && context.component_count != 3) { dbgln_if(JPG_DEBUG, "{}: Unsupported number of components in SOF: {}!", stream.offset(), context.component_count); return false; }
  - Flex247A 5y ago
    :^)
sunyc 5y ago
TLDR: Logically Wrong program was working under an specific condition that no longer exists, thus broken.
jeffbee 5y ago
Ignoring the tasteless act of trying to use the slack at the end of an allocation for your side projects, the bug really highlights the dangers of illiterate interfaces, to wit Color::Color(u8 r, u8 g, u8 b) from Serenity LibGfx. Calling this incorrectly is incredibly easy to do and invisible to the reader at the call site. Authors need to work with the type system to avoid these bugs, in this case having distinct types for red, green, and blue so the compiler will stop you from assigning red to blue without an explicit conversion. "Simple confusion of RGB vs. BGR" is not something that should seem natural to programmers. It's an error caused by underuse of the type system, just treating everything as a bag of numbers.
- dvt 5y ago
  > "Simple confusion of RGB vs. BGR" is not something that should seem natural to programmers. These kinds of errors are extremely common in much more mature libraries, including OpenCV, as well as HLSL or GLSL. No disrespect, but it sounds like you've never really touched graphics programming before. Color spaces are literally just a bag of numbers. A good analogy is coordinate systems. There's no type difference between an x-coordinate or a y-coordinate; they're just numbers and are defined by their ordinal position in an (x, y) tuple.
  - owl57 5y ago
    Also, even if we model the color space in some overly clever way, we are talking about a JPEG loader here. Its input is inevitably a bag of numbers, and a horribly underspecified one.
    - owl57 5y ago
      I felt like I forgot to add a link. Why don't we see images in wrong color space nearly as often as text with wrong character encoding, remains a mystery to me since the moment I was writing a toy JPEG decoder and found this article: https://entropymine.wordpress.com/2018/10/22/how-is-a-jpeg-images-color-type-determined/ https://entropymine.wordpress.com/2018/10/22/how-is-a-jpeg-i...
thangalin 5y ago
"If a professor makes a sexist joke, a female student might well find it so disturbing that she is unable to listen to the rest of the lecture. Suggestive pictures used in lectures on image processing are similarly distracting to the women listeners and convey the message that the lecturer caters to the males only. For example, it is amazing that the Lena pin-up image is still used as an example in courses and published as a test image in journals today." ~D. P. O'Leary, 1999 http://www.cs.umd.edu/users/oleary/faculty/node8.html http://www.cs.umd.edu/users/oleary/faculty/node8.html Alternatives: http://sipi.usc.edu/database/database.php?volume=misc http://sipi.usc.edu/database/database.php?volume=misc
- 1970-01-01 5y ago
  The sources for D.P. O'Leary's references are all dead.
  - re 5y ago
    The links are dead, but the citations are valid. Here are working links: J. Gutbezahl, How Negative Expectancies and Attitudes Undermine Females' Math Confidence and Performance: A Review of the Literature. https://eric.ed.gov/?id=ED380279 https://eric.ed.gov/?id=ED380279 E. Spertus, Why are There so Few Female Computer Scientists? https://hdl.handle.net/1721.1/7040 https://hdl.handle.net/1721.1/7040
    - 1970-01-01 5y ago
      So I looked into these links. On [3] there is no data that backs this quote of hers: "Suggestive pictures used in lectures on image processing are similarly distracting to the women listeners and convey the message that the lecturer caters to the males only." The 30 (!) year old Spertus paper even states that most of the data collected was anecdotal.
- young_unixer 5y ago
  How is Lenna's picture disturbing or suggestive?
evmar 5y ago
To prevent these kinds of bugs, the iteration order in a Go map is randomized across each execution.
- iab 5y ago
  Does that prevent, or more expose?
  - klodolph 5y ago
    I think the general idea is "shift left" which you can say exposes bugs earlier, or prevents bugs from reaching production, which is kind of a "six dozen of one, half dozen of the other". Bugs which are exposed early enough do not get committed. "Shift left" just means that you shift the feedback to the developer farther left in the build process, closer (in time and space) to when the mistake was made.
  - EE84M3i 5y ago
    I don't know about go specifically, but many languages randomize their hash tables to avoid Hash Collision DoS attacks. This is a problem for any piece of software putting attacker-controlled data into a hash-table that does not randomize the hashing and where they assume that it will be amortized constant time.
    - masklinn 5y ago
      Go does have that, but it also specifically and explicitly randomises iteration order.
      - EE84M3i 5y ago
        Is that a separate implementation?
        masklinn 5y ago
        No, it’s the builtin hashmap. It had a random seed for the hash to avoid collision predictability but it also, separately has a shuffled iteration order for maps.
userbinator 5y ago
I think the most important lesson of this article is in this sentence: Why this code was written this way instead of just checking against the ID by linearly iterating over the Components, I have no idea. There's another comment here that shows their JPEG decoder only supports 1 or 3 components. Using a hash table for at most 3 entries is astronomical overkill! The field for the number of components in a JPEG file is only a byte - so even if you were to support more than 3 components, it would be 255 at most, and sane JPEG files are unlikely to have more than 4 in practice. So fixed-size arrays are the perfect solution. I have a very good idea why it was written like that, however: the mere availability and ease of use of abstract data structures naturally leads to their overuse by what seems to be an overwhelming majority of developers, and the eagerness to "futureproof" and add unnecessary complexity is also very common. Overcomplexity creates bugs, and (leaky) abstractions hide them. Even if the complexity (and bug) isn't visible in your code, it's still there. If the initial code had been reviewed by me, it most certainly would not pass. I am saying this as someone who has actually written a JPEG decoder --- it is not as difficult as it may sound, and I highly recommend giving it a try --- and also witnessed (and fixed) the messes that people get in with overcomplicating things. Perhaps that slight "architecture astronaut" mentality comes from starting with a higher-level language; I started with Asm and my preferred language is usually C, and I haven't seen the tendency to overcomplicate much in others who did the same. The reason the Components were in a hash table was that they would then be checked against the component ordering in a “Start of Scan” section to make sure all the components in the SOS section are in the expected order. For comparison, this is the corresponding code in my JPEG decoder. I didn't even bother using a loop: if(read_byte()!= cids[0]) data_error("SOS scan first component must match"); hts[0] = read_byte(); /* high nybble: DC table index; low nybble: AC table index */ if(read_byte() != cids[1]) data_error("SOS scan second component must match"); hts[1] = read_byte(); if(read_byte() != cids[2]) data_error("SOS scan third component must match"); hts[2] = read_byte();
- deleted 5y ago
  [deleted]
- logicchains 5y ago
  >I have a very good idea why it was written like that, however: the mere availability and ease of use of abstract data structures naturally leads to their overuse by what seems to be an overwhelming majority of developers, and the eagerness to "futureproof" and add unnecessary complexity is also very common. To give some context, iterating over an array of three small items takes worst case roughly 100ns(cache miss), best case 1ns(l1 cache hit). Most common hashmap implementations (like std::unordered_map) dynamically allocate items so they're stored randomly in memory, giving roughly 300ns worst case(3 cache misses), 3ns best case(3 l1 cache hits) for iterating over them. So using a hash map is going to be 3x slower without even accounting for the time spent hashing, and 3x more likely to hit the worse case due to requiring three cachelines still in the l1 cache for best performance as opposed to just one. If regularly adding/deleting items, using a std::unordered_map would literally be orders of magnitude slower due to using malloc/free for each item added/removed.
raggi 5y ago
I can absolutely confirm that this is what it's like to diagnose weird bugs on nascent operating systems, particularly on or nearby "portability boundaries", which are not always what you think they are. Pull that thread, but be sure you're ready for jenga.
asdfasgasdgasdg 5y ago
This bug is an example of why the absl swiss tables have nondeterministic iteration order. Found so many bugs in the codebase when this got turned on. https://abseil.io/docs/cpp/guides/container#iteration-order-instability https://abseil.io/docs/cpp/guides/container#iteration-order-...
- yxhuvud 5y ago
  Yes, hash tables need to iterate in either a guaranteed order (usually insertion order) or a guaranteed to be random order. Either choice make sense, but one of them needs to be picked or people will create bugs like this.
  - masklinn 5y ago
    FWIW most modern hash tables are randomised on a per-run basis as side-effect if the hash being seeded with a random value for attacker-controlled collision resistance.
    - mikemike 5y ago
      One year ago I hardened LuaJIT's VM against these kind of attacks. Since then, there has been a constant influx of complaints and issues filed. All bitterly complaining their code, which mistakenly assumed a fixed hash table iteration order, is now broken. Even when told that the Lua manual clearly states the undefined order since 20 years, they do not cease to complain. They do not realize this change helped them to discover a serious bug in their code (the order could differ even before that change). Sigh. You can now have a guess, what one of the lesser enlightened forks of LuaJIT did ...
      - masklinn 5y ago
        I’m not surprised. The same issue occurred in python. And to be fair it’s a pain in the ass to debug and find out why something happens to implicitly depend on iteration order (float stability is common but not alone). And their code did work beforehand, for most values of work. The biggest pain in the ass is that — at least in python - while you can set the hash seed explicitely if you don’t the langage doesn’t tell you. This makes reproducing the issue very annoying when only some seeds trigger it. > the order could differ even before that change While the order could differ I assume it was deterministic and nothing influencing those bits had changed in a while.
cratermoon 5y ago
malloc didn't break JPGLoader. The code was already broken, malloc just exposed the bug
- rocqua 5y ago
  The code was wrong, but the produced binaries were not. From the user perspective, a change to malloc really did break JPGLoader. That it broke this by revealing a pre-existing fault in the code is interesting to note. Especially for the developers. But it does not change the user experience.
happyweasel 5y ago
Come on, just use a Map/Dictionary structure where ordered key iteration is possible..
deleted 5y ago
[deleted]
indolering 5y ago
Fuck, Lenna [1]? Could we stop alienating women in tech [2]? Don't take my word for it, the AV1 folks are pleading with the field to stop using Lenna too [3]. [1]: https://en.wikipedia.org/wiki/Lenna#Criticism https://en.wikipedia.org/wiki/Lenna#Criticism [2]: https://xkcd.com/322/ https://xkcd.com/322/ [3]: https://youtu.be/8SA2t75zgZs?t=2434 https://youtu.be/8SA2t75zgZs?t=2434
- vkoskiv 5y ago
  Huh, I had no idea that image was controversial. I think it's an easy mistake to make. Didn't know it was from a nude magazine originally, I just thought it was a traditionally used test image, like the Utah teapot in 3D rendering. I wouldn't jump to the conclusion that the image was intentionally chosen to alienate women in tech, though. Thanks for the TIL!
  - 1_player 5y ago
    Nobody would know or ever care to know if these so called justice warrior weren't always mentioning it and linking the whole naked picture every time there is a chance to do so. "Look at it! How _disgustingly_ immoral!" It's a beautiful portrait, and a standard in image compression comparison. Deal with it. I strongly dislike that prudish and puritan zealots now exploit the ideals of feminism and social justice to push forward the idea that we should be afraid of sex and our bodies. They're not "doing it for the women in tech", but because of their own issues with sexuality.

335 points by trashburger 5y ago

deleted 5y ago

[deleted]

Hyrum's Law strikes again: With a sufficient number of users of an API, it does not matter what you promise in the contract: all observable behaviors of your system will be depended on by somebody. https://www.hyrumslaw.com/ https://www.hyrumslaw.com/

qayxc 5y ago
Mark my words: Hyrum's Law will strike in full force and introduce a whole new world of pain once more and more software development will be done (or helped-) by machine learning. What happened here is a perfect example of what an optimiser might come up with and resulting systems will be so brittle and delicate that a whole new form of cargo cult might develop around them :D
- coliveira 5y ago
  Future systems will be like human genome: a small letter change will lead to the system self destroying after 20 days of flawless operation.
  - deleted 5y ago
    [deleted]
  - tryauuum 5y ago
    I wonder if there actually is a possibility of something like that in human genome. Are there any known bugs that can be introduced to human genome and instantly kill a human after, e.g. 18 years of normal operation?
    - a_t48 5y ago
      Aneurysms.
    - NavinF 5y ago
      Do genes associated with cancer count? I can't think of anything that kicks in instantly, but there are plenty of probabilistic bugs
    - masklinn 5y ago
      “Known” probably not because nobody cares but if you can edit the generic code of all cells (not just one) you just need to do a function-affecting substitution of a protein-coding segment for a vital protein. Doesn’t matter which one as long as it’s not solely developmental. It would not quite be instant though, the body would first have to run out of the existing supply then break down as operations stop. If you pick the right protein (e.g. something affecting the muscles or brain) I’d think the timescale would be minutes if not seconds. If you can only edit one cell or a small number if them then probably not, you can definitely cause long-term issues (e.g. cancers) but I would not think instant death an option. I think the GP was talking more about existing genetic defects leading to sudden issues down the line though.
  - masklinn 5y ago
    Surely they’d already the case? There’s tons of latent bugs which are only revealed because the conditions to trigger them have not been encountered yet. Every 4 years code breaks all over in leap days. A program crashing after not crashing is essentially “the system self destroying”.
Zababa 5y ago
It's intersting to see that some people add randomness to fight this, for example with maps in Go. It seems like it's the right choice.
- MaulingMonkey 5y ago
  Inserting randomness can help prevent denial of service attacks as well, by making it harder to manufacture pathological hash collisions (which can turn ~O(1) operations into O(N) operations).
- ncmncm 5y ago
  Right, like every release of any component should vary some detail that the spec doesn't guarantee. Especially, all hash functions should change on every release -- at least when building in debug mode.
  - vlovich123 5y ago
    Hash functions should use a random seed on every new container instance (or at least once per launch). Those hash tables that need specific properties of the hash should inject it in that way (cryptographic, deterministic, DOS-resistant, etc).
- jeffbee 5y ago
  Another place to insert randomness that could have uncovered this would be in the allocator size classes. In non-optimized builds, if your allocator has size classes, just pick them randomly. In my experience this uncovered a lot of bugs in programs linked against tcmalloc.
- yxhuvud 5y ago
  Other people fight it by adding a defined iteration order. That works just as well and don't introduce randomness.
  - wizzwizz4 5y ago
    But prevents optimisation, if that optimisation would lose the iteration order. If you need defined ordering in your type, use it. Otherwise, don't specify it.
tialaramex 5y ago
There's even a CPPCon talk about Google's "Swiss" tables with interruptions by Hyrum each time the new code's observable behaviour changes because, at Google, they internally have enough users for Hyrum's law to kick in all the time: https://www.youtube.com/watch?v=JZE3_0qvrMg https://www.youtube.com/watch?v=JZE3_0qvrMg The talk was presumably better live because Hyrum doesn't have a microphone, so his interjections are hard to follow, but it's a good way to illustrate. Some of the examples are much like this story, you design this sophisticated, heavily optimised unordered container for millions of items, and then your users put three items into it, and they depend on the order of those items and you "broke" their code by not having this behaviour you never promised and it made no sense to depend on. And the defence mentioned in this thread (randomise things which aren't guaranteed to have stability) is introduced because these are Google employees, they know about Hyrum, it just isn't enough. Sure the code failed when I tried to store 40 items due to your randomisation, but I found it worked OK with ten items as then the randomisation was defeated, so now I store ten items, and then your latest change broke that... The pathological use of data structure is why stuff like making the constructor for empty strings very cheap has a big effect on some codebases. Rust const-ified String::new() because an empty string doesn't need any heap store. So this means code which loops over a large array setting all the members to the empty string is only about as expensive as looping over an integer array setting all the integers to zero, it doesn't incur a heap allocation, or a function call. Of course modifying these strings now takes on the expense of allocating, but guess how often people who do stuff like this never actually touch the string...
- rasz 5y ago
  >they depend on the order of those items and you "broke" their code by not having this behaviour you never promised and it made no sense to depend on reminds me of a time my extension started glitching because localStorage stopped returning results in same order they were put in :o) Now that I think about it it happened somewhere around 2017-2018, did google drop it into Chrome at this point?

dvt 5y ago

Great read, and fantastic debugging! Correct me if I'm wrong, but I think this bug would have been caught if a CMYK JPEG would've been tested, assuming that an extra component would break the accidental well-orderedness of the stream.

trashburger 5y ago
I'm pretty sure Serenity does not support CMYK colors right now, if I understand this snippet correctly :^) if (context.component_count != 1 && context.component_count != 3) { dbgln_if(JPG_DEBUG, "{}: Unsupported number of components in SOF: {}!", stream.offset(), context.component_count); return false; }
- Flex247A 5y ago
  :^)

sunyc 5y ago

TLDR: Logically Wrong program was working under an specific condition that no longer exists, thus broken.

jeffbee 5y ago

Ignoring the tasteless act of trying to use the slack at the end of an allocation for your side projects, the bug really highlights the dangers of illiterate interfaces, to wit Color::Color(u8 r, u8 g, u8 b) from Serenity LibGfx. Calling this incorrectly is incredibly easy to do and invisible to the reader at the call site. Authors need to work with the type system to avoid these bugs, in this case having distinct types for red, green, and blue so the compiler will stop you from assigning red to blue without an explicit conversion. "Simple confusion of RGB vs. BGR" is not something that should seem natural to programmers. It's an error caused by underuse of the type system, just treating everything as a bag of numbers.

dvt 5y ago
> "Simple confusion of RGB vs. BGR" is not something that should seem natural to programmers. These kinds of errors are extremely common in much more mature libraries, including OpenCV, as well as HLSL or GLSL. No disrespect, but it sounds like you've never really touched graphics programming before. Color spaces are literally just a bag of numbers. A good analogy is coordinate systems. There's no type difference between an x-coordinate or a y-coordinate; they're just numbers and are defined by their ordinal position in an (x, y) tuple.
- owl57 5y ago
  Also, even if we model the color space in some overly clever way, we are talking about a JPEG loader here. Its input is inevitably a bag of numbers, and a horribly underspecified one.
  - owl57 5y ago
    I felt like I forgot to add a link. Why don't we see images in wrong color space nearly as often as text with wrong character encoding, remains a mystery to me since the moment I was writing a toy JPEG decoder and found this article: https://entropymine.wordpress.com/2018/10/22/how-is-a-jpeg-images-color-type-determined/ https://entropymine.wordpress.com/2018/10/22/how-is-a-jpeg-i...

thangalin 5y ago

"If a professor makes a sexist joke, a female student might well find it so disturbing that she is unable to listen to the rest of the lecture. Suggestive pictures used in lectures on image processing are similarly distracting to the women listeners and convey the message that the lecturer caters to the males only. For example, it is amazing that the Lena pin-up image is still used as an example in courses and published as a test image in journals today." ~D. P. O'Leary, 1999 http://www.cs.umd.edu/users/oleary/faculty/node8.html http://www.cs.umd.edu/users/oleary/faculty/node8.html Alternatives: http://sipi.usc.edu/database/database.php?volume=misc http://sipi.usc.edu/database/database.php?volume=misc

1970-01-01 5y ago
The sources for D.P. O'Leary's references are all dead.
- re 5y ago
  The links are dead, but the citations are valid. Here are working links: J. Gutbezahl, How Negative Expectancies and Attitudes Undermine Females' Math Confidence and Performance: A Review of the Literature. https://eric.ed.gov/?id=ED380279 https://eric.ed.gov/?id=ED380279 E. Spertus, Why are There so Few Female Computer Scientists? https://hdl.handle.net/1721.1/7040 https://hdl.handle.net/1721.1/7040
  - 1970-01-01 5y ago
    So I looked into these links. On [3] there is no data that backs this quote of hers: "Suggestive pictures used in lectures on image processing are similarly distracting to the women listeners and convey the message that the lecturer caters to the males only." The 30 (!) year old Spertus paper even states that most of the data collected was anecdotal.
young_unixer 5y ago
How is Lenna's picture disturbing or suggestive?

evmar 5y ago

To prevent these kinds of bugs, the iteration order in a Go map is randomized across each execution.

iab 5y ago
Does that prevent, or more expose?
- klodolph 5y ago
  I think the general idea is "shift left" which you can say exposes bugs earlier, or prevents bugs from reaching production, which is kind of a "six dozen of one, half dozen of the other". Bugs which are exposed early enough do not get committed. "Shift left" just means that you shift the feedback to the developer farther left in the build process, closer (in time and space) to when the mistake was made.
- EE84M3i 5y ago
  I don't know about go specifically, but many languages randomize their hash tables to avoid Hash Collision DoS attacks. This is a problem for any piece of software putting attacker-controlled data into a hash-table that does not randomize the hashing and where they assume that it will be amortized constant time.
  - masklinn 5y ago
    Go does have that, but it also specifically and explicitly randomises iteration order.
    - EE84M3i 5y ago
      Is that a separate implementation?
      - masklinn 5y ago
        No, it’s the builtin hashmap. It had a random seed for the hash to avoid collision predictability but it also, separately has a shuffled iteration order for maps.

userbinator 5y ago

I think the most important lesson of this article is in this sentence: Why this code was written this way instead of just checking against the ID by linearly iterating over the Components, I have no idea. There's another comment here that shows their JPEG decoder only supports 1 or 3 components. Using a hash table for at most 3 entries is astronomical overkill! The field for the number of components in a JPEG file is only a byte - so even if you were to support more than 3 components, it would be 255 at most, and sane JPEG files are unlikely to have more than 4 in practice. So fixed-size arrays are the perfect solution. I have a very good idea why it was written like that, however: the mere availability and ease of use of abstract data structures naturally leads to their overuse by what seems to be an overwhelming majority of developers, and the eagerness to "futureproof" and add unnecessary complexity is also very common. Overcomplexity creates bugs, and (leaky) abstractions hide them. Even if the complexity (and bug) isn't visible in your code, it's still there. If the initial code had been reviewed by me, it most certainly would not pass. I am saying this as someone who has actually written a JPEG decoder --- it is not as difficult as it may sound, and I highly recommend giving it a try --- and also witnessed (and fixed) the messes that people get in with overcomplicating things. Perhaps that slight "architecture astronaut" mentality comes from starting with a higher-level language; I started with Asm and my preferred language is usually C, and I haven't seen the tendency to overcomplicate much in others who did the same. The reason the Components were in a hash table was that they would then be checked against the component ordering in a “Start of Scan” section to make sure all the components in the SOS section are in the expected order. For comparison, this is the corresponding code in my JPEG decoder. I didn't even bother using a loop: if(read_byte()!= cids[0]) data_error("SOS scan first component must match"); hts[0] = read_byte(); /* high nybble: DC table index; low nybble: AC table index */ if(read_byte() != cids[1]) data_error("SOS scan second component must match"); hts[1] = read_byte(); if(read_byte() != cids[2]) data_error("SOS scan third component must match"); hts[2] = read_byte();

deleted 5y ago
[deleted]
logicchains 5y ago
>I have a very good idea why it was written like that, however: the mere availability and ease of use of abstract data structures naturally leads to their overuse by what seems to be an overwhelming majority of developers, and the eagerness to "futureproof" and add unnecessary complexity is also very common. To give some context, iterating over an array of three small items takes worst case roughly 100ns(cache miss), best case 1ns(l1 cache hit). Most common hashmap implementations (like std::unordered_map) dynamically allocate items so they're stored randomly in memory, giving roughly 300ns worst case(3 cache misses), 3ns best case(3 l1 cache hits) for iterating over them. So using a hash map is going to be 3x slower without even accounting for the time spent hashing, and 3x more likely to hit the worse case due to requiring three cachelines still in the l1 cache for best performance as opposed to just one. If regularly adding/deleting items, using a std::unordered_map would literally be orders of magnitude slower due to using malloc/free for each item added/removed.

raggi 5y ago

I can absolutely confirm that this is what it's like to diagnose weird bugs on nascent operating systems, particularly on or nearby "portability boundaries", which are not always what you think they are. Pull that thread, but be sure you're ready for jenga.

asdfasgasdgasdg 5y ago

This bug is an example of why the absl swiss tables have nondeterministic iteration order. Found so many bugs in the codebase when this got turned on. https://abseil.io/docs/cpp/guides/container#iteration-order-instability https://abseil.io/docs/cpp/guides/container#iteration-order-...

yxhuvud 5y ago
Yes, hash tables need to iterate in either a guaranteed order (usually insertion order) or a guaranteed to be random order. Either choice make sense, but one of them needs to be picked or people will create bugs like this.
- masklinn 5y ago
  FWIW most modern hash tables are randomised on a per-run basis as side-effect if the hash being seeded with a random value for attacker-controlled collision resistance.
  - mikemike 5y ago
    One year ago I hardened LuaJIT's VM against these kind of attacks. Since then, there has been a constant influx of complaints and issues filed. All bitterly complaining their code, which mistakenly assumed a fixed hash table iteration order, is now broken. Even when told that the Lua manual clearly states the undefined order since 20 years, they do not cease to complain. They do not realize this change helped them to discover a serious bug in their code (the order could differ even before that change). Sigh. You can now have a guess, what one of the lesser enlightened forks of LuaJIT did ...
    - masklinn 5y ago
      I’m not surprised. The same issue occurred in python. And to be fair it’s a pain in the ass to debug and find out why something happens to implicitly depend on iteration order (float stability is common but not alone). And their code did work beforehand, for most values of work. The biggest pain in the ass is that — at least in python - while you can set the hash seed explicitely if you don’t the langage doesn’t tell you. This makes reproducing the issue very annoying when only some seeds trigger it. > the order could differ even before that change While the order could differ I assume it was deterministic and nothing influencing those bits had changed in a while.

cratermoon 5y ago

malloc didn't break JPGLoader. The code was already broken, malloc just exposed the bug

rocqua 5y ago
The code was wrong, but the produced binaries were not. From the user perspective, a change to malloc really did break JPGLoader. That it broke this by revealing a pre-existing fault in the code is interesting to note. Especially for the developers. But it does not change the user experience.

happyweasel 5y ago

Come on, just use a Map/Dictionary structure where ordered key iteration is possible..

deleted 5y ago

[deleted]

indolering 5y ago

Fuck, Lenna [1]? Could we stop alienating women in tech [2]? Don't take my word for it, the AV1 folks are pleading with the field to stop using Lenna too [3]. [1]: https://en.wikipedia.org/wiki/Lenna#Criticism https://en.wikipedia.org/wiki/Lenna#Criticism [2]: https://xkcd.com/322/ https://xkcd.com/322/ [3]: https://youtu.be/8SA2t75zgZs?t=2434 https://youtu.be/8SA2t75zgZs?t=2434

vkoskiv 5y ago
Huh, I had no idea that image was controversial. I think it's an easy mistake to make. Didn't know it was from a nude magazine originally, I just thought it was a traditionally used test image, like the Utah teapot in 3D rendering. I wouldn't jump to the conclusion that the image was intentionally chosen to alienate women in tech, though. Thanks for the TIL!
- 1_player 5y ago
  Nobody would know or ever care to know if these so called justice warrior weren't always mentioning it and linking the whole naked picture every time there is a chance to do so. "Look at it! How _disgustingly_ immoral!" It's a beautiful portrait, and a standard in image compression comparison. Deal with it. I strongly dislike that prudish and puritan zealots now exploit the ideals of feminism and social justice to push forward the idea that we should be afraid of sex and our bodies. They're not "doing it for the women in tech", but because of their own issues with sexuality.