[SERVER-21663] Invalid parameter to ensureIndex can trigger server hang on operation Created: 25/Nov/15  Updated: 16/Feb/16  Resolved: 27/Jan/16

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: 2.6.11, 3.0.7, 3.2.0-rc4
Fix Version/s: None

Type: Bug Priority: Major - P3
Reporter: Robert Guo (Inactive) Assignee: Max Hirschhorn
Resolution: Duplicate Votes: 0
Labels: fuzzer-blacklist
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Depends
Related
is related to SERVER-11064 Stricter validation of index key patt... Closed
Operating System: ALL
Sprint: QuInt E (01/11/16), Query F (02/01/16)
Participants:
Linked BF Score: 0

 Description   

Passing an invalid parameter to ensureIndex can cause the query planner to get stuck in the for loop in PlanExecutor::getNextImpl.

This hangs the server on 2.6 and 3.0 but only the operation thread on 3.2.0-rc4

 [2015/11/20 02:07:24.294] #0  0x0000000001038489 in mongo::KeyString::toBson(char const*, unsigned long, mongo::Ordering, mongo::KeyString::TypeBits const&) ()
 [2015/11/20 02:07:24.294] #1  0x00000000010ddf43 in mongo::(anonymous namespace)::WiredTigerIndexCursorBase::seek(mongo::IndexSeekPoint const&, mongo::SortedDataInterface::Cursor::RequestedInfo) ()
 [2015/11/20 02:07:24.294] #2  0x0000000000bd9f80 in mongo::IndexScan::work(unsigned long*) ()
 [2015/11/20 02:07:24.295] #3  0x0000000000bcdbb1 in mongo::FetchStage::work(unsigned long*) ()
 [2015/11/20 02:07:24.295] #4  0x0000000000bfffe9 in mongo::SubplanStage::work(unsigned long*) ()
 [2015/11/20 02:07:24.295] #5  0x0000000000e82be5 in mongo::PlanExecutor::getNextImpl(mongo::Snapshotted<mongo::BSONObj>*, mongo::RecordId*) ()
 [2015/11/20 02:07:24.295] #6  0x0000000000e832a9 in mongo::PlanExecutor::getNext(mongo::BSONObj*, mongo::RecordId*) ()
 [2015/11/20 02:07:24.295] #7  0x0000000000b22b4d in mongo::FindCmd::run(mongo::OperationContext*, std::string const&, mongo::BSONObj&, int, std::string&, mongo::BSONObjBuilder&) ()
 [2015/11/20 02:07:24.295] #8  0x0000000000ba4819 in mongo::Command::run(mongo::OperationContext*, mongo::rpc::RequestInterface const&, mongo::rpc::ReplyBuilderInterface*) ()
 [2015/11/20 02:07:24.295] #9  0x0000000000ba5346 in mongo::Command::execCommand(mongo::OperationContext*, mongo::Command*, mongo::rpc::RequestInterface const&, mongo::rpc::ReplyBuilderInterface*) ()
 [2015/11/20 02:07:24.296] #10 0x0000000000afed00 in mongo::runCommands(mongo::OperationContext*, mongo::rpc::RequestInterface const&, mongo::rpc::ReplyBuilderInterface*) ()
 [2015/11/20 02:07:24.296] #11 0x0000000000cb885d in mongo::assembleResponse(mongo::OperationContext*, mongo::Message&, mongo::DbResponse&, mongo::HostAndPort const&) ()
 [2015/11/20 02:07:24.296] #12 0x000000000098a19c in mongo::MyMessageHandler::process(mongo::Message&, mongo::AbstractMessagingPort*) ()
 [2015/11/20 02:07:24.296] #13 0x000000000132940d in mongo::PortMessageServer::handleIncomingMsg(void*)



 Comments   
Comment by Max Hirschhorn [ 27/Jan/16 ]

Closing as a duplicate of SERVER-11064. (Cleared the backport requested fields.)

Comment by Max Hirschhorn [ 22/Dec/15 ]

