Stack overflow in debug build when translating policy cedar->json

[cdisselkoen]

Before opening, please confirm:

• I have searched for duplicate or closed issues.
• I have read the guide for submitting bug reports.
• I have done my best to include a minimal, self-contained set of instructions for consistently reproducing the issue.

Bug Category

Other

Describe the bug

There is a stack overflow in the debug build when translating a large enough policy from Cedar format to JSON format. The size of policy needed to trigger this is large but not obscenely large, enough that this is probably worth fixing. The stack overflow doesn't happen in the release build though, so this is a low priority.

Expected behavior

No stack overflow. Either an error or, ideally, a correct JSON result.

Reproduction steps

1. I reproduced this using cedar commit dd6b9f0 (latest main as of this writing)
2. cd cedar-policy-cli
3. Copy the following to a file problem.cedar:

permit ( principal == User::"bob", action == Action::"view", resource ) when { action == Action::"view"+002+-0*-0+000000+0-00000000+00000+0-0+-0+000+0-0+0-00000000+0000+00000+0-0*-0+000000000000+00000+0-0+-0+000+0-0+0-0000006600+000000+0-0+002+-0*-0+000000+0-00000615+00000+0-0+-0+000+0-0+0-00000000+0000+00000+0-0*-0+000000000000+00000+0-0+-0+000+0-0+0-000000662*-002+-0+000000+000000+0-0+002+-0*-0+000000+0-00000000+00000+0-0+-0+-0+002+-0*-0+000000+0-00000000+00000+0-0+-0+0+0000+00000+0-0*-0+000000000000+00000+0-0+-0+000+0-0+0-0000006600+000000+0-0+002+-0*-0+000000+0-00000000+00000+0-0+-0+000+0-0+0-00000000+0000+00000+0-0*-0+000000000000+00000+0-0+-0+000+0-0+0-000000662*-002+-0+000000+0-0+002+-0*-0+000000+0-00000000+00000+0-0+-0+-0+002+-0*-0+000000+0-00000000+00000+0-0+-0+000+0-0+0-00000000+0000+00000+0-0*-0+000000000000+00000+0-0+-0+000+0-0+0-000000662*-002+-0+000000+0-0+002+-0*-0+000000+0-00000000+00000+0-0+-0+0-000+00000+0-0+-0+000+0-0+0-00000000+0000+00000+0-0*-0+000000000000+00000+0-0+-0+000+0-0+0-0+000+0-0+0-000000662*-002+-0+000000+0-0+002+-0*-0+000000+0-00000000+000+-0+000000+0-0+002+-0*-0+000000+0-00000000+00000+0-0+-0+000+0-0+0-000+00000+0-0+-0+000+0-0+0-0000000+0-0+0-00000000+0000+00000+0-0*-0+000000000000+00000+0-0+-0+000+0-0+0-000000662*-002+-0+000000+0-0+002+-0*-0+000000+0-00000000+00000+0-0+-0+0-000+00000+0-0+-0+000+0-0+0-00000000+0000+00000+0-0*-0+000000000000+00000+0-0+-0+000+0-0+0-000000662*-002+-0+000000+0-0+002+-0*-0+000000+0-00000000+000+-0+000000+0-0+002+-0*-0+000000+0-00000000+00000+0-0+-0+000+0-0+0-000+00000+0-0+-0+000+0-0+0-00000000+0000+00000+0-0*-0+000000000000+00000+0-0+-0+000+0-0+0-000000662*-002+-0+000000+0-0+002+-0*-0+000000+0-00000000+00000+0-0+-0+00000+0-0+0-000+0-000000662*-002+-0+000000+0-0+002+-0*-0+000000+0-00000000+00000+0-0+-0+00000+0-0+0-0000000+0-0+0-00000000+0000+00000+0-0*-0+000000000000+00000+0-0+-0+000+0-0+0-000000662*-002+-0+000000+0-0+002+-0*-0+000000+0-00000000+00000+-000000662*-002+-0+000000+0-0+002+-0*-0+000000+0-00000000+000+-0+000000+0-0+002+-0*-0+000000+0-00000000+00000+0-0+-0+000+0-0+0-000+00000+0-0+-0+000+0-0+0-0000000+0-0+0-00000000+0000+00000+0-0*-0+000000000000+00000+0-0+-0+000+0-0+0-000000662*-002+-0+000000+0-0+002+-0*-0+000000+0-00000000+00000+0-0+-0+0-000+00000+0-0+-0+000+0-0+0-00000000+0000+00000+0-0*-0+000000000000+00000+0-0+-0+000+0-0+0-000000662*-002+-0+000000+0-0+002+-0*-0+000000+0-00000000+000+-0+000000+0-0+002+-0*-0+000000+0-00000000+00000+0-0+-0+000+0-0+0-000+00000+0-0+-0+000+0-0+0-00000000+0000+00000+0-0*-0+000000000000+00000+0-0+-0+000+0-0+0-000000662*-002+-0+000000+0-0+002+-0*-0+000000+0-00000000+00000+0-0+-0+00000+0-0+0-0000000+0-0+0-00000000+0000+00000+0-0*-0+000000000000+00000+0-0+-0+000+0-0+0-000000662*-002+-0+000000+0-0+002+-0*-0+000000+0-00000000+00000+0-0+-0+0-000+00000+0-0+-0+000+0-0+0-00000000+0000+00000+0-0*-0+000000000000+00000+0-0+-0+000+0-0+0-000000662*-002+-0+000000+0-0+002+-0*-0+000000+0-00000000+000+-0+000000+00+0-0+0000+00000+0-0+-0+000+0-0+0-000000662*-002+-0+000000+0--5*-0+000000+0-00000000+00000+0-0+-0+-0+002+-0*-0+000000+0-00000000+00000+0-0+-0+000+0-0+0-000+0-0+0-00000000+0000+000+0-0*-0+000000000000+00000+0-0+0000+00000+0-0+-0+000+0-0+0-000000662*-002+-0+000000+0--5*-0+000000+0-00000000+00000+0-0+-0+-0+002+-0*-0+000000+0-00000000+00000+0-0+-0+000+0-0+0-000 };

