pascal-lab / tai-e-assignments Goto Github PK

View Code? Open in Web Editor NEW

1.0K 4.0 230.0 29.05 MB

Tai-e assignments for static program analysis

Home Page: https://tai-e.pascal-lab.net/

License: GNU Lesser General Public License v3.0

Kotlin 0.64% Java 99.36%

education java static-analysis program-analysis

tai-e-assignments's Introduction

Tai-e Assignments for Static Program Analysis

Getting Started

If you want to do the assignments, please start with "Overview of Tai-e Assignments" [中文][English].

tai-e-assignments's People

Contributors

Stargazers

Watchers

Forkers

xrbin0 su18 penguinfirst linuer vgalaxies wliuxingxiangyu sunfloweraries one-pr zhangt2333 suxnju xiaoxianghuayu lsmatpackrat nickgrand yuuuuu422 cyztql jaic1 tangben1997 crwen flankerhqd canliture 0xerath0 bluesbreaker45 kingking888 breathleas happyxzw shengjiezhao nothingtonothing kevindadi pan2013e meizjm3i meisli xzf1234 he1pa luorongluorong j0hn50n133 wfbreezee bingkuair y360u dizhizhou airahc funny1dog xzy0311 bakasea qifanwang bjrjk lirui-shanghaitech zzctmac scorpionre smallchester insorker 71aoo xiaozhouqi gitwk86 kaximiss buriedpot shmily8421 fxti matthewxy01 gm-lwhh ch1y0q jiyidi-1 shutupandhax last-las roderland miragelyu codexma sunshine-lcc aur0ra-m wangdh15 0v3rw4tch yqyq-w mm0n5ter hcplantern ling-yuchen floatshadow dianqk abc767234318 xieyu567 qixubin garymao b1cat i-pear jiadwu2 fsbinhe clingfei pgzxb 1475505 yangyunteng northsecond tomapu lukejyk river-li chobynleo papayawd gwokhiujin tzupingkao w2n1ck lydsera paul-georgeee gotaroo

tai-e-assignments's Issues

Omissions from OnlineJudge's test cases (A6)

What happened:
I actually found this out by accident, my Solver.java's visitor pattern had a misplaced context in one place, but A6's OJ didn't check for it until I got hit hard with it in A7.

The ❌ part is code that is fooling OJ (A6), but will be exposed by local test cases in A7 .

If there is an official will to improve the online testing,
My A6's Submission ID for the test is 81fc0b28a293035
I didn't touch the wrong code, you can easily reproduce the problem by downloading the Accepted commit from this A6 ID, taking Solver.java and putting it into A7, and perhaps the A7 error message will help you refine the A6 online test case.

Testing Question

I am doing A1.
I don't know why it takes very long to run the test.
It's been 14 minutes, but still running.
Could anyone give me some suggestions.

About the A7

Hi, everyone, I just meet a strange problem: to maintain corresponding StoreField(a.f = x), LoadField(x = a.f), StoreArray(a[*] = x), LoadArray(x = a[*]) statements for variable a, if I use the builtin HashMap just like below

private Map<Var, Set<Stmt>> fieldStore;
private Map<Var, Set<Stmt>> fieldLoad;
private Map<Var, Set<Stmt>> arrayLoad;
private Map<Var, Set<Stmt>> arrayStore;
...

protected void initialize() {
    String ptaId = getOptions().getString("pta");
    PointerAnalysisResult pta = World.get().getResult(ptaId);
    // You can do initialization work here

    fieldLoad = new HashMap<>();
    fieldStore = new HashMap<>();
    arrayLoad = new HashMap<>();
    arrayStore = new HashMap<>();
    for (Var var : pta.getVars()) {
        fieldStore.put(var, new HashSet<>());
        fieldLoad.put(var, new HashSet<>());
        arrayStore.put(var, new HashSet<>());
        arrayLoad.put(var, new HashSet<>());
        for (Var other : pta.getVars()) {
            for (Obj obj : pta.getPointsToSet(var)) {
                if (pta.getPointsToSet(other).contains(obj)) {
                    fieldStore.get(var).addAll(other.getStoreFields());
                    fieldLoad.get(var).addAll(other.getLoadFields());
                    arrayLoad.get(var).addAll(other.getLoadArrays());
                    arrayStore.get(var).addAll(other.getStoreArrays());
                    break;
                }
            }
        }
    }
}

