SERVER-10026 limit tree depth allowed by the match expression parser

4 files changed, 76 insertions, 9 deletions

diff --git a/src/mongo/db/matcher/expression_parser.cpp b/src/mongo/db/matcher/expression_parser.cpp
index 823543ac29d..bfc363ceda1 100644
--- a/src/mongo/db/matcher/expression_parser.cpp
+++ b/src/mongo/db/matcher/expression_parser.cpp
@@ -245,10 +245,17 @@ namespace mongo {
                                           mongoutils::str::stream() << "not handled: " << e.fieldName() );
     }
 
-    StatusWithMatchExpression MatchExpressionParser::_parse( const BSONObj& obj, bool topLevel ) {
+    StatusWithMatchExpression MatchExpressionParser::_parse( const BSONObj& obj, int level ) {
+        if (level > kMaximumTreeDepth) {
+            return StatusWithMatchExpression( ErrorCodes::BadValue,
+                                              "exceeded maximum query tree depth" );
+        }
 
         std::auto_ptr<AndMatchExpression> root( new AndMatchExpression() );
 
+        bool topLevel = (level == 0);
+        level++;
+
         BSONObjIterator i( obj );
         while ( i.more() ){
 
@@ -262,7 +269,7 @@ namespace mongo {
                         return StatusWithMatchExpression( ErrorCodes::BadValue,
                                                      "$or needs an array" );
                     std::auto_ptr<OrMatchExpression> temp( new OrMatchExpression() );
-                    Status s = _parseTreeList( e.Obj(), temp.get() );
+                    Status s = _parseTreeList( e.Obj(), temp.get(), level );
                     if ( !s.isOK() )
                         return StatusWithMatchExpression( s );
                     root->add( temp.release() );
@@ -272,7 +279,7 @@ namespace mongo {
                         return StatusWithMatchExpression( ErrorCodes::BadValue,
                                                      "and needs an array" );
                     std::auto_ptr<AndMatchExpression> temp( new AndMatchExpression() );
-                    Status s = _parseTreeList( e.Obj(), temp.get() );
+                    Status s = _parseTreeList( e.Obj(), temp.get(), level );
                     if ( !s.isOK() )
                         return StatusWithMatchExpression( s );
                     root->add( temp.release() );
@@ -282,7 +289,7 @@ namespace mongo {
                         return StatusWithMatchExpression( ErrorCodes::BadValue,
                                                      "and needs an array" );
                     std::auto_ptr<NorMatchExpression> temp( new NorMatchExpression() );
-                    Status s = _parseTreeList( e.Obj(), temp.get() );
+                    Status s = _parseTreeList( e.Obj(), temp.get(), level );
                     if ( !s.isOK() )
                         return StatusWithMatchExpression( s );
                     root->add( temp.release() );
diff --git a/src/mongo/db/matcher/expression_parser.h b/src/mongo/db/matcher/expression_parser.h
index 6b3bbc93eab..6b714429920 100644
--- a/src/mongo/db/matcher/expression_parser.h
+++ b/src/mongo/db/matcher/expression_parser.h
@@ -50,7 +50,8 @@ namespace mongo {
          * the tree has views (BSONElement) into obj
          */
         static StatusWithMatchExpression parse( const BSONObj& obj ) {
-            return _parse( obj, true );
+            // The 0 initializes the match expression tree depth.
+            return _parse( obj, 0 );
         }
 
     private:
@@ -75,7 +76,14 @@ namespace mongo {
          */
         static bool _isDBRefDocument( const BSONObj& obj, bool allowIncompleteDBRef );
 
-        static StatusWithMatchExpression _parse( const BSONObj& obj, bool topLevel );
+        /**
+         * Parse 'obj' and return either a MatchExpression or an error.
+         *
+         * 'level' tracks the current depth of the tree across recursive calls to this
+         * function. Used in order to apply special logic at the top-level and to return an
+         * error if the tree exceeds the maximum allowed depth.
+         */
+        static StatusWithMatchExpression _parse( const BSONObj& obj, int level );
 
         /**
          * parses a field in a sub expression
@@ -123,10 +131,12 @@ namespace mongo {
 
         // tree
 
-        static Status _parseTreeList( const BSONObj& arr, ListOfMatchExpression* out );
+        static Status _parseTreeList( const BSONObj& arr, ListOfMatchExpression* out, int level );
 
         static StatusWithMatchExpression _parseNot( const char* name, const BSONElement& e );
 
+        // The maximum allowed depth of a query tree. Just to guard against stack overflow.
+        static const int kMaximumTreeDepth;
     };
 
     typedef boost::function<StatusWithMatchExpression(const char* name, int type, const BSONObj& section)> MatchExpressionParserGeoCallback;
diff --git a/src/mongo/db/matcher/expression_parser_tree.cpp b/src/mongo/db/matcher/expression_parser_tree.cpp
index 4b7c6df75b2..9f020230ac3 100644
--- a/src/mongo/db/matcher/expression_parser_tree.cpp
+++ b/src/mongo/db/matcher/expression_parser_tree.cpp
@@ -42,7 +42,14 @@
 
 namespace mongo {
 
-    Status MatchExpressionParser::_parseTreeList( const BSONObj& arr, ListOfMatchExpression* out ) {
+    // static
+    const int MatchExpressionParser::kMaximumTreeDepth = 20;
+
+    Status MatchExpressionParser::_parseTreeList( const BSONObj& arr,
+                                                  ListOfMatchExpression* out,
+                                                  int level ) {
+        level++;
+
         if ( arr.isEmpty() )
             return Status( ErrorCodes::BadValue,
                            "$and/$or/$nor must be a nonempty array" );
@@ -55,7 +62,7 @@ namespace mongo {
                 return Status( ErrorCodes::BadValue,
                                "$or/$and/$nor entries need to be full objects" );
 
-            StatusWithMatchExpression sub = _parse( e.Obj(), false );
+            StatusWithMatchExpression sub = _parse( e.Obj(), level );
             if ( !sub.isOK() )
                 return sub.getStatus();
 
diff --git a/src/mongo/db/matcher/expression_parser_tree_test.cpp b/src/mongo/db/matcher/expression_parser_tree_test.cpp
index 7257353e2ec..ee0507ad274 100644
--- a/src/mongo/db/matcher/expression_parser_tree_test.cpp
+++ b/src/mongo/db/matcher/expression_parser_tree_test.cpp
@@ -100,6 +100,49 @@ namespace mongo {
         ASSERT( !result.getValue()->matchesBSON( BSON( "x" << 8 ) ) );
     }
 
+    TEST( MatchExpressionParserTreeTest, MaximumTreeDepth ) {
+        // This match tree is about 60 levels deep, which exceeds
+        // the maximum allowed depth.
+        BSONObj query = fromjson(
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2},"
+            "{$and: [{a: 3}, {$or: [{b: 2}, {b: 4}]}]}"
+            "]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]"
+            "}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}"
+            "]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]});"
+        );
+
+        StatusWithMatchExpression result = MatchExpressionParser::parse( query );
+        ASSERT_FALSE( result.isOK() );
+    }
+
     TEST( MatchExpressionParserLeafTest, NotRegex1 ) {
         BSONObjBuilder b;
         b.appendRegex( "$not", "abc", "i" );