Repository: google/go-flow-levee
Pull request #174 (2020-11-06 15:24:43)

Do not infer sources from functions
This PR prevents named types from being inferred as sources due to holding functions that have source arguments or return values.

As a happy side effect, the implementation of the fix also greatly simplifies the code.

## Context

This PR removes the `ast` visitors that were previously used to find objects. The issue with the visitors is that they were grabbing all `selectors` and `identifiers`, which included those in function type definitions, e.g. the `Source` in `func() Source`. It's possible to avoid those by adding logic to each visitor to stop traversing when they hit an `ast.FuncType` node, but I wasn't too keen to add some duplicated special case behavior, so I looked for a simpler way.

The key insight I had is that we don't actually need to traverse the `ast`. We can find the information we need by "traversing" the type. We already had some code for doing this, i.e. `findNamedTypes`. That code already avoids functions, because it does not traverse through `type.Signatures`, so types within functions aren't an issue. However, it now needs to traverse through `type.Structs` in order to find struct fields, because those can be tagged. Since fields now needed to be handled in this function, it made sense to extract the objects instead of the types. Indeed, we don't want `string` in our graph, but we do want the `types.Var` that represents a `string "levee:\"source\""` field. I think it also makes sense from the client's point of view: the function that creates the object graph is interested in the objects.

- [x] Tests pass
- (N/A) [ ] 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


Patch:
diff --git a/internal/pkg/fieldpropagator/analyzer.go b/internal/pkg/fieldpropagator/analyzer.go
index 8904cb8..1dcf5a5 100644
--- a/internal/pkg/fieldpropagator/analyzer.go
+++ b/internal/pkg/fieldpropagator/analyzer.go
@@ -74,8 +74,9 @@ func run(pass *analysis.Pass) (interface{}, error) {
 		}
 		methods := ssaProg.MethodSets.MethodSet(ssaType.Type())
 		for i := 0; i < methods.Len(); i++ {
-			meth := ssaProg.MethodValue(methods.At(i))
-			analyzeBlocks(pass, conf, taggedFields, meth)
+			if meth := ssaProg.MethodValue(methods.At(i)); meth != nil {
+				analyzeBlocks(pass, conf, taggedFields, meth)
+			}
 		}
 	}
 
diff --git a/internal/pkg/sourceinfer/analyzer.go b/internal/pkg/sourceinfer/analyzer.go
index 9ace505..c20df47 100644
--- a/internal/pkg/sourceinfer/analyzer.go
+++ b/internal/pkg/sourceinfer/analyzer.go
@@ -115,94 +115,52 @@ func createObjectGraph(pass *analysis.Pass, ins *inspector.Inspector) objectGrap
 			return
 		}
 
-		typeBeingDefined := pass.TypesInfo.ObjectOf(ts.Name)
-
-		// Find selector expressions and add them to the graph.
-		// We need to look at SelectorExprs first, because they
-		// contain identifiers, e.g. foo.Bar contains the identifiers
-		// foo (qualifying package) and Bar (unqualified type).
-		// We need to look at the whole expression in order to resolve
-		// the type correctly.
-		selectorFinder := &selectorFinder{nil, map[*ast.Ident]bool{}}
-		ast.Walk(selectorFinder, (ast.Node)(ts.Type))
-		for _, sel := range selectorFinder.foundSelectors {
-			named, ok := pass.TypesInfo.TypeOf(sel).(*types.Named)
-			if !ok {
-				continue
-			}
-			obj := named.Obj()
-			objGraph[obj] = append(objGraph[obj], typeBeingDefined)
-		}
+		objectBeingDefined := pass.TypesInfo.ObjectOf(ts.Name)
 
-		// Find identifiers that aren't in selector expressions
-		// and add them to the graph.
-		idFinder := &identFinder{}
-		ast.Walk(idFinder, (ast.Node)(ts.Type))
-		for _, id := range idFinder.foundIdentifiers {
-			// identifier is part of a SelectorExpr and has already been handled
-			if selectorFinder.foundIdentifiers[id] {
-				continue
-			}
-			obj := pass.TypesInfo.ObjectOf(id)
-			objGraph[obj] = append(objGraph[obj], typeBeingDefined)
+		for o := range findObjects(pass.TypesInfo.TypeOf(ts.Type)) {
+			objGraph[o] = append(objGraph[o], objectBeingDefined)
 		}
 	})
 
 	return objGraph
 }
 