there are always some testcases that I cannot pass through in online judge, however if I switch to Guava HashMultiMap(com.google.common.collect.HashMultimap) and initialize the map like below(others is still)

private final Multimap<Var, Stmt> fieldStore = HashMultimap.create();
private final Multimap<Var, Stmt> fieldLoad = HashMultimap.create();
private final Multimap<Var, Stmt> arrayLoad = HashMultimap.create();
private final Multimap<Var, Stmt> arrayStore = HashMultimap.create();
...

protected void initialize() {
    String ptaId = getOptions().getString("pta");
    PointerAnalysisResult pta = World.get().getResult(ptaId);
    // You can do initialization work here

    for (Var var : pta.getVars()) {
        for (Var other : pta.getVars()) {
            for (Obj obj : pta.getPointsToSet(var)) {
                if (pta.getPointsToSet(other).contains(obj)) {
                    fieldStore.putAll(var, other.getStoreFields());
                    fieldLoad.putAll(var, other.getLoadFields());
                    arrayLoad.putAll(var, other.getLoadArrays());
                    arrayStore.putAll(var, other.getStoreArrays());
                    break;
                }
            }
        }
    }
}

everything is ok. And after the initialization, I only use these maps as lookup tables just look like fieldLoad.get(var).stream().map(fieldStore -> (LoadField) fieldStore) .filter(fieldLoad -> fieldLoad.getFieldRef().resolve() == ((StoreField) stmt).getFieldRef().resolve()).collect(Collectors.toSet())

So if there are some bugs in jvm or someone can point out that I miss some important issues?

No warning/tip for uploading without login in OJ

When I forgot logging in my account and uploaded my assignment on OJ, the "uploading" tip hovered there permanently and no tips reminded me of logging in. Maybe it could be fixed?

A4的test case出现NoSuchMethodError

问题

没有对不相关代码做任何修改，拷贝的是本仓库的最新代码
跑A4的InterCPTest.java的testExample方法出现下面的错误

