37 ms·

Deterministic Linux for controlled testing and software bug-finding

167 points by rrnewton 4y ago

eatonphil 4y ago
I don't know for sure if they use sysemu in ptrace to do this (just that they use ptrace) but here's an awesome blog post that shows how you could build an emulator with just ptrace's sysemu: https://nullprogram.com/blog/2018/06/23/ https://nullprogram.com/blog/2018/06/23/.
- jasonwhite 4y ago
  I'm the primary author of Reverie[1], the syscall interception framework that Hermit sits on top of. We don't currently use ptrace's SYSEMU, but that's something I'm interested in looking into. Any way we can speed up syscall interception is a win. We currently use seccomp to trap just the syscalls we're interested in. This has the advantage of not even stopping on syscalls we don't care about. Note that we commonly want to inject multiple syscalls per intercepted syscall. I'm not sure how this would work with SYSEMU, but with the seccomp approach we mmap a page at a fixed address into the guest's memory that contains a syscall instruction. Then, we run this instruction instead of the original syscall instruction. Since it is always at a fixed address, we can exclude it from our seccomp filter. This prevents us from intercepting syscalls that we're injecting, getting into an infinite loop. Overall, we only have two ptrace stops: one before the syscall is executed and one after. We have a "tail_inject" optimization that can avoid the second ptrace stop and it results in about a 40% speed up, but in my observations we usually do care about the result of the syscall and must do the second ptrace stop for correctness. Perhaps ptrace's SYSEMU can be combined with seccomp can lead to a speed up, but I just haven't looked into it yet. [1]: https://github.com/facebookexperimental/reverie https://github.com/facebookexperimental/reverie
rrnewton 4y ago
This has been the culmination of several years of work intercepting and sanitizing the Linux system call API. It's now open source.
- hoosieree 4y ago
  I guess FB poaching you from IU in the middle of teaching your compiler course has a silver lining! Nice to see this being shared with the open source community.
  - rrnewton 4y ago
    Ah, at least you were in good hands with Michael Vollmer. Btw, he's now a prof at University of Kent in the UK (http://recurial.com/ http://recurial.com/).
    - hoosieree 4y ago
      So true! Glad to hear Michael is still in teaching.
- aseipp 4y ago
  Hey Ryan, just wanted to say I hope you're doing great these days! Really glad to see that the work originally done by you and Joe at Cloudseal evolving and becoming more readily available to all of us. I still thought back every once in a while about what y'all were up to. :) Super excited that it's kept on chuggin' and now is something we can all enjoy!
jasonwhite 4y ago
TL;DR: This is a Rust project that forces deterministic execution of arbitrary programs and acts like a reproducible container. That is, it hermetically isolates the program from sources of non-determinism such as time, thread interleavings, random number generation, etc. Guaranteed determinism is a powerful tool and it serves as a basis for a number of applications, including concurrency stress testing, record/replay, reproducible builds, automatic diagnosis of concurrency bugs, and more. I've been on the team working on this project over the past ~2 years. AMA! Here is the GitHub repository: https://github.com/facebookexperimental/hermit https://github.com/facebookexperimental/hermit
- CJefferson 4y ago
  This looks cool. Personally I'd also be interested in this for academic work -- anything which makes it easier to be sure an experiment can be reproduced later (a week, year, or decade later, in increasing order of difficulty), is good to have.
  - rrnewton 4y ago
    Yes, I'm very interested in that as well. I've been involved with the ACM Artifact Evaluation process which has been going on in several conferences for a while. https://www.acm.org/publications/policies/artifact-review-badging https://www.acm.org/publications/policies/artifact-review-ba... But it's been pretty frustrating. As an author, my PLDI 2014 artifact stopped working less than 5 years later (Docker image binary incompatibility). And when I was co-chair of an Artifact Evaluation Committee in 2017, there was not great reproducibilty of the artifacts that were submitted either. If you package a VM (freezing the Linux kernel), and are pretty sure that VM will run in 10 years, PLUS you determinize the execution itself... that should allow durable bitwise reproducibility. Maybe Hermit could be one ingredient of that. For scientific reproducibility, there is a lot of other tooling to build too, and I know some folks have been working in that area: https://ctuning.org/ https://ctuning.org/
