search

wala / WALA

T.J. Watson Libraries for Analysis, with frontends for Java, Android, and JavaScript, and may common static program analyses
http://github.com/wala/WALA
Eclipse Public License 2.0
743 stars 221 forks source link

Multiple fake root nodes? #259

Open khatchad opened 6 years ago

khatchad commented 6 years ago

I understand:

  1. WALA may create fake root nodes in the call graph.
  2. A call graph may have multiple nodes representing a single method due to context sensitivity.

However, I don't quite understand why WALA would make multiple *fake root nodes. Wouldn't one suffice? In particular, I am seeing the following nodes correspond to a particular method:

Node: < Application, Lcom/iluwatar/abstractdocument/App, <init>()V > Context: CallStringContext: [ com.ibm.wala.FakeRootClass.fakeRootMethod()V@2 ]
Node: < Application, Lcom/iluwatar/abstractdocument/App, <init>()V > Context: CallStringContext: [ com.ibm.wala.FakeRootClass.fakeRootMethod()V@3 ]
khatchad commented 6 years ago

Here's the IR corresponding to the above nodes:

synthetic < Primordial, Lcom/ibm/wala/FakeRootClass, fakeRootMethod()V >
CFG:
BB0[0..0]
    -> BB1
    -> BB85
BB1[1..1]
    -> BB2
    -> BB85
BB2[2..2]
    -> BB3
    -> BB85
BB3[3..3]
    -> BB4
    -> BB85
BB4[4..4]
    -> BB5
    -> BB85
BB5[5..5]
    -> BB6
    -> BB85
BB6[6..6]
    -> BB7
    -> BB85
BB7[7..7]
    -> BB8
    -> BB85
BB8[8..8]
    -> BB9
    -> BB85
BB9[9..9]
    -> BB10
    -> BB85
BB10[10..10]
    -> BB11
    -> BB85
BB11[11..11]
    -> BB12
    -> BB85
BB12[12..12]
    -> BB13
    -> BB85
BB13[13..13]
    -> BB14
    -> BB85
BB14[14..14]
    -> BB15
    -> BB85
BB15[15..15]
    -> BB16
    -> BB85
BB16[16..16]
    -> BB17
    -> BB85
BB17[17..17]
    -> BB18
    -> BB85
BB18[18..18]
    -> BB19
    -> BB85
BB19[19..19]
    -> BB20
    -> BB85
BB20[20..20]
    -> BB21
    -> BB85
BB21[21..21]
    -> BB22
    -> BB85
BB22[22..22]
    -> BB23
    -> BB85
BB23[23..23]
    -> BB24
    -> BB85
BB24[24..24]
    -> BB25
    -> BB85
BB25[25..25]
    -> BB26
    -> BB85
BB26[26..26]
    -> BB27
    -> BB85
BB27[27..27]
    -> BB28
    -> BB85
BB28[28..28]
    -> BB29
    -> BB85
BB29[29..29]
    -> BB30
    -> BB85
BB30[30..30]
    -> BB31
    -> BB85
BB31[31..31]
    -> BB32
    -> BB85
BB32[32..32]
    -> BB33
    -> BB85
BB33[33..33]
    -> BB34
    -> BB85
BB34[34..34]
    -> BB35
    -> BB85
BB35[35..35]
    -> BB36
    -> BB85
BB36[36..36]
    -> BB37
    -> BB85
BB37[37..37]
    -> BB38
    -> BB85
BB38[38..38]
    -> BB39
    -> BB85
BB39[39..39]
    -> BB40
    -> BB85
BB40[40..40]
    -> BB41
    -> BB85
BB41[41..41]
    -> BB42
    -> BB85
BB42[42..42]
    -> BB43
    -> BB85
BB43[43..43]
    -> BB44
    -> BB85
BB44[44..44]
    -> BB45
    -> BB85
BB45[45..45]
    -> BB46
    -> BB85
BB46[46..46]
    -> BB47
    -> BB85
BB47[47..47]
    -> BB48
    -> BB85
BB48[48..48]
    -> BB49
    -> BB85
BB49[49..49]
    -> BB50
    -> BB85
BB50[50..50]
    -> BB51
    -> BB85
BB51[51..51]
    -> BB52
    -> BB85
BB52[52..52]
    -> BB53
    -> BB85
BB53[53..53]
    -> BB54
    -> BB85