java.lang.NoSuchMethodError
	at jdk.internal.reflect.NativeConstructorAccessorImpl.newInstance0(Native Method)
	at jdk.internal.reflect.NativeConstructorAccessorImpl.newInstance(NativeConstructorAccessorImpl.java:77)
	at jdk.internal.reflect.DelegatingConstructorAccessorImpl.newInstance(DelegatingConstructorAccessorImpl.java:45)
	at java.lang.reflect.Constructor.newInstanceWithCaller(Constructor.java:499)
	at java.lang.reflect.Constructor.newInstance(Constructor.java:480)
	at java.util.concurrent.ForkJoinTask.getThrowableException(ForkJoinTask.java:564)
	at java.util.concurrent.ForkJoinTask.reportException(ForkJoinTask.java:591)
	at java.util.concurrent.ForkJoinTask.invoke(ForkJoinTask.java:689)
	at java.util.stream.ForEachOps$ForEachOp.evaluateParallel(ForEachOps.java:159)
	at java.util.stream.ForEachOps$ForEachOp$OfRef.evaluateParallel(ForEachOps.java:173)
	at java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:233)
	at java.util.stream.ReferencePipeline.forEach(ReferencePipeline.java:596)
	at java.util.stream.ReferencePipeline$Head.forEach(ReferencePipeline.java:765)
	at pascal.taie.analysis.AnalysisManager.runMethodAnalysis(AnalysisManager.java:134)
	at pascal.taie.analysis.AnalysisManager.runAnalysis(AnalysisManager.java:75)
	at pascal.taie.analysis.AnalysisManager.lambda$execute$0(AnalysisManager.java:60)
	at pascal.taie.util.Timer.lambda$runAndCount$0(Timer.java:112)
	at pascal.taie.util.Timer.runAndCount(Timer.java:93)
	at pascal.taie.util.Timer.runAndCount(Timer.java:111)
	at pascal.taie.util.Timer.runAndCount(Timer.java:107)
	at pascal.taie.analysis.AnalysisManager.lambda$execute$1(AnalysisManager.java:59)
	at java.util.ArrayList.forEach(ArrayList.java:1511)
	at pascal.taie.analysis.AnalysisManager.execute(AnalysisManager.java:59)
	at pascal.taie.Main.executePlan(Main.java:142)
	at pascal.taie.Main.lambda$main$0(Main.java:56)
	at pascal.taie.util.Timer.lambda$runAndCount$0(Timer.java:112)
	at pascal.taie.util.Timer.runAndCount(Timer.java:93)
	at pascal.taie.util.Timer.runAndCount(Timer.java:111)
	at pascal.taie.util.Timer.runAndCount(Timer.java:107)
	at pascal.taie.Main.main(Main.java:48)
	at pascal.taie.analysis.Tests.test(Tests.java:89)
	at pascal.taie.analysis.dataflow.analysis.constprop.InterCPTest.test(InterCPTest.java:34)
	at pascal.taie.analysis.dataflow.analysis.constprop.InterCPTest.testReference(InterCPTest.java:48)
	at jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:77)
	at jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:568)
	at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:59)
	at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
	at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:56)
	at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
	at org.junit.runners.ParentRunner$3.evaluate(ParentRunner.java:306)
	at org.junit.runners.BlockJUnit4ClassRunner$1.evaluate(BlockJUnit4ClassRunner.java:100)
	at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:366)
	at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:103)
	at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:63)
	at org.junit.runners.ParentRunner$4.run(ParentRunner.java:331)
	at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:79)
	at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:329)
	at org.junit.runners.ParentRunner.access$100(ParentRunner.java:66)
	at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:293)
	at org.junit.runners.ParentRunner$3.evaluate(ParentRunner.java:306)
	at org.junit.runners.ParentRunner.run(ParentRunner.java:413)
	at org.gradle.api.internal.tasks.testing.junit.JUnitTestClassExecutor.runTestClass(JUnitTestClassExecutor.java:110)
	at org.gradle.api.internal.tasks.testing.junit.JUnitTestClassExecutor.execute(JUnitTestClassExecutor.java:58)
	at org.gradle.api.internal.tasks.testing.junit.JUnitTestClassExecutor.execute(JUnitTestClassExecutor.java:38)
	at org.gradle.api.internal.tasks.testing.junit.AbstractJUnitTestClassProcessor.processTestClass(AbstractJUnitTestClassProcessor.java:62)
	at org.gradle.api.internal.tasks.testing.SuiteTestClassProcessor.processTestClass(SuiteTestClassProcessor.java:51)
	at jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:77)
	at jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:568)
	at org.gradle.internal.dispatch.ReflectionDispatch.dispatch(ReflectionDispatch.java:36)
	at org.gradle.internal.dispatch.ReflectionDispatch.dispatch(ReflectionDispatch.java:24)
	at org.gradle.internal.dispatch.ContextClassLoaderDispatch.dispatch(ContextClassLoaderDispatch.java:33)
	at org.gradle.internal.dispatch.ProxyDispatchAdapter$DispatchingInvocationHandler.invoke(ProxyDispatchAdapter.java:94)
	at jdk.proxy1.$Proxy2.processTestClass(Unknown Source)
	at org.gradle.api.internal.tasks.testing.worker.TestWorker$2.run(TestWorker.java:176)
	at org.gradle.api.internal.tasks.testing.worker.TestWorker.executeAndMaintainThreadName(TestWorker.java:129)
	at org.gradle.api.internal.tasks.testing.worker.TestWorker.execute(TestWorker.java:100)
	at org.gradle.api.internal.tasks.testing.worker.TestWorker.execute(TestWorker.java:60)
	at org.gradle.process.internal.worker.child.ActionExecutionWorker.execute(ActionExecutionWorker.java:56)
	at org.gradle.process.internal.worker.child.SystemApplicationClassLoaderWorker.call(SystemApplicationClassLoaderWorker.java:133)
	at org.gradle.process.internal.worker.child.SystemApplicationClassLoaderWorker.call(SystemApplicationClassLoaderWorker.java:71)
	at worker.org.gradle.process.internal.worker.GradleWorkerMain.run(GradleWorkerMain.java:69)
	at worker.org.gradle.process.internal.worker.GradleWorkerMain.main(GradleWorkerMain.java:74)