The IndexBoundsChecker incorrectly computed the orientation of the index as being descending on "a", but sees that the index cursor is doing a forward scan of the index. The hang is an infinite loop that comes from the IndexBoundsChecker viewing the index cursor as positioned BEHIND where it should be to search the next interval; IndexBoundsChecker::checkKey() returns MUST_ADVANCE and causes the index cursor to seek to where it is currently positioned.

Consider the situation where the collection contains only the document {a: 'string'} and the index {a: NaN}. The query {a: {$in: [1, 3]}} will then try to search the intervals [1, 1] and [3, 3] of that index.

1. With the debugger, we can learn that key is {"" : "string"} in IndexBoundsChecker::checkKey(key, out).
2. The _expectedDirection of the index is incorrectly identified by the index bounds checker as -1 because NaN >= 0 returns false.
3. The index bounds checker compares the key to the first interval [3, 3]. (Where "first" is from the perspective of a descending index on the "a" field.) intervalCmp([3, 3], { "" : "string" }, -1) returns BEHIND because bsonWoCompare({"": "string"}, {"" : 3}) > 0 (mongo::NumberDouble comes before mongo::String).

4. The following IndexSeekPoint is generated:

keyPrefix = { "" : "string" }
prefixLen = 0
prefixExclusive = false
keySuffix = [ { "" : 3 } ]
suffixInclusive = [ true ]

5. The index cursor seeks to {"" : 3} and remains positioned at the document {a: 'string'} (rather than say EOF) because it's a forward cursor and an ascending index on the "a" field. The index bound checker sees the cursor still as behind the position of where it needs to be to search the next interval and tells it to see to the same IndexSeekPoint ad infinitum.

Comment by David Storch [ 21/Dec/15 ]

max.hirschhorn, that patch looks pretty sketchy to me, since

  1. we'd have to find all the places that use (elt.number() >= 0) as an ascending check, and
  2. it makes the correct way to check for ascending/descending even more subtle.

I'm tempted to fold this into SERVER-11064, schedule SERVER-11064, and then resolve this as a duplicate of SERVER-11064. We'd have to think carefully about what kind of values we can reject inside an index key pattern without breaking applications, but I think the following we could do safely:

  • Reject NaN
  • Reject undefined
  • Reject JavaScript code
  • Reject BinData

This would plug in nicely in index_key_validate.cpp and index_key_validate_test.cpp. Does that plan sound good to you?

One question: why does the planner's bounds error result in a server hang?

Comment by Max Hirschhorn [ 21/Dec/15 ]

This appears to be a bug in index bounds generation. The Ordering class considers the index {a: NaN} to be ascending on "a", but bounds are generated as though the index was descending on "a".

> db.foo.drop()
> db.foo.insert({a: 1})
> db.foo.createIndex({a: NaN})
> db.foo.find({})
{ "_id" : ObjectId("567730db95459c76838b7c76"), "a" : 1 }
> db.foo.find({}).hint({a: NaN})
> db.foo.find({}).hint({a: NaN}).explain()
{
    "queryPlanner" : {
        "plannerVersion" : 1,
        "namespace" : "test.foo",
        "indexFilterSet" : false,
        "parsedQuery" : {
            "$and" : [ ]
        },
        "winningPlan" : {
            "stage" : "FETCH",
            "inputStage" : {
                "stage" : "IXSCAN",
                "keyPattern" : {
                    "a" : NaN
                },
                "indexName" : "a_NaN",
                "isMultiKey" : false,
                "isUnique" : false,
                "isSparse" : false,
                "isPartial" : false,
                "indexVersion" : 1,
                "direction" : "forward",
                "indexBounds" : {
                    "a" : [
                        "[MaxKey, MinKey]"
                    ]
                }
            }
        },
        "rejectedPlans" : [ ]
    },
    "serverInfo" : {
        "host" : "gopher-blue",
        "port" : 27017,
        "version" : "3.2.0",
        "gitVersion" : "45d947729a0315accb6d4f15a6b06be6d9c19fe7"
    },
    "ok" : 1
}
> db.foo.find({a: 1}).hint({a: NaN})
{ "_id" : ObjectId("567730db95459c76838b7c76"), "a" : 1 }
> db.foo.find({a: {$in: [2, 1, 3]}}).hint({a: NaN}).explain()
{
    "queryPlanner" : {
        "plannerVersion" : 1,
        "namespace" : "test.foo",
        "indexFilterSet" : false,
        "parsedQuery" : {
            "a" : {
                "$in" : [
                    1,
                    2,
                    3
                ]
            }
        },
        "winningPlan" : {
            "stage" : "FETCH",
            "inputStage" : {
                "stage" : "IXSCAN",
                "keyPattern" : {
                    "a" : NaN
                },
                "indexName" : "a_NaN",
                "isMultiKey" : false,
                "isUnique" : false,
                "isSparse" : false,
                "isPartial" : false,
                "indexVersion" : 1,
                "direction" : "forward",
                "indexBounds" : {
                    "a" : [
                        "[3.0, 3.0]",
                        "[2.0, 2.0]",
                        "[1.0, 1.0]"
                    ]
                }
            }
        },
        "rejectedPlans" : [ ]
    },
    "serverInfo" : {
        "host" : "gopher-blue",
        "port" : 27017,
        "version" : "3.2.0",
        "gitVersion" : "45d947729a0315accb6d4f15a6b06be6d9c19fe7"
    },
    "ok" : 1
}

