Repository: google/go-flow-levee
Pull request #80 (2020-09-02 21:11:57)

Fix false positives due to propagation through extracts
## The bug
While running the analyzer on kubernetes, I got a false positive report for an error value that was returned from a function that returns two values: a `Source` value and an `error`. Here is an abstract example:
```go
func CreateSource() (core.Source, error) {
	return core.Source{}, nil
}

func TestExtracts() {
	s, err := CreateSource()
	core.Sink(err) // unexpected diagnostic here
	_ = s
}
```
Just because the `error` value is returned next to a `Source`, that doesn't mean it should be tainted.

## The problem

The core of the problem is that we are traversing to nodes that we shouldn't be traversing to. Consider the following piece of an SSA graph:
![image](https://user-images.githubusercontent.com/28677454/92034025-a62bdd00-ed3a-11ea-8f8f-ef817b884199.png)

While scanning the instructions, the code in `source.go:sourcesFromBlocks` will find the `Alloc` and create a `Source` from it, which will start a DFS. The DFS reaches the `Extract`, which is used to extract the `Source` from the tuple created that is returned by the `CreateSource` function. The problem is that with the current call, the traversal continues through the `Call`, and into the other `Extract` (not shown in the image), which leads to the call to `core.Sink`, and therefore an unexpected diagnostic.

## The fix

The fix is simply to avoid traversing to a `Call` from an `Extract`. The tainted `Extract` will have the `Source`-producing call as an `Operand`, which just need to avoid it.

## Additional details

The tests cover a variety of failure cases that I ran into while developing this fix.

The last test case documents a logical extension of current behavior, namely that if a function takes a `Source` as argument, we consider its return value(s) to be tainted.

- [x] Tests pass
- [x] Appropriate changes to README are included in PR

mlevesquedion: These are good test cases, but I believe they are caused by a different issue.

The first one is caused by the fact that no `Source` is identified from the instructions. Because the call returns a pointer, no local copy (`Alloc`) is made, so we never catch it. We might've caught it through our `case *ssa.Call:` in `source.go:sourcesFromBlocks`, but because what's returned is a `tuple`, not directly a `Source`, we don't catch it. Here's the SSA graph:

![image](https://user-images.githubusercontent.com/28677454/92121984-ea65be80-edc8-11ea-86aa-8a9e957b7ee2.png)

The second one is also caused by the previous observation, along with the fact that we don't visit through `Source` methods. So when the returned value is a `Source`, not a `*Source`, we don't DFS through the method call, but there `is` an `Alloc` for the returned `Source`, so we find the sink. If the returned value is a `*Source` though, we don't detect it.

So in both cases, the fix is we need better `Source` identification. I think that belongs to its own PR, along with additional tests. WDYT?

Patch:
diff --git a/internal/pkg/source/source.go b/internal/pkg/source/source.go
index d33c7f9..3c9618d 100644
--- a/internal/pkg/source/source.go
+++ b/internal/pkg/source/source.go
@@ -82,7 +82,7 @@ func (a *Source) dfs(n ssa.Node) {
 	var operands []*ssa.Value
 	operands = n.Operands(operands)
 	if operands != nil {
-		a.visitOperands(operands)
+		a.visitOperands(n, operands)
 	}
 }
 
@@ -134,12 +134,24 @@ func (a *Source) visitReferrers(referrers *[]ssa.Instruction) {
 	}
 }
 
-func (a *Source) visitOperands(operands []*ssa.Value) {
+func (a *Source) visitOperands(n ssa.Node, operands []*ssa.Value) {
+	_, visitingFromExtract := n.(*ssa.Extract)
+
 	for _, o := range operands {
 		n, ok := (*o).(ssa.Node)
 		if !ok || a.marked[n] {
 			continue
 		}
+
+		// Do not visit a Call if the current node is an Extract.
+		// This is to avoid incorrectly tainting non-Source values that are
+		// returned from a call that has a Source among its return values,
+		// e.g. a call to a function with a signature like:
+		// func CreateSource() (core.Source, error)
+		if _, ok := (*o).(*ssa.Call); visitingFromExtract && 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
diff --git a/internal/pkg/sourcetype/analyzer.go b/internal/pkg/sourcetype/analyzer.go
index afb9fb7..9ec612f 100644
--- a/internal/pkg/sourcetype/analyzer.go
+++ b/internal/pkg/sourcetype/analyzer.go
@@ -24,6 +24,7 @@ import (
 	"sort"
 
 	"github.com/google/go-flow-levee/internal/pkg/config"
+	"github.com/google/go-flow-levee/internal/pkg/fieldtags"
 	"golang.org/x/tools/go/analysis"
 	"golang.org/x/tools/go/analysis/passes/buildssa"
 	"golang.org/x/tools/go/ssa"
@@ -78,7 +79,7 @@ var Analyzer = &analysis.Analyzer{
 	Doc:        "This analyzer identifies types.Types values which contain dataflow sources.",
 	Flags:      config.FlagSet,
 	Run:        run,
-	Requires:   []*analysis.Analyzer{buildssa.Analyzer},
+	Requires:   []*analysis.Analyzer{buildssa.Analyzer, fieldtags.Analyzer},
 	ResultType: reflect.TypeOf(new(sourceClassifier)),
 	FactTypes:  []analysis.Fact{new(typeDeclFact), new(fieldDeclFact)},
 }
@@ -86,6 +87,7 @@ var Analyzer = &analysis.Analyzer{
 var Report bool
 
 func run(pass *analysis.Pass) (interface{}, error) {
+	taggedFields := pass.ResultOf[fieldtags.Analyzer].(fieldtags.ResultType)
 	ssaInput := pass.ResultOf[buildssa.Analyzer].(*buildssa.SSA)
 	conf, err := config.ReadConfig()
 	if err != nil {
@@ -95,7 +97,7 @@ func run(pass *analysis.Pass) (interface{}, error) {
 	// Members contains all named entities
 	for _, mem := range ssaInput.Pkg.Members {
 		if ssaType, ok := mem.(*ssa.Type); ok && conf.IsSource(ssaType.Type()) {
-			exportSourceFacts(pass, ssaType, conf)
+			exportSourceFacts(pass, ssaType, conf, taggedFields)
 		}
 	}
 
@@ -107,11 +109,15 @@ func run(pass *analysis.Pass) (interface{}, error) {
 	return classifier, nil
 }
 
-func exportSourceFacts(pass *analysis.Pass, ssaType *ssa.Type, conf *config.Config) {
+func exportSourceFacts(pass *analysis.Pass, ssaType *ssa.Type, conf *config.Config, taggedFields fieldtags.ResultType) {
 	pass.ExportObjectFact(ssaType.Object(), &typeDeclFact{})
 	if under, ok := ssaType.Type().Underlying().(*types.Struct); ok {
 		for i := 0; i < under.NumFields(); i++ {
-			if fld := under.Field(i); conf.IsSourceField(ssaType.Type(), fld) && fld.Pkg() == pass.Pkg {
+			fld := under.Field(i)
+			if fld.Pkg() != pass.Pkg {
+				continue
+			}
+			if conf.IsSourceField(ssaType.Type(), fld) || taggedFields.IsSource(fld) {
 				pass.ExportObjectFact(fld, &fieldDeclFact{})
 			}
 		}


Test patch:
diff --git a/internal/pkg/levee/testdata/src/example.com/tests/extracts/tests.go b/internal/pkg/levee/testdata/src/example.com/tests/extracts/tests.go
new file mode 100644
index 0000000..d457fb5
--- /dev/null
+++ b/internal/pkg/levee/testdata/src/example.com/tests/extracts/tests.go
@@ -0,0 +1,62 @@
+// 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 extracts
+
+import (
+	"example.com/core"
+)
+
+func CreateSource() (core.Source, error) {
+	return core.Source{}, nil
+}
+
+func CreateSourceFlipped() (error, core.Source) {
+	return nil, core.Source{}
+}
+
+func TakeSource(s core.Source) (string, int, interface{}) {
+	return "", 0, nil
+}
+
+func TestOnlySourceExtractIsTainted() {
+	s, err := CreateSource()
+	core.Sink(s) // want "a source has reached a sink"
+	core.Sink(err)
+}
+
+func TestOnlySourceExtractIsTaintedInstructionOrder() {
+	s, err := CreateSource()
+	core.Sink(err)
+	core.Sink(s) // want "a source has reached a sink"
+}
+
+func TestOnlySourceExtractIsTaintedFlipped() {
+	err, s := CreateSourceFlipped()
+	core.Sink(s) // want "a source has reached a sink"
+	core.Sink(err)
+}
+
+func TestOnlySourceExtractIsTaintedInstructionOrderFlipped() {
+	err, s := CreateSourceFlipped()
+	core.Sink(err)
+	core.Sink(s) // want "a source has reached a sink"
+}
+
+func TestExtractsFromCallWithSourceArgAreTainted(s core.Source) {
+	str, i, e := TakeSource(s)
+	core.Sink(str) // want "a source has reached a sink"
+	core.Sink(i)   // want "a source has reached a sink"
+	core.Sink(e)   // want "a source has reached a sink"
+}
diff --git a/internal/pkg/sourcetype/testdata/src/sourcetype/test.go b/internal/pkg/sourcetype/testdata/src/sourcetype/test.go
index 5189af5..b7dd560 100644
--- a/internal/pkg/sourcetype/testdata/src/sourcetype/test.go
+++ b/internal/pkg/sourcetype/testdata/src/sourcetype/test.go
@@ -15,8 +15,10 @@
 package sourcetype
 
 type Source struct { // want Source:"source type"
-	Data string // want Data:"source field"
-	ID   int
+	Data         string // want Data:"source field"
+	Tagged       string `levee:"source"` // want Tagged:"source field"
+	Name1, Name2 string `levee:"source"` // want Name1:"source field" Name2:"source field"
+	ID           int
 }
 
 type AliasStruct = Source // want AliasStruct:"source type"