Caused by: java.lang.NoSuchMethodError: 'java.util.Collection pascal.taie.language.classes.ClassHierarchy.getAllSubclassesOf(pascal.taie.language.classes.JClass, boolean)'
	at pascal.taie.analysis.exception.IntraExplicitThrowAnalysis.mayThrowExplicitly(IntraExplicitThrowAnalysis.java:107)
	at pascal.taie.analysis.exception.IntraExplicitThrowAnalysis.lambda$analyze$0(IntraExplicitThrowAnalysis.java:53)
	at java.lang.Iterable.forEach(Iterable.java:75)
	at pascal.taie.analysis.exception.IntraExplicitThrowAnalysis.analyze(IntraExplicitThrowAnalysis.java:50)
	at pascal.taie.analysis.exception.ThrowAnalysis.analyze(ThrowAnalysis.java:58)
	at pascal.taie.analysis.exception.ThrowAnalysis.analyze(ThrowAnalysis.java:29)
	at pascal.taie.analysis.AnalysisManager.lambda$runMethodAnalysis$3(AnalysisManager.java:136)
	at java.util.stream.ForEachOps$ForEachOp$OfRef.accept(ForEachOps.java:183)
	at java.util.AbstractList$RandomAccessSpliterator.forEachRemaining(AbstractList.java:720)
	at java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:509)
	at java.util.stream.ForEachOps$ForEachTask.compute(ForEachOps.java:290)
	at java.util.concurrent.CountedCompleter.exec(CountedCompleter.java:754)
	at java.util.concurrent.ForkJoinTask.doExec(ForkJoinTask.java:373)
	at java.util.concurrent.ForkJoinPool$WorkQueue.topLevelExec(ForkJoinPool.java:1182)
	at java.util.concurrent.ForkJoinPool.scan(ForkJoinPool.java:1655)
	at java.util.concurrent.ForkJoinPool.runWorker(ForkJoinPool.java:1622)
	at java.util.concurrent.ForkJoinWorkerThread.run(ForkJoinWorkerThread.java:165)

About A3

I have got 40/42 in A3, but all methods in test seem to be correct. Is there something wrong?

Analyze 42 methods, pass 40 methods
There are 516 dead Stmts in all test cases
Your submission correctly detects 516 dead Stmts
#false negatives: 0
#false positives: 2

About A8 StringAppend

I think the mode cs: ci can not pass test, it will show 9 taintflows in output.Anyone have a good idea about optimization?

A1 里面的DataflowResult<Node, Fact>类

我怎样知道Node和Fact的暴露出来的具体接口，因为要实现
Solver.initializeBackward(CFG,DataflowResult)
IterativeSolver.doSolveBackward(CFG,DataflowResult)
万分感谢

请问Tai-e如何分析单个.java文件？

A4: icfg has no nodes

In interSolver::initialize() method, I iterate icfg to init in/out fact, but I find icfg has no nodes.
I have been stuck on this for two days and still have no idea how to solve it.

About A4 test cases

Hi! Can anyone provide more tips about test cases of A2.

Your submission correctly analyzes 84 out of 85 call sites in test cases for CHA,
and 1065 out of 1065 Stmts in test cases for interprocedural constant propagation.

It seems that I do something wrong on CHA, however, I have no idea where I make mistakes. Any suggestion is welcome. Thanks in advance. :)

Question about assignment 4

My submission failed on 2 statements of interprocedural constant propagation. Could anyone provide some tips on it?

Your submission correctly analyzes 85 out of 85 call sites in test cases for CHA,
and 1063 out of 1065 Stmts in test cases for interprocedural constant propagation.


[!] Failed on [hidden] testcase(s)
Tips: we will not give you any information about [hidden] testcase(s)

Testcase about A2

Can you provide more tips about the testcase of A2, the acceptance of A2 is only 2%. 51 of the 52 methods were passed for my program, for the last method I have no idea about the reason.

