Having some problems when learning the algorithm of Andersen pointer analysis in SVF?

SVF-tools / SVF

Static Value-Flow Analysis Framework for Source Code

http://svf-tools.github.io/SVF/

Other

1.36k stars 431 forks source link

Having some problems when learning the algorithm of Andersen pointer analysis in SVF? #676

Open for-just-we opened 2 years ago

for-just-we commented 2 years ago

Hi, author, recently I have been trying to learning the different versions of Andersen algorithm in SVF, including Andersen class and its child classes. And I found its hard to completely understand those algorithms because they are too different from original Andersen algorithm, So far I have following questions:

Are those field-sensitive Andersen algorithms derived from your paper: "Fast and Precise Handling of Positive Weight Cycles for Field-sensitive Pointer Analysis" or Pearce et al.’s field-sensitive?
Where could I found the papers or documentations describing different variant Andersen algorithms implemented in SVF?
There are some APIs which I don't understand their functions. for example, NodeToRepMap and NodeToSubsMap in ConsG.h. Are there any detailed documentations describing those API or where I could found any detailed documentations to help me understand the rationale of SVF?

I appreciate it very much if you could reply this.

yuleisui commented 2 years ago

You can refer here to learn a bit more about API, https://github.com/SVF-tools/Teaching-Software-Analysis/blob/slides/slides/Data-Dependence.pdf

for-just-we commented 2 years ago

You can refer here to learn a bit more about API, https://github.com/SVF-tools/Teaching-Software-Analysis/blob/slides/slides/Data-Dependence.pdf

Thank you very much, I have read the slide, but now I am trying to understand every Andersen algorithm implemented in SVF. The chain of classes of Andersen algorithm is

graph LR
E(Andersen) --> F(AndersenWaveDiff)
F --> G(AndersenWaveDiffWithType)
E --> H(AndersenLCD)
E --> I(AndersenHCD)
I --> J(AndersenHLCD)
H --> J
E --> K(AndersenSCD)
K --> L(AndersenSFR)

And I am wondering what are the differences between them, is there any documentations or papers I can refer to? I just want to learn the algorithm in each class. I recently have been studying related field-sensitive algorithms but I couldn't found the corresponding relationship between them and SVF.

I appreciate it very much if you could help me

yuleisui commented 2 years ago

Unfortunately, we don't have lecture slides or documents for these implementations. Hopefully, the code is self-explanatory. You may wish to refer to the following papers if you want to understand more

AnderWaveDiff: Wave propagation and deep propagation for pointer analysis AnderSFR and AnderSCD: Fast and precise handling of positive weight cycles for field-sensitive pointer analysis. Andersen HCD/LCD: Fast and accurate pointer analysis for millions of lines of code

for-just-we commented 2 years ago

Unfortunately, we don't have lecture slides or documents for these implementations. Hopefully, the code is self-explanatory. You may wish to refer to the following papers if you want to understand more

AnderWaveDiff: Wave propagation and deep propagation for pointer analysis AnderSFR and AnderSCD: Fast and precise handling of positive weight cycles for field-sensitive pointer analysis. Andersen HCD/LCD: Fast and accurate pointer analysis for millions of lines of code

What about base class Andersen, I notice that in Andersen::handleCopyGep method, there is computeDiffPts(nodeId); and if (!getDiffPts(nodeId).empty()) before processCopy and processGep. I actually don't get what computeDiffPts and getDiffPts do here. Are these part of original Andersen Algorithm?