I had thought to implement the core algorithms of fic-finder in one week, but it seems that it is quite a challenge for me, because of my little knowledge on PDG i.e. program dependence graph.
As we know, core of the algorithm of fic-finder is an operation/technique called “Program Slicing”, it is highly dependent on PDG, going backward down which, we can easily find all dependencies aka slicing of a specific method/field.
List<Node> runBackwardSlicingFor(Node target) {
List<Node> slicing = new ArrayList<Node>();
int ptr = -1;
slicing.add(pdg.getNode(target));
ptr += 1;
do {
Node n = slicing.get(ptr);
Iterator<Node> iterator = n.getPrevious().iterator();
while(iterator.hasNext()) {
Node n = iterator.next();
if (slicing.indexOf(n) == -1) {
slicing.add(iterator.next());
}
ptr += 1;
}
} while(ptr != slicing.size());
return slicing;
}
As shown above, Program Slicing is quite easy when you get the PDG. However, the complex thing is the PDG itself.
This week, after I had knowledge of Program Slicing, I stepped to find the algorithm of PDG, and implement it by myself. But fine, it scared me. The paper stating its principle PAPER-The.Program.Dependence.Graph.And.Its.Use.In.Optimization is long and not easy to understand. By reading it and its slides as well as some other files(I attached it in this email), I figured out what is PDG and how to manually draw an easy PDG.
I marked word easy, because when it involves function invoking, things of PDG get quite complex. And I have not clearly understand how it runs. So it will continue taking a somewhat long time for me to figure it out clearly.
"But whatever, implementation sometime is less relavant to the principle. There must be many libraries already implementing PDG and we can just use it by now." I thought. Yes, soot implements a PDG, but as the maintainer said: "It lacks the implementation of DDG and I seldom use it."(Sorry that I cannot find url of this sentence). And when I used it, the program just complained "java.lang.RuntimeException: PDG construction: A and B are not supposed to be the same node!", I searched and no solutions found.
Then I turned to Github, tried to find some libraries, but to be honest, I couldnot find some suitable libraries that we could easily and directly use. The following libraries implenents PDG as part of it:
wala: a large program analysis lib, just like soot, but not compatible
indus: another program analysis lib, Jimple based, compatible with soot
Slithice: a slicer. No docs offered, not easy to use, soot based
As you can see above, the last three libs/projs are soot based, but they directly use soot to analyse general jars not android apks, and they all use a separate soot as their engine, that is to say, if we directly include them, we will have 2 soot instance, and the performance will be quite bad.
By now, I have added some files of jpdg to fic-finder, and I am reading the source codes of jpdg now. jpdg is the least large one of these three, but question is it doesn't provide any interface to access the inner data structure of it's node and node relationships. So I intend to rewrite jpdg so that we can use one soot instance and I will have more knowledge on PDG(It may take a long time).
Structure and new Ideas
I add some new todo features to fic-finder:
[ ] Make every apk containable, that is to say, every apk runs separately, and fic-finder will have the ability to handle multiple apks
[ ] A official website that can, receive apk and models rules, and return issues
[ ] The website can hold the following functions:
[ ] separately run a FIC checking using the predefined rules
[ ] separately run a FIC checking using self-defined i.e. customized rules
[ ] separately run a FIC checking using the mixed rules i.e. predefined and customized
[ ] request a list of api-models, well defined rules i.e. quite useful rules will be added to predefined rules
[ ] a graph showing the issue distributions on api-context models
Weekly report - QUESTIONS SUMMARY
Complexity
I had thought to implement the core algorithms of fic-finder in one week, but it seems that it is quite a challenge for me, because of my little knowledge on PDG i.e. program dependence graph.
As we know, core of the algorithm of fic-finder is an operation/technique called “Program Slicing”, it is highly dependent on PDG, going backward down which, we can easily find all dependencies aka slicing of a specific method/field.
As shown above, Program Slicing is quite easy when you get the PDG. However, the complex thing is the PDG itself.
This week, after I had knowledge of Program Slicing, I stepped to find the algorithm of PDG, and implement it by myself. But fine, it scared me. The paper stating its principle PAPER-The.Program.Dependence.Graph.And.Its.Use.In.Optimization is long and not easy to understand. By reading it and its slides as well as some other files(I attached it in this email), I figured out what is PDG and how to manually draw an easy PDG.
I marked word easy, because when it involves function invoking, things of PDG get quite complex. And I have not clearly understand how it runs. So it will continue taking a somewhat long time for me to figure it out clearly.
"But whatever, implementation sometime is less relavant to the principle. There must be many libraries already implementing PDG and we can just use it by now." I thought. Yes, soot implements a PDG, but as the maintainer said: "It lacks the implementation of DDG and I seldom use it."(Sorry that I cannot find url of this sentence). And when I used it, the program just complained "java.lang.RuntimeException: PDG construction: A and B are not supposed to be the same node!", I searched and no solutions found.
Then I turned to Github, tried to find some libraries, but to be honest, I couldnot find some suitable libraries that we could easily and directly use. The following libraries implenents PDG as part of it:
As you can see above, the last three libs/projs are soot based, but they directly use soot to analyse general jars not android apks, and they all use a separate soot as their engine, that is to say, if we directly include them, we will have 2 soot instance, and the performance will be quite bad.
By now, I have added some files of jpdg to fic-finder, and I am reading the source codes of jpdg now. jpdg is the least large one of these three, but question is it doesn't provide any interface to access the inner data structure of it's node and node relationships. So I intend to rewrite jpdg so that we can use one soot instance and I will have more knowledge on PDG(It may take a long time).
Structure and new Ideas
I add some new todo features to fic-finder:
The structure will be: