PAG: "black hole" and "variant GEP" edges?

[dtzWill]

Hi,

What are "black hole" and "variant GEP" edges (black hole especially) and what roles do they play in the precision/performance of the various analyses?

[yuleisui]

"black hole" is used to conservatively handle tricky instructions such as "IntToPtr". A pointer points to unknown location if its points-to set contains a black hole node. For example, in "p = IntToPtr (i)", we make the analysis sound by letting "p" points to the "black hole" node.

To avoid propagating the "black hole" across the program, sometime we can make analysis more aggressive (unsound) by turning off this conservative handling using option "-blk=false".

"variant GEP" denotes a gep instruction that at least one of its operands may be a variable e.g., p = gep i
"normal GEP" denotes a gep instruction whose operands are all constants e.g., p = gep 5

[dtzWill]

Thanks for the explanation!

Looks like -blk is false by default currently, perhaps it would be better to enable it by default so the analysis is sound unless the client specifies otherwise?

Regarding "variant GEP"s, when enabling/disabling "handling" of these, is it correct to say that not handling them is sound (copy edges are used) but handling them is potentially more precise (but may not be able to reason about some index operations soundly)?

[yuleisui]

Yes, you can turn on "-blk" to get sound results.

The variant GEP edge is treated as copy when "-vgep" is false.

When the option is turned on, VariantGepPE is generated as a special field sensitive edge on PAG and ConstraintGraph with the hope that we can achieve more precise field-sensitive results. However, current implementation is still sound and conservative see Andersen.cpp.

The precision of field-sensitive analysis can be improved if we can handle variant GEP by introducing value range analysis or some loop trip information.