From 31179bc75602cbe8f0421b44f19ff1b960039644 Mon Sep 17 00:00:00 2001 From: Aleksandr Nogikh Date: Thu, 28 Dec 2023 21:31:00 +0100 Subject: 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. --- prog/expr_test.go | 226 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 226 insertions(+) create mode 100644 prog/expr_test.go (limited to 'prog/expr_test.go') 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 +} -- cgit mrf-deployment