Algorithm to detect if a file(or string) have been patched

Question

This question is related to string algorithm, not version control tools or management tools.

I learnt the diff algorithm and tried to implement one. That is, given string A and string B, the diff calculate a sequence of actions that can convert A into B.

I wonder, if it possible, given a string S, and a sequence of actions that diff algorithm can produce, the algorithm will tell if the string S is (a) the origin string A, (b) the patched string B, (c) unrelated string. And what if S is only one of A and B.

Actuallly, what I'm really doing is researching a method that can tell if a patch have been applied (source code level or binary code level). I tried google some time, but didn't find something useful.

Answer 1

It's pretty complicated, but it can be done, on some level.

Essentially, you parse the source level into tokens, after that, you build the abstract syntax tree. Once that is done, you must build a diff tool that can do semantic differential analysis between abstract syntax trees. SemanticMerge for example, does that.

Once that is done, you have semantical difference between two source codes, and then you need to define what exactly consists of a patch.

Some of the rules can be:

1) Variable content was changed

2) A if check was added

The bottom line is, differenting between patch and new functionality is not an easy task. The most reliable way is to probably check the binary file version numbers, and understand the versioning schema.

Eg, only minor version is updated, if patches are applied.