Repository: joernio/joern (scala)

Issue:
Separate Type Recovery Stubs in a Different Namespace
**Is your feature request related to a problem? Please describe.**
Normal method stubs are generated when after the base AST pass, which only sets method full names based on mostly factual information. The stubs generated by `XTypeRecovery` are speculatively built on heuristics, which may lead to invalid methods at times - where the value is mostly knowing what namespace the method is a part of. It would be good to separate these.

**Describe the solution you'd like**
Some kind of namespace such as `speculative` might be good for methods generated by `XTypeRecovery` that were not already in the CPG after the base passes.

**Additional context**
Spoke offline with @ml86 about this. Relates to issues introduced by[ this PR](https://github.com/joernio/joern/pull/2282/files) where type stubs are generated speculatively from method full name in `X2Cpg` which is not sound.

Pull request:
MethodStubs generated by the type recovery that end up not matching up to an existing method (or associate with a type that does not exist) will be associated with a special namespace.

Resolves #2673

Patch:
diff --git a/joern-cli/frontends/x2cpg/src/main/scala/io/joern/x2cpg/passes/base/MethodStubCreator.scala b/joern-cli/frontends/x2cpg/src/main/scala/io/joern/x2cpg/passes/base/MethodStubCreator.scala
index cf31e69ae74f..a54b248cd339 100644
--- a/joern-cli/frontends/x2cpg/src/main/scala/io/joern/x2cpg/passes/base/MethodStubCreator.scala
+++ b/joern-cli/frontends/x2cpg/src/main/scala/io/joern/x2cpg/passes/base/MethodStubCreator.scala
@@ -11,7 +11,7 @@ import overflowdb.BatchedUpdate
 import overflowdb.BatchedUpdate.DiffGraphBuilder
 
 import scala.collection.mutable
-import scala.util.{Success, Try}
+import scala.util.Try
 
 case class CallSummary(name: String, signature: String, fullName: String, dispatchType: String)
 
@@ -75,32 +75,6 @@ object MethodStubCreator {
     }
   }
 
