15 ms·

Breaking java.lang.String

220 points by coekie 3y ago

cogman10 3y ago
This is exactly why java needs frozen arrays [1]. The safe thing to do is freeze the array before doing anything with it. Then, you can rely on COW to copy to the array if someone is modifying it concurrently with you reading it. In the general case, you'd have fast string creation and in the tricky case you simply pay the clone cost as a penalty for being dumb. [1] https://openjdk.org/jeps/8261007#:~:text=How%20do%20I%20use%20a%20frozen%20array%3F%201,an%20array%20is%20frozen%20or%20modifiable.%20More%20items https://openjdk.org/jeps/8261007#:~:text=How%20do%20I%20use%...
- malfist 3y ago
  Java does have immutable collections. It's just not an explicit type. Lots of common ways to instantiate arrays (i.e. Arrays.asList) generate immutable lists
  - thfuran 3y ago
    That's instantiating a List, not an array.
    - tialaramex 3y ago
      As you would expect in a vaguely modern language, Java's "List" interface is typically backed by a growable array as the type ArrayList. Only people who have no idea about caches would think List should necessarily be some sort of Linked List type. You would use Collections.unmodifiableList to make it unmodifiable.
      - cowsandmilk 3y ago
        Collections.unmodifiableList doesn’t prevent anyone who has a reference to the original List (or the array behind it) from modifying the List. Calling that in the constructor would not help.
      - thfuran 3y ago
        Yes, ArrayLists are array-backed, but Arrays.asList instantiates a List and does not instantiate an array.
        tialaramex 3y ago
        As I explained, List is an interface. You can't instantiate it, values are instances of types not interfaces. All that return type is telling you is, surprise, asList promises what you're getting implements the List interface. See if you can guess how you can implement the List interface using an Array. Still struggling, here's the one line of a typical implementation: return new Arrays.ArrayList(a);
        thfuran 3y ago
        You should at least try to be correct if you're going to be so insufferable about it.
  - cowsandmilk 3y ago
    Arrays.asList doesn’t generate an immutable list, prevent writes to the array, or prevent modifying the array via the List interface. https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Arrays.html#asList(T https://docs.oracle.com/en/java/javase/17/docs/api/java.base......)
- layer8 3y ago
  This doesn’t help when the parameter is one of the collection interfaces, or CharSequence, or the like. You always need to defensively copy their contents first to “freeze“ their values.
- wjholden 3y ago
  I would love to have this in Java, hopefully this JEP makes it!
  - cogman10 3y ago
    As would I. There are a ton of places where the JVM is defensively copying arrays. It often comes up (for me in my work) as a performance problem. A real common example of this is `Enum#values`. Ideally (IMO) this applies some aggressive COW operations. So perhaps internal to the enum you have a frozen array of the values and for "values()" you return something like `VALUES.unfreeze()` which points to a transparent unfrozen array. On a write action, you'd copy the array but in the general case you'd simply read from the frozen array until someone does something dumb. You could take it a step further and simply expose the `values` field or add a new "frozenValues" method to not break existing code. In either case, you'd end up with faster performance because the JVM isn't copying the internal array needlessly.
josephcsible 3y ago
This is the exact kind of bug that Rust solves with its borrowing system. The problem is that Java has no way to express the concept of "something that nothing else can modify while I'm looking at it".
- Thaxll 3y ago
  Mutexes etc ... exist in Java.
  - jjnoakes 3y ago
    Right, but in rust, not using one is a compile time error. In Java (as you can see by the article), not using one is a silent bug at runtime.
    - kaba0 3y ago
      This is a heavily optimized system library - you don’t use mutexes here. Rust wouldn’t help here, if mutexes would be fine, they would have been used. Especially that this is the result of C++ and Java code simultaneously. Hell, it’s probably one area where rust’s benefits are a “hard sell” — you would have to constantly be in unsafe rust manipulating pointers manually as the compiler can’t reason statically about what a layer built on top does without a huge runtime cost (huge, as in you really don’t want to lock/unlock, or even refcount in these hot paths).
      - lostmsu 3y ago
        Huh? This is exactly where Rust would help. In Rust the caller of the constructor would either have to add mutex if they needed concurrency, or just use the constructor without mutex overhead if they did not.
      - ironmagma 3y ago
        It's a compile-time cost instead of a runtime cost.
      - 3y ago
