Tool to scan files for common byte sequences

[dila]

Yes, i made a prototype. But it turns out such a tool is of no use to anyone, so i will not continue to develop it.

I think the idea is quite simple, but it seems not many people understood. Binary (or text) difference tools that compare a pair of files is not really the same at all.

The prototype I created can compare any number of files and find a string that is present in all of them, up to some desired length.

[chants]

The problem with this task - e.g. common substrings problem, is that is a high complexity so that it requires a lot of difficult heuristic tricks to get it below O(n^2) otherwise it is too slow or uses too much memory. I have not seen any tools to do this. It would work with pictures or videos or audio as well - to find matching image sections, video subclips, etc. But really, it would be quite useful. I am quite certain we are talking an NP-hard problem please see:

https://en.wikipedia.org/wiki/Longest_common_substring_problem

Although this problem is less complex, you did not specify only the longest common substring but all common substrings. Yes the suffix tree and other tricks can solve this one faster.

And there are proofs I believe that shortest common substring is NP-hard.
See for example

https://docs.lib.purdue.edu/cgi/viewcontent.cgi?httpsredir=1&article=2225&context=cstech

[Stingered]

Originally Posted by chants

The problem with this task - e.g. common substrings problem, is that is a high complexity so that it requires a lot of difficult heuristic tricks to get it below O(n^2) otherwise it is too slow or uses too much memory. I have not seen any tools to do this. It would work with pictures or videos or audio as well - to find matching image sections, video subclips, etc. But really, it would be quite useful. I am quite certain we are talking an NP-hard problem please see:

Although this problem is less complex, you did not specify only the longest common substring but all common substrings. Yes the suffix tree and other tricks can solve this one faster.

And there are proofs I believe that shortest common substring is NP-hard.
See for example

I mean, yes, the same for grep (in general).

[Stingered]

Originally Posted by dila

Yes, i made a prototype. But it turns out such a tool is of no use to anyone, so i will not continue to develop it.

I think the idea is quite simple, but it seems not many people understood. Binary (or text) difference tools that compare a pair of files is not really the same at all.

The prototype I created can compare any number of files and find a string that is present in all of them, up to some desired length.

Actually, I think it could be depending one what you are searching for. obviously it is not a simple search, but very specific (over a large spectrum). Does not mean it isn't useful. I was intrigued by the thought.

[chants]

Grep is just looking for regex's so its complexity is that of pattern matching of regex's. Now you are asking a very general and arbitrary common substring problem. They are not the same issue really at all.

This would be very useful, but it has a really problematic size vs speed tradeoff and would need some kind of limiting parameters like you are getting at. The NP-hard issue can be side stepped through heuristics and domain specific approach. Nonetheless, I doubt you will find such a tool for general cases.

[Stingered]

Originally Posted by chants

Grep is just looking for regex's so its complexity is that of pattern matching of regex's. Now you are asking a very general and arbitrary common substring problem. They are not the same issue really at all.

This would be very useful, but it has a really problematic size vs speed tradeoff and would need some kind of limiting parameters like you are getting at. The NP-hard issue can be side stepped through heuristics and domain specific approach. Nonetheless, I doubt you will find such a tool for general cases.

Good explanation (both posts). There was an old (privately written back in the early 90's) tool that I used for function and string searches (waaay before this particular code base was being indexed). And even that tool could take all day to search through (the code base was very large). Not exactly the same example, but I see your point regarding the size vs speed you described.

I believe I read that the metasploit framework included some heuristics for this kind of search, but I could find no specific tool.

I too agree that a tool like this would be very useful.

[ontryit]

Originally Posted by dila

Yes, i made a prototype. But it turns out such a tool is of no use to anyone, so i will not continue to develop it.

I think the idea is quite simple, but it seems not many people understood. Binary (or text) difference tools that compare a pair of files is not really the same at all.

The prototype I created can compare any number of files and find a string that is present in all of them, up to some desired length.

You can share you prototype tool with its source code here, may be it will be useful for someone. Thx

[dosprog]

Similar problem solve the archivers.
That if try to take out the algorithm from some open-source archiver?

[dila]

Yes, I figured the problem was similar to building a dictionary of common sequences, which you'd then substitute with shorter codes corresponding to the dictionary entries.

As we discussed, it doesn't sound like a perfect solution is possible, but some heuristics would work. You mentioned compression which would do exactly this kind of operation - pick your favourite algorithm.

(I won't make the code available for my tool, since it was a rushed prototype and I don't think there any chance of anyone getting all the necessary libs to compile it.)