If you need newgrp, you dun goofed (and "setuidgid" may be the culprit)

Recently, on a machine with custom upstart init scripts, I couldn't figure out why I couldn't access serial ports or USB devices, even though my username was in the dialout and plugdev groups in /etc/group.

Running the "groups" command, I could see that my groupset only contained my own personal group:

$ groups
credentiality

I found that I could run "newgrp dialout" to get it added to my groupset:

$ newgrp dialout
$ groups

dialout credentiality

And looking online, I found various tricks people would use to run the commands they needed using newgrp.  (It's not trivial, since newgrp insists on creating a subshell).

But I kept getting the sense that newgrp should almost never be necessary anymore, now that modern unix systems have the notion of a groupset.

Turns out the culprit was "setuidgid", which we were using in the upstart scripts to run programs as me.  They said things like:

exec setuidgid credentiality startx

Now that I know to look for it, setuidgid's manpage points out that it "remov[es] all supplementary groups".  Which isn't very helpful if, for instance, a process needs to access files from both the "dialout" and "plugdev" groups.

Fortunately, there are several alternatives to setuidgid that preserve the group memberships you expect, and you can use the "groups" command to verify that:

# setuidgid credentiality groups

credentiality

# su -c groups credentiality

credentiality adm disk dialout cdrom floppy sudo audio dip video plugdev

# sudo -u credentiality groups

credentiality adm disk dialout cdrom floppy sudo audio dip video plugdev

# start-stop-daemon -c credentiality -S --exec /usr/bin/groups

credentiality adm disk dialout cdrom floppy sudo audio dip video plugdev

# # chpst is in package runit (yet another init system, ugh.), and lets you specify a list of groups explicitly:

# chpst -u credentiality:credentiality:plugdev:dialout groups

credentiality plugdev dialout

Carmichael numbers and Fermat primality

I did some recreational mathematics today, and created this plot, showing the number of values for which a^(n-1) = 1 (mod n), for all composite n in the range [3..10000]:

The formula a^(n-1) mod n appears in Fermat's Little Theorem, which says that for prime values of n, the result will always be 1, no matter what a you choose.  If you get a value other than 1, you know that n is composite.

That's neat because it lets us test whether a given n is composite much more quickly than by trying to factor it.  We call that the Fermat Primality Test.  

However, the converse doesn't always hold: sometimes a^(n-1)=1 (mod n) even if n is composite.  When  that happens for some a and n, we say that a is a false witness for n, since it incorrectly suggests that n might be prime.

And that's what the above graph shows: how many false witnesses there are for each value n up to 10,000.  In particular, I scaled the y axis so that it shows the percentage of relatively prime a values that are false witnesses.

Carmichael Numbers

Most interesting are the vertical lines in the graph that reach all the way to the top.  Those are the falsest of the pseudoprimes (with respect to the Fermat test).  They're called the Carmichael Numbers, and I've always found them fascinating, because the smallest of them is 561!  That's the leftmost line in the graph that reaches all the way to the top.

Just how prime are you?

The other thing I was surprised to find in this graph are what we might call the halfway-prime numbers -- numbers for which half of the witnesses will suggest primality with the Fermat test.  And there are one-third-prime numbers, and so on.

Merry Christmas!

All that graphing got me wondering how often a^(n-1) produces numbers other than 1.  So I created this image, which shows increasing values of n as you work downward, and shows how often we get a remainder r.  r is shown on the X axis, while the number of times it came up is shown as a color:

 0=black, 1=dark gray, 2=light gray, 3=blue, 4=orange, 5=red, 6 or more = white

The other trick is that in number theory, we sometimes talk about negative remainders.  If you're working (mod 5), you might get remainders of 0,1,2,3,4, but since the next remainder after 4 is 0 again, sometimes it's easier to think of a remainder of 4 as -1.  So instead of 0,1,2,3,4, we call them 0,1,2,-2,-1, and that's what I've done here. 

Consider the topmost orange pixel in the above image.  It's the 5th pixel from the top, so that whole row represents n=5.  The orange pixel (and all the ones below it) are the "remainder=1" column.  The column to the left of it is the "remainder=0" column, and the one to the right is "remainder=2".  Since 5 is prime, we expect a^4 to be 1 (mod 5) for all 4 possible values of a: 1,2,3 and 4.  And indeed, orange is the color for 4.

Two pixels down, you'll see a white pixel telling us that 7 is prime, since a^6=1 (mod 7) for a=1,2,3,4,5,6.  In the above image, you can keep counting down from the orange pixel at n=5 and see all the primes as white pixels, with 31 at the very bottom.

Give me one of everything

One surprise to me was row 6 (just below the topmost orange pixel).  It has a solid dark gray line extending all the way across.  That means that the five values of a: 1,2,3,4,5 in the equation a^5 (mod 6) produced... the values 1,2,3,4,5!  (Try it: 2^5=32, mod 6=2.  3^5=243, mod 6=3.)

And you can see that lots of other numbers have this behavior: 10, 14, (but not 18!), 22, 26, 30 and so on.

I need a bigger tree

Here's how the image looks if we keep going all the way to 100:

And if you really have a tall living room, you can see the numbers up to 1000, as well as the python source code I used to generate the images.

Bechdel Test: Aeon Flux

I had forgotten what a great movie Aeon Flux was.  I can't think of a more Bechdel-compliant action movie, it's visually stunning, and has a creative plot.

Escalation

The answer was in the stars. For some reason, Earthlings had founded universities, and those universities had supported thousands of astronomers for hundreds of years. They refined their techniques over the centuries, collecting databases of statistics on distant stars which no human could ever visit.

And then a grad student in cryptography had gotten fed up with her adviser and switched to astronomy. To familiarize herself with the star database, Li had fed the coordinates of all the known stars in the galaxy into a PRNG test suite used to assess the predictability of cryptographic random number generators.

She hadn't been surprised when the database failed the test; stars aren't randomly distributed, and as they later found, at least 7 different astronomical techniques had also added artificial patterns to the database. However, Li thought it amusing when the test suite claimed the values were generated by a Linear Feedback Shift Register, the simplistic random number generator included in most programming libraries. It had even helpfully produced the LFSR parameters which, with a few lines of code, would generate a sequence of numbers that the test suite thought were somehow related to the database values.

Li had shown it to her advisor, and over a few months they had toyed with the results at odd hours, musing on a publication about systemic errors in sky survey techniques, or perhaps uncovering evidence of fabrication by some unscrupulous astronomer. When Li's model started predicting locations of stars before they were discovered, they worked full time on it for 18 months before telling another soul: surely it would be seen as plagiarism, not prediction.

But in the end, the systemic errors were identified and eliminated, and Li was confirmed to have made the greatest scientific discovery in all of history: the universe they lived in was incontrovertibly a simulation. And moreover, whatever Gods had placed the stars in their galaxies had been lazy in their choice of random number generators, just as human programmers are. (This did create a certain smugness among the kind of cryptographers who used cryptograpic-strength PRNGs to shuffle music playlists.)

As news-show pundits spouted absurdities and mankind came to grips with the hand of God, scientists in all fields now knew what to look for, and found bugs aplenty.

And as the fabric of the universe resolved under our microscopes, it was the cryptographers once again who made a profoundly disturbing hypothesis. The universe was made of bits, and manipulated by algorithms. Far more bits than our computers had, and running algorithms more complex than mankind had ever managed. But we knew there were bugs. What if some of those bugs were also security holes?

Teenagers had been exploiting complex systems for years. A carefully crafted string of a few hundred unexpected characters could cause a buggy subroutine to turn a user into an administrator. Or, if the string was slightly off, crash the server. This was normally no concern to the budding hackers. But then, they usually weren't hacking their own life support.

When the politicians finally understood, the strictest laws were passed. But studying really isn't much different than hacking, and eventually we learned all about our host machine. And several of the shortcomings of our universe started looking tantalizingly exploitable.

Ubuntu Lucid running alongside android on my phone

At first I thought running ubuntu on my phone would require blowing away the android OS, but that's not the case. Instead, an ubuntu filesystem gets mounted on the SD card, with all the system files set up right so that things like apt-get work. Some things don't work, I think because the android kernel isn't quite what the ubuntu apps expect, but you know you're doing well when firefox runs!

The nexusonehacks Ubuntu disk image worked great for me, but took forever to download and had a ton of stuff that I didn't need, like firefox and openoffice.org.

So I stripped it down to bare bones and upgraded it to lucid. Check it out: run a bare-bones Ubuntu Lucid filesystem alongside android on a froyo phone.

Native vim for android

Update: The vim binary has moved to the downloads page.

Update: Created a code.google.com project to keep stuff like this. Also, I got color syntax hilighting to work. See the README.txt in the vim/ directory of the repository.

Tonight I managed to compile vim to run natively on my android phone! My phone is rooted and running cyanogenmod CM6 rc3. Rooting is necessary to run vim, but cyanogen probably isn't necessary.

First I had to compile ncurses using the ndk. Follow that link and compile ncurses the way I did if you want to have any hope of compiling vim using these instructions.

Once I had ncurses built, I had to make just a few changes to vim to get it to work.

I downloaded vim from the mercurial archive, which as of today is pretty much the same as the 7.3 release, I think. I figured out how to call configure by trial and error:

vim_cv_memcpy_handles_overlap=no \
vim_cv_bcopy_handles_overlap=no \
vim_cv_memmove_handles_overlap=no \
vim_cv_stat_ignores_slash=no \
vim_cv_getcwd_broken=no \
vim_cv_tty_group=world \
vim_cv_terminfo=yes \
LDFLAGS="-L/path/to/ncurses-5.7/lib" \
CFLAGS="-I/path/to/ncurses-5.7/lib" \
vim_cv_toupper_broken=no \
CC=agcc.pl \
./configure --host=arm-eabi --with-tlib=ncurses

I got this error message: "could not compile program using uint32_t", and manually patched the configure script because I couldn't remember how to regenerate the script from the configure.in:

$as_echo_n "checking uint32_t is 32 bits... " >&6; }
if test "$cross_compiling" = yes; then :
  true
