forked from facebookincubator/nvdtools
-
Notifications
You must be signed in to change notification settings - Fork 0
/
cvecache.go
287 lines (260 loc) · 8.52 KB
/
cvecache.go
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
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
// Copyright (c) Facebook, Inc. and its affiliates.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package cvefeed
import (
"sort"
"strings"
"sync"
"sync/atomic"
"unsafe"
"github.com/facebookincubator/flog"
"github.com/facebookincubator/nvdtools/wfn"
)
const cacheEvictPercentage = 0.1 // every eviction cycle invalidates this part of cache size at once
// Index maps the CPEs to the entries in the NVD feed they mentioned in
type Index map[string][]Vuln
// NewIndex creates new Index from a slice of CVE entries
func NewIndex(d Dictionary) Index {
idx := Index{}
for _, entry := range d {
set := map[string]bool{}
for _, cpe := range entry.Config() {
// Can happen, for instance, when the feed contains illegal binding of CPE name. Unfortunately, it happens to NVD,
// e.g. embedded ? in cpe:2.3:a:disney:where\\'s_my_perry?_free:1.5.1:*:*:*:*:android:*:* of CVE-2014-5606
if cpe == nil {
continue
}
product := cpe.Product
if wfn.HasWildcard(product) {
product = wfn.Any
}
if !set[product] {
set[product] = true
idx[product] = append(idx[product], entry)
}
}
}
return idx
}
// MatchResult stores CVE and a slice of CPEs that matched it
type MatchResult struct {
CVE Vuln
CPEs []*wfn.Attributes
}
// cachedCVEs stores cached CVEs, a channel to signal if the value is ready
type cachedCVEs struct {
res []MatchResult
ready chan struct{}
size int64
evictionIndex int // position in eviction queue
}
// updateResSize calculates the size of cached MatchResult and assigns it to cves.size
func (cves *cachedCVEs) updateResSize(key string) {
cves.size = int64(int(unsafe.Sizeof(key)) + len(key))
if cves == nil {
return
}
cves.size += int64(unsafe.Sizeof(cves.res))
for i := range cves.res {
cves.size += int64(unsafe.Sizeof(cves.res[i].CVE))
for _, attr := range cves.res[i].CPEs {
cves.size += int64(len(attr.Part)) + int64(unsafe.Sizeof(attr.Part))
cves.size += int64(len(attr.Vendor)) + int64(unsafe.Sizeof(attr.Vendor))
cves.size += int64(len(attr.Product)) + int64(unsafe.Sizeof(attr.Product))
cves.size += int64(len(attr.Version)) + int64(unsafe.Sizeof(attr.Version))
cves.size += int64(len(attr.Update)) + int64(unsafe.Sizeof(attr.Update))
cves.size += int64(len(attr.Edition)) + int64(unsafe.Sizeof(attr.Edition))
cves.size += int64(len(attr.SWEdition)) + int64(unsafe.Sizeof(attr.SWEdition))
cves.size += int64(len(attr.TargetHW)) + int64(unsafe.Sizeof(attr.TargetHW))
cves.size += int64(len(attr.Other)) + int64(unsafe.Sizeof(attr.Other))
cves.size += int64(len(attr.Language)) + int64(unsafe.Sizeof(attr.Language))
}
}
}
// Cache caches CVEs for known CPEs
type Cache struct {
// Used to compute the hit ratio
numLookups int64
numHits int64
// Actual cache data
data map[string]*cachedCVEs
evictionQ *evictionQueue
mu sync.Mutex
Dict Dictionary
Idx Index
MaxSize int64 // maximum size of the cache, 0 -- unlimited, -1 -- no caching
size int64 // current size of the cache
RequireVersion bool // ignore matching specifications that have Version == ANY
}
// NewCache creates new Cache instance with dictionary dict.
func NewCache(dict Dictionary) *Cache {
return &Cache{Dict: dict, evictionQ: new(evictionQueue)}
}
// SetRequireVersion sets if the instance of cache fails matching the dictionary
// records without Version attribute of CPE name.
// Returns a pointer to the instance of Cache, for easy chaining.
func (c *Cache) SetRequireVersion(requireVersion bool) *Cache {
c.RequireVersion = requireVersion
return c
}
// SetMaxSize sets maximum size of the cache to some pre-defined value,
// size of 0 disables eviction (makes the cache grow indefinitely),
// negative size disables caching.
// Returns a pointer to the instance of Cache, for easy chaining.
func (c *Cache) SetMaxSize(size int64) *Cache {
c.MaxSize = size
return c
}
// Get returns slice of CVEs for CPE names from cpes parameter;
// if CVEs aren't cached (and the feature is enabled) it finds them in cveDict and caches the results
func (c *Cache) Get(cpes []*wfn.Attributes) []MatchResult {
atomic.AddInt64(&c.numLookups, 1)
// negative max size of the cache disables caching
if c.MaxSize < 0 {
return c.match(cpes)
}
// otherwise, let's get to the business
key := cacheKey(cpes)
c.mu.Lock()
if c.data == nil {
c.data = make(map[string]*cachedCVEs)
}
cves := c.data[key]
if cves != nil {
atomic.AddInt64(&c.numHits, 1)
// value is being computed, wait till ready
c.mu.Unlock()
<-cves.ready
c.mu.Lock() // TODO: XXX: ugly, consider using atomic.Value instead
cves.evictionIndex = c.evictionQ.touch(cves.evictionIndex)
c.mu.Unlock()
return cves.res
}
// first request; the goroutine that sent it computes the value
cves = &cachedCVEs{ready: make(chan struct{})}
c.data[key] = cves
c.mu.Unlock()
// now other requests for same key wait on the channel, and the requests for the different keys aren't blocked
cves.res = c.match(cpes)
cves.updateResSize(key)
c.mu.Lock()
if c.MaxSize != 0 && c.size+cves.size > c.MaxSize {
c.evict(int64(cacheEvictPercentage*float64(c.MaxSize)) + cves.size)
}
c.size += cves.size
cves.evictionIndex = c.evictionQ.push(key)
c.mu.Unlock()
close(cves.ready)
return cves.res
}
// match will return all match results based on the given cpes
func (c *Cache) match(cpes []*wfn.Attributes) []MatchResult {
d := c.Dict
if c.Idx != nil {
d = c.dictFromIndex(cpes)
}
return c.matchDict(cpes, d)
}
// dictFromIndex creates CVE dictionary from entries indexed by CPE names
func (c *Cache) dictFromIndex(cpes []*wfn.Attributes) Dictionary {
d := Dictionary{}
if c.Idx == nil {
return d
}
knownEntries := map[Vuln]bool{}
addVulns := func(product string) {
for _, vuln := range c.Idx[product] {
if !knownEntries[vuln] {
knownEntries[vuln] = true
d[vuln.ID()] = vuln
}
}
}
for _, cpe := range cpes {
if cpe == nil { // should never happen
flog.Warning("nil CPE in list")
continue
}
// any of the CPEs having product=ANY would mean we need to match against the entire dictionary
if cpe.Product == wfn.Any {
return c.Dict
}
addVulns(cpe.Product)
}
addVulns(wfn.Any)
return d
}
// match matches the CPE names against internal vulnerability dictionary and returns a slice of matching resutls
func (c *Cache) matchDict(cpes []*wfn.Attributes, dict Dictionary) (results []MatchResult) {
for _, v := range dict {
if matches := v.Match(cpes, c.RequireVersion); len(matches) > 0 {
results = append(results, MatchResult{v, matches})
}
}
return results
}
// evict the least recently used records untile nbytes of capacity is achieved or no more records left.
// It is not concurrency-safe, c.mu should be locked before calling it.
func (c *Cache) evict(nbytes int64) {
for c.size > 0 && c.size+nbytes > c.MaxSize {
key := c.evictionQ.pop()
cd, ok := c.data[key]
if !ok { // should not happen
panic("attempted to evict non-existent record")
}
c.size -= cd.size
delete(c.data, key)
}
}
func cacheKey(cpes []*wfn.Attributes) string {
parts := make([]string, 0, len(cpes))
for _, cpe := range cpes {
if cpe == nil {
continue
}
var out strings.Builder
out.WriteString(cpe.Part)
out.WriteByte('^')
out.WriteString(cpe.Vendor)
out.WriteByte('^')
out.WriteString(cpe.Product)
out.WriteByte('^')
out.WriteString(cpe.Version)
out.WriteByte('^')
out.WriteString(cpe.Update)
out.WriteByte('^')
out.WriteString(cpe.Edition)
out.WriteByte('^')
out.WriteString(cpe.SWEdition)
out.WriteByte('^')
out.WriteString(cpe.TargetSW)
out.WriteByte('^')
out.WriteString(cpe.TargetHW)
out.WriteByte('^')
out.WriteString(cpe.Other)
out.WriteByte('^')
out.WriteString(cpe.Language)
parts = append(parts, out.String())
}
sort.Strings(parts)
return strings.Join(parts, "#")
}
// HitRatio returns the cache hit ratio, the number of cache hits to the number
// of lookups, as a percentage.
func (c *Cache) HitRatio() float64 {
if c.numLookups == 0 {
return 0
}
return float64(c.numHits) / float64(c.numLookups) * 100
}