4. `cargo run -- translate-policy --direction cedar-to-json -p problem.cedar`

Note that the problem doesn't reproduce if you add --release to the cargo run command, which is why this is low priority

Code Snippet

No response

Log output

No response

Additional configuration

No response

Operating System

No response

Additional information and screenshots

No response

[cdisselkoen]

The overflow is during CST->EST translation, specifically TryFrom<&Node<Option<cst::Mult>>> for Expr and friends, which mutually recurse a lot on this particular policy

[cdisselkoen]

Some possible refactors to reduce stack usage would rely on the optimizer; for instance, trying to create opportunities for tail-call optimization. But the optimizer only really runs on release builds. I'm now questioning whether it's worth trying to avoid stack overflows on policies like this in debug builds. Perhaps it only makes sense to worry about release builds.

[john-h-kastner-aws]

I there a reason why this overflows for CST->EST but not CST->AST? It feels like these should have the same structure

[cdisselkoen]

Maybe it does overflow for CST->AST as well, but this particular operation doesn't construct an AST, or tries to construct an EST first?

[john-h-kastner-aws]

cargo run --check-parse < problem.cedar doesn't error

[john-h-kastner-aws]

backtrace from gdb suggests the overflow happens while serializing to json with serde

#0  0x000055555678f5e7 in alloc::slice::hack::to_vec (s=...) at /rustc/f6e511eec7342f59a25f7c0534f1dbea00d01b14/library/alloc/src/slice.rs:110
#1  alloc::slice::<impl [T]>::to_vec_in (self=...) at /rustc/f6e511eec7342f59a25f7c0534f1dbea00d01b14/library/alloc/src/slice.rs:477
#2  alloc::slice::<impl [T]>::to_vec (self=...) at /rustc/f6e511eec7342f59a25f7c0534f1dbea00d01b14/library/alloc/src/slice.rs:452
#3  alloc::slice::<impl alloc::borrow::ToOwned for [T]>::to_owned (self=...) at /rustc/f6e511eec7342f59a25f7c0534f1dbea00d01b14/library/alloc/src/slice.rs:859
#4  alloc::str::<impl alloc::borrow::ToOwned for str>::to_owned (self=...) at /rustc/f6e511eec7342f59a25f7c0534f1dbea00d01b14/library/alloc/src/str.rs:210
#5  <alloc::string::String as core::convert::From<&str>>::from (s=...) at /rustc/f6e511eec7342f59a25f7c0534f1dbea00d01b14/library/alloc/src/string.rs:2758
#6  0x0000555556773ae4 in <serde_json::value::ser::Serializer as serde::ser::Serializer>::serialize_struct_variant (_name=..., _variant_index=15, variant=..., _len=2) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde_json-1.0.133/src/value/ser.rs:289
#7  0x0000555555b42320 in cedar_policy_core::est::expr::_::<impl serde::ser::Serialize for cedar_policy_core::est::expr::ExprNoExt>::serialize (self=0x555557163150, __serializer=...) at cedar-policy-core/src/est/expr.rs:162
#8  0x0000555555b3e62f in cedar_policy_core::est::expr::_::<impl serde::ser::Serialize for cedar_policy_core::est::expr::Expr>::serialize (self=0x555557163150, __serializer=...) at cedar-policy-core/src/est/expr.rs:41
#9  0x0000555555b24269 in serde::ser::impls::<impl serde::ser::Serialize for alloc::sync::Arc<T>>::serialize (self=0x5555571631f8, serializer=...) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde-1.0.215/src/ser/impls.rs:521
#10 0x0000555555b241e9 in serde::ser::impls::<impl serde::ser::Serialize for &T>::serialize (self=0x7fffff602be0, serializer=...) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde-1.0.215/src/ser/impls.rs:521
#11 0x0000555555b7bc4f in serde_json::value::to_value (value=0x5555571631f8) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde_json-1.0.133/src/value/mod.rs:992
#12 0x0000555555b1df65 in <serde_json::value::ser::SerializeStructVariant as serde::ser::SerializeStructVariant>::serialize_field (self=0x7fffff604920, key=..., value=0x5555571631f8) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde_json-1.0.133/src/value/ser.rs:704
#13 0x0000555555b4203b in cedar_policy_core::est::expr::_::<impl serde::ser::Serialize for cedar_policy_core::est::expr::ExprNoExt>::serialize (self=0x5555571631f0, __serializer=...) at cedar-policy-core/src/est/expr.rs:162
#14 0x0000555555b3e62f in cedar_policy_core::est::expr::_::<impl serde::ser::Serialize for cedar_policy_core::est::expr::Expr>::serialize (self=0x5555571631f0, __serializer=...) at cedar-policy-core/src/est/expr.rs:41
#15 0x0000555555b24269 in serde::ser::impls::<impl serde::ser::Serialize for alloc::sync::Arc<T>>::serialize (self=0x555557163298, serializer=...) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde-1.0.215/src/ser/impls.rs:521
#16 0x0000555555b241e9 in serde::ser::impls::<impl serde::ser::Serialize for &T>::serialize (self=0x7fffff606790, serializer=...) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde-1.0.215/src/ser/impls.rs:521
#17 0x0000555555b7bc4f in serde_json::value::to_value (value=0x555557163298) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde_json-1.0.133/src/value/mod.rs:992
#18 0x0000555555b1df65 in <serde_json::value::ser::SerializeStructVariant as serde::ser::SerializeStructVariant>::serialize_field (self=0x7fffff6084d0, key=..., value=0x555557163298) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde_json-1.0.133/src/value/ser.rs:704
#19 0x0000555555b4203b in cedar_policy_core::est::expr::_::<impl serde::ser::Serialize for cedar_policy_core::est::expr::ExprNoExt>::serialize (self=0x555557163290, __serializer=...) at cedar-policy-core/src/est/expr.rs:162
#20 0x0000555555b3e62f in cedar_policy_core::est::expr::_::<impl serde::ser::Serialize for cedar_policy_core::est::expr::Expr>::serialize (self=0x555557163290, __serializer=...) at cedar-policy-core/src/est/expr.rs:41
#21 0x0000555555b24269 in serde::ser::impls::<impl serde::ser::Serialize for alloc::sync::Arc<T>>::serialize (self=0x555557163338, serializer=...) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde-1.0.215/src/ser/impls.rs:521
#22 0x0000555555b241e9 in serde::ser::impls::<impl serde::ser::Serialize for &T>::serialize (self=0x7fffff60a340, serializer=...) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde-1.0.215/src/ser/impls.rs:521
#23 0x0000555555b7bc4f in serde_json::value::to_value (value=0x555557163338) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde_json-1.0.133/src/value/mod.rs:992
#24 0x0000555555b1df65 in <serde_json::value::ser::SerializeStructVariant as serde::ser::SerializeStructVariant>::serialize_field (self=0x7fffff60c080, key=..., value=0x555557163338) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde_json-1.0.133/src/value/ser.rs:704
#25 0x0000555555b4203b in cedar_policy_core::est::expr::_::<impl serde::ser::Serialize for cedar_policy_core::est::expr::ExprNoExt>::serialize (self=0x555557163330, __serializer=...) at cedar-policy-core/src/est/expr.rs:162

