[HN Gopher] So you think you want to write a deterministic hyper...
___________________________________________________________________
So you think you want to write a deterministic hypervisor?
Author : wwilson
Score : 123 points
Date : 2024-03-20 13:32 UTC (9 hours ago)
(HTM) web link (antithesis.com)
(TXT) w3m dump (antithesis.com)
| deater wrote:
| strange they seem unaware of the RR deterministic debugger work
|
| especially as that builds off of the extensive work done on x86
| counter determinism here:
| https://web.eece.maine.edu/~vweaver/projects/deterministic/
|
| it turns out x86/amd chips many of the perf counter events are
| offset by the (unpredictable) interrupt count because the
| interrupt return instruction uop gets counted as both a user and
| kernel instruction. On many processors the retired store
| instruction avoids this issue.
| voidmain wrote:
| There is some overlap, but the situation in a hypervisor is in
| fact pretty different.
| wwilson wrote:
| We are not only aware of RR, we've had extensive conversations
| with Rob and Kyle! Big fans of their work at Pernosco.
| debbiedowner wrote:
| We do something similar in house where I work. Is it hard to
| onboard new customers? Since they make a special container for
| you they basically adopt your build system, which may be hard for
| them. Does this go beyond mutation testing?
| wwilson wrote:
| With most of our customers, they don't actually have to change
| their build system at all. We take their normal CI products,
| plus a small amount of special configuration, and run them.
| This is actually a good thing because we're testing something
| very similar to what runs in production.
|
| The kinds of state space exploration we do are a lot more
| general than mutation testing. Our current product does
| exploration by (1) varying the space of faults, packet delivery
| times, thread schedules, etc., and (2) driving a customer-
| provided pseudo-randomized workload. We have plans to make both
| these mechanisms much more expressive, powerful, and
| configurable; and we have longer-term plans to add entirely new
| kinds of testing to the same platform.
|
| Disclosure: I'm one of the co-founders of Antithesis.
| ilzmastr wrote:
| Thanks! Where does the "want" come from to compare your
| "got"s to? If the customer code handles errors gracefully,
| can you still surface undesirable behavior?
| wwilson wrote:
| We provide a bunch of different ways for you to express
| your test properties. (1) A lot of stuff we can detect
| automatically, like crashes, OOMs, etc. (2) You should turn
| on assertions in all the code you send to us. (3) We can
| write generalized temporal regexes against your log
| messages or other output. (4) We offer SDKs that allow you
| to declare test properties inline in your code. (5) We can
| integrate with off-the-shelf sanitizers like ASAN, the Go
| race detector, etc.
| wyldfire wrote:
| Hermit [1] is another cool effort at determinism/reproducibility.
|
| [1] https://github.com/facebookexperimental/hermit
| eatonphil wrote:
| Yes it is, for simple programs anyway. On the other hand, I've
| tried using Hermit to wrap around tests of a Raft
| implementation in Rust and Hermit would crash no matter what I
| did. Perhaps it was me using threads, perhaps it was me using
| sockets, I have no idea. The error messages were pretty obscure
| to me. The Hermit devs don't seem to be super responsive in
| general to issues on the repo. I don't blame them of course.
| wyldfire wrote:
| > The Hermit devs don't seem to be super responsive in
| general to issues on the repo. I don't blame them of course.
|
| Maybe I got lucky but I reported some issues right around the
| time of their article publication [1] - Nov '22 - and they
| were pretty responsive then.
|
| [1] https://developers.facebook.com/blog/post/2022/11/22/herm
| it-...
| eatonphil wrote:
| Yeah the repo activity in general seems to have died down a
| bit since then.
| immibis wrote:
| This is for a distributed database product that claims to bypass
| the CAP theorem or have I misunderstood?
|
| > Back then Spanner wasn't public yet and a lot of people
| misinterpreted the CAP theorem to say that a strongly consistent
| database couldn't also be highly available in the face of network
| faults.
|
| - https://antithesis.com/blog/is_something_bugging_you/
| wwilson wrote:
| A lot of us worked at FoundationDB, but this is a new company
| (Antithesis) which develops autonomous testing and debugging
| tools.
| Joker_vD wrote:
| By the way, that's one cool-looking cybernetic ant-eater. Is
| that what an ant-ithesis supposed to look like?
| terpimost wrote:
| Thank you :) anteater is Antithesis mascot but this cyber
| version of it the only illustration I could come up with
| for the Determinator. There were other much more creepy
| versions :)
| wmf wrote:
| Probably referring to:
|
| https://cloud.google.com/blog/products/databases/inside-clou...
|
| https://apple.github.io/foundationdb/cap-theorem.html
| comex wrote:
| What a tease! They describe in detail two problems they had to
| "invent workarounds" for, but say nothing about what the
| workarounds are. I'm very curious, since both of the problems
| sound quite hard to work around. I wonder if they're being
| purposefully vague to make it harder for competitors to replicate
| their work...
| aftbit wrote:
| 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.
|
| Not hypothetical scenarios, both real bugs I've had to
| troubleshoot in my career.
| wwilson wrote:
| 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 of the inputs to
| your system are being provided by our platform, and that any
| dependencies have to be mocked, or run inside the hypervisor
| with you.
|
| In practice this can cause friction for people with a ton of
| dependencies. Some of the most common things we've already
| mocked (for example we have an entire fake AWS that we can run
| in there with you), and if your dependency is one of our
| existing customers, we can probably work something out...
| indiv0 wrote:
| How do y'all provide the fake AWS? Is it built in-house or
| are you running something like LocalStack?
| Veserv wrote:
| 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.
| wwilson wrote:
| 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.
| Veserv wrote:
| 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.
| wzdd wrote:
| 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.
| wwilson wrote:
| 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.)
| wzdd wrote:
| Nifty! Thanks for the response.
| wmf wrote:
| _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.
| wwilson wrote:
| 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.
| tlb wrote:
| 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?
| wmf wrote:
| If history is any guide, everybody has concurrency bugs.
| metalcrow wrote:
| > 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?
| tlb wrote:
| 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.
| metalcrow wrote:
| 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.
| monocasa wrote:
| 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 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.
| wwilson wrote:
| 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...
| metalcrow wrote:
| 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.
| wwilson wrote:
| 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!
| metalcrow wrote:
| 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.
| delta64 wrote:
| 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.
___________________________________________________________________
(page generated 2024-03-20 23:01 UTC)