prog: support conditional fields

pkg/compiler restructures conditional fields in structures into unions,
so we only have to implement the support for unions.

Semantics is as follows:
If a union has conditions, syzkaller picks the first field whose
condition matches. Since we require the last union field to have no
conditions, we can always construct an object.

Changes from this commit aim at ensuring that the selected union fields
always follow the rule above.

1 files changed, 226 insertions, 0 deletions

diff --git a/prog/expr_test.go b/prog/expr_test.go
new file mode 100644
index 000000000..69bd790db
--- /dev/null
+++ b/prog/expr_test.go
@@ -0,0 +1,226 @@
+// Copyright 2023 syzkaller project authors. All rights reserved.
+// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file.
+
+package prog
+
+import (
+	"bytes"
+	"fmt"
+	"strings"
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+)
+
+func TestGenerateConditionalFields(t *testing.T) {
+	// Ensure that we reach different combinations of conditional fields.
+	target, rs, _ := initRandomTargetTest(t, "test", "64")
+	ct := target.DefaultChoiceTable()
+	r := newRand(target, rs)
+
+	combinations := [][]bool{
+		{false, false},
+		{false, false},
+	}
+	b2i := func(b bool) int {
+		if b {
+			return 1
+		}
+		return 0
+	}
+	for i := 0; i < 150; i++ {
+		p := genConditionalFieldProg(target, ct, r)
+		f1, f2 := parseConditionalStructCall(t, p.Calls[len(p.Calls)-1])
+		combinations[b2i(f1)][b2i(f2)] = true
+	}
+	for _, first := range []int{0, 1} {
+		for _, second := range []int{0, 1} {
+			if !combinations[first][second] {
+				t.Fatalf("Did not generate a combination f1=%v f2=%v", first, second)
+			}
+		}
+	}
+}
+
+func TestMutateConditionalFields(t *testing.T) {
+	target, rs, _ := initRandomTargetTest(t, "test", "64")
+	ct := target.DefaultChoiceTable()
+	r := newRand(target, rs)
+	iters := 500
+	if testing.Short() {
+		iters /= 10
+	}
+	nonAny := 0
+	for i := 0; i < iters; i++ {
+		prog := genConditionalFieldProg(target, ct, r)
+		for j := 0; j < 5; j++ {
+			prog.Mutate(rs, 10, ct, nil, nil)
+			hasAny := bytes.Contains(prog.Serialize(), []byte("ANY="))
+			if hasAny {
+				// No sense to verify these.
+				break
+			}
+			nonAny++
+			validateConditionalProg(t, prog)
+		}
+	}
+	assert.Greater(t, nonAny, 10) // Just in case.
+}
+
+func TestEvaluateConditionalFields(t *testing.T) {
+	target := InitTargetTest(t, "test", "64")
+	tests := []struct {
+		good []string
+		bad  []string
+	}{
+		{
+			good: []string{
+				`test$conditional_struct(&AUTO={0x0, @void, @void})`,
+				`test$conditional_struct(&AUTO={0x4, @void, @value=0x123})`,
+				`test$conditional_struct(&AUTO={0x6, @value={AUTO}, @value=0x123})`,
+			},
+			bad: []string{
+				`test$conditional_struct(&AUTO={0x0, @void, @value=0x123})`,
+				`test$conditional_struct(&AUTO={0x0, @value={AUTO}, @value=0x123})`,
+			},
+		},
+		{
+			good: []string{
+				`test$parent_conditions(&AUTO={0x0, @without_flag1=0x123, {0x0, @void}})`,
+				`test$parent_conditions(&AUTO={0x2, @with_flag1=0x123, {0x0, @void}})`,
+				`test$parent_conditions(&AUTO={0x4, @without_flag1=0x123, {0x0, @value=0x0}})`,
+				`test$parent_conditions(&AUTO={0x6, @with_flag1=0x123, {0x0, @value=0x0}})`,
+			},
+			bad: []string{
+				`test$parent_conditions(&AUTO={0x0, @with_flag1=0x123, {0x0, @void}})`,
+				`test$parent_conditions(&AUTO={0x2, @without_flag1=0x123, {0x0, @void}})`,
+				`test$parent_conditions(&AUTO={0x4, @with_flag1=0x123, {0x0, @void}})`,
+				`test$parent_conditions(&AUTO={0x4, @with_flag1=0x123, {0x0, @value=0x0}})`,
+			},
+		},
+	}
+
+	for i, test := range tests {
+		t.Run(fmt.Sprintf("%d", i), func(tt *testing.T) {
+			for _, good := range test.good {
+				_, err := target.Deserialize([]byte(good), Strict)
+				assert.NoError(tt, err)
+			}
+			for _, bad := range test.bad {
+				_, err := target.Deserialize([]byte(bad), Strict)
+				assert.ErrorIs(tt, err, ErrViolatedConditions)
+			}
+		})
+	}
+}
+
+func TestConditionalMinimize(t *testing.T) {
+	tests := []struct {
+		input  string
+		pred   func(*Prog, int) bool
+		output string
+	}{
+		{
+			input: `test$conditional_struct(&AUTO={0x6, @value={AUTO}, @value=0x123})`,
+			pred: func(p *Prog, _ int) bool {
+				return len(p.Calls) == 1 && p.Calls[0].Meta.Name == `test$conditional_struct`
+			},
+			output: `test$conditional_struct(0x0)`,
+		},
+		{
+			input: `test$conditional_struct(&(0x7f0000000040)={0x6, @value, @value=0x123})`,
+			pred: func(p *Prog, _ int) bool {
+				return bytes.Contains(p.Serialize(), []byte("0x123"))
+			},
+			// We don't drop individual bits from integers, so there's no chance
+			// to turn 0x6 into 0x4.
+			output: `test$conditional_struct(&(0x7f0000000040)={0x6, @value, @value=0x123})`,
+		},
+		{
+			input: `test$conditional_struct_minimize(&(0x7f0000000040)={0x1, @value=0xaa, 0x1, @value=0xbb})`,
+			pred: func(p *Prog, _ int) bool {
+				return bytes.Contains(p.Serialize(), []byte("0xaa"))
+			},
+			output: `test$conditional_struct_minimize(&(0x7f0000000040)={0x1, @value=0xaa})`,
+		},
+		{
+			input: `test$conditional_struct_minimize(&(0x7f0000000040)={0x1, @value=0xaa, 0x1, @value=0xbb})`,
+			pred: func(p *Prog, _ int) bool {
+				return bytes.Contains(p.Serialize(), []byte("0xbb"))
+			},
+			output: `test$conditional_struct_minimize(&(0x7f0000000040)={0x0, @void, 0x1, @value=0xbb})`,
+		},
+		{
+			input: `test$conditional_struct_minimize(&(0x7f0000000040)={0x1, @value=0xaa, 0x1, @value=0xbb})`,
+			pred: func(p *Prog, _ int) bool {
+				serialized := p.Serialize()
+				return bytes.Contains(serialized, []byte("0xaa")) &&
+					bytes.Contains(serialized, []byte("0xbb"))
+			},
+			output: `test$conditional_struct_minimize(&(0x7f0000000040)={0x1, @value=0xaa, 0x1, @value=0xbb})`,
+		},
+	}
+
+	for i, test := range tests {
+		t.Run(fmt.Sprintf("%d", i), func(tt *testing.T) {
+			target, err := GetTarget("test", "64")
+			assert.NoError(tt, err)
+			p, err := target.Deserialize([]byte(test.input), Strict)
+			assert.NoError(tt, err)
+			p1, _ := Minimize(p, 0, false, test.pred)
+			res := p1.Serialize()
+			assert.Equal(tt, test.output, strings.TrimSpace(string(res)))
+		})
+	}
+}
+
+func genConditionalFieldProg(target *Target, ct *ChoiceTable, r *randGen) *Prog {
+	s := newState(target, ct, nil)
+	calls := r.generateParticularCall(s, target.SyscallMap["test$conditional_struct"])
+	return &Prog{
+		Target: target,
+		Calls:  calls,
+	}
+}
+
+const FLAG1 = 2
+const FLAG2 = 4
+
+func validateConditionalProg(t *testing.T, p *Prog) {
+	for _, call := range p.Calls {
+		if call.Meta.Name == "test$conditional_struct" {
+			parseConditionalStructCall(t, call)
+		}
+	}
+}
+
+// Validates a test$conditional_struct call.
+func parseConditionalStructCall(t *testing.T, c *Call) (bool, bool) {
+	if c.Meta.Name != "test$conditional_struct" {
+		t.Fatalf("generated wrong call %v", c.Meta.Name)
+	}
+	if len(c.Args) != 1 {
+		t.Fatalf("generated wrong number of args %v", len(c.Args))
+	}
+	va, ok := c.Args[0].(*PointerArg)
+	if !ok {
+		t.Fatalf("expected PointerArg: %v", c.Args[0])
+	}
+	if va.Res == nil {
+		// Cannot validate.
+		return false, false
+	}
+	ga, ok := va.Res.(*GroupArg)
+	if !ok {
+		t.Fatalf("expected GroupArg: %v", va.Res)
+	}
+	if len(ga.Inner) != 3 {
+		t.Fatalf("wrong number of struct args %v", len(ga.Inner))
+	}
+	mask := ga.Inner[0].(*ConstArg).Val
+	f1 := ga.Inner[1].(*UnionArg).Index == 0
+	f2 := ga.Inner[2].(*UnionArg).Index == 0
+	assert.Equal(t, mask&FLAG1 != 0, f1, "flag1 must only be set if mask&FLAG1")
+	assert.Equal(t, mask&FLAG2 != 0, f2, "flag2 must only be set if mask&FLAG2")
+	return f1, f2
+}