-  /** Will attempt to link the method stub to a type declaration if one exists. This uses the `name` and `fullName`
-    * properties of the stub to determine the type declaration.
-    *
-    * Method full names take 2 designs in the CPG. This approach works for both.
-    *
-    * 1: Dynamic languages do `filename`:`some_path`.`call_name`.`optional_info`
-    *
-    * 2: Static languages do `namespace`.`type_name`.`call_name`:`signature`
-    *
-    * @param stub
-    *   the method stub.
-    * @return
-    *   the type declaration string, if successfully generated.
-    */
-  private def addTypeDeclInfo(stub: NewMethod): Option[String] = {
-    Try {
-      val nameIdx = stub.fullName.indexOf(stub.name)
-      stub.fullName.substring(0, nameIdx - 1)
-    } match {
-      case Success(typeFullName) if typeFullName != "" && !typeFullName.startsWith("<operator>") =>
-        stub.astParentFullName(typeFullName).astParentType(NodeTypes.TYPE_DECL)
-        Some(typeFullName)
-      case _ => None
-    }
-  }
-
   def createMethodStub(
     name: String,
     fullName: String,
@@ -108,19 +82,20 @@ object MethodStubCreator {
     dispatchType: String,
     parameterCount: Int,
     dstGraph: DiffGraphBuilder,
-    isExternal: Boolean = true
+    isExternal: Boolean = true,
+    astParentType: String = NodeTypes.NAMESPACE_BLOCK,
+    astParentFullName: String = "<global>"
   ): NewMethod = {
     val methodNode = NewMethod()
       .name(name)
       .fullName(fullName)
       .isExternal(isExternal)
       .signature(signature)
-      .astParentType(NodeTypes.NAMESPACE_BLOCK)
-      .astParentFullName("<global>")
+      .astParentType(astParentType)
+      .astParentFullName(astParentFullName)
       .order(0)
 
     addLineNumberInfo(methodNode, fullName)
-    addTypeDeclInfo(methodNode)
 
     dstGraph.addNode(methodNode)
 
diff --git a/joern-cli/frontends/x2cpg/src/main/scala/io/joern/x2cpg/passes/frontend/XTypeHintCallLinker.scala b/joern-cli/frontends/x2cpg/src/main/scala/io/joern/x2cpg/passes/frontend/XTypeHintCallLinker.scala
index 654736c7e6ac..11e74df94909 100644
--- a/joern-cli/frontends/x2cpg/src/main/scala/io/joern/x2cpg/passes/frontend/XTypeHintCallLinker.scala
+++ b/joern-cli/frontends/x2cpg/src/main/scala/io/joern/x2cpg/passes/frontend/XTypeHintCallLinker.scala
@@ -2,8 +2,8 @@ package io.joern.x2cpg.passes.frontend
 
 import io.joern.x2cpg.passes.base.MethodStubCreator
 import io.shiftleft.codepropertygraph.Cpg
-import io.shiftleft.codepropertygraph.generated.nodes.{Call, Method, MethodBase, NewMethod}
-import io.shiftleft.codepropertygraph.generated.{EdgeTypes, PropertyNames}
+import io.shiftleft.codepropertygraph.generated.nodes._
+import io.shiftleft.codepropertygraph.generated.{EdgeTypes, NodeTypes, PropertyNames}
 import io.shiftleft.passes.CpgPass
 import io.shiftleft.proto.cpg.Cpg.DispatchTypes
 import io.shiftleft.semanticcpg.language._
@@ -40,6 +40,7 @@ abstract class XTypeHintCallLinker(cpg: Cpg) extends CpgPass(cpg) {
     val callerAndCallees = calls.map(call => (call, calleeNames(call))).toList
     val methodMap        = mapMethods(callerAndCallees, builder)
     linkCallsToCallees(callerAndCallees, methodMap, builder)
+    linkSpeculativeNamespaceNodes(methodMap.view.values.collectAll[NewMethod], builder)
   }
 
   protected def mapMethods(
@@ -104,16 +105,66 @@ abstract class XTypeHintCallLinker(cpg: Cpg) extends CpgPass(cpg) {
       if (methodName.contains(pathSep) && methodName.length > methodName.lastIndexOf(pathSep) + 1)
         methodName.substring(methodName.lastIndexOf(pathSep) + 1)
       else methodName
+    createMethodStub(name, methodName, call.argumentOut.size, isExternal, builder)
+  }
+
+  /** Try to extract a type full name from the method full name, if one exists in the CPG then we are lucky and we use
+    * it, else we ignore for now.
+    */
+  protected def createMethodStub(
+    name: String,
+    fullName: String,
+    argSize: Int,
+    isExternal: Boolean,
+    builder: DiffGraphBuilder
+  ): NewMethod = {
+    val nameIdx = fullName.lastIndexOf(name)
+    val default = (NodeTypes.NAMESPACE_BLOCK, XTypeHintCallLinker.namespace)
+    val (astParentType, astParentFullName) =
+      if (!fullName.isBlank && !fullName.startsWith("<operator") && nameIdx > 0) {
+        cpg.typeDecl
+          .fullNameExact(fullName.substring(0, nameIdx - 1))
+          .map(t => t.label -> t.fullName)
+          .headOption
+          .getOrElse(default)
+      } else {
+        default
+      }
+
     MethodStubCreator
       .createMethodStub(
         name,
-        methodName,
+        fullName,
         "",
         DispatchTypes.DYNAMIC_DISPATCH.name(),
-        call.argumentOut.size,
+        argSize,
         builder,
-        isExternal
+        isExternal,
+        astParentType,
+        astParentFullName
       )
   }
 
+  /** Once we have connected methods that were speculatively generated and managed to correctly link to methods already
+    * in the CPG, we link the rest to the "speculativeMethods" namespace as a way to show that these may not actually
+    * exist.
+    */
+  protected def linkSpeculativeNamespaceNodes(newMethods: IterableOnce[NewMethod], builder: DiffGraphBuilder): Unit = {
+    val speculativeNamespace =
+      NewNamespaceBlock().name(XTypeHintCallLinker.namespace).fullName(XTypeHintCallLinker.namespace)
+
+    builder.addNode(speculativeNamespace)
+    newMethods
+      .filter(_.astParentFullName == XTypeHintCallLinker.namespace)
+      .foreach(m => builder.addEdge(speculativeNamespace, m, EdgeTypes.AST))
+  }
+}
+
+object XTypeHintCallLinker {
+
+  /** The shared namespace for all methods generated from the type recovery that may not exist with this exact full name
+    * in reality.
+    */
+  val namespace: String = "<speculatedMethods>"
+
 }


Test patch:
diff --git a/joern-cli/frontends/pysrc2cpg/src/test/scala/io/joern/pysrc2cpg/passes/TypeRecoveryPassTests.scala b/joern-cli/frontends/pysrc2cpg/src/test/scala/io/joern/pysrc2cpg/passes/TypeRecoveryPassTests.scala
index 73d02adefd38..a70beb0390c4 100644
--- a/joern-cli/frontends/pysrc2cpg/src/test/scala/io/joern/pysrc2cpg/passes/TypeRecoveryPassTests.scala
+++ b/joern-cli/frontends/pysrc2cpg/src/test/scala/io/joern/pysrc2cpg/passes/TypeRecoveryPassTests.scala
@@ -1,6 +1,7 @@
 package io.joern.pysrc2cpg.passes
 
 import io.joern.pysrc2cpg.PySrc2CpgFixture
+import io.joern.x2cpg.passes.frontend.XTypeHintCallLinker
 import io.shiftleft.semanticcpg.language._
 
 import java.io.File
@@ -35,9 +36,10 @@ class TypeRecoveryPassTests extends PySrc2CpgFixture(withOssDataflow = false) {
     }
 
     "resolve 'z' identifier calls conservatively" in {
-      // TODO: These should have callee entries but the method stubs are not present here
       val List(zAppend) = cpg.call("append").l
       zAppend.methodFullName shouldBe "<unknownFullName>"
+      // Since we don't have method nodes with this full name, this should belong to the call linker namespace
+      zAppend.callee.astParentFullName.headOption shouldBe Some(XTypeHintCallLinker.namespace)
       zAppend.dynamicTypeHintFullName shouldBe Seq(
         "__builtin.dict.append",
         "__builtin.list.append",