Re: [sleuthkit-users] Regular Expressions

[Tim <tim...@se...>]

Makes sense.  But yeah, if you deal with this situation properly, then
you get a lot more flexibility in what block sizes and tokenization
approach you use.  If you don't deal with this situation, large blocks
don't eliminate the problem, they just make missing things less likely.

tim


On Mon, Nov 14, 2016 at 06:39:59PM -0500, Simson Garfinkel wrote:
> Hi Tim,
> 
> Take a look at the bulk_extractor paper, which explains this in detail. There is no need to index block[N-1] below, just block[N] || X bytes from block[N+1], where X is the margin.
> 
> You always need to worry about the margins, because if you don't, you double-report findings. It turns out that there are a lot of optimizations that you can implement if you do things the way I recommend below. For example, you never need to do duplicate suppression if you only index strings that being in block[N], even if they extend into block[N+1].
> 
> > On Nov 14, 2016, at 6:04 PM, Tim <tim...@se...> wrote:
> > 
> > 
> > Right.  Why not go with 32KB blocks and then index based on overlapped
> > windows?  To index block[N], you include this string in the index:
> >   (block[N-1] || block[N] || block[N+1])
> > 
> > Then when a match occurs, you just add some logic to figure out where
> > it actually showed up (only in margin blocks or partially in block[N])
> > 
> > This is perhaps more naive than what Simson suggests, but with small
> > blocks you don't need to worry about having the margins be much
> > smaller than the block you're indexing.
> > 
> > tim
> > 
> > PS - I'm probably missing something here.  I've been out of the game a
> > while.
> > 
> > 
> > On Mon, Nov 14, 2016 at 05:22:26PM -0500, Simson Garfinkel wrote:
> >> Brian,
> >> 
> >> With respect to #1 - I solved this problem with bulk_extractor by using an overlapping margin. Extend each block 1K or so into the next block. The extra 1k is called the Margin. Only report hits on string search if the text string beings in the main block, not if it begin in the margin (because then it is included entirely in the next block). You can tune the margin size to describe the largest text object that you wish to find with search.
> >> 
> >> Simson
> >> 
> >> 
> >>> On Nov 14, 2016, at 5:14 PM, Brian Carrier <ca...@sl...> wrote:
> >>> 
> >>> Making this a little more specific, we seem to have two options to solve this problem (which is inherent to Lucene/Solr/Elastic):
> >>> 
> >>> 1) We store text in 32KB chunks (instead of our current 1MB chunks) and can have the full power of regular expressions.   The downside of the smaller chunks is that there are more boundaries and places where a term could span the boundary and we could miss a hit if it spans that boundary.   If we needed to, we could do some fancy overlapping.   32KB of text is about 12 pages of English text (less for non-English). 
> >>> 
> >>> 2) We limit the types of regular expressions that people can use and keep our 1MB chunks. We’ll add some logic into Autopsy to span tokens, but we won’t be able to support all expressions.  For example, if you gave us “\d\d\d\s\d\d\d\d” we’d turn that into a search for “\d\d\d \d\d\d\d”, but we wouldn’t able to support a search like “\d\d\d[\s-]\d\d\d\d”.  Well we could in theory, but we dont’ want to add crazy complexity here. 
> >>> 
> >>> So, the question is if you’d rather have smaller chunks and the full breadth of regular expressions or a more limited set of expressions and bigger chunks.  We are looking at the performance differences now, but wanted to get some initial opinions. 
> >>> 
> >>> 
> >>> 
> >>> 
> >>>> On Nov 14, 2016, at 1:09 PM, Brian Carrier <ca...@sl...> wrote:
> >>>> 
> >>>> Autopsy currently has a limitation when searching for regular expressions, that spaces are not supported.  It’s not a problem for Email addresses and URLs, but becomes an issue phone numbers, account numbers, etc.  This limitation comes from using an indexed search engine (since spaces are used to break text into tokens). 
> >>>> 
> >>>> We’re looking at ways of solving that and need some guidance. 
> >>>> 
> >>>> If you write your own regular expressions, can you please let me know and share what they look like.  We want to know how complex the expressions are that people use in real life. 
> >>>> 
> >>>> Thanks!
> >>>> ------------------------------------------------------------------------------
> >>>> _______________________________________________
> >>>> sleuthkit-users mailing list
> >>>> https://lists.sourceforge.net/lists/listinfo/sleuthkit-users
> >>>> http://www.sleuthkit.org
> >>> 
> >>> 
> >>> ------------------------------------------------------------------------------
> >>> _______________________________________________
> >>> sleuthkit-users mailing list
> >>> https://lists.sourceforge.net/lists/listinfo/sleuthkit-users
> >>> http://www.sleuthkit.org
> >> 
> >> 
> >> ------------------------------------------------------------------------------
> >> _______________________________________________
> >> sleuthkit-users mailing list
> >> https://lists.sourceforge.net/lists/listinfo/sleuthkit-users
> >> http://www.sleuthkit.org
>