Help wanted: IDEA could not get openjdk 17

Hi, sir!
I followed the instructions in Set Up Tai-e Assignments. But when I built the Tai-e project, I failed. The information IDEA output is as follows:

Failed to calculate the value of task ':compileJava' property 'javaCompiler'.
Unable to download toolchain matching these requirements: {languageVersion=17, vendor=any, implementation=vendor-specific}
Could not GET 'https://api.adoptopenjdk.net/v3/binary/latest/17/ga/windows/x64/jdk/hotspot/normal/adoptopenjdk'.
Read timed out
Read timed out

So I download https://api.adoptopenjdk.net/v3/binary/latest/17/ga/windows/x64/jdk/hotspot/normal/adoptopenjdk. It is a zip file named OpenJDK17U-jdk_x64_windows_hotspot_17.0.2_8.zip. But when I check File->Project structure->SDK, there was a jdk corretto-17. I don't know why IDEA still wanna download another openjdk.

And I still don't know how to deal the build fail problem. So, could anybody help me? Thank you : )

Question about A2 (ConstProp) - Shadowed by another constant or NAC ?

In the test case Assign, analyzing the following code in function Assign.assign():

    void assign() {
        int x = 1, y;
        x = 2;
        x = 3;
        x = 4;
        y = x;
    }

We can get respectively {x=1}, {x=2}, {x=3} and {x=4} , meaning that we still consider x as constant value instead of NAC while its value has been changed.

However, in the test case 'Loop', the following function leads to a failure on OJ:

    void whileNAC() {
        int a, b = 0, c = 0;
        int i = 0;
        while (i < 10) {
            a = b;
            b = c;
            c = 1;
            ++i;
        }
    }

the variable c is expected as NAC while my analyzer regards it as constant 1 in the while loop.

When should a variable become another constant, and when should it become NAC? It confused me a lot, need I do some dead code detection to it? But I think it's not the task of this assignment.

a doubt about hashCode of Value

current implementation of Value's hashCode is:
public int hashCode() { return value; }
but this will result in
Value.makeConstant(0).hashCode() equals Value.getNAC().hashCode() and Value.getUndef().hashCode()

and thus a hashCode of CPFact's instance may not changed when a Value changed.

an optional implementation
public int hashCode() { return toString().hashCode(); }

About A8

what append about the ERROR "file 'Solver.java' uses text 'Process' (it is disallowed)" in oj system?

Question about A3(DeadCodeDetection)

When doing graph traversal, I first chose a LinkedList to maintain all visited nodes.
But I can't figure out why there would be a false negative test case.

        List<Stmt> isVisited = new LinkedList<>();
        ArrayDeque<Stmt> queue = new ArrayDeque<>();    // BFS queue
        queue.add(cfg.getEntry());

Then, if I change to use a HashSet, all test cases will pass.

improvement of assignment2

I think when some value*0, the result should be 0, same for 0/some value and 0 % some value, but OJ judged me wrong in testcase Switch.java

class Switch{
    int switch1(int x, int y){
        int a = 0;
        switch(x){
            case 1:
                a-=y;
                break;
            case 2:
                a+=y;
                break;
            case 3:
                a*=y;
                break;
            case 4:
                a/=y;
                break;
            default:
                a = a-1;
        }
        a = a+x;
        return a;
    }

in case3/4 a must be zero, but the answer is NAC

------ Failure on <Switch: int switch1(int,int)> ------
Expected: [9@L12] a = a * y; {a=NAC, x=NAC, y=NAC}
Expected: [10@L13] goto 21; {a=NAC, x=NAC, y=NAC}

output文件夹中没有生成相应的.dot文件

output文件夹中没有生成相应的.dot文件只有options.yml tai-e-plan.yml两个文件

Question about A3

There are 516 dead Stmts in all test cases
Your submission correctly detects 516 dead Stmts
#false negatives: 0
#false positives: 2

can anyone give some tips?i trap in this situation and have no idea indeed.

About the A1

How could I get the value from statement? The Lvalueclass and the Rvalueclass is not a Varclass