- rrnewton 4y ago
  Note that this is a follow-on project from the earlier Dettrace system, which was applied mainly to reproducible builds (as in the academic paper, https://dl.acm.org/doi/10.1145/3373376.3378519 https://dl.acm.org/doi/10.1145/3373376.3378519, and presented to the Debian Reproducible Builds summit): - https://github.com/dettrace/dettrace https://github.com/dettrace/dettrace And one cool part of it is this Rust program instrumentation layer: - https://github.com/facebookexperimental/reverie https://github.com/facebookexperimental/reverie It's good for building OS-emulator style projects or tracing tools.
alex_suzuki 4y ago
Is it just me or are we experiencing an uptick in high-quality, sophisticated software projects being open-sourced by FAANG companies?
- crmd 4y ago
  It’s great how much open source infrastructure software has come out of FAANG in the past decade. Between Kubernetes, react, Kafka, etc it’s wild how much of my tech stack is open source software developed by people at large tech companies. It’s also great PR for the companies.
  - rrnewton 4y ago
    Heh, I implore you to consider the engineers-eye view. We're tech geeks inside or outside of FAANG, with all the usual incentives. I've been the tech lead on this project for 5 years, through 2 companies, and of course I hope someone finds it useful and chooses to contribute. I'd like to think we could help someone somehow with public relations, but I don't think we can ;-). Actually, I don't think any of the big techs are leaning all that much into recruiting right now though....
    - crmd 4y ago
      Hey, I totally rewrote my comment after reading your response. Thanks for engaging - hearing from the project author made me realize I was acting like a cynical asshole. Congrats on Hermit and thanks for supporting free software.
  - Enginerrrd 4y ago
    Facebook/Meta in particular seem to be hitting the front page with nerd-bait research. I suspect it is indeed part of a public relations strategy. And I hate to say it, but it's working on me. I've seen some really cool projects come out of Facebook lately!
- School-Cotton 4y ago
  Are we? PyTorch, React, etc. have been around for ages.
topazas 4y ago
maybe symbolic execution also can be included here?
- rrnewton 4y ago
  It's a good question. We would like to make it usable as a platform for dynamic analysis. The idea being that you can control all these external factors (like thread scheduling), find a crashing run, and then ask introspective questions of what the code is doing in a crashing run. In practice, one challenge we have is bridging between the runtime view of the software (as a debugger would see) -- raw machine instructions and system calls, and the static view that you would get from analyzing the source code. Sanitizers, for example (ASAN, TSAN, etc), are typically implemented in the compiler as program instrumenations. If we integrated binary instrumentation tools like Intel Pin or DynamoRio, we could perform additional dynamic analysis, but still at the machine code rather than source code level, which is a big gap from how symbolic execution normally happens, at the source code / AST level.
