Repository: joernio/joern (scala)

Issue:
Dataflow semantic of assignments
Hi, I just noticed that data does not propagate over multiple assignments, e.g., `a = b = c`.  The dataflow semantic for assignments should include the return value as output.

Pull request:
Fix #1921

Patch:
diff --git a/dataflowengineoss/src/main/scala/io/joern/dataflowengineoss/DefaultSemantics.scala b/dataflowengineoss/src/main/scala/io/joern/dataflowengineoss/DefaultSemantics.scala
index ed2c36d20164..f860bb5152d3 100644
--- a/dataflowengineoss/src/main/scala/io/joern/dataflowengineoss/DefaultSemantics.scala
+++ b/dataflowengineoss/src/main/scala/io/joern/dataflowengineoss/DefaultSemantics.scala
@@ -18,19 +18,19 @@ object DefaultSemantics {
   def operatorFlows: List[FlowSemantic] = List(
     F(Operators.addition, List((1, -1), (2, -1))),
     F(Operators.addressOf, List((1, -1))),
-    F(Operators.assignment, List((2, 1))),
-    F(Operators.assignmentAnd, List((2, 1), (1, 1))),
-    F(Operators.assignmentArithmeticShiftRight, List((2, 1), (1, 1))),
-    F(Operators.assignmentDivision, List((2, 1), (1, 1))),
-    F(Operators.assignmentExponentiation, List((2, 1), (1, 1))),
-    F(Operators.assignmentLogicalShiftRight, List((2, 1), (1, 1))),
-    F(Operators.assignmentMinus, List((2, 1), (1, 1))),
-    F(Operators.assignmentModulo, List((2, 1), (1, 1))),
-    F(Operators.assignmentMultiplication, List((2, 1), (1, 1))),
-    F(Operators.assignmentOr, List((2, 1), (1, 1))),
-    F(Operators.assignmentPlus, List((2, 1), (1, 1))),
-    F(Operators.assignmentShiftLeft, List((2, 1), (1, 1))),
-    F(Operators.assignmentXor, List((2, 1), (1, 1))),
+    F(Operators.assignment, List((2, 1), (2, -1))),
+    F(Operators.assignmentAnd, List((2, 1), (1, 1), (2, -1))),
+    F(Operators.assignmentArithmeticShiftRight, List((2, 1), (1, 1), (2, -1))),
+    F(Operators.assignmentDivision, List((2, 1), (1, 1), (2, -1))),
+    F(Operators.assignmentExponentiation, List((2, 1), (1, 1), (2, -1))),
+    F(Operators.assignmentLogicalShiftRight, List((2, 1), (1, 1), (2, -1))),
+    F(Operators.assignmentMinus, List((2, 1), (1, 1), (2, -1))),
+    F(Operators.assignmentModulo, List((2, 1), (1, 1), (2, -1))),
+    F(Operators.assignmentMultiplication, List((2, 1), (1, 1), (2, -1))),
+    F(Operators.assignmentOr, List((2, 1), (1, 1), (2, -1))),
+    F(Operators.assignmentPlus, List((2, 1), (1, 1), (2, -1))),
+    F(Operators.assignmentShiftLeft, List((2, 1), (1, 1), (2, -1))),
+    F(Operators.assignmentXor, List((2, 1), (1, 1), (2, -1))),
     F(Operators.cast, List((1, -1), (2, -1))),
     F(Operators.computedMemberAccess, List((1, -1))),
     F(Operators.conditional, List((2, -1), (3, -1))),
@@ -49,10 +49,10 @@ object DefaultSemantics {
     F(Operators.indirection, List((1, -1))),
     F(Operators.memberAccess, List((1, -1))),
     F(Operators.pointerShift, List((1, -1))),
-    F(Operators.postDecrement, List((1, 1))),
-    F(Operators.postIncrement, List((1, 1))),
-    F(Operators.preDecrement, List((1, 1))),
-    F(Operators.preIncrement, List((1, 1))),
+    F(Operators.postDecrement, List((1, 1), (1, -1))),
+    F(Operators.postIncrement, List((1, 1), (1, -1))),
+    F(Operators.preDecrement, List((1, 1), (1, -1))),
+    F(Operators.preIncrement, List((1, 1), (1, -1))),
     F(Operators.sizeOf, List()),
 
     //  some of those operators have duplicate mappings due to a typo


Test patch:
diff --git a/joern-cli/frontends/c2cpg/src/test/scala/io/joern/c2cpg/dataflow/DataFlowTests.scala b/joern-cli/frontends/c2cpg/src/test/scala/io/joern/c2cpg/dataflow/DataFlowTests.scala
index 83758e4d54b8..2dda960b1a40 100644
--- a/joern-cli/frontends/c2cpg/src/test/scala/io/joern/c2cpg/dataflow/DataFlowTests.scala
+++ b/joern-cli/frontends/c2cpg/src/test/scala/io/joern/c2cpg/dataflow/DataFlowTests.scala
@@ -1199,12 +1199,15 @@ class DataFlowTests extends DataFlowCodeToCpgSuite {
         |
         |""".stripMargin)
 
-    "find that there is no flow from `y = 1` to exit node" in {
+    "find that there is a flow from `y = 1` to exit node" in {
+      // This one may be a bit surprising, but what's happening here
+      // is that the expression "y = 1" flows to the exit node, and
+      // since that is influenced by 1, there is in fact a flow from
+      // "1" to the exit node.
       val source = cpg.literal("1")
       val sink   = cpg.method("foo").methodReturn
-
-      val flows = sink.reachableByFlows(source)
-      flows.size shouldBe 0
+      val flows  = sink.reachableByFlows(source)
+      flows.size shouldBe 1
     }
   }
 
@@ -2153,4 +2156,29 @@ class DataFlowTestsWithCallDepth extends DataFlowCodeToCpgSuite {
       freeArg.reachableByFlows(freeArg).count(path => path.elements.size > 1) shouldBe 1
     }
   }
+
+  "DataFlowTest69" should {
+    val cpg = code("""
+        |void sink(int);
+        |
+        |void foo() {
+        |	int val = 42, a, b;
+        |	a = b = val;
+        |	sink(a);
+        |}
+        |
+        |void bar() {
+        |	int val = 42, a;
+        |	a = val++;
+        |	sink(a);
+        |}
+        |
+        |""".stripMargin)
+
+    "find flows" in {
+      val sink = cpg.method("sink").parameter.index(1).l
+      val src  = cpg.literal.l
+      sink.reachableBy(src).method.name.toSet shouldBe Set("foo", "bar")
+    }
+  }
 }
diff --git a/joern-cli/frontends/c2cpg/src/test/scala/io/joern/c2cpg/io/dotgenerator/DotDdgGeneratorTests.scala b/joern-cli/frontends/c2cpg/src/test/scala/io/joern/c2cpg/io/dotgenerator/DotDdgGeneratorTests.scala
index b626a4feebd3..4645f60ff81f 100644
--- a/joern-cli/frontends/c2cpg/src/test/scala/io/joern/c2cpg/io/dotgenerator/DotDdgGeneratorTests.scala
+++ b/joern-cli/frontends/c2cpg/src/test/scala/io/joern/c2cpg/io/dotgenerator/DotDdgGeneratorTests.scala
@@ -26,7 +26,7 @@ class DotDdgGeneratorTests extends DataFlowCodeToCpgSuite {
       inside(cpg.method.name("foo").dotDdg.l) { case List(elem) =>
         val lines = elem.split("\n")
         lines.head should startWith("digraph \"foo\"")
-        lines.count(x => x.contains("->")) shouldBe 31
+        lines.count(x => x.contains("->")) shouldBe 34
         lines.last should startWith("}")
       }
     }
@@ -51,120 +51,4 @@ class DotDdgGeneratorTests extends DataFlowCodeToCpgSuite {
     }
   }
 
-  def dumpDDg(method: Method): String = {
-    def printNode(n: AstNode): String = s"${n.label}:[${n.code}]@${n.lineNumber.getOrElse(-1)}"
-
-    method.ast
-      .collectAll[CfgNode]
-      .map { n => (n, n.ddgIn.l) }
-      .collect {
-        case (node, ddgIn) if ddgIn.nonEmpty => printNode(node) + " <- " + ddgIn.map(printNode).mkString(", ")
-      }
-      .mkString("\n")
-  }
-
-  "Compute dependencies according to Kuck et al 81 (Dependence Graphs and Compiler Optimizations)" should {
-    // cf https://dl.acm.org/doi/pdf/10.1145/567532.567555
-    // Note that this test is descriptive, not normative: It only documents current behavior and makes no judgement whether
-    // output, or anti, or even input dependencies should be included in the DDG.
-    "include flow-dependencies" in {
-      val cpg = code("""
-          |int fun(int* p)
-          |{
-          | int tmp = *p;
-          | *p = tmp + 1;
-          | return 0;
-          |}
-          |""".stripMargin)
-      dumpDDg(cpg.method.name("fun").head) shouldBe
-        """CALL:[tmp = *p]@4 <- IDENTIFIER:[tmp]@4
-          |IDENTIFIER:[tmp]@4 <- CALL:[*p]@4
-          |IDENTIFIER:[p]@4 <- METHOD_PARAMETER_IN:[int* p]@2
-          |CALL:[*p = tmp + 1]@5 <- CALL:[*p]@5, IDENTIFIER:[tmp]@4
-          |CALL:[*p]@5 <- CALL:[tmp + 1]@5
-          |IDENTIFIER:[p]@5 <- METHOD_PARAMETER_IN:[int* p]@2
-          |CALL:[tmp + 1]@5 <- IDENTIFIER:[tmp]@4
-          |IDENTIFIER:[tmp]@5 <- IDENTIFIER:[tmp]@4
-          |RETURN:[return 0;]@6 <- LITERAL:[0]@6
-          |METHOD_RETURN:[int]@2 <- RETURN:[return 0;]@6, METHOD_PARAMETER_IN:[int* p]@2, CALL:[*p]@5, IDENTIFIER:[tmp]@5, CALL:[tmp + 1]@5
-          |METHOD_PARAMETER_OUT:[int* p]@2 <- METHOD_PARAMETER_IN:[int* p]@2, CALL:[*p]@5""".stripMargin
-      // we see that there is a ddgIn edge to the store (line 5) via identifier tmp from the load (line 4)
-    }
-
-    "Not include output-dependencies" in {
-      val cpg = code("""
-          |int fun(int* p)
-          |{
-          | *p = 0;
-          | *p = 1;
-          | return 0;
-          |}
-          |""".stripMargin)
-      dumpDDg(cpg.method.name("fun").head) shouldBe
-        """CALL:[*p = 0]@4 <- CALL:[*p]@4
-        |CALL:[*p]@4 <- LITERAL:[0]@4
-        |IDENTIFIER:[p]@4 <- METHOD_PARAMETER_IN:[int* p]@2
-        |CALL:[*p = 1]@5 <- CALL:[*p]@5
-        |CALL:[*p]@5 <- LITERAL:[1]@5
-        |IDENTIFIER:[p]@5 <- METHOD_PARAMETER_IN:[int* p]@2, CALL:[*p]@4
-        |RETURN:[return 0;]@6 <- LITERAL:[0]@6
-        |METHOD_RETURN:[int]@2 <- RETURN:[return 0;]@6, METHOD_PARAMETER_IN:[int* p]@2, CALL:[*p]@5
-        |METHOD_PARAMETER_OUT:[int* p]@2 <- METHOD_PARAMETER_IN:[int* p]@2, CALL:[*p]@5""".stripMargin
-      // we see that there is no ddgIn edge to the second store (line 5) from the first (line 4)
-    }
-
-    "Not include anti-dependencies" in {
-      val cpg = code("""
-          |int fun(int* p)
-          |{
-          | int tmp = *p;
-          | *p = 1;
-          | return tmp;
-          |}
-          |""".stripMargin)
-      dumpDDg(cpg.method.name("fun").head) shouldBe
-        """CALL:[tmp = *p]@4 <- IDENTIFIER:[tmp]@4
-          |IDENTIFIER:[tmp]@4 <- CALL:[*p]@4
-          |IDENTIFIER:[p]@4 <- METHOD_PARAMETER_IN:[int* p]@2
-          |CALL:[*p = 1]@5 <- CALL:[*p]@5
-          |CALL:[*p]@5 <- LITERAL:[1]@5
-          |IDENTIFIER:[p]@5 <- METHOD_PARAMETER_IN:[int* p]@2
-          |RETURN:[return tmp;]@6 <- IDENTIFIER:[tmp]@6, IDENTIFIER:[tmp]@4
-          |METHOD_RETURN:[int]@2 <- RETURN:[return tmp;]@6, METHOD_PARAMETER_IN:[int* p]@2, IDENTIFIER:[tmp]@4, CALL:[*p]@5
-          |METHOD_PARAMETER_OUT:[int* p]@2 <- METHOD_PARAMETER_IN:[int* p]@2, CALL:[*p]@5""".stripMargin
-      // we see that there is no ddgIn path to the store (line 5) from the load (line 4)
-    }
-    "Not include input dependencies" in {
-      val cpg = code("""
-          |int fun(volatile int* p)
-          |{
-          | int tmp = *p;
-          | int tmp2 = *p;
-          | return tmp + tmp2;
-          |}
-          |""".stripMargin)
-      dumpDDg(cpg.method.name("fun").head) shouldBe
-        """CALL:[tmp = *p]@4 <- IDENTIFIER:[tmp]@4
-          |IDENTIFIER:[tmp]@4 <- CALL:[*p]@4
-          |IDENTIFIER:[p]@4 <- METHOD_PARAMETER_IN:[volatile int* p]@2
-          |CALL:[tmp2 = *p]@5 <- IDENTIFIER:[tmp2]@5
-          |IDENTIFIER:[tmp2]@5 <- CALL:[*p]@5
-          |IDENTIFIER:[p]@5 <- METHOD_PARAMETER_IN:[volatile int* p]@2
-          |RETURN:[return tmp + tmp2;]@6 <- CALL:[tmp + tmp2]@6
-          |CALL:[tmp + tmp2]@6 <- IDENTIFIER:[tmp]@4, IDENTIFIER:[tmp2]@5
-          |IDENTIFIER:[tmp]@6 <- IDENTIFIER:[tmp]@4
-          |IDENTIFIER:[tmp2]@6 <- IDENTIFIER:[tmp2]@5
-          |METHOD_RETURN:[int]@2 <- RETURN:[return tmp + tmp2;]@6, METHOD_PARAMETER_IN:[volatile int* p]@2, CALL:[*p]@5, IDENTIFIER:[tmp]@6, IDENTIFIER:[tmp2]@6, CALL:[tmp + tmp2]@6
-          |METHOD_PARAMETER_OUT:[volatile int* p]@2 <- METHOD_PARAMETER_IN:[volatile int* p]@2, CALL:[*p]@5""".stripMargin
-      // we see that there is no ddgIn path to the load (line 5) from the other load (line 4).
-      /*FIXME
-         Choose a more instructive example, volatile has too crazy semantics. But we want an example that also works if we
-         use an optimizing compiler and then use llvm2cpg or ghidra2cpg. This is conceptual and not about the C frontend.
-         Without volatile, an optimizing compiler would load from memory once and then re-use the register value.
-         With volatile, the two loads are IO operations and are ordered (i.e. one could argue that they are flow-dependent
-         via global state. Volatile reads can have side-effects! We are not modeling that in c2cpg, though).
-       */
-    }
-  }
-
 }