m_0x 3y ago
Every time, without fail, somebody shows a bug about a piece of code that we take for granted (In this case, the String class) the bug is related to concurrent modifications. Concurrency is so hard that even OpenJDK developers can't prevent these kind of bugs
- singron 3y ago
  Go has trouble with this too. You can cause undefined behavior with completely safe code by making concurrent modifications to a fat pointer. The writes won't be atomic, and the pointer can be interpreted as the wrong type. E.g. in this example, the B.foo method will be called with a C value as the receiver, which tricks it into accessing memory at 0x1000 and segfaulting, but you could also arbitrarily access any memory this way without using unsafe. https://go.dev/play/p/y4z_vs-I1jb https://go.dev/play/p/y4z_vs-I1jb
- bill3478 3y ago
  Is not that OpenJDK developers can't prevent these, but there's a forbidding cost for doing so. The simplest "safe" way of doing this involves defensively copying the input argument. However, the `compress` function will likely make yet another smaller copy, making the constructor very allocation and CPU intensive. In fact, due to the fixed array size in Java, all thread-safe implementations must either allocate two arrays to hold the two possible encodings, which guarantees one piece of garbage, or iterating the input array twice. For such a core class like String, this is probably unacceptable cost. And the constructor is not documented to be thread-safe, so no one should expect it to. In reality, there are much more impactful data structures to abuse in Java.
CJefferson 3y ago
Out of interest, how should this be handled? Is this a bug in Java which should be fixed (looks like that to me)? My understanding was Java generally doesn't do "you did an undefined behaviour, so it's your fault", except for specifically marked very low-level interfaces.
- thfuran 3y ago
  Java definitely does "you wrote thread dangerous code, so it's your fault" for APIs not marked as being thread safe.
  - ccooffee 3y ago
    This is yet another way that running untrusted code inside the same JVM is a terrible mess. There's a lot of JVM state that gets "locked in" on first use (e.g. <clinit>) and a malicious bit of code could corrupt a LOT of shared data (like the post's mentioned string internment zone) even if you sanitize all of your inputs and outputs. I wonder if you could do something nasty with this bug from inside an IntelliJ plugin...
  - kaba0 3y ago
    For what it's worth, Java does at least give some guarantees in case of data races -- the observed value will always be one that was explicitly set by one thread. This is different from most other languages, e.g. in C,C++, unsafe Rust it is UB. Of course it can and still will result in invalid states.
    - tialaramex 3y ago
      > Of course it can and still will result in invalid states. While of course they can't stop you from creating "invalid" states of your own types, whether through a data race or just bad coding - Java's own types should not have invalid states which can come into existence this way. For example, suppose we've got a Goose type, and it can be Happy or Sad, and when it's Sad it has a Reason, when it is Happy there's no Reason. We, as Java, should not design this type so that it's possible for it to get flipped from Happy to Sad without choosing a Reason. As a result, after a race the Goose might be Happy when you expected Sad, or vice versa, but it can't enter the invalid state where it's Sad but for no Reason.
