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
Description
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