Repository: google/go-flow-levee
Pull request #145 (2020-10-07 21:09:11)

Do not traverse from an Extract to its Operands
See #142 for context.

This PR re-introduces the behavior of "not traversing to an Extract's Operands". Traversing to an Extract's operands never makes sense because it means we are propagating taint "backwards in time". Indeed, the Extract instruction always comes after the instruction that produced the Tuple that the Extract is extracting a value from. Up to now, we were only avoiding this traversal when the `Operand` is a `Call`.

As extra justification for this change, this PR adds a test that would otherwise fail (involving a `TypeAssert` instead of a `Call`).

Tests + changes for the case that caused the failure on master are here: #146.

- [x] Tests pass
- [x] Appropriate changes to README are included in PR


Patch:
diff --git a/.github/ISSUE_TEMPLATE/bug_report.md b/.github/ISSUE_TEMPLATE/bug_report.md
new file mode 100644
index 0000000..09973bd
--- /dev/null
+++ b/.github/ISSUE_TEMPLATE/bug_report.md
@@ -0,0 +1,19 @@
+---
+name: Bug report
+about: Create a report to help us improve
+title: "[BUG]: "
+labels: bug
+assignees: ''
+
+---
+
+## Bug report
+
+**Describe the bug**
+Please include a clear and concise description of what the bug is.
+
+**To Reproduce**
+Please make it as easy as possible for us to reproduce what you observed. If possible, provide the exact configuration and code on which you were using when you encountered the bug. If the code cannot be shared, please provide a simplified example and confirm that it also exposes the bug.
+
+**Additional context**
+Add any other context about the problem here.
diff --git a/.github/ISSUE_TEMPLATE/false-negative.md b/.github/ISSUE_TEMPLATE/false-negative.md
new file mode 100644
index 0000000..93e816f
--- /dev/null
+++ b/.github/ISSUE_TEMPLATE/false-negative.md
@@ -0,0 +1,28 @@
+---
+name: False negative
+about: Report a false negative.
+title: "[FALSE NEGATIVE]: "
+labels: false negative
+assignees: ''
+
+---
+
+## False negative report
+
+Use this issue template to describe a situation where the analyzer failed to recognize that a piece of unsafe code is unsafe. For example, if the analyzer did not produce a report on the following piece of code, then that would be a false negative:
+
+```go
+func Oops() {
+    Sink(Source{"sensitive data"})
+}
+```
+(We are assuming that `Source` has been configured as a source and `Sink` has been configured as a sink.)
+
+**Describe the issue**
+Please include a clear and concise description of what happened and why you think it is a false negative.
+
+**To Reproduce**
+Please make it as easy as possible for us to reproduce what you observed. If possible, provide the exact configuration and code on which the analyzer failed to produce a report. If the code cannot be shared, please provide a simplified example and confirm that it also contains the false negative.
+
+**Additional context**
+Add any other context about the problem here.
diff --git a/.github/ISSUE_TEMPLATE/false-positive.md b/.github/ISSUE_TEMPLATE/false-positive.md
new file mode 100644
index 0000000..ef1be09
--- /dev/null
+++ b/.github/ISSUE_TEMPLATE/false-positive.md
@@ -0,0 +1,28 @@
+---
+name: False positive
+about: Report a false positive.
+title: "[FALSE POSITIVE]: "
+labels: false positive
+assignees: ''
+
+---
+
+## False positive report
+
+Use this issue template to describe a false positive report produced by the analyzer. A false positive report is a report produced by the analyzer on code that you consider to be safe. For example, if the analyzer were to produce a report on the following piece of code, then that would be a false positive:
+
+```go
+func NothingWrongHere() {
+    Sink(Safe{"not a secret"}) // we don't want a report here, since the value that reached the sink is not sensitive
+}
+```
+(We are assuming that `Sink` has been configured as a sink and that `Safe` has *not* been configured as a source.)
+
+**Describe the issue**
+Please include a clear and concise description of what happened and why you think it is a false positive.
+
+**To Reproduce**
+Please make it as easy as possible for us to reproduce what you observed. If possible, provide the exact configuration and code on which the analyzer failed to produce a report. If the code cannot be shared, please provide a simplified example and confirm that it also yields the false positive report.
+
+**Additional context**
+Add any other context about the problem here.
diff --git a/README.md b/README.md
index c7ff097..7c9d0cd 100644
--- a/README.md
+++ b/README.md
@@ -32,6 +32,16 @@ See [design/](design/README.md).
 
 See [configuration/](configuration/README.md) for configuration details.
 