daniel-levin 4y ago
Neat! This is the direction I’d hoped to see gvisor go in. What’s the reasoning for building from scratch and not piggybacking off gvisor?
- jasonwhite 4y ago
  We certainly looked into gVisor and Firecracker when we started this project a few years ago. These systems use KVM and gVisor in particular uses the Model Specific Registers (MSRs) to intercept system calls before forwarding them to the host kernel. Intercepting syscalls this way has less overhead than ptrace and we would have complete control over the system environment. I think it's a good approach and worth exploring more, but ultimately the deal breaker was that KVM requires root privileges to run and it wouldn't run on our already-virtualized dev machines. We also wanted to allow the guest program to interact with the host's file system. So, we went with good ol' ptrace. Last I checked gVisor also has a ptrace backend, but it wasn't very far along at the time. When going the ptrace route, there is less reason to depend on another project. Another reason of course is that we'd be beholden to a Google project. ;)
  - nn3 4y ago
    > that KVM requires root privileges to run It doesn't. It only requires privileges to access /dev/kvm
    - jasonwhite 4y ago
      Oops, yes, you are correct and it's not too hard to get around that by adding the user to a group that has access. Still, nested virtualization isn't always enabled, which I think limits the number of places we can run.
  - rrnewton 4y ago
    I thought it was very cool how gVisor is multi-backend (their “sentry” implemented vie either ptrace or kvm), which is pretty unusual with instrumentation tools. We could maybe have shared this logic to intercept syscalls and redirect them to user space code serving as the kernel. That is, we could have shared the Reverie layer. We saw ourselves as headed towards an in-guest binary instrumentation model (like rr’s syscall buffer). And so one factor is that Rust is a better fit than Go for injecting code into guest processes. Regarding the actual gVisor user space kernel.. we could have started with that and forked it to start adding determinism features to that kernel. At first glance that would seem to save on implementation work, but “implement futexes deterministically” is a pretty different requirement than “implement futexes”, so it’s not clear how much savings could have been had. We could still have a go at reusing their kvm setup to implement a Reverie backend. But there’s some impedance matching to do across the FFI there, with the Reverie API relying on Rusts async concurrency mode and Tokio. Hopefully we could cleanly manage separate thread pools for the go threads taking syscalls vs the Tokio thread pool hosting Reverie handler tasks. Or maybe it would be possible to reuse their solution without delivering each syscall to Go code.
teknopaul 4y ago
Can you explain how making flakey tests, not flakey, helps find bugs. I would have thought these differences are essentially free fuzzing and desirable?
- jasonwhite 4y ago
  Once we have complete control over the determinism of a test, we can start to play with tweaking the non-deterministic inputs in a controlled way. For example, we can tweak the RNG seed used for thread scheduling to explore schedules that wouldn't normally happen under the Linux scheduler.
- stonemetal12 4y ago
  How do you know if a flakey test has been fixed? A deterministic environment can turn flakey into repeatable failure and then known to be fixed.
  - rrnewton 4y ago
    Well, we don't prove the absence of concurrency bugs -- that would be more a job for formal verification, type systems, at the source level. But we can tell when our `--chaos` stress tests cease to produce crashes in reasonable numbers of runs. And when we do achieve a crash we can use our analysis phase to identify the racing operations. It's both a pro and a con of the approach that we work with real crashes/failures. This means its a less sensitive instrument than tools like TSAN (which can detect data races that never cause a failure in an actual run), but conversely we don't have to worry about false positives, because we can present evidence that a particular order of events definitely causes a failure. Also we catch a much more general category of concurrency bugs (ordering problems between arbitrary instructions/syscalls, even between processes and in multiple languages).
- rrnewton 4y ago
  Sure! I think underpinning your question is a really subtle point there. And I think the answer is in the different purposes of regression testing and bug finding. In regression testing (CI), you're testing if the code introduced new problems. You don't at that point in time really want to know that someone else's test downstream from your component fails when given a new thread schedule that it has not previously seen. Wherease if you're stress testing (including fuzzing and concurrency testing) you probably want to torture the program overnight to see if you can turn up new failures. The Coyote project at Microsoft is a concurrency testing project with some similarities to Hermit. For the reasons above, they say in their docs to use a constant seed for CI regression testing, but use random exploration for bug finding: https://www.microsoft.com/en-us/research/project/coyote/ Still, it does feel like wasted resources to test the same points in the (exponentially large) schedule space again and again. Kind of like some exploration/exploitation tradeoff. We don't do it yet, but I would consider doing a randomized exploration during CI, but making the observable semantics the fixed version. If the randomized one fails, send that over to the "bug finding" component for further study, while quickly retrying with the known-good seed for the CI visible regression test results. I don't think there's one right policy here. But having control over these knobs lets us be intentional about it. P.S. Taking the random schedules the OS gives us is kind of "free fuzzing", but it is very BAD free fuzzing. It over-samples the probable, boring schedules and under-samples the more extreme corner cases. Hence concurrency bugs lurk until the machine is under load in production and edge cases emerge.
