There are some other deliberate holes in that safety, such as using reflection to access private members, and instrumentation, where it is clear you are stepping outside the safety zone, but even that is getting locked down now with the "Integrity and Strong Encapsulation" effort https://openjdk.org/jeps/8305968 .
In general, most code we write would not (and should not) try to protect against such abuse, but classes in the core platform play by different rules.
Btw, this has been accepted into the bug database now: https://bugs.java.com/bugdatabase/view_bug?bug_id=JDK-831190... . I expect this to be fixed in a future release.
EDIT: another idea is to do a hash of the input array, and compare between start and end. But that also requires an O(n) walk through the input...
Compressing requires an O(n) walk through the input either way.
Upon encountering a non-Latin1 char, convert the existing latin1 array to an utf16 one, append the char (converted), then resume iteration in utf16 copy mode.
This way you know the char which made you bail out on Latin1 is part of the output.
> While the javadoc doesn't state it explicitly, immutable classes in the core library are expected to be thread safe.
If it's not documented it's just an assumption.
The author could call it 'probably bug' or 'misleading String constructor documentation' but instead they state it's a bug without any proofs.
It was accepted as a bug. I'm not saying I would condemn anyone to the death penalty based on that but being accepted as a bug there has to have a significant weight attached to it.
I know. It was in this thread above. So there is no link to the specification to proof that it's a bug.
The understanding 'It first tries to encode the characters as latin-1 using StringUTF16.compress. If that fails, it returns null and the constructor falls back to using UTF-16. ' is incorrect in unsynchronized code. The reality is that it's permitted to do all these things at the same time in any order (or speculatively do both at the same time) as long as the observable consequences are the same. This relies on the assumption that the data stays the same. If you violate that assumption, you get bizarre and often unpredictable behavior.
I don't think this is a bug in String. It may be a security vulnerability in the JVM, in a log4j-esque "it's working as we intended but holy crap did we ever not intend on this interaction" manner.
It may run your code out of order, and even JIT-recompile it out of order, and your code that's like
int oldValue = val;
doSomething(val);
if (val != oldValue) throw new ConcurrentModificationException();
int oldValue = val;
if (val != oldValue) throw new ConcurrentModificationException();
doSomething(val);
doSomething(val);
The Java Memory Model is a great accomplishment and if you heed it you will write performant multi-threaded applications with an ease that is rare in other languages. If on the other hand you do not heed the JMM, you will at best get a CME alerting you of this case, but in most cases just get holes in your feet.
...sure, if you are using primitives. But here we have an array (reference), the contents of which can be modified by `doSomething(val)` in your example. It is only the reference value that cannot be modified.
java.lang.String is a final class so in this case so doSomething can't be overridden, and strong assumptions can be made about doSomething's behavior and in practice it's likely inlined given that this is an extremely hot method.
Since this is a constructor, the reference can't be aliased by e.g. fields in the class, so static analysis of the code is surprisingly easy. The compiler just needs to answer whether this particular reference is mutated by the invoked function(s).
Yes, given the code in the String class, the JVM is allowed to execute it in this way. I'm not claiming that is wrong, I'm claiming the code in the String class should not have been written in a way that allowed the JVM to do that.
> If you violate that assumption, you get bizarre and often unpredictable behavior.
Java is (supposed to be) a safe language, that maintains its integrity. It does not have the effect that doing something that was not documented as being safe leads to _undefined behaviour_ and therefor all bets are off (like e.g. C).
I'm pretty sure the JDK maintainers intended for String to be a thread safe class with guarantees that can not be broken with race conditions. It's true that the thread safety of String is not explicitly documented, but I believe that's just an oversight in the docs, that String being thread safe just goes without saying. I realize that's hand-wavy, and I don't have any hard proof for that right now, so I understand not everyone might be convinced of that. I'll wait for the bugfix to make that more clear. I don't expect that fix to have a significant performance impact. Fixing it doesn't necessarily require more barriers or more defensive copies. See e.g. this draft patch (incomplete, but good enough to give a rough idea of how it could be done): https://gist.github.com/amaembo/83b4aeab1cd190f2e1dbd75eacb3... .
But the combination with interning, the "hello world".startsWith("hello") example, is clear evidence that it is a bug. Some code running in the same JVM having triggered some race condition earlier should not break unrelated code, it should not put the JVM in a broken state where such code behaves in nonsensical ways.
"hello world".startsWith("hello")
can return false in any circumstance, is a bug in the language. The fact that some other code in an entirely unrelated part of the codebase can intern a broken string and thus break string-comparisons for the entire codebase, is mind boggling.
Fortunately, I don't think the fix needs to be too expensive. After a defensive copy of the byte-array is made, just before returning the newly constructed string object, verify once again that the chosen coder matches the string contents. If it doesn't, that would imply a race condition, and the broken string instance should not be returned
Maybe poster meant only copying the reference with `char[] copy = original` which indeed does nothing, but that's not a defensive copy.
Whether the JVM actually does this for arraycopy is an implementation detail. The JVM is permitted to perform this type of escape analysis and elision, and definitely does for some allocations.
In general arrays and concurrency doesn't mix very well in Java, and is something I'd avoid mixing on principle. You avoid most of these types of problems by having threads talk by passing around immutable objects via concurrency primitives, volatile references, synchronized-blocks, etc.
Sound sensible. I think what you've said is any semi-malicious code can give you a primitive array, then modify it from under you in another thread. That's not completely surprising but the clincher is, you can't even take a defensive copy.
This would probably do
byte[] b;
// A
synchronized (a) {
b = System.arraycopy(a);
}
// B
It is "fully permitted to assume the original array is identical to the copied array" only to the extent that affects reading from the original array, not the copy (ie, it can pretend that the original didn't change, even it did).
Anything else would break causality requirements (JLS§17.4.8.).
Allocating new String objects might very well be the most frequent memory allocation operation in the JVM. IMO it would be a mistake to do anything to slow this down to protect against this weird instantiation behavior, unless it implies a security vulnerability which can't be fixed by guards at the interning step.
Compared to this, I wager that the incremental cost is small to verify that the coder matches the content.
Also, depending on the implementation of string-interning and StringUTF16.compress, it's possible that the verification step is only needed for non-LATIN1 strings. Which according to the JEP is only a small minority of strings seen.
If there is a cheaper solution, I'm certainly all for it. I'm just spitballing ideas here. But I don't think it is acceptable to allow "hello world".startsWith("hello") to return false.
It would likely be faster since currently the implementation restarts the entire conversion from 0 in utf16 mode.
It is weird Java considered it a bug, I expect it to be resolved as "wont do"
I might tell you about another "bug" and "invariant violation" which is possible but is not a bug. Try to use Sets or Maps with keys having broken hashcode.
Is it good that this can happen? No, Java must be more like Scala and push immutability as sane default.
Is it a bug? No.
Is it possible to "fix" the language and the VM at this stage? Yes, but that would be a new language and new VM. So, that's not going to happen.
But it's specified that standard Java classes are thread unsafe by default. So this is a specified behaviour.
In my opinion the author might need to read the vm and memory model spec and understand that such things are expected in Java.
There are real bugs in standard library singletons (e.g. concurrent Filesystem calls might fail during singleton initialization, while plugins are loaded). These bugs are being ignored for years.
The author must not expect any "fix" for this in foreseeable future, but they might expect being laughed at.
The author's views on how concurrency works is very common and taught in schools and textbooks, but also quite inadequate.
Instead let's take this opportunity to talk and teach about the JMM and deepen the collective understanding of the many unintuitive behaviors of multi-threaded applications.
It is the key to reasoning about Java concurrency. Any other model that is not the JMM is flat out wrong. It is virtually impossible to write correct concurrent Java without understanding the memory model.
The bug is a potential security vulnerability since it can affect the value of interned strings, which can break other libraries.
This is not a bug, but a specified behavior.
You are right that there is an expecation or assumption of such (from the users), which makes it even more interesting when it breaks.
Locking a thread for every allocation of a string is very likely cost-prohibitive and not a great trade-off for the common case. It would make more sense to add something like StringFactory.CreateString(char[]) and instruct developers in using it if thread safety is nessecary.
I don't think the correct answer is to sacrifice any performance to guard against this weird edge case, though.
The type whose thread safety is in question here is not actually String, but char[]. I'm not going to say it is always wrong to share char[] between threads (as a primitive array of something other than double and long, the Java Spec does make some guarentees about char[]), however it is almost always wrong to be sharing char[] between threads.
If you want a language that protects you from this type of mistake, you simply need something more advanced than Java.
This isn't even the biggest hole in Java's safety. Java has a type system, which is at least a nominal claim to type safety. Yet, you can do things like:
Integer[] foo = new Integer[1];
Object[] bar = foo;
bar[0] = new Object()
Its even worse with generics:
List<Integer> foo = new ArrayList<>();
List bar = foo;
bar.add(new Object());
System.out.println(foo.get(0));
Integer x = foo.get(0);
In fairness to java on the last one, it is at least a warning, and a deliberate compromise to support backwards compatability when they introduced generics.
Every language’s type system gives you escape hatches, so that last example is similar to how one might implement an optimization library in Rust where you have uninitiated elements. Hell, there you don’t even get runtime errors if you get it wrong, it will just segfault. So I really disagree with this notion of “it even worse with generics”.
The correct way to do this is use the MaybeUninit<T> type. Then you're responsible for correctly initializing a T before you call MaybeUninit<T>::assume_init() to get a T.
(nonetheless, thanks for mentioning the MaybeUninit, that was what I was thinking of, but didn't remember the name -- I haven't programmed in Rust for a long time)
Depending on how long "a long time" is, you might well not actually have been thinking of MaybeUninit. The prior solution (until mid-2019) was as you describe, and it was in fact unsound.
MaybeUninit<T> doesn't override the compiler's knowledge. It's using one very, very clever trick. Take a look at how MaybeUninit is defined. It's a union! The compiler can see this might be a T, but it can't ever see whether it's actually a T right now. As a result all the mis-optimisations which occur with the unsound approaches can't happen. MaybeUninit<T>::assume_init() is just a union read, which, sure enough, is an unsafe operation in Rust (writing to a union is safe, but reading from one is not) and that's why the function is unsafe.
† This is technically sound for Zero Size Types, because then we're basically saying e.g. "You see nothing? Well, I promise it's actually no Spoons, like, an array of 0 Spoons". So that can't cause the compiler to emit code that we didn't expect - the Rust compiler isn't going to emit code to read or write no Spoons, whether or not they "exist" according to type analysis.
Not quite, it is String constructor that has the race condition, char array is incidental there.
For example, take a java.util.concurrent.ConcurrentHashMap, which is thread-safe. If your value object is mutated concurrently, and is not thread-safe, you can't expect anything sensible to happen if you call containsValue().
Likewise, String's char[] constructor can only be thread safe if there are no concurrent changes to the argument.
While that’s generally true it’s not the case here, char[] does not invalidate anything upon mutation it just changes.
The issue is that the ctor checks for a property (all chars are under 256) then assumes that holds indefinitely.
You could say that this is a classical TOCTOU bug as the ctor assumes that a mutable argument does not mutate.
The core question[s] here are whether this assumption is and should be in the contract.
Protection against these kinds of bugs is only possible with deep copies of mutable arguments or COW semantics. So you either implement callee defensively and slow down general case (remember, this is stdlib), or you leave concurrency control to the caller. Probably every sane general purpose language does the latter.
Indeed.
> Protection against these kinds of bugs is only possible with deep copies of mutable arguments or COW semantics.
In the general case yes, but in this case no, you can solve the issue and improve performances by implementing the thing correctly, in a single pass over the input. This way you don’t get a split-brain situation.
Basically, if you look at why the standard library would not go out of its way to prevent you from doing stuff like this it boils down to the same reason as why they put the string compression optimization in to begin with: doing so would make things slower rather than faster. And that's just not desirable in something as performance critical as string initialization, which is a thing that a lot of Java programs would do a lot.
Having string compression helps save some memory but it's a weird low level hack. It's fine as long as you don't actively try to break things in your own program. You'd have to jump through some hoops to do it accidentally. That is not likely to happen just like that.
So, not a bug but a known limitation that you should be aware of if you go down the path of doing lots of concurrent modifications to arrays that may or may not be used to create Strings. Java has lots of nice primitives and frameworks to make writing such code less error prone but it's up to you to use those properly and it's entirely possible to write all sorts of code that has lots of concurrency issues.
[1] https://en.wikipedia.org/wiki/Time-of-check_to_time-of-use
Currently the code tries to encode the chars, and if it fails it completely bails out and restarts with a code unit copy. The bailing and restarting is what offers the opportunity for TOCTOU.
But if instead of bailing it converted the data collected so far to code units, then appended the code unit on which it failed, then switched to a UTF16 copy loop, the result would necessarily be correct (at least insofar as a UTF16 string would not contain just latin1)
And in fact this would likely be more efficient than the current version, because we already know that everything we've already converted is valid latin-1, which means we can literally just copy that to every other byte. There is no need to re-do that validation and conversion work. Which is currently the case, because StringUTF16.toBytes redoes the entire thing from zero.
But still, for the few people who actually trust Java's isolation features and use it, possible bypasses are a concern. Having said that, I don't see how you can turn this into an attack on String.intern.
The guarentees about interning are as follows:
> When the intern method is invoked, if the pool already contains a string equal to this String object as determined by the equals(Object) method, then the string from the pool is returned. Otherwise, this String object is added to the pool and a reference to this String object is returned.
> It follows that for any two strings s and t, s.intern() == t.intern() is true if and only if s.equals(t) is true.
If you pollute the pool with a "broken" String, all that would happen is that that String would not be returned in place of a logically equivalent correct String, and vice-versa.
Regardless, the fix is quite simple. The public String.intern method just needs to validate the encoding first. This will have little impact on performance because the String.intern method is rarely called.
It's perfectly fine to code String.intern() defensively against such dodgy String-s, but in any sizable program with shared memory concurrency and untrusted or unverified code, there will be millions of other potential data races. The only sensible choice would be to not use such a mix.
By my reckoning it would speed things up, at least going by the Java code.
Unconditionally duplicating the array would use more memory and wouldn’t be faster.
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 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
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.
Wasn't there an attempt for Java to define the range of outcomes even of programs with data races?
More specifically Java says something like, if you race a value of some sort, even a complex value like a hash table, it doesn't get fatally damaged, but its new state is some state it had, or might have during other executions.
It's not Good that the Java code has a bug you don't understand, but it's very unlikely to have completely wild outcomes like giving Jimmy a massive pay rise.
When they began this work, as I understand it the Java engineers imagined humans can successfully reason about the resulting bugs, but turns out that's not true. So this work might have been deemed unnecessary if they'd known that but obviously it's hard to know without trying.
// specifies that "compareTo returns 0 exactly when the
// equals(Object) method would return true")
Seems like at least a documentation error.