<div dir="ltr"><div>Hi Sasha,</div><div><br></div><div>Thank you for bringing to my attention these potentially serious</div><div>issues. I will certainly investigate each of them and make the</div><div>appropriate changes. I've included an associate who is familiar</div><div>with the origins and development of this `bc' to help me address</div><div>each point below, as you make some strong assertions.</div><div><br></div><div>To your message [1] "Toybox bc run away interactive process",</div><div><br></div><div>> When attempting to use ctrl-c to kill the toybox `bc' implementation</div><div>> while in non-interactive mode a bug results in it entering interactive</div><div>> mode while the program continues to run and then the user loses</div><div>> control of both interactive and non-interactive modes.</div><div>></div><div>> To reproduce:</div><div>> echo "s(131231)" | ./bc -l .. and hit ctrl-c</div><div>></div><div>> This consumes many GB of memory before finally exhausting the system.</div><div><br></div><div>On a glibc-based x86_64 system I was not able to reproduce this</div><div>issue as stated above, however one of your later messages stated</div><div>that you encountered the issues on an Alpine Linux (musl-based)</div><div>system. On an Alpine 3.8 system I still could not reproduce it,</div><div>both in the Toybox environment and the stand-alone upstream [5].</div><div><br></div><div>My associate was able to reproduce this using '131231' and '0.5'</div><div>on Alpine, even using a fixed scale, e.g., "scale=50", using the</div><div>stand-alone version.</div><div><br></div><div>As to your second message [2] "Toybox bc's transcendental and</div><div>irrational functions produce incorrect results, memory leaks and</div><div>exhibit brute force algorithmic complexity.",</div><div><br></div><div>> Upon inspection of the mathematics core of the toybox `bc' it appears</div><div>> to have multiple systemic issues and is potentially unsalvagable.</div><div><br></div><div>Let me begin by saying that I'm grateful for your insightful and</div><div>detailed suggestions. If you have any more suggestions that may</div><div>be helpful please feel free to write those to the mailing list.</div><div>Several subscribers are definitely interested in this material.</div><div><br></div><div>> All transcendental functions produce out of bounds memory accesses.</div><div>> All builtin functions produce gratuitous and insecure memory errors.</div><div><br></div><div>We've tested `bc' using three static analysis tools, two memory</div><div>scanners (Google Address Sanitizer and Valgrind), in addition to</div><div>manual review, and have not found "gratuitous and insecure</div><div>memory errors". There may be a single leak in the IO module, and</div><div>we are presently looking into this.</div><div><br></div><div>Valgrind does indicate excess (but not illegal) memory allocation in</div><div>some of the transcendental functions, with certain inputs. We've</div><div>yet to isolate specific classes of inputs that cause the issue.</div><div><br></div><div>> Excessive or incorrect memory consumption for invocations of</div><div>> transcendental functions result in total memory exhaustion consuming</div><div>> about 1 GB for every few seconds of run time.</div><div><br></div><div>Would you please explain how we might be able to reproduce this?</div><div>Is there a specific scenario or condition where this occurs, and</div><div>on which particular platform(s) does this occur?</div><div><br></div><div>> The algorithms used are of the most naive possible variety and balk</div><div>> under even the smallest inputs taking hundreds of times longer than</div><div>> similar implementations.</div><div><br></div><div>Typically, "naive" algorithms perform better for smaller inputs</div><div>and more "advanced" algorithms are desired for their lower bound</div><div>which is realized as the input grows large. To hear that "even</div><div>the smallest inputs [are] taking hundreds of times longer" than</div><div>similar implementations is ... odd.</div><div><br></div><div>Would you please share your benchmarks and testing methods? It</div><div>will be tremendously helpful. Reference benchmarks to "similar"</div><div>implementations (and what those are) would be even better.</div><div><br></div><div>For larger problems, you are certainly correct. This `bc' hasn't</div><div>been optimized for performance; it's been optimized for size. It</div><div>implements a complete language, virtual machine and math library</div><div>in under 6000 LOC.</div><div><br></div><div>> All builtin transcendental and irrational functions produce incorrect</div><div>> results.</div><div><br></div><div>Would you please provide an example (ideally for each) showing</div><div>an instance where incorrect results are produced?</div><div><br></div><div>> Functions that should be complete in a fraction of a second are</div><div>> getting bogged down in naive algorithmic complexity.</div><div><br></div><div>See my above remark re: algorithmic complexity, and please offer</div><div>an example or two. There had been some discussion regarding just</div><div>how "precise" the computation needs to be: an exact solution for</div><div>all digits except the last? We will refer to the specification</div><div>for clarification on this matter.</div><div><br></div><div>> I had read that a team of mathematicians and systems programmers were</div><div>> working on the new toybox bc implementation. What exactly happened</div><div>> here?</div><div><br></div><div>I was not aware of such efforts/arrangements. The Toybox mailing</div><div>list on 2018-03-09 by a Christopher M. Graff states that he had</div><div>asked a few people, including Gavin D. Howard ("gdh") who wrote</div><div>the `bc' in question [5], to assist him with his implementation.</div><div>Who are you referring to? That message doesn't reference either,</div><div>but perhaps we could collaborate with the mathematicians to help</div><div>in achieving lower bounds?</div><div><br></div><div>In your third message [4],</div><div><br></div><div>> We ran across these errors while doing "make check" on the hebimath</div><div>> bignum library on an alpine linux system running against toybox's</div><div>> `bc'. Hebimath uses POSIX bc as part of its test suite, Perhaps it</div><div>> could be used to drive the core arithmetic of your POSIX bc</div><div>> implementation as it is MIT licensed and is fast and accurate.</div><div><br></div><div>> <a href="https://github.com/suiginsoft/hebimath">https://github.com/suiginsoft/hebimath</a></div><div><br></div><div>This is a helpful suggestion (to use the 'hebimath' test suite);</div><div>thank you Sasha. In December 2017 my associate had discussed the</div><div>'hebimath' library in a Freenode channel with the aforementioned</div><div>CM Graff and determined it a reasonable implementation, but that</div><div>it was rather large and would not "fit" into the Toybox project</div><div>(and size is the limiting factor).</div><div><br></div><div>Anyway, we'll review and make the necessary improvements.</div><div><br></div><div>Regards,</div><div><br></div><div> Gavin D. Howard Zach van Rijn</div><div> "gdh" "Thalheim"</div><div><br></div><div><br></div><div>[1]: <a href="http://lists.landley.net/pipermail/toybox-landley.net">http://lists.landley.net/pipermail/toybox-landley.net</a></div><div>/2018-August/009626.html</div><div><br></div><div>[2]: <a href="http://lists.landley.net/pipermail/toybox-landley.net">http://lists.landley.net/pipermail/toybox-landley.net</a></div><div>/2018-August/009628.html</div><div><br></div><div>[3]: <a href="http://lists.landley.net/pipermail/toybox-landley.net">http://lists.landley.net/pipermail/toybox-landley.net</a></div><div>/2018-March/009403.html</div><div><br></div><div>[4]: <a href="http://lists.landley.net/pipermail/toybox-landley.net">http://lists.landley.net/pipermail/toybox-landley.net</a></div><div>/2018-August/009629.html</div><div><br></div><div>[5]: <a href="https://github.com/gavinhoward/bc">https://github.com/gavinhoward/bc</a></div></div><br><div class="gmail_quote"><div dir="ltr">On Mon, Aug 27, 2018 at 7:29 AM Sasha Toltec <<a href="mailto:sashatoltec1@gmail.com">sashatoltec1@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">We ran across these errors while doing "make check" on the hebimath<br>
bignum library on an alpine linux system running against toybox's<br>
`bc'. Hebimath uses POSIX bc as part of its test suite, Perhaps it<br>
could be used to drive the core arithmetic of your POSIX bc<br>
implementation as it is MIT licensed and is fast and accurate.<br>
<br>
<a href="https://github.com/suiginsoft/hebimath" rel="noreferrer" target="_blank">https://github.com/suiginsoft/hebimath</a><br>
<br>
Sasha Toltec<br>
Toltec Enterprises<br>
<a href="mailto:sashatoltec1@gmail.com" target="_blank">sashatoltec1@gmail.com</a><br>
<br>
On 8/27/18, Sasha Toltec <<a href="mailto:sashatoltec1@gmail.com" target="_blank">sashatoltec1@gmail.com</a>> wrote:<br>
> Upon inspection of the mathematics core of the toybox bc it appears to<br>
> have multiple systemic issues and is potentially unsalvagable.<br>
><br>
> All transcendental functions produce out of bounds memory accesses.<br>
><br>
> All builtin functions produce gratuitous and insecure memory errors.<br>
><br>
> Excessive or incorrect memory consumption for invocations of<br>
> transcendental functions result in total memory exhaustion consuming<br>
> about 1 GB for every few seconds of run time.<br>
><br>
> The algorithms used are of the most naive possible variety and balk<br>
> under even the smallest inputs taking hundreds of times longer than<br>
> similar implementations.<br>
><br>
> All builtin transcendental and irrational functions produce incorrect<br>
> results.<br>
><br>
> Functions that should be complete in a fraction of a second are<br>
> getting bogged down in naive algorithmic complexity.<br>
><br>
> I had read that a team of mathematicians and systems programmers were<br>
> working on the<br>
> new toybox bc implementation. What exactly happened here?<br>
><br>
><br>
> Sasha Toltec<br>
> Toltec Enterprises<br>
> <a href="mailto:sashatoltec1@gmail.com" target="_blank">sashatoltec1@gmail.com</a><br>
><br>
_______________________________________________<br>
Toybox mailing list<br>
<a href="mailto:Toybox@lists.landley.net" target="_blank">Toybox@lists.landley.net</a><br>
<a href="http://lists.landley.net/listinfo.cgi/toybox-landley.net" rel="noreferrer" target="_blank">http://lists.landley.net/listinfo.cgi/toybox-landley.net</a><br>
</blockquote></div>