Repository: google/go-flow-levee
Pull request #63 (2020-08-25 18:55:55)

Take instruction order into account when visiting calls
## The bug
Currently, the analyzer does not differentiate between the following two (abstract) scenarios:
1. Bad
```
taint(value)
sink(value)
```
2. Ok
```
sink(value)
taint(value)
```
Specifically, in this second case, a diagnostic is produced at the `sink` call, even though the `value` has not yet been `taint`ed. This is because we rely mostly on the SSA value graph to determine if a source reaches a sink, and that graph has no concept of the "order" of instructions: it only contains `Referrers`/`Operands` relationships.

## The fix
While traversing from a `Source`, for each `ssa.BasicBlock`, we keep track of the max index of an instruction visited within it. 
When we visit an instruction, we find its index in its block and update the max seen so far if necessary. When we encounter a `Call` instruction, we check that it is higher than the current max for its block, i.e. that it occurs after the value that led us to the call was tainted.

## Future PR's
The solution proposed here only works for single-block functions. If a function has multiple blocks, in most cases this approach will not work as is, so I will need to extend it in a future PR.

- [x] Tests pass
- [x] Appropriate changes to README are included in PR

immutableT: Do you think it would be possible to leverage SSA's dominance to answer the question of whether a taint instruction dominates the sink instruction.
In other words, could we use the same pattern for exempting a sink if it was sanitized?
mlevesquedion: I originally thought of using dominance, but then I ran into some issues which made me look for a simpler way. I think certainly dominance could be used in some way, especially in the multi-block case. For example, we could check that at least one "tainting instruction" dominates the call to a sink. However, the problem is that the `Call` instruction can easily end up sandwiched between "tainting" instructions:
```
0: entry
	// top bun
	0(*ssa.Alloc          ): t0 = local example.com/core.Source (s)
	1(*ssa.Store          ): *t0 = s

	// sandwich contents
	2(*ssa.Alloc          ): t1 = new [1]interface{} (varargs)
	3(*ssa.IndexAddr      ): t2 = &t1[0:int]
	4(*ssa.ChangeInterface): t3 = change interface interface{} <- io.Writer (w)
	5(*ssa.Store          ): *t2 = t3
	6(*ssa.Slice          ): t4 = slice t1[:]
	7(*ssa.Call           ): t5 = example.com/core.Sink(t4...)
 
	// bottom bun
	8(*ssa.UnOp           ): t6 = *t0
	9(*ssa.Alloc          ): t7 = new [1]interface{} (varargs)
	10(*ssa.IndexAddr      ): t8 = &t7[0:int]
	11(*ssa.MakeInterface  ): t9 = make interface{} <- example.com/core.Source (t6)
	12(*ssa.Store          ): *t8 = t9
	13(*ssa.Slice          ): t10 = slice t7[:]
	14(*ssa.Call           ): t11 = fmt.Fprintf(w, "%v":string, t10...)
	15(*ssa.Extract        ): t12 = extract t11 #0
	16(*ssa.Extract        ): t13 = extract t11 #1
	17(*ssa.Return         ): return
```
The tainting instructions at the top dominate the call, but they actually have nothing to do with it. So we would need to find what values are involved in the call, and only consider the tainting instructions that also involve those values (which in this case, are at the bottom and do not dominate the call). So the problem becomes "what values are involved in the call"? In general, figuring that out also requires a graph traversal (e.g. here it is not immediate that the call to `Sink` involves the `Writer` `w`, because of the varargs), and I'm worried that it could get convoluted and that we might end up running in circles: when trying to find what values go into a call, how do we know when to stop? If we don't stop "early enough", we'll end up back at the `Source` value, and then we'll consider the instructions at the top to be using the same values as those the call uses, and we'll incorrectly assume that the call is dominated.

