Creating Relations from The Programs CFG

[JuanCortezEclyp]

Hey Langston I just wanted to know your opinion on the matter as I don't know how feasible could be to integrate this into treeedb.

We've been using Souffle to do different types of Static Analysis over different programs, and in some cases we have seen that the information from the AST of the program is not enough as it's way to complicated to create relations that may indicate which instruction affects a certain instruction.
So we've been thinking that it could be useful to have certain relations from the Control Flow Graph of the program, like for example modify the node relation to also include a Basic Block ID to indicate to which Basic Block the node belongs, may be a new relation for Basic Blocks indicating the successor and the direct ancestor.

We think this could allow for stronger program analysis, but I know that this changes are not trivial and I don't know how hard it may be to generalize it.

Once again I just wanted to know your opinion about this idea.

[langston-barrett]

@JuanCortezEclyp I like the idea of including richer semantic information in the relations, but I'm not really sure how to generate it. I think you would have to actually instrument the compiler / interpreter for each language, rather than just looking at the output of a parser.

So we've been thinking that it could be useful to have certain relations from the Control Flow Graph of the program, like for example modify the node relation to also include a Basic Block ID to indicate to which Basic Block the node belongs, may be a new relation for Basic Blocks indicating the successor and the direct ancestor.

I don't think any of our supported languages have a concept of basic blocks? That is usually a compiler IR or assembly level concept.

[JuanCortezEclyp]

Yeah, I assumed that Tree-sitters output could have to be manipulated in some shape or form. Although I don't think is impossible I also don't think is easy, plus I think it would need to be done specifically for each language as I don't see an easy way of generalizing the jump instructions.

[langston-barrett]

Yeah, I assumed that Tree-sitters output could have to be manipulated in some shape or form.

Agreed. One way I could envision this working would be for each language to have a "prelude" .dl file that computes relations like control_flow(from, to) and data_flow(from, to). We might want to compute just direct (not transitive) edges, so that these relations don't become too large. Client analyses could compute the transitive closure if they cared to.

It would be very challenging to make these relations sound (that would require at a minimum a full pointer analysis for languages like C/Python/Java/etc.), but we could provide a best-effort version.

PRs very welcome 😄