Use full paths to executables.
If you don't provide a full path to the executable, you execute the first one on the path.
$ cat <<EOF > /tmp/head
$chmod +x /tmp/head
$ export PATH=/tmp:$PATH
Now run a program that calls 'head' instead of '/full/path/to/head
You'll run /tmp/head.
If you combine this with setuid/setgid, you have an escalation of privileges waiting to happen.
See also: level one of Stripe Capture the Flag
What if there was something like...
UnixUtils.paths[:cut] = '/my/path/to/cut'
That is how it should be. Full path to executable == not using $PATH == one less well-known vulnerability.
I completely understand why you'd go for the pathless method. You basically need to add a configure script to go out and find all the programs, or make the person installing the gem configure it by hand.
But, with the Linux File System Standards, it shouldn't be an overly big deal to track down where the executables live.
That's a good idea -- check all the reasonable places on startup, in order of reasonableness, allow configuration override, and die if something's nowhere to be found.