prefilter

Documentation

Overview

Package prefilter narrows the set of regular expressions that must be evaluated against a file.

The scan engine holds several hundred vendor rules. Evaluating every one of them against every file is the dominant cost of a scan, and on ordinary source files essentially all of that work is wasted: a rule for a GitHub token cannot match text that does not contain "ghp_".

The prefilter makes a single Aho-Corasick pass over the file and returns the rules whose mandatory literal occurs in it. Everything else is skipped.

Soundness

The entire value of this package rests on one property:

If rule R can match input D, then R is in Candidates(D).

The converse is deliberately not guaranteed. Returning a rule that turns out not to match costs one wasted regex evaluation and nothing else, so the filter is free to over-admit. Under-admitting would silently lose findings, which is why every decision in seeds.go is biased towards admitting.

A rule is only filtered when we can *prove* from its syntax tree that a particular literal must appear in any string it matches. Rules for which no such proof is available go into the residual set and are always run. FuzzPrefilterSoundness checks the property directly against real rules.

Index

• type Matcher
  • func Build(rules map[string]*regexp.Regexp) *Matcher
  • func (m *Matcher) CandidateIDs(data []byte) []string
  • func (m *Matcher) Candidates(data []byte, dst *Set)
  • func (m *Matcher) IndexOf(id string) (int, bool)
  • func (m *Matcher) NewSet() *Set
  • func (m *Matcher) NumRules() int
  • func (m *Matcher) Residual() []string
  • func (m *Matcher) RuleIDs() []string
  • func (m *Matcher) SeedsFor(id string) []string
• type Set
  • func (s *Set) Count() int
  • func (s *Set) Has(i int) bool

Types

type Matcher

type Matcher struct {
	// contains filtered or unexported fields
}

Matcher maps file content to the set of rules worth evaluating against it.

A Matcher is built once and is immutable thereafter, so a single instance is safe to share across every scan worker without synchronisation. The only mutable state involved in a lookup is the caller's Set.

func Build

func Build(rules map[string]*regexp.Regexp) *Matcher

Build constructs a Matcher over the supplied rules.

Rules whose mandatory literal cannot be established are recorded as residual and are returned by every lookup.

func (*Matcher) CandidateIDs

func (m *Matcher) CandidateIDs(data []byte) []string

CandidateIDs is a convenience wrapper returning rule IDs. It allocates, and exists for tests and diagnostics rather than the scan path.

func (*Matcher) Candidates

func (m *Matcher) Candidates(data []byte, dst *Set)

Candidates fills dst with every rule that could match data.

dst is reset first, so it may be reused across files; reuse is the point, since allocating a bitset per file would reintroduce the per-file allocation cost that phase 2 removed.

func (*Matcher) IndexOf

func (m *Matcher) IndexOf(id string) (int, bool)

IndexOf returns the bit position of a rule, and whether it is known.

func (*Matcher) NewSet

func (m *Matcher) NewSet() *Set

NewSet returns a reusable result set sized for this Matcher.

func (*Matcher) NumRules

func (m *Matcher) NumRules() int

NumRules returns the total number of rules known to the Matcher.

func (*Matcher) Residual

func (m *Matcher) Residual() []string

Residual returns the rules that are always evaluated because no mandatory literal could be proved for them.

func (*Matcher) RuleIDs

func (m *Matcher) RuleIDs() []string

RuleIDs returns the rule IDs in index order.

func (*Matcher) SeedsFor

func (m *Matcher) SeedsFor(id string) []string

SeedsFor returns the seeds proved for a rule, or nil if it is residual.

type Set

type Set struct {
	// contains filtered or unexported fields
}

Set is a bitset of rule indices.

func (*Set) Count

func (s *Set) Count() int

Count returns the number of candidate rules.

func (*Set) Has

func (s *Set) Has(i int) bool

Has reports whether the rule at index i is a candidate.