SPARK missing support for collection element type

[flankerhqd]

Hi:

It seems the current SPARK implementation does not support detection for collection element types. For example, for the following unit test code :

public class ContainerMultiTypeSample {
    public void target() {
        //this.helpers.get("").handle();
        for(Helper helper: helpers)
            helper.handle();
        //helper.handle();
    }

    Set<Helper> helpers;
    public ContainerMultiTypeSample () {
        this.helpers = new HashSet<>();
        this.helpers.add(new AHelper());
    }
}

interface Helper {
    public void handle();
}

class AHelper implements Helper {

    @Override
    public void handle() {
        System.out.println("wtf");
    }
}

class BHelper implements Helper {

    @Override
    public void handle() {
    }
}

Using target as entrypoint, the Call Graph is missing edge to any implementation of handle.

The test case driver is as follows:

package soot.jimple.toolkit.callgraph;

/*-
 * #%L
 * Soot - a J*va Optimization Framework
 * %%
 * Copyright (C) 2021 Qidan He
 * %%
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation, either version 2.1 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Lesser Public License for more details.
 *
 * You should have received a copy of the GNU General Lesser Public
 * License along with this program.  If not, see
 * <http://www.gnu.org/licenses/lgpl-2.1.html>.
 * #L%
 */

import org.junit.Assert;
import org.junit.Test;
import org.powermock.core.classloader.annotations.PowerMockIgnore;
import soot.Scene;
import soot.jimple.toolkits.callgraph.Edge;
import soot.testing.framework.AbstractTestingFramework;

@PowerMockIgnore({ "com.sun.org.apache.xerces.*", "javax.xml.*", "org.xml.*", "org.w3c.*" })
public class MultiCallGraphVirtualEdgesTest extends AbstractTestingFramework {

    private static final String TARGET_CLASS = "soot.jimple.toolkit.callgraph.ContainerMultiTypeSample";
    private static final String TARGET_METHOD = "void target()";

    @Test
    public void TestAsyncTaskBasicCG() {
        prepareTarget(methodSigFromComponents(TARGET_CLASS, TARGET_METHOD), TARGET_CLASS);

        boolean found = false;
        for (Edge edge : Scene.v().getCallGraph()) {
            String sig = edge.getTgt().method().toString();
            if (sig.contains("handle"))
                found = true;
        }

        Assert.assertTrue(found); //assert failed
    }
}

It seems currently there is no handling for collection item type in SPARK. (If I'm missing something please correct me) Any idea on best ways to implement this?

Thanks!

[linghuiluo]

The problem is you have target as entry point. The allocation site new AHelper() is in the constructor, but it is not reachable from your entry point. So with spark, this allocation site wont be found, thus no edge. So you have to set some method as entry point that calls the constructor at first, then somewhere later the target.

[flankerhqd]

The problem is you have target as entry point. The allocation site new AHelper() is in the constructor, but it is not reachable from your entry point. So with spark, this allocation site wont be found, thus no edge. So you have to set some method as entry point that calls the constructor at first, then somewhere later the target.

Nope, linghui, the test case driver creates the allocation site for constructor in makeDummyClass, (https://github.com/soot-oss/soot/blob/19630a60fa9070be071e54e50d366279deb9a179/src/systemTest/java/soot/testing/framework/AbstractTestingFramework.java#L206)

The class instance containing the targetMethod is created and constructor called in dummy method.

    Local argsParameter = jimp.newLocal("args", argsParamterType);
    locals.add(argsParameter);
    units.add(jimp.newIdentityStmt(argsParameter, jimp.newParameterRef(argsParamterType, 0)));
    RefType testCaseType = RefType.v(sootTestMethod.getDeclaringClass());
    Local allocatedTestObj = jimp.newLocal("dummyObj", testCaseType);
    locals.add(allocatedTestObj);
    units.add(jimp.newAssignStmt(allocatedTestObj, jimp.newNewExpr(testCaseType)));

    SootMethod method;
    try {
      method = testCaseType.getSootClass().getMethod("void <init>()");
    } catch (RuntimeException ex) {
      method = testCaseType.getSootClass().getMethodByName("<init>");
    }

    List<Value> constructorArgs = Collections.nCopies(method.getParameterCount(), NullConstant.v());
    units.add(jimp.newInvokeStmt(jimp.newSpecialInvokeExpr(allocatedTestObj, method.makeRef(), constructorArgs)));

[linghuiluo]

I did not notice that you were using that test class.

this.helpers.add(new AHelper()); is not considered by spark, since spark only considers four kinds of statements when building up the Pointer Assignment Graph (see screenshot below). I don't know how this can be modeled in PAG, as helpers hold pointers to a set of allocation sites. But you can write an analysis to detect such cases and add those edges to the call graph later. CHA and RTA would also include such edges in the call graph, but they are not so precise.

[flankerhqd]

Thanks for the reply. I'll see if SPARK can be improved to handle this.

[linghuiluo]

@flankerhqd Hi, I talked with my advisor about this issue. He said Spark should handle such cases if the library methods collection.add() is analyzed, because the assignments are usually in the method. But often people exclude these libraries methods, maybe you can check the excluded list of packages?

[flankerhqd]

Hi linghui @linghuiluo :

Thanks for the reply.

It seems even if the java.util.* is removed from exclude list, the result still does not contain relevant edges. See this pull request with added test case: https://github.com/soot-oss/soot/pull/1772.

[linghuiluo]

@flankerhqd thanks for the test. I will take a look into it.

[flankerhqd]

Please use https://github.com/soot-oss/soot/pull/1772 instead, thanks!