Repository: google/go-flow-levee
Pull request #178 (2020-11-10 18:27:20)

Explicitly handle each node type
This PR implements explicit handling of each node type. The idea is to make taint propagation a deliberate choice, instead of the current "just traverse to everything, except if X, Y or Z". Indeed, in most cases, propagating everywhere doesn't make much sense.

I think the resulting code is easier to understand. The epic `switch` looks intimidating, but for every node type, where to traverse is specified explicitly, in a single place. Also, `visitReferrers` actually means "visit the referrers" now (same for `visitOperands`).

Performing this work has made me discover some issues/potentially missing test cases:
- [x] `BinOp` needs tests, e.g. to make sure we aren't propagating to the other (non-tainted) operand : #179 
- [x] `Phi` needs tests, e.g. to make sure we aren't propagating to the other (non-tainted) operand : #180 
- [x] `MapUpdate` needs tests to make sure we are propagating only to the `Map`, not to the `Key` or the `Val`. #181
- [x] Tests for Index/IndexAddr : #187

The above issues have all been demonstrated via test cases, which are fixed by this PR.

For cases where the correct propagation is ambiguous, I have opened an issue here: #188. These will need further investigation. In the meantime, this PR maintains the current behavior of "traverse everywhere" for these cases.

- [x] Tests pass
- [x] Running against a large codebase such as [Kubernetes](https://github.com/kubernetes/kubernetes) does not error out.
- (N/A) [ ] Appropriate changes to README are included in PR

PurelyApplied: First off, 🎉.  Thank you for taking the time to look at each of the `Node` types.

> out of 42 node types

Just as a point of order, I only see 41 implemented and in the docs - 41 Nodes (30 Values, 35 Instructions, many both).  But that's still a heap load.

> Performing this work has made me discover some issues/potentially missing test cases:

I suspected this would happen, which is why I was pushing on it.  So double-thanks.

-----

High level comments:

Overall, I like it.  Good comments on the various switch case groups.  For consistency, I'd probably add a one-liner even to the more obvious ones, like `Call` or `FieldAddr`.  I might want to take a closer look into some of the instructions being skipped, like `Builtin`, `FreeVar` and maybe `Return`, but that might be lower-level than you're looking for right now.

I think this is pushing against our long-standing issue of `source` analyzer doing the actual propagation logic.  This seems pretty well modular, so it probably is orthogonal to that effort.

It might help to conceptualize the directional flow of taint better if we had a layer of separation between `Value` and `Instruction` in our propagation.  We are (and have long been) traversing from `Node` to `Node`, but conceptually, taint progresses from `Value` to `Value` along edges defined by `Instruction`s.  It might read better if we had start with a `Value`, got it's `referrers()`, and determined what neighboring `Value`s taint might flow through using a switch like this.  But that also feels like a refactor that is orthogonal to this work and could come in a future PR, if at all.

> `MapUpdate` needs tests to make sure we aren't propagating to the key, and that the key isn't tainting the map.

For the expression `m[k] = v`, I would expect:

* If `k` is tainted, `m` becomes tainted.  (`v` remains untainted.)
* If `v` is tainted, `m` becomes tainted.  (`k` remains untainted.)

We're probably on the same page, but your comment seems focused on the second case.  Or is it not a `MapUpdate` instruction if `k` is not already in `m`?

----

👍 overall.  Glad to see this improvement.
mlevesquedion: Thanks for pushing on this, and thanks for your thoughts!

> ... 41 nodes ...

Oops. I was looking at the entire list in `ssa/doc.go`, which includes some non-nodes (actually it looks like I miscounted those as well). There are indeed 41, according to `vim-go`'s `:GoImplements`.

> look into some of the instructions being skipped, like Builtin, FreeVar and maybe Return, but that might be lower-level than you're looking for right now.

A closer look at some/all of the instructions would be very welcome. This stuff can be tricky, so I think some duplication of effort could be good.

For the specific ones that you are mentioning here, here are some of my thoughts:
* `Builtin` is just a `Value`, conceptually it is a reference to one of the `Builtin` functions, so it can't be tainted. If there is a `Call` to a `Builtin`, we will propagate the taint via the `Call`. (I am fairly confident of this, but additional tests would not be unwelcome.)
* `FreeVar`s are handled by `sourcesFromClosure`.
* `Return` can't have `Referrers`, and it is not possible for a value being returned to taint another value that is also being returned via the `Return` instruction.

(Maybe I should add these extra thoughts to the switches? Maybe each instruction should get its own `case` + comment? That might get unwieldy, though.)

> It might help to conceptualize...

I think that would be difficult to do. Sometimes we need to propagate in ways that don't really make sense from a code execution point of view, so I'm not sure we would be able to realize this idea of traversing from `Value` to `Value` via `Instruction`s.

> For the expression m[k] = v, I would expect: ...

Agreed, those are my same thoughts. We should never propagate to anything but the `Map`.
PurelyApplied: > Builtin is just a Value, conceptually it is a reference to one of the Builtin functions, so it can't be tainted. If there is a Call to a Builtin, we will propagate the taint via the Call. (I am fairly confident of this, but additional tests would not be unwelcome.)

Ahh, yes.  I thought it was one that was both a `Value` and an `Instruction`, and as an `Instruction`, I would expect, say, `copy` to propagate taint.  My mistake.

> Return can't have Referrers, and it is not possible for a value being returned to taint another value via the Return instruction.

Similarly, I thought `Return` had a `Value`, but it looks like it's just the "We're done now" `Instruction`.  The underlying `Return.Value` should already be tainted if the return value should be tainted.

> FreeVars are handled by sourcesFromClosure.

For both `FreeVars` and `Return.Value`s, it was more a comment about completion than consumption.  If we're explicitly relying here on how things are handled elsewhere regarding `FreeVars`, we might want to at least add that comment in this `switch`.  But yeah, not necessary in the current implementation.
mlevesquedion: > Ahh, yes. I thought it was one that was both a Value and an Instruction, and as an Instruction, I would expect, say, copy to propagate taint. My mistake.

That would have made sense, that was also my expectation before looking at the docs.

> If we're explicitly relying here on how things are handled elsewhere regarding FreeVars, we might want to at least add that comment in this switch.

Done.
PurelyApplied: I'm not sure how much more work here needs to be done before this graduates from a `Draft` to an "official" PR.

I don't feel like this PR needs to be help up by decisions about how to handle various instructions.  Just getting this switch in place would allow easier iteration for correcting, e.g., how we handle `BinOp` or `Range` instructions.

It's up to you, but I'd be happy with an "in-place, no observable behavior change" refactor PR that allows easy iteration on specific instructions in future PRs.
mlevesquedion: Yep, I agree! I had the same sentiment and I was about to write a comment expressing it.

I plan to review the switch to make sure that cases where things are a bit ambiguous don't lose any propagation for now, and create an issue for each of those to investigate them further.

I'll round this out and send this for review as soon as I'm ready.
mlevesquedion: This PR is ready for review. Please read the updated description for a current summary of what this PR represents.

Patch:
diff --git a/configuration/README.md b/configuration/README.md
index 0061b7c..786c983 100644
--- a/configuration/README.md
+++ b/configuration/README.md
@@ -13,14 +13,18 @@ For design details concerning value and instruction classification, see [/design
 
 Configuration is provided to `go-flow-levee` via YAML.
 
-Objects of interest are identified primarily via regexp. An empty regexp will match any string.
+Sources are identified by package, type, and field names.
+You may specify these with a combination of string literals or regexp.
+Use `Package`, `Type`, and `Field` to specify by string literal.
+Use `PackageRE`, `TypeRE`, and `FieldRE` to specify by regexp.
+If neither a literal nor a regexp is provided, a wildcard matcher is assumed.
+Providing both a literal and a regexp matcher is considered a misconfiguration and will error.
 
-Sources are identified via regexp according to package, type, and field names.
 ```yaml
 Sources:
-- PackageRE: "<package path regexp>"
-  TypeRE: "<type name regexp>"
-  FieldRE: "<field name regexp>"
+- Package: "full/package/path"
+  # Neither Type nor TypeRE are specified - match all type names
+  FieldRE: "Token|Password|Secret" 
 ```
 
 Sources may also be identified via field tags:
@@ -37,35 +41,40 @@ FieldTags:
   Val: source
 ```
 
-Sinks and sanitizers are identified via regexp according to package, method, and (optional) receiver name.
+Sinks and sanitizers are identified by package, method, and (if applicable) receiver name.
+As with source configuration, these may be specified by either a provided string literal or regexp.
+Use `Package`, `Receiver`, and `Method` to specify by string literal.
+Use `PackageRE`, `ReceiverRE`, and `MethodRE` to specify by regexp.
+If neither a literal nor a regexp is provided, a wildcard matcher is assumed.
+Providing both a literal and a regexp matcher is considered a misconfiguration and will error.
 
 ```yaml
 Sinks:
-- PackageRE: <package path regexp>
-  ReceiverRE: <type name regexp>
-  MethodRE: <method name regexp>
+- PackageRE:  ".*/sinks(/v1)?"  # Regexp match a collection of packages 
+  # Neither Receiver nor ReceiverRE is provided - match any (or no) receiver
+  Method: "Sink"  # Match only functions named exactly "Sink"
 Sanitizers:
-- PackageRE: <package path regexp>
-  ReceiverRE: <type name regexp>
-  MethodRE: <method name regexp>
+- # Neither Package nor PackageRE is provided - match any package
+  ReceiverRE: "^Safe"  # Match any receiver beginning with "Safe"
+  Method: "sanitize"  # Match methods named exactly "sanitize"
 ```
 
-Taint propagation is performed automatically and does not need to be explicitly configured.
+To explicitly match an empty string, such as top-level functions without a receiver, explicitly configure an empty string matcher, e.g., `Receiver: ""`.
 
-For matchers that accept a `ReceiverRE` regexp matcher, an unspecified string will match any (or no) receiver.
-To match only methods without any receiver (i.e., a top-level function), use the matcher `^$` to match an empty-string receiver name.
+Taint propagation is performed automatically and does not need to be explicitly configured.
 
 ### Restricting analysis scope
 
-Functions can be explicitly excluded from analysis using regexps,
+Functions can be explicitly excluded from analysis using string literals or regexps,
 constructed similarly to those used to identify sanitizers and sinks:
 ```yaml
 Exclude:
-- PathRE: "^myproject/mypackage$"
-  MethodRE: "^myfunction$"
+- Package: "myproject/mypackage"
+  MethodRE: "^my.*"
 ```
 
-The above will match the function `myfunction` from the `myproject/mypackage` package. It will also match a method named `myfunction` in the same package.
+The above will match any function beginning with "my" in the `myproject/mypackage` package.
+Since no receiver matcher was provided, it will match any method beginning with "my" bound to any (or no) receiver.
 
 As just two examples, this may be used to avoid analyzing test code, or to suppress "false positive" reports.
 
diff --git a/internal/pkg/config/config.go b/internal/pkg/config/config.go
index e9305f1..5e045a5 100644
--- a/internal/pkg/config/config.go
+++ b/internal/pkg/config/config.go
@@ -15,6 +15,7 @@
 package config
 
 import (
+	"encoding/json"
 	"flag"
 	"fmt"
 	"io/ioutil"
@@ -120,31 +121,129 @@ func (c Config) IsSourceField(path, typeName, fieldName string) bool {
 	return false
 }
 
-// A sourceMatcher defines what types are or contain sources.
-// Within a given type, specific field access can be specified as the actual source data
-// via the fieldRE.
+type stringMatcher interface {
+	MatchString(string) bool
+}
+
+type literalMatcher string
+
+func (lm literalMatcher) MatchString(s string) bool {
+	return string(lm) == s
+}
+
+type vacuousMatcher struct{}
+
+func (vacuousMatcher) MatchString(string) bool {
+	return true
+}
+
+// Returns the first non-nil matcher.  If all are nil, returns a vacuousMatcher.
+func matcherFrom(lm *literalMatcher, r *regexp.Regexp) stringMatcher {
+	switch {
+	case lm != nil:
+		return lm
+	case r != nil:
+		return r
+	default:
+		return vacuousMatcher{}
+	}
+}
+
+// A sourceMatcher matches by package, type, and field.
+// Matching may be done against string literals Package, Type, Field,
+// or against regexp PackageRE, TypeRE, FieldRE.
 type sourceMatcher struct {
-	PackageRE regexp.Regexp
-	TypeRE    regexp.Regexp
-	FieldRE   regexp.Regexp
+	Package stringMatcher
+	Type    stringMatcher
+	Field   stringMatcher
+}
+
+// this type uses the default unmarshaler and mirrors configuration key-value pairs
+type rawSourceMatcher struct {
+	Package   *literalMatcher
+	Type      *literalMatcher
+	Field     *literalMatcher
+	PackageRE *regexp.Regexp
+	TypeRE    *regexp.Regexp
+	FieldRE   *regexp.Regexp
+}
+
+func (s *sourceMatcher) UnmarshalJSON(bytes []byte) error {
+	raw := rawSourceMatcher{}
+	if err := json.Unmarshal(bytes, &raw); err != nil {
+		return err
+	}
+
+	// validation: do not double-specify any attribute with literal and regexp
+	if raw.Package != nil && raw.PackageRE != nil {
+		return fmt.Errorf("expected only one of Package, PackageRE to be configured")
+	}
+	if raw.Type != nil && raw.TypeRE != nil {
+		return fmt.Errorf("expected only one of Type, TypeRE to be configured")
+	}
+	if raw.Field != nil && raw.FieldRE != nil {
+		return fmt.Errorf("expected only one of Field, FieldRE to be configured")
+	}
+
+	*s = sourceMatcher{
+		Package: matcherFrom(raw.Package, raw.PackageRE),
+		Type:    matcherFrom(raw.Type, raw.TypeRE),
+		Field:   matcherFrom(raw.Field, raw.FieldRE),
+	}
+	return nil
 }
 
 func (s sourceMatcher) MatchType(path, typeName string) bool {
-	return s.PackageRE.MatchString(path) && s.TypeRE.MatchString(typeName)
+	return s.Package.MatchString(path) && s.Type.MatchString(typeName)
 }
 
 func (s sourceMatcher) MatchField(path, typeName, fieldName string) bool {
-	return s.PackageRE.MatchString(path) && s.TypeRE.MatchString(typeName) && s.FieldRE.MatchString(fieldName)
+	return s.Package.MatchString(path) && s.Type.MatchString(typeName) && s.Field.MatchString(fieldName)
 }
 
 type funcMatcher struct {
-	PackageRE  regexp.Regexp
-	ReceiverRE regexp.Regexp
-	MethodRE   regexp.Regexp
+	Package  stringMatcher
+	Receiver stringMatcher
+	Method   stringMatcher
+}
+
+// this type uses the default unmarshaler and mirrors configuration key-value pairs
+type rawFuncMatcher struct {
+	Package    *literalMatcher
+	Receiver   *literalMatcher
+	Method     *literalMatcher
+	PackageRE  *regexp.Regexp
+	ReceiverRE *regexp.Regexp
+	MethodRE   *regexp.Regexp
+}
+
+func (fm *funcMatcher) UnmarshalJSON(bytes []byte) error {
+	raw := rawFuncMatcher{}
+	if err := json.Unmarshal(bytes, &raw); err != nil {
+		return err
+	}
+
+	// validation: do not double-specify any attribute with literal and regexp
+	if raw.Package != nil && raw.PackageRE != nil {
+		return fmt.Errorf("expected at most one of Package, PackageRE to be configured")
+	}
+	if raw.Receiver != nil && raw.ReceiverRE != nil {
+		return fmt.Errorf("expected at most one of Receiver, ReceiverRE to be configured")
+	}
+	if raw.Method != nil && raw.MethodRE != nil {
+		return fmt.Errorf("expected at most one of Method, MethodRE to be configured")
+	}
+
+	*fm = funcMatcher{
+		Package:  matcherFrom(raw.Package, raw.PackageRE),
+		Receiver: matcherFrom(raw.Receiver, raw.ReceiverRE),
+		Method:   matcherFrom(raw.Method, raw.MethodRE),
+	}
+	return nil
 }
 
 func (fm funcMatcher) MatchFunction(path, receiver, name string) bool {
-	return fm.PackageRE.MatchString(path) && fm.ReceiverRE.MatchString(receiver) && fm.MethodRE.MatchString(name)
+	return fm.Package.MatchString(path) && fm.Receiver.MatchString(receiver) && fm.Method.MatchString(name)
 }
 
 var readFileOnce sync.Once
diff --git a/internal/pkg/config/regexp/regexp.go b/internal/pkg/config/regexp/regexp.go
index 54a84a8..57252f6 100644
--- a/internal/pkg/config/regexp/regexp.go
+++ b/internal/pkg/config/regexp/regexp.go
@@ -26,6 +26,11 @@ type Regexp struct {
 	r *regexp.Regexp
 }
 
+func New(s string) (*Regexp, error) {
+	r, err := regexp.Compile(s)
+	return &Regexp{r: r}, err
+}
+
 // MatchString delegates matching to the regex package.
 func (mr *Regexp) MatchString(s string) bool {
 	return mr.r == nil || mr.r.MatchString(s)
diff --git a/internal/pkg/source/source.go b/internal/pkg/source/source.go
index fc4731c..675d9f5 100644
--- a/internal/pkg/source/source.go
+++ b/internal/pkg/source/source.go
@@ -75,21 +75,19 @@ func New(in ssa.Node, config classifier) *Source {
 		marked: make(map[ssa.Node]bool),
 		config: config,
 	}
-	s.dfs(in, map[*ssa.BasicBlock]int{}, nil)
+	s.dfs(in, map[*ssa.BasicBlock]int{}, nil, false)
 	return s
 }
 
 // dfs performs Depth-First-Search on the def-use graph of the input Source.
 // While traversing the graph we also look for potential sanitizers of this Source.
 // If the Source passes through a sanitizer, dfs does not continue through that Node.
-func (s *Source) dfs(n ssa.Node, maxInstrReached map[*ssa.BasicBlock]int, lastBlockVisited *ssa.BasicBlock) {
-	if s.marked[n] {
-		return
-	}
-	// booleans can't meaningfully be tainted
-	if isBoolean(n) {
+func (s *Source) dfs(n ssa.Node, maxInstrReached map[*ssa.BasicBlock]int, lastBlockVisited *ssa.BasicBlock, isReferrer bool) {
+	if s.shouldNotVisit(n, maxInstrReached, lastBlockVisited, isReferrer) {
 		return
 	}
+	s.preOrder = append(s.preOrder, n)
+	s.marked[n] = true
 
 	mirCopy := map[*ssa.BasicBlock]int{}
 	for m, i := range maxInstrReached {
@@ -97,82 +95,165 @@ func (s *Source) dfs(n ssa.Node, maxInstrReached map[*ssa.BasicBlock]int, lastBl
 	}
 
 	if instr, ok := n.(ssa.Instruction); ok {
-		// If the referrer is in a different block from the one we last visited,
-		// and it can't be reached from the block we are visiting, then stop visiting.
-		if ib := instr.Block(); lastBlockVisited != nil &&
-			ib != lastBlockVisited &&
-			!s.canReach(lastBlockVisited, ib) {
+		instrIndex, ok := indexInBlock(instr)
+		if !ok {
 			return
 		}
 
-		b := instr.Block()
-		if i, ok := indexInBlock(instr); ok && mirCopy[b] < i {
-			mirCopy[b] = i
+		if mirCopy[instr.Block()] < instrIndex {
+			mirCopy[instr.Block()] = instrIndex
 		}
-		lastBlockVisited = b
-	}
-	s.preOrder = append(s.preOrder, n)
-	s.marked[n] = true
 
-	s.visitReferrers(n, mirCopy, lastBlockVisited)
+		lastBlockVisited = instr.Block()
+	}
 
-	s.visitOperands(n, n.Operands(nil), mirCopy, lastBlockVisited)
+	s.visit(n, mirCopy, lastBlockVisited)
 }
 
-func (s *Source) visitReferrers(n ssa.Node, maxInstrReached map[*ssa.BasicBlock]int, lastBlockVisited *ssa.BasicBlock) {
-	referrers := s.referrersToVisit(n, maxInstrReached)
+func (s *Source) shouldNotVisit(n ssa.Node, maxInstrReached map[*ssa.BasicBlock]int, lastBlockVisited *ssa.BasicBlock, isReferrer bool) bool {
+	if s.marked[n] {
+		return true
+	}
 
-	for _, r := range referrers {
-		switch v := r.(type) {
-		case *ssa.Call:
-			if callee := v.Call.StaticCallee(); callee != nil && s.config.IsSanitizer(utils.DecomposeFunction(callee)) {
-				s.sanitizers = append(s.sanitizers, &sanitizer.Sanitizer{Call: v})
-			}
+	// booleans can't meaningfully be tainted
+	if isBoolean(n) {
+		return true
+	}
+
+	if instr, ok := n.(ssa.Instruction); ok {
+		instrIndex, ok := indexInBlock(instr)
+		if !ok {
+			return true
+		}
+
+		// If the referrer is in a different block from the one we last visited,
+		// and it can't be reached from the block we are visiting, then stop visiting.
+		if lastBlockVisited != nil && instr.Block() != lastBlockVisited && !s.canReach(lastBlockVisited, instr.Block()) {
+			return true
 		}
 
-		s.dfs(r.(ssa.Node), maxInstrReached, lastBlockVisited)
+		// If this call's index is lower than the highest seen so far in its block,
+		// then this call is "in the past". If this call is a referrer,
+		// then we would be propagating taint backwards in time, so stop traversing.
+		// (If the call is an operand, then it is being used as a value, so it does
+		// not matter when the call occurred.)
+		if _, ok := instr.(*ssa.Call); ok && instrIndex < maxInstrReached[instr.Block()] && isReferrer {
+			return true
+		}
 	}
+
+	return false
 }
 
-// referrersToVisit produces a filtered list of Referrers for an ssa.Node.
-// Specifically, we want to avoid referrers that shouldn't be visited, e.g.
-// because they would not be reachable in an actual execution of the program.
-func (s *Source) referrersToVisit(n ssa.Node, maxInstrReached map[*ssa.BasicBlock]int) (referrers []ssa.Instruction) {
-	if n.Referrers() == nil {
+func (s *Source) visit(n ssa.Node, maxInstrReached map[*ssa.BasicBlock]int, lastBlockVisited *ssa.BasicBlock) {
+	if s.node == n {
+		s.visitReferrers(n, maxInstrReached, lastBlockVisited)
 		return
 	}
-	for _, r := range *n.Referrers() {
-		if c, ok := r.(*ssa.Call); ok {
-			// This is to avoid attaching calls where the source is the receiver, ex:
-			// core.Sinkf("Source id: %v", wrapper.Source.GetID())
-			if recv := c.Call.Signature().Recv(); recv != nil && s.config.IsSourceType(utils.DecomposeType(utils.Dereference(recv.Type()))) {
-				continue
-			}
 
-			// If this call's index is lower than the highest in its block,
-			// then this call is "in the past" and we should stop traversing.
-			i, ok := indexInBlock(r)
-			if !ok {
-				continue
-			}
-			if i < maxInstrReached[r.Block()] {
-				continue
-			}
+	switch t := n.(type) {
+	case *ssa.Alloc:
+		// An Alloc represents the allocation of space for a variable. If a Node is an Alloc,
+		// and the thing being allocated is not an array, then either:
+		// a) it is a Source value, in which case it will get its own traversal when sourcesFromBlocks
+		//    finds this Alloc
+		// b) it is not a Source value, in which case we should not visit it.
+		// However, if the Alloc is an array, then that means the source that we are visiting from
+		// is being placed into an array, slice or varags, so we do need to keep visiting.
+		if _, isArray := utils.Dereference(t.Type()).(*types.Array); isArray {
+			s.visitReferrers(n, maxInstrReached, lastBlockVisited)
 		}
 
-		if fa, ok := r.(*ssa.FieldAddr); ok {
-			deref := utils.Dereference(fa.X.Type())
-			typPath, typName := utils.DecomposeType(deref)
-			fieldName := utils.FieldName(fa)
+	case *ssa.Call:
+		if callee := t.Call.StaticCallee(); callee != nil && s.config.IsSanitizer(utils.DecomposeFunction(callee)) {
+			s.sanitizers = append(s.sanitizers, &sanitizer.Sanitizer{Call: t})
+		}
 
-			if !s.config.IsSourceField(typPath, typName, fieldName) {
-				continue
-			}
+		// This is to avoid attaching calls where the source is the receiver, ex:
+		// core.Sinkf("Source id: %v", wrapper.Source.GetID())
+		if recv := t.Call.Signature().Recv(); recv != nil && s.config.IsSourceType(utils.DecomposeType(utils.Dereference(recv.Type()))) {
+			return
+		}
+
+		s.visitReferrers(n, maxInstrReached, lastBlockVisited)
+		s.visitOperands(n, maxInstrReached, lastBlockVisited)
+
+	case *ssa.FieldAddr:
+		deref := utils.Dereference(t.X.Type())
+		typPath, typName := utils.DecomposeType(deref)
+		fieldName := utils.FieldName(t)
+		if !s.config.IsSourceField(typPath, typName, fieldName) {
+			return
 		}
+		s.visitReferrers(n, maxInstrReached, lastBlockVisited)
+		s.visitOperands(n, maxInstrReached, lastBlockVisited)
+
+	// Everything but the actual integer Index should be visited.
+	case *ssa.Index:
+		s.visitReferrers(n, maxInstrReached, lastBlockVisited)
+		s.dfs(t.X.(ssa.Node), maxInstrReached, lastBlockVisited, false)
+
+	// The actual integer Index should not be visited.
+	// Everything but the actual integer Index should be visited.
+	case *ssa.IndexAddr:
+		s.visitReferrers(n, maxInstrReached, lastBlockVisited)
+		s.dfs(t.X.(ssa.Node), maxInstrReached, lastBlockVisited, false)
+
+	// Only the Map itself can be tainted by an Update.
+	// The Key can't be tainted.
+	// The Value can propagate taint to the Map, but not receive it.
+	// MapUpdate has no referrers, it is only an Instruction, not a Value.
+	case *ssa.MapUpdate:
+		s.dfs(t.Map.(ssa.Node), maxInstrReached, lastBlockVisited, false)
+
+	// The only Operand that can be tainted by a Send is the Chan.
+	// The Value can propagate taint to the Chan, but not receive it.
+	// Send has no referrers, it is only an Instruction, not a Value.
+	case *ssa.Send:
+		s.dfs(t.Chan.(ssa.Node), maxInstrReached, lastBlockVisited, false)
+
+	// These nodes' operands should not be visited, because they can only receive
+	// taint from their operands, not propagate taint to them.
+	case *ssa.BinOp, *ssa.ChangeInterface, *ssa.ChangeType, *ssa.Convert, *ssa.Extract, *ssa.MakeChan, *ssa.MakeMap, *ssa.MakeSlice, *ssa.Phi, *ssa.Range, *ssa.Slice, *ssa.UnOp:
+		s.visitReferrers(n, maxInstrReached, lastBlockVisited)
+
+	// These nodes don't have operands; they are Values, not Instructions.
+	case *ssa.Const, *ssa.FreeVar, *ssa.Global, *ssa.Lookup, *ssa.Parameter:
+		s.visitReferrers(n, maxInstrReached, lastBlockVisited)
+
+	// These nodes don't have referrers; they are Instructions, not Values.
+	case *ssa.Go, *ssa.Store:
+		s.visitOperands(n, maxInstrReached, lastBlockVisited)
+
+	// These nodes are both Instructions and Values, and currently have no special restrictions.
+	case *ssa.Field, *ssa.MakeInterface, *ssa.Select, *ssa.TypeAssert:
+		s.visitReferrers(n, maxInstrReached, lastBlockVisited)
+		s.visitOperands(n, maxInstrReached, lastBlockVisited)
+
+	// These nodes cannot propagate taint.
+	case *ssa.Builtin, *ssa.DebugRef, *ssa.Defer, *ssa.Function, *ssa.If, *ssa.Jump, *ssa.MakeClosure, *ssa.Next, *ssa.Panic, *ssa.Return, *ssa.RunDefers:
+
+	default:
+		fmt.Printf("unexpected node received: %T %v; please report this issue\n", n, n)
+	}
+}
+
+func (s *Source) visitReferrers(n ssa.Node, maxInstrReached map[*ssa.BasicBlock]int, lastBlockVisited *ssa.BasicBlock) {
+	if n.Referrers() == nil {
+		return
+	}
+	for _, r := range *n.Referrers() {
+		s.dfs(r.(ssa.Node), maxInstrReached, lastBlockVisited, true)
+	}
+}
 
-		referrers = append(referrers, r)
+func (s *Source) visitOperands(n ssa.Node, maxInstrReached map[*ssa.BasicBlock]int, lastBlockVisited *ssa.BasicBlock) {
+	for _, o := range n.Operands(nil) {
+		if *o == nil {
+			continue
+		}
+		s.dfs((*o).(ssa.Node), maxInstrReached, lastBlockVisited, false)
 	}
-	return referrers
 }
 
 func (s *Source) canReach(start *ssa.BasicBlock, dest *ssa.BasicBlock) bool {
@@ -198,47 +279,6 @@ func (s *Source) canReach(start *ssa.BasicBlock, dest *ssa.BasicBlock) bool {
 	return false
 }
 
-func (s *Source) visitOperands(from ssa.Node, operands []*ssa.Value, maxInstrReached map[*ssa.BasicBlock]int, lastBlockVisited *ssa.BasicBlock) {
-	// Do not visit Operands if the current node is an Extract.
-	// This is to avoid incorrectly tainting non-Source values that are
-	// produced by an Instruction that has a Source among the values it
-	// produces, e.g. a call to a function with a signature like:
-	// func NewSource() (*core.Source, error)
-	// Which leads to a flow like:
-	// Extract (*core.Source) --> Call (NewSource) --> error
-	if _, ok := from.(*ssa.Extract); ok {
-		return
-	}
-
-	for _, o := range operands {
-		n, ok := (*o).(ssa.Node)
-		if !ok {
-			continue
-		}
-
-		// An Alloc represents the allocation of space for a variable. If a Node is an Alloc,
-		// and the thing being allocated is not an array, then either:
-		// a) it is a Source value, in which case it will get its own traversal when sourcesFromBlocks
-		//    finds this Alloc
-		// b) it is not a Source value, in which case we should not visit it.
-		// However, if the Alloc is an array, then that means the source that we are visiting from
-		// is being placed into an array, slice or varags, so we do need to keep visiting.
-		if al, isAlloc := (*o).(*ssa.Alloc); isAlloc {
-			if _, isArray := utils.Dereference(al.Type()).(*types.Array); !isArray {
-				continue
-			}
-		}
-
-		// Don't traverse to the key in a lookup.
-		// For example, if a map is tainted, looking up a value in the map
-		// doesn't taint the key, so we shouldn't traverse to the key.
-		if look, ok := from.(*ssa.Lookup); ok && *o == look.Index {
-			continue
-		}
-		s.dfs(n, maxInstrReached, lastBlockVisited)
-	}
-}
-
 // compress removes the elements from the graph that are not required by the
 // taint-propagation analysis. Concretely, only propagators, sanitizers and
 // sinks should constitute the output. Since, we already know what the source
@@ -374,7 +414,7 @@ func sourcesFromBlocks(fn *ssa.Function, conf classifier) []*Source {
 				}
 
 			// source obtained through a field or an index operation
-			case *ssa.Field, *ssa.FieldAddr, *ssa.IndexAddr, *ssa.Lookup:
+			case *ssa.Field, *ssa.FieldAddr, *ssa.Index, *ssa.IndexAddr, *ssa.Lookup:
 
 			// source chan or map (arrays and slices have regular Allocs)
 			case *ssa.MakeMap, *ssa.MakeChan:


Test patch:
diff --git a/internal/pkg/config/matcher_test.go b/internal/pkg/config/matcher_test.go
new file mode 100644
index 0000000..38d91e4
--- /dev/null
+++ b/internal/pkg/config/matcher_test.go
@@ -0,0 +1,369 @@
+// Copyright 2020 Google LLC
+//
+// 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
+//
+// https://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 config
+
+import (
+	"testing"
+
+	"github.com/google/go-flow-levee/internal/pkg/config/regexp"
+	"sigs.k8s.io/yaml"
+)
+
+func TestFuncMatcherUnmarshaling(t *testing.T) {
+	testCases := []struct {
+		desc, yaml        string
+		shouldErrorOnLoad bool
+	}{
+		{
+			desc: "Unmarshaling is strict",
+			yaml: `
+Blahblah: foo
+PackageRE: bar`,
+			shouldErrorOnLoad: false, // TODO true
+		},
+		{
+			desc: "Malformed YAML errors gracefully",
+			yaml: `
+PackageRE: "No ending quote`,
+			shouldErrorOnLoad: true,
+		},
+		{
+			desc: "Malformed regexp errors gracefully",
+			yaml: `
+PackageRE: "(?:NoEndingParen"`,
+			shouldErrorOnLoad: true,
+		},
+		{
+			desc: "Do not permit both Package and PackageRE",
+			yaml: `
+Package: foo
+PackageRE: bar`,
+			shouldErrorOnLoad: true,
+		},
+		{
+			desc: "Do not permit both Receiver and ReceiverRE",
+			yaml: `
+Receiver: foo
+ReceiverRE: bar`,
+			shouldErrorOnLoad: true,
+		},
+		{
+			desc: "Do not permit both Field and FieldRE",
+			yaml: `
+Method: foo
+MethodRE: bar`,
+			shouldErrorOnLoad: true,
+		},
+	}
+
+	for _, tc := range testCases {
+		t.Run(tc.desc, func(t *testing.T) {
+			fm := funcMatcher{}
+			err := yaml.UnmarshalStrict([]byte(tc.yaml), &fm)
+
+			if (err != nil) != tc.shouldErrorOnLoad {
+				t.Errorf("error expectation = %v, but got err=%v", tc.shouldErrorOnLoad, err)
+			}
+		})
+	}
+}
+
+func TestFuncMatcherMatching(t *testing.T) {
+	testCases := []struct {
+		desc, yaml       string
+		path, recv, name string
+		shouldMatch      bool
+	}{
+		{
+			desc: "Literal foo.bar should match foo.bar; no receiver arg",
+			yaml: `
+Package: foo
+Method: bar`,
+			path:        "foo",
+			recv:        "",
+			name:        "bar",
+			shouldMatch: true,
+		},
+		{
+			desc: "Literal foo.bar should match foo.(baz).bar; no receiver arg",
+			yaml: `
+Package: foo
+Method: bar`,
+			path:        "foo",
+			recv:        "baz",
+			name:        "bar",
+			shouldMatch: true,
+		},
+		{
+			desc: "Literal foo.bar should NOT match foodstuff.bar; no receiver arg",
+			yaml: `
+Package: foo
+Method: bar`,
+			path:        "foodstuff",
+			recv:        "",
+			name:        "bar",
+			shouldMatch: false,
+		},
+		{
+			desc: "Mixed regexp and literal matchers are permitted - positive case",
+			yaml: `
+PackageRE: foo
+Receiver: baz
+Method: bar`,
+			path:        "foodstuff",
+			recv:        "baz",
+			name:        "bar",
+			shouldMatch: true,
+		},
+		{
+			desc: "Mixed regexp and literal matchers are permitted - negative case",
+			yaml: `
+PackageRE: foo
+Receiver: baz
+Method: bar`,
+			path:        "foodstuff",
+			recv:        "bazinga",
+			name:        "bar",
+			shouldMatch: false,
+		},
+	}
+
+	for _, tc := range testCases {
+		t.Run(tc.desc, func(t *testing.T) {
+			fm := funcMatcher{}
+			if err := yaml.UnmarshalStrict([]byte(tc.yaml), &fm); err != nil {
+				t.Errorf("Unexpected error unmarshalling funcMatcher: %v", err)
+			}
+
+			if tc.shouldMatch != fm.MatchFunction(tc.path, tc.recv, tc.name) {
+				t.Errorf("MatchFunction(%q, %q, %q) = %v; got %v", tc.path, tc.recv, tc.name, tc.shouldMatch, !tc.shouldMatch)
+			}
+		})
+	}
+}
+
+func TestSourceMatcherUnmarshaling(t *testing.T) {
+	testCases := []struct {
+		desc, yaml        string
+		shouldErrorOnLoad bool
+	}{
+		{
+			desc: "Unmarshaling is strict",
+			yaml: `
+Blahblah: foo
+PackageRE: bar`,
+			shouldErrorOnLoad: false, // TODO true
+		},
+		{
+			desc: "Malformed YAML errors gracefully",
+			yaml: `
+PackageRE: "No ending quote`,
+			shouldErrorOnLoad: true,
+		},
+		{
+			desc: "Malformed regexp errors gracefully",
+			yaml: `
+PackageRE: "(?:NoEndingParen"`,
+			shouldErrorOnLoad: true,
+		},
+		{
+			desc: "Do not permit both Package and PackageRE",
+			yaml: `
+Package: foo
+PackageRE: bar`,
+			shouldErrorOnLoad: true,
+		},
+		{
+			desc: "Do not permit both Type and TypeRE",
+			yaml: `
+Type: foo
+TypeRE: bar`,
+			shouldErrorOnLoad: true,
+		},
+		{
+			desc: "Do not permit both Field and FieldRE",
+			yaml: `
+Field: foo
+FieldRE: bar`,
+			shouldErrorOnLoad: true,
+		},
+	}
+
+	for _, tc := range testCases {
+		t.Run(tc.desc, func(t *testing.T) {
+			sm := sourceMatcher{}
+			err := yaml.UnmarshalStrict([]byte(tc.yaml), &sm)
+
+			if (err != nil) != tc.shouldErrorOnLoad {
+				t.Errorf("error expectation = %v, but got err=%v", tc.shouldErrorOnLoad, err)
+			}
+		})
+	}
+}
+
+func TestSourceMatcherMatching(t *testing.T) {
+	testCases := []struct {
+		desc, yaml           string
+		path, typ, fieldName string
+		shouldMatchType      bool
+		shouldMatchField     bool
+	}{
+		{
+			desc: "Literal foo.bar (no field args) should match foo.bar and foo.bar.baz",
+			yaml: `
+Package: foo
+Type: bar`,
+			path:             "foo",
+			typ:              "bar",
+			fieldName:        "baz",
+			shouldMatchType:  true,
+			shouldMatchField: true,
+		},
+		{
+			desc: "Literal foo.bar (no field args) should NOT match foodstuff.bar or foodstuff.bar.baz",
+			yaml: `
+Package: foo
+Type: bar`,
+			path:             "foodstuff",
+			typ:              "bar",
+			fieldName:        "baz",
+			shouldMatchType:  false,
+			shouldMatchField: false,
+		},
+		{
+			desc: "Regexp foo.bar (no field args) should match foodstuff.bar and foodstuff.bar.baz",
+			yaml: `
+PackageRE: foo
+TypeRE: bar`,
+			path:             "foodstuff",
+			typ:              "bar",
+			fieldName:        "baz",
+			shouldMatchType:  true,
+			shouldMatchField: true,
+		},
+		{
+			desc: "Mixed regexp and literal matchers are permitted",
+			yaml: `
+PackageRE: foo
+Type: bar
+Field: baz`,
+			path:             "foodstuff",
+			typ:              "bar",
+			fieldName:        "baz",
+			shouldMatchType:  true,
+			shouldMatchField: true,
+		},
+		{
+			desc: "Literal foo.bar.qux should MatchType foo.bar but not MatchField foo.bar.baz",
+			yaml: `
+PackageRE: foo
+Type: bar
+Field: qux`,
+			path:             "foodstuff",
+			typ:              "bar",
+			fieldName:        "baz",
+			shouldMatchType:  true,
+			shouldMatchField: false,
+		},
+	}
+
+	for _, tc := range testCases {
+		t.Run(tc.desc, func(t *testing.T) {
+			sm := sourceMatcher{}
+			if err := yaml.UnmarshalStrict([]byte(tc.yaml), &sm); err != nil {
+				t.Errorf("Unexpected error unmarshalling sourceMatcher: %v", err)
+			}
+
+			if tc.shouldMatchType != sm.MatchType(tc.path, tc.typ) {
+				t.Errorf("MatchType(%q, %q) = %v; got %v", tc.path, tc.typ, tc.shouldMatchType, !tc.shouldMatchType)
+			}
+			if tc.shouldMatchField != sm.MatchField(tc.path, tc.typ, tc.fieldName) {
+				t.Errorf("MatchField(%q, %q, %q) = %v; got %v", tc.path, tc.typ, tc.fieldName, tc.shouldMatchType, !tc.shouldMatchType)
+			}
+		})
+	}
+}
+
+func TestMatcherTypes(t *testing.T) {
+	testCases := []struct {
+		desc        string
+		matcher     stringMatcher
+		s           string
+		shouldMatch bool
+	}{
+		{
+			desc:        "literal matcher foo == foo",
+			matcher:     literalMatcher("foo"),
+			s:           "foo",
+			shouldMatch: true,
+		},
+		{
+			desc:        "literal matcher foo != food",
+			matcher:     literalMatcher("foo"),
+			s:           "food",
+			shouldMatch: false,
+		},
+		{
+			desc:        "literal matcher foo != bar",
+			matcher:     literalMatcher("foo"),
+			s:           "bar",
+			shouldMatch: false,
+		},
+		{
+			desc:        "regexp matcher /foo/ matches foo",
+			matcher:     func() stringMatcher { r, _ := regexp.New("foo"); return r }(),
+			s:           "foo",
+			shouldMatch: true,
+		},
+		{
+			desc:        "regexp matcher /foo/ matches food",
+			matcher:     func() stringMatcher { r, _ := regexp.New("foo"); return r }(),
+			s:           "food",
+			shouldMatch: true,
+		},
+		{
+			desc:        "regexp matcher /foo/ does not match bar",
+			matcher:     func() stringMatcher { r, _ := regexp.New("foo"); return r }(),
+			s:           "bar",
+			shouldMatch: false,
+		},
+		{
+			desc:        "vacuous matcher matches foo",
+			matcher:     vacuousMatcher{},
+			s:           "foo",
+			shouldMatch: true,
+		},
+		{
+			desc:        "vacuous matcher matches food",
+			matcher:     vacuousMatcher{},
+			s:           "food",
+			shouldMatch: true,
+		},
+		{
+			desc:        "vacuous matcher matches bar",
+			matcher:     vacuousMatcher{},
+			s:           "bar",
+			shouldMatch: true,
+		},
+	}
+
+	for _, tc := range testCases {
+		t.Run(tc.desc, func(t *testing.T) {
+			if tc.matcher.MatchString(tc.s) != tc.shouldMatch {
+				t.Errorf("Expected matcher (%T) %v to return MatchString(%q) == %v, got %v", tc.matcher, tc.matcher, tc.s, tc.shouldMatch, !tc.shouldMatch)
+			}
+		})
+	}
+}
diff --git a/internal/pkg/levee/testdata/src/example.com/tests/binop/tests.go b/internal/pkg/levee/testdata/src/example.com/tests/binop/tests.go
index 44b4020..5da7316 100644
--- a/internal/pkg/levee/testdata/src/example.com/tests/binop/tests.go
+++ b/internal/pkg/levee/testdata/src/example.com/tests/binop/tests.go
@@ -24,8 +24,7 @@ func TestConcatenatingTaintedAndNonTaintedStrings(prefix string) {
 	s := core.Source{Data: "password1234"}
 	message := fmt.Sprintf("source: %v", s)
 	fullMessage := prefix + message
-	// TODO: no report should be produced for "prefix"
-	core.Sink(prefix)      // want "a source has reached a sink"
+	core.Sink(prefix)
 	core.Sink(message)     // want "a source has reached a sink"
 	core.Sink(fullMessage) // want "a source has reached a sink"
 }
