Repository navigation
TaintTracking: copy inside range on map produces multiple (incomplete) path variants if struct or field are a pointer #9308
Description
Summary
When a transfer of taint happens in a range loop, and the domain is a pointer to a struct and the field is a map, then the results will contain multiple paths.
Preamble code
package main
func main() {}
func source() interface{} { return nil }
func sink(v interface{}) {}
func link(in interface{}, out interface{}) {}
type StructWithPointerField struct {
Params *map[string]string
}
type StructWithValueField struct {
Params map[string]string
}Cases with domain = a field of a struct (spoiler: most produce unexpected results)
func range_2A() {
src := source().(StructWithValueField)
{
data := make(map[string]interface{})
for key, value := range src.Params {
data[key] = value
}
sink(data)
}
}nets the following result (one path, which is expected):
func range_2B() {
src := source().(*StructWithValueField)
{
data := make(map[string]interface{})
for key, value := range src.Params {
data[key] = value
}
sink(data)
}
}nets the following result (multiple paths, which is UNexpected):
func range_2C() {
src := source().(StructWithPointerField)
{
data := make(map[string]interface{})
for key, value := range *src.Params {
data[key] = value
}
sink(data)
}
}nets the following result (multiple paths, which is UNexpected):
func range_2D() {
src := source().(*StructWithPointerField)
{
data := make(map[string]interface{})
for key, value := range *src.Params {
data[key] = value
}
sink(data)
}
}nets the following result (multiple paths, which is UNexpected):
Cases with domain = map (spoiler: all satisfy expectations)
func range_1A() {
src := source().(map[string]string)
{
data := make(map[string]interface{})
for key, value := range src {
data[key] = value
}
sink(data)
}
}nets the following result (one path, which is expected):
func range_1B() {
src := source().(*map[string]string)
{
data := make(map[string]interface{})
for key, value := range *src {
data[key] = value
}
sink(data)
}
}nets the following result (one path, which is expected):
func range_1C() {
src := source().(*map[*string]string)
{
data := make(map[string]interface{})
for key, value := range *src {
data[*key] = value
}
sink(data)
}
}nets the following result (one path, which is expected):
func range_1D() {
src := source().(*map[string]*string)
{
data := make(map[string]interface{})
for key, value := range *src {
data[key] = *value
}
sink(data)
}
}nets the following result (one path, which is expected):
func range_1E() {
src := source().(*map[*string]*string)
{
data := make(map[string]interface{})
for key, value := range *src {
data[*key] = *value
}
sink(data)
}
}nets the following result (one path, which is expected):
func range_1F() {
src := source().(string)
var (
Map map[string]string
)
link([]byte(src), &Map)
{
data := make(map[string]interface{})
for key, value := range Map {
data[key] = value
}
sink(data)
}
}nets the following result (one path, which is expected):
func range_1G() {
src := source().(string)
Map := new(map[string]string)
link([]byte(src), Map)
{
data := make(map[string]interface{})
for key, value := range *Map {
data[key] = value
}
sink(data)
}
}nets the following result (one path, which is expected):
func range_1H() {
src := source().(string)
Map := make(map[string]string)
link([]byte(src), &Map)
{
data := make(map[string]interface{})
for key, value := range Map {
data[key] = value
}
sink(data)
}
}nets the following result (one path, which is expected):
Activity
gagliardetto commentedon Mar 24, 2021
Go source code:
gagliardetto commentedon Mar 24, 2021
Codeql query code:
gagliardetto commentedon Mar 24, 2021
The
RangeCopy.expectedfile:gagliardetto commentedon Mar 25, 2021
@smowton As per our discussion, I think this is the cause of result inconsistency.
gagliardetto commentedon Mar 25, 2021
Another separate issue is that there's no mention of the range loop step in the tain flow steps' list.
smowton commentedon Mar 25, 2021
The root cause of all this is our algorithm for exposing steps in a path explanation. The actual paths are basically fine, as you can see using something like
If you follow definitions from
PathGraph::edges, you'll eventually get tolocalFlowBigStep, which is drawing a maximal subsequence of small steps (here exposed bylocalTaintStep), plus requiring the endpoint to satisfylocalFlowExit, which is true in particular if the step at either end is a read or store step.In the simple cases there is only one maximal subsequence to find, straight from the source to the sink. However when derefs get involved we find extra paths because we have general taint rules
x -taint-> *xand*x -taint-> x, which of course introduces a trivial loop and a new candidate forlocalFlowBigStep, because the end of a loop constitutes a maximal subsequence and a deref operation can be either a read or a store step. We want to retain both these taint rules, but ideally we would refrain from showing a confusing explanation like this -- I've asked the core team whether that's likely to be possible in the future.Some but not all of these taint-flow loops are attributable to Go's imprecise model of dataflow out of an update operation -- in particular its
PostUpdateNodes, which represent a particular expression after a side-effect has taken place -- are not as precisely connected to only control-flow-successive reads as they are in other languages.To summarise, all the problems observed here are issues with how dataflow is displayed rather than the actual results being incorrect. The possible improvements that might make this better are:
gagliardetto commentedon Mar 25, 2021
@smowton Thanks for the in-depth response!