[Soot-list] Reaching definition analysis for a subset of the program

[Diego Bravo Velasquez]

Hey guys,


I am providing some context to my question so bear with me. I want to use the IFDS solver to find the reaching definitions of the parameters at a specific function call. I want to only calculate the definitions only at this point and not every point on the program.


My goal is to create a tool to find hard-coded encryption in Android applications. I am looking for functions that create Key objects and finding the definition of the parameter used as byte data to create the key. For example, the SecretKeySpec constructor takes in a byte[] to create the key. Interprocedural analysis may be required as the definition of the variable is not always a local variable. I am looking to see what definitions reach the constructor of the key and do not care about the definitions at every point on the program.


I tried running the "soot.jimple.toolkits.ide.exampleproblems.IFDSReachingDefinitions" example on the APK I want to analyze but I do not have enough memory to complete the analysis. Flowdroid does not even finish on this APK (Computer specs: i7-6700, 32GB RAM). For this reason I want to limit the analysis to a subset of the program.


The current solution that I am working on is finding instances of key constructors and using SimpleLocaDefs to find the definitions intraprocedurally. If the Local is a parameter then check the Edges that point to the current method, and check the value parameters at the callsites. At this I would recursively repeat this process for any Local found and print the results. The results would be any Constants found, or Expr that represent the definition of the variable and can no further be resolved. I believe this is a naive solution and this process could be implemented using the IFDSSolver.


I've looked endlessly at the Flowdroid source code to get an idea of how to formulate my problem as an IFDS problem. I have found out that I can use the BackwardsInterproceruralCFG as I will be traversing backwards looking for the definitions. I am still trying to decide what data-flow facts I should use. I thought I could keep a list of variables that I have defined and a list of variables I have yet to define. The facts would flow backwards though and I would like to query the result at the "starting" function call (ie SecretKeySpec constructor). Additionally, I don't know the stopping condition for the IFDSSolver. Would the solver stop when the variable definitions cannot be resolved further? Is this stopping condition dependent on how the FlowFunctions are implemented? What would be a good method of aggregating the results at the "starting" function call?


I would appreciate any feedback/suggestion. I will continue implementing my naive solution for now and will continue to contemplate the IFDS method.


Cheers,

Diego


-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://mailman.CS.McGill.CA/pipermail/soot-list/attachments/20160715/c8c418dd/attachment.html