gizmo686 3y ago
Is this actually a bug? The default assumption in Java is that types are not thread-safe unless otherwise specified. Attempting to use types in a way that exceeds their documented thread safety has always been allowed to leave your program in an inconsistent state.
- neandrake 3y ago
  My thinking is the same. I doubt this is an oversight. Making the String constructor thread-safe would likely slow things significantly. Great point about things being assumed not thread-safe. The JDK is pretty thorough with documenting thread-safety.
  - neandrake 3y ago
    Coming back to this the answer is probably not strictly about concurrency and so there is a possibility something would need addressed about this.
  - masklinn 3y ago
    > Making the String constructor thread-safe would likely slow things significantly. By my reckoning it would speed things up, at least going by the Java code.
    - neandrake 3y ago
      By what means? The only ways I would expect are either unconditionally duplicating the array or mutex, and I don’t think the mutex wouldn’t be simple. Adding a sync block on the input could be done but that’s assuming nothing else is locked on it (but probably points to there being a race condition elsewhere if there is..). Unconditionally duplicating the array would use more memory and wouldn’t be faster.
      - masklinn 3y ago
        Inlining `StringUTF16.compress` and `StringUTF16.bytes what the code currently does is essentially this (using python as pseudocode): latin1 = bytearray(len(input)) for i in range(len(input)): c = input[i] if c > 255: latin1 = None break latin1[i] = c if latin1 is not None: return LATIN1, latin1 utf16 = bytearray(len(input)*2) for i in range(0, len(input)): c = input[i] utf16[2*i] = c >> HI_BYTE_SHIFT utf16[2*i+1] = c >> LO_BYTE_SHIFT return UTF16, utf16 The issue occurs because `input` can be mutated between the moment it finds a char that's above 255 in the first loop and the moment it visits that same char in the second loop. The solution is to not do that, but instead something like: latin1 = bytearray(len(input)) for i in range(len(input)): c = input[i] if c <= 255: latin1[i] = c continue utf16 = bytearray(len(input)*2) for j in range(i): utf16[2*j] = latin1[j] latin1 = None utf16[2*i] = c utf16[2*i+1] = c >> 8 for j in range(i+1, len(input)): c = input[j] utf16[2*i] = c utf16[2*i+1] = c >> 8 return UTF16, utf16 return LATIN1, latin1 This means if you find a char that's above 255 you will always append that char to the UTF16 array, there's no possibility that someone will change it under you because you append the exact same char you tested. So you can not get into the situation the essay describes, a utf16 string will always contain at least one non-latin1-code unit. Non-vectorised performances should an improvement as latin1 to utf16 is a trivial operation (just copy every byte of the input to every other byte of the output) Though if you vectorised the char to utf16 conversion you now vectorise two loops on bailout (latin1 -> utf16 up to i, then char -> utf16) which is probably less efficient. I don't know if the JDK has vectorised optimisations, the source has "HotSpotIntrinsicCandidate" annotations but I don't know to what extent the intrinsics go.
deleted 3y ago
[deleted]
dundarious 3y ago
Calling this a "bug in java.lang.String" is silly. The same "bug" exists for all functions that take mutable objects. If you take a map and lookup two different keys, yep, that's a "bug". The bug is the other piece of code that introduces the data race in the first place. You can argue the case for languages like Rust with it's borrow system, or others that use linear types or something along those lines, to eliminate the possibility of this happening, but it's quite misleading to say that the innocent user of a mutable object is the source of a bug. You may as well say there's a bug in `printf("Hello, World!\n");` in C because you could have another thread writing random values to random memory, running `while(1) { *((unsigned char*)(void*)rand()) = rand(); }`
- quickthrower2 3y ago
  It is probably a gotcha. But yeah if you hit this problem you have bigger worries, the code immediately before the constructor is not thread safe.
- layer8 3y ago
  It’s a bug for constructor functions, in my book. I certainly always code defensively to prevent such misbehavior. A successfully constructed object should obey its documented interface contract, period.
  - ris58h 3y ago
    > A successfully constructed object should obey its documented interface contract, period. Could you provide the contract you are talking about?
    - layer8 3y ago
      Yes, the contract of String::equals: The result is true if and only if the argument is not null and is a String object that represents the same sequence of characters as this object. The article constructs two String objects representing the same character sequence, for which however equals() returns false, in violation of the above-quoted contract.
vbezhenar 3y ago
That's a very interesting finding. Nowadays Java security is a joke, but back in the day, Java security was a serious topic. Users were able to run downloaded applets in their browser, so protecting the sandbox was important. It's very likely that using those kinds of "corrupted" strings would allow to break out of this sandbox, because that protection code definitely relied on strings being sane and correct. I can't imagine this behaviour to cause much problem with modern Java, nobody runs untrusted code anyway. But good to know.
robertlagrant 3y ago
> Why is "foo!".equals("foo⁉") false? I don't really understand this question. They...look different? One is an exclamation mark, and the other is an exclamation mark/question mark combo?
- j16sdiz 3y ago
  This is not a question. The paragraph after that get into the implementation details on how have know they are different without comparing the bytes.
JediPig 3y ago
in the words of linus, java is a horrible language.
coekie 3y ago
I just added solutions to the empty String challenge in the blog post. This includes a very interesting find from Xavier Cooney, that causes the same problem without involving any concurrency. It instead makes StringBuilder misbehave by throwing an exception at an unexpected place: https://gist.github.com/XavierCooney/e9f6235f05479ac6bf962ca25e31d8d0 https://gist.github.com/XavierCooney/e9f6235f05479ac6bf962ca...
doodpants 3y ago
I enjoyed the article, but if I may express a peeve of mine... In the code listings, can we please not use a syntax coloring scheme that makes the comments nearly unreadable? Especially in blog posts like this, where the code deliberately contains numerous explanatory comments. Such low-contrast text slows down my tired old eyes.
nayuki 3y ago
It is possible to fix this String constructor implementation without creating a defensive copy of the input array or having a TOCTOU vulnerability. // Change this implementation to a loop. public String(char[] value) { while (true) { byte[] temp = StringUTF16.compress(value); if (temp != null) { this.value = temp; this.coder = LATIN1; break; } temp = StringUTF16.toBytes(value); if (temp != null) { this.value = temp; this.coder = UTF16; break; } } } // This implementation stays the same. static byte[] StringUTF16.compress(char[] value) { ... } // Change this contract and implementation so that it returns null // if all characters are below 256, otherwise it returns byte[]. // The difference is that previously, this function would never return null. // Now, we make sure that the function succeeds if and only if the // char array *requires* UTF-16 as opposed to Latin-1. static byte[] StringUTF16.compress(char[] value) { ... }
- dundarious 3y ago
  An unconditional loop with no guarantee of forward progress may loop indefinitely, and hence, is not a sensible solution to the problem.
  - Dylan16807 3y ago
    It only loops if you modify the string in certain ways partway through the loop. Is that a significant problem? As soon as you stop your indefinite loop of race-condition writes, this loop is guaranteed to finish.
    - dundarious 3y ago
      Well it's trading "bad code can populate the program's string intern table with invalid string objects" for "bad code can instantly deadlock the program", which is not much of an upgrade. And wouldn't you need to do this in every function that uses more than 2 or more related mutable objects 1 time each, or uses 1 mutable object more than 1 time? Do you know of any systems that work like this? This is basically a very poor man's version of software transactional memory. Noticing this is one step on the road to realizing that shared memory concurrency needs cooperative synchronization (and locks are just one way to achieve that), and most important of all, you should strictly limit the number of functions that need to synchronize at all, by strictly limiting the number of shared data objects. I think the article OP and many in the comments here have taken the wrong lessons from this. I think the real lessons are: 1. In a program containing data races, one cannot assume objects obey their stated invariants. 2. Therefore, security/correctness in a shared memory concurrent system cannot be achieved if there is untrusted/unverified code (i.e., code that may introduce data races). 3. Regardless, it may pay dividends to try harder to learn from 1 and do better at validating input, especially in silently pervasively used shared state (e.g., the string intern table). Unfortunately, I think this will always be best effort.

220 points by coekie 3y ago

This is exactly why java needs frozen arrays [1]. The safe thing to do is freeze the array before doing anything with it. Then, you can rely on COW to copy to the array if someone is modifying it concurrently with you reading it. In the general case, you'd have fast string creation and in the tricky case you simply pay the clone cost as a penalty for being dumb. [1] https://openjdk.org/jeps/8261007#:~:text=How%20do%20I%20use%20a%20frozen%20array%3F%201,an%20array%20is%20frozen%20or%20modifiable.%20More%20items https://openjdk.org/jeps/8261007#:~:text=How%20do%20I%20use%...

malfist 3y ago
Java does have immutable collections. It's just not an explicit type. Lots of common ways to instantiate arrays (i.e. Arrays.asList) generate immutable lists
- thfuran 3y ago
  That's instantiating a List, not an array.
  - tialaramex 3y ago
    As you would expect in a vaguely modern language, Java's "List" interface is typically backed by a growable array as the type ArrayList. Only people who have no idea about caches would think List should necessarily be some sort of Linked List type. You would use Collections.unmodifiableList to make it unmodifiable.
    - cowsandmilk 3y ago
      Collections.unmodifiableList doesn’t prevent anyone who has a reference to the original List (or the array behind it) from modifying the List. Calling that in the constructor would not help.
    - thfuran 3y ago
      Yes, ArrayLists are array-backed, but Arrays.asList instantiates a List and does not instantiate an array.
      - tialaramex 3y ago
        As I explained, List is an interface. You can't instantiate it, values are instances of types not interfaces. All that return type is telling you is, surprise, asList promises what you're getting implements the List interface. See if you can guess how you can implement the List interface using an Array. Still struggling, here's the one line of a typical implementation: return new Arrays.ArrayList(a);
        thfuran 3y ago
        You should at least try to be correct if you're going to be so insufferable about it.
- cowsandmilk 3y ago
  Arrays.asList doesn’t generate an immutable list, prevent writes to the array, or prevent modifying the array via the List interface. https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Arrays.html#asList(T https://docs.oracle.com/en/java/javase/17/docs/api/java.base......)
layer8 3y ago
This doesn’t help when the parameter is one of the collection interfaces, or CharSequence, or the like. You always need to defensively copy their contents first to “freeze“ their values.
wjholden 3y ago
I would love to have this in Java, hopefully this JEP makes it!
- cogman10 3y ago
  As would I. There are a ton of places where the JVM is defensively copying arrays. It often comes up (for me in my work) as a performance problem. A real common example of this is `Enum#values`. Ideally (IMO) this applies some aggressive COW operations. So perhaps internal to the enum you have a frozen array of the values and for "values()" you return something like `VALUES.unfreeze()` which points to a transparent unfrozen array. On a write action, you'd copy the array but in the general case you'd simply read from the frozen array until someone does something dumb. You could take it a step further and simply expose the `values` field or add a new "frozenValues" method to not break existing code. In either case, you'd end up with faster performance because the JVM isn't copying the internal array needlessly.

