sys/linux: automatic syscall interface extraction

[dvyukov]

This topic pops up periodically. Filing this as tracking bug.

We could use clang static analysis capabilities, or Coccinelle or Smatch. See also difuze which already does something similar using llvm bitcode. And also IMF: Inferred Model-based Fuzzer.
We probably should stick with clang.

Staged implementation plan should probably be:

1. Start with a tool that is given a header file and generates skeleton of syzkaller descriptions from it (structs with fields, enums as flags).

2. Extend the tool to read in existing description file and parse corresponding kernel headers and produce warnings about possible mismatches. E.g. descriptions have struct foo with 2 fields, but kernel headers have struct foo with 3 fields (or field sizes/alignment mismatch).

3. Locate all kernel interfaces (file_operations, sockets, netlink, filesystems, etc).

At this point we have 3 useful functionalities and some infrastructure code to parse kernel headers, extract some info from them and generate syzkaller descriptions from it. Then we can attack:

4. Automatically extract descriptions. Probably starting from some simple common cases.

5. Iterate on 4 to extract more descriptions and of higher quality.

6. A related functionality that may be easy to build on top is collecting set of functions reachable from syscalls. This would be useful to provide meaningful % of covered code in coverage reports. There are lots of functions that are not reachable from syscalls at all (interrupts, soft interrupts, init functions, rcu/timer callbacks, background threads, etc). If we calculate coverage % based on all code, the number will be too pessimistic and not meaningful and it won't be possible to get close to 100%. If we take only reachable functions as the base, then the % must be much more meaningful and optimistic.

Important aspects for interface auto-generation:

• How will manual and automatic descriptions co-exist? Most likely automated descriptions won't be on par for all subsystems. I can imagine for some subsystems we will use complete generated ones, for some - completely manual (here verification becomes critical), and for some partially manual/partially automated (how that will look like?)
• Automated descriptions readability and fixability. Lots of automated descriptions that I saw are unreadable mess. When you start digging they turn out to be bad in some way, but discovering that is extremely hard, it should be easy (e.g. literal constant names). And then there should be some way to fix up problems in automated descriptions.
• Merging descriptions for multiple arches.

For linux the main interfaces are:

1. syscalls, marked with SYSCALL_DEFINE macros, e.g.:

SYSCALL_DEFINE1(fdatasync, unsigned int, fd)

2. File operations, marked with struct file_operations, e.g.:

static const struct file_operations timerfd_fops = {
	.release	= timerfd_release,
	.poll		= timerfd_poll,
	.read		= timerfd_read,
	.llseek		= noop_llseek,
	.show_fdinfo	= timerfd_show,
	.unlocked_ioctl	= timerfd_ioctl,
};

There can be associated with anon files returned by syscalls (timer_fd), or mounted to devfs, procfs, binfmt_misc and other special file systems.

3. Socket operations. Denoted by struct proto_ops, e.g.:

static const struct proto_ops caif_seqpacket_ops = {
	.family = PF_CAIF,
	.owner = THIS_MODULE,
	.release = caif_release,
	.bind = sock_no_bind,
	.connect = caif_connect,
	.socketpair = sock_no_socketpair,
	.accept = sock_no_accept,
	.getname = sock_no_getname,
	.poll = caif_poll,
	.ioctl = sock_no_ioctl,
	.listen = sock_no_listen,
	.shutdown = sock_no_shutdown,
	.setsockopt = setsockopt,
	.getsockopt = sock_no_getsockopt,
	.sendmsg = caif_seqpkt_sendmsg,
	.recvmsg = caif_seqpkt_recvmsg,
	.mmap = sock_no_mmap,
	.sendpage = sock_no_sendpage,
};

Each set of operations is also associated with a specific socket family/type/protocol. In particular we need to understand sockaddr type used for this socket in connect/bind/sendto/etc.

4. As a special case, ioctl's and set/getsockopt's. These hang off file_operations and proto_ops. These usually contain a switch on commands and we need the switch cases and argument types.

5. File systems, denoted by struct file_system_type, e.g.:

static struct file_system_type bm_fs_type = {
	.owner		= THIS_MODULE,
	.name		= "binfmt_misc",
	.mount		= bm_mount,
	.kill_sb	= kill_litter_super,
};