I think for now, it is simpler to use the approach I propose in the current PR. Handling the multi-block elegantly will require more 
immutableT: Could you please add the original Go code for the example above.
mlevesquedion: Certainly, here it is:
```go
func TestSinkBeforeTainting(s core.Source, w io.Writer) {
	core.Sink(w)
	_, _ = fmt.Fprintf(w, "%v", s)
}
```
mlevesquedion: Looking at the SSA graph, I think finding the values + instructions involving the values might not be so difficult after all:
![image](https://user-images.githubusercontent.com/28677454/91232108-722e3780-e6fc-11ea-99b7-4a702692ac65.png)

Starting from the call to `Sink` on the left:
![image](https://user-images.githubusercontent.com/28677454/91232141-840fda80-e6fc-11ea-9612-e71ba77097c7.png)

If we traverse through `Instructions` and we stop traversing when we hit `Value`s, that will allow us to find `w`:
![image](https://user-images.githubusercontent.com/28677454/91232209-a6a1f380-e6fc-11ea-9bac-e450ef39f4ed.png)

Then, we could ask `w` for its `Referrers`, which would allow us to find the call to `Fprintf`:
![image](https://user-images.githubusercontent.com/28677454/91232191-9ee24f00-e6fc-11ea-9fd4-fb9d803d2f53.png)

Asking whether `Fprintf` dominates the call to `Sink` would give us the answer we want.

I think this is more likely to scale than the approach using block indexes that I am proposing here. There might be problems that I don't see right now, but this is promising enough that I want to give it a shot.

Thanks! I'll try implementing this tomorrow morning and we'll see what happens.
PurelyApplied: > Do you think it would be possible to leverage SSA's dominance to answer the question of whether a taint instruction dominates the sink instruction.

We are interested in the inverse, are we not?  If there exists a taint-path, regardless of whether or not that instruction dominates a sink call, we want to report it.

```golang
func Foo(s Source) {
  var st string
  if time.Now().Day == 0 {
    st := fmt.Sprintf("%v", s)
  }
  Sink(st)
}
```

I think dominance will only come into play when we're examining sanitization.
mlevesquedion: > The tainting of st does not dominate the sink instruction, but we still should report a Diagnostic. I think dominance will only come into play when we're examining sanitization.

It doesn't? Intuitively, if we've made it into the `if`, then we have no choice but to get through the `sink` call once we leave the `if`.
mlevesquedion: If I tweak your example a little:
```
func Foo(s Source) {
  st := fmt.Sprintf("%v", s)
  if time.Now().Day() == 0 {
    Sink(st)
  }
}
```
The call to `Sink` here is not dominated by the tainting of `st`, so we would fail to produce a report.

With this in mind, I think I'm going to hold off until the next PR, where I'll look into this more deeply as I add test cases for multi-block functions.

Patch:
diff --git a/internal/pkg/config/config.go b/internal/pkg/config/config.go
index 6d3851a..58a4379 100644
--- a/internal/pkg/config/config.go
+++ b/internal/pkg/config/config.go
@@ -53,12 +53,25 @@ func (c Config) IsSink(call *ssa.Call) bool {
 }
 
 func (c Config) IsSinkFunction(f *ssa.Function) bool {
+	// according to the documentation for ssa.Function, this can happen if
+	// f is a "shared func", e.g. "wrappers and error.Error"
+	if f.Pkg == nil {
+		return false
+	}
+
+	var recvName string
+	if recv := f.Signature.Recv(); recv != nil {
+		recvName = recv.Type().String()
+	}
+
 	for _, p := range c.Sinks {
-		if p.MethodRE.MatchString(f.Name()) {
+		if !p.PackageRE.MatchString(f.Pkg.Pkg.Path()) || !p.MethodRE.MatchString(f.Name()) {
+			continue
+		}
+		if p.ReceiverRE.MatchString(recvName) {
 			return true
 		}
 	}
-
 	return false
 }
 
diff --git a/internal/pkg/sanitizer/sanitizer.go b/internal/pkg/sanitizer/sanitizer.go
index 50822be..b703d45 100644
--- a/internal/pkg/sanitizer/sanitizer.go
+++ b/internal/pkg/sanitizer/sanitizer.go
@@ -57,11 +57,5 @@ func (s Sanitizer) Dominates(target ssa.Instruction) bool {
 		return sanitizationIdx < targetIdx
 	}
 
-	for _, d := range s.Call.Block().Dominees() {
-		if target.Block() == d {
-			return true
-		}
-	}
-
 	return false
 }
diff --git a/internal/pkg/source/source.go b/internal/pkg/source/source.go
index 8a8a93f..d96ea46 100644
--- a/internal/pkg/source/source.go
+++ b/internal/pkg/source/source.go
@@ -38,11 +38,12 @@ type classifier interface {
 // its referrers.
 // Source.sanitized notes sanitizer calls that sanitize this Source
 type Source struct {
-	node       ssa.Node
-	marked     map[ssa.Node]bool
-	preOrder   []ssa.Node
-	sanitizers []*sanitizer.Sanitizer
-	config     classifier
+	node            ssa.Node
+	marked          map[ssa.Node]bool
+	preOrder        []ssa.Node
+	sanitizers      []*sanitizer.Sanitizer
+	config          classifier
+	maxInstrReached map[*ssa.BasicBlock]int
 }
 
 // Node returns the underlying ssa.Node of the Source.
@@ -53,9 +54,10 @@ func (a *Source) Node() ssa.Node {
 // New constructs a Source
 func New(in ssa.Node, config classifier) *Source {
 	a := &Source{
-		node:   in,
-		marked: make(map[ssa.Node]bool),
-		config: config,
+		node:            in,
+		marked:          make(map[ssa.Node]bool),
+		config:          config,
+		maxInstrReached: map[*ssa.BasicBlock]int{},
 	}
 	a.dfs(in)
 	return a
@@ -68,6 +70,10 @@ func (a *Source) dfs(n ssa.Node) {
 	a.preOrder = append(a.preOrder, n)
 	a.marked[n.(ssa.Node)] = true
 
+	if instr, ok := n.(ssa.Instruction); ok {
+		a.recordIndex(instr)
+	}
+
 	if n.Referrers() != nil {
 		a.visitReferrers(n.Referrers())
 	}
@@ -79,6 +85,17 @@ func (a *Source) dfs(n ssa.Node) {
 	}
 }
 
+func (a *Source) recordIndex(target ssa.Instruction) {
+	b := target.Block()
+	i, ok := indexInBlock(target)
+	if !ok {
+		return
+	}
+	if a.maxInstrReached[b] < i {
+		a.maxInstrReached[b] = i
+	}
+}
+
 func (a *Source) visitReferrers(referrers *[]ssa.Instruction) {
 	for _, r := range *referrers {
 		if a.marked[r.(ssa.Node)] {
@@ -94,6 +111,18 @@ func (a *Source) visitReferrers(referrers *[]ssa.Instruction) {
 			if a.config.IsSanitizer(v) {
 				a.sanitizers = append(a.sanitizers, &sanitizer.Sanitizer{Call: v})
 			}
+
+			// If this call's index is lower than the highest in its block,
+			// then this call is "in the past" and we should stop traversing.
+			i, ok := indexInBlock(r)
+			if !ok {
+				break
+			}
+
+			if i < a.maxInstrReached[r.Block()] {
+				continue
+			}
+
 		case *ssa.FieldAddr:
 			if !a.config.IsSourceFieldAddr(v) {
 				continue
@@ -266,3 +295,15 @@ func isProducedBySanitizer(v *ssa.Alloc, conf classifier) bool {
 	}
 	return false
 }
+
+// indexInBlock returns this instruction's index in its parent block.
+func indexInBlock(target ssa.Instruction) (int, bool) {
+	for i, instr := range target.Block().Instrs {
+		if instr == target {
+			return i, true
+		}
+	}
+	// we can only hit this return if there is a bug in the ssa package
+	// i.e. an instruction does not appear within its parent block
+	return 0, false
+}


Test patch:
diff --git a/internal/pkg/config/config_test.go b/internal/pkg/config/config_test.go
new file mode 100644
index 0000000..36d36d9
--- /dev/null
+++ b/internal/pkg/config/config_test.go
@@ -0,0 +1,58 @@
+// 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 config
+
+import (
+	"path/filepath"
+	"testing"
+
+	"golang.org/x/tools/go/analysis"
+	"golang.org/x/tools/go/analysis/analysistest"
+	"golang.org/x/tools/go/analysis/passes/buildssa"
+)
+
+var testAnalyzer = &analysis.Analyzer{
+	Name:     "config",
+	Run:      runTest,
+	Doc:      "test harness for the logic related to config",
+	Requires: []*analysis.Analyzer{buildssa.Analyzer},
+}
+
+func runTest(pass *analysis.Pass) (interface{}, error) {
+	in := pass.ResultOf[buildssa.Analyzer].(*buildssa.SSA)
+
+	conf, err := ReadConfig()
+	if err != nil {
+		return nil, err
+	}
+
+	for _, f := range in.SrcFuncs {
+		if conf.IsSinkFunction(f) {
+			pass.Reportf(f.Pos(), "sink")
+		}
+	}
+
+	return nil, nil
+}
+
+func TestConfig(t *testing.T) {
+	testdata := analysistest.TestData()
+	if err := FlagSet.Set("config", filepath.Join(testdata, "test-config.json")); err != nil {
+		t.Fatal(err)
+	}
+	for _, p := range []string{"example.com/core", "example.com/notcore", "notexample.com/core"} {
+		analysistest.Run(t, testdata, testAnalyzer, p)
+	}
+}
diff --git a/internal/pkg/config/testdata/src/example.com/core/core.go b/internal/pkg/config/testdata/src/example.com/core/core.go
new file mode 100644
index 0000000..38cd223
--- /dev/null
+++ b/internal/pkg/config/testdata/src/example.com/core/core.go
@@ -0,0 +1,25 @@
+// 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 core
+
+func Sink() {} // want "sink"
+
+func NotSink() {}
+
+type Sinker struct{}
+
+func (s Sinker) Do() {} // want "sink"
+
+func (s Sinker) DoNot() {}
diff --git a/internal/pkg/config/testdata/src/example.com/notcore/notcore.go b/internal/pkg/config/testdata/src/example.com/notcore/notcore.go
new file mode 100644
index 0000000..c469c1e
--- /dev/null
+++ b/internal/pkg/config/testdata/src/example.com/notcore/notcore.go
@@ -0,0 +1,25 @@
+// 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 notcore
+
+func Sink() {}
+
+func NotSink() {}
+
+type Sinker struct{}
+
+func (s Sinker) Do() {}
+
+func (s Sinker) DoNot() {}
diff --git a/internal/pkg/config/testdata/src/notexample.com/core/core.go b/internal/pkg/config/testdata/src/notexample.com/core/core.go
new file mode 100644
index 0000000..d56edbf
--- /dev/null
+++ b/internal/pkg/config/testdata/src/notexample.com/core/core.go
@@ -0,0 +1,25 @@
+// 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 core
+
+func Sink() {}
+
+func NotSink() {}
+
+type Sinker struct{}
+
+func (s Sinker) Do() {}
+
+func (s Sinker) DoNot() {}
diff --git a/internal/pkg/config/testdata/test-config.json b/internal/pkg/config/testdata/test-config.json
new file mode 100644
index 0000000..de3b362
--- /dev/null
+++ b/internal/pkg/config/testdata/test-config.json
@@ -0,0 +1,13 @@
+{
+  "Sinks": [
+    {
+      "PackageRE": "^example.com/core$",
+      "MethodRE": "^Sink$"
+    },
+    {
+      "PackageRE": "^example.com/core$",
+      "MethodRE": "^Do$",
+      "TypeRE": "^Sinker$"
+    }
+  ]
+}
diff --git a/internal/pkg/levee/testdata/src/example.com/tests/callorder/tests.go b/internal/pkg/levee/testdata/src/example.com/tests/callorder/tests.go
new file mode 100644
index 0000000..968808a
--- /dev/null
+++ b/internal/pkg/levee/testdata/src/example.com/tests/callorder/tests.go
@@ -0,0 +1,38 @@
+// 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 callorder
+
+import (
+	"fmt"
+	"io"
+
+	"example.com/core"
+)
+
+func TestTaintBeforeSinking(s core.Source, w io.Writer) {
+	_, _ = fmt.Fprintf(w, "%v", s)
+	core.Sink(w) // want "a source has reached a sink"
+}
+
+func TestSinkBeforeTainting(s core.Source, w io.Writer) {
+	core.Sink(w)
+	_, _ = fmt.Fprintf(w, "%v", s)
+}
+
+func TestSinkBeforeAndAfterTainting(s core.Source, w io.Writer) {
+	core.Sink(w)
+	_, _ = fmt.Fprintf(w, "%v", s)
+	core.Sink(w) // want "a source has reached a sink"
+}
diff --git a/internal/pkg/levee/testdata/src/example.com/tests/collections/chans.go b/internal/pkg/levee/testdata/src/example.com/tests/collections/chans.go
new file mode 100644
index 0000000..752cafa
--- /dev/null
+++ b/internal/pkg/levee/testdata/src/example.com/tests/collections/chans.go
@@ -0,0 +1,41 @@
+// 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 TestSourceReceivedFromChannelIsTainted(sources <-chan core.Source) {
+	s := <-sources
+	core.Sink(s) // want "a source has reached a sink"
+}
+
+func TestChannelIsTaintedWhenSourceIsPlacedOnIt(sources chan<- core.Source) {
+	sources <- core.Source{}
+	core.Sink(sources) // want "a source has reached a sink"
+}
+
+func TestValueObtainedFromTaintedChannelIsTainted(c chan interface{}) {
+	c <- core.Source{}
+	s := <-c
+	core.Sink(s) // want "a source has reached a sink"
+}
+
+func TestChannelIsNoLongerTaintedWhenNilledOut(sources chan core.Source) {
+	sources <- core.Source{}
+	sources = nil
+	core.Sink(sources)
+}