srosenberg 4y ago
Great work and thanks for making it OSS! I was familiar with the prior (academic) work and its limitations, specifically TCP/IP. Could you elaborate on how you solved that problem?
- rrnewton 4y ago
  Sure! So it really breaks down into two cases: internal and external networking relative to the container Hermit creates. (1) internal networking If you run a test like `rust/network_hello_world.rs` under Hermit, then the communication between threads is part of the "deterministic bubble" that we're running inside of. When one thread blocks on a network call, the Hermit scheduler takes the thread out of the run pool, and it has to deterministically decide when it is ready to rejoin the run-pool by waking up. The scheduler proceeds in linear turns (labeled "COMMIT" in the logs), and if thread 5 unblocks from a network read at turn 100 in one run, it must unblock at that same point in time in all other runs. Sometimes we use a precise model of the blocking operation (like with futexes) and other times we depend on sending Linux a non-blocking version of the syscall as a way to poll the IO and see if it is ready to complete (given the history of every operation that has committed on turns 1..N-1). (2) external networking This is impossible to determinize, of course. Unless you suck the whole network including both hosts into the deterministic bubble, as the DDOS fork of Linux experimented with in ~2013. That was kind of a negative result IMO because performance was pretty bad, but the paper is here: https://www.dcc.fc.up.pt/~ines/aulas/1314/SDM/papers/DDOS.pdf That's where record-replay comes in. `hermit record` can record network calls, but is in a pretty early state and doesn't support many programs. `hermit run` can just allow networking through and hope for the best, but in the future we plan to add features to record just network calls (and no other syscalls), so that you can mix and match different external-network-responses with different thread schedules. That is, you could "pin" the network responses with network-only recording, and then mess around with other parameters or even modify the program.
theamk 4y ago
missing from blog post: overhead of the system. The full paper provides answer: > IO-intensive software builds have an average overhead of 3.49x, while a compute-bound bioinformatics workflow is under 2%.
- rrnewton 4y ago
  Yep, good point -- should have mentioned it. That's still roughly accurate because Hermit is, today, still ptrace-powered. I'll quote my reply from elsewhere about the WIP high-perf backend: > The `experimental/reverie-sabre` directory in the Reverie repo contains our high performance backend, but it's still work-in-progress. It uses binary instrumentation and in our early experiments is 10X faster than our current backend in the worst case (i.e. strace is >10X faster when rewritten with reverie-sabre and run on a program that does nothing but syscalls). Indeed, releasing a faster drop-in "riptrace" strace replacement is one of the goals ;-).
- yjftsjthsd-h 4y ago
  For what it is, that's really quite good:) I wouldn't run a prod database in it, but for development/testing/debugging 3.5x is completely fine.
wyldfire 4y ago
Some many years ago there was a commercial product called Jinx debugger [1]. I think I only ever got to kick the tires and find out I couldn't get the hypervisor to run on my machine. Good to see Meta making more practical Open Source tools like this (and BOLT). [1] https://en.wikipedia.org/wiki/Jinx_Debugger https://en.wikipedia.org/wiki/Jinx_Debugger
- rrnewton 4y ago
  There’s a bit of shared lineage there. Joseph Devietti and I started working in this area together around 2015. And Joe had worked on the deterministic dOS at UW during his PhD (which led to Jinx). Another related effort is antithesis.com which also seems to use a hypervisor approach rather than Hermits Linux-syscall-API level approach.
mrich 4y ago
Performance is much better than UndoDB I suppose? Are there any sources of nondeterminism UndoDB handles but hermit does not?
- rrnewton 4y ago
  The distinction that we often have trouble getting across is between eliminating/controlling nondeterminism, vs recording what happens to occur. Undo, like rr, and Microsoft TTD, records basically all syscalls, but doesn’t determinize anything in the original execution, only in the replay. A “hermit run” call is like a 0-byte recording —- no nondeterminism so you can “replay” by just running again. On the overhead, the largest factor is the means of program instrumentation. I don’t know where rr sits, but I’ve heard Microsoft’s solution is quite performant on Windows.