....

#4140 0x0000555555b1feb0 in serde::ser::SerializeMap::serialize_entry (self=0x7fffffffbab0, key=0x7fffffffb880, value=0x7fffffffb888) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde-1.0.215/src/ser/mod.rs:1817
#4141 0x0000555555ba7543 in serde::ser::Serializer::collect_map::{{closure}} () at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde-1.0.215/src/ser/mod.rs:1326
#4142 0x0000555555b0f189 in core::iter::traits::iterator::Iterator::try_for_each::call::{{closure}} (x=...) at /rustc/f6e511eec7342f59a25f7c0534f1dbea00d01b14/library/core/src/iter/traits/iterator.rs:2464
#4143 0x0000555555b387dc in core::iter::adapters::map::map_try_fold::{{closure}} (acc=(), elt=...) at /rustc/f6e511eec7342f59a25f7c0534f1dbea00d01b14/library/core/src/iter/adapters/map.rs:95
#4144 0x0000555555b73f1b in core::iter::traits::iterator::Iterator::try_fold (self=0x7fffffffba88, init=(), f=...) at /rustc/f6e511eec7342f59a25f7c0534f1dbea00d01b14/library/core/src/iter/traits/iterator.rs:2405
#4145 0x0000555555b34350 in <core::iter::adapters::map::Map<I,F> as core::iter::traits::iterator::Iterator>::try_fold (self=0x7fffffffba88, init=(), g=...) at /rustc/f6e511eec7342f59a25f7c0534f1dbea00d01b14/library/core/src/iter/adapters/map.rs:121
#4146 0x0000555555b355d4 in core::iter::traits::iterator::Iterator::try_for_each (self=0x7fffffffba88, f=...) at /rustc/f6e511eec7342f59a25f7c0534f1dbea00d01b14/library/core/src/iter/traits/iterator.rs:2467
#4147 0x0000555555b1ecd6 in serde::ser::Serializer::collect_map (self=..., iter=...) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde-1.0.215/src/ser/mod.rs:1326
#4148 0x0000555555b70737 in serde_with::ser::impls::<impl serde_with::ser::SerializeAs<std::collections::hash::map::HashMap<K,V,H>> for std::collections::hash::map::HashMap<KU,VU,H>>::serialize_as (source=0x7fffffffc6b8, serializer=...)
    at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde_with-3.11.0/src/ser/impls.rs:381
