According to sudoers manual:
It is generally not effective to "subtract" commands from ALL using the
’!’ operator. A user can trivially circumvent this by copying the
desired command to a different name and then executing that. For
example:
bill ALL = ALL, !SU, !SHELLS
Doesn’t really prevent bill from running the commands listed in SU or
SHELLS since he can simply copy those commands to a different name, or
use a shell escape from an editor or other program. Therefore, these
kind of restrictions should be considered advisory at best (and
reinforced by policy).
This is why your sudoers policy doesn't work.
If you would like to prevent user to gain root permission and change its password, try this procedure:
Assuming your sudoers contains this directive:
root ALL=(ALL:ALL) ALL
%sudo ALL=(ALL:ALL) ALL
Assuming your user name is foo, his groups are foo and sudo. groups command output is:
foo sudo
Remove user foo from sudo group: gpasswd -d foo sudo after this, user foo can not run any command with sudo.
Edit sudoers file. Use this command:
sudo visudo -f /etc/sudoers.d/foo
Define user foo permission, for example:
foo ALL=/usr/bin, !/usr/bin/passwd, !/usr/bin/su
This means that user foo may run any commands in the directory /usr/bin/ except passwd and su command.
Note: If the user foo wants to change his password, can run passwd command without sudo.
Another example of user foo permission:
foo ALL =/usr/bin, /usr/bin/passwd [A-Za-z]*, !/usr/bin/passwd root
This means that user foo may run any commands in the directory /usr/bin/ and is allowed to change anyone’s password except for root on ALL machines.
You can define groups of command by define Cmnd_Aliases and create "levels of permissions". You can found useful examples in EXAMPLE section of sudoers manual, and here is a useful link about how to use sudoers.