Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Thu, 28 Feb 2013 21:24:27 +0100
From: Jan Starke <jan.starke@...ofbed.org>
To: john-users@...ts.openwall.com
Subject: Re: Fuzzing with regular expressions

Hi,

I was able to compile rexgen with clang 3.2. Thogh it produced a bunch
of warnings, it worked. I'll try to fix these problems, clang seems to
be interesting.

I considered performance aspects when designing the data structures,
which have been the only performance measures I did so far. Tasks I
have on the table are support for multiple processor cores (I assume
john does this already) and optimization using a profiler. As long as
someone has interest in using rexgen, I will put work on It, so thank
you :-)

Kind regards, Jan

2013/2/28 magnum <john.magnum@...hmail.com>:
> On 28 Feb, 2013, at 13:37 , Jan Starke <jan.starke@...ofbed.org> wrote:
>
>> I fixed the version detection of bison and flex, so that e.g. a
>> version 2.7 will also match.
>>
>> I also tried to compile the code with clang (I only have 3.0), which
>> failed (with segmentation fault of clang). This evening I'll try to
>> install clang 3.3, which should have full support for C++11, which I
>> need for deque::cbegin() and deque::cend(), beyond others. You can set
>> CXX=g++ to circumvent this, so far...
>
> Ah, I did not notice that CXX was still wrong. With that fixed and latest updates everything works as it should except I miss some lua library on OSX at final linking (not likely your fault at all). On Linux it builds fine.
>
> Performance is about as bad as I feared though. Hopefully you haven't really tried optimizing it much yet, and there may be low hanging fruit. It is definitely usable already but the faster you can get it, the better. Here is what I hope is a fair benchmark:
>
> $ ./john -inc:alpha -max-len=6 -stdout | dd of=/dev/null
> words: 321272406  time: 0:00:00:13 DONE (Thu Feb 28 18:54:36 2013)  w/s: 23230K  current: qzvxqv
> 4367296+1 records in
> 4367296+1 records out
> 2236055952 bytes (2.2 GB) copied, 13.8361 s, 162 MB/s
>
> $ rexgen '[a-z]{0,6}' | dd of=/dev/null
> 1209+225843612 records in
> 4367296+1 records out
> 2236055953 bytes (2.2 GB) copied, 384.179 s, 5.8 MB/s
>
> Note that -inc is not a simple aaa-zzz bruteforce - it's much more expensive than that. I do not expect you to get near that speed unless you drop a few layers of high-level-stuff overhead but hopefully you can boost it a lot. BTW the difference in "records in" is puzzling, I wonder what it tells us?
>
> Anyway, I really like this and I will follow your progress.
>
> magnum
>
>
>> 2013/2/28 magnum <john.magnum@...hmail.com>:
>>> On 28 Feb, 2013, at 10:02 , Jan Starke <jan.starke@...ofbed.org> wrote:
>>>
>>>> Hi John,
>>>
>>> I'm just magnum, the john part of my email address refers to this JtR project. Sorry for the confusion.
>>>
>>>> I described the prerequisites under
>>>> https://code.google.com/p/rexgen/wiki/QuickStart.
>>>
>>> As a lower prio enhancement, you might want to try to relax the prerequisites (ie. the bison version). Maybe it's not that trivial though.
>>>
>>>> I discovered that gcc has some problems with lambda expressions, i.e.
>>>> that they're changing their semantics continuously. To resolve the
>>>> error in question, I've added everything to the capture list and hope
>>>> that your gcc will accept this.
>>>
>>> I installed a newer bison but somehow cmake screws up:
>>>
>>> magnum@...r-osx:build [master]$ CC=gcc cmake ..
>>> -- The C compiler identification is GNU 4.7.2
>>> -- The CXX compiler identification is Clang 4.2.0
>>> -- Checking whether C compiler has -isysroot
>>> -- Checking whether C compiler has -isysroot - yes
>>> -- Checking whether C compiler supports OSX deployment target flag
>>> -- Checking whether C compiler supports OSX deployment target flag - yes
>>> -- Check for working C compiler: /usr/local/bin/gcc
>>> -- Check for working C compiler: /usr/local/bin/gcc -- works
>>> -- Detecting C compiler ABI info
>>> -- Detecting C compiler ABI info - done
>>> -- Check for working CXX compiler: /usr/bin/c++
>>> -- Check for working CXX compiler: /usr/bin/c++ -- works
>>> -- Detecting CXX compiler ABI info
>>> -- Detecting CXX compiler ABI info - done
>>> -- Found BISON: /usr/local/bin/bison (found version "2.7")
>>> CMake Error at librexgen/CMakeLists.txt:8 (message):
>>>  rexgen-0.1.0 requires at least bison 2.5
>>>
>>>
>>> -- Configuring incomplete, errors occurred!
>>>
>>> As you can see, it finds the right bison at first but somehow confuses the version detection (probably using /usr/bin/bison). Actually, if I comment that out from librexgen/CMakeLists.txt I get the same problem with flex:
>>>
>>> ...
>>> -- Found BISON: /usr/local/bin/bison (found version "2.7")
>>> -- Found FLEX: /usr/bin/flex (found version "2.5.35")
>>> CMake Error at librexgen/CMakeLists.txt:10 (message):
>>>  rexgen-0.1.0 requires at least flex 2.5
>>>
>>>
>>> -- Configuring incomplete, errors occurred!
>>>
>>> This is even weirder since I do not have any version of flex older than 2.5.35 on this system. Ah wait, I see now it's a typo - you use BISON_VERSION where it should say FLEX_VERSION. Fixing that, cmake finishes correctly but make bails out with this:
>>>
>>> ...
>>> [ 31%] Building CXX object librexgen/CMakeFiles/rexgen-0.1.0.dir/regex/compoundregex.cpp.o
>>> In file included from /Users/magnum/src/rexgen/src/librexgen/regex/compoundregex.cpp:29:
>>> In file included from /Users/magnum/src/rexgen/src/librexgen/regex/compoundregex.h:35:
>>> /Users/magnum/src/rexgen/src/librexgen/regex/../iterator/iteratorpermuter.h:88:27: error: no member named 'cbegin' in
>>>      'std::deque<Iterator *, std::allocator<Iterator *> >'
>>>  for (auto i = iterators.cbegin(); i!=iterators.cend(); ++i) {
>>>                ~~~~~~~~~ ^
>>> /Users/magnum/src/rexgen/src/librexgen/regex/../iterator/iteratorpermuter.h:88:50: error: no member named 'cend' in
>>>      'std::deque<Iterator *, std::allocator<Iterator *> >'
>>>  for (auto i = iterators.cbegin(); i!=iterators.cend(); ++i) {
>>>                                       ~~~~~~~~~ ^
>>> /Users/magnum/src/rexgen/src/librexgen/regex/../iterator/iteratorpermuter.h:197:24: error: no member named 'cbegin'
>>>      in 'std::deque<Iterator *, std::allocator<Iterator *> >'
>>>  for(auto i=iterators.cbegin(); i!=iterators.cend(); ++i) {
>>>             ~~~~~~~~~ ^
>>> /Users/magnum/src/rexgen/src/librexgen/regex/../iterator/iteratorpermuter.h:197:47: error: no member named 'cend' in
>>>      'std::deque<Iterator *, std::allocator<Iterator *> >'
>>>  for(auto i=iterators.cbegin(); i!=iterators.cend(); ++i) {
>>>                                    ~~~~~~~~~ ^
>>>
>>>
>>> Using Clang 4.2.0 instead, I get the exact same errors.
>>>
>>> thanks,
>>> magnum
>>>
>>>
>>>> I'm currently using gcc-4.6.3-1ubuntu5 as compiler and Ubuntu 12.04.2
>>>> as platform. But nevertheless, this should compile on any current
>>>> system, I think, as I'm planning to port this to Windows, too.
>>>>
>>>> Kind Regards, Jan
>>>>
>>>> 2013/2/28 magnum <john.magnum@...hmail.com>:
>>>>> On 27 Feb, 2013, at 20:47 , Jan Starke <jan.starke@...ofbed.org> wrote:
>>>>>
>>>>>> Hi folks,
>>>>>>
>>>>>> I'm currently working on a library to create values (e.g. passwords)
>>>>>> based on regular expressions. One could use this tool together with
>>>>>> john like this:
>>>>>>
>>>>>> $ rexgen -i 'password[0-9]{2,4}' | john -pipe ....
>>>>>
>>>>> I really like this idea but I'm concerned it might be too slow. Let's hope I am wrong.
>>>>>
>>>>> A list of requirements would be nice. So far I know of cmake, log4cpp, libunistring and lua52.
>>>>>
>>>>> After fetching your latest commits I have this problem on OSX:
>>>>>
>>>>> [  5%] [FLEX][regexlexer] Building scanner with flex 2.5.35
>>>>> [ 10%] [BISON][regexparser] Building parser with bison 2.3
>>>>> parser/regex_parser.y:162.4: invalid character: `['
>>>>> parser/regex_parser.y:162.7: invalid character: `]'
>>>>> parser/regex_parser.y:165.29-30: $3 of `GroupRegex' has no declared type
>>>>> parser/regex_parser.y:166.20: warning: stray `$'
>>>>> parser/regex_parser.y:159.3-170.3: warning: unused value: $2
>>>>> make[2]: *** [librexgen/parser.cpp] Error 1
>>>>> make[1]: *** [librexgen/CMakeFiles/rexgen-0.1.0.dir/all] Error 2
>>>>> make: *** [all] Error 2
>>>>>
>>>>> The above looks like bison is too old [the OSX native one] so I tried latest Ubuntu Linux instead of digging into it. But then I got other problems:
>>>>>
>>>>> [  5%] [FLEX][regexlexer] Building scanner with flex 2.5.35
>>>>> [ 10%] [BISON][regexparser] Building parser with bison 2.5
>>>>> [ 15%] Building CXX object librexgen/CMakeFiles/rexgen-0.1.0.dir/librexgen.cpp.o
>>>>> /home/magnum/src/rexgen/src/librexgen/librexgen.cpp:46:2: warning: #warning this must be handled with normal syntax error reporting [-Wcpp]
>>>>> In file included from /home/magnum/src/rexgen/src/librexgen/parser/rexgenparsercontext.h:35:0,
>>>>>                from /home/magnum/src/rexgen/src/librexgen/librexgen.cpp:28:
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/groupreference.h: In member function ‘virtual const char_type* GroupReference::getXmlTag() const’:
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/groupreference.h:42:1: warning: cast from type ‘const char32_t*’ to type ‘char_type* {aka unsigned int*}’ casts away qualifiers [-Wcast-qual]
>>>>> [ 21%] Building CXX object librexgen/CMakeFiles/rexgen-0.1.0.dir/librexgen_lua.cpp.o
>>>>> [ 26%] Building CXX object librexgen/CMakeFiles/rexgen-0.1.0.dir/debug.cpp.o
>>>>> [ 31%] Building CXX object librexgen/CMakeFiles/rexgen-0.1.0.dir/regex/compoundregex.cpp.o
>>>>> In file included from /home/magnum/src/rexgen/src/librexgen/regex/compoundregex.h:35:0,
>>>>>                from /home/magnum/src/rexgen/src/librexgen/regex/compoundregex.cpp:29:
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/../iterator/iteratorpermuter.h: In member function ‘void IteratorPermuter<REGEX>::next()’:
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/../iterator/iteratorpermuter.h:138:9: error: capture of non-variable ‘Iterator::state’
>>>>> In file included from /home/magnum/src/rexgen/src/librexgen/regex/regex.h:32:0,
>>>>>                from /home/magnum/src/rexgen/src/librexgen/regex/compoundregex.h:32,
>>>>>                from /home/magnum/src/rexgen/src/librexgen/regex/compoundregex.cpp:29:
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/../iterator/iterator.h:58:5: note: ‘Iterator::<anonymous enum> Iterator::state’ declared here
>>>>> In file included from /home/magnum/src/rexgen/src/librexgen/regex/compoundregex.h:35:0,
>>>>>                from /home/magnum/src/rexgen/src/librexgen/regex/compoundregex.cpp:29:
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/../iterator/iteratorpermuter.h: In lambda function:
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/../iterator/iteratorpermuter.h:138:71: error: ‘this’ was not captured for this lambda function
>>>>> In file included from /home/magnum/src/rexgen/src/librexgen/regex/compoundregex.cpp:29:0:
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/compoundregex.h: In member function ‘virtual const char_type* CompoundRegex::getXmlTag() const’:
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/compoundregex.h:45:1: warning: cast from type ‘const char32_t*’ to type ‘char_type* {aka unsigned int*}’ casts away qualifiers [-Wcast-qual]
>>>>> In file included from /home/magnum/src/rexgen/src/librexgen/regex/compoundregex.cpp:30:0:
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/terminalregex.h: In constructor ‘TerminalRegex::TerminalRegex()’:
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/terminalregex.h:9:1: warning: cast from type ‘const char32_t*’ to type ‘char_type* {aka unsigned int*}’ casts away qualifiers [-Wcast-qual]
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/terminalregex.h: In member function ‘virtual const char_type* TerminalRegex::getXmlTag() const’:
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/terminalregex.h:19:1: warning: cast from type ‘const char32_t*’ to type ‘char_type* {aka unsigned int*}’ casts away qualifiers [-Wcast-qual]
>>>>> In file included from /home/magnum/src/rexgen/src/librexgen/regex/compoundregex.cpp:31:0:
>>>>> /home/magnum/src/rexgen/src/librexgen/iterator/compoundregexiterator.h: In lambda function:
>>>>> /home/magnum/src/rexgen/src/librexgen/iterator/compoundregexiterator.h:47:75: warning: deleting object of polymorphic class type ‘Iterator’ which has non-virtual destructor might cause undefined behaviour [-Wdelete-non-virtual-dtor]
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/compoundregex.cpp: In destructor ‘virtual CompoundRegex::~CompoundRegex()’:
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/compoundregex.cpp:38:13: warning: deleting object of abstract class type ‘Regex’ which has non-virtual destructor will cause undefined behaviour [-Wdelete-non-virtual-dtor]
>>>>> In file included from /home/magnum/src/rexgen/src/librexgen/regex/compoundregex.h:35:0,
>>>>>                from /home/magnum/src/rexgen/src/librexgen/regex/compoundregex.cpp:29:
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/../iterator/iteratorpermuter.h: In instantiation of ‘IteratorPermuter<REGEX>::initIterators() [with REGEX = Regex]::<lambda(Iterator*)>’:
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/../iterator/iteratorpermuter.h:173:49:   required from ‘struct IteratorPermuter<REGEX>::initIterators() [with REGEX = Regex]::<lambda(class Iterator*)>’
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/../iterator/iteratorpermuter.h:173:3:   required from ‘void IteratorPermuter<REGEX>::initIterators() [with REGEX = Regex]’
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/../iterator/iteratorpermuter.h:71:3: required from ‘IteratorPermuter<REGEX>::IteratorPermuter(int, const REGEX*, IteratorState*, unsigned int, unsigned int) [with REGEX = Regex]’
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/compoundregex.cpp:88:63:   required from here
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/../iterator/iteratorpermuter.h:173:64: warning: deleting object of polymorphic class type ‘Iterator’ which has non-virtual destructor might cause undefined behaviour [-Wdelete-non-virtual-dtor]
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/../iterator/iteratorpermuter.h: In instantiation of ‘IteratorPermuter<REGEX>::initIterators() [with REGEX = CompoundRegex]::<lambda(Iterator*)>’:
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/../iterator/iteratorpermuter.h:173:49:   required from ‘struct IteratorPermuter<REGEX>::initIterators() [with REGEX = CompoundRegex]::<lambda(class Iterator*)>’
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/../iterator/iteratorpermuter.h:173:3:   required from ‘void IteratorPermuter<REGEX>::initIterators() [with REGEX = CompoundRegex]’
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/../iterator/iteratorpermuter.h:71:3: required from ‘IteratorPermuter<REGEX>::IteratorPermuter(int, const REGEX*, IteratorState*, unsigned int, unsigned int) [with REGEX = CompoundRegex]’
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/compoundregex.cpp:96:59:   required from here
>>>>> /home/magnum/src/rexgen/src/librexgen/regex/../iterator/iteratorpermuter.h:173:64: warning: deleting object of polymorphic class type ‘Iterator’ which has non-virtual destructor might cause undefined behaviour [-Wdelete-non-virtual-dtor]
>>>>> make[2]: *** [librexgen/CMakeFiles/rexgen-0.1.0.dir/regex/compoundregex.cpp.o] Error 1
>>>>> make[1]: *** [librexgen/CMakeFiles/rexgen-0.1.0.dir/all] Error 2
>>>>> make: *** [all] Error 2
>>>>>
>>>>>
>>>>> Is this the result of me still missing something? On what platform are you developing this?
>>>>>
>>>>> magnum
>>>>
>>>
>>>
>>
>
>

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.