1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
// Copyright 2024 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 corpus
import (
"sort"
"github.com/google/syzkaller/pkg/signal"
)
func (corpus *Corpus) Minimize(cover bool) {
corpus.mu.Lock()
defer corpus.mu.Unlock()
inputs := make([]signal.Context, 0, len(corpus.progs))
for _, inp := range corpus.progsMap {
inputs = append(inputs, signal.Context{
Signal: inp.Signal,
Context: inp,
})
}
// Note: inputs are unsorted (based on map iteration).
// This gives some intentional non-determinism during minimization.
// However, we want to give preference to non-squashed inputs,
// so let's sort by this criteria.
// We also want to give preference to smaller corpus programs:
// - they are faster to execute,
// - minimization occasionally fails, so we need to clean it up over time.
sort.SliceStable(inputs, func(i, j int) bool {
first := inputs[i].Context.(*Item)
second := inputs[j].Context.(*Item)
if first.HasAny != second.HasAny {
return !first.HasAny
}
return len(first.Prog.Calls) < len(second.Prog.Calls)
})
corpus.progsMap = make(map[string]*Item)
// Overwrite the program lists.
corpus.ProgramsList = &ProgramsList{}
corpus.ProgramsList.prios.reserve(len(inputs))
for _, area := range corpus.focusAreas {
area.ProgramsList = &ProgramsList{}
}
progs := signal.Minimize(inputs)
sort.SliceStable(progs, func(i, j int) bool {
first := progs[i].(*Item)
second := progs[j].(*Item)
return first.ExecLast > second.ExecLast
})
inputs = make([]signal.Context, 0, len(progs))
for _, inp := range progs {
inputs = append(inputs, signal.Context{
Signal: inp.(*Item).StableSignal,
Context: inp,
})
}
progs = signal.Minimize(inputs)
for _, ctx := range progs {
inp := ctx.(*Item)
corpus.progsMap[inp.Sig] = inp
corpus.saveProgram(inp.Prog, inp.Signal)
for area := range inp.areas {
area.saveProgram(inp.Prog, inp.Signal)
}
}
}
|