BB54[54..54]
    -> BB55
    -> BB85
BB55[55..55]
    -> BB56
    -> BB85
BB56[56..56]
    -> BB57
    -> BB85
BB57[57..57]
    -> BB58
    -> BB85
BB58[58..58]
    -> BB59
    -> BB85
BB59[59..59]
    -> BB60
    -> BB85
BB60[60..60]
    -> BB61
    -> BB85
BB61[61..61]
    -> BB62
    -> BB85
BB62[62..62]
    -> BB63
    -> BB85
BB63[63..63]
    -> BB64
    -> BB85
BB64[64..64]
    -> BB65
    -> BB85
BB65[65..65]
    -> BB66
    -> BB85
BB66[66..66]
    -> BB67
    -> BB85
BB67[67..67]
    -> BB68
    -> BB85
BB68[68..68]
    -> BB69
    -> BB85
BB69[69..69]
    -> BB70
    -> BB85
BB70[70..70]
    -> BB71
    -> BB85
BB71[71..71]
    -> BB72
    -> BB85
BB72[72..72]
    -> BB73
    -> BB85
BB73[73..73]
    -> BB74
    -> BB85
BB74[74..74]
    -> BB75
    -> BB85
BB75[75..75]
    -> BB76
    -> BB85
BB76[76..76]
    -> BB77
    -> BB85
BB77[77..77]
    -> BB78
    -> BB85
BB78[78..78]
    -> BB79
    -> BB85
BB79[79..79]
    -> BB80
    -> BB85
BB80[80..80]
    -> BB81
    -> BB85
BB81[81..81]
    -> BB82
    -> BB85
BB82[82..82]
    -> BB83
    -> BB85
BB83[83..83]
    -> BB84
    -> BB85
BB84[84..84]
    -> BB85
