So you think you want to write a deterministic hypervisor? • Hacker News Board

Re: So you think you want to write a deterministic hypervisor?

#21

Post by Veserv » Wed, Mar 20, 2024, 6:53 PM UTC

aftbit wrote: post #17

How does this deal with non-determinism from the outside world? For example, let's say one of my tests is flaky because it asks an external service to give it some data, and that external service is flaky in what it returns? Or what if my bug is caused by bitflips in failing memory, that lead to impossible control flow paths being hit? Think something like: if x != 0: return 1/x Failing with an error because x is 0.…

The product does not appear to be a record-replay debugging product, it appears to be a precise fault injection test generation product.

In a record-replay debugging product, you want to reproduce the execution of your system to translate what occurred in reality into the debugging lab.

In this product, the goal appears to be creating a deterministic environment so that you can precisely inject non-determinism/faults to probe the response of your product to the environment.

The former is about analyzing bugs your test found, the latter is about creating tests to produce bugs. In that context, your question is unrelated to the product. It does not seek to reproduce flaky tests, it seeks to help invent new and exciting flaky tests.

Re: So you think you want to write a deterministic hypervisor?

#22

Post by wzdd » Wed, Mar 20, 2024, 7:07 PM UTC

I'm not familiar with the area, so am likely missing something, but how do they do deterministic thread-level context switching? Something like:

  var_1 = 0  
  var_2 = 0
  
  thread_a:
    while true:
      something_complex()
      var_1 ++
  
  thread_b:
    while true:
      something_complex()
      var_2 ++

Under the quoted definition of determinism, for every point in time, var_1 and var_2 should have the same values across all executions. But this would seem to amount to ensuring that exactly the same number of instructions are executed each time a thread is scheduled.

Re: So you think you want to write a deterministic hypervisor?

#23

Post by wwilson » Wed, Mar 20, 2024, 7:14 PM UTC

wzdd wrote: post #22

I'm not familiar with the area, so am likely missing something, but how do they do deterministic thread-level context switching? Something like: var_1 = 0 var_2 = 0 thread_a: while true: something_complex() var_1 ++ thread_b: while true: something_complex() var_2 ++ Under the quoted definition of determinism, for every point in time, var_1 and var_2 should have the same values across all executions. But this would se…

You are exactly correct. Our hypervisor grants you this power (and then we use the power to explore as many possible values of var_1 and var_2 as we can, in case some of them trigger a concurrency bug, e.g.)

Re: So you think you want to write a deterministic hypervisor?

#24

Post by wzdd » Wed, Mar 20, 2024, 7:21 PM UTC

wwilson wrote: post #23

wzdd wrote: post #22

I'm not familiar with the area, so am likely missing something, but how do they do deterministic thread-level context switching? Something like: var_1 = 0 var_2 = 0 thread_a: while true: something_complex() var_1 ++ thread_b: while true: something_complex() var_2 ++ Under the quoted definition of determinism, for every point in time, var_1 and var_2 should have the same values across all executions. But this would se…

You are exactly correct. Our hypervisor grants you this power (and then we use the power to explore as many possible values of var_1 and var_2 as we can, in case some of them trigger a concurrency bug, e.g.)

Nifty! Thanks for the response.

Re: So you think you want to write a deterministic hypervisor?

#25

Post by tlb » Wed, Mar 20, 2024, 7:47 PM UTC

Interesting project. I almost wish I had a concurrency bug to test it on.

> Guest software running in the Antithesis platform still experiences concurrency similar to a multi-core / multi-machine system, thanks to the process scheduling imposed by the guest OS

This might not exercise the full set of race conditions. When two threads are running simultaneously on separate cores (or hyper-threaded on the same core) they can interleave instructions at a much finer granularity than any OS time slicing would cause, even within instructions.

For example, could it find a race condition where two threads are executing INC [addr] on the same memory address, where context switching between instructions doesn't trigger it?

Re: So you think you want to write a deterministic hypervisor?

#26

Post by metalcrow » Wed, Mar 20, 2024, 7:48 PM UTC

This is a very promising project that I've seen a lot of attempts to do in the past, but never got to the level of progress that you have! Very impressive work!

I am sad that you decided to give up on solving the multi-core parallelism issue, since each guest running on a single core is a dead giveaway to malware that they're not on a real machine, but it's understandable. I do wonder if that means that some class of bugs will be undetectable to this hypervisor, though.

Re: So you think you want to write a deterministic hypervisor?

#27

Post by wmf » Wed, Mar 20, 2024, 7:51 PM UTC

tlb wrote: post #25

Interesting project. I almost wish I had a concurrency bug to test it on. > Guest software running in the Antithesis platform still experiences concurrency similar to a multi-core / multi-machine system, thanks to the process scheduling imposed by the guest OS This might not exercise the full set of race conditions. When two threads are running simultaneously on separate cores (or hyper-threaded on the same core) the…

If history is any guide, everybody has concurrency bugs.

Re: So you think you want to write a deterministic hypervisor?

#28

Post by metalcrow » Wed, Mar 20, 2024, 7:52 PM UTC

tlb wrote: post #25

Interesting project. I almost wish I had a concurrency bug to test it on. > Guest software running in the Antithesis platform still experiences concurrency similar to a multi-core / multi-machine system, thanks to the process scheduling imposed by the guest OS This might not exercise the full set of race conditions. When two threads are running simultaneously on separate cores (or hyper-threaded on the same core) the…

> For example, could it find a race condition where two threads are executing INC [addr] on the same memory address, where context switching between instructions doesn't trigger it?

I'm not actually familiar with the details of hardware MMUs, but would they not enforce sequential access of the address? Or do MMUs allow parallel reads and writes?

Re: So you think you want to write a deterministic hypervisor?

#29

Post by wmf » Wed, Mar 20, 2024, 7:53 PM UTC

wzdd wrote: post #22

I'm not familiar with the area, so am likely missing something, but how do they do deterministic thread-level context switching? Something like: var_1 = 0 var_2 = 0 thread_a: while true: something_complex() var_1 ++ thread_b: while true: something_complex() var_2 ++ Under the quoted definition of determinism, for every point in time, var_1 and var_2 should have the same values across all executions. But this would se…

ensuring that exactly the same number of instructions are executed each time a thread is scheduled

AFAIK this is possible by (mis)using performance counters.

Re: So you think you want to write a deterministic hypervisor?

#30

Post by tlb » Wed, Mar 20, 2024, 8:01 PM UTC

metalcrow wrote: post #28

tlb wrote: post #25

Interesting project. I almost wish I had a concurrency bug to test it on. > Guest software running in the Antithesis platform still experiences concurrency similar to a multi-core / multi-machine system, thanks to the process scheduling imposed by the guest OS This might not exercise the full set of race conditions. When two threads are running simultaneously on separate cores (or hyper-threaded on the same core) the…

> For example, could it find a race condition where two threads are executing INC [addr] on the same memory address, where context switching between instructions doesn't trigger it? I'm not actually familiar with the details of hardware MMUs, but would they not enforce sequential access of the address? Or do MMUs allow parallel reads and writes?

x86 processors have a LOCK instruction prefix, which makes some instructions atomic including increment. Increment is nontrivial to make atomic, because there are two memory accesses: read X and write back X+1. It's a bit slow, because it has to inform every other core in the system, "Hey, I just read this memory address and I'm about to write something back to it, so don't don't use it until I'm done." C++ has functions to do this like std::atomic_fetch_add, but they're clunky to use so people often forget.