How to secure grub recovery mode
There is a post on Ubuntu forums about protecting entries by password, basically to make the recovery menuitems require you to login as superman with password 1234 you need to edit some very hairy config/script files:
Add to /etc/grub.d/00_header
cat << EOF
set superusers="superman"
password superman 1234
password bill 5678
EOF
Change /etc/grub.d/10_linux
From:
printf "menuentry '${title}' ${CLASS} {\n" "${os}" "${version}"
To:
if ${recovery} ; then
printf "menuentry '${title}' --users superman ${CLASS} {\n" "${os}" "${version}"
else
printf "menuentry '${title}' ${CLASS} {\n" "${os}" "${version}"
fi
Perfecting protection is profoundly hard
Other things you need to do is to password protect your bios, disable booting from anything else than primary hard drive, and encrypt your root partition and mount any other partition as noexec. This still leaves lots of vectors.
The only reliable way to protect the system from an attacker having physical access to the machine is full-disk encryption.