4 ms·
What's the state of the art of progarm-diffing (i.e based on LLVM IR)?
by senatorobama 9y ago
What's the state of the art of progarm-diffing (i.e based on LLVM IR)?
- yorwba 9y agoWhat kind of differences are you looking for? And equally important, what kind of differences do you want to ignore? Is if(condition) { a(); } else { b(); } meaningfully different from if(!condition) { b(); } else { a(); } or not? Depending on your needs, you could just diff a textual representation using a string diff algorithm, or diff the control flow graph using a graph diff algorithm (but that might require solving graph isomorphism problems, which are hard (potentially NP-hard)).
- senatorobama 9y agoCan't I check whether every instruction in every BasicBlock of the CFG is equal?
- yorwba 9y agoSure, but how do you determine which basic blocks correspond to each other, when there have been changes to parts of the graph?
- senatorobama 9y agoDamn. Is this an unsolved problem in CS?
- raphlinus 9y agoGraph isomorphism is a known NP-hard problem, but the vast majority of subgraphs in programs are reducible, so I expect that aligning two control flow graphs admits a good heuristic solution.
- yorwba 9y agoActually, the complexity of Graph Isomorphism in general is still unknown, and any definite classification would have interesting consequences. https://en.wikipedia.org/wiki/Graph_isomorphism_problem https://en.wikipedia.org/wiki/Graph_isomorphism_problem I agree though that control flow graphs are probably easier to align than completely random graphs, although there might be pathological cases e.g. if you have lots of identical subgraphs like if err != nil { return nil, err }.