#4149 0x0000555555bf4e16 in serde_with::ser::duplicates::<impl serde_with::ser::SerializeAs<std::collections::hash::map::HashMap<K,V,H>> for serde_with::MapPreventDuplicates<KAs,VAs>>::serialize_as (value=0x7fffffffc6b8, serializer=...)
    at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde_with-3.11.0/src/ser/duplicates.rs:55
#4150 0x0000555555bf4f16 in serde_with::ser::<impl serde_with::As<T>>::serialize (value=0x7fffffffc6b8, serializer=...) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde_with-3.11.0/src/ser/mod.rs:173
#4151 0x0000555555b5ab69 in <cedar_policy_core::est::policy_set::_::<impl serde::ser::Serialize for cedar_policy_core::est::policy_set::PolicySet>::serialize::__SerializeWith as serde::ser::Serialize>::serialize (self=0x7fffffffc1e0, __s=...) at cedar-policy-core/src/est/policy_set.rs:27
#4152 0x0000555555b5b7c9 in serde::ser::impls::<impl serde::ser::Serialize for &T>::serialize (self=0x7fffffffbd90, serializer=...) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde-1.0.215/src/ser/impls.rs:521
#4153 0x0000555555b7bb5f in serde_json::value::to_value (value=0x7fffffffc1e0) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde_json-1.0.133/src/value/mod.rs:992
#4154 0x0000555555b231e4 in <serde_json::value::ser::SerializeMap as serde::ser::SerializeMap>::serialize_value (self=0x7fffffffc040, value=0x7fffffffc1e0) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde_json-1.0.133/src/value/ser.rs:427
#4155 0x0000555555b1fb37 in serde::ser::SerializeMap::serialize_entry (self=0x7fffffffc040, key=..., value=0x7fffffffc1e0) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde-1.0.215/src/ser/mod.rs:1817
#4156 0x0000555555b238fe in <serde_json::value::ser::SerializeMap as serde::ser::SerializeStruct>::serialize_field (self=0x7fffffffc040, key=..., value=0x7fffffffc1e0) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde_json-1.0.133/src/value/ser.rs:659
#4157 0x0000555555b582b3 in cedar_policy_core::est::policy_set::_::<impl serde::ser::Serialize for cedar_policy_core::est::policy_set::PolicySet>::serialize (self=0x7fffffffc670, __serializer=...) at cedar-policy-core/src/est/policy_set.rs:28
#4158 0x0000555555b7b72a in serde_json::value::to_value (value=...) at /home/jkastner/.cargo/registry/src/index.crates.io-6f17d22bba15001f/serde_json-1.0.133/src/value/mod.rs:992
#4159 0x0000555555ae3e31 in cedar_policy::api::PolicySet::to_json (self=...) at cedar-policy/src/api.rs:2051
#4160 0x00005555555ab6d5 in cedar_policy_cli::translate_policy_to_json (cedar_src=...) at cedar-policy-cli/src/lib.rs:903
#4161 0x00005555555a1eef in core::ops::function::FnOnce::call_once () at /rustc/f6e511eec7342f59a25f7c0534f1dbea00d01b14/library/core/src/ops/function.rs:250
#4162 0x00005555555cc88c in core::result::Result<T,E>::and_then (self=..., op=0x7fffffffd9e000) at /rustc/f6e511eec7342f59a25f7c0534f1dbea00d01b14/library/core/src/result.rs:1346
#4163 0x000055555558b289 in cedar_policy_cli::translate_policy_inner (args=0x7fffffffd9e0) at cedar-policy-cli/src/lib.rs:911
#4164 0x000055555558b2bc in cedar_policy_cli::translate_policy (args=0x7fffffffd9e0) at cedar-policy-cli/src/lib.rs:915
#4165 0x000055555557f7ad in cedar::main () at cedar-policy-cli/src/main.rs:56

