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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
// 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 (
"math/rand"
"sort"
"github.com/google/syzkaller/pkg/hash"
"github.com/google/syzkaller/pkg/signal"
"github.com/google/syzkaller/prog"
)
type ProgramsList struct {
progs []*prog.Prog
progToInd map[*prog.Prog]int
prios fenwikTree
}
func (pl *ProgramsList) chooseProgram(r *rand.Rand) *prog.Prog {
if len(pl.progs) == 0 {
return nil
}
randVal := r.Int63n(pl.prios.fullSum + 1)
idx := sort.Search(len(pl.progs), func(i int) bool {
return pl.prios.prefixSumTo(i+1) >= randVal
})
return pl.progs[idx]
}
func (pl *ProgramsList) saveProgram(p *prog.Prog, signal signal.Signal) {
if len(pl.progs) == 0 {
pl.progToInd = make(map[*prog.Prog]int)
}
prio := int64(len(signal))
if prio == 0 {
prio = 1
}
if ind, ok := pl.progToInd[p]; ok {
pl.prios.set(ind, prio)
} else {
pl.progs = append(pl.progs, p)
pl.progToInd[p] = len(pl.progs)
pl.prios.addNew(prio)
}
}
func (pl *ProgramsList) modifyPriority(p *prog.Prog, probSignal signal.Signal, koef int64) {
prio := int64(len(probSignal))
if prio == 0 {
prio = 1
}
if ind, ok := pl.progToInd[p]; ok {
pl.prios.add(ind, koef*prio)
}
}
func (corpus *Corpus) ChooseProgram(r *rand.Rand) *prog.Prog {
corpus.mu.RLock()
defer corpus.mu.RUnlock()
if len(corpus.progsMap) == 0 {
return nil
}
// We could have used an approach similar to chooseProgram(), but for small number
// of focus areas that is an overkill.
var randArea *focusAreaState
if len(corpus.focusAreas) > 0 {
sum := 0.0
nonEmpty := make([]*focusAreaState, 0, len(corpus.focusAreas))
for _, area := range corpus.focusAreas {
if len(area.progs) == 0 {
continue
}
sum += area.Weight
nonEmpty = append(nonEmpty, area)
}
val := r.Float64() * sum
currSum := 0.0
for _, area := range nonEmpty {
if val >= currSum {
randArea = area
}
currSum += area.Weight
}
}
if randArea != nil {
return randArea.chooseProgram(r)
}
prog := corpus.chooseProgram(r)
progData := prog.Serialize()
sig := hash.String(progData)
item := corpus.progsMap[sig]
if item.ExecLast > 0 {
corpus.modifyPriority(prog, item.Signal, -1)
item.ExecLast--
}
return prog
}
func (corpus *Corpus) Programs() []*prog.Prog {
corpus.mu.RLock()
defer corpus.mu.RUnlock()
return corpus.progs
}
|