167 points by rrnewton 4y ago

I don't know for sure if they use sysemu in ptrace to do this (just that they use ptrace) but here's an awesome blog post that shows how you could build an emulator with just ptrace's sysemu: https://nullprogram.com/blog/2018/06/23/ https://nullprogram.com/blog/2018/06/23/.

jasonwhite 4y ago
I'm the primary author of Reverie[1], the syscall interception framework that Hermit sits on top of. We don't currently use ptrace's SYSEMU, but that's something I'm interested in looking into. Any way we can speed up syscall interception is a win. We currently use seccomp to trap just the syscalls we're interested in. This has the advantage of not even stopping on syscalls we don't care about. Note that we commonly want to inject multiple syscalls per intercepted syscall. I'm not sure how this would work with SYSEMU, but with the seccomp approach we mmap a page at a fixed address into the guest's memory that contains a syscall instruction. Then, we run this instruction instead of the original syscall instruction. Since it is always at a fixed address, we can exclude it from our seccomp filter. This prevents us from intercepting syscalls that we're injecting, getting into an infinite loop. Overall, we only have two ptrace stops: one before the syscall is executed and one after. We have a "tail_inject" optimization that can avoid the second ptrace stop and it results in about a 40% speed up, but in my observations we usually do care about the result of the syscall and must do the second ptrace stop for correctness. Perhaps ptrace's SYSEMU can be combined with seccomp can lead to a speed up, but I just haven't looked into it yet. [1]: https://github.com/facebookexperimental/reverie https://github.com/facebookexperimental/reverie

rrnewton 4y ago

This has been the culmination of several years of work intercepting and sanitizing the Linux system call API. It's now open source.

hoosieree 4y ago
I guess FB poaching you from IU in the middle of teaching your compiler course has a silver lining! Nice to see this being shared with the open source community.
- rrnewton 4y ago
  Ah, at least you were in good hands with Michael Vollmer. Btw, he's now a prof at University of Kent in the UK (http://recurial.com/ http://recurial.com/).
  - hoosieree 4y ago
    So true! Glad to hear Michael is still in teaching.
aseipp 4y ago
Hey Ryan, just wanted to say I hope you're doing great these days! Really glad to see that the work originally done by you and Joe at Cloudseal evolving and becoming more readily available to all of us. I still thought back every once in a while about what y'all were up to. :) Super excited that it's kept on chuggin' and now is something we can all enjoy!

jasonwhite 4y ago

TL;DR: This is a Rust project that forces deterministic execution of arbitrary programs and acts like a reproducible container. That is, it hermetically isolates the program from sources of non-determinism such as time, thread interleavings, random number generation, etc. Guaranteed determinism is a powerful tool and it serves as a basis for a number of applications, including concurrency stress testing, record/replay, reproducible builds, automatic diagnosis of concurrency bugs, and more. I've been on the team working on this project over the past ~2 years. AMA! Here is the GitHub repository: https://github.com/facebookexperimental/hermit https://github.com/facebookexperimental/hermit

CJefferson 4y ago
This looks cool. Personally I'd also be interested in this for academic work -- anything which makes it easier to be sure an experiment can be reproduced later (a week, year, or decade later, in increasing order of difficulty), is good to have.
- rrnewton 4y ago
  Yes, I'm very interested in that as well. I've been involved with the ACM Artifact Evaluation process which has been going on in several conferences for a while. https://www.acm.org/publications/policies/artifact-review-badging https://www.acm.org/publications/policies/artifact-review-ba... But it's been pretty frustrating. As an author, my PLDI 2014 artifact stopped working less than 5 years later (Docker image binary incompatibility). And when I was co-chair of an Artifact Evaluation Committee in 2017, there was not great reproducibilty of the artifacts that were submitted either. If you package a VM (freezing the Linux kernel), and are pretty sure that VM will run in 10 years, PLUS you determinize the execution itself... that should allow durable bitwise reproducibility. Maybe Hermit could be one ingredient of that. For scientific reproducibility, there is a lot of other tooling to build too, and I know some folks have been working in that area: https://ctuning.org/ https://ctuning.org/
