Patroonherkenning in bestanden

[Verwijderd]

Ik wil in willekeurige bestanden zoeken naar bepaalde patronen.
De patronen zijn willekeurig van aard (denk aan het idee van een virusscanner, anti spyware). Het is niet voldoende om alleen een hash van het bestand te vergelijken.

Ideaal zou natuurlijk zijn om voor elk patroon een 'soort eindige automaat' te maken en die om te zetten naar een wiskundige grammatica.
Alle patronen/grammatica's samenvoegen d.m.v. een zelfgemaakte compiler in een eigen formaat bestand en die dan gebruiken bij het scannen.
Overigens denk ik niet dat ik de patronen op deze manier kan beschrijven, omdat ik ook bestandslengte checks e.d. moet uitvoeren. Deze optie lijkt me dus erg bewerkelijk.

Een andere optie is om gewoon voor elk patroon het bestand van begin tot eind te doorzoeken. Mijn eerste ingeving zegt dat dit niet echt positief is voor de performance. Maar het maakt het programma wel flexibel en makkelijk uitbreidbaar met andere patronen.

Hoe pakken andere scanners dit aan?
En wat is verstandig?

[Soultaker]

Kun je misschien toelichten hoe een 'patroon' er precies uitziet? Dat lijkt me namelijk wel relevant voor de vraag hoe je die moet matchen op een bestand.

Overigens weet ik ook niet precies hoe virusscanners werken. (Die scannen toch op aardig wat signatures in relatief weinig tijd.)

[Verwijderd]

Soultaker schreef op zondag 16 april 2006 @ 17:36:
Kun je misschien toelichten hoe een 'patroon' er precies uitziet? Dat lijkt me namelijk wel relevant voor de vraag hoe je die moet matchen op een bestand.

Dat kan van alles zijn.
Bijvoorbeeld een zelfgemaakt bestandsformaat met eigen structuren.
Of bijvoorbeeld het patroon van een mp3-bestand. Controle of header klopt en of waarden binnen bereik liggen, ID3v2-tag, etc.
Of bijvoorbeeld het patroon van een .exe-bestand...

[Spruit_elf]

Verwijderd schreef op zondag 16 april 2006 @ 20:17:
[...]

Dat kan van alles zijn.
Bijvoorbeeld een zelfgemaakt bestandsformaat met eigen structuren.
Of bijvoorbeeld het patroon van een mp3-bestand. Controle of header klopt en of waarden binnen bereik liggen, ID3v2-tag, etc.
Of bijvoorbeeld het patroon van een .exe-bestand...

heb ik het goed als ik denk dat je:

van te voren de 'structuur' van het bestand dus al kent en dat je een scanner wilt maken met die een hele set van zulke 'structuren' kent en op basis daarvan kijkt of bijv een mp3tje echt een mp3tje is enz?

ik denk dat je met een regexp oid in veel gevallen al een eind komt
als ik dit zo lees
http://www.codeproject.com/csharp/ahocorasick.asp

kan je idd beter ht onderstaande algoritme gebruiken

[ Voor 11% gewijzigd door Spruit_elf op 17-04-2006 21:52 ]

[Verwijderd]

mrcactus schreef op zondag 16 april 2006 @ 23:19:
[...]

heb ik het goed als ik denk dat je:

van te voren de 'structuur' van het bestand dus al kent en dat je een scanner wilt maken met die een hele set van zulke 'structuren' kent en op basis daarvan kijkt of bijv een mp3tje echt een mp3tje is enz?

Ja, klopt.

mrcactus schreef op zondag 16 april 2006 @ 23:19:
ik denk dat je met een regexp oid in veel gevallen al een eind komt

[Apollo_Futurae]

Virusscanners werken denk ik met (een variant op) het Aho-Corasick algoritme. Kort gezegd komt dat erop neer dat je op een hele verzameling strings tegelijk zoekt, door de strings van tevoren te combineren tot een eindig automaton (zoiets suggereerde je zelf ook al). Als je patroon niet een simpele stringmatch is, zul je erover na moeten denken of je die patronen ook nog op zinnige wijze kunt combineren.

[MSalters]

Er zijn patronen waarbij het onvermijdelijk is dat je de hele file moet doorzoeken (patroon "bevat de file een 0xCC?" bijvoorbeeld.). Het is dus essentieel dat je engine dat kan.In het algemeen zou ik het echter anders opzetten, door stream matchers te gebruiken. Elke matcher kan op basis van de eerste N bytes dan de antwoorden { match, nog geen match, zeker geen match } geven. Je kunt dan vaak eerder stoppen; hoe vroeg hangt er vanaf wat je wil weten (tenminste 1 match of het precieze aantal).

Hoe effectief dit is hangt af van je patronen, maar elk patroon is ermee te matchen. Strings zijn vaak efficient ermee te matchen; 95% van de strings vallen na het eerste karakter af.