Proposal - Linear Time Ruling

[TotalTechGeek]

Background

While we work to identify our error-handling strategy (which affects several proposals), I’d like to propose a restriction on recognized/default JSON Logic operators to strengthen the computational guarantees of the standard.

JSON Logic advertises the following:

deterministic computation time

This is a solid guarantee, but I believe we can provide a stronger one: "Linear Computation Time."

Fortunately, the operators defined by JSON Logic already appear to adhere to this guarantee.

I truly do not expect this to significantly change our course on anything we plan to do for Core, but might help explain JSON Logic's out of the box goals.

Proposal

I propose the following:

• All Core JSON Logic operators must be definable to run in linear time in their worst case, i.e., they must be ≤ Θ(n), where n is the size of the input provided to the operator.
• For an implementation to be recommended by the JSON Logic Organization, it MUST ONLY enable operators that can be defined to run in ≤ Θ(n) by default.
• The JSON Logic Organization may recognize Community Extensions with operators that run in > Θ(n). However, these operators MUST NOT be enabled by default and must be clearly documented as higher-complexity extensions.

Additionally:

• Algorithms with common implementations that exceed Θ(n), even if a linear-time implementation is theoretically possible, should be avoided (e.g., regex with catastrophic backtracking).

This is not an implementation mandate, as it would be fairly difficult to ensure that with tests alone. This is a guideline for TC and Community members to help with default operator selection.

Assumptions

• Arithmetic operations are treated as O(1) for computational purposes. This is a standard convention outside of designing arithmetic algorithms.

Motivation

JSON Logic advertises itself as a safe way to serialize and execute "logic" or "rules," even when the rules come from an untrusted source.

By imposing a restriction on default operators, we mitigate potential denial-of-service attacks and ensure consistent, predictable performance.

While developers are free to extend JSON Logic for their specific use cases (e.g., making JSON Logic Turing complete by adding while), I believe any default operators should adhere to the stronger guarantee of linear computation time.

[JTeeuwissen]

Even if not enabled by default, it should still be safe to use input from users in json logic when using e.g. sort or regex operators. Perhaps a global/per operator timeout is a better catch all approach to achieve this?

Additionally, should any space limits be enforced?

[TotalTechGeek]

Perhaps a global/per operator timeout is a better catch all approach to achieve this?

Personally, I'd strongly prefer to avoid this in Core / Community Extensions -- I'm worried it'd either incur heavy performance penalties (to make logic interruptable) or be rather architecturally complex.

This would add quite a hefty impl requirement I think.

I think it's a nice feature, but a heavy mandate...

it should still be safe to use input from users in json logic when using e.g. sort or regex operators

Tbh, sort likely would be fine. Maybe in the future we could relax the restriction.

regex really SHOULD BE fine, it SHOULD be able to run in linear time, but I think if we add a regex / pattern operator, most folks will implement their languages built-in mechanism for it, and end up with exponential time attacks.

I think it'd be hard to enforce the regex thing, unless we had test cases built into our suite that we knew would trip up the common impls.

[TotalTechGeek]

Re: Space Limits

Do you have any thoughts on this? I think for Core, constant space should work?

[TotalTechGeek]

@JTeeuwissen I'd be open to a Community Extension like { "timeout": [expr, time] }

In my implementation, it'd probably move the work into a worker that it can terminate.

I think I'd prefer this as an extension though, and not in Core.

[JTeeuwissen]

@JTeeuwissen I'd be open to a Community Extension like { "timeout": [expr, time] }

Wouldn't work if the json logic itself is provided by users (without modifying it, that is)

Do you have any thoughts on this? I think for Core, constant space should work?

I guess it would come down to permissible operators as well. Anything like a range to list operator would go out the window.
Additionally, perhaps a configurable json complexity limit (like those used for graphql query validation) would be useful, to avoid large inputs.

[TotalTechGeek]

Wouldn't work if the json logic itself is provided by users (without modifying it, that is)

Right, which is why if you do want to timebox it, you'd wrap it, or specify something on the runner (which would likely wrap it).

Additionally, perhaps a configurable json complexity limit (like those used for graphql query validation) would be useful

I think this is stretching this concept a bit past my intentions / the scope of this proposal.

It's related... but I feel this is a simple guideline for TC members to follow for deciding which operators are on the table for default inclusion.

[gregsdennis]

This really feels like an implementation detail to me and shouldn't be part of the spec. What happens when an implementation can't meet this requirement due to some language/framework limitation? Do we say that that language simply cannot support JSON Logic, even though the processing works, just more slowly?

[TotalTechGeek]

To clarify: this isn't meant to be a performance or implementation guideline, and may not even appear in the specification.

This is not an implementation mandate.

This is meant to be a guideline for TC and Org members to help us decide which operators we should include in JSON Logic out of the box, to help mitigate denial-of-service attacks when logic is delivered from an untrusted source.

[TotalTechGeek]

I can clarify that in the proposal -- that it's mostly a guideline for operator selection and what we enable by default to help protect developers who adopt the technology.

Edit I've amended my proposal to clarify this.

[codetiger]

If this is a guideline for the TC and not for implementation developers, then it perfectly makes sense. Otherwise I initially felt, some programming languages and frameworks will have a hard time to implement.

[TotalTechGeek]

Hey, is the thumbs up / the "makes sense" a positive vote? (I don't want to assume)

[TotalTechGeek]

Current Votes

Aggregate	TC Votes in Favor	Votes
1	1	@TotalTechGeek (+1)

Here is a link to our voting procedures