/ Check-in [1f68c184]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Limit the depth of recursion for valid JSON in the JSON1 extension in order to avoid using excess stack space in the recursive descent parser. Fix for ticket [981329adeef51011052667a9].
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 1f68c184596912d742b50b1ca38252a9e783aacf121619a27b17a7ae9f6df041
User & Date: drh 2017-04-11 18:55:05
Context
2017-04-11
20:48
Avoid updating unaffected indexes on a table as part of an UPDATE that requires foreign key processing in some cases. check-in: 7aae5c0f user: dan tags: trunk
19:58
Avoid updating unaffected indexes on a table as part of an UPDATE that requires foreign key processing in some cases. Closed-Leaf check-in: 477bea9e user: dan tags: fkey-optimization
18:55
Limit the depth of recursion for valid JSON in the JSON1 extension in order to avoid using excess stack space in the recursive descent parser. Fix for ticket [981329adeef51011052667a9]. check-in: 1f68c184 user: drh tags: trunk
18:06
Smaller and faster implementation of exprMightBeIndexed(). check-in: 76cd611d user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/misc/json1.c.

    86     86   #define safe_isspace(x) (jsonIsSpace[(unsigned char)x])
    87     87   
    88     88   #ifndef SQLITE_AMALGAMATION
    89     89     /* Unsigned integer types.  These are already defined in the sqliteInt.h,
    90     90     ** but the definitions need to be repeated for separate compilation. */
    91     91     typedef sqlite3_uint64 u64;
    92     92     typedef unsigned int u32;
           93  +  typedef unsigned short int u16;
    93     94     typedef unsigned char u8;
    94     95   #endif
    95     96   
    96     97   /* Objects */
    97     98   typedef struct JsonString JsonString;
    98     99   typedef struct JsonNode JsonNode;
    99    100   typedef struct JsonParse JsonParse;
