Unit testing of potential concurrency problems

Question

I have had recently a small contest with one of my colleagues (whom I very respect) regarding a theoretical possibility to test whether some code is thread-safe or not.

Let us suppose that we have a some "black-box" class FooUnknown taken from the 3rd party library, so we don't have an access to its original source code. Furthermore, it might be that it internally uses some native methods (if this is a matter).

Can we write such an unit test which will tell us that usage of this class (for example, its instance shared between several threads) is 100% thread-safe or not?

My conclusion, that it is not possible. For me it is obvious and straightforward: although one can write a code which will lead to some concurrency problems which is possible to detect. But an absent of such results doesn't guarantee that there are not concurrency issues at all.

Also I believe, that this question is not too broad. For certainty let us say we have a class some.FooUnknown and we want to use it in the following way:

@ApplicationScoped
public class FooService {
    private some.FooUnkown foo = new some.FooUnknown();

    public void someStuff() {
        // ...
        String result = foo.doSomeStuff();
        // ...
    }
}

How to test it to be sure that it is thread-safe, that we don't need to wrap it into ThreadLocal<FooUnknown> for instance?

Answer 1

Ignoring all practical reasons, this is also why it's theoretically hard to achieve a complete set of concurrency safety tests:

Assuming there are n threads operating on the same data structure. Then any thread i has a sequence of S_i atomic operations on this datastructure, where each sequence may have a different length. Now what you need to make sure in an ideal environment is that every possible iteration sequence across all threads through these operation is covered by your tests. Even for relatively small operation sequences and only 2 threads this number grows quite fast.

But now the difficult part is to translate these findings to a real computer. Identifying such atomic operations itself is a complex task of its own, given the freedom of how jvms can be implemented and the java memory model. Then there is also thread scheduling controlled by os. So it's usually out of your control what actual operation sequence takes place on the data structure.

Answer 2

It is impossible, because there are to many ways to produce thread unsafety. Just a global variable in native code could be enough.