Repository: google/go-flow-levee
Pull request #38 (2020-08-03 14:13:12)

Handle slices
This PR adds support for propagating taint to slices in order to report "a source has reached a sink" when a slice containing a tainted value gets sinked.

In order to propagate the taint to slices, we need to DFS into the operands of nodes.

I have also modified the source analyzer to not visit sink functions. This was required to prevent a spurious diagnostic in the "domination" test.

- [x] Tests pass
- [x] Appropriate changes to README are included in PR (N/A)

PurelyApplied: Please don't force pushes onto an open PR.  The various `View Changes` links in comment threads are now broken.
mlevesquedion: Gotcha.

(It seemed like the simpler path in the moment, I didn't know it would break those links.)

Patch:
diff --git a/internal/pkg/config/config.go b/internal/pkg/config/config.go
index 117ecb2..db4e78a 100644
--- a/internal/pkg/config/config.go
+++ b/internal/pkg/config/config.go
@@ -84,6 +84,16 @@ func (c Config) IsSink(call *ssa.Call) bool {
 	return false
 }
 
+func (c Config) IsSinkFunction(f *ssa.Function) bool {
+	for _, p := range c.Sinks {
+		if p.MethodRE.MatchString(f.Name()) {
+			return true
+		}
+	}
+
+	return false
+}
+
 func (c Config) IsSanitizer(call *ssa.Call) bool {
 	for _, p := range c.Sanitizers {
 		if p.Match(call) {
diff --git a/internal/pkg/source/source.go b/internal/pkg/source/source.go
index dbf5e83..eae79fa 100644
--- a/internal/pkg/source/source.go
+++ b/internal/pkg/source/source.go
@@ -31,6 +31,7 @@ type classifier interface {
 	IsSanitizer(*ssa.Call) bool
 	IsPropagator(*ssa.Call) bool
 	IsSourceFieldAddr(*ssa.FieldAddr) bool
+	IsSinkFunction(fn *ssa.Function) bool
 }
 
 // Source represents a Source in an SSA call tree.
@@ -68,15 +69,22 @@ func (a *Source) dfs(n ssa.Node) {
 	a.preOrder = append(a.preOrder, n)
 	a.marked[n.(ssa.Node)] = true
 
-	if n.Referrers() == nil {
-		return
+	if n.Referrers() != nil {
+		a.visitReferrers(n.Referrers())
 	}
 
-	for _, r := range *n.Referrers() {
+	var operands []*ssa.Value
+	operands = n.Operands(operands)
+	if operands != nil {
+		a.visitOperands(operands)
+	}
+}
+
+func (a *Source) visitReferrers(referrers *[]ssa.Instruction) {
+	for _, r := range *referrers {
 		if a.marked[r.(ssa.Node)] {
 			continue
 		}
-
 		switch v := r.(type) {
 		case *ssa.Call:
 			// This is to avoid attaching calls where the source is the receiver, ex:
@@ -84,7 +92,6 @@ func (a *Source) dfs(n ssa.Node) {
 			if v.Call.Signature().Recv() != nil {
 				continue
 			}
-
 			if a.config.IsSanitizer(v) {
 				a.sanitizers = append(a.sanitizers, &sanitizer.Sanitizer{Call: v})
 			}
@@ -93,11 +100,23 @@ func (a *Source) dfs(n ssa.Node) {
 				continue
 			}
 		}
-
 		a.dfs(r.(ssa.Node))
 	}
 }
 
+func (a *Source) visitOperands(operands []*ssa.Value) {
+	for _, o := range operands {
+		n, ok := (*o).(ssa.Node)
+		if !ok || a.marked[n] {
+			continue
+		}
+		al, ok := (*o).(*ssa.Alloc)
+		if !ok || al.Comment == "slicelit" || a.config.IsSource(al.Type()) {
+			a.dfs(n)
+		}
+	}
+}
+
 // 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
@@ -148,6 +167,11 @@ func identify(conf classifier, ssaInput *buildssa.SSA) map[*ssa.Function][]*Sour
 	sourceMap := make(map[*ssa.Function][]*Source)
 
 	for _, fn := range ssaInput.SrcFuncs {
+		// no need to analyze the body of sinks
+		if conf.IsSinkFunction(fn) {
+			continue
+		}
+
 		var sources []*Source
 		sources = append(sources, sourcesFromParams(fn, conf)...)
 		sources = append(sources, sourcesFromClosure(fn, conf)...)


Test patch:
diff --git a/internal/pkg/source/source_test.go b/internal/pkg/source/source_test.go
index 5870dda..57d7acf 100644
--- a/internal/pkg/source/source_test.go
+++ b/internal/pkg/source/source_test.go
@@ -32,6 +32,7 @@ type testConfig struct {
 	propagatorsPattern string
 	fieldsPattern      string
 	sanitizerPattern   string
+	sinkPattern        string
 }
 
 func (c *testConfig) IsSource(t types.Type) bool {
@@ -60,6 +61,11 @@ func (c *testConfig) IsSourceFieldAddr(field *ssa.FieldAddr) bool {
 	return match
 }
 
+func (c *testConfig) IsSinkFunction(f *ssa.Function) bool {
+	match, _ := regexp.MatchString(c.sinkPattern, f.Name())
+	return match
+}
+
 var testAnalyzer = &analysis.Analyzer{
 	Name:     "source",
 	Run:      runTest,
@@ -74,6 +80,7 @@ func runTest(pass *analysis.Pass) (interface{}, error) {
 		propagatorsPattern: "propagator",
 		sanitizerPattern:   "sanitizer",
 		fieldsPattern:      "name",
+		sinkPattern:        "sink",
 	}
 
 	sm := identify(config, in)
diff --git a/internal/pkg/varargs/varargs_test.go b/internal/pkg/varargs/varargs_test.go
index ffea747..042eb31 100644
--- a/internal/pkg/varargs/varargs_test.go
+++ b/internal/pkg/varargs/varargs_test.go
@@ -49,6 +49,10 @@ func (c *testConfig) IsSourceFieldAddr(field *ssa.FieldAddr) bool {
 	return false
 }
 
+func (c *testConfig) IsSinkFunction(f *ssa.Function) bool {
+	return false
+}
+
 type analyzerResult struct {
 	allocations []*ssa.Alloc
 	calls       []*ssa.Call
diff --git a/internal/testdata/src/example.com/tests/collections/tests.go b/internal/testdata/src/example.com/tests/collections/tests.go
new file mode 100644
index 0000000..859996e
--- /dev/null
+++ b/internal/testdata/src/example.com/tests/collections/tests.go
@@ -0,0 +1,28 @@
+// 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 collections
+
+import (
+	"example.com/core"
+)
+
+func TestSlices(s core.Source) {
+	slice := []core.Source{s}
+	core.Sink(slice)                      // want "a source has reached a sink"
+	core.Sink([]core.Source{s})           // want "a source has reached a sink"
+	core.Sink([]interface{}{s})           // want "a source has reached a sink"
+	core.Sink([]interface{}{0, "", s})    // want "a source has reached a sink"
+	core.Sink([]interface{}{0, "", s}...) // want "a source has reached a sink"
+}
diff --git a/internal/testdata/src/example.com/tests/propagation/tests.go b/internal/testdata/src/example.com/tests/propagation/tests.go
new file mode 100644
index 0000000..435464c
--- /dev/null
+++ b/internal/testdata/src/example.com/tests/propagation/tests.go
@@ -0,0 +1,40 @@
+// 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 propagation
+
+import (
+	"fmt"
+
+	"example.com/core"
+)
+
+func Identity(arg interface{}) interface{} {
+	return arg
+}
+
+func TestIdentityPropagator(s core.Source) {
+	i := Identity(s)
+	core.Sink(i)           // want "a source has reached a sink"
+	core.Sink(Identity(s)) // want "a source has reached a sink"
+}
+
+func ToString(arg interface{}) string {
+	return fmt.Sprintf("%v", arg)
+}
+
+func TestToStringPropagator(s core.Source) {
+	v := ToString(s)
+	core.Sink(v) // want "a source has reached a sink"
+}
diff --git a/internal/testdata/src/example.com/tests/sinks/tests.go b/internal/testdata/src/example.com/tests/sinks/tests.go
index 0c753c2..18f30f1 100644
--- a/internal/testdata/src/example.com/tests/sinks/tests.go
+++ b/internal/testdata/src/example.com/tests/sinks/tests.go
@@ -25,9 +25,6 @@ func TestSinks(s core.Source, writer io.Writer) {
 	core.Sinkf("a source: %v", s) // want "a source has reached a sink"
 	core.FSinkf(writer, s)        // want "a source has reached a sink"
 	core.OneArgSink(s)            // want "a source has reached a sink"
-
-	core.Sink([]interface{}{s, s, s}...) // want "a source has reached a sink"
-	core.Sink([]interface{}{s, s, s})    // TODO want "a source has reached a sink"
 }
 
 func TestSinksWithRef(s *core.Source, writer io.Writer) {
@@ -35,9 +32,6 @@ func TestSinksWithRef(s *core.Source, writer io.Writer) {
 	core.Sinkf("a source: %v", s) // want "a source has reached a sink"
 	core.FSinkf(writer, s)        // want "a source has reached a sink"
 	core.OneArgSink(s)            // want "a source has reached a sink"
-
-	core.Sink([]interface{}{s, s, s}...) // want "a source has reached a sink"
-	core.Sink([]interface{}{s, s, s})    // TODO want "a source has reached a sink"
 }
 
 func TestSinksInnocuous(innoc core.Innocuous, writer io.Writer) {
diff --git a/internal/testdata/test-config.json b/internal/testdata/test-config.json
index 67e634c..340cb40 100644
--- a/internal/testdata/test-config.json
+++ b/internal/testdata/test-config.json
@@ -9,7 +9,7 @@
   "Sinks": [
     {
       "PackageRE": "^example.com/core$",
-      "MethodRE": "Sink"
+      "MethodRE": "Sinkf?$"
     }
   ],
   "Sanitizers": [