josephcsible 3y ago

This is the exact kind of bug that Rust solves with its borrowing system. The problem is that Java has no way to express the concept of "something that nothing else can modify while I'm looking at it".

Thaxll 3y ago
Mutexes etc ... exist in Java.
- jjnoakes 3y ago
  Right, but in rust, not using one is a compile time error. In Java (as you can see by the article), not using one is a silent bug at runtime.
  - kaba0 3y ago
    This is a heavily optimized system library - you don’t use mutexes here. Rust wouldn’t help here, if mutexes would be fine, they would have been used. Especially that this is the result of C++ and Java code simultaneously. Hell, it’s probably one area where rust’s benefits are a “hard sell” — you would have to constantly be in unsafe rust manipulating pointers manually as the compiler can’t reason statically about what a layer built on top does without a huge runtime cost (huge, as in you really don’t want to lock/unlock, or even refcount in these hot paths).
    - lostmsu 3y ago
      Huh? This is exactly where Rust would help. In Rust the caller of the constructor would either have to add mutex if they needed concurrency, or just use the constructor without mutex overhead if they did not.
    - ironmagma 3y ago
      It's a compile-time cost instead of a runtime cost.
    - 3y ago

m_0x 3y ago

Every time, without fail, somebody shows a bug about a piece of code that we take for granted (In this case, the String class) the bug is related to concurrent modifications. Concurrency is so hard that even OpenJDK developers can't prevent these kind of bugs

