Repository: google/go-flow-levee
Pull request #39 (2020-08-05 20:07:15)

Introduce minimal field propagator analyzer
Introduces a (minimal) new analyzer for identifying **field propagators** automatically.

By **field propagators**, I mean any function on a `Source` type that returns a value tainted by a `Source` field. At present the code does not actually cover *all* such cases, but it does the cover the cases that we are currently testing for. More cases will be added in a future PR, and the code will be extended to capture those as well.

Integration with the main analyzer (levee) will come in a future PR, along with additional tests.

- [x] Tests pass
- [x] Appropriate changes to README are included in PR (N/A)


mlevesquedion: Thanks for your comments! I think the code is much more robust now.

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/fieldpropagator/analyzer.go b/internal/pkg/fieldpropagator/analyzer.go
new file mode 100644
index 0000000..c6ae602
--- /dev/null
+++ b/internal/pkg/fieldpropagator/analyzer.go
@@ -0,0 +1,118 @@
+// 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 fieldpropagator implements identification of field propagators.
+// A field propagator is a function that returns a source field.
+package fieldpropagator
+
+import (
+	"go/types"
+	"reflect"
+
+	"github.com/google/go-flow-levee/internal/pkg/config"
+	"golang.org/x/tools/go/analysis"
+	"golang.org/x/tools/go/analysis/passes/buildssa"
+	"golang.org/x/tools/go/ssa"
+)
+
+// ResultType is a map telling whether an object (really a function) is a field propagator.
+type ResultType = map[types.Object]bool
+
+type isFieldPropagator struct{}
+
+func (i isFieldPropagator) AFact() {}
+
+func (i isFieldPropagator) String() string {
+	return "field propagator identified"
+}
+
+var Analyzer = &analysis.Analyzer{
+	Name: "fieldpropagator",
+	Doc: `This analyzer identifies field propagators.
+
+A field propagator is a function that returns a source field.`,
+	Flags:      config.FlagSet,
+	Run:        run,
+	Requires:   []*analysis.Analyzer{buildssa.Analyzer},
+	ResultType: reflect.TypeOf(new(ResultType)).Elem(),
+	FactTypes:  []analysis.Fact{new(isFieldPropagator)},
+}
+
+func run(pass *analysis.Pass) (interface{}, error) {
+	ssaInput := pass.ResultOf[buildssa.Analyzer].(*buildssa.SSA)
+
+	conf, err := config.ReadConfig()
+	if err != nil {
+		return nil, err
+	}
+
+	ssaProg := ssaInput.Pkg.Prog
+	for _, mem := range ssaInput.Pkg.Members {
+		ssaType, ok := mem.(*ssa.Type)
+		if !ok || !conf.IsSource(ssaType.Type()) {
+			continue
+		}
+		methods := ssaProg.MethodSets.MethodSet(ssaType.Type())
+		for i := 0; i < methods.Len(); i++ {
+			meth := ssaProg.MethodValue(methods.At(i))
+			analyzeBlocks(pass, conf, meth)
+		}
+	}
+
+	isFieldPropagator := map[types.Object]bool{}
+	for _, f := range pass.AllObjectFacts() {
+		isFieldPropagator[f.Object] = true
+	}
+	return isFieldPropagator, nil
+}
+
+func analyzeBlocks(pass *analysis.Pass, conf *config.Config, meth *ssa.Function) {
+	// Function does not return anything
+	if res := meth.Signature.Results(); res == nil || (*res).Len() == 0 {
+		return
+	}
+	for _, b := range meth.Blocks {
+		if len(b.Instrs) == 0 {
+			continue
+		}
+		lastInstr := b.Instrs[len(b.Instrs)-1]
+		ret, ok := lastInstr.(*ssa.Return)
+		if !ok {
+			continue
+		}
+		analyzeResults(pass, conf, meth, ret.Results)
+	}
+}
+
+func analyzeResults(pass *analysis.Pass, conf *config.Config, meth *ssa.Function, results []ssa.Value) {
+	for _, r := range results {
+		fa, ok := fieldAddr(r)
+		if !ok {
+			continue
+		}
+		if conf.IsSourceFieldAddr(fa) {
+			pass.ExportObjectFact(meth.Object(), &isFieldPropagator{})
+		}
+	}
+}
+
+func fieldAddr(x ssa.Value) (*ssa.FieldAddr, bool) {
+	switch t := x.(type) {
+	case *ssa.FieldAddr:
+		return t, true
+	case *ssa.UnOp:
+		return fieldAddr(t.X)
+	}
+	return nil, false
+}
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/levee_test.go b/internal/levee_test.go
index 1f5b9f0..b216ef8 100644
--- a/internal/levee_test.go
+++ b/internal/levee_test.go
@@ -15,24 +15,31 @@
 package internal
 
 import (
+	"io/ioutil"
+	"path/filepath"
 	"testing"
 
 	"golang.org/x/tools/go/analysis/analysistest"
 )
 