rrnewton 4y ago
Note that this is a follow-on project from the earlier Dettrace system, which was applied mainly to reproducible builds (as in the academic paper, https://dl.acm.org/doi/10.1145/3373376.3378519 https://dl.acm.org/doi/10.1145/3373376.3378519, and presented to the Debian Reproducible Builds summit): - https://github.com/dettrace/dettrace https://github.com/dettrace/dettrace And one cool part of it is this Rust program instrumentation layer: - https://github.com/facebookexperimental/reverie https://github.com/facebookexperimental/reverie It's good for building OS-emulator style projects or tracing tools.

alex_suzuki 4y ago

Is it just me or are we experiencing an uptick in high-quality, sophisticated software projects being open-sourced by FAANG companies?

crmd 4y ago
It’s great how much open source infrastructure software has come out of FAANG in the past decade. Between Kubernetes, react, Kafka, etc it’s wild how much of my tech stack is open source software developed by people at large tech companies. It’s also great PR for the companies.
- rrnewton 4y ago
  Heh, I implore you to consider the engineers-eye view. We're tech geeks inside or outside of FAANG, with all the usual incentives. I've been the tech lead on this project for 5 years, through 2 companies, and of course I hope someone finds it useful and chooses to contribute. I'd like to think we could help someone somehow with public relations, but I don't think we can ;-). Actually, I don't think any of the big techs are leaning all that much into recruiting right now though....
  - crmd 4y ago
    Hey, I totally rewrote my comment after reading your response. Thanks for engaging - hearing from the project author made me realize I was acting like a cynical asshole. Congrats on Hermit and thanks for supporting free software.
- Enginerrrd 4y ago
  Facebook/Meta in particular seem to be hitting the front page with nerd-bait research. I suspect it is indeed part of a public relations strategy. And I hate to say it, but it's working on me. I've seen some really cool projects come out of Facebook lately!
School-Cotton 4y ago
Are we? PyTorch, React, etc. have been around for ages.

topazas 4y ago

maybe symbolic execution also can be included here?

rrnewton 4y ago
It's a good question. We would like to make it usable as a platform for dynamic analysis. The idea being that you can control all these external factors (like thread scheduling), find a crashing run, and then ask introspective questions of what the code is doing in a crashing run. In practice, one challenge we have is bridging between the runtime view of the software (as a debugger would see) -- raw machine instructions and system calls, and the static view that you would get from analyzing the source code. Sanitizers, for example (ASAN, TSAN, etc), are typically implemented in the compiler as program instrumenations. If we integrated binary instrumentation tools like Intel Pin or DynamoRio, we could perform additional dynamic analysis, but still at the machine code rather than source code level, which is a big gap from how symbolic execution normally happens, at the source code / AST level.

daniel-levin 4y ago

Neat! This is the direction I’d hoped to see gvisor go in. What’s the reasoning for building from scratch and not piggybacking off gvisor?

jasonwhite 4y ago
We certainly looked into gVisor and Firecracker when we started this project a few years ago. These systems use KVM and gVisor in particular uses the Model Specific Registers (MSRs) to intercept system calls before forwarding them to the host kernel. Intercepting syscalls this way has less overhead than ptrace and we would have complete control over the system environment. I think it's a good approach and worth exploring more, but ultimately the deal breaker was that KVM requires root privileges to run and it wouldn't run on our already-virtualized dev machines. We also wanted to allow the guest program to interact with the host's file system. So, we went with good ol' ptrace. Last I checked gVisor also has a ptrace backend, but it wasn't very far along at the time. When going the ptrace route, there is less reason to depend on another project. Another reason of course is that we'd be beholden to a Google project. ;)
- nn3 4y ago
  > that KVM requires root privileges to run It doesn't. It only requires privileges to access /dev/kvm
  - jasonwhite 4y ago
    Oops, yes, you are correct and it's not too hard to get around that by adding the user to a group that has access. Still, nested virtualization isn't always enabled, which I think limits the number of places we can run.