Each file system has set of options that is useful to understand, some require an image in particular format.

6. Netlink, usually denoted by struct nla_policy, e.g.:

static const struct nla_policy cgw_policy[CGW_MAX+1] = {
	[CGW_MOD_AND]	= { .len = sizeof(struct cgw_frame_mod) },
	[CGW_MOD_OR]	= { .len = sizeof(struct cgw_frame_mod) },
	[CGW_MOD_XOR]	= { .len = sizeof(struct cgw_frame_mod) },
	[CGW_MOD_SET]	= { .len = sizeof(struct cgw_frame_mod) },
	[CGW_CS_XOR]	= { .len = sizeof(struct cgw_csum_xor) },
	[CGW_CS_CRC8]	= { .len = sizeof(struct cgw_csum_crc8) },
	[CGW_SRC_IF]	= { .type = NLA_U32 },
	[CGW_DST_IF]	= { .type = NLA_U32 },
	[CGW_FILTER]	= { .len = sizeof(struct can_filter) },
	[CGW_LIM_HOPS]	= { .type = NLA_U8 },
	[CGW_MOD_UID]	= { .type = NLA_U32 },
};

But some messages may also have no policy. There are 3 main levels that I know of: netlink as-is, rtnl, genetlink. All are useful to support.

7. Netfilter, denoted by struct xt_target and struct xt_match, e.g.:

static struct xt_match xt_osf_match = {
	.name 		= "osf",
	.revision	= 0,
	.family		= NFPROTO_IPV4,
	.proto		= IPPROTO_TCP,
	.hooks      	= (1 << NF_INET_LOCAL_IN) |
				(1 << NF_INET_PRE_ROUTING) |
				(1 << NF_INET_FORWARD),
	.match 		= xt_osf_match_packet,
	.matchsize	= sizeof(struct xt_osf_info),
	.me		= THIS_MODULE,
};

One potential improvement: detect unused/reserved/padding fields (esp in structs, but may be direct syscall args too). These either appear unused in code, or only checked against 0 (to ensure reserved fields have 0 values). We should use const[0] in descriptions for these. Need to be careful to not confuse them with "bool" flags that are also only compared with 0.

[mspecter]

The Android Security research team is really interested in getting this feature off the ground. I'm going to start hacking on a tool that starts doing some of this using clang (so as to avoid dependence on other projects).

In particular, we're going to start with # 1 as outlined above, specifically targeting Android source as a starting target, but attempt to build-in flexibility later for adding other operating systems. This particularly impacts target # 3 above, since how file operations, sockets, ioctls, etc are all done are definitely going to depend heavily on the OS.

[dvyukov]

@mspecter This is great!
Maybe a bit late to point out, but we have this rough prototype:
https://github.com/google/syzkaller/blob/master/tools/syz-declextract/syz-declextract.cpp
If you did something with clang before, then it's probably of no use. But otherwise can be used to get things rolling.

Yes, it would be nice to separate common code and linux-specific code form day one. Ideally, OS-specific info is provided as some set of declarative rules. Whole syzkaller used to be heavily linux-specific throughout, and then it was painful to de-linuxify the codebase.

[dvyukov]

As soon as you have something that converts a C struct to a basic syzkaller form, we can start merging.

I think it's important to figure out and agree on user interfaces (how it will look for end users).

For step 1, I am thinking about something along the lines of:

syz-something -sourcedir=/path/to/linux/checkout -header=include/linux/fs/.h -includes=comma-separated-list-of-other-headers-to-include

and this will print syzkaller descriptions from the header to stdout.
We will need -includes flag because lots of kernel headers are not self-contained and require including other headers before they can be parsed.
Any other options?

For step 2, ultimately I would like to run:

make declcheck TARGETOS=linux SOURCEDIR=/path/to/linux/checkout

and that will print set of warnings (we will figure out some story for false positive warnings).

[dvyukov]

Another high-level question is how to split code between C++ and Go.
I would prefer that we have most of the logic in Go because we already have machinery to work with syzkaller descriptions in Go, it's much easier to test, it does not depend on clang sources and Go is type-safe and memory-safe language.
We can either have a C++ clang tool that merely produces syzkaller descriptions and then handle the rest in Go by invoking the native tool and parsing it's output; or use Go clang bindings (e.g. https://github.com/go-clang/bootstrap). However, it's unclear how stable and easy-to-use they are and if it will cause more pain in the long run then just writing a native tool.