-type selectorFinder struct {
-	foundSelectors   []*ast.SelectorExpr
-	foundIdentifiers map[*ast.Ident]bool
-}
-
-func (sf *selectorFinder) Visit(n ast.Node) ast.Visitor {
-	sel, ok := n.(*ast.SelectorExpr)
-	if !ok {
-		return sf
-	}
-	pkg, ok := sel.X.(*ast.Ident)
-	if !ok {
-		return nil
-	}
-	sf.foundSelectors = append(sf.foundSelectors, sel)
-	sf.foundIdentifiers[pkg] = true
-	sf.foundIdentifiers[sel.Sel] = true
-	return nil
-}
-
-type identFinder struct {
-	foundIdentifiers []*ast.Ident
-}
-
-func (i *identFinder) Visit(n ast.Node) ast.Visitor {
-	if id, ok := n.(*ast.Ident); ok {
-		i.foundIdentifiers = append(i.foundIdentifiers, id)
-		return nil
-	}
-	return i
-}
-
-func findNamedTypes(t types.Type) map[*types.Named]bool {
-	namedTypes := map[*types.Named]bool{}
-
-	var find func(t types.Type)
-	find = func(t types.Type) {
+// findObjects traverses a type to find objects of interest within that type.
+// Objects of interest are objects that could be sources, either via configuration
+// or via inference. Specifically, this includes:
+// 1. objects related to named types,
+// 2. objects related to struct fields.
+// Some types whose objects cannot be sources are avoided.
+// In particular, functions (Signatures) are avoided because they can't be sources, but
+// their types can contain types that are tied to relevant objects, e.g. func(s Source) contains
+// a named type "Source" that would be relevant if it did not occur within a function type.
+func findObjects(t types.Type) map[types.Object]bool {
+	objects := map[types.Object]bool{}
+
+	var traverse func(t types.Type)
+	traverse = func(t types.Type) {
 		deref := utils.Dereference(t)
 		switch tt := deref.(type) {
 		case *types.Named:
-			namedTypes[tt] = true
+			objects[tt.Obj()] = true
 		case *types.Array:
-			find(tt.Elem())
+			traverse(tt.Elem())
 		case *types.Slice:
-			find(tt.Elem())
+			traverse(tt.Elem())
 		case *types.Chan:
-			find(tt.Elem())
+			traverse(tt.Elem())
 		case *types.Map:
-			find(tt.Key())
-			find(tt.Elem())
-		case *types.Basic, *types.Struct, *types.Tuple, *types.Interface, *types.Signature:
-			// these types cannot hold named types
+			traverse(tt.Key())
+			traverse(tt.Elem())
+		case *types.Struct:
+			for i := 0; i < tt.NumFields(); i++ {
+				f := tt.Field(i)
+				// The field itself could be a source, e.g. in the case of a tagged field.
+				objects[f] = true
+				traverse(f.Type())
+			}
+		case *types.Basic, *types.Tuple, *types.Interface, *types.Signature:
+			// these do not contain relevant objects
 		case *types.Pointer:
 			// this should be unreachable due to the dereference above
 		default:
@@ -211,9 +169,9 @@ func findNamedTypes(t types.Type) map[*types.Named]bool {
 		}
 	}
 
-	find(t)
+	traverse(t)
 
-	return namedTypes
+	return objects
 }
 
 func inferSources(pass *analysis.Pass, conf *config.Config, ft fieldtags.ResultType, objGraph objectGraph) ResultType {
@@ -284,8 +242,8 @@ func topoSort(graph objectGraph) []types.Object {
 }
 
 func isSourceType(c *config.Config, t types.Type) bool {
-	for nt := range findNamedTypes(t) {
-		if c.IsSourceType(utils.DecomposeType(nt)) {
+	for o := range findObjects(t) {
+		if c.IsSourceType(utils.DecomposeType(o.Type())) {
 			return true
 		}
 	}


Test patch:
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
new file mode 100644
index 0000000..44b4020
--- /dev/null
+++ b/internal/pkg/levee/testdata/src/example.com/tests/binop/tests.go
@@ -0,0 +1,31 @@
+// 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 binop
+
+import (
+	"fmt"
+
+	"example.com/core"
+)
+
+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(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 9168132..b9e897e 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
@@ -40,3 +40,10 @@ func TestArrayRemainsTaintedWhenSourceIsOverwritten(s core.Source) {
 	arr[0] = nil
 	core.Sink(arr) // want "a source has reached a sink"
 }
+
+func TestRangeOverArray() {
+	sources := [1]core.Source{core.Source{Data: "password1234"}}
+	for _, s := range sources {
+		core.Sink(s) // want "a source has reached a sink"
+	}
+}
diff --git a/internal/pkg/levee/testdata/src/example.com/tests/collections/chans.go b/internal/pkg/levee/testdata/src/example.com/tests/collections/chans.go
index 752cafa..d7d87a2 100644
--- a/internal/pkg/levee/testdata/src/example.com/tests/collections/chans.go
+++ b/internal/pkg/levee/testdata/src/example.com/tests/collections/chans.go
@@ -39,3 +39,9 @@ func TestChannelIsNoLongerTaintedWhenNilledOut(sources chan core.Source) {
 	sources = nil
 	core.Sink(sources)
 }
+
+func TestRangeOverChan(sources chan core.Source) {
+	for s := range sources {
+		core.Sink(s) // want "a source has reached a sink"
+	}
+}
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 f2e32c7..2b33f98 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
@@ -52,3 +52,28 @@ func TestMapRemainsTaintedWhenSourceIsDeleted(s core.Source) {
 	delete(m, s)
 	core.Sink(m) // want "a source has reached a sink"
 }
+
+func TestDeletingFromTaintedMapDoesNotTaintTheKey(key string, sources map[string]core.Source) {
+	delete(sources, key)
+	// TODO: no report should be produced here
+	core.Sink(key) // want "a source has reached a sink"
+}
+
+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"
+}
+
+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"
+}
+
+func TestRangeOverMap() {
+	m := map[string]core.Source{"secret": core.Source{Data: "password1234"}}
+	for _, s := range m {
+		core.Sink(s) // want "a source has reached a sink"
+	}
+}
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 859996e..7c6594d 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
@@ -26,3 +26,16 @@ func TestSlices(s core.Source) {
 	core.Sink([]interface{}{0, "", s})    // want "a source has reached a sink"
 	core.Sink([]interface{}{0, "", s}...) // want "a source has reached a sink"
 }
+
+func TestRangeOverSlice() {
+	sources := []core.Source{core.Source{Data: "password1234"}}
+	for _, s := range sources {
+		core.Sink(s) // want "a source has reached a sink"
+	}
+}
+
+func TestRangeOverInterfaceSlice() {
+	for _, s := range []interface{}{core.Source{Data: "password1235"}} {
+		core.Sink(s) // want "a source has reached a sink"
+	}
+}
diff --git a/internal/pkg/levee/testdata/src/example.com/tests/colocation/tests.go b/internal/pkg/levee/testdata/src/example.com/tests/colocation/tests.go
index 6395052..8311a76 100644
--- a/internal/pkg/levee/testdata/src/example.com/tests/colocation/tests.go
+++ b/internal/pkg/levee/testdata/src/example.com/tests/colocation/tests.go
@@ -15,6 +15,8 @@
 package colocation
 
 import (
+	"encoding/json"
+
 	"example.com/core"
 )
 
@@ -32,6 +34,18 @@ func TestTaintIsPropagatedToColocatedPointerArgumentsThroughEface(s core.Source,
 	core.Sink(ip) // want "a source has reached a sink"
 }
 
+// CVE-2020-8564
+func TestTaintIsPropagatedToDataBeingUnmarshalled(contents []byte) (src core.Source, err error) {
+	if err = json.Unmarshal(contents, &src); err != nil {
+		core.Sink(src)      // want "a source has reached a sink"
+		core.Sink(contents) // want "a source has reached a sink"
+		return
+	}
+	core.Sink(src)      // want "a source has reached a sink"
+	core.Sink(contents) // want "a source has reached a sink"
+	return
+}
+
 func taintColocated(s core.Source, i *core.Innocuous, ip *core.Innocuous) {
 }
 
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
new file mode 100644
index 0000000..bf7a38f
--- /dev/null
+++ b/internal/pkg/levee/testdata/src/example.com/tests/phi/tests.go
@@ -0,0 +1,44 @@
+// 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 phi
+
+import (
+	"example.com/core"
+)
+
+func TestPhiNodeDoesntPropagateTaintToOperands(i *core.Innocuous) {
+	for {
+		s := core.Source{}
+		var ss, ii interface{} = s, i
+		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(ss) // want "a source has reached a sink"
+	}
+}
+
+func TestPhiNodeIsTaintedByTaintedOperand(s core.Source, i *core.Innocuous) {
+	var ss, ii interface{} = s, i
+	if true {
+		ii = ss
+	}
+	core.Sink(ss) // want "a source has reached a sink"
+	core.Sink(ii) // want "a source has reached a sink"
+	core.Sink(i)
+}
diff --git a/internal/pkg/sourceinfer/testdata/src/example.com/tests/core/field.go b/internal/pkg/sourceinfer/testdata/src/example.com/tests/core/field.go
index 116dfeb..7eaadab 100644
--- a/internal/pkg/sourceinfer/testdata/src/example.com/tests/core/field.go
+++ b/internal/pkg/sourceinfer/testdata/src/example.com/tests/core/field.go
@@ -57,6 +57,14 @@ type (
 	NotSourceHolder struct {
 		ns source.NotSource
 	}
+
+	FieldFuncWithSourceArg struct {
+		f func(s source.Source)
+	}
+
+	FieldFuncWithSourceRetval struct {
+		f func() source.Source
+	}
 )
 
 func Field() {
diff --git a/internal/pkg/sourceinfer/testdata/src/example.com/tests/core/typedef.go b/internal/pkg/sourceinfer/testdata/src/example.com/tests/core/typedef.go
index 3417990..93204aa 100644
--- a/internal/pkg/sourceinfer/testdata/src/example.com/tests/core/typedef.go
+++ b/internal/pkg/sourceinfer/testdata/src/example.com/tests/core/typedef.go
@@ -30,7 +30,8 @@ type (
 )
 
 type (
-	NotDefinedSource source.NotSource
+	NotDefinedSource       source.NotSource
+	FunctionsAreNotSources func() map[string]source.Source
 )
 
 func Typedef() {