david.storch, should we apply (something like) the following change to make the index bounds builder consistent with the Ordering class, or should we disallow the creation of indexes with a key pattern using NaN?

diff --git a/src/mongo/db/query/index_bounds.cpp b/src/mongo/db/query/index_bounds.cpp
index 85708c6..678affd 100644
--- a/src/mongo/db/query/index_bounds.cpp
+++ b/src/mongo/db/query/index_bounds.cpp
@@ -323,7 +323,7 @@ bool IndexBounds::isValidFor(const BSONObj& keyPattern, int direction) {
 
         // Special indices are all inserted increasing.  elt.number() will return 0 if it's
         // not a number.  Special indices are strings, not numbers.
-        int expectedOrientation = direction * ((elt.number() >= 0) ? 1 : -1);
+        int expectedOrientation = direction * ((elt.number() < 0) ? -1 : 1);
 
         if (!field.isValidFor(expectedOrientation)) {
             return false;
@@ -343,7 +343,7 @@ IndexBoundsChecker::IndexBoundsChecker(const IndexBounds* bounds,
     : _bounds(bounds), _curInterval(bounds->fields.size(), 0) {
     BSONObjIterator it(keyPattern);
     while (it.more()) {
-        int indexDirection = it.next().number() >= 0 ? 1 : -1;
+        int indexDirection = it.next().number() < 0 ? -1 : 1;
         _expectedDirection.push_back(indexDirection * scanDirection);
     }
 }
diff --git a/src/mongo/db/query/index_bounds_builder.cpp b/src/mongo/db/query/index_bounds_builder.cpp
index 364f957..2fcef73 100644
--- a/src/mongo/db/query/index_bounds_builder.cpp
+++ b/src/mongo/db/query/index_bounds_builder.cpp
@@ -860,9 +860,11 @@ void IndexBoundsBuilder::alignBounds(IndexBounds* bounds, const BSONObj& kp, int
     size_t oilIdx = 0;
     while (it.more()) {
         BSONElement elt = it.next();
-        // The canonical check as to whether a key pattern element is "ascending" or "descending" is
-        // (elt.number() >= 0). This is defined by the Ordering class.
-        int direction = (elt.number() >= 0) ? 1 : -1;
+        // Match the behavior of the Ordering class when considering whether the direction of a key
+        // pattern element 'elt' is "ascending" or "descending". The Ordering class defines the
+        // direction to be "descending" if 'elt.number() < 0', and "ascending" otherwise. In
+        // particular, {field: NaN} is considered to be an ascending index on "field".
+        int direction = (elt.number() < 0) ? -1 : 1;
         direction *= scanDir;
         if (-1 == direction) {
             vector<Interval>& iv = bounds->fields[oilIdx].intervals;

Generated at Thu Feb 08 03:58:01 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.