[Soot-list] PathReconstructionMode vs PathBuildingAlgorithm

[Miguel Velez]

Hi Steven,

The explanation helped a lot. Thanks!

However, I am running into problems when obtaining the results of which 
sources flow into which sinks. For instance, when comparing the results 
of the map in the TaintPropagationResults class and the map in 
InfoflowResults, they do not much on the number of entries. Now, based 
on your explanation of how taint abstractions are propagated and paths 
are constructed, this should be expected since, as taints get 
propagated, new taint abstractions are created and they are also 
propagated through the program.

However, if I just look at the unique sinks at both of these maps, they 
do not match. In some cases, there are sinks missing in the results of 
InfoflowResults. I believe that is a bug. Even weirder is that if I run 
multiple times the same program with the same settings and same sources 
and sinks, I get different results (i.e., even more sinks are missing 
from the InfoflowResults map or I get all of the correct sinks). I am 
not sure if this behavior is similar to the issue described here:

https://github.com/secure-software-engineering/soot-infoflow-android/issues/31

Thanks,

Regards,

Miguel Velez
On 4/11/18 12:08 PM, Arzt, Steven wrote:
> Hi Miguel,
>
> The two concepts are indeed related. There are different algorithms that can be used for building source-to-sink paths from a taint graph. FlowDroid always first propagates the taint abstractions from the sources through the interprocedural control flow graph, which yields a taint graph. It then needs to find paths through this graph to connect a taint abstraction at a sink with a taint abstraction at a source through a chain of predecessors in the taint graph. There are multiple approaches to this problem, modeled as different algorithms. Some algorithms, for example, are context-sensitive, while others are not. Some are faster than others, etc.
>
> On the other hand, there are also choices you can make regardless of the chosen algorithm. The details are complex, but in case you do not need a completely precise paths, you can abstract away from a few things along the path. You will still get the correct source-to-sink connection, but you be ok with losing a few statements on the path for improving your performance. That's what the modes are about.
>
> Unless you run into problems, I'd suggest to leave both settings alone and see whether it's already useful what you get. If not, you most commonly want a different algorithm. Only under rare circumstances, you need a different mode. In fact, the modes were implement because of a very specific problem one of my student has encountered in his use of the tool for his thesis.
>
> Best regards,
>    Steven
>
> -----Original Message-----
> From: Soot-list <soot-list-bounces at cs.mcgill.ca> On Behalf Of Miguel Velez
> Sent: Wednesday, April 11, 2018 2:42 PM
> To: soot-list at cs.mcgill.ca
> Subject: [Soot-list] PathReconstructionMode vs PathBuildingAlgorithm
>
> Hello,
>
> I am unable to understand what is the difference between PathReconstructionMode and PathBuildingAlgorithm. There has to be some difference between them, but "reconstructing" or "building" a path seem similar to me. Are they somehow related to one another? Do they interact in the results that we obtain from the analysis? Do the individual settings affect the results (i.e., would the settings change what sources flow into what sinks)?
>
> Thanks,
>
> --
> Regards,
>
> Miguel Velez
> _______________________________________________
> Soot-list mailing list
> Soot-list at CS.McGill.CA
> https://mailman.CS.McGill.CA/mailman/listinfo/soot-list