- rrnewton 4y ago
  I thought it was very cool how gVisor is multi-backend (their “sentry” implemented vie either ptrace or kvm), which is pretty unusual with instrumentation tools. We could maybe have shared this logic to intercept syscalls and redirect them to user space code serving as the kernel. That is, we could have shared the Reverie layer. We saw ourselves as headed towards an in-guest binary instrumentation model (like rr’s syscall buffer). And so one factor is that Rust is a better fit than Go for injecting code into guest processes. Regarding the actual gVisor user space kernel.. we could have started with that and forked it to start adding determinism features to that kernel. At first glance that would seem to save on implementation work, but “implement futexes deterministically” is a pretty different requirement than “implement futexes”, so it’s not clear how much savings could have been had. We could still have a go at reusing their kvm setup to implement a Reverie backend. But there’s some impedance matching to do across the FFI there, with the Reverie API relying on Rusts async concurrency mode and Tokio. Hopefully we could cleanly manage separate thread pools for the go threads taking syscalls vs the Tokio thread pool hosting Reverie handler tasks. Or maybe it would be possible to reuse their solution without delivering each syscall to Go code.

teknopaul 4y ago

Can you explain how making flakey tests, not flakey, helps find bugs. I would have thought these differences are essentially free fuzzing and desirable?

jasonwhite 4y ago
Once we have complete control over the determinism of a test, we can start to play with tweaking the non-deterministic inputs in a controlled way. For example, we can tweak the RNG seed used for thread scheduling to explore schedules that wouldn't normally happen under the Linux scheduler.
stonemetal12 4y ago
How do you know if a flakey test has been fixed? A deterministic environment can turn flakey into repeatable failure and then known to be fixed.
- rrnewton 4y ago
  Well, we don't prove the absence of concurrency bugs -- that would be more a job for formal verification, type systems, at the source level. But we can tell when our `--chaos` stress tests cease to produce crashes in reasonable numbers of runs. And when we do achieve a crash we can use our analysis phase to identify the racing operations. It's both a pro and a con of the approach that we work with real crashes/failures. This means its a less sensitive instrument than tools like TSAN (which can detect data races that never cause a failure in an actual run), but conversely we don't have to worry about false positives, because we can present evidence that a particular order of events definitely causes a failure. Also we catch a much more general category of concurrency bugs (ordering problems between arbitrary instructions/syscalls, even between processes and in multiple languages).
rrnewton 4y ago
Sure! I think underpinning your question is a really subtle point there. And I think the answer is in the different purposes of regression testing and bug finding. In regression testing (CI), you're testing if the code introduced new problems. You don't at that point in time really want to know that someone else's test downstream from your component fails when given a new thread schedule that it has not previously seen. Wherease if you're stress testing (including fuzzing and concurrency testing) you probably want to torture the program overnight to see if you can turn up new failures. The Coyote project at Microsoft is a concurrency testing project with some similarities to Hermit. For the reasons above, they say in their docs to use a constant seed for CI regression testing, but use random exploration for bug finding: https://www.microsoft.com/en-us/research/project/coyote/ Still, it does feel like wasted resources to test the same points in the (exponentially large) schedule space again and again. Kind of like some exploration/exploitation tradeoff. We don't do it yet, but I would consider doing a randomized exploration during CI, but making the observable semantics the fixed version. If the randomized one fails, send that over to the "bug finding" component for further study, while quickly retrying with the known-good seed for the CI visible regression test results. I don't think there's one right policy here. But having control over these knobs lets us be intentional about it. P.S. Taking the random schedules the OS gives us is kind of "free fuzzing", but it is very BAD free fuzzing. It over-samples the probable, boring schedules and under-samples the more extreme corner cases. Hence concurrency bugs lurk until the machine is under load in production and edge cases emerge.

srosenberg 4y ago

