Repository: google/go-flow-levee
Pull request #28 (2020-06-26 20:47:30)

Remove dependency of the index-based testing approach of Sources.
Remove dependency of the index-based testing approach of Sources.

The key idea is to use the String representation of a Source in the corresponding "want' comment, where the String representation is reduced to the the expected propagators, sanitizers and sinks attached to the source in question.


Patch:
diff --git a/go.mod b/go.mod
index 7a00737..34f01d8 100644
--- a/go.mod
+++ b/go.mod
@@ -2,7 +2,4 @@ module github.com/google/go-flow-levee
 
 go 1.14
 
-require (
-	github.com/eapache/queue v1.1.0
-	golang.org/x/tools v0.0.0-20200416214402-fc959738d646
-)
+require golang.org/x/tools v0.0.0-20200416214402-fc959738d646
diff --git a/go.sum b/go.sum
index 934933c..f91eab3 100644
--- a/go.sum
+++ b/go.sum
@@ -1,5 +1,3 @@
-github.com/eapache/queue v1.1.0 h1:YOEu7KNc61ntiQlcEeUIoDTJ2o8mQznoNvUhiigpIqc=
-github.com/eapache/queue v1.1.0/go.mod h1:6eCeP0CKFpHLu8blIFXhExK/dRa7WDZfr6jVFPTqq+I=
 github.com/yuin/goldmark v1.1.27/go.mod h1:3hX8gzYuyVAZsxl0MRgGTJEmQBFcNTphYh9decYSb74=
 golang.org/x/crypto v0.0.0-20190308221718-c2843e01d9a2/go.mod h1:djNgcEr1/C05ACkg1iLfiJU5Ep61QUkGW8qpdssI0+w=
 golang.org/x/crypto v0.0.0-20191011191535-87dc89f01550/go.mod h1:yigFU9vqHzYiE8UmvKecakEJjdnWj3jj499lnFckfCI=
