regex and binary data

[u0206397]

Is regex the right tool for searching binary data?

For example, if I have a directory of binary files, and I want to find those that contains certain byte sequence.

Or should I write a custom program/script for it?

 

[cwchong]

No experience in this, just chiming, regex prob not too efficient since it literally searches the whole string

Maybe there is some transformation filter you can apply to the bin files to reduce to a result that shows markers if the sequence you are looking for exists?

Brb googling

 

[cwchong]

Here is a paper on that
https://resources.sei.cmu.edu/library/asset-view.cfm?assetid=312841

 

[u0206397]

I am thinking for those bioinformatics researchers who probably have to scan through long sequence of data (in binary?), they tend to use Python or Perl. Wonder if there's something in Python or Perl that helps them do this well.

 

[cwchong]

I am thinking for those bioinformatics researchers who probably have to scan through long sequence of data (in binary?), they tend to use Python or Perl. Wonder if there's something in Python or Perl that helps them do this well.

Maybe they are regexing thats why take so long? I remember long time ago there’s that human genome project where we can contribute our idle cpu to help do the calculations, before crypto

 

[davidktw]

Is regex the right tool for searching binary data?

For example, if I have a directory of binary files, and I want to find those that contains certain byte sequence.

Or should I write a custom program/script for it?

Regex operating on binary should be just as efficient as operating on textual. The basics of regex is based on DFA, Deterministic Finite Automata. The matching of characters are mostly language or code pages agnostics, it is matching for equivalence mostly, not really english or non-english or chinese or other human languages. There are those grouping cases like matching for “Alphabets”, which are in basics expressed as [A-Za-z]. Here the search space is 52 characters, which is often just a O(1) operation. Even if it is another group like \AlienAlphabets, it is still going to be O(1) when it is span across 1000 possible characters.

When you apply this to binary, it is just another set of characters set, so regex works just the same as long as you know the structure in the binary you are searching for. The issue is you need structure to search, otherwise the regex will not understand 4 bytes make an integer, and in the binary world, a 32bits double word can be 4 ASCII characters, or 2 16bits words, or one 32bits integer, or even a single precision float point value.

When it comes to performance, regex is not the most effective string matching algorithm, but it is an extremely flexible one.

If you want to find matching sequence of bytes in a directory, there is one extremely good software for it

egrep -r DIRECTORY REGEX

 

[davidktw]

I am thinking for those bioinformatics researchers who probably have to scan through long sequence of data (in binary?), they tend to use Python or Perl. Wonder if there's something in Python or Perl that helps them do this well.

Perl has /(probably)?/ the most powerful regex implementation available in the industry today, Python is lagging behind Perl in regex implementation but probably scientists are using it for it’s scientific libraries such as SciPy.

 

[cwchong]

Regex operating on binary should be just as efficient as operating on textual. The basics of regex is based on DFA, Deterministic Finite Automata. The matching of characters are mostly language or code pages agnostics, it is matching for equivalence mostly, not really english or non-english or chinese or other human languages. There are those grouping cases like matching for “Alphabets”, which are in basics expressed as [A-Za-z]. Here the search space is 52 characters, which is often just a O(1) operation. Even if it is another group like \AlienAlphabets, it is still going to be O(1) when it is span across 1000 possible characters.

When you apply this to binary, it is just another set of characters set, so regex works just the same as long as you know the structure in the binary you are searching for. The issue is you need structure to search, otherwise the regex will not understand 4 bytes make an integer, and in the binary world, a 32bits double word can be 4 ASCII characters, or 2 16bits words, or one 32bits integer, or even a single precision float point value.

When it comes to performance, regex is not the most effective string matching algorithm, but it is an extremely flexible one.

If you want to find matching sequence of bytes in a directory, there is one extremely good software for it

egrep -r DIRECTORY REGEX

I remember back in an uni project abt image recognition and matching what we did was apply various mathlab transformations and did something like an intersection between resultant images; I wonder if the technique is similar

 

[davidktw]

I remember back in an uni project abt image recognition and matching what we did was apply various mathlab transformations and did something like an intersection between resultant images; I wonder if the technique is similar

Well images are quite different discussion and it normally don't fall under this thread context.

Suppose if I give you 2 images. One is halve the resolution of another, would you consider them different ? That's where you need to define "different".

In some strict cases, we want every single pixel exactly the same. In some cases, we only consider different if the imagery content is different.

One naive approach is simply normalise the 2 images to same or near similar size and resolution, compare the percentage of pixel differences, then put in a threshold to determine beyond how much of pixel colour differences that one would consider the images are different.

There are quite a number of such image differences engines designed using javascript that you can get a feel on it. Here is one of them http://humblesoftware.github.io/js-imagediff/

So it boils down to what your definition of differences between images mean.