1

I want to write a program to do this, based on Soot's build-in Reaching-Definition analysis. Now I'm wondering is this the correct approach? I searched and found nobody seems to ever be interested in this direction.

Any suggestions?

Elderry
  • 1,902
  • 5
  • 31
  • 45
  • This doesn't make a lot of sense to me. What does it mean to estimate a variable's value? And how is reaching-definition analysis relevant? – Stephen C Apr 08 '14 at 08:02
  • @StephenC, I'm doing some security evaluation here, for instance, if I can find out that one Android app uses a paid target in its sendText() function, I can flag it. – Elderry Apr 08 '14 at 08:47
  • With reaching-definition analysis, I can find a variable's related definition sites and check each one recursively to find the may-value assigned to this variable. – Elderry Apr 08 '14 at 08:48
  • Well that is nothing to do with estimating a variable's value. – Stephen C Apr 08 '14 at 09:44
  • @StephenC: Each reaching definition shows how the source of range of values (at the start, a range of zero width around some input ["a paid target"] or constant value such a 3) can be consumed by an assignment. The set of reaching definitions reaching a points give the set of ranges, which can conservatively be combined into a single range. You might argue that a set would be better model than a range; all this does is change the effort compute the result, and gives a different conservative result. – Ira Baxter Apr 09 '14 at 00:59
  • @IraBaxter - but what has this to do with "estimating" anything? Or does "estimate" have a special technical meaning in this context? – Stephen C Apr 09 '14 at 02:29
  • @StephenC: An "estimation" by definition is a plausible value for something of interest. If one computes a conservative range of values of a variable at a point in the code, that range *is* an estimate of its actual value at that point. I don't think the term "estimate" is actually a technical term in the static analysis literature but it was clear to me what OP wanted when he wrote it. – Ira Baxter Apr 09 '14 at 02:36
  • See http://stackoverflow.com/q/10145554/120163 for a similar question and related answers, but for C#. The problem is much the same. – Ira Baxter Apr 09 '14 at 02:38

2 Answers2

0

What you probably want to do is combine a set of ranges using an iterative data flow solver. You want to combine range-values from inputs into range-values for the set of definitions that cross basic blocks.

For this you generally need a control flow graph and the transfer functions across the basic blocks. I suppose you can treat the reaching-definitions graph in a similar way.

You'll then need interprocedural range propagation to push the ranges across the code.

Ira Baxter
  • 93,541
  • 22
  • 172
  • 341
0

This is a really generic problem you are stating. Reaching Definitions does not have much to do with this. Global Value Numbering is more what you apparently want but it's too hard to tell from your description. Try the Soot mailing list with a more detailed problem statement.

Eric
  • 1,343
  • 1
  • 11
  • 19