Great work and thanks for making it OSS! I was familiar with the prior (academic) work and its limitations, specifically TCP/IP. Could you elaborate on how you solved that problem?

rrnewton 4y ago
Sure! So it really breaks down into two cases: internal and external networking relative to the container Hermit creates. (1) internal networking If you run a test like `rust/network_hello_world.rs` under Hermit, then the communication between threads is part of the "deterministic bubble" that we're running inside of. When one thread blocks on a network call, the Hermit scheduler takes the thread out of the run pool, and it has to deterministically decide when it is ready to rejoin the run-pool by waking up. The scheduler proceeds in linear turns (labeled "COMMIT" in the logs), and if thread 5 unblocks from a network read at turn 100 in one run, it must unblock at that same point in time in all other runs. Sometimes we use a precise model of the blocking operation (like with futexes) and other times we depend on sending Linux a non-blocking version of the syscall as a way to poll the IO and see if it is ready to complete (given the history of every operation that has committed on turns 1..N-1). (2) external networking This is impossible to determinize, of course. Unless you suck the whole network including both hosts into the deterministic bubble, as the DDOS fork of Linux experimented with in ~2013. That was kind of a negative result IMO because performance was pretty bad, but the paper is here: https://www.dcc.fc.up.pt/~ines/aulas/1314/SDM/papers/DDOS.pdf That's where record-replay comes in. `hermit record` can record network calls, but is in a pretty early state and doesn't support many programs. `hermit run` can just allow networking through and hope for the best, but in the future we plan to add features to record just network calls (and no other syscalls), so that you can mix and match different external-network-responses with different thread schedules. That is, you could "pin" the network responses with network-only recording, and then mess around with other parameters or even modify the program.

theamk 4y ago

missing from blog post: overhead of the system. The full paper provides answer: > IO-intensive software builds have an average overhead of 3.49x, while a compute-bound bioinformatics workflow is under 2%.

rrnewton 4y ago
Yep, good point -- should have mentioned it. That's still roughly accurate because Hermit is, today, still ptrace-powered. I'll quote my reply from elsewhere about the WIP high-perf backend: > The `experimental/reverie-sabre` directory in the Reverie repo contains our high performance backend, but it's still work-in-progress. It uses binary instrumentation and in our early experiments is 10X faster than our current backend in the worst case (i.e. strace is >10X faster when rewritten with reverie-sabre and run on a program that does nothing but syscalls). Indeed, releasing a faster drop-in "riptrace" strace replacement is one of the goals ;-).
yjftsjthsd-h 4y ago
For what it is, that's really quite good:) I wouldn't run a prod database in it, but for development/testing/debugging 3.5x is completely fine.

wyldfire 4y ago

Some many years ago there was a commercial product called Jinx debugger [1]. I think I only ever got to kick the tires and find out I couldn't get the hypervisor to run on my machine. Good to see Meta making more practical Open Source tools like this (and BOLT). [1] https://en.wikipedia.org/wiki/Jinx_Debugger https://en.wikipedia.org/wiki/Jinx_Debugger

rrnewton 4y ago
There’s a bit of shared lineage there. Joseph Devietti and I started working in this area together around 2015. And Joe had worked on the deterministic dOS at UW during his PhD (which led to Jinx). Another related effort is antithesis.com which also seems to use a hypervisor approach rather than Hermits Linux-syscall-API level approach.

mrich 4y ago

Performance is much better than UndoDB I suppose? Are there any sources of nondeterminism UndoDB handles but hermit does not?

rrnewton 4y ago
The distinction that we often have trouble getting across is between eliminating/controlling nondeterminism, vs recording what happens to occur. Undo, like rr, and Microsoft TTD, records basically all syscalls, but doesn’t determinize anything in the original execution, only in the replay. A “hermit run” call is like a 0-byte recording —- no nondeterminism so you can “replay” by just running again. On the overhead, the largest factor is the means of program instrumentation. I don’t know where rr sits, but I’ve heard Microsoft’s solution is quite performant on Windows.