BB85[-1..-2]
Instructions:
BB0
0   invokestatic < Primordial, Lcom/ibm/wala/FakeRootClass, fakeWorldClinit()V > @0 exception:v2
BB1
1   v3 = new <Application,Lcom/iluwatar/abstractdocument/App>@1
BB2
2   invokespecial < Application, Lcom/iluwatar/abstractdocument/App, <init>()V > v3 @2 exception:v4
BB3
3   invokespecial < Application, Lcom/iluwatar/abstractdocument/App, <init>()V > v3 @3 exception:v5
BB4
4   v6 = new <Primordial,Ljava/io/FileInputStream>@4
BB5
5   invokespecial < Primordial, Ljava/io/InputStream, <init>()V > v6 @5 exception:v7
BB6
6   invokevirtual < Primordial, Ljava/io/FileInputStream, finalize()V > v6 @6 exception:v8
BB7
7   v9 = new <Primordial,Ljava/io/FileOutputStream>@7
BB8
8   invokespecial < Primordial, Ljava/io/OutputStream, <init>()V > v9 @8 exception:v10
BB9
9   invokevirtual < Primordial, Ljava/io/FileOutputStream, finalize()V > v9 @9 exception:v11
BB10
10   v12 = new <Primordial,Ljava/util/stream/StreamOpFlag>@10
BB11
11   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v12 @11 exception:v13
BB12
12   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v12 @12 exception:v14
BB13
13   v15 = new <Primordial,Ljava/util/stream/StreamOpFlag$Type>@13
BB14
14   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v15 @14 exception:v16
BB15
15   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v15 @15 exception:v17
BB16
16   v18 = new <Primordial,Ljava/util/stream/StreamShape>@16
BB17
17   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v18 @17 exception:v19
BB18
18   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v18 @18 exception:v20
BB19
19   v21 = new <Primordial,Ljava/util/Locale$Category>@19
BB20
20   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v21 @20 exception:v22
BB21
21   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v21 @21 exception:v23
BB22
22   v24 = new <Primordial,Ljava/util/regex/UnicodeProp$1>@22
BB23
23   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v24 @23 exception:v25
BB24
24   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v24 @24 exception:v26
BB25
25   v27 = new <Primordial,Ljava/util/regex/UnicodeProp$2>@25
BB26
26   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v27 @26 exception:v28
BB27
27   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v27 @27 exception:v29
BB28
28   v30 = new <Primordial,Ljava/util/regex/UnicodeProp$3>@28
BB29
29   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v30 @29 exception:v31
BB30
30   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v30 @30 exception:v32
BB31
31   v33 = new <Primordial,Ljava/util/regex/UnicodeProp$4>@31
BB32
32   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v33 @32 exception:v34
BB33
33   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v33 @33 exception:v35
BB34
34   v36 = new <Primordial,Ljava/util/regex/UnicodeProp$5>@34
BB35
35   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v36 @35 exception:v37
BB36
36   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v36 @36 exception:v38
BB37
37   v39 = new <Primordial,Ljava/util/regex/UnicodeProp$6>@37
BB38
38   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v39 @38 exception:v40
BB39
39   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v39 @39 exception:v41
BB40
40   v42 = new <Primordial,Ljava/util/regex/UnicodeProp$7>@40
BB41
41   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v42 @41 exception:v43
BB42
42   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v42 @42 exception:v44
BB43
43   v45 = new <Primordial,Ljava/util/regex/UnicodeProp$8>@43
BB44
44   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v45 @44 exception:v46
BB45
45   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v45 @45 exception:v47
BB46
46   v48 = new <Primordial,Ljava/util/regex/UnicodeProp$9>@46
BB47
47   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v48 @47 exception:v49
BB48
48   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v48 @48 exception:v50
BB49
49   v51 = new <Primordial,Ljava/util/regex/UnicodeProp$10>@49
BB50
50   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v51 @50 exception:v52
BB51
51   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v51 @51 exception:v53
BB52
52   v54 = new <Primordial,Ljava/util/regex/UnicodeProp$11>@52
BB53
53   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v54 @53 exception:v55
BB54
54   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v54 @54 exception:v56
BB55
55   v57 = new <Primordial,Ljava/util/regex/UnicodeProp$12>@55
BB56
56   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v57 @56 exception:v58
BB57
57   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v57 @57 exception:v59
BB58
58   v60 = new <Primordial,Ljava/util/regex/UnicodeProp$13>@58
BB59
59   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v60 @59 exception:v61
BB60
60   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v60 @60 exception:v62
BB61
61   v63 = new <Primordial,Ljava/util/regex/UnicodeProp$14>@61
BB62
62   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v63 @62 exception:v64
BB63
63   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v63 @63 exception:v65
BB64
64   v66 = new <Primordial,Ljava/util/regex/UnicodeProp$15>@64
BB65
65   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v66 @65 exception:v67
BB66
66   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v66 @66 exception:v68
BB67
67   v69 = new <Primordial,Ljava/util/regex/UnicodeProp$16>@67
BB68
68   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v69 @68 exception:v70
BB69
69   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v69 @69 exception:v71
BB70
70   v72 = new <Primordial,Ljava/util/regex/UnicodeProp$17>@70
BB71
71   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v72 @71 exception:v73
BB72
72   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v72 @72 exception:v74
BB73
73   v75 = new <Primordial,Ljava/util/regex/UnicodeProp$18>@73
BB74
74   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v75 @74 exception:v76
BB75
75   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v75 @75 exception:v77
BB76
76   v78 = new <Primordial,Ljava/util/regex/UnicodeProp$19>@76
BB77
77   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v78 @77 exception:v79
BB78
78   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v78 @78 exception:v80
BB79
79   v81 = new <Primordial,Ljava/lang/Character$UnicodeScript>@79
BB80
80   invokespecial < Primordial, Ljava/lang/Object, <init>()V > v81 @80 exception:v82
BB81
81   invokevirtual < Primordial, Ljava/lang/Enum, finalize()V > v81 @81 exception:v83
BB82
82   v84 = new <Application,Lcom/iluwatar/abstractdocument/App>@82
BB83
83   invokespecial < Application, Lcom/iluwatar/abstractdocument/App, <init>()V > v84 @83 exception:v85
BB84
84   invokespecial < Application, Lcom/iluwatar/abstractdocument/App, <init>()V > v84 @84 exception:v86
BB85
khatchad commented 6 years ago

It seems odd that the ctor is called twice.

juliandolby commented 6 years ago

It looks like there is, in fact, only one fact root node, and the multiple constructor contexts come from call string sensitivity. However, it does seem odd that the fake root node ends up with two creations of com.iluwatar.abstractdocument.App, and then each of those gets two constructor calls.

Could you attach the driver code used to create this call graph? I want to understand what could cause this.