Repository: joernio/joern (scala)

Issue:
[x2cpg] DynamicCallLinker Excludes Non-Overriden Inheritted Methods
In the following example:
```java
class Foo {

  private int x = 0;

  public int foo(int a) {
    this.x = a;
    return this.x;
  }
}

class Bar extends Foo {

  public int bar(int b) {
    return foo(b);
  }

}
```

The call to `foo` within the method `Foo.bar` gives a full name of `Bar.foo:int(int)`. The call graph does not see `Bar.foo` as this is not explicitly overridden and thus isn't a concrete method and simply an alias to the superclass.

Desired solution:
* Change the `methodFullName` of calls to the superclass if no overridden method is present
* Include superclass methods in the `validM` value set for a call in the `DynamicCallLinker`

Pull request:
- If no methods are in the list of callees, attempts to first resolve the result by inspecting the superclass method names and signatures
- The method full name still makes use of the derived full name

Resolves #2142

Patch:
diff --git a/joern-cli/frontends/x2cpg/src/main/scala/io/joern/x2cpg/passes/callgraph/DynamicCallLinker.scala b/joern-cli/frontends/x2cpg/src/main/scala/io/joern/x2cpg/passes/callgraph/DynamicCallLinker.scala
index 3fd1bf2ecbaf..4d5c53d48295 100644
--- a/joern-cli/frontends/x2cpg/src/main/scala/io/joern/x2cpg/passes/callgraph/DynamicCallLinker.scala
+++ b/joern-cli/frontends/x2cpg/src/main/scala/io/joern/x2cpg/passes/callgraph/DynamicCallLinker.scala
@@ -1,5 +1,6 @@
 package io.joern.x2cpg.passes.callgraph
 
+import io.joern.x2cpg.Defines.DynamicCallUnknownFallName
 import io.shiftleft.codepropertygraph.Cpg
 import io.shiftleft.codepropertygraph.generated.nodes.{Call, Method, TypeDecl}
 import io.shiftleft.codepropertygraph.generated.{DispatchTypes, EdgeTypes, PropertyNames}
@@ -8,6 +9,7 @@ import io.shiftleft.semanticcpg.language._
 import org.slf4j.{Logger, LoggerFactory}
 import overflowdb.{NodeDb, NodeRef}
 
+import scala.annotation.tailrec
 import scala.collection.mutable
 import scala.jdk.CollectionConverters._
 
@@ -29,7 +31,8 @@ class DynamicCallLinker(cpg: Cpg) extends CpgPass(cpg) {
   // the best interest of reproducibility during debugging.
   private val validM = mutable.Map.empty[String, mutable.LinkedHashSet[String]]
   // Used for dynamic programming as subtree's don't need to be recalculated later
-  private val subclassCache = mutable.Map.empty[String, mutable.LinkedHashSet[String]]
+  private val subclassCache   = mutable.Map.empty[String, mutable.LinkedHashSet[String]]
+  private val superclassCache = mutable.Map.empty[String, mutable.LinkedHashSet[String]]
   // Used for O(1) lookups on methods that will work without indexManager
   private val typeMap = mutable.Map.empty[String, TypeDecl]
   // For linking loose method stubs that cannot be resolved by crawling parent types
@@ -75,28 +78,51 @@ class DynamicCallLinker(cpg: Cpg) extends CpgPass(cpg) {
     }
   }
 
-  /** Recursively returns all the sub-types of the given type declaration. Does not account for circular hierarchies.
+  /** Recursively returns all the sub-types of the given type declaration. Does account for circular hierarchies.
     */