................................................................................
   165    166     u32 nNode;         /* Number of slots of aNode[] used */
   166    167     u32 nAlloc;        /* Number of slots of aNode[] allocated */
   167    168     JsonNode *aNode;   /* Array of nodes containing the parse */
   168    169     const char *zJson; /* Original JSON string */
   169    170     u32 *aUp;          /* Index of parent of each node */
   170    171     u8 oom;            /* Set to true if out of memory */
   171    172     u8 nErr;           /* Number of errors seen */
          173  +  u16 iDepth;        /* Nesting depth */
   172    174   };
   173    175   
          176  +/*
          177  +** Maximum nesting depth of JSON for this implementation.
          178  +**
          179  +** This limit is needed to avoid a stack overflow in the recursive
          180  +** descent parser.  A depth of 2000 is far deeper than any sane JSON
          181  +** should go.
          182  +*/
          183  +#define JSON_MAX_DEPTH  2000
          184  +
   174    185   /**************************************************************************
   175    186   ** Utility routines for dealing with JsonString objects
   176    187   **************************************************************************/
   177    188   
   178    189   /* Set the JsonString object to an empty string
   179    190   */
   180    191   static void jsonZero(JsonString *p){
................................................................................
   731    742     while( safe_isspace(z[i]) ){ i++; }
   732    743     if( (c = z[i])=='{' ){
   733    744       /* Parse object */
   734    745       iThis = jsonParseAddNode(pParse, JSON_OBJECT, 0, 0);
   735    746       if( iThis<0 ) return -1;
   736    747       for(j=i+1;;j++){
   737    748         while( safe_isspace(z[j]) ){ j++; }
          749  +      if( ++pParse->iDepth > JSON_MAX_DEPTH ) return -1;
   738    750         x = jsonParseValue(pParse, j);
   739    751         if( x<0 ){
          752  +        pParse->iDepth--;
   740    753           if( x==(-2) && pParse->nNode==(u32)iThis+1 ) return j+1;
   741    754           return -1;
   742    755         }
   743    756         if( pParse->oom ) return -1;
   744    757         pNode = &pParse->aNode[pParse->nNode-1];
   745    758         if( pNode->eType!=JSON_STRING ) return -1;
   746    759         pNode->jnFlags |= JNODE_LABEL;
   747    760         j = x;
   748    761         while( safe_isspace(z[j]) ){ j++; }
   749    762         if( z[j]!=':' ) return -1;
   750    763         j++;
   751    764         x = jsonParseValue(pParse, j);
          765  +      pParse->iDepth--;
   752    766         if( x<0 ) return -1;
   753    767         j = x;
   754    768         while( safe_isspace(z[j]) ){ j++; }
   755    769         c = z[j];
   756    770         if( c==',' ) continue;
   757    771         if( c!='}' ) return -1;
   758    772         break;
................................................................................
   761    775       return j+1;
   762    776     }else if( c=='[' ){
   763    777       /* Parse array */
   764    778       iThis = jsonParseAddNode(pParse, JSON_ARRAY, 0, 0);
   765    779       if( iThis<0 ) return -1;
   766    780       for(j=i+1;;j++){
   767    781         while( safe_isspace(z[j]) ){ j++; }
          782  +      if( ++pParse->iDepth > JSON_MAX_DEPTH ) return -1;
   768    783         x = jsonParseValue(pParse, j);
          784  +      pParse->iDepth--;
   769    785         if( x<0 ){
   770    786           if( x==(-3) && pParse->nNode==(u32)iThis+1 ) return j+1;
   771    787           return -1;
   772    788         }
   773    789         j = x;
   774    790         while( safe_isspace(z[j]) ){ j++; }
   775    791         c = z[j];
................................................................................
   881    897     int i;
   882    898     memset(pParse, 0, sizeof(*pParse));
   883    899     if( zJson==0 ) return 1;
   884    900     pParse->zJson = zJson;
   885    901     i = jsonParseValue(pParse, 0);
   886    902     if( pParse->oom ) i = -1;
   887    903     if( i>0 ){
          904  +    assert( pParse->iDepth==0 );
   888    905       while( safe_isspace(zJson[i]) ) i++;
   889    906       if( zJson[i] ) i = -1;
   890    907     }
   891    908     if( i<=0 ){
   892    909       if( pCtx!=0 ){
   893    910         if( pParse->oom ){
   894    911           sqlite3_result_error_nomem(pCtx);

Changes to test/json101.test.

   684    684   do_execsql_test json-10.94 {
   685    685     SELECT json_valid('" \} "');
   686    686   } {0}
   687    687   do_execsql_test json-10.95 {
   688    688     SELECT json_valid('" \~ "');
   689    689   } {0}
   690    690   
          691  +#--------------------------------------------------------------------------
          692  +# 2017-04-11.  https://www.sqlite.org/src/info/981329adeef51011
          693  +# Stack overflow on deeply nested JSON.
          694  +#
          695  +# The following tests confirm that deeply nested JSON is considered invalid.
          696  +#
          697  +do_execsql_test json-11.0 {
          698  +  /* Shallow enough to be parsed */
          699  +  SELECT json_valid(printf('%.2000c0%.2000c','[',']'));
          700  +} {1}
          701  +do_execsql_test json-11.1 {
          702  +  /* Too deep by one */
          703  +  SELECT json_valid(printf('%.2001c0%.2001c','[',']'));
          704  +} {0}
          705  +do_execsql_test json-11.2 {
          706  +  /* Shallow enough to be parsed { */
          707  +  SELECT json_valid(replace(printf('%.2000c0%.2000c','[','}'),'[','{"a":'));
          708  +  /* } */
          709  +} {1}
          710  +do_execsql_test json-11.3 {
          711  +  /* Too deep by one { */
          712  +  SELECT json_valid(replace(printf('%.2001c0%.2001c','[','}'),'[','{"a":'));
          713  +  /* } */
          714  +} {0}
   691    715   
   692    716   finish_test