A way to make mutated code stop eventually

[ordnungswidrig]

Mutated code can be stuck in a loop. I suggest to add to the mutation a check for the running time or iteration count which can throw an Exception as a last resort to kill the thread.

[mbj]

@ordnungswidrig This is a known problem and I suggest to add a timeout always inside the test framework. This is superior as having mutant to add the timeout in the mutation testing tool.

Its an important invariant you can take mutated code and run it by hand without the mutation testing tool involved and get "exactly" the same red-green behavior you'd get from with the tool. If the mutation testing tool where adding timeouts results where misleading on manual reproduction.

[jstepien]

Thanks for filing the issue, @ordnungswidrig. I appreciate your feedback, @mbj; thanks a lot for sharing your insights.

We're facing a number of constraints with regard to non-terminating mutants. To the best of my knowledge:

• We can't tell whether a mutant will terminate,
• There's no timeout functionality built into clojure.test,
• There's no reliable way to stop a JVM thread or a Clojure future,
• JVM cannot fork, thus preventing us from running tests in child processes,
• Spinning up a JVM per test run would be extremely time-consuming, and
• Extra code inserted into mutants for determining non-termination at runtime might be fragile and unreliable.

Please correct me if there's anything proving to the contrary.

In the light of those constraints I'm considering two approaches right now.

To begin with, we should look into what's been done in the JVM world already. Pitest is a valuable example of prior work; we share the same virtual machine and are probably facing same limitations. Markus' Mutant might be facing same constraints when running on JRuby.

In case research won't lead us anywhere, we could do what follows. We could maintain an on-disk per-project list of mutants which led to non-termination. Whenever a mutant exceeds our timeout threshold we'd append it to the on-disk list, stop the JVM, and restart our mutation testing cycle from where we were, skipping the guilty mutant. The on-disk list would prevent us from running into it again in future.

I'd love to learn your thoughts on this.

[ordnungswidrig]

There's no timeout functionality built into clojure.test,

There's no way for any test framework to stop an endless loop an a test anyways. Besides killing the JVM the only way I see is to add a check to the code mutation like I described.

[mbj]

There's no way for any test framework to stop an endless loop an a test anyways. Besides killing the JVM the only way I see is to add a check to the code mutation like I described.

There is no way to spin up a thread to run the tests, and have a 2nd thread monitor the first one and raising an async (timeout) exception in case it runs to long?

[jstepien]

There is no way to spin up a thread to run the tests, and have a 2nd thread monitor the first one and raising an async (timeout) exception in case it runs to long?

That's a vey good question. To the best of my knowledge there's no easy way to achieve it on JVM.

We can spin up a thread to run the tests and have another thread monitor the first one. Unfortunately, we can't forcefully raise an exception in another thread in a general case. It is possible to interrupt a JVM thread, which will cause an exception only if the interrupted thread is in a particular state. If it's not interrupting it will set its interrupted status, which can be ignored in a tight CPU loop.

Consider the following example. I'll start a background thread, which will keep sleeping in a loop, 1ms per iteration. After 2s I'll interrupt the thread from the main thread. The interrupted thread will terminate. Afterwards I'll repeat the experiment, but this time the background thread will execute a CPU-intensive task. My interruption is ignored. The program never terminates.

(println "Starting the background thread.")

(let [thread (doto (Thread. (fn [] (while true (Thread/sleep 1))))
               (.start))]
  (Thread/sleep 2000)
  (println "Interrupting.")
  (.interrupt thread)
  (while (.isAlive thread)))

(println "Done.")

(println "Starting the background thread with a tight CPU loop.")

(let [thread (doto (Thread. (fn [] (while true (+ 1 2))))
               (.start))]
  (Thread/sleep 2000)
  (println "Interrupting.")
  (.interrupt thread)
  (while (.isAlive thread)))

(println "Done.")

A similar experiment can be conducted with Clojure futures, replacing the interrupt method call with future-cancel invocations. A future with a tight CPU loop will keep executing in background.

An alternative method of stopping a thread—by using Thread.stop—is unfortunately deprecated according to the official documentation.

We could theoretically allow our mutants to be interrupted by injecting (Thread/sleep 1) into them and then calling the interrupt method on timeout. I'm not sure if it solves the problem in a general case, though.

[mbj]

We could theoretically allow our mutants to be interrupted by injecting (Thread/sleep 1) into them and then calling the interrupt method on timeout. I'm not sure if it solves the problem in a general case, though.

Also this changes the semantics in subtle ways, and may not be desired at all. Alternatively you could insert mutations that check a global "should be stopped" variable often enough. Still this would fall short in case the execution is working a long time (or even infinite / stuck) on code outside the mutated area.

What about using futures as described here: http://stackoverflow.com/questions/5715235/java-set-timeout-on-a-certain-block-of-code/15120935#15120935

[ordnungswidrig]

Thread/interrupt only signals the request to interrupt to the Thread: "If none of the previous conditions hold then this thread's interrupt status will be set." . Thread/sleep and few other JDK methods check for it, as should any eventually long lasting looping code.

There's no way to force it besides checking for Thread/isInterrupted in the injected/mutated code. I figure Thread/isInterruped is highly optimized and thus cheap compared to JVM restart etc. and maybe a simple thing mutant can try.

[hcoles]

There's two parts to this issue.

a) Determining if an infinite loop has occurred
b) Killing the running code

The best solution I've come across for a) is to insert probes into the code and count how many times they are executed by the tests when a mutant is not present. A limit can then be set for how many times those probes can be hit when a mutant is active (e.g allow 3x the hits).

This solution ensures the result cannot be affected by other things happening on the box at the same time.

An easier to implement but less good approach (which pitest currently uses) is to time the normal execution time of each test, and consider a mutant to have caused an infinite loop if it exceeds some multiple of this + a fudge factor to take into account other things that might be happening in the environment.

For part b) it's true that you can't reliably kill a thread in Java. You can however reliably kill a jvm.

Pitest has one main controlling process/jvm which launches sub processes. The main process can then kill a minion if it becomes unresponsive.

An alternative I experimented with for a while was instrumenting the mutated code with calls along the lines of.

if (DIE_FLAG_IS_SET) {
  throw RuntimeException();
}

The idea being that if this was present within each loop then we could get the code to exit out.

This sort of worked, but the sub process approach is far more robust and can also be used to provide isolation between mutants (e.g corrupted static variables, exhausted memory etc).

A trade off can be made between performance and isolation by choosing which/how many mutants are processed through a recycled minion.

[gilch]

These infinite loops are supposed to happen so rarely that if there are a multiple worker JVMs in subprocesses, occassionally killing and restarting one shouldn't affect run times much.

I think the chances of infinite loops can be further reduced by special-casing mutations in looping constructs, while suppressing the normal boolean mutations. E.g. just replace the whole condition expression with false so you loop zero times. I don't know if this is worth it, but I think Stryker mutates loops in this way.