-  def allSubclasses(typDeclFullName: String): mutable.LinkedHashSet[String] = {
-    subclassCache.get(typDeclFullName) match {
-      case Some(value) => value
+  private def allSubclasses(typDeclFullName: String): mutable.LinkedHashSet[String] =
+    inheritanceTraversal(typDeclFullName, subclassCache, inSuperDirection = false)
+
+  /** Recursively returns all the super-types of the given type declaration. Does account for circular hierarchies.
+    */
+  private def allSuperClasses(typDeclFullName: String): mutable.LinkedHashSet[String] =
+    inheritanceTraversal(typDeclFullName, superclassCache, inSuperDirection = true)
+
+  private def inheritanceTraversal(
+    typDeclFullName: String,
+    cache: mutable.Map[String, mutable.LinkedHashSet[String]],
+    inSuperDirection: Boolean
+  ): mutable.LinkedHashSet[String] = {
+    cache.get(typDeclFullName) match {
+      case Some(superClasses) => superClasses
       case None =>
-        val directSubclasses =
-          cpg.typ
-            .nameExact(typDeclFullName)
-            .flatMap(_.in(EdgeTypes.INHERITS_FROM).asScala)
-            .collect { case x: TypeDecl =>
-              x.fullName
-            }
-            .to(mutable.LinkedHashSet)
-        // The second check makes sure that set is changing which wouldn't be the case in circular hierarchies
-        val totalSubclasses: mutable.LinkedHashSet[String] = if (directSubclasses.isEmpty) {
-          directSubclasses ++ mutable.LinkedHashSet(typDeclFullName)
-        } else {
-          directSubclasses.flatMap(t => allSubclasses(t)) ++ mutable.LinkedHashSet(typDeclFullName)
-        }
-        subclassCache.put(typDeclFullName, totalSubclasses)
-        totalSubclasses
+        val totalSuperclasses = (cpg.typeDecl
+          .fullNameExact(typDeclFullName)
+          .headOption match {
+          case Some(curr) => inheritTraversal(curr, inSuperDirection)
+          case None       => mutable.LinkedHashSet.empty
+        }).map(_.fullName)
+        cache.put(typDeclFullName, totalSuperclasses)
+        totalSuperclasses
+    }
+  }
+
+  private def inheritTraversal(
+    cur: TypeDecl,
+    inSuperDirection: Boolean,
+    visitedNodes: mutable.LinkedHashSet[TypeDecl] = mutable.LinkedHashSet.empty
+  ): mutable.LinkedHashSet[TypeDecl] = {
+    if (visitedNodes.contains(cur)) return visitedNodes
+    visitedNodes.addOne(cur)
+
+    (if (inSuperDirection) cpg.typeDecl.fullNameExact(cur.fullName).flatMap(_.inheritsFromOut.referencedTypeDecl)
+     else cpg.typ.fullNameExact(cur.fullName).flatMap(_.inheritsFromIn))
+      .collectAll[TypeDecl]
+      .to(mutable.LinkedHashSet) match {
+      case classesToEval if classesToEval.isEmpty => visitedNodes
+      case classesToEval =>
+        classesToEval.flatMap(t => inheritTraversal(t, inSuperDirection, visitedNodes))
+        visitedNodes
     }
   }
 
@@ -114,7 +140,32 @@ class DynamicCallLinker(cpg: Cpg) extends CpgPass(cpg) {
     }
   }
 
+  private def resolveCallInSuperClasses(call: Call): Boolean = {
+    if (!call.methodFullName.contains(":")) return false
+    def split(str: String, n: Int) = (str.take(n), str.drop(n + 1))
+    val (fullName, signature)      = split(call.methodFullName, call.methodFullName.lastIndexOf(":"))
+    val typeDeclFullName           = fullName.replace(s".${call.name}", "")
+    val candidateInheritedMethods =
+      cpg.typeDecl
+        .fullNameExact(allSuperClasses(typeDeclFullName).toArray: _*)
+        .astChildren
+        .isMethod
+        .name(call.name)
+        .and(_.signatureExact(signature))
+        .fullName
+        .l
+    if (candidateInheritedMethods.nonEmpty) {
+      validM.put(call.methodFullName, mutable.LinkedHashSet.from(candidateInheritedMethods))
+      true
+    } else {
+      false
+    }
+  }
+
+  @tailrec
   private def linkDynamicCall(call: Call, dstGraph: DiffGraphBuilder): Unit = {
+    // This call linker requires a method full name entry
+    if (call.methodFullName.equals("<empty>") || call.methodFullName.equals(DynamicCallUnknownFallName)) return
     validM.get(call.methodFullName) match {
       case Some(tgts) =>
         val callsOut = call.callOut.fullName.toSetImmutable
@@ -130,7 +181,11 @@ class DynamicCallLinker(cpg: Cpg) extends CpgPass(cpg) {
             fallbackToStaticResolution(call, dstGraph)
           }
         }
-      case None => fallbackToStaticResolution(call, dstGraph)
+      case None if resolveCallInSuperClasses(call) =>
+        // Resolve "hidden" inherited method and leave an alias for the result in validM, then retry
+        linkDynamicCall(call, dstGraph)
+      case None =>
+        fallbackToStaticResolution(call, dstGraph)
     }
   }
 