[cdisselkoen]

Doh, I made a stupid mistake in my own analysis. Upon further investigation I agree that's the cause haha

[cdisselkoen]

Does that mean this issue is out of scope then? Is the problem with serde itself (or serde_json), or with our usage of it? If the problem is just that debug builds of serde / serde_json require a lot of stack space to handle deeply nested JSON objects, that's probably just something we should accept

[john-h-kastner-aws]

Probably out of scope in this case. I'm not sure what we could do other than making the EST shallower, which we wouldn't want to do.

Does our nightly testing run the debug build? I would think it using a release build and this stack overflow was found by it, so we can't entirely write this off just because it's hard to reproduce in the release build.

[john-h-kastner-aws]

I found that serde_json by default enforces a recursion limit of 128 when deserializing.

https://github.com/serde-rs/json/blob/0903de449c52c1b4a2271e909b7afb18909dc379/src/de.rs#L57

To me this suggests two things:

1. If serde_json guards against stack overflow when deserializing, then it should be within the scope of serde_json to apply a similar guard when serializing, so this stack overflow should ideally be fixed in serde_json by adding a recursion guard causing an Err result instead of an overflow.
2. Our current JSON parers will error on structures nested more than 128 levels, which gives us an upper limit for the size of policies we should be able to support. On anything larger than this, a stack overflow would be acceptable (albeit less ideal than an Err) because we couldn't deserialize it anyways.