Proposal - Making JSON Logic Safe

[TotalTechGeek]

Background

Hey folks! It's been a while!

I've had some time to think, and I believe I stumbled across some issues with the JSON Logic Specification that undermines its goals.

The goals of JSON Logic, shared from the first section of its website -- https://jsonlogic.com/:

• share logic between front-end and back-end code

• Secure.

• JsonLogic has no setters, no loops, no functions or gotos. One rule leads to one decision, with no side effects and deterministic computation time.

More recently, we had a discussion about how operators needed to be definable in such a way where they could run in Linear Time (while we did not harden it to require linear time execution).

See: https://github.com/orgs/json-logic/discussions/24

The Flaws

I believe that the iterators in JSON Logic open vulnerabilities in contexts where the rules come from an untrusted source,

I've stumbled across two types of issues, and I believe they should be fairly "simple" to mitigate. Both of these rules crash every implementation I've tested against.

The first classification of issue is one that allows for exponential growth in data, which could lead to DOS in either memory or compute, if the output were passed into another operator.

Exponential Growth in Reduce

Here is such a rule that should be compatible with every implementation of JSON Logic.

{
    "reduce": [
        [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
        {
            "merge": [
                { "var": "accumulator" },
                { "var": "accumulator" },
                { "var": "accumulator" },
                { "var": "accumulator" },
                { "var": "accumulator" },
                { "var": "accumulator" },
                { "var": "current"     }
            ]
        },
        []
    ]
}

Because the accumulator is able to self-reference between executions and be used multiple times, you end up with exponential growth during the iterations (recursive expansion).

Nested Outer Iterator Increase The Degree of Time Complexity

The second classification is more obvious, and one I believe folks were more generally aware of,

{
 "map": [
  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
  {
   "map": [
    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
    {
     "map": [
      [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
      {
       "map": [
        [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
        {
         "map": [
          [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
          {
           "map": [
            [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
            {
             "map": [
              [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
              {
               "map": [
                [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
                {
                 "map": [ [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 0 ]
                }
               ]
              }
             ]
            }
           ]
          }
         ]
        }
       ]
      }
     ]
    }
   ]
  }
 ]
}

By nesting iterator statements in the outer expression, each nested iterator can increase the time complexity another degree, (n^1 becomes n^2 becomes n^3 ...).

This can also be used to create a denial of service from compute.

My Take

I believe that it should be a goal of the JSON Logic project to provide a safe runtime to users, even if the rules come from an untrusted source, and that Core operators should be defined with reasonable constraints to protect that safety for users out of the box.

However, with JSON Logic being a powerful AST, I believe we should recommend that implementations provide configurabilty for some of these constraints for trusted contexts.

Recommendations

I think we should aim to keep the changes relatively simple and straightforward, where possible. They also need to be compatible with previously approved tests.

So:

• reduce MUST throw if array / object is used as either a defaultValue or returned from the expression.

My recommendation for implementations is to make this configurable, but out of the box this should be disabled to mitigate exponential growth.

This allows reduce to be used to aggregate scalar values (and strings) while not allowing it to aggregate complex structures by default.

I feel like most real-world use-cases that would need to generate structures in reduce in an untrusted context in linear time could be managed with { merge: { map: [...] } }

I feel this constraint helps mitigate other weird attacks where people could make awkwardly nested data structures to avoid the other constraints described below.

• maxStringLength should be a specified configuration setting.
• maxArrayLength should be a specified configuration setting.
• cat must honor maxStringLength and throw where applicable.
• merge must honor maxArrayLength and throw where applicable
• All iterators must check maxArrayLength prior to iterating.
• maxIteratorDepth should be a specified configuration setting, with a default of 0.
• The outer expression / "body" of an iterator should increase the depth.
• Iterators should throw when they are executed beyond their allowed depth.

Note that depth is only increased in the body of the iterator, for example, you can still do { map: [{ filter: ... }, ...] }

[dslmeinte]

My thoughts:

• I think it's probably doable to determine statically what the algorithmic complexity of a given rule is, with “mild” assumptions on the input data. That way, operators don't need to be restricted (as proposed above for reduce) but a runtime could choose to not run a rule with excessive complexity.
• Making the runtime configurable adds unexpected complexity/variability — unexpected in the sense that bonafide rule providers would need to know whether the targeted runtime implements the restrictions you propose.
• Nevertheless, the max*{Length|Depth} constraints/setting described above look like a good idea, if only to make it explicit for a given runtime what the effective/practical limits are. In other words: a runtime {c|sh}ould state its max*{Length|Depth} parameters upfront.

[TotalTechGeek]

probably doable to determine statically what the algorithmic complexity of a given rule

I'm not so certain, especially as custom operators get introduced and w/ "lazy evaluation" being a thing.

Plus, the reduce example runs in linear time, but grows the array exponentially.

Thus if I did a map(reduce(...), ...) that would likely measure as linear, but have an exponential input passed ino the map, though the maxLength would potentially mitigate that issue.

The reason I'm being aggressive with reduce in spite of those additional checks is because I'm afraid that someone could concoct some sort of weird nested array in the reducer that can still grow the accumulator exponentially, while avoiding the simple checks, which means that it'd need some sort of recursive size analyzer to mitigate that behavior.

There are alternative approaches I could entertain though, like instead of forbidding arrays and objects, maybe instead mandating a max depth on the data structures it produces by default.

Making the runtime configurable adds unexpected complexity/variability

Full agreement on this.

I don't like adding complexity / ecosystem fragmentation, but I want to try to prioritize out-of-the-box safety for untrusted sources of rules.

[TotalTechGeek]

As discussed before, I'm open to the JSON Logic Organization recommending certain profiles, I'd like the default profile to be safe for untrusted contexts and mitigate denial-of-service attacks, but we could also promote a "Trusted" profile which allows for nesting & recursive accumulators and all the things that would make it generally useful as an AST 😄 .

I dunno -- I'm definitely open to input.

I feel this setup / some variant of it would well for securing the core JSON Logic operators, and I believe folks could incorporate these parameters into their operators, but I question if a different constraint should also (or alternatively) be considered along the lines of maxIterations, which would terminate the rule's execution if the number of iterations in the rule exceeds that count. (The main thing I dislike about the rule is that it essentially keeps track of state that isn't local to the operator)

[TotalTechGeek]

One nice thing about maxIterations is that it could help safeguard some of my side-projects like handlebars-jle...

{{#each this}}
{{#each ../this}}
- X
{{#each ../../this}}
- Y
{{#each ../../../this}}
- Z
{{#each ../../../../this}}
- A
{{#each ../../../../../this}}
- B
{{#each ../../../../../../this}}
- C
{{/each}}
{{/each}}
{{/each}}
{{/each}}
{{/each}}
{{/each}}
{{/each}}

It seems like some people sandbox this by opening a separate worker thread & timing it out though

[rmannibucau]

I have a few use cases where I do trigger the exec in a thread pool and awaits it with a timeout and kills the thread if not done (same spirit in java I think), but it is closer to bulkhead pattern and related libs than something which should be built-in,
also the decorator solution sounds nice since it can validate dynamic ".." and the static one can kill most of them before the exec so i'd rather go that way for built-in security, ie enabling decorators in jsonlogic (and code but this can't be specified). The decorator can have a limited syntax but enable to failfast.

[rmannibucau]

Here a few inputs (food for thoughts):

• max string/items length is mainly a JSON parser thing, as soon as it is loaded in mem - and json logic can't use streaming, then memory is used so adding similar limitations to jsonlogic is mainly about runtime and reducers but i'm not sure about the security it brings since you should validate the ast before the runtime if you fear unsecure code and JSON logic is well designed to do that without these new constraints no?
• cat, merge, etc (any operator) can have more precise sanity checks but it becomes operator specific in the operator config object which could be a standard like in react for ex, (some cat having different limitations in a push down mode for ex)
• for me it is not safe to add these validations since you can still have denial of services, what is safe in JSONLogic is the hability to have a trivial ast to visit and validate it a) upfront and b) decorate any operator to add such validations easily in a runtime
• it would be a regression functionally to not be able to have infinite loops for ex - I do use it to define no-code runtimes for ex (consumming kafka messages etc)

I do not think the max length limitation is bad, more than it should move to the specific operator configuration and stay unrelated to the security as it is when you code in any language since once "compiled"/interpreted, JSON-Logic is a runtime as any language.

As a summary security doesn't really comes from limiting the runtime but 1) ensuring it can be validated upfront and 2) at runtime as an harnessing and complement.
So I do not think the safety is that justifiable for these features.

[TotalTechGeek]

JSON Logic is already iteration safe since it is based on arrays, so fixed

But you can nest iterators and easily get to 1e9 iterations (or significantly higher with little effort); and with "lazy traversal" of operators, it can be difficult to evaluate statically, especially with custom ops. (You could try to ignore laziness traversal rules for static analysis, but that can get tricky, especially depending on how the operator is designed).

The pieces of logic I defined above crashed every implementation I tested against (though it was only about 10).

does it belong to the spec

We're on the same page here, it does not belong in the "specification", it should be implementation owned.

not sure specifying it will make it more secure since if you have a stream/iterator notion you will just ignore that validation or still do a vendor/language specific solution no?

I'm thinking it would be a implementation solution where you could specify "I want to put a cap on iterations -- 8K at most."

And throw if the iterators go beyond that (shared count). That kind of a thing.

[TotalTechGeek]

log, will break your log output easily so you end up being blind in your observability stack - or miss some key data - i tend to override it to use an actual logger even if not aligned on the original "spec".

Side note: Yeah, I think I want to leave "log" out of core :P

I don't think it's even in tests.json

[rmannibucau]

I'm thinking it would be a implementation solution where you could specify "I want to put a cap on iterations -- 8K at most."

Current strategies are mainly (I think):

• timeout (bulkhead like)
• sandbox memory to limit it (not sure it can be done in all languages but in several you can)

If you can combine both you do not care much about any limitation on the complexity, no?

So an appendix with try that or that else provide this sounds good to me. Can be a "vendor/implementation advices" optional section.

[dslmeinte]

You might want to warn authors of rules upfront that their rule has (possibly) unreasonable algorithmic complexity, though.

[rmannibucau]

@dslmeinte exactly, this was one of my two points in https://github.com/orgs/json-logic/discussions/39#discussioncomment-14786454, the thing is upfront also means statically so outside the runtime and purely in some tooling (I see it fitting well in your beloved editor for ex). I'm also pretty sure it will fit quite well LLM to guide the writer. Having the validation embeddable is possible but depends the use case and library I'd say - exactly like JSON-Schema, we are on the same kind of solution, ie validation, offline or at runtime.
So documentation sounds like the best deliverable for that issue IMHO.

[dslmeinte]

@TotalTechGeek Do you mean to impose maxIterationsDepth purely as a runtime constraint, or purely as a static constraint, or both?

If I had more time I'd be tempted to write a type system of sorts for evaluating the algorithmic complexity of a JSONLogic expression.