1// Copyright 2015 syzkaller project authors. All rights reserved.
2// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file.
3
4package prog
5
6import (
7	"bytes"
8	"fmt"
9	"math/rand"
10	"sync"
11	"testing"
12)
13
14func TestClone(t *testing.T) {
15	target, rs, iters := initTest(t)
16	for i := 0; i < iters; i++ {
17		p := target.Generate(rs, 10, nil)
18		p1 := p.Clone()
19		data := p.Serialize()
20		data1 := p1.Serialize()
21		if !bytes.Equal(data, data1) {
22			t.Fatalf("program changed after clone\noriginal:\n%s\n\nnew:\n%s\n", data, data1)
23		}
24	}
25}
26
27func TestMutateRandom(t *testing.T) {
28	testEachTargetRandom(t, func(t *testing.T, target *Target, rs rand.Source, iters int) {
29	next:
30		for i := 0; i < iters; i++ {
31			p := target.Generate(rs, 10, nil)
32			data0 := p.Serialize()
33			p1 := p.Clone()
34			// There is a chance that mutation will produce the same program.
35			// So we check that at least 1 out of 20 mutations actually change the program.
36			for try := 0; try < 20; try++ {
37				p1.Mutate(rs, 10, nil, nil)
38				data := p.Serialize()
39				if !bytes.Equal(data0, data) {
40					t.Fatalf("program changed after mutate\noriginal:\n%s\n\nnew:\n%s\n",
41						data0, data)
42				}
43				data1 := p1.Serialize()
44				if bytes.Equal(data, data1) {
45					continue
46				}
47				if _, err := target.Deserialize(data1); err != nil {
48					t.Fatalf("Deserialize failed after Mutate: %v\n%s", err, data1)
49				}
50				continue next
51			}
52			t.Fatalf("mutation does not change program:\n%s", data0)
53		}
54	})
55}
56
57func TestMutateCorpus(t *testing.T) {
58	target, rs, iters := initTest(t)
59	var corpus []*Prog
60	for i := 0; i < 100; i++ {
61		p := target.Generate(rs, 10, nil)
62		corpus = append(corpus, p)
63	}
64	for i := 0; i < iters; i++ {
65		p1 := target.Generate(rs, 10, nil)
66		p1.Mutate(rs, 10, nil, corpus)
67	}
68}
69
70func TestMutateTable(t *testing.T) {
71	target := initTargetTest(t, "test", "64")
72	tests := [][2]string{
73		// Insert a call.
74		{`
75mutate0()
76mutate2()
77`, `
78mutate0()
79mutate1()
80mutate2()
81`},
82		// Remove calls and update args.
83		{`
84r0 = mutate5(&(0x7f0000000000)="2e2f66696c653000", 0x0)
85mutate0()
86mutate6(r0, &(0x7f0000000000)="00", 0x1)
87mutate1()
88`, `
89mutate0()
90mutate6(0xffffffffffffffff, &(0x7f0000000000)="00", 0x1)
91mutate1()
92`},
93		// Mutate flags.
94		{`
95r0 = mutate5(&(0x7f0000000000)="2e2f66696c653000", 0x0)
96mutate0()
97mutate6(r0, &(0x7f0000000000)="00", 0x1)
98mutate1()
99`, `
100r0 = mutate5(&(0x7f0000000000)="2e2f66696c653000", 0xcdcdcdcdcdcdcdcd)
101mutate0()
102mutate6(r0, &(0x7f0000000000)="00", 0x1)
103mutate1()
104`},
105		// Mutate data (delete byte and update size).
106		{`
107mutate4(&(0x7f0000000000)="11223344", 0x4)
108`, `
109mutate4(&(0x7f0000000000)="112244", 0x3)
110`},
111		// Mutate data (insert byte and update size).
112		// TODO: this is not working, because Mutate constantly tends
113		// update addresses and insert mmap's.
114		/*
115					{`
116			mutate4(&(0x7f0000000000)="1122", 0x2)
117			`, `
118			mutate4(&(0x7f0000000000)="112200", 0x3)
119			`},
120		*/
121		// Mutate data (change byte).
122		{`
123mutate4(&(0x7f0000000000)="1122", 0x2)
124`, `
125mutate4(&(0x7f0000000000)="1100", 0x2)
126`},
127		// Change filename.
128		{`
129mutate5(&(0x7f0000001000)="2e2f66696c653000", 0x22c0)
130mutate5(&(0x7f0000001000)="2e2f66696c653000", 0x22c0)
131`, `
132mutate5(&(0x7f0000001000)="2e2f66696c653000", 0x22c0)
133mutate5(&(0x7f0000001000)="2e2f66696c653100", 0x22c0)
134`},
135		// Extend an array.
136		{`
137mutate3(&(0x7f0000000000)=[0x1, 0x1], 0x2)
138`, `
139mutate3(&(0x7f0000000000)=[0x1, 0x1, 0x1], 0x3)
140`},
141		// Mutate size from it's natural value.
142		{`
143mutate7(&(0x7f0000000000)='123', 0x3)
144`, `
145mutate7(&(0x7f0000000000)='123', 0x2)
146`},
147		// Mutate proc to the special value.
148		{`
149mutate8(0x2)
150`, `
151mutate8(0xffffffffffffffff)
152`},
153	}
154	for ti, test := range tests {
155		test := test
156		t.Run(fmt.Sprint(ti), func(t *testing.T) {
157			t.Parallel()
158			p, err := target.Deserialize([]byte(test[0]))
159			if err != nil {
160				t.Fatalf("failed to deserialize original program: %v", err)
161			}
162			goal, err := target.Deserialize([]byte(test[1]))
163			if err != nil {
164				t.Fatalf("failed to deserialize goal program: %v", err)
165			}
166			want := goal.Serialize()
167			enabled := make(map[*Syscall]bool)
168			for _, c := range p.Calls {
169				enabled[c.Meta] = true
170			}
171			for _, c := range goal.Calls {
172				enabled[c.Meta] = true
173			}
174			ct := target.BuildChoiceTable(nil, enabled)
175			rs := rand.NewSource(0)
176			for i := 0; i < 1e5; i++ {
177				p1 := p.Clone()
178				p1.Mutate(rs, len(goal.Calls), ct, nil)
179				data1 := p1.Serialize()
180				if bytes.Equal(want, data1) {
181					t.Logf("success on iter %v", i)
182					return
183				}
184			}
185			t.Fatalf("failed to achieve goal, original:%s\ngoal:%s", test[0], test[1])
186		})
187	}
188}
189
190func BenchmarkMutate(b *testing.B) {
191	olddebug := debug
192	debug = false
193	defer func() { debug = olddebug }()
194	target, err := GetTarget("linux", "amd64")
195	if err != nil {
196		b.Fatal(err)
197	}
198	ct := linuxAmd64ChoiceTable(target)
199	const progLen = 30
200	p := target.Generate(rand.NewSource(0), progLen, nil)
201	b.ResetTimer()
202	b.RunParallel(func(pb *testing.PB) {
203		rs := rand.NewSource(0)
204		for pb.Next() {
205			p.Clone().Mutate(rs, progLen, ct, nil)
206		}
207	})
208}
209
210func BenchmarkGenerate(b *testing.B) {
211	olddebug := debug
212	debug = false
213	defer func() { debug = olddebug }()
214	target, err := GetTarget("linux", "amd64")
215	if err != nil {
216		b.Fatal(err)
217	}
218	ct := linuxAmd64ChoiceTable(target)
219	const progLen = 30
220	b.ResetTimer()
221	b.RunParallel(func(pb *testing.PB) {
222		rs := rand.NewSource(0)
223		for pb.Next() {
224			target.Generate(rs, progLen, ct)
225		}
226	})
227}
228
229var (
230	linuxCTOnce sync.Once
231	linuxCT     *ChoiceTable
232)
233
234func linuxAmd64ChoiceTable(target *Target) *ChoiceTable {
235	linuxCTOnce.Do(func() {
236		linuxCT = target.BuildChoiceTable(target.CalculatePriorities(nil), nil)
237	})
238	return linuxCT
239}
240