| 1 | // Copyright 2021 The Go Authors. All rights reserved. |
|---|---|
| 2 | // Use of this source code is governed by a BSD-style |
| 3 | // license that can be found in the LICENSE file. |
| 4 | |
| 5 | package vta |
| 6 | |
| 7 | import ( |
| 8 | "fmt" |
| 9 | "go/token" |
| 10 | "go/types" |
| 11 | |
| 12 | "golang.org/x/tools/go/callgraph" |
| 13 | "golang.org/x/tools/go/ssa" |
| 14 | "golang.org/x/tools/go/types/typeutil" |
| 15 | ) |
| 16 | |
| 17 | // node interface for VTA nodes. |
| 18 | type node interface { |
| 19 | Type() types.Type |
| 20 | String() string |
| 21 | } |
| 22 | |
| 23 | // constant node for VTA. |
| 24 | type constant struct { |
| 25 | typ types.Type |
| 26 | } |
| 27 | |
| 28 | func (c constant) Type() types.Type { |
| 29 | return c.typ |
| 30 | } |
| 31 | |
| 32 | func (c constant) String() string { |
| 33 | return fmt.Sprintf("Constant(%v)", c.Type()) |
| 34 | } |
| 35 | |
| 36 | // pointer node for VTA. |
| 37 | type pointer struct { |
| 38 | typ *types.Pointer |
| 39 | } |
| 40 | |
| 41 | func (p pointer) Type() types.Type { |
| 42 | return p.typ |
| 43 | } |
| 44 | |
| 45 | func (p pointer) String() string { |
| 46 | return fmt.Sprintf("Pointer(%v)", p.Type()) |
| 47 | } |
| 48 | |
| 49 | // mapKey node for VTA, modeling reachable map key types. |
| 50 | type mapKey struct { |
| 51 | typ types.Type |
| 52 | } |
| 53 | |
| 54 | func (mk mapKey) Type() types.Type { |
| 55 | return mk.typ |
| 56 | } |
| 57 | |
| 58 | func (mk mapKey) String() string { |
| 59 | return fmt.Sprintf("MapKey(%v)", mk.Type()) |
| 60 | } |
| 61 | |
| 62 | // mapValue node for VTA, modeling reachable map value types. |
| 63 | type mapValue struct { |
| 64 | typ types.Type |
| 65 | } |
| 66 | |
| 67 | func (mv mapValue) Type() types.Type { |
| 68 | return mv.typ |
| 69 | } |
| 70 | |
| 71 | func (mv mapValue) String() string { |
| 72 | return fmt.Sprintf("MapValue(%v)", mv.Type()) |
| 73 | } |
| 74 | |
| 75 | // sliceElem node for VTA, modeling reachable slice and array element types. |
| 76 | type sliceElem struct { |
| 77 | typ types.Type |
| 78 | } |
| 79 | |
| 80 | func (s sliceElem) Type() types.Type { |
| 81 | return s.typ |
| 82 | } |
| 83 | |
| 84 | func (s sliceElem) String() string { |
| 85 | return fmt.Sprintf("Slice([]%v)", s.Type()) |
| 86 | } |
| 87 | |
| 88 | // channelElem node for VTA, modeling reachable channel element types. |
| 89 | type channelElem struct { |
| 90 | typ types.Type |
| 91 | } |
| 92 | |
| 93 | func (c channelElem) Type() types.Type { |
| 94 | return c.typ |
| 95 | } |
| 96 | |
| 97 | func (c channelElem) String() string { |
| 98 | return fmt.Sprintf("Channel(chan %v)", c.Type()) |
| 99 | } |
| 100 | |
| 101 | // field node for VTA. |
| 102 | type field struct { |
| 103 | StructType types.Type |
| 104 | index int // index of the field in the struct |
| 105 | } |
| 106 | |
| 107 | func (f field) Type() types.Type { |
| 108 | s := f.StructType.Underlying().(*types.Struct) |
| 109 | return s.Field(f.index).Type() |
| 110 | } |
| 111 | |
| 112 | func (f field) String() string { |
| 113 | s := f.StructType.Underlying().(*types.Struct) |
| 114 | return fmt.Sprintf("Field(%v:%s)", f.StructType, s.Field(f.index).Name()) |
| 115 | } |
| 116 | |
| 117 | // global node for VTA. |
| 118 | type global struct { |
| 119 | val *ssa.Global |
| 120 | } |
| 121 | |
| 122 | func (g global) Type() types.Type { |
| 123 | return g.val.Type() |
| 124 | } |
| 125 | |
| 126 | func (g global) String() string { |
| 127 | return fmt.Sprintf("Global(%s)", g.val.Name()) |
| 128 | } |
| 129 | |
| 130 | // local node for VTA modeling local variables |
| 131 | // and function/method parameters. |
| 132 | type local struct { |
| 133 | val ssa.Value |
| 134 | } |
| 135 | |
| 136 | func (l local) Type() types.Type { |
| 137 | return l.val.Type() |
| 138 | } |
| 139 | |
| 140 | func (l local) String() string { |
| 141 | return fmt.Sprintf("Local(%s)", l.val.Name()) |
| 142 | } |
| 143 | |
| 144 | // indexedLocal node for VTA node. Models indexed locals |
| 145 | // related to the ssa extract instructions. |
| 146 | type indexedLocal struct { |
| 147 | val ssa.Value |
| 148 | index int |
| 149 | typ types.Type |
| 150 | } |
| 151 | |
| 152 | func (i indexedLocal) Type() types.Type { |
| 153 | return i.typ |
| 154 | } |
| 155 | |
| 156 | func (i indexedLocal) String() string { |
| 157 | return fmt.Sprintf("Local(%s[%d])", i.val.Name(), i.index) |
| 158 | } |
| 159 | |
| 160 | // function node for VTA. |
| 161 | type function struct { |
| 162 | f *ssa.Function |
| 163 | } |
| 164 | |
| 165 | func (f function) Type() types.Type { |
| 166 | return f.f.Type() |
| 167 | } |
| 168 | |
| 169 | func (f function) String() string { |
| 170 | return fmt.Sprintf("Function(%s)", f.f.Name()) |
| 171 | } |
| 172 | |
| 173 | // nestedPtrInterface node represents all references and dereferences |
| 174 | // of locals and globals that have a nested pointer to interface type. |
| 175 | // We merge such constructs into a single node for simplicity and without |
| 176 | // much precision sacrifice as such variables are rare in practice. Both |
| 177 | // a and b would be represented as the same PtrInterface(I) node in: |
| 178 | // |
| 179 | // type I interface |
| 180 | // var a ***I |
| 181 | // var b **I |
| 182 | type nestedPtrInterface struct { |
| 183 | typ types.Type |
| 184 | } |
| 185 | |
| 186 | func (l nestedPtrInterface) Type() types.Type { |
| 187 | return l.typ |
| 188 | } |
| 189 | |
| 190 | func (l nestedPtrInterface) String() string { |
| 191 | return fmt.Sprintf("PtrInterface(%v)", l.typ) |
| 192 | } |
| 193 | |
| 194 | // nestedPtrFunction node represents all references and dereferences of locals |
| 195 | // and globals that have a nested pointer to function type. We merge such |
| 196 | // constructs into a single node for simplicity and without much precision |
| 197 | // sacrifice as such variables are rare in practice. Both a and b would be |
| 198 | // represented as the same PtrFunction(func()) node in: |
| 199 | // |
| 200 | // var a *func() |
| 201 | // var b **func() |
| 202 | type nestedPtrFunction struct { |
| 203 | typ types.Type |
| 204 | } |
| 205 | |
| 206 | func (p nestedPtrFunction) Type() types.Type { |
| 207 | return p.typ |
| 208 | } |
| 209 | |
| 210 | func (p nestedPtrFunction) String() string { |
| 211 | return fmt.Sprintf("PtrFunction(%v)", p.typ) |
| 212 | } |
| 213 | |
| 214 | // panicArg models types of all arguments passed to panic. |
| 215 | type panicArg struct{} |
| 216 | |
| 217 | func (p panicArg) Type() types.Type { |
| 218 | return nil |
| 219 | } |
| 220 | |
| 221 | func (p panicArg) String() string { |
| 222 | return "Panic" |
| 223 | } |
| 224 | |
| 225 | // recoverReturn models types of all return values of recover(). |
| 226 | type recoverReturn struct{} |
| 227 | |
| 228 | func (r recoverReturn) Type() types.Type { |
| 229 | return nil |
| 230 | } |
| 231 | |
| 232 | func (r recoverReturn) String() string { |
| 233 | return "Recover" |
| 234 | } |
| 235 | |
| 236 | // vtaGraph remembers for each VTA node the set of its successors. |
| 237 | // Tailored for VTA, hence does not support singleton (sub)graphs. |
| 238 | type vtaGraph map[node]map[node]bool |
| 239 | |
| 240 | // addEdge adds an edge x->y to the graph. |
| 241 | func (g vtaGraph) addEdge(x, y node) { |
| 242 | succs, ok := g[x] |
| 243 | if !ok { |
| 244 | succs = make(map[node]bool) |
| 245 | g[x] = succs |
| 246 | } |
| 247 | succs[y] = true |
| 248 | } |
| 249 | |
| 250 | // successors returns all of n's immediate successors in the graph. |
| 251 | // The order of successor nodes is arbitrary. |
| 252 | func (g vtaGraph) successors(n node) []node { |
| 253 | var succs []node |
| 254 | for succ := range g[n] { |
| 255 | succs = append(succs, succ) |
| 256 | } |
| 257 | return succs |
| 258 | } |
| 259 | |
| 260 | // typePropGraph builds a VTA graph for a set of `funcs` and initial |
| 261 | // `callgraph` needed to establish interprocedural edges. Returns the |
| 262 | // graph and a map for unique type representatives. |
| 263 | func typePropGraph(funcs map[*ssa.Function]bool, callgraph *callgraph.Graph) (vtaGraph, *typeutil.Map) { |
| 264 | b := builder{graph: make(vtaGraph), callGraph: callgraph} |
| 265 | b.visit(funcs) |
| 266 | return b.graph, &b.canon |
| 267 | } |
| 268 | |
| 269 | // Data structure responsible for linearly traversing the |
| 270 | // code and building a VTA graph. |
| 271 | type builder struct { |
| 272 | graph vtaGraph |
| 273 | callGraph *callgraph.Graph // initial call graph for creating flows at unresolved call sites. |
| 274 | |
| 275 | // Specialized type map for canonicalization of types.Type. |
| 276 | // Semantically equivalent types can have different implementations, |
| 277 | // i.e., they are different pointer values. The map allows us to |
| 278 | // have one unique representative. The keys are fixed and from the |
| 279 | // client perspective they are types. The values in our case are |
| 280 | // types too, in particular type representatives. Each value is a |
| 281 | // pointer so this map is not expected to take much memory. |
| 282 | canon typeutil.Map |
| 283 | } |
| 284 | |
| 285 | func (b *builder) visit(funcs map[*ssa.Function]bool) { |
| 286 | // Add the fixed edge Panic -> Recover |
| 287 | b.graph.addEdge(panicArg{}, recoverReturn{}) |
| 288 | |
| 289 | for f, in := range funcs { |
| 290 | if in { |
| 291 | b.fun(f) |
| 292 | } |
| 293 | } |
| 294 | } |
| 295 | |
| 296 | func (b *builder) fun(f *ssa.Function) { |
| 297 | for _, bl := range f.Blocks { |
| 298 | for _, instr := range bl.Instrs { |
| 299 | b.instr(instr) |
| 300 | } |
| 301 | } |
| 302 | } |
| 303 | |
| 304 | func (b *builder) instr(instr ssa.Instruction) { |
| 305 | switch i := instr.(type) { |
| 306 | case *ssa.Store: |
| 307 | b.addInFlowAliasEdges(b.nodeFromVal(i.Addr), b.nodeFromVal(i.Val)) |
| 308 | case *ssa.MakeInterface: |
| 309 | b.addInFlowEdge(b.nodeFromVal(i.X), b.nodeFromVal(i)) |
| 310 | case *ssa.MakeClosure: |
| 311 | b.closure(i) |
| 312 | case *ssa.UnOp: |
| 313 | b.unop(i) |
| 314 | case *ssa.Phi: |
| 315 | b.phi(i) |
| 316 | case *ssa.ChangeInterface: |
| 317 | // Although in change interface a := A(b) command a and b are |
| 318 | // the same object, the only interesting flow happens when A |
| 319 | // is an interface. We create flow b -> a, but omit a -> b. |
| 320 | // The latter flow is not needed: if a gets assigned concrete |
| 321 | // type later on, that cannot be propagated back to b as b |
| 322 | // is a separate variable. The a -> b flow can happen when |
| 323 | // A is a pointer to interface, but then the command is of |
| 324 | // type ChangeType, handled below. |
| 325 | b.addInFlowEdge(b.nodeFromVal(i.X), b.nodeFromVal(i)) |
| 326 | case *ssa.ChangeType: |
| 327 | // change type command a := A(b) results in a and b being the |
| 328 | // same value. For concrete type A, there is no interesting flow. |
| 329 | // |
| 330 | // Note: When A is an interface, most interface casts are handled |
| 331 | // by the ChangeInterface instruction. The relevant case here is |
| 332 | // when converting a pointer to an interface type. This can happen |
| 333 | // when the underlying interfaces have the same method set. |
| 334 | // type I interface{ foo() } |
| 335 | // type J interface{ foo() } |
| 336 | // var b *I |
| 337 | // a := (*J)(b) |
| 338 | // When this happens we add flows between a <--> b. |
| 339 | b.addInFlowAliasEdges(b.nodeFromVal(i), b.nodeFromVal(i.X)) |
| 340 | case *ssa.TypeAssert: |
| 341 | b.tassert(i) |
| 342 | case *ssa.Extract: |
| 343 | b.extract(i) |
| 344 | case *ssa.Field: |
| 345 | b.field(i) |
| 346 | case *ssa.FieldAddr: |
| 347 | b.fieldAddr(i) |
| 348 | case *ssa.Send: |
| 349 | b.send(i) |
| 350 | case *ssa.Select: |
| 351 | b.selekt(i) |
| 352 | case *ssa.Index: |
| 353 | b.index(i) |
| 354 | case *ssa.IndexAddr: |
| 355 | b.indexAddr(i) |
| 356 | case *ssa.Lookup: |
| 357 | b.lookup(i) |
| 358 | case *ssa.MapUpdate: |
| 359 | b.mapUpdate(i) |
| 360 | case *ssa.Next: |
| 361 | b.next(i) |
| 362 | case ssa.CallInstruction: |
| 363 | b.call(i) |
| 364 | case *ssa.Panic: |
| 365 | b.panic(i) |
| 366 | case *ssa.Return: |
| 367 | b.rtrn(i) |
| 368 | case *ssa.MakeChan, *ssa.MakeMap, *ssa.MakeSlice, *ssa.BinOp, |
| 369 | *ssa.Alloc, *ssa.DebugRef, *ssa.Convert, *ssa.Jump, *ssa.If, |
| 370 | *ssa.Slice, *ssa.SliceToArrayPointer, *ssa.Range, *ssa.RunDefers: |
| 371 | // No interesting flow here. |
| 372 | // Notes on individual instructions: |
| 373 | // SliceToArrayPointer: t1 = slice to array pointer *[4]T <- []T (t0) |
| 374 | // No interesting flow as sliceArrayElem(t1) == sliceArrayElem(t0). |
| 375 | return |
| 376 | default: |
| 377 | panic(fmt.Sprintf("unsupported instruction %v\n", instr)) |
| 378 | } |
| 379 | } |
| 380 | |
| 381 | func (b *builder) unop(u *ssa.UnOp) { |
| 382 | switch u.Op { |
| 383 | case token.MUL: |
| 384 | // Multiplication operator * is used here as a dereference operator. |
| 385 | b.addInFlowAliasEdges(b.nodeFromVal(u), b.nodeFromVal(u.X)) |
| 386 | case token.ARROW: |
| 387 | t := u.X.Type().Underlying().(*types.Chan).Elem() |
| 388 | b.addInFlowAliasEdges(b.nodeFromVal(u), channelElem{typ: t}) |
| 389 | default: |
| 390 | // There is no interesting type flow otherwise. |
| 391 | } |
| 392 | } |
| 393 | |
| 394 | func (b *builder) phi(p *ssa.Phi) { |
| 395 | for _, edge := range p.Edges { |
| 396 | b.addInFlowAliasEdges(b.nodeFromVal(p), b.nodeFromVal(edge)) |
| 397 | } |
| 398 | } |
| 399 | |
| 400 | func (b *builder) tassert(a *ssa.TypeAssert) { |
| 401 | if !a.CommaOk { |
| 402 | b.addInFlowEdge(b.nodeFromVal(a.X), b.nodeFromVal(a)) |
| 403 | return |
| 404 | } |
| 405 | // The case where a is <a.AssertedType, bool> register so there |
| 406 | // is a flow from a.X to a[0]. Here, a[0] is represented as an |
| 407 | // indexedLocal: an entry into local tuple register a at index 0. |
| 408 | tup := a.Type().Underlying().(*types.Tuple) |
| 409 | t := tup.At(0).Type() |
| 410 | |
| 411 | local := indexedLocal{val: a, typ: t, index: 0} |
| 412 | b.addInFlowEdge(b.nodeFromVal(a.X), local) |
| 413 | } |
| 414 | |
| 415 | // extract instruction t1 := t2[i] generates flows between t2[i] |
| 416 | // and t1 where the source is indexed local representing a value |
| 417 | // from tuple register t2 at index i and the target is t1. |
| 418 | func (b *builder) extract(e *ssa.Extract) { |
| 419 | tup := e.Tuple.Type().Underlying().(*types.Tuple) |
| 420 | t := tup.At(e.Index).Type() |
| 421 | |
| 422 | local := indexedLocal{val: e.Tuple, typ: t, index: e.Index} |
| 423 | b.addInFlowAliasEdges(b.nodeFromVal(e), local) |
| 424 | } |
| 425 | |
| 426 | func (b *builder) field(f *ssa.Field) { |
| 427 | fnode := field{StructType: f.X.Type(), index: f.Field} |
| 428 | b.addInFlowEdge(fnode, b.nodeFromVal(f)) |
| 429 | } |
| 430 | |
| 431 | func (b *builder) fieldAddr(f *ssa.FieldAddr) { |
| 432 | t := f.X.Type().Underlying().(*types.Pointer).Elem() |
| 433 | |
| 434 | // Since we are getting pointer to a field, make a bidirectional edge. |
| 435 | fnode := field{StructType: t, index: f.Field} |
| 436 | b.addInFlowEdge(fnode, b.nodeFromVal(f)) |
| 437 | b.addInFlowEdge(b.nodeFromVal(f), fnode) |
| 438 | } |
| 439 | |
| 440 | func (b *builder) send(s *ssa.Send) { |
| 441 | t := s.Chan.Type().Underlying().(*types.Chan).Elem() |
| 442 | b.addInFlowAliasEdges(channelElem{typ: t}, b.nodeFromVal(s.X)) |
| 443 | } |
| 444 | |
| 445 | // selekt generates flows for select statement |
| 446 | // |
| 447 | // a = select blocking/nonblocking [c_1 <- t_1, c_2 <- t_2, ..., <- o_1, <- o_2, ...] |
| 448 | // |
| 449 | // between receiving channel registers c_i and corresponding input register t_i. Further, |
| 450 | // flows are generated between o_i and a[2 + i]. Note that a is a tuple register of type |
| 451 | // <int, bool, r_1, r_2, ...> where the type of r_i is the element type of channel o_i. |
| 452 | func (b *builder) selekt(s *ssa.Select) { |
| 453 | recvIndex := 0 |
| 454 | for _, state := range s.States { |
| 455 | t := state.Chan.Type().Underlying().(*types.Chan).Elem() |
| 456 | |
| 457 | if state.Dir == types.SendOnly { |
| 458 | b.addInFlowAliasEdges(channelElem{typ: t}, b.nodeFromVal(state.Send)) |
| 459 | } else { |
| 460 | // state.Dir == RecvOnly by definition of select instructions. |
| 461 | tupEntry := indexedLocal{val: s, typ: t, index: 2 + recvIndex} |
| 462 | b.addInFlowAliasEdges(tupEntry, channelElem{typ: t}) |
| 463 | recvIndex++ |
| 464 | } |
| 465 | } |
| 466 | } |
| 467 | |
| 468 | // index instruction a := b[c] on slices creates flows between a and |
| 469 | // SliceElem(t) flow where t is an interface type of c. Arrays and |
| 470 | // slice elements are both modeled as SliceElem. |
| 471 | func (b *builder) index(i *ssa.Index) { |
| 472 | et := sliceArrayElem(i.X.Type()) |
| 473 | b.addInFlowAliasEdges(b.nodeFromVal(i), sliceElem{typ: et}) |
| 474 | } |
| 475 | |
| 476 | // indexAddr instruction a := &b[c] fetches address of a index |
| 477 | // into the field so we create bidirectional flow a <-> SliceElem(t) |
| 478 | // where t is an interface type of c. Arrays and slice elements are |
| 479 | // both modeled as SliceElem. |
| 480 | func (b *builder) indexAddr(i *ssa.IndexAddr) { |
| 481 | et := sliceArrayElem(i.X.Type()) |
| 482 | b.addInFlowEdge(sliceElem{typ: et}, b.nodeFromVal(i)) |
| 483 | b.addInFlowEdge(b.nodeFromVal(i), sliceElem{typ: et}) |
| 484 | } |
| 485 | |
| 486 | // lookup handles map query commands a := m[b] where m is of type |
| 487 | // map[...]V and V is an interface. It creates flows between `a` |
| 488 | // and MapValue(V). |
| 489 | func (b *builder) lookup(l *ssa.Lookup) { |
| 490 | t, ok := l.X.Type().Underlying().(*types.Map) |
| 491 | if !ok { |
| 492 | // No interesting flows for string lookups. |
| 493 | return |
| 494 | } |
| 495 | b.addInFlowAliasEdges(b.nodeFromVal(l), mapValue{typ: t.Elem()}) |
| 496 | } |
| 497 | |
| 498 | // mapUpdate handles map update commands m[b] = a where m is of type |
| 499 | // map[K]V and K and V are interfaces. It creates flows between `a` |
| 500 | // and MapValue(V) as well as between MapKey(K) and `b`. |
| 501 | func (b *builder) mapUpdate(u *ssa.MapUpdate) { |
| 502 | t, ok := u.Map.Type().Underlying().(*types.Map) |
| 503 | if !ok { |
| 504 | // No interesting flows for string updates. |
| 505 | return |
| 506 | } |
| 507 | |
| 508 | b.addInFlowAliasEdges(mapKey{typ: t.Key()}, b.nodeFromVal(u.Key)) |
| 509 | b.addInFlowAliasEdges(mapValue{typ: t.Elem()}, b.nodeFromVal(u.Value)) |
| 510 | } |
| 511 | |
| 512 | // next instruction <ok, key, value> := next r, where r |
| 513 | // is a range over map or string generates flow between |
| 514 | // key and MapKey as well value and MapValue nodes. |
| 515 | func (b *builder) next(n *ssa.Next) { |
| 516 | if n.IsString { |
| 517 | return |
| 518 | } |
| 519 | tup := n.Type().Underlying().(*types.Tuple) |
| 520 | kt := tup.At(1).Type() |
| 521 | vt := tup.At(2).Type() |
| 522 | |
| 523 | b.addInFlowAliasEdges(indexedLocal{val: n, typ: kt, index: 1}, mapKey{typ: kt}) |
| 524 | b.addInFlowAliasEdges(indexedLocal{val: n, typ: vt, index: 2}, mapValue{typ: vt}) |
| 525 | } |
| 526 | |
| 527 | // addInFlowAliasEdges adds an edge r -> l to b.graph if l is a node that can |
| 528 | // have an inflow, i.e., a node that represents an interface or an unresolved |
| 529 | // function value. Similarly for the edge l -> r with an additional condition |
| 530 | // of that l and r can potentially alias. |
| 531 | func (b *builder) addInFlowAliasEdges(l, r node) { |
| 532 | b.addInFlowEdge(r, l) |
| 533 | |
| 534 | if canAlias(l, r) { |
| 535 | b.addInFlowEdge(l, r) |
| 536 | } |
| 537 | } |
| 538 | |
| 539 | func (b *builder) closure(c *ssa.MakeClosure) { |
| 540 | f := c.Fn.(*ssa.Function) |
| 541 | b.addInFlowEdge(function{f: f}, b.nodeFromVal(c)) |
| 542 | |
| 543 | for i, fv := range f.FreeVars { |
| 544 | b.addInFlowAliasEdges(b.nodeFromVal(fv), b.nodeFromVal(c.Bindings[i])) |
| 545 | } |
| 546 | } |
| 547 | |
| 548 | // panic creates a flow from arguments to panic instructions to return |
| 549 | // registers of all recover statements in the program. Introduces a |
| 550 | // global panic node Panic and |
| 551 | // 1. for every panic statement p: add p -> Panic |
| 552 | // 2. for every recover statement r: add Panic -> r (handled in call) |
| 553 | // |
| 554 | // TODO(zpavlinovic): improve precision by explicitly modeling how panic |
| 555 | // values flow from callees to callers and into deferred recover instructions. |
| 556 | func (b *builder) panic(p *ssa.Panic) { |
| 557 | // Panics often have, for instance, strings as arguments which do |
| 558 | // not create interesting flows. |
| 559 | if !canHaveMethods(p.X.Type()) { |
| 560 | return |
| 561 | } |
| 562 | |
| 563 | b.addInFlowEdge(b.nodeFromVal(p.X), panicArg{}) |
| 564 | } |
| 565 | |
| 566 | // call adds flows between arguments/parameters and return values/registers |
| 567 | // for both static and dynamic calls, as well as go and defer calls. |
| 568 | func (b *builder) call(c ssa.CallInstruction) { |
| 569 | // When c is r := recover() call register instruction, we add Recover -> r. |
| 570 | if bf, ok := c.Common().Value.(*ssa.Builtin); ok && bf.Name() == "recover" { |
| 571 | if v, ok := c.(ssa.Value); ok { |
| 572 | b.addInFlowEdge(recoverReturn{}, b.nodeFromVal(v)) |
| 573 | } |
| 574 | return |
| 575 | } |
| 576 | |
| 577 | for _, f := range siteCallees(c, b.callGraph) { |
| 578 | addArgumentFlows(b, c, f) |
| 579 | } |
| 580 | } |
| 581 | |
| 582 | func addArgumentFlows(b *builder, c ssa.CallInstruction, f *ssa.Function) { |
| 583 | // When f has no paremeters (including receiver), there is no type |
| 584 | // flow here. Also, f's body and parameters might be missing, such |
| 585 | // as when vta is used within the golang.org/x/tools/go/analysis |
| 586 | // framework (see github.com/golang/go/issues/50670). |
| 587 | if len(f.Params) == 0 { |
| 588 | return |
| 589 | } |
| 590 | cc := c.Common() |
| 591 | |
| 592 | offset := 0 |
| 593 | if cc.Method != nil { |
| 594 | // We don't add interprocedural flows for receiver objects. |
| 595 | // At a call site, the receiver object is interface while the |
| 596 | // callee object is concrete. The flow from interface to |
| 597 | // concrete type does not make sense. The flow other way around |
| 598 | // would bake in information from the initial call graph. |
| 599 | offset = 1 |
| 600 | } |
| 601 | for i, v := range cc.Args { |
| 602 | // Parameters of f might not be available, as in the case |
| 603 | // when vta is used within the golang.org/x/tools/go/analysis |
| 604 | // framework (see github.com/golang/go/issues/50670). |
| 605 | // |
| 606 | // TODO: investigate other cases of missing body and parameters |
| 607 | if len(f.Params) <= i+offset { |
| 608 | return |
| 609 | } |
| 610 | b.addInFlowAliasEdges(b.nodeFromVal(f.Params[i+offset]), b.nodeFromVal(v)) |
| 611 | } |
| 612 | } |
| 613 | |
| 614 | // rtrn produces flows between values of r and c where |
| 615 | // c is a call instruction that resolves to the enclosing |
| 616 | // function of r based on b.callGraph. |
| 617 | func (b *builder) rtrn(r *ssa.Return) { |
| 618 | n := b.callGraph.Nodes[r.Parent()] |
| 619 | // n != nil when b.callgraph is sound, but the client can |
| 620 | // pass any callgraph, including an underapproximate one. |
| 621 | if n == nil { |
| 622 | return |
| 623 | } |
| 624 | |
| 625 | for _, e := range n.In { |
| 626 | if cv, ok := e.Site.(ssa.Value); ok { |
| 627 | addReturnFlows(b, r, cv) |
| 628 | } |
| 629 | } |
| 630 | } |
| 631 | |
| 632 | func addReturnFlows(b *builder, r *ssa.Return, site ssa.Value) { |
| 633 | results := r.Results |
| 634 | if len(results) == 1 { |
| 635 | // When there is only one return value, the destination register does not |
| 636 | // have a tuple type. |
| 637 | b.addInFlowEdge(b.nodeFromVal(results[0]), b.nodeFromVal(site)) |
| 638 | return |
| 639 | } |
| 640 | |
| 641 | tup := site.Type().Underlying().(*types.Tuple) |
| 642 | for i, r := range results { |
| 643 | local := indexedLocal{val: site, typ: tup.At(i).Type(), index: i} |
| 644 | b.addInFlowEdge(b.nodeFromVal(r), local) |
| 645 | } |
| 646 | } |
| 647 | |
| 648 | // addInFlowEdge adds s -> d to g if d is node that can have an inflow, i.e., a node |
| 649 | // that represents an interface or an unresolved function value. Otherwise, there |
| 650 | // is no interesting type flow so the edge is omitted. |
| 651 | func (b *builder) addInFlowEdge(s, d node) { |
| 652 | if hasInFlow(d) { |
| 653 | b.graph.addEdge(b.representative(s), b.representative(d)) |
| 654 | } |
| 655 | } |
| 656 | |
| 657 | // Creates const, pointer, global, func, and local nodes based on register instructions. |
| 658 | func (b *builder) nodeFromVal(val ssa.Value) node { |
| 659 | if p, ok := val.Type().(*types.Pointer); ok && !types.IsInterface(p.Elem()) && !isFunction(p.Elem()) { |
| 660 | // Nested pointer to interfaces are modeled as a special |
| 661 | // nestedPtrInterface node. |
| 662 | if i := interfaceUnderPtr(p.Elem()); i != nil { |
| 663 | return nestedPtrInterface{typ: i} |
| 664 | } |
| 665 | // The same goes for nested function types. |
| 666 | if f := functionUnderPtr(p.Elem()); f != nil { |
| 667 | return nestedPtrFunction{typ: f} |
| 668 | } |
| 669 | return pointer{typ: p} |
| 670 | } |
| 671 | |
| 672 | switch v := val.(type) { |
| 673 | case *ssa.Const: |
| 674 | return constant{typ: val.Type()} |
| 675 | case *ssa.Global: |
| 676 | return global{val: v} |
| 677 | case *ssa.Function: |
| 678 | return function{f: v} |
| 679 | case *ssa.Parameter, *ssa.FreeVar, ssa.Instruction: |
| 680 | // ssa.Param, ssa.FreeVar, and a specific set of "register" instructions, |
| 681 | // satisifying the ssa.Value interface, can serve as local variables. |
| 682 | return local{val: v} |
| 683 | default: |
| 684 | panic(fmt.Errorf("unsupported value %v in node creation", val)) |
| 685 | } |
| 686 | } |
| 687 | |
| 688 | // representative returns a unique representative for node `n`. Since |
| 689 | // semantically equivalent types can have different implementations, |
| 690 | // this method guarantees the same implementation is always used. |
| 691 | func (b *builder) representative(n node) node { |
| 692 | if n.Type() == nil { |
| 693 | // panicArg and recoverReturn do not have |
| 694 | // types and are unique by definition. |
| 695 | return n |
| 696 | } |
| 697 | t := canonicalize(n.Type(), &b.canon) |
| 698 | |
| 699 | switch i := n.(type) { |
| 700 | case constant: |
| 701 | return constant{typ: t} |
| 702 | case pointer: |
| 703 | return pointer{typ: t.(*types.Pointer)} |
| 704 | case sliceElem: |
| 705 | return sliceElem{typ: t} |
| 706 | case mapKey: |
| 707 | return mapKey{typ: t} |
| 708 | case mapValue: |
| 709 | return mapValue{typ: t} |
| 710 | case channelElem: |
| 711 | return channelElem{typ: t} |
| 712 | case nestedPtrInterface: |
| 713 | return nestedPtrInterface{typ: t} |
| 714 | case nestedPtrFunction: |
| 715 | return nestedPtrFunction{typ: t} |
| 716 | case field: |
| 717 | return field{StructType: canonicalize(i.StructType, &b.canon), index: i.index} |
| 718 | case indexedLocal: |
| 719 | return indexedLocal{typ: t, val: i.val, index: i.index} |
| 720 | case local, global, panicArg, recoverReturn, function: |
| 721 | return n |
| 722 | default: |
| 723 | panic(fmt.Errorf("canonicalizing unrecognized node %v", n)) |
| 724 | } |
| 725 | } |
| 726 | |
| 727 | // canonicalize returns a type representative of `t` unique subject |
| 728 | // to type map `canon`. |
| 729 | func canonicalize(t types.Type, canon *typeutil.Map) types.Type { |
| 730 | rep := canon.At(t) |
| 731 | if rep != nil { |
| 732 | return rep.(types.Type) |
| 733 | } |
| 734 | canon.Set(t, t) |
| 735 | return t |
| 736 | } |
| 737 |
Members