Here is a (very high-level) breakdown of how Esh computes similarity:
- Decomposing the procedure into strands: We decompose procedures into smaller segments (we refer to as strands), which are feasible to compare, and try to use semantically similar strands from one procedure to compose the other.
- Pairwise semantic comparison: We use a program verifier to check whether two strands are semantically equivalent by assuming input equivalence and checking if intermediate and output values are the same (this is essentially the demo you played with). When they are not equivalent, we define a quantitative notion of strand similarity based on the proportion of matching values to the total number of values in the strand. To allow for this semantic comparison, we translate the assembly code segments to higher level BoogieIR.
- Statistical reasoning over strands: We compute whole-procedure similarity using local similarity between strands and applying statistical reasoning. A matching pair of strands is not enough to suggest similarity, we also require statistical evidence. A key aspect of our statistical framework is that we amplify matches of unique strands, and dampen the significance of “common” strands (with respect to the target database examined) as they are less indicative of similarity.