singron 3y ago
Go has trouble with this too. You can cause undefined behavior with completely safe code by making concurrent modifications to a fat pointer. The writes won't be atomic, and the pointer can be interpreted as the wrong type. E.g. in this example, the B.foo method will be called with a C value as the receiver, which tricks it into accessing memory at 0x1000 and segfaulting, but you could also arbitrarily access any memory this way without using unsafe. https://go.dev/play/p/y4z_vs-I1jb https://go.dev/play/p/y4z_vs-I1jb
bill3478 3y ago
Is not that OpenJDK developers can't prevent these, but there's a forbidding cost for doing so. The simplest "safe" way of doing this involves defensively copying the input argument. However, the `compress` function will likely make yet another smaller copy, making the constructor very allocation and CPU intensive. In fact, due to the fixed array size in Java, all thread-safe implementations must either allocate two arrays to hold the two possible encodings, which guarantees one piece of garbage, or iterating the input array twice. For such a core class like String, this is probably unacceptable cost. And the constructor is not documented to be thread-safe, so no one should expect it to. In reality, there are much more impactful data structures to abuse in Java.

CJefferson 3y ago

Out of interest, how should this be handled? Is this a bug in Java which should be fixed (looks like that to me)? My understanding was Java generally doesn't do "you did an undefined behaviour, so it's your fault", except for specifically marked very low-level interfaces.

thfuran 3y ago
Java definitely does "you wrote thread dangerous code, so it's your fault" for APIs not marked as being thread safe.
- ccooffee 3y ago
  This is yet another way that running untrusted code inside the same JVM is a terrible mess. There's a lot of JVM state that gets "locked in" on first use (e.g. <clinit>) and a malicious bit of code could corrupt a LOT of shared data (like the post's mentioned string internment zone) even if you sanitize all of your inputs and outputs. I wonder if you could do something nasty with this bug from inside an IntelliJ plugin...