diff --git a/internal/pkg/source/source.go b/internal/pkg/source/source.go
index 82248ca..adbe4f6 100644
--- a/internal/pkg/source/source.go
+++ b/internal/pkg/source/source.go
@@ -20,7 +20,6 @@ import (
 	"go/types"
 	"strings"
 
-	"github.com/eapache/queue"
 	"github.com/google/go-flow-levee/internal/pkg/sanitizer"
 	"github.com/google/go-flow-levee/internal/pkg/utils"
 	"golang.org/x/tools/go/analysis/passes/buildssa"
@@ -41,6 +40,7 @@ type classifier interface {
 type Source struct {
 	node       ssa.Node
 	marked     map[ssa.Node]bool
+	preOrder   []ssa.Node
 	sanitizers []*sanitizer.Sanitizer
 	config     classifier
 }
@@ -57,55 +57,61 @@ func New(in ssa.Node, config classifier) *Source {
 		marked: make(map[ssa.Node]bool),
 		config: config,
 	}
-	a.bfs()
+	a.dfs(in)
 	return a
 }
 
-// bfs performs Breadth-First-Search on the def-use graph of the input Source.
+// dfs performs Depth-First-Search on the def-use graph of the input Source.
 // While traversing the graph we also look for potential sanitizers of this Source.
 // If the Source passes through a sanitizer, bfs does not continue through that Node.
-func (a *Source) bfs() {
-	q := queue.New()
-	q.Add(a.node)
-	a.marked[a.node] = true
+func (a *Source) dfs(n ssa.Node) {
+	a.preOrder = append(a.preOrder, n)
+	a.marked[n.(ssa.Node)] = true
 
-	for q.Length() > 0 {
-		e := q.Remove().(ssa.Node)
+	if n.Referrers() == nil {
+		return
+	}
 
-		if e.Referrers() == nil {
+	for _, r := range *n.Referrers() {
+		if a.marked[r.(ssa.Node)] {
 			continue
 		}
 
-		for _, r := range *e.Referrers() {
-			if _, ok := a.marked[r.(ssa.Node)]; ok {
+		switch v := r.(type) {
+		case *ssa.Call:
+			// This is to avoid attaching calls where the source is the receiver, ex:
+			// core.Sinkf("Source id: %v", wrapper.Source.GetID())
+			if v.Call.Signature().Recv() != nil {
 				continue
 			}
 
-			// TODO(immutableT) We are putting too much logic into this function - it should just
-			// be constructing a graph. Add specialized methods that know how to trim or interpret
-			// connections.
-
-			switch v := r.(type) {
-			case *ssa.Call:
-				// This is to avoid attaching calls where the source is the receiver, ex:
-				// core.Sinkf("Source id: %v", wrapper.Source.GetID())
-				if v.Call.Signature().Recv() != nil {
-					continue
-				}
-
-				if a.config.IsSanitizer(v) {
-					a.sanitizers = append(a.sanitizers, &sanitizer.Sanitizer{Call: v})
-				}
-			case *ssa.FieldAddr:
-				if !a.config.IsSourceFieldAddr(v) {
-					continue
-				}
+			if a.config.IsSanitizer(v) {
+				a.sanitizers = append(a.sanitizers, &sanitizer.Sanitizer{Call: v})
 			}
+		case *ssa.FieldAddr:
+			if !a.config.IsSourceFieldAddr(v) {
+				continue
+			}
+		}
 
-			a.marked[r.(ssa.Node)] = true
-			q.Add(r)
+		a.dfs(r.(ssa.Node))
+	}
+}
+
+// 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
+// is, it is also removed.
+func (a *Source) compress() []ssa.Node {
+	var compressed []ssa.Node
+	for _, n := range a.preOrder {
+		switch n.(type) {
+		case *ssa.Call:
+			compressed = append(compressed, n)
 		}
 	}
+
+	return compressed
 }
 
 // HasPathTo returns true when a Node is part of declaration-use graph.
@@ -127,21 +133,8 @@ func (a *Source) IsSanitizedAt(call ssa.Instruction) bool {
 // String implements Stringer interface.
 func (a *Source) String() string {
 	var b strings.Builder
-	fmt.Fprintf(&b, "%v\n", a.node.String())
-
-	fmt.Fprint(&b, "Connections:\n")
-	for k := range a.marked {
-		fmt.Fprintf(&b, "\t%v : %T\n", k.String(), k)
-	}
-
-	fmt.Fprint(&b, "Referrers:\n")
-	for _, k := range *a.node.Referrers() {
-		fmt.Fprintf(&b, "\t%v : %T\n", k.String(), k)
-	}
-
-	fmt.Fprint(&b, "Sanitizers:\n")
-	for _, k := range a.sanitizers {
-		fmt.Fprintf(&b, "\t%v : %T\n", k.Call, k)
+	for _, n := range a.compress() {
+		b.WriteString(fmt.Sprintf("%v ", n))
 	}
 
 	return b.String()


Test patch:
diff --git a/internal/pkg/source/source_test.go b/internal/pkg/source/source_test.go
index ca43551..5870dda 100644
--- a/internal/pkg/source/source_test.go
+++ b/internal/pkg/source/source_test.go
@@ -16,7 +16,6 @@ package source
 
 import (
 	"go/types"
-	"reflect"
 	"regexp"
 	"testing"
 
@@ -29,13 +28,21 @@ import (
 )
 
 type testConfig struct {
+	sourcePattern      string
 	propagatorsPattern string
 	fieldsPattern      string
 	sanitizerPattern   string
 }
 
 func (c *testConfig) IsSource(t types.Type) bool {
-	return true
+	d := utils.Dereference(t)
+	_, ok := d.(*types.Named)
+	if !ok {
+		return false
+	}
+
+	match, _ := regexp.MatchString(c.sourcePattern, d.String())
+	return match
 }
 
 func (c *testConfig) IsSanitizer(call *ssa.Call) bool {
@@ -53,127 +60,56 @@ func (c *testConfig) IsSourceFieldAddr(field *ssa.FieldAddr) bool {
 	return match
 }
 
-type analyzerResult struct {
-	allocations []*ssa.Alloc
-	calls       []*ssa.Call
-	fieldAddr   []*ssa.FieldAddr
-	store       []*ssa.Store
-}
-
 var testAnalyzer = &analysis.Analyzer{
-	Name:       "source",
-	Run:        runTest,
-	Doc:        "test harness for the logic related to sources",
-	Requires:   []*analysis.Analyzer{buildssa.Analyzer},
-	ResultType: reflect.TypeOf(analyzerResult{}),
+	Name:     "source",
+	Run:      runTest,
+	Doc:      "test harness for the logic related to sources",
+	Requires: []*analysis.Analyzer{buildssa.Analyzer},
 }
 
 func runTest(pass *analysis.Pass) (interface{}, error) {
 	in := pass.ResultOf[buildssa.Analyzer].(*buildssa.SSA)
-	var result analyzerResult
-	for _, fn := range in.SrcFuncs {
-		for _, b := range fn.Blocks {
-			for _, i := range b.Instrs {
-				switch v := i.(type) {
-				case *ssa.Alloc:
-					result.allocations = append(result.allocations, v)
-				case *ssa.Call:
-					result.calls = append(result.calls, v)
-				case *ssa.FieldAddr:
-					result.fieldAddr = append(result.fieldAddr, v)
-				case *ssa.Store:
-					result.store = append(result.store, v)
-				}
+	config := &testConfig{
+		sourcePattern:      `\.foo`,
+		propagatorsPattern: "propagator",
+		sanitizerPattern:   "sanitizer",
+		fieldsPattern:      "name",
+	}
+
+	sm := identify(config, in)
+	for _, f := range sm {
+		for _, s := range f {
+			if s.String() != "" {
+				pass.Reportf(s.node.Pos(), s.String())
 			}
 		}
 	}
 
-	return result, nil
+	return nil, nil
 }
 
 func TestSource(t *testing.T) {
 	dir := analysistest.TestData()
-	config := &testConfig{
-		propagatorsPattern: "propagator",
-		sanitizerPattern:   "sanitizer",
-		fieldsPattern:      "name",
-	}
-
 	testCases := []struct {
-		pattern                      string
-		config                       *testConfig
-		wantCallConnectionIdx        []int
-		wantSanitizedCallIdx         []int
-		wantFieldAccessConnectionIdx []int
-		wantStoreConnectionIdx       []int
+		pattern string
 	}{
 		{
-			pattern:                      "allocation",
-			config:                       config,
-			wantStoreConnectionIdx:       []int{0},
-			wantFieldAccessConnectionIdx: []int{0},
+			pattern: "allocation",
 		},
 		{
-			pattern:                      "propagation",
-			config:                       config,
-			wantCallConnectionIdx:        []int{0},
-			wantFieldAccessConnectionIdx: []int{0},
+			pattern: "propagation",
 		},
 		{
-			pattern:                      "sanitization",
-			config:                       config,
-			wantFieldAccessConnectionIdx: []int{0},
-			wantSanitizedCallIdx:         []int{1},
+			pattern: "sanitization",
 		},
 		{
-			pattern:               "domination",
-			config:                config,
-			wantCallConnectionIdx: []int{2},
+			pattern: "domination",
 		},
 	}
 
 	for _, tt := range testCases {
 		t.Run(tt.pattern, func(t *testing.T) {
-			r := analysistest.Run(t, dir, testAnalyzer, tt.pattern)
-			if len(r) != 1 {
-				t.Fatalf("Got len(result) == %d, want 1", len(r))
-			}
-
-			a, ok := r[0].Result.(analyzerResult)
-			if !ok {
-				t.Fatalf("Got result of type %T, wanted analyzerResult", a)
-			}
-
-			if len(a.allocations) == 0 {
-				t.Fatal("Got 0 allocations want at least one")
-			}
-
-			src := New(a.allocations[0], tt.config)
-			t.Logf("Testing source:\n%v", src)
-
-			for i := 0; i < len(tt.wantCallConnectionIdx); i++ {
-				if !src.HasPathTo(a.calls[tt.wantCallConnectionIdx[i]]) {
-					t.Errorf("Expected\n%v to have a path to %v", src, a.calls[i])
-				}
-			}
-
-			for i := 0; i < len(tt.wantSanitizedCallIdx); i++ {
-				if !src.IsSanitizedAt(a.calls[tt.wantSanitizedCallIdx[i]]) {
-					t.Errorf("Expected\n%v to be sanitized befere a call to %v", src, a.calls[i])
-				}
-			}
-
-			for i := 0; i < len(tt.wantStoreConnectionIdx); i++ {
-				if !src.HasPathTo(a.store[i]) {
-					t.Errorf("Expected\n%v to have a path to %v", src, a.store[i])
-				}
-			}
-
-			for i := 0; i < len(tt.wantFieldAccessConnectionIdx); i++ {
-				if !src.HasPathTo(a.fieldAddr[i]) {
-					t.Fatalf("Expected\n%v to have a path to %v", src, a.fieldAddr[i])
-				}
-			}
+			analysistest.Run(t, dir, testAnalyzer, tt.pattern)
 		})
 	}
 }
diff --git a/internal/pkg/source/testdata/src/allocation/test.go b/internal/pkg/source/testdata/src/allocation/test.go
index 78d026c..a2d9918 100644
--- a/internal/pkg/source/testdata/src/allocation/test.go
+++ b/internal/pkg/source/testdata/src/allocation/test.go
@@ -14,26 +14,14 @@
 
 package allocation
 
-import (
-	"fmt"
-)
-
 type foo struct {
 	name string
 }
 
 func f1() {
-	f := &foo{name: "bar"}
-
-	// Since f will exit ths scope of f1, log will not be added to the graph of f.
-	// Expected graph:
-	// new foo (complit) : *ssa.Alloc
-	// &t0.name [#0] : *ssa.FieldAddr
-	// *t1 = "bar":string : *ssa.Store
-
+	f := &foo{name: "bar"} // want "log"
 	log(f)
 }
 
 func log(in *foo) {
-	fmt.Printf("Logging foo: %v", in)
 }
diff --git a/internal/pkg/source/testdata/src/domination/test.go b/internal/pkg/source/testdata/src/domination/test.go
index 2aee36e..d0bf650 100644
--- a/internal/pkg/source/testdata/src/domination/test.go
+++ b/internal/pkg/source/testdata/src/domination/test.go
@@ -25,7 +25,7 @@ type foo struct {
 }
 
 func f1() {
-	f := &foo{name: "n", password: "p"}
+	f := &foo{name: "n", password: "p"} // want `sanitizer\(t0\) sink\(t0\) `
 	if time.Now().Year() == 2020 {
 		sanitizer(f)
 	}
diff --git a/internal/pkg/source/testdata/src/propagation/test.go b/internal/pkg/source/testdata/src/propagation/test.go
index 46e1895..3843343 100644
--- a/internal/pkg/source/testdata/src/propagation/test.go
+++ b/internal/pkg/source/testdata/src/propagation/test.go
@@ -21,11 +21,11 @@ type foo struct {
 }
 
 func f1() {
-	f := &foo{name: "bar"}
+	f := &foo{name: "bar"} // want "propagator"
 	transformedFoo := propagator(f)
 	fmt.Println(transformedFoo)
 }
 
 func propagator(in *foo) string {
-	return fmt.Sprintf("Transformed foo: %v", in)
+	return in.name + "transformed"
 }
diff --git a/internal/pkg/source/testdata/src/sanitization/test.go b/internal/pkg/source/testdata/src/sanitization/test.go
index b791dec..d95c7aa 100644
--- a/internal/pkg/source/testdata/src/sanitization/test.go
+++ b/internal/pkg/source/testdata/src/sanitization/test.go
@@ -22,7 +22,7 @@ type foo struct {
 }
 
 func f1() {
-	f := &foo{name: "n", password: "p"}
+	f := &foo{name: "n", password: "p"} // want "sanitizer"
 	sanitizer(f)
 	fmt.Println(f)
 }