Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Policies with too high nesting depth are not rejected: It is possible to create small inputs that cause extreme memory usage (in practice: OOM kill or std::bad_alloc) #7

Open
practicalswift opened this issue Aug 29, 2019 · 1 comment
Open

Policies with too high nesting depth are not rejected: It is possible to create small inputs that cause extreme memory usage (in practice: OOM kill or std::bad_alloc) #7

practicalswift opened this issue Aug 29, 2019 · 1 comment

Comments

@practicalswift
Copy link
Contributor

practicalswift commented Aug 29, 2019 •
edited
Loading

Policies with too high nesting depth are not rejected: It is possible to create small inputs that cause extreme memory usage (in reality: OOM) and long running time.

The ./threshold.py 9 example below is 252 bytes and causes a memory consumption of 18.5 GB RAM and a running time of more than ten minutes.

The ./threshold.py 10 example below is 280 bytes will hit OOM on most systems before having a chance to finish.

The following script can be used to construct pathological inputs based on nested thresh:

#!/usr/bin/env python3

import sys


def main():
    if len(sys.argv) != 2:
        print("Usage: {} <number-of-nested-thresholds>".format(sys.argv[0]))
        sys.exit(0)

    N_DEPTH = int(sys.argv[1])
    assert N_DEPTH >= 1

    N_PK = 3
    assert N_PK >= 1

    s = None
    for _ in range(N_DEPTH):
        s = "thresh(1," + ",".join(N_PK * ["pk(H)"]) + ("," + s if s else "") + ")"
    print(s)


if __name__ == "__main__":
    main()

Example runs with varying levels of nesting:

$ ./threshold.py 1 > input
$ wc -c input
28 input
$ cat input
thresh(1,pk(H),pk(H),pk(H))
$ \time ./miniscript < input
X    179.0000000000   105 thresh_m(1,H,H,H) thresh(1,pk(H),pk(H),pk(H))
0.00user 0.00system 0:00.00elapsed 66%CPU (0avgtext+0avgdata 3644maxresident)k
0inputs+0outputs (0major+142minor)pagefaults 0swaps

$ ./threshold.py 2 > input
$ wc -c input
56 input
$ cat input
thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H)))
$ \time ./miniscript < input
X    263.1250000000   170 c:or_i(pk(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),pk_h(H)))))) thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H)))
0.01user 0.00system 0:00.01elapsed 83%CPU (0avgtext+0avgdata 3940maxresident)k
0inputs+0outputs (0major+210minor)pagefaults 0swaps

$ ./threshold.py 3 > input
$ wc -c input
84 input
$ cat input
thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H))))
$ \time ./miniscript < input
X    344.3645833333   251 c:or_i(pk(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),pk_h(H))))))))) thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H))))
0.05user 0.00system 0:00.05elapsed 94%CPU (0avgtext+0avgdata 5404maxresident)k
0inputs+0outputs (0major+573minor)pagefaults 0swaps

$ ./threshold.py 4 > input
$ wc -c input
112 input
$ cat input
thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H)))))
$ \time ./miniscript < input
X    425.4244791667   332 c:or_i(pk(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),pk_h(H)))))))))))) thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H)))))
0.31user 0.00system 0:00.32elapsed 98%CPU (0avgtext+0avgdata 12712maxresident)k
0inputs+0outputs (0major+2413minor)pagefaults 0swaps

$ ./threshold.py 5 > input
$ wc -c input
140 input
$ cat input
thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H))))))
$ \time ./miniscript < input
X    506.4394531250   413 c:or_i(pk(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),pk_h(H))))))))))))))) thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk
(H),thresh(1,pk(H),pk(H),pk(H))))))
1.38user 0.01system 0:01.41elapsed 99%CPU (0avgtext+0avgdata 47732maxresident)k
0inputs+0outputs (0major+11148minor)pagefaults 0swaps

$ ./threshold.py 6 > input
$ wc -c input
168 input
$ cat input
thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H)))))))
$ \time ./miniscript < input
X    587.4431966146   494 c:or_i(pk(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),pk_h(H)))))))))))))))))) thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1
,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H)))))))
7.07user 0.10system 0:07.25elapsed 98%CPU (0avgtext+0avgdata 208636maxresident)k
0inputs+0outputs (0major+51370minor)pagefaults 0swaps

$ ./threshold.py 7 > input
$ wc -c input
196 input
$ cat input
thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H))))))))
$ \time ./miniscript < input
X    668.4441324870   575 c:or_i(pk(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),pk_h(H))))))))))))))))))))) thresh(1,pk(H),pk(H)
,pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H))))))))
33.60user 0.61system 0:34.51elapsed 99%CPU (0avgtext+0avgdata 935792maxresident)k
0inputs+0outputs (0major+233170minor)pagefaults 0swaps

$ ./threshold.py 8 > input
$ wc -c input
224 input
$ cat input
thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H)))))))))
$ \time ./miniscript < input
X    749.4443664551   656 c:or_i(pk(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),pk_h(H)))
))))))))))))))))))))) thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H)))))))))
152.81user 3.02system 2:37.25elapsed 99%CPU (0avgtext+0avgdata 4178928maxresident)k
0inputs+0outputs (0major+1043945minor)pagefaults 0swaps

$ ./threshold.py 9 > input
$ wc -c input
252 input
$ cat input
thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H))))))))))
$ \time ./miniscript < input
X    830.4444249471   737 c:or_i(pk(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h
(H),or_i(pk_h(H),or_i(pk_h(H),pk_h(H))))))))))))))))))))))))))) thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H))))))))))
703.78user 11.88system 12:02.40elapsed 99%CPU (0avgtext+0avgdata 18487544maxresident)k
0inputs+0outputs (0major+4621129minor)pagefaults 0swaps

$ ./threshold.py 10 > input
$ wc -c input
280 input
$ cat input
thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H)))))))))))
$ \time ./miniscript < input
… will most likely call in the OOM killer or throw std::bad_alloc before finishing …
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
Command terminated by signal 6
@practicalswift practicalswift changed the title Policies with too high nesting depth are not rejected: It is possible to create small inputs that cause extreme memory usage (in practice: OOM) Policies with too high nesting depth are not rejected: It is possible to create small inputs that cause extreme memory usage (in practice: OOM kill or std::bad_alloc) Aug 30, 2019
@practicalswift practicalswift mentioned this issue Sep 4, 2019
Closed
@practicalswift
Copy link
Contributor Author

practicalswift commented Sep 4, 2019 •
edited
Loading

Somewhat similar issue in the miniscript implementation in Rust: https://github.com/apoelstra/rust-miniscript/issues/41

@practicalswift practicalswift mentioned this issue Sep 9, 2019
Merged
@practicalswift practicalswift mentioned this issue Sep 18, 2019
Merged
@practicalswift practicalswift mentioned this issue Sep 8, 2020
Closed
@practicalswift practicalswift mentioned this issue Sep 4, 2021
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@practicalswift