diff --git a/internal/pkg/levee/testdata/src/example.com/tests/collections/arrays.go b/internal/pkg/levee/testdata/src/example.com/tests/collections/arrays.go
index eb0fbf0..3edf8d0 100644
--- a/internal/pkg/levee/testdata/src/example.com/tests/collections/arrays.go
+++ b/internal/pkg/levee/testdata/src/example.com/tests/collections/arrays.go
@@ -45,7 +45,6 @@ func TestRangeOverArray() {
 	sources := [1]core.Source{core.Source{Data: "password1234"}}
 	for i, s := range sources {
 		core.Sink(s) // want "a source has reached a sink"
-		// TODO want no diagnostic reported for string value
-		core.Sink(i) // want "a source has reached a sink"
+		core.Sink(i)
 	}
 }
diff --git a/internal/pkg/levee/testdata/src/example.com/tests/collections/maps.go b/internal/pkg/levee/testdata/src/example.com/tests/collections/maps.go
index b3a2de4..e251a52 100644
--- a/internal/pkg/levee/testdata/src/example.com/tests/collections/maps.go
+++ b/internal/pkg/levee/testdata/src/example.com/tests/collections/maps.go
@@ -61,22 +61,19 @@ func TestDeletingFromTaintedMapDoesNotTaintTheKey(key string, sources map[string
 
 func TestMapUpdateWithTaintedValueDoesNotTaintTheKey(key string, value core.Source, sources map[string]core.Source) {
 	sources[key] = value
-	// TODO: no report should be produced here
-	core.Sink(key) // want "a source has reached a sink"
+	core.Sink(key)
 }
 
 func TestMapUpdateWithTaintedKeyDoesNotTaintTheValue(key core.Source, value string, sources map[core.Source]string) {
 	sources[key] = value
-	// TODO: no report should be produced here
-	core.Sink(value) // want "a source has reached a sink"
+	core.Sink(value)
 }
 
 func TestRangeOverMapWithSourceAsValue() {
 	m := map[string]core.Source{"secret": core.Source{Data: "password1234"}}
 	for k, s := range m {
 		core.Sink(s) // want "a source has reached a sink"
-		// TODO want no diagnostic reported for string key
-		core.Sink(k) // want "a source has reached a sink"
+		core.Sink(k)
 	}
 }
 
@@ -84,7 +81,6 @@ func TestRangeOverMapWithSourceAsKey() {
 	m := map[core.Source]string{core.Source{Data: "password1234"}: "don't sink me"}
 	for src, str := range m {
 		core.Sink(src) // want "a source has reached a sink"
-		// TODO want no diagnostic reported for string value
-		core.Sink(str) // want "a source has reached a sink"
+		core.Sink(str)
 	}
 }
diff --git a/internal/pkg/levee/testdata/src/example.com/tests/collections/slices.go b/internal/pkg/levee/testdata/src/example.com/tests/collections/slices.go
index ec63ebf..da2f641 100644
--- a/internal/pkg/levee/testdata/src/example.com/tests/collections/slices.go
+++ b/internal/pkg/levee/testdata/src/example.com/tests/collections/slices.go
@@ -31,15 +31,13 @@ func TestRangeOverSlice() {
 	sources := []core.Source{core.Source{Data: "password1234"}}
 	for i, s := range sources {
 		core.Sink(s) // want "a source has reached a sink"
-		// TODO want no diagnostic reported for string value
-		core.Sink(i) // want "a source has reached a sink"
+		core.Sink(i)
 	}
 }
 
 func TestRangeOverInterfaceSlice() {
 	for i, s := range []interface{}{core.Source{Data: "password1235"}} {
 		core.Sink(s) // want "a source has reached a sink"
-		// TODO want no diagnostic reported for string value
-		core.Sink(i) // want "a source has reached a sink"
+		core.Sink(i)
 	}
 }
diff --git a/internal/pkg/levee/testdata/src/example.com/tests/phi/tests.go b/internal/pkg/levee/testdata/src/example.com/tests/phi/tests.go
index bf7a38f..d065af6 100644
--- a/internal/pkg/levee/testdata/src/example.com/tests/phi/tests.go
+++ b/internal/pkg/levee/testdata/src/example.com/tests/phi/tests.go
@@ -25,10 +25,8 @@ func TestPhiNodeDoesntPropagateTaintToOperands(i *core.Innocuous) {
 		if true {
 			ss = ii
 		}
-		// TODO: no report should be produced for ii
-		core.Sink(ii) // want "a source has reached a sink"
-		// TODO: no report should be produced for i
-		core.Sink(i)  // want "a source has reached a sink"
+		core.Sink(ii)
+		core.Sink(i)
 		core.Sink(ss) // want "a source has reached a sink"
 	}
 }
diff --git a/internal/pkg/levee/testdata/src/example.com/tests/typeassert/tests.go b/internal/pkg/levee/testdata/src/example.com/tests/typeassert/tests.go
index 5c3f2ce..db62d4c 100644
--- a/internal/pkg/levee/testdata/src/example.com/tests/typeassert/tests.go
+++ b/internal/pkg/levee/testdata/src/example.com/tests/typeassert/tests.go
@@ -36,5 +36,5 @@ func TestSourcePointerAssertedFromParameterEface(e interface{}) {
 func TestSourcePointerAssertedFromParameterEfaceCommaOk(e interface{}) {
 	s, ok := e.(*core.Source)
 	core.Sink(s) // want "a source has reached a sink"
-	_ = ok
+	core.Sink(ok)
 }