You could try using whereis(1) to find a binary. You'd run it by using system(), or exec() , or shell_exec(), or whatever they'll allow, if anything.
IOW, to find grep(1) as an example, you might:
<?php
echo system("whereis grep");
?>
This works here for me, and tells me that grep(1) is under /usr/bin ....
HTH,