+## Reporting bugs
+
+Static taint propagation analysis is a hard problem. In fact, it is [undecidable](https://en.wikipedia.org/wiki/Rice%27s_theorem). Concretely, this means two things:
+* False negatives: the analyzer may fail to recognize that a piece of code is unsafe.
+* False positives: the analyzer may incorrectly claim that a safe piece of code is unsafe. 
+
+Since taint propagation is often used as a security safeguard, we care more deeply about false negatives. If you discover unsafe code that the analyzer is not recognizing as unsafe, please open an issue [here](https://github.com/google/go-flow-levee/issues/new?template=false-negative.md). Conversely, fales positives waste developer time and should also be addressed. If the analyzer produces a report for code that you consider to be safe, please open an issue [here](https://github.com/google/go-flow-levee/issues/new?template=false-positive.md).
+
+For general bug reports (e.g. crashes), please open an issue [here](https://github.com/google/go-flow-levee/issues/new?template=bug_report.md).
+
 ### Debugging
 
 The main analyzer depends heavily on the SSA package. Being able to read the SSA code and visualize its graph can be very useful for debugging. In order to generate the SSA code and DOT (graphviz) source for every function in a test, run `go test levee_test.go -debug`. Results are written to the `output` directory. You can generate a PDF from the DOT source using `dot -Tpdf <file> -o "$(basename <file> .dot).pdf"`.
diff --git a/internal/pkg/config/config.go b/internal/pkg/config/config.go
index 7062634..ba24abe 100644
--- a/internal/pkg/config/config.go
+++ b/internal/pkg/config/config.go
@@ -20,6 +20,8 @@ import (
 	"fmt"
 	"go/types"
 	"io/ioutil"
+	"reflect"
+	"strconv"
 	"strings"
 	"sync"
 
@@ -50,21 +52,25 @@ type fieldTagMatcher struct {
 	Val string
 }
 
-func (ftm fieldTagMatcher) matches(key, val string) bool {
-	return ftm.Key == key && ftm.Val == val
-}
-
 // IsSourceFieldTag determines whether a field tag made up of a key and value
 // is a Source.
-func (c Config) IsSourceFieldTag(key, val string) bool {
+func (c Config) IsSourceFieldTag(tag string) bool {
+	if unq, err := strconv.Unquote(tag); err == nil {
+		tag = unq
+	}
+	st := reflect.StructTag(tag)
+
 	// built in
-	if key == "levee" && val == "source" {
+	if st.Get("levee") == "source" {
 		return true
 	}
 	// configured
 	for _, ft := range c.FieldTags {
-		if ft.matches(key, val) {
-			return true
+		val := st.Get(ft.Key)
+		for _, v := range strings.Split(val, ",") {
+			if v == ft.Val {
+				return true
+			}
 		}
 	}
 	return false
diff --git a/internal/pkg/debug/render/ssa.go b/internal/pkg/debug/render/ssa.go
index d8454c1..8f4dfce 100644
--- a/internal/pkg/debug/render/ssa.go
+++ b/internal/pkg/debug/render/ssa.go
@@ -40,7 +40,7 @@ func SSA(f *ssa.Function) string {
 		}
 	}
 
-	for i, blk := range f.Blocks {
+	for i, blk := range f.DomPreorder() {
 		renderBlock(&b, i, blk, maxBlockLength)
 	}
 
diff --git a/internal/pkg/fieldtags/analyzer.go b/internal/pkg/fieldtags/analyzer.go
index 77f4a8e..542d93d 100644
--- a/internal/pkg/fieldtags/analyzer.go
+++ b/internal/pkg/fieldtags/analyzer.go
@@ -71,14 +71,7 @@ func run(pass *analysis.Pass) (interface{}, error) {
 			return
 		}
 		for _, f := range (*s).Fields.List {
-			tags := extractTags(f)
-			isTaggedField := false
-			for _, ft := range tags {
-				if conf.IsSourceFieldTag(ft.key, ft.val) {
-					isTaggedField = true
-				}
-			}
-			if !isTaggedField || len(f.Names) == 0 {
+			if f.Tag == nil || len(f.Names) == 0 || !conf.IsSourceFieldTag(f.Tag.Value) {
 				continue
 			}
 			fNames := make([]string, len(f.Names))
diff --git a/internal/pkg/source/source.go b/internal/pkg/source/source.go
index 531a055..ecbde83 100644
--- a/internal/pkg/source/source.go
+++ b/internal/pkg/source/source.go
@@ -218,7 +218,16 @@ func (s *Source) canReach(start *ssa.BasicBlock, dest *ssa.BasicBlock) bool {
 }
 
 func (s *Source) visitOperands(n ssa.Node, operands []*ssa.Value, maxInstrReached map[*ssa.BasicBlock]int, lastBlockVisited *ssa.BasicBlock) {
-	_, visitingFromExtract := n.(*ssa.Extract)
+	// 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 := n.(*ssa.Extract); ok {
+		return
+	}
 
 	for _, o := range operands {
 		n, ok := (*o).(ssa.Node)
@@ -226,15 +235,6 @@ func (s *Source) visitOperands(n ssa.Node, operands []*ssa.Value, maxInstrReache
 			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


Test patch:
diff --git a/internal/pkg/config/fieldtags_test.go b/internal/pkg/config/fieldtags_test.go
index f1b73ad..c112449 100644
--- a/internal/pkg/config/fieldtags_test.go
+++ b/internal/pkg/config/fieldtags_test.go
@@ -30,41 +30,71 @@ func TestFieldTagsIdentification(t *testing.T) {
 
 	cases := []struct {
 		desc string
-		key  string
-		val  string
+		tag  string
 		want bool
 	}{
 		{
 			"built-in field tag",
-			"levee",
-			"source",
+			"`levee:\"source\"`",
 			true,
 		},
 		{
 			"custom field tag",
-			"example",
-			"sensitive",
+			"`example:\"sensitive\"`",
 			true,
 		},
 		{
 			"different tag key",
-			"notexample",
-			"sensitive",
+			"`notexample:\"sensitive\"`",
 			false,
 		},
 		{
 			"different tag value",
-			"example",
-			"notsensitive",
+			"`example:\"notsensitive\"`",
+			false,
+		},
+		{
+			"escaped tag accepted",
+			`"levee:\"source\""`,
+			true,
+		},
+		{
+			"multiple values, no target",
+			"`example:\"foo,bar,baz\"`",
+			false,
+		},
+		{
+			"multiple values, with target",
+			"`example:\"foo,sensitive,bar\"`",
+			true,
+		},
+		{
+			"multiple key value sets, no target",
+			"`foo:\"bar,baz\" example:\"foo,bar,baz\" fizz:\"bang\"`",
+			false,
+		},
+		{
+			"multiple key value sets, with target",
+			"`foo:\"bar,baz\" example:\"foo,sensitive,bar\"` fizz:\"bang\"",
+			true,
+		},
+		{
+			"empty",
+			"",
+			false,
+		},
+		{
+			"malformed",
+			"`noEndQuote:\"malform",
 			false,
 		},
 	}
 
 	for _, tt := range cases {
 		t.Run(tt.desc, func(t *testing.T) {
-			got := config.IsSourceFieldTag(tt.key, tt.val)
+			got := config.IsSourceFieldTag(tt.tag)
 			if got != tt.want {
-				t.Errorf("config.IsSourceFieldTag(%q, %q) == %v, want %v", tt.key, tt.val, got, tt.want)
+				t.Errorf("config.IsSourceFieldTag(%q) == %v, want %v", tt.tag, got, tt.want)
 			}
 		})
 	}
diff --git a/internal/pkg/debug/render/ssa_test.go b/internal/pkg/debug/render/ssa_test.go
index 399b822..86f2270 100644
--- a/internal/pkg/debug/render/ssa_test.go
+++ b/internal/pkg/debug/render/ssa_test.go
@@ -47,7 +47,7 @@ func TestSSA(t *testing.T) {
 		got := SSA(f)
 
 		if diff := cmp.Diff(want, got); diff != "" {
-			t.Errorf("render.SSA diff (-want +got):\n%s", diff)
+			t.Errorf("render.SSA(%s) diff (-want +got):\n%s", f.Name(), diff)
 		}
 	}
 }
diff --git a/internal/pkg/debug/render/testdata/TestMultiBlock.ssa b/internal/pkg/debug/render/testdata/TestMultiBlock.ssa
index 374c9f7..385ef0f 100644
--- a/internal/pkg/debug/render/testdata/TestMultiBlock.ssa
+++ b/internal/pkg/debug/render/testdata/TestMultiBlock.ssa
@@ -14,17 +14,7 @@ func TestMultiBlock()
 	 1(*ssa.UnOp           ): t7 = *t6
 	 2(*ssa.BinOp          ): t8 = t7 > 0:int
 	 3(*ssa.If             ): if t8 goto 4 else 2
-2: if.done
-	 0(*ssa.Return         ): return
-3: if.else
-	 0(*ssa.Alloc          ): t9 = new [1]interface{} (varargs)
-	 1(*ssa.IndexAddr      ): t10 = &t9[0:int]
-	 2(*ssa.MakeInterface  ): t11 = make interface{} <- string ("somewhere":string)
-	 3(*ssa.Store          ): *t10 = t11
-	 4(*ssa.Slice          ): t12 = slice t9[:]
-	 5(*ssa.Call           ): t13 = fmt.Println(t12...)
-	 6(*ssa.Jump           ): jump 2
-4: if.then
+2: if.then
 	 0(*ssa.FieldAddr      ): t14 = &t0.X [#0]
 	 1(*ssa.UnOp           ): t15 = *t14
 	 2(*ssa.FieldAddr      ): t16 = &t0.Y [#1]
@@ -39,3 +29,13 @@ func TestMultiBlock()
 	11(*ssa.Slice          ): t23 = slice t18[:]
 	12(*ssa.Call           ): t24 = fmt.Printf("in top right quad...":string, t23...)
 	13(*ssa.Jump           ): jump 2
+3: if.done
+	 0(*ssa.Return         ): return
+4: if.else
+	 0(*ssa.Alloc          ): t9 = new [1]interface{} (varargs)
+	 1(*ssa.IndexAddr      ): t10 = &t9[0:int]
+	 2(*ssa.MakeInterface  ): t11 = make interface{} <- string ("somewhere":string)
+	 3(*ssa.Store          ): *t10 = t11
+	 4(*ssa.Slice          ): t12 = slice t9[:]
+	 5(*ssa.Call           ): t13 = fmt.Println(t12...)
+	 6(*ssa.Jump           ): jump 2
diff --git a/internal/pkg/fieldtags/testdata/src/tests/test.go b/internal/pkg/fieldtags/testdata/src/tests/test.go
index 4e244df..511ff3f 100644
--- a/internal/pkg/fieldtags/testdata/src/tests/test.go
+++ b/internal/pkg/fieldtags/testdata/src/tests/test.go
@@ -19,7 +19,7 @@ type Person struct {
 	secret                   string      `json:"secret" levee:"source"` // want "tagged field: secret"
 	another                  interface{} "levee:\"source\""             // want "tagged field: another"
 	hasCustomFieldTag        string      `example:"sensitive"`          // want "tagged field: hasCustomFieldTag"
-	hasTagWithMultipleValues string      `levee:"value0,source,value2"` // want "tagged field: hasTagWithMultipleValues"
+	hasTagWithMultipleValues string      `example:"val,sensitive,long"` // want "tagged field: hasTagWithMultipleValues"
 	name                     string      `some_key:"non_secret"`
 	spaceAfterFinalQuote     string      `key:"value" `
 	someNotTaggedField       int
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
index 4e8873f..1273395 100644
--- a/internal/pkg/levee/testdata/src/example.com/tests/extracts/tests.go
+++ b/internal/pkg/levee/testdata/src/example.com/tests/extracts/tests.go
@@ -30,12 +30,18 @@ func TakeSource(s core.Source) (string, int, interface{}) {
 	return "", 0, nil
 }
 
-func TestOnlySourceExtractIsTainted() {
+func TestOnlySourceExtractIsTaintedFromCall() {
 	s, err := CreateSource()
 	core.Sink(s) // want "a source has reached a sink"
 	core.Sink(err)
 }
 
+func TestOnlySourceExtractIsTaintedFromTypeAssert(p interface{}) {
+	s, ok := p.(core.Source)
+	core.Sink(s) // want "a source has reached a sink"
+	core.Sink(ok)
+}
+
 func TestOnlySourceExtractIsTaintedInstructionOrder() {
 	s, err := CreateSource()
 	core.Sink(err)