- kaba0 3y ago
  For what it's worth, Java does at least give some guarantees in case of data races -- the observed value will always be one that was explicitly set by one thread. This is different from most other languages, e.g. in C,C++, unsafe Rust it is UB. Of course it can and still will result in invalid states.
  - tialaramex 3y ago
    > Of course it can and still will result in invalid states. While of course they can't stop you from creating "invalid" states of your own types, whether through a data race or just bad coding - Java's own types should not have invalid states which can come into existence this way. For example, suppose we've got a Goose type, and it can be Happy or Sad, and when it's Sad it has a Reason, when it is Happy there's no Reason. We, as Java, should not design this type so that it's possible for it to get flipped from Happy to Sad without choosing a Reason. As a result, after a race the Goose might be Happy when you expected Sad, or vice versa, but it can't enter the invalid state where it's Sad but for no Reason.

gizmo686 3y ago

Is this actually a bug? The default assumption in Java is that types are not thread-safe unless otherwise specified. Attempting to use types in a way that exceeds their documented thread safety has always been allowed to leave your program in an inconsistent state.

neandrake 3y ago
My thinking is the same. I doubt this is an oversight. Making the String constructor thread-safe would likely slow things significantly. Great point about things being assumed not thread-safe. The JDK is pretty thorough with documenting thread-safety.
- neandrake 3y ago
  Coming back to this the answer is probably not strictly about concurrency and so there is a possibility something would need addressed about this.
