Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

So you think you want to write a deterministic hypervisor?

antithesis.com

Post reply on HN
Print view View original

31–40 of 56 posts

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

#31

Post by wwilson »

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…

You are correct. There's a set of concurrency bugs that require actual SMP setups to trigger (like stuff with atomic operations, memory ordering, etc.). If you're trying to build a very low-level lock-free data structure where this is your primary threat model, Antithesis is not the right tool for you... for now... until we build a CPU simulator...

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

#32

Post by wwilson »

metalcrow wrote: post #26

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…

What do you mean by a dead giveaway to malware? We're allowed to lie to the guest OS about how many CPUs there are!

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

#33

Post by wwilson »

Veserv wrote: post #21
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…

You're sort of right, but we're actually sort of both. We use determinism to do controlled fault-injection and to explore your program's state space, but we can also use it for very powerful debugging. Look for future announcements about this.

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

#34

Post by metalcrow »

tlb wrote: post #30
metalcrow wrote: post #28

Earlier quoted context omitted.

> 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 funct…

Ahh, it's 2 separate memory accesses just encapsulated in one instruction, that explains it. Yeah, unless this hypervisor allows context switching at the level of microcode ops, that seems to be undetectable currently.

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

#35

Post by metalcrow »

wwilson wrote: post #32
metalcrow wrote: post #26

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…

What do you mean by a dead giveaway to malware? We're allowed to lie to the guest OS about how many CPUs there are!

Not a dead giveaway i suppose, you're right. And in fact, since you can control precisely the number of instructions per thread timeslice, it does seem non-trivial to decide if you're running under more then one core due to the hypervisor being able to inject non-determinism into the context switching.

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

#36

Post by wwilson »

wmf wrote: post #29
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.

Alex discusses this in the post. Performance counters were the first thing we tried, but alas they're non-deterministic about every one-in-a-trillion instructions.

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

#37

Post by delta64 »

I've long thought about these kind of OS designs, and what great features they can enable (such as time travel debugging). But the non-determinism introduced by inter-CPU interactions is a fundamental limitation, hence the need to run everything on a single isolated core.

One day(^TM) I'm really keen to design a multi-core CPU architecture that allows for deterministic message passing between cores in such a way that you could get this kind of software working with true parallelism.

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

#38

Post by Veserv »

wwilson wrote: post #33
Veserv wrote: post #21

Earlier quoted context omitted.

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…

You're sort of right, but we're actually sort of both. We use determinism to do controlled fault-injection and to explore your program's state space, but we can also use it for very powerful debugging. Look for future announcements about this.

Certainly. Once you have a deterministic environment, the ability to replay execution is basically free.

In fact, what has been described is basically the replay engine in a record-replay system which “runs” the recorded execution of a non-deterministic system in a deterministic mode to replay the exact same execution. As such, it retains the same benefits available to any replay. The key here is that you can “bypass” the record step since you are already running in the replay engine from the start.

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

#39

Post by monocasa »

tlb wrote: post #30
metalcrow wrote: post #28

Earlier quoted context omitted.

> 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 funct…

The way that's currently implemented is actually just one memory operation these days. L2 (or really wherever coherency is mostly managed) has a tiny ALU so in addition to read or write, atomicop is an operation you can send to L2. It'll gain Modified or Exclusive access to the cache line(s) that op is addressed to and just do the operation right there. That way the normal cache protocol is all you need for atomicity, and really the line is only contended for a single cycle from the L2 controller's (and the rest of the coherency peers) perspective.

That's why they retconned the lock prefix to not be an actual assertion of the #LOCK signal any more.

That's also why TileLink and AMBA include atomic ops like addition and bitwise ops in their coherency protocols rather than just 'claim region'.

That's also why you see newer archs like RISC-V and Arm64 that have both lr/sc style ops, in addition to direct atomic memory ops like amoadd.w, it better matches the primitives of the underlying memory system.

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

#40

Post by indiv0 »

wwilson wrote: post #19
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.…

Bitflips are an interesting form of fault-injection that we could add: https://antithesis.com/docs/applications/reliability/fault_i... If you know somebody who will pay money for us to prioritize this feature, let me know! Otherwise, I'm sure we'll get to it eventually. We have all kinds of crazy ideas for new faults. Communication with the outside world is something that we obviously have to ban. This means that all…

How do y'all provide the fake AWS? Is it built in-house or are you running something like LocalStack?
Post reply on HN