[mspecter]

Re: code split between Go and C++, I'd love some guidance.

The way I was considering doing this was by writing a clangtool (much like the prototype you linked) to walk the AST since I generally don't trust the Go clang bindings, then leverage the code you already have in pkg/ast/ast.go and pkg/ast/format.go, along with a few Go->C++ bindings to actually create nodes and serialize them out; doing something like an AST->AST conversion.

This has the benefit of relying less on a secondary generator of syzkaller syntax. So, if the project decides to add tokens or change what a token means, this part won't have to be modified as well. The downside appears to be a not-insignificant amount of added complexity. Thoughts?

[mspecter]

Also, I completely agree on the user interface, all of that makes sense. ^_^

[dvyukov]

along with a few Go->C++ bindings to actually create nodes and serialize them out; doing something like an AST->AST conversion.

Do you want to call Go from C++, or C++ from Go? It's possible but writing bindings can be painful, also it will be harder to build and test. The pure Go part will build and run trivially an can be tested, so the idea was to localize dependencies on clang to as small binary as possible (not sure if we will be able to tests it on travis CI).
So I was thinking of writing a minimal clangtool that spews syzkaller descriptions (by just printf'ing them, printing is much easier than parsing). And hen have a Go program that parses output with pkg/ast, does transformations, compiles them, formats etc.
However, it seems that the main smartness should happen before clangtool writes descriptions, because otherwise all auxiliary semantic information and relations between things will be lost (can't be represented in syzkaller descriptions). And if clangtool will do all of the hard work, then it's unclear what transformation we still can do on the Go side.
Another option would be for the clangtool to produce raw syzkaller descriptions and some additional auxiliary semantic information and relations in a separate file (say json), and then Go tool will parse both and do some transformations and refining on the descriptions.
But it's hard for me to judge what will work better without knowing what exactly auxiliary information we will have and how complex it is and how complex is post-processing of descriptions.

[dvyukov]

I've added descriptions of 7 main Linux kernel interfaces that I know of:
#590 (comment)
Anything else I am missing?
@mspecter

[mspecter]

I can't currently think of anything you're missing, and that list is incredibly helpful, thanks!

[dvyukov]

A related functionality that may be easy to build on top is collecting set of functions reachable from syscalls. This would be useful to provide meaningful % of covered code in coverage reports. There are lots of functions that are not reachable from syscalls at all (interrupts, soft interrupts, init functions, rcu/timer callbacks, background threads, etc). If we calculate coverage % based on all code, the number will be too pessimistic and not meaningful and it won't be possible to get close to 100%. If we take only reachable functions as the base, then the % must be much more meaningful and optimistic.
But we also need to figure out how to integrate this analysis into coverage reports (reports are generated online).

[dvyukov]

One thing that may be useful and possible with smarter code analysis: detecting unused/reserved/padding fields (esp in structs, but may be direct syscall args too). These either appear unused in code, or only checked against 0. We should use const[0] in descriptions for these.

[dvyukov]

FTR here is an interface extraction utility for NetBSD, can extract ioctl definitions:
https://github.com/ais2397/sys2syz

[dvyukov]

For fuchsia there is fidlgen: https://fuchsia.googlesource.com/fuchsia/+/4ad0d5717d65/tools/fidl/fidlgen_syzkaller/main.go

[dvyukov]

For netlink we could consider extracting info from ynl project once it's merged upstream:
https://github.com/kuba-moo/ynl/blob/main/Documentation/netlink/specs/fou.yaml
It contains machine-readable descriptions of netlink protocols.
However, it needs to cover more protocols and needs to be extended with semantic info for attributes (ip addr, ifindex, fd, device name, etc).

[dvyukov]

FTR another paper on automatic interface extraction:
KSG: Augmenting Kernel Fuzzing with System Call Specification Generation

[izzeem]

https://github.com/seclab-ucr/SyzDescribe another paper which claims to be better than KSG

[dvyukov]

One interesting addition to this is analysis of what interfaces are reachable on with different privileges (non-privileged, requires userns, root-only). This info can also be crossed with coverage reports to see e.g. what unpriv interfaces are not covered.