-var patterns = []string{
-	"example.com/tests/arguments",
-	"example.com/tests/declarations",
-	"example.com/tests/dominance",
-	"example.com/tests/fields",
-	"example.com/tests/receivers",
-	"example.com/tests/sinks",
-}
-
 func TestLevee(t *testing.T) {
-	dir := analysistest.TestData()
-	if err := Analyzer.Flags.Set("config", dir+"/test-config.json"); err != nil {
+	dataDir := analysistest.TestData()
+	testsDir := filepath.Join(dataDir, "src/example.com/tests")
+	patterns := findTestPatterns(t, testsDir)
+	if err := Analyzer.Flags.Set("config", dataDir+"/test-config.json"); err != nil {
 		t.Error(err)
 	}
-	analysistest.Run(t, dir, Analyzer, patterns...)
+	analysistest.Run(t, dataDir, Analyzer, patterns...)
+}
+
+func findTestPatterns(t *testing.T, testsDir string) (patterns []string) {
+	t.Helper()
+	files, err := ioutil.ReadDir(testsDir)
+	if err != nil {
+		t.Fatalf("Failed to read tests dir (%s): %v", testsDir, err)
+	}
+	for _, f := range files {
+		patterns = append(patterns, filepath.Join(testsDir, f.Name()))
+	}
+	return
 }
diff --git a/internal/pkg/fieldpropagator/analyzer_test.go b/internal/pkg/fieldpropagator/analyzer_test.go
new file mode 100644
index 0000000..6dc234d
--- /dev/null
+++ b/internal/pkg/fieldpropagator/analyzer_test.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 fieldpropagator
+
+import (
+	"path/filepath"
+	"testing"
+
+	"github.com/google/go-flow-levee/internal/pkg/config"
+	"golang.org/x/tools/go/analysis/analysistest"
+)
+
+func TestFieldPropagatorAnalysis(t *testing.T) {
+	testdata := analysistest.TestData()
+	if err := config.FlagSet.Set("config", filepath.Join(testdata, "test-config.json")); err != nil {
+		t.Error(err)
+	}
+	analysistest.Run(t, testdata, Analyzer, "source", "test")
+}
diff --git a/internal/pkg/fieldpropagator/testdata/src/source/test.go b/internal/pkg/fieldpropagator/testdata/src/source/test.go
new file mode 100644
index 0000000..931c55a
--- /dev/null
+++ b/internal/pkg/fieldpropagator/testdata/src/source/test.go
@@ -0,0 +1,66 @@
+// 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 source
+
+type Source struct {
+	data    string
+	dataPtr *string
+	id      int
+}
+
+func (s Source) ID() int {
+	return s.id
+}
+
+func (s Source) Data() string { // want Data:"field propagator identified"
+	return s.data
+}
+
+func (s Source) DataRef() *string { // want DataRef:"field propagator identified"
+	return &s.data
+}
+
+func (s Source) DataPtr() *string { // want DataPtr:"field propagator identified"
+	return s.dataPtr
+}
+
+func (s Source) DataDeref() string { // want DataDeref:"field propagator identified"
+	return *s.dataPtr
+}
+
+var isAdmin bool
+
+func (s Source) MaybeData() string { // want MaybeData:"field propagator identified"
+	if isAdmin {
+		return s.data
+	}
+	return "<redacted>"
+}
+
+func (s Source) TryGetData() (string, error) { // want TryGetData:"field propagator identified"
+	return s.data, nil
+}
+
+func New(data string) Source {
+	return Source{data: data, id: 0}
+}
+
+type NotSource struct {
+	data string
+}
+
+func (n NotSource) Data() string {
+	return n.data
+}
diff --git a/internal/pkg/fieldpropagator/testdata/src/test/test.go b/internal/pkg/fieldpropagator/testdata/src/test/test.go
new file mode 100644
index 0000000..82f8638
--- /dev/null
+++ b/internal/pkg/fieldpropagator/testdata/src/test/test.go
@@ -0,0 +1,23 @@
+// 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 test
+
+import "source"
+
+func Test() {
+	s := source.New("secret")
+	d := s.Data()
+	_ = d
+}
diff --git a/internal/pkg/fieldpropagator/testdata/test-config.json b/internal/pkg/fieldpropagator/testdata/test-config.json
new file mode 100644
index 0000000..e06512a
--- /dev/null
+++ b/internal/pkg/fieldpropagator/testdata/test-config.json
@@ -0,0 +1,9 @@
+{
+  "Sources": [
+    {
+      "PackageRE": "source",
+      "TypeRE": "^Source$",
+      "FieldRE": "^data"
+    }
+  ]
+}
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": [