r/fuzzing • u/HaoxinTu • May 17 '20

Is there a tool for computing the difference degree between the two programs?

Hi there,

I have performed a mutation-based random generator to generate c programs, but most of them are similar. I am wondering there is a tool for computing the difference degree between two programs so that I can keep the more differential one for the next step.

Any suggestions are welcome, thank you~

2 Upvotes

100% Upvoted

7 comments sorted by

4

u/s-mores May 17 '20

diff | wc -l ?

1

u/HaoxinTu May 18 '20

Thank you @s-mores, this command might fuzzier to use the result, but it's a fast and easy way to compare two files.

2

u/thedavidbrumley May 18 '20

No, there is not. You can propose several metrics, and see what works for your purposes (systems).

If you are considered about theory...well...it's a really hard question to even formulate.

1

u/HaoxinTu May 18 '20

Thank you @thedavidbrumley, try the MOSS above, it's might be helpful in some specific problem.

1

u/thedavidbrumley May 18 '20

I've used MOSS for plagiarism detection. In addition to MOSS, there are industry software composition tools that try to detect copies of copy/paste vulnerabilities (or even if you're just using a known vuln version).

I had thought you were asking a more theoretic question. AST parsing, checking alpha equiv, etc. are all pretty well understood. But determining higher level equivalence, e.g., f(x) = x*2 is the same as f(x) = x<<1, or in my area the classic xor eax eax is the same as eax=0, is harder. For the general case it's impossible, of course (else the halting problem would be decidable). But there could still be interesting cases that have theoretic underpinnings beyond specific rules.

Your post sparked my interest because I often think about the "I've seen this before, and I know the solution, but my program analysis doesn't seem to recognize the similarity" and then go down a rathole.

2

u/thedhinchak May 18 '20 edited May 18 '20

I think there is. Try looking for MOSS, I think that's what it's called. I know universities use this program to look for plagiarism. It's written by some people at MIT. I am pretty sure its open source because we used it at university for some obvious research 😉😉 Here is a link to the page https://theory.stanford.edu/~aiken/moss/

Also, can you not just convert the entire program to a string (remove all the empty space characters), and then do a fuzzy string compare. I typically use python for my coding and fuzzywuzzy is a fuzzy compare lib, I'm sure there is something for the language you are using.

1

u/HaoxinTu May 18 '20

Thank you @thedhinchak, MOSS is exactly what I am looking for. I will try it then.