syzlang: add conditional fields

[a-nogikh]

trafficstars

In networking descriptions, it is often the case that some field is present only when the corresponding flag is set (in some cases even some special combination of field values is required).

Right now it seems that unions are the only way to describe this. With some clever use of templates, this approach can scale up to a handful of such fields, but it is really hard to extend beyond that.

For example, in radiotap headers there are 29 field types. Each of these fields is only present when the corresponding bit in a special bitmap is set. With 29 fields, it will take a lot of extra structures to describe this with syzlang. Below is an example for just 4 radiotap fields.

type append[A, B] {
	field_a		A
	field_b		B
} [packed]

type radiotap_bitmap[TSFT, FLAGS, RATE, CHANNEL] {
	tsft_bit	const[TSFT, int32:1]
	flags_bit	const[FLAGS, int32:1]
	rate_bit	const[RATE, int32:1]
	channel_bit	const[CHANNEL, int32:1]
	rest		const[0, int32:28]
} [packed]

type radiotap_append_channel [
	with_channel	append[radiotap_append_rate[1], channel_field]
	without_channel	radiotap_append_rate[0]
] [varlen, packed]

type radiotap_append_rate[CHANNEL] [
	with_rate	append[radiotap_append_flags[1, CHANNEL], rate_field]
	without_rate	radiotap_append_flags[0, CHANNEL]
] [varlen, packed]

type radiotap_append_flags[RATE, CHANNEL] [
	with_flags	append[radiotap_append_tsft[1, RATE, CHANNEL], flags_field]
	without_flags	adiotap_append_tsft[0, RATE, CHANNEL]
] [varlen, packed]

type radiotap_append_tsft[FLAGS, RATE, CHANNEL] [
	with_tsft	append[radiotap_bitmap[1, FLAGS, RATE, CHANNEL], flags_tsft]
	without_tsft	radiotap_bitmap[0, FLAGS, RATE, CHANNEL]
] [varlen, packed]

type radiotap_bitmap_body radiotap_append_channel

radiotap {
	it_version	const[0, int8]
	it_pad		const[0, int8]
	it_len		len[parent, int16]
	bitmap_body	radiotap_bitmap_body
} [packed]

It all could be greatly simplified if there was an ability to specify a condition for each attribute to be present. The example above could look like this

radiotap_flags = IEEE80211_RADIOTAP_TSFT, IEEE80211_RADIOTAP_FLAGS, IEEE80211_RADIOTAP_RATE, IEEE80211_RADIOTAP_CHANNEL

radiotap {
	it_version	const[0, int8]
	it_pad		const[0, int8]
	it_len		len[parent, int16]
	it_present	flags[radiotap_flags, int32]
	tsft		tsft_field	(if IEEE80211_RADIOTAP_TSFT in it_present)
	flags		flags_field	(if IEEE80211_RADIOTAP_FLAGS in it_present)
	rate		rate_field	(if IEEE80211_RADIOTAP_RATE in it_present)
	channel		channel_field	(if IEEE80211_RADIOTAP_CHANNEL in it_present)
} [packed]

I think most use cases can be covered without full expression evaluation - it should be enough to be able to check if a flag is present and to compare a field with a const value.

[dvyukov]

Interesting. For such proposals it always help to have move places where this can be used. 1-3 places vs "many" leads to very different trade offs. And we will need the list if/when we actually add this feature. Do you know more potential use places?

I think the syntax should support at least == and !=. Maybe (if it_present & IEEE80211_RADIOTAP_TSFT)? There is actually an issue for expression evaluation (#2164), which may be useful in some other contexts as well.

On implementation level one interesting possibility is to make majority of processing (generation/mutation/serialization) ignore the if attribute and then only make encodingexec procedure skip the fields if necessary. This way it may have pretty minimal code footprint.

[pchaigno]

For such proposals it always help to have move places where this can be used. 1-3 places vs "many" leads to very different trade offs. And we will need the list if/when we actually add this feature. Do you know more potential use places?

As discussed in https://github.com/google/syzkaller/issues/4191, id_or_fd from the BPF description is one example. Ideally, we'd like to change the type of relative_obj from id_or_fd to a more specific type based on conditions such as (if flags & BPF_F_ID & BPF_F_LINK) or (if !(flags & BPF_F_LINK)).

Another example in BPF is program loading, where we'd want to restrict the set of possible flags based on the program type. So the condition would be on bpf_prog_t.flags and bpf_prog_t.expected_attach_type with something like (if type == BPF_PROG_TYPE_XDP).

Yet another BPF example is for 128-bits loading instructions, where we might want to condition the type of imm based on the value of src.

[a-nogikh]

The comment is WIP

What needs to be taken care of:

In general

• Do/will we need it for unions as well?
• Just curious: if we add conditions on the struct direction (DirIn/DirOut), will it help somewhere?
• The fields on which conditional expressions depend:
  • Must be integers.
  • Cannot be conditional fields themselves.
  • Must always be DirIn (i.e. set by syzkaller).
    • This one is harder to enforce than the rest, maybe in some later PR.
• What if len/bytesize references a conditional field?

Generation

• The conditional field may contain an output resource.
  • Don't generate it via resource constructors for now?

Mutation

• Only mutate fields that will actually be included in the program.
• What do we do with the fields the conditional expressions depend on?
  • Don't mutate them for now and don't substitute hints there?
  • Mutate them, but then just discard no longer needed fields and generate some random value for the newly appeared ones?
• Ensure that size[N] and align[N] attributes always stay satisfied.

Syzlang

For start, we can limit ourselves to ==, != and &.

mask_flags = CONST_0, CONST_1, CONST_2
A {
 mask    int32[mask_flags]
 f0      int32 (if[value[mask] == CONST_0])
 f1      int32 (if[value[mask] != CONST_1]) 
 f2      int32 (if[value[mask] & CONST_2])
 f3      int32 (if[value[mask] & CONST_2 == 0) 
}

Syzlang programs

• How do we print such programs in prog/encoding.go?
  • Looks like we can just use nil.