[Toybox] Toybox bc run away interactive process
When attempting to use ctrl-c to kill the toybox bc implementation while in non-interactive mode a bug results in it entering interactive mode while the program continues to run and then the user loses control of both interactive and non-interactive modes. To reproduce: echo "s(131231)" | ./bc -l .. and hit ctrl-c This consumes many GB of memory before finally exhausting the system. Sasha Toltec Toltec Enterprises sashatolt...@gmail.com ___ Toybox mailing list Toybox@lists.landley.net http://lists.landley.net/listinfo.cgi/toybox-landley.net
[Toybox] [PENDING] [fold.c] [Question]
Hi Rob,
I started working on fold.c cleanup,
going through the code, and testing it out, i have a couple of questions.
1. gnu fold engulfs \n unconditionally i.e if there is a \n after the fold
has happend that redundant \n does not make it to the output , that kind of
makes sense but the posix spec only mentions carriage returns and only if the
-b option is not specified. (Note* That the current pending/fold outputs an
extra new line.)
2. the current fold implementation has unfold capability , that i think
should not be squeezed in fold (as of yet), my plan is to have unfold as a
separate utility that uses infrastructure from fold if necessary, or at least
make unfold as a config option, please share your thoughts on this.
3. The tabstop thing is bit confusing for me, as the posix spec says "Tab
stops shall be at each column position n such that n modulo 8 equals 1." ( from
this i understand that given the column the next column where the tab ends
should be a column whose modulo 8 returns 1 , kind of this pseudo code ? where
start is the current column. (am i understanding it right ?)
int get_next_ts(int start)
{
if (start <= 1)
return 9;
if ((start % 8) == 1)
return start;
return get_next_ts(++start);
}
Haroon
___
Toybox mailing list
Toybox@lists.landley.net
http://lists.landley.net/listinfo.cgi/toybox-landley.net
[Toybox] Toybox bc's transcendental and irrational functions produce incorrect results, memory leaks and exhibit brute force algorithmic complexity.
Upon inspection of the mathematics core of the toybox bc it appears to have multiple systemic issues and is potentially unsalvagable. All transcendental functions produce out of bounds memory accesses. All builtin functions produce gratuitous and insecure memory errors. Excessive or incorrect memory consumption for invocations of transcendental functions result in total memory exhaustion consuming about 1 GB for every few seconds of run time. The algorithms used are of the most naive possible variety and balk under even the smallest inputs taking hundreds of times longer than similar implementations. All builtin transcendental and irrational functions produce incorrect results. Functions that should be complete in a fraction of a second are getting bogged down in naive algorithmic complexity. I had read that a team of mathematicians and systems programmers were working on the new toybox bc implementation. What exactly happened here? Sasha Toltec Toltec Enterprises sashatolt...@gmail.com ___ Toybox mailing list Toybox@lists.landley.net http://lists.landley.net/listinfo.cgi/toybox-landley.net
Re: [Toybox] Toybox bc's transcendental and irrational functions produce incorrect results, memory leaks and exhibit brute force algorithmic complexity.
We ran across these errors while doing "make check" on the hebimath bignum library on an alpine linux system running against toybox's `bc'. Hebimath uses POSIX bc as part of its test suite, Perhaps it could be used to drive the core arithmetic of your POSIX bc implementation as it is MIT licensed and is fast and accurate. https://github.com/suiginsoft/hebimath Sasha Toltec Toltec Enterprises sashatolt...@gmail.com On 8/27/18, Sasha Toltec wrote: > Upon inspection of the mathematics core of the toybox bc it appears to > have multiple systemic issues and is potentially unsalvagable. > > All transcendental functions produce out of bounds memory accesses. > > All builtin functions produce gratuitous and insecure memory errors. > > Excessive or incorrect memory consumption for invocations of > transcendental functions result in total memory exhaustion consuming > about 1 GB for every few seconds of run time. > > The algorithms used are of the most naive possible variety and balk > under even the smallest inputs taking hundreds of times longer than > similar implementations. > > All builtin transcendental and irrational functions produce incorrect > results. > > Functions that should be complete in a fraction of a second are > getting bogged down in naive algorithmic complexity. > > I had read that a team of mathematicians and systems programmers were > working on the > new toybox bc implementation. What exactly happened here? > > > Sasha Toltec > Toltec Enterprises > sashatolt...@gmail.com > ___ Toybox mailing list Toybox@lists.landley.net http://lists.landley.net/listinfo.cgi/toybox-landley.net
[Toybox] [PATCH] sendevent: remove ioctl call
The version number queried by this ioctl call is never used.
Delete it.
-- Nick
From 3addf78f5670c24ed8f8f9717947bb24870ea0b5 Mon Sep 17 00:00:00 2001
From: Nick Kralevich
Date: Mon, 27 Aug 2018 11:18:38 -0700
Subject: [PATCH] sendevent: remove ioctl call
The version number queried by this ioctl call is never used.
Delete it.
Signed-off-by: Nick Kralevich
---
toys/android/sendevent.c | 4
1 file changed, 4 deletions(-)
diff --git a/toys/android/sendevent.c b/toys/android/sendevent.c
index 8e982e0..6d1f124 100644
--- a/toys/android/sendevent.c
+++ b/toys/android/sendevent.c
@@ -22,12 +22,8 @@ config SENDEVENT
void sendevent_main(void)
{
int fd = xopen(*toys.optargs, O_RDWR);
- int version;
struct input_event ev;
- if (ioctl(fd, EVIOCGVERSION, &version))
-perror_exit("EVIOCGVERSION failed for %s", *toys.optargs);
-
memset(&ev, 0, sizeof(ev));
// TODO: error checking and support for named constants.
ev.type = atoi(toys.optargs[1]);
--
2.19.0.rc0.228.g281dcd1b4d0-goog
___
Toybox mailing list
Toybox@lists.landley.net
http://lists.landley.net/listinfo.cgi/toybox-landley.net
Re: [Toybox] [PATCH] sendevent: remove ioctl call
It just occurred to me that there could be another intention behind the ioctl call. Calling ioctl(EVIOCGVERSION) on the /dev/input device is a way for the code to verify it's actually sending messages to a /dev/input file, vs some other file. So, while not documented in the source code, this call may actually have value and protect the caller from inadvertently specifying an invalid file. -- Nick On Mon, Aug 27, 2018 at 11:31 AM Nick Kralevich wrote: > > The version number queried by this ioctl call is never used. > Delete it. > > -- Nick -- Nick Kralevich | n...@google.com ___ Toybox mailing list Toybox@lists.landley.net http://lists.landley.net/listinfo.cgi/toybox-landley.net
Re: [Toybox] Toybox bc's transcendental and irrational functions produce incorrect results, memory leaks and exhibit brute force algorithmic complexity.
Hi Sasha,
Thank you for bringing to my attention these potentially serious
issues. I will certainly investigate each of them and make the
appropriate changes. I've included an associate who is familiar
with the origins and development of this `bc' to help me address
each point below, as you make some strong assertions.
To your message [1] "Toybox bc run away interactive process",
> When attempting to use ctrl-c to kill the toybox `bc' implementation
> while in non-interactive mode a bug results in it entering interactive
> mode while the program continues to run and then the user loses
> control of both interactive and non-interactive modes.
>
> To reproduce:
> echo "s(131231)" | ./bc -l .. and hit ctrl-c
>
> This consumes many GB of memory before finally exhausting the system.
On a glibc-based x86_64 system I was not able to reproduce this
issue as stated above, however one of your later messages stated
that you encountered the issues on an Alpine Linux (musl-based)
system. On an Alpine 3.8 system I still could not reproduce it,
both in the Toybox environment and the stand-alone upstream [5].
My associate was able to reproduce this using '131231' and '0.5'
on Alpine, even using a fixed scale, e.g., "scale=50", using the
stand-alone version.
As to your second message [2] "Toybox bc's transcendental and
irrational functions produce incorrect results, memory leaks and
exhibit brute force algorithmic complexity.",
> Upon inspection of the mathematics core of the toybox `bc' it appears
> to have multiple systemic issues and is potentially unsalvagable.
Let me begin by saying that I'm grateful for your insightful and
detailed suggestions. If you have any more suggestions that may
be helpful please feel free to write those to the mailing list.
Several subscribers are definitely interested in this material.
> All transcendental functions produce out of bounds memory accesses.
> All builtin functions produce gratuitous and insecure memory errors.
We've tested `bc' using three static analysis tools, two memory
scanners (Google Address Sanitizer and Valgrind), in addition to
manual review, and have not found "gratuitous and insecure
memory errors". There may be a single leak in the IO module, and
we are presently looking into this.
Valgrind does indicate excess (but not illegal) memory allocation in
some of the transcendental functions, with certain inputs. We've
yet to isolate specific classes of inputs that cause the issue.
> Excessive or incorrect memory consumption for invocations of
> transcendental functions result in total memory exhaustion consuming
> about 1 GB for every few seconds of run time.
Would you please explain how we might be able to reproduce this?
Is there a specific scenario or condition where this occurs, and
on which particular platform(s) does this occur?
> The algorithms used are of the most naive possible variety and balk
> under even the smallest inputs taking hundreds of times longer than
> similar implementations.
Typically, "naive" algorithms perform better for smaller inputs
and more "advanced" algorithms are desired for their lower bound
which is realized as the input grows large. To hear that "even
the smallest inputs [are] taking hundreds of times longer" than
similar implementations is ... odd.
Would you please share your benchmarks and testing methods? It
will be tremendously helpful. Reference benchmarks to "similar"
implementations (and what those are) would be even better.
For larger problems, you are certainly correct. This `bc' hasn't
been optimized for performance; it's been optimized for size. It
implements a complete language, virtual machine and math library
in under 6000 LOC.
> All builtin transcendental and irrational functions produce incorrect
> results.
Would you please provide an example (ideally for each) showing
an instance where incorrect results are produced?
> Functions that should be complete in a fraction of a second are
> getting bogged down in naive algorithmic complexity.
See my above remark re: algorithmic complexity, and please offer
an example or two. There had been some discussion regarding just
how "precise" the computation needs to be: an exact solution for
all digits except the last? We will refer to the specification
for clarification on this matter.
> I had read that a team of mathematicians and systems programmers were
> working on the new toybox bc implementation. What exactly happened
> here?
I was not aware of such efforts/arrangements. The Toybox mailing
list on 2018-03-09 by a Christopher M. Graff states that he had
asked a few people, including Gavin D. Howard ("gdh") who wrote
the `bc' in question [5], to assist him with his implementation.
Who are you referring to? That message doesn't reference either,
but perhaps we could collaborate with the mathematicians to help
in achieving lower bounds?
In your third message [4],
> We ran across these errors while doing "make check" on the hebimath
> bignum library on an
Re: [Toybox] [PENDING] [fold.c] [Question]
Hi,
On 08/27/18 03:09, haroon maqsood wrote:
> Hi Rob,
> I started working on fold.c cleanup,
> going through the code, and testing it out, i have a couple of questions.
>
> 1. gnu fold engulfs \n unconditionally i.e if there is a \n after the fold
> has
> happened that redundant \n does not make it to the output , that kind of
> makes sense but the posix spec only mentions carriage returns and only if
> the -b option is not specified. (Note* That the current pending/fold
> outputs
> an extra new line.)
If a line is exactly the length that a newline would need to go after the last
character, no additional newline should be added. If there is, that's a bug. If
you're referring to a different situation, please give an example.
> 2. the current fold implementation has unfold capability , that i think
> should
> not be squeezed in fold (as of yet), my plan is to have unfold as a
> separate
> utility that uses infrastructure from fold if necessary, or at least make
> unfold as a config option, please share your thoughts on this.
> 3. The tabstop thing is bit confusing for me, as the posix spec says "Tab
> stops
> shall be at each column position such that n modulo 8 equals 1." ( from
> this i understand that given the column the next column where the tab ends
> should be a column whose modulo 8 returns 1 , kind of this pseudo code ?
> where start is the current column. (am i understanding it right ?)
>
> int get_next_ts(int start)
> {
> if (start <= 1)
> return 9;
>
> if ((start % 8) == 1)
> return start;
>
> return get_next_ts(++start);
> }
Yes, this is correct. A more idiomatic algorithm would be:
int get_next_ts(int start)
{
return ((start + 8) & -8) + 1;
}
> Haroon
Samuel
___
Toybox mailing list
Toybox@lists.landley.net
http://lists.landley.net/listinfo.cgi/toybox-landley.net
Re: [Toybox] Toybox bc's transcendental and irrational functions produce incorrect results, memory leaks and exhibit brute force algorithmic complexity.
Wait.. what? Am I really reading an email signed by two people? First off, you used subtractive chunking for division. Calling this a naive algorithm is giving it more credit than it is worth. The only time subtractive chunking is used is by school children. I cloned your repository (van Rijn and Howard?) https://github.com/gavinhoward/bc/ You (both?) seem to have no idea how to force errors out of a badly scaled irrational function so I supplied an example (though judging from the first example I gave, you (both?) will just lie/boast and say this one works on your system too!): echo "sqrt(.123)" | ./bc -l .0035071539807692832 echo "sqrt(.123)" | bc -l .0035071355833500363 As you can see, the "solution" is not even close. It is very hard to produce test results from such a badly made library, as it has actually taken my computer offline twice now (by overusing memory and other strange bugs), but I will give it another go: This command takes 25 seconds using your math (if you want to call it that), but only .01 seconds using a correct implementation: echo "sqrt(123123^123)" | time ./bc -l 11372609275300462201446509717277573045371910522125088219567947999131\ 66658519961107066259363279984633201203915727943358917486581704249214\ 07062970046980106751948432347504473036486754487763304174402241913448\ 76069500421950114801423888362557755902898498344596580006258740796194\ 54490321132814795761735241438589907716.72501611371543803908 25.30user echo "sqrt(123123^123)" | time bc -l 11372609275300462201446509717277573045371910522125088219567947999131\ 66658519961107066259363279984633201203915727943358917486581704249214\ 07062970046980106751948432347504473036486754487763304174402241913448\ 76069500421950114801423888362557755902898498344596580006258740796194\ 54490321132814795761735241438589907716.72501611371543803908 0.01user It is easy to scale this to take more time than the lifetime of the universe while other implementations are still instantaneous. I revved your repository back using git checkout and discovered a sordid history. Including an entire fast arbitrary precision implementation written by other authors (appears to be CM Graff and Bao Hexing) which was stripped, renamed and then badly reimplemented. Please just fix your fix your "implementation" (if one can really call it that) and stop wasting everyone's time. Sasha Toltec Toltec Enterprises sashatolt...@gmail.com On 8/27/18, Gavin Howard wrote: > Hi Sasha, > > Thank you for bringing to my attention these potentially serious > issues. I will certainly investigate each of them and make the > appropriate changes. I've included an associate who is familiar > with the origins and development of this `bc' to help me address > each point below, as you make some strong assertions. > > To your message [1] "Toybox bc run away interactive process", > >> When attempting to use ctrl-c to kill the toybox `bc' implementation >> while in non-interactive mode a bug results in it entering interactive >> mode while the program continues to run and then the user loses >> control of both interactive and non-interactive modes. >> >> To reproduce: >> echo "s(131231)" | ./bc -l .. and hit ctrl-c >> >> This consumes many GB of memory before finally exhausting the system. > > On a glibc-based x86_64 system I was not able to reproduce this > issue as stated above, however one of your later messages stated > that you encountered the issues on an Alpine Linux (musl-based) > system. On an Alpine 3.8 system I still could not reproduce it, > both in the Toybox environment and the stand-alone upstream [5]. > > My associate was able to reproduce this using '131231' and '0.5' > on Alpine, even using a fixed scale, e.g., "scale=50", using the > stand-alone version. > > As to your second message [2] "Toybox bc's transcendental and > irrational functions produce incorrect results, memory leaks and > exhibit brute force algorithmic complexity.", > >> Upon inspection of the mathematics core of the toybox `bc' it appears >> to have multiple systemic issues and is potentially unsalvagable. > > Let me begin by saying that I'm grateful for your insightful and > detailed suggestions. If you have any more suggestions that may > be helpful please feel free to write those to the mailing list. > Several subscribers are definitely interested in this material. > >> All transcendental functions produce out of bounds memory accesses. >> All builtin functions produce gratuitous and insecure memory errors. > > We've tested `bc' using three static analysis tools, two memory > scanners (Google Address Sanitizer and Valgrind), in addition to > manual review, and have not found "gratuitous and insecure > memory errors". There may be a single leak in the IO module, and > we are presently looking into this. > > Valgrind does indicate excess (but not illegal) memory allocation in > some of the transcendental f
[Toybox] Valgrind errors with toybox bc
Here are the valgrind errors that were requested. The problem seems to be that if you don't understand what types of numbers put stress on a bignum library, then it is difficult/impossible to force the memory errors. If one of the senior programmers involved with toybox has time to take a look at the bc bignum library and suggest some fixes and reading material to its authors that would perhaps be the best course of action. Toltec Enterprises generally charges for consultation ergo cannot offer much more input. sasha@sasha:~/toybox$ uname -a Linux sasha 4.4.0-103-generic #126-Ubuntu SMP Mon Dec 4 16:23:28 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux sasha@sasha:~/toybox$ make bc sasha@sasha:~/toybox$ echo "sqrt(.00123)" | valgrind ./bc ==10636== Memcheck, a memory error detector ==10636== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al. ==10636== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info ==10636== Command: ./bc -l ==10636== ==10636== Invalid read of size 1 ==10636==at 0x402D68: ??? (in /home/sasha/toybox/bc) ==10636==by 0x403C3B: ??? (in /home/sasha/toybox/bc) ==10636==by 0xFFEFFF84F: ??? ==10636==by 0x15: ??? ==10636==by 0x5945C9F: ??? ==10636==by 0x15: ??? ==10636==by 0x16: ??? ==10636==by 0x23: ??? ==10636== Address 0x5945aef is 1 bytes before a block of size 55 alloc'd ==10636==at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==10636==by 0x402FFB: ??? (in /home/sasha/toybox/bc) ==10636== ==10636== Invalid read of size 1 ==10636==at 0x402D68: ??? (in /home/sasha/toybox/bc) ==10636==by 0x402E5A: ??? (in /home/sasha/toybox/bc) ==10636==by 0xFFEFFF977: ??? ==10636==by 0x403727: ??? (in /home/sasha/toybox/bc) ==10636==by 0x4036B7: ??? (in /home/sasha/toybox/bc) ==10636==by 0xFFEFFF977: ??? ==10636==by 0xFFEFFF84F: ??? ==10636==by 0x5938397: ??? ==10636==by 0xFFEFFF977: ??? ==10636==by 0x5938397: ??? ==10636==by 0x4036B7: ??? (in /home/sasha/toybox/bc) ==10636==by 0x403142: ??? (in /home/sasha/toybox/bc) ==10636== Address 0x59458ef is 1 bytes before a block of size 16 alloc'd ==10636==at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==10636==by 0x402FFB: ??? (in /home/sasha/toybox/bc) ==10636==by 0xE: ??? ==10636==by 0xFFEFFFCC7: ??? ==10636==by 0xFFEFFFA2F: ??? ==10636==by 0x405561: ??? (in /home/sasha/toybox/bc) ==10636==by 0xFFEFFFBC7: ??? ==10636==by 0xD: ??? ==10636== ==10636== Invalid read of size 1 ==10636==at 0x402D68: ??? (in /home/sasha/toybox/bc) ==10636== Address 0x594633f is 1 bytes before a block of size 45 alloc'd ==10636==at 0x4C2FD5F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==10636==by 0x403030: ??? (in /home/sasha/toybox/bc) ==10636==by 0xFFEFFF927: ??? ==10636==by 0xFFEFFF8FF: ??? ==10636==by 0xFFEFFF977: ??? ==10636==by 0x403181: ??? (in /home/sasha/toybox/bc) ==10636==by 0x4048AF7: ??? ==10636== ==10636== Invalid read of size 1 ==10636==at 0x402D6B: ??? (in /home/sasha/toybox/bc) ==10636== Address 0x594601f is 1 bytes before a block of size 45 alloc'd ==10636==at 0x4C2FD5F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==10636==by 0x403030: ??? (in /home/sasha/toybox/bc) ==10636==by 0xFFEFFF8FF: ??? ==10636==by 0xFFEFFF927: ??? ==10636==by 0xFFEFFF977: ??? ==10636==by 0x403181: ??? (in /home/sasha/toybox/bc) ==10636==by 0x4048AF7: ??? ==10636== .0350713558335195 ==10636== ==10636== HEAP SUMMARY: ==10636== in use at exit: 1,768 bytes in 15 blocks ==10636== total heap usage: 588 allocs, 573 frees, 53,516 bytes allocated ==10636== ==10636== LEAK SUMMARY: ==10636==definitely lost: 1,216 bytes in 5 blocks ==10636==indirectly lost: 528 bytes in 9 blocks ==10636== possibly lost: 0 bytes in 0 blocks ==10636==still reachable: 24 bytes in 1 blocks ==10636== suppressed: 0 bytes in 0 blocks ==10636== Rerun with --leak-check=full to see details of leaked memory ==10636== ==10636== For counts of detected and suppressed errors, rerun with: -v ==10636== ERROR SUMMARY: 7 errors from 4 contexts (suppressed: 0 from 0) Sasha Toltec Toltec Enterprises sashatolte...@gmail.com ___ Toybox mailing list Toybox@lists.landley.net http://lists.landley.net/listinfo.cgi/toybox-landley.net
