Using Taint Analysis Configuration for Static Slicing

[asoifer]

Dear everybody,
I've been working on program slicing for some years, and I think that is possible to perform a static slice using CodeQL.
My first attempt is to extend the classical taint analysis configuration, adding the predicate "isAdditionalTaintStep" for addressing the control dependencies.
Unfortunately, it doesn't work, and I don't understand exactly what is doing the tainter with this predicate.
I have a CodeQL example and a basic program, with a counterexample of which lines are not included in any path.

CodeQL Query:

/**
 * @name Static slicing
 * @description An attempt to perform a static slice
 * @id cs/static-slicing
 * @problem.severity error
 * @precision very-high
 * @tags security
 * @kind path-problem
 */

import csharp
import semmle.code.csharp.security.dataflow.flowsources.Remote
import semmle.code.csharp.commons.Util
import semmle.code.csharp.dataflow.DataFlow::DataFlow::PathGraph
import semmle.code.csharp.controlflow.Guards
import semmle.code.csharp.controlflow.BasicBlocks
import semmle.code.csharp.ExprOrStmtParent

class TaintTrackingConfiguration extends TaintTracking::Configuration {
  TaintTrackingConfiguration() { this = "CustomSlice" }

  override predicate isSource(DataFlow::Node source) {
    any()
  }

  override predicate isSink(DataFlow::Node sink) {
     sink.asExpr().getLocation().getFile().getAbsolutePath().indexOf("Program.cs") > 0
	 and sink.asExpr().getLocation().getStartLine() = 12 // Target of the slicer (catching the variable result)
  }

  // An attempt to add the control dependencies
  override predicate isAdditionalTaintStep(DataFlow::Node pred, DataFlow::Node succ) {
    exists (Guard g, BasicBlock b, AbstractValue v | 
        g.getAControlFlowNode() = pred.getControlFlowNode() and
        b.getANode() = succ.getControlFlowNode() and
        g.controlsBasicBlock(b, v)
      )
  }
}

from TaintTrackingConfiguration c, DataFlow::PathNode source, DataFlow::PathNode sink
where c.hasFlowPath(source, sink)
select sink.getNode(), source, sink, "Msg", source.getNode(), "Msg"

So I run this query to the next source code:

using System;

namespace example2
{
	public class Program
	{
		public static void Main(string[] args)
		{
			int levels = 5;
			TreeNode root = new TreeNode(levels);
			int result = root.addTree(); // *
			var slicingVariable1 = result; // *
			System.Console.WriteLine("Done!");
		}
	}

	internal class TreeNode
	{
		private int value = 0;
		private TreeNode left = null;
		private TreeNode right = null;

		internal TreeNode(int levels)
		{
			value = 1;
			if (levels <= 1)
			{
				if (levels <= 0)
					throw new System.Exception("Number of levels must be positive no.");
				left = null;
				right = null;
			}
			else
			{
				left = new TreeNode(levels - 1);
				right = new TreeNode(levels - 1);
			}
		}

		internal virtual int addTree()
		{
			int total = value; // *
			if (left != null) // *
				total += left.addTree(); // *
			if (right != null) // *
				total += right.addTree(); // *
			return total; // *
		}
	}
}

After running the query I collect every line in every path, and I get these lines: {11, 12, 42, 43, 44, 45, 46, 47} (marked with // *).
In this case, I expected more lines.

For example,
If I run the same query, recursively (with an external program) adding previous lines as new targets
(performing one query for line 12, but also for line 42, 43, 44, 45, .. etc.) I get these lines:
{9, 10, 11, 12, 19, 20, 21, 23, 25, 26, 28, 30, 31, 35, 36, 40, 42, 43, 44, 45, 46, 47}.
This is what I really want, a kind of closure of data dependencies over control dependencies.
I thought that I can reach that using isAdditionalTaintStep but I see that is not the same,

Any suggestions?
I want to avoid performing several queries for getting the final "static slice".
Thanks everybody in advance,
Regards.

[RasmusWL]

Hi @asoifer,

I'm sorry to say that our data-flow analysis has a specific limitation that disallows defining sources/sinks of a data-flow configuration based on paths found with that configuration. For the security queries we are writing, that has not been a big problem so far. In some cases, we've had to have two layers of data-flow, which we have managed by just introducing a separate copy of the whole data-flow analysis, and then each part can sit in it's own "layer". In this way we can define sources/sinks in one layer based on the results form the other layer.

For C# this would be DataFlow, DataFlow2, DataFlow3, DataFlow4, DataFlow5. And as an example of actually combining such two layers, I will highlight path injection query in Python.

But I think this would at best be a band-aid for the specific problem you are trying to solve, where I would assume you want to reach a fixed point, and not just do a few iterations at most.

Also sorry for the very late reply. This question somehow slipped off the radar 😐

[asoifer]

Thanks for your answer, I understood why my attempt didn't work.
For the moment I won't try again to develop a static slicer using CodeQL but I think that is possible changing the current behavior that you talked about. I'll keep in mind,
Have a nice week, :)