#  as_fn_error "could not compile program using uint32_t." "$LINENO" 5
else

I also got an "undefined reference to sysinfo" error due to an android bug that omitted the sysinfo() call. So I commented out the HAVE_SYSINFO and HAVE_SYSINFO_MEM_UNIT lines in src/auto/config.h.

I think that was it! Once it finished compiling, I copied over the runtime/ directory and the src/vim binary to /data/vim on my phone. I did an "export VIMRUNTIME=/data/vim/runtime", and vim worked great!

Once I got my VIMRUNTIME set, I was able to ":syntax on", although I'm not getting any color. But otherwise it seems to work great!

You can find a tarball of vim for android on the Downloads page: look for vim-7.3-android-binary.tar.gz. There's also a tarred-up copy of my build directory, although I'm not sure why anyone would want that.

Compile ncurses for android

Update: The tarball of my ncurses build directory has moved to the downloads page.  (Also, agcc -> agcc.pl thanks to Interarticle)

I got the crazy notion to try to compile a native vim binary for android, and one of its dependencies is libncurses.

Make sure you have the ndk installed and working.

You'll need the agcc wrapper, a perl script that creates appropriate command line arguments for arm-eabi-gcc. I learned today that the order of arguments to gcc can be quite significant while linking. I kept getting errors about the "__aeabi_unwind_cpp_pr0" symbol and common functions like printf not being found when it tried to link.

So I hacked Vlad's hacked agcc to make sure that libgcc.a and libc.a get put at the end of the command line, which seems to be necessary for static linking. Here's my hacked version of Vlad's agcc.

Make sure both agcc and arm-eabi-gcc are in your path.

Download ncurses-5.7.tar.gz.

Run configure:

CC=agcc.pl ./configure --host=arm-eabi --without-cxx-binding

When I tried to build, I got errors saying "'struct lconv' has no member named 'decimal_point'"", because android has a broken locale implementation.

So I commented out the HAVE_LOCALE_H line from include/ncurses_cfg.h. (Is there a better way to force configure to set a value like that during the ./configure process?)

It might be possible to build ncurses with the C++ binding, but I didn't try.

Once I had all that fixed, the make ran just fine, and I ended up with lib/libncurses.a.