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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
|
// 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 declextract
import (
"fmt"
"slices"
"strings"
"github.com/google/syzkaller/pkg/cover"
)
type Interface struct {
Type string
Name string
IdentifyingConst string
Files []string
Func string
Access string
Subsystems []string
ManualDescriptions TristateVal
AutoDescriptions TristateVal
ReachableLOC int
CoveredBlocks int
TotalBlocks int
scopeArg int
scopeVal string
}
type TristateVal int
const (
TristateUnknown TristateVal = iota
TristateYes
TristateNo
)
const (
IfaceSyscall = "SYSCALL"
IfaceNetlinkOp = "NETLINK"
IfaceFileop = "FILEOP"
IfaceIoctl = "IOCTL"
IfaceIouring = "IOURING"
AccessUnknown = "unknown"
AccessUser = "user"
AccessNsAdmin = "ns_admin"
AccessAdmin = "admin"
)
func (ctx *context) noteInterface(iface *Interface) {
ctx.interfaces = append(ctx.interfaces, iface)
}
func (ctx *context) finishInterfaces() {
ctx.interfaces = sortAndDedupSlice(ctx.interfaces)
count := make(map[string]int)
for _, iface := range ctx.interfaces {
count[iface.Type+iface.Name]++
}
// Lots of file ops have the same name, add file name to them.
for _, iface := range ctx.interfaces {
if count[iface.Type+iface.Name] > 1 {
iface.Name = iface.Name + "_" + fileNameSuffix(iface.Files[0])
}
}
for _, iface := range ctx.interfaces {
ctx.calculateLOC(iface)
slices.Sort(iface.Files)
iface.Files = slices.Compact(iface.Files)
if iface.Access == "" {
iface.Access = AccessUnknown
}
if iface.Access == "" {
iface.Access = AccessUnknown
}
}
ctx.interfaces = sortAndDedupSlice(ctx.interfaces)
}
func (ctx *context) processFunctions() {
for _, fn := range ctx.Functions {
ctx.funcs[fn.File+fn.Name] = fn
// Strictly speaking there may be several different static functions in different headers,
// but we ignore such possibility for now.
if !fn.IsStatic || strings.HasSuffix(fn.File, ".h") {
ctx.funcs[fn.Name] = fn
}
}
coverBlocks := make(map[string][]*cover.Block)
for _, file := range ctx.coverage {
for _, fn := range file.Functions {
coverBlocks[file.FilePath+fn.FuncName] = fn.Blocks
}
}
for _, fn := range ctx.Functions {
for _, block := range coverBlocks[fn.File+fn.Name] {
var match *FunctionScope
for _, scope := range fn.Scopes {
if scope.Arg == -1 {
match = scope
}
if block.FromLine >= scope.StartLine && block.FromLine <= scope.EndLine {
match = scope
break
}
}
match.totalBlocks++
if block.HitCount != 0 {
match.coveredBlocks++
}
}
for _, scope := range fn.Scopes {
for _, callee := range scope.Calls {
called := ctx.findFunc(callee, fn.File)
if called == nil || called == fn {
continue
}
scope.calls = append(scope.calls, called)
called.callers++
}
}
}
}
func (ctx *context) calculateLOC(iface *Interface) {
fn := ctx.findFunc(iface.Func, iface.Files[0])
if fn == nil {
ctx.warn("can't find function %v called in %v", iface.Func, iface.Files[0])
return
}
scopeFnArgs := ctx.inferArgFlow(fnArg{fn, iface.scopeArg})
visited := make(map[*Function]bool)
iface.ReachableLOC = ctx.collectLOC(iface, fn, scopeFnArgs, iface.scopeVal, visited)
}
func (ctx *context) collectLOC(iface *Interface, fn *Function, scopeFnArgs map[fnArg]bool,
scopeVal string, visited map[*Function]bool) int {
// Ignore very common functions when computing reachability for complexity analysis.
// Counting kmalloc/printk against each caller is not useful (they have ~10K calls).
// There are also subsystem common functions (e.g. functions called in some parts of fs/net).
// The current threshold is somewhat arbitrary and is based on the number of callers in syzbot kernel:
// 6 callers - 2272 functions
// 5 callers - 3468 functions
// 4 callers - 6295 functions
// 3 callers - 16527 functions
const commonFuncThreshold = 5
visited[fn] = true
loc := max(0, fn.EndLine-fn.StartLine-1)
for _, scope := range fn.Scopes {
if !relevantScope(scopeFnArgs, scopeVal, scope) {
loc -= max(0, scope.EndLine-scope.StartLine)
continue
}
iface.TotalBlocks += scope.totalBlocks
iface.CoveredBlocks += scope.coveredBlocks
for _, callee := range scope.calls {
if visited[callee] || callee.callers >= commonFuncThreshold {
continue
}
loc += ctx.collectLOC(iface, callee, scopeFnArgs, scopeVal, visited)
}
}
return loc
}
func (ctx *context) findFunc(name, file string) *Function {
if fn := ctx.funcs[file+name]; fn != nil {
return fn
}
return ctx.funcs[name]
}
func (ctx *context) mustFindFunc(name, file string) *Function {
if name == "" {
return nil
}
fn := ctx.findFunc(name, file)
if fn == nil {
panic(fmt.Sprintf("no func %q in %q", name, file))
}
return fn
}
func fileNameSuffix(file string) string {
// Remove file extension.
ext := strings.LastIndexByte(file, '.')
if ext != -1 {
file = file[:ext]
}
raw := []byte(file)
for i, v := range raw {
if v >= 'a' && v <= 'z' || v >= 'A' && v <= 'Z' || v >= '0' && v <= '9' {
continue
}
raw[i] = '_'
}
return string(raw)
}
func Tristate(v bool) TristateVal {
if v {
return TristateYes
}
return TristateNo
}
func (tv TristateVal) String() string {
switch tv {
case TristateYes:
return "true"
case TristateNo:
return "false"
default:
return "unknown"
}
}
|