Test patch:
diff --git a/joern-cli/frontends/jimple2cpg/src/test/scala/io/joern/jimple2cpg/querying/DynamicCallGraphTests.scala b/joern-cli/frontends/jimple2cpg/src/test/scala/io/joern/jimple2cpg/querying/DynamicCallGraphTests.scala
index 5192752005fe..ece23d2d839f 100644
--- a/joern-cli/frontends/jimple2cpg/src/test/scala/io/joern/jimple2cpg/querying/DynamicCallGraphTests.scala
+++ b/joern-cli/frontends/jimple2cpg/src/test/scala/io/joern/jimple2cpg/querying/DynamicCallGraphTests.scala
@@ -3,54 +3,54 @@ package io.joern.jimple2cpg.querying
 import io.joern.jimple2cpg.testfixtures.JimpleCode2CpgFixture
 import io.shiftleft.semanticcpg.language.{NoResolve, _}
 
-class DynamicCallGraphTests extends JimpleCode2CpgFixture {
+class DynamicCallGraphTests1 extends JimpleCode2CpgFixture {
 
   implicit val resolver: NoResolve.type = NoResolve
 
-  val cpg = code("""
-class Foo {
-
-	public static void main(String[] args){
-		A b1 = new B();
-		A c1 = new C();
-
-		A b2 = b1;
-		A c2 = c1;
-
-		// what will get printed?
-		b2.print(c2);
-	}
-
-	public static class A extends Object {
-		public void print(A object) {
-			System.out.println("An instance of " + object.getClass().getSimpleName()
-					+ " was passed to A's print(A object)");
-		}
-	}
-
-	public static class B extends A {
-		public void print(A object) {
-			System.out.println("An instance of " + object.getClass().getSimpleName()
-					+ " was passed to B's print(A object)");
-		}
-	}
-
-	public static class C extends B {
-		public void print(A object) {
-			System.out.println("An instance of " + object.getClass().getSimpleName()
-					+ " was passed to C's print(A object)");
-		}
-	}
-
-	public static class D extends A {
-		public void print(A object) {
-			System.out.println("An instance of " + object.getClass().getSimpleName()
-					+ " was passed to D's print(A object)");
-		}
-	}
-
-}
-    """)
+  private val cpg = code("""
+      |class Foo {
+      |
+      |      public static void main(String[] args){
+      |          A b1 = new B();
+      |          A c1 = new C();
+      |
+      |          A b2 = b1;
+      |          A c2 = c1;
+      |
+      |          // what will get printed?
+      |          b2.print(c2);
+      |      }
+      |
+      |      public static class A extends Object {
+      |          public void print(A object) {
+      |              System.out.println("An instance of " + object.getClass().getSimpleName()
+      |                      + " was passed to A's print(A object)");
+      |          }
+      |      }
+      |
+      |      public static class B extends A {
+      |          public void print(A object) {
+      |              System.out.println("An instance of " + object.getClass().getSimpleName()
+      |                      + " was passed to B's print(A object)");
+      |          }
+      |      }
+      |
+      |      public static class C extends B {
+      |          public void print(A object) {
+      |              System.out.println("An instance of " + object.getClass().getSimpleName()
+      |                      + " was passed to C's print(A object)");
+      |          }
+      |      }
+      |
+      |      public static class D extends A {
+      |          public void print(A object) {
+      |              System.out.println("An instance of " + object.getClass().getSimpleName()
+      |                      + " was passed to D's print(A object)");
+      |          }
+      |      }
+      |
+      |}
+      |""".stripMargin)
 
   "should find that add is called by main" in {
     cpg.method.name("print").caller.name.toSetMutable shouldBe Set("main")
@@ -66,3 +66,41 @@ class Foo {
   }
 
 }
+
+class DynamicCallGraphTests2 extends JimpleCode2CpgFixture {
+
+  implicit val resolver: NoResolve.type = NoResolve
+
+  private val cpg = code("""
+      |class Foo {
+      |
+      |  private int x = 0;
+      |
+      |  public int foo(int a) {
+      |    this.x = a;
+      |    return this.x;
+      |  }
+      |}
+      |
+      |class Bar extends Foo {
+      |
+      |  public int bar(int b) {
+      |    return foo(b);
+      |  }
+      |
+      |}
+      |""".stripMargin)
+
+  "should find that foo is still called with the derived full name" in {
+    cpg.call.name("foo").methodFullName.toSetMutable shouldBe Set("Bar.foo:int(int)")
+  }
+
+  "should find that foo is not defined and thus point to the superclass implementation" in {
+    cpg.method.name("foo").caller.name.toSetMutable shouldBe Set("bar")
+  }
+
+  "should account for call to inherited superclass" in {
+    cpg.call.name("foo").callee.definingTypeDecl.fullName.toSetMutable shouldBe Set("Foo")
+  }
+
+}