- masklinn 3y ago
  > Making the String constructor thread-safe would likely slow things significantly. By my reckoning it would speed things up, at least going by the Java code.
  - neandrake 3y ago
    By what means? The only ways I would expect are either unconditionally duplicating the array or mutex, and I don’t think the mutex wouldn’t be simple. Adding a sync block on the input could be done but that’s assuming nothing else is locked on it (but probably points to there being a race condition elsewhere if there is..). Unconditionally duplicating the array would use more memory and wouldn’t be faster.
    - masklinn 3y ago
      Inlining `StringUTF16.compress` and `StringUTF16.bytes what the code currently does is essentially this (using python as pseudocode): latin1 = bytearray(len(input)) for i in range(len(input)): c = input[i] if c > 255: latin1 = None break latin1[i] = c if latin1 is not None: return LATIN1, latin1 utf16 = bytearray(len(input)*2) for i in range(0, len(input)): c = input[i] utf16[2*i] = c >> HI_BYTE_SHIFT utf16[2*i+1] = c >> LO_BYTE_SHIFT return UTF16, utf16 The issue occurs because `input` can be mutated between the moment it finds a char that's above 255 in the first loop and the moment it visits that same char in the second loop. The solution is to not do that, but instead something like: latin1 = bytearray(len(input)) for i in range(len(input)): c = input[i] if c <= 255: latin1[i] = c continue utf16 = bytearray(len(input)*2) for j in range(i): utf16[2*j] = latin1[j] latin1 = None utf16[2*i] = c utf16[2*i+1] = c >> 8 for j in range(i+1, len(input)): c = input[j] utf16[2*i] = c utf16[2*i+1] = c >> 8 return UTF16, utf16 return LATIN1, latin1 This means if you find a char that's above 255 you will always append that char to the UTF16 array, there's no possibility that someone will change it under you because you append the exact same char you tested. So you can not get into the situation the essay describes, a utf16 string will always contain at least one non-latin1-code unit. Non-vectorised performances should an improvement as latin1 to utf16 is a trivial operation (just copy every byte of the input to every other byte of the output) Though if you vectorised the char to utf16 conversion you now vectorise two loops on bailout (latin1 -> utf16 up to i, then char -> utf16) which is probably less efficient. I don't know if the JDK has vectorised optimisations, the source has "HotSpotIntrinsicCandidate" annotations but I don't know to what extent the intrinsics go.

deleted 3y ago

[deleted]

dundarious 3y ago

Calling this a "bug in java.lang.String" is silly. The same "bug" exists for all functions that take mutable objects. If you take a map and lookup two different keys, yep, that's a "bug". The bug is the other piece of code that introduces the data race in the first place. You can argue the case for languages like Rust with it's borrow system, or others that use linear types or something along those lines, to eliminate the possibility of this happening, but it's quite misleading to say that the innocent user of a mutable object is the source of a bug. You may as well say there's a bug in `printf("Hello, World!\n");` in C because you could have another thread writing random values to random memory, running `while(1) { *((unsigned char*)(void*)rand()) = rand(); }`

quickthrower2 3y ago
It is probably a gotcha. But yeah if you hit this problem you have bigger worries, the code immediately before the constructor is not thread safe.
layer8 3y ago
It’s a bug for constructor functions, in my book. I certainly always code defensively to prevent such misbehavior. A successfully constructed object should obey its documented interface contract, period.
- ris58h 3y ago
  > A successfully constructed object should obey its documented interface contract, period. Could you provide the contract you are talking about?
  - layer8 3y ago
    Yes, the contract of String::equals: The result is true if and only if the argument is not null and is a String object that represents the same sequence of characters as this object. The article constructs two String objects representing the same character sequence, for which however equals() returns false, in violation of the above-quoted contract.

vbezhenar 3y ago

That's a very interesting finding. Nowadays Java security is a joke, but back in the day, Java security was a serious topic. Users were able to run downloaded applets in their browser, so protecting the sandbox was important. It's very likely that using those kinds of "corrupted" strings would allow to break out of this sandbox, because that protection code definitely relied on strings being sane and correct. I can't imagine this behaviour to cause much problem with modern Java, nobody runs untrusted code anyway. But good to know.

robertlagrant 3y ago

> Why is "foo!".equals("foo⁉") false? I don't really understand this question. They...look different? One is an exclamation mark, and the other is an exclamation mark/question mark combo?

j16sdiz 3y ago
This is not a question. The paragraph after that get into the implementation details on how have know they are different without comparing the bytes.

JediPig 3y ago

in the words of linus, java is a horrible language.

coekie 3y ago

I just added solutions to the empty String challenge in the blog post. This includes a very interesting find from Xavier Cooney, that causes the same problem without involving any concurrency. It instead makes StringBuilder misbehave by throwing an exception at an unexpected place: https://gist.github.com/XavierCooney/e9f6235f05479ac6bf962ca25e31d8d0 https://gist.github.com/XavierCooney/e9f6235f05479ac6bf962ca...

doodpants 3y ago

I enjoyed the article, but if I may express a peeve of mine... In the code listings, can we please not use a syntax coloring scheme that makes the comments nearly unreadable? Especially in blog posts like this, where the code deliberately contains numerous explanatory comments. Such low-contrast text slows down my tired old eyes.

nayuki 3y ago

It is possible to fix this String constructor implementation without creating a defensive copy of the input array or having a TOCTOU vulnerability. // Change this implementation to a loop. public String(char[] value) { while (true) { byte[] temp = StringUTF16.compress(value); if (temp != null) { this.value = temp; this.coder = LATIN1; break; } temp = StringUTF16.toBytes(value); if (temp != null) { this.value = temp; this.coder = UTF16; break; } } } // This implementation stays the same. static byte[] StringUTF16.compress(char[] value) { ... } // Change this contract and implementation so that it returns null // if all characters are below 256, otherwise it returns byte[]. // The difference is that previously, this function would never return null. // Now, we make sure that the function succeeds if and only if the // char array *requires* UTF-16 as opposed to Latin-1. static byte[] StringUTF16.compress(char[] value) { ... }

dundarious 3y ago
An unconditional loop with no guarantee of forward progress may loop indefinitely, and hence, is not a sensible solution to the problem.
- Dylan16807 3y ago
  It only loops if you modify the string in certain ways partway through the loop. Is that a significant problem? As soon as you stop your indefinite loop of race-condition writes, this loop is guaranteed to finish.
  - dundarious 3y ago
    Well it's trading "bad code can populate the program's string intern table with invalid string objects" for "bad code can instantly deadlock the program", which is not much of an upgrade. And wouldn't you need to do this in every function that uses more than 2 or more related mutable objects 1 time each, or uses 1 mutable object more than 1 time? Do you know of any systems that work like this? This is basically a very poor man's version of software transactional memory. Noticing this is one step on the road to realizing that shared memory concurrency needs cooperative synchronization (and locks are just one way to achieve that), and most important of all, you should strictly limit the number of functions that need to synchronize at all, by strictly limiting the number of shared data objects. I think the article OP and many in the comments here have taken the wrong lessons from this. I think the real lessons are: 1. In a program containing data races, one cannot assume objects obey their stated invariants. 2. Therefore, security/correctness in a shared memory concurrent system cannot be achieved if there is untrusted/unverified code (i.e., code that may introduce data races). 3. Regardless, it may pay dividends to try harder to learn from 1 and do better at validating input, especially in silently pervasively used shared state (e.g., the string intern table). Unfortunately, I think this will always be best effort.