6 ms·
No. Proving termination for programs written in models less powerful than a Turing machine does not require you to solve the halting problem. Programs using pr
by rcoder 17y ago
No.
Proving termination for programs written in models less powerful than a Turing machine does not require you to solve the halting problem. Programs using primitive recursion, finite automata, and regular expressions, for example, can all be proved to terminate, and can express a number of useful computations.
The problem is that the pickle module is far too permissive. In particular, the REDUCE operation invokes a Python callable with an argument tuple on the pickle stack, which means that 'pickles' are at least as powerful (in the Turing-general, halting problem sense) as Python.
- tptacek 17y agoIt sure sounds like you said "No, <stuff> <stuff> <stuff>, but yes."
- rcoder 17y agoI guess it was, "no, it shouldn't be, except that the pickle module is broken by design." I.e., data structure parsing should not require a Turing-complete language. If it does, your serialization format is broken. But yeah, I can see the issue with my original comment.
- tptacek 17y agoPickle isn't a data structure parsing system, though. It's a system for dumping out and restoring (parts of) the state of the Python interpreter. If pyasn1 allowed code execution or method invocation, you could say it was broken by design. You can't say that about Pickle.
- rcoder 17y agoSince the pickle module doesn't marshal many types of stateful objects (filehandles, functions, etc.), I'm not sure it's fair to describe it as a means of saving the "state of the Python interpreter". It really just serves to save a compact representation of data on disk, without explicitly managing packing an unpacking from the binary serialization. In that respect, it intuitively seems like it should behave more like the ASN1 or YAML formats w.r.t. the safety of data loaded from it. I may understand the risks, and you may understand the risks, but I think that a new Python programmer could be forgiven for simply scanning the standard library documentation and thinking that the pickle format would be safe for transport across untrusted channels.
- eru 17y agoJust add crypthographic authentication (and hashes) and some problems go away.
- calcnerd256 17y agoNo, they are saying that Pickle as it is currently designed is too powerful. Depending on the goals of Pickle, it may be possible to reduce its power by redesigning it to do no more than its goals.
- tptacek 17y agoAnd I'm saying "pickle isn't really designed to solve the problem they're saying it's bad at solving".
- stonemetal 17y agoSo If we reduce the scope of Pickle's goals then the current Pickle that meets its current goals is to strong, and could be reduced.