Two recent bug examples: https://lore.kernel.org/netdev/20200908104025.4009085-1-edumazet@google.com/ https://lore.kernel.org/netdev/20200908145911.4090480-1-edumazet@google.com/ In both cases the race window is extremely narrow. And I suspect in the first case it's not just the race window, but also the typical scheduling of events is such that the UAF won't happen. Namely here: - ieee802154_xmit_complete(&local->hw, skb, false); - dev->stats.tx_packets++; dev->stats.tx_bytes += skb->len; + ieee802154_xmit_complete(&local->hw, skb, false); + The dev is _usually_ not freed by the call to ieee802154_xmit_complete. But the bug is very straightforward (we literally free the object and use it after that) and was introduced and unnoticed since 2014(!). The other one was present in WireGuard initial implementation and was not noticed since then as well. There are sure way more examples like this -- most of the bugs that happen few times and don't have reproducers. The proposal is to introduce artificial random delays into execution and/or some atypical scheduler perturbations. There are some sound approaches for systematic enumeration of all possible executions (or specific subsets of executions), but that's probably not feasible for kernel. Just some random (maybe somewhat intelligently random) perturbations should be good enough for starters. For race-free programs it's enough to introduce delays only before synchronization actions (atomic/lock operations). Any delays between local actions can't lead to observable behavior differences. Now the kernel is not race-free, so it does not have this nice properly. But we probably still want to start with introducing delays only before synchronizations actions, that's still a good oracle. We already have some instrumentation hooks in atomic ops. Not sure about locks (maybe something like might_sleep() will do?). This should be useful for any automated/manual testing/fuzzing. The proposed name: KSHAKER.
We had discussed a potential implementation, specifically "NMI injection" as the means to inject such delays. It's summarized here: https://github.com/google/syzkaller/issues/1891 Having an interface from userspace to inject NMIs that simply add a delay would enable e.g. syzkaller to generate programs that include such injected delays. There may be alternative designs as you propose as well, but using NMIs gives us arbitrary delay-injection points.
Right. I am not sure it's possible to inject NMIs anywhere besides qemu/kvm and special dev boards (i.e. not syzbot). But even there it's controlled from outside of the machine, while we want to control this from inside. Even if we expose a special kernel interface inside of the machine, it won't be possible to achieve right granularity. E.g. on a machine with 1 CPU, user-space can't issue the request until the executing kernel code will be preempted for other reasons at an uncontrolable point. And at this point it's already too late to preempt it, it's already preempted. Having this in kernel in cooperative way seems to provide much better portability, precision and effectiveness.
Another idea: if the places we would be interested in inserting delays are limited we could use kprobes.
I think we one type of systematic testing is feasible as well. Namely, one-factor enumeration like we do for fault injection: delay first point in a syscall, then second, then 3rd and so on until we enumerate all of them. This will require some debugfs interface to arm this per-task and query if the delay was injected or not.
Could these UAFs be detected by KCSAN? Maybe we could bundle the two, as KCSAN already instruments the code?
> Could these UAFs be detected by KCSAN? KCSAN already instruments kfree() and will detect races between usage and kfree(). But we know that KASAN is still the better tool to detect UAFs, due to quarantine etc. > Maybe we could bundle the two, as KCSAN already instruments the code? KCSAN instruments memory accesses, and I think that's overkill/too fine-grained. From what I gather, we want to insert delays into strategic locations, such as synchronization or special functions, to enumerate interesting schedules. This will require (as suggested by Dmitry) a cooperative approach, inserting delay functions either directly or via means of kprobes etc. The other requirement seems to be, that we want something that could be applied to all sanitizers, not just KCSAN. On a whole, one direction I'm being reminded of is stateless model checking, which can be applied to real code to perturb schedules in a systematic way. One popular paper I'm aware of is the CHESS paper: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/pldi08-FairStatelessModelChecking.pdf