You can chmod u+s /usr/bin/sudo
Though you’ll need to actually log as root, if you can’t sudo right now.

I don’t know of any way of automatically restoring all the permissions on the rest of the files.

Thank you lampreyOne,

I do not know if your solution works, but I found an article here:

http://bitmapcake.blogspot.sk/2014/08/linux-fixing-error-sudo-usr-bin-sudo-must-be-owned-by-uid.html

and it worked for me. Thank you.

First restart your pc, and press the SHIFT key while Ubuntu is booting.

This will bring you up the boot menu.

Select Advanced Options.

Select your OS version in (recovery mode), and press Enter Key.

Ex : Ubuntu 14.04 (recovery mode)

It will bring you up another screen. Now select “Drop to root shell prompt” and press Enter.

It will load a command line at the bottom of the screen.

Now run each of the following commands.

mount -o remount,rw /

mount –all

chown root:root /usr/bin/sudo

chmod 4755 /usr/bin/sudo

restart

Now your pc will restart. Once you log in, you will find that you can use the sudo command again .

https://www.youtube.com/channel/UCo-36Ev7P3LuuB856IDRL7Q

First of all we will get an error which will show : “sudo /usr/bin/sudo must be owned by uid 0 and have the setuid bit set aws.
This means the sudo root permission has been over written, which creates restriction of using sudo and it leads you into problems like all the root access you lost and getting back from this situation is not a one way solution , so lets take a look and try to back track :

1. Do not forget to create a back up using AMI or snapshot
2. Create a totally new instance and detach the effected volume from the last instance attach it back to the newly created instance.
3. Login to new instance and create a new folder in the root, and start operation as root.
4. Now time to check the attached drive in new instance : “mount”…… “fdisk -l | grep Disk”.
   
5. Create new folder in root directory : “mkdir /newfolder”
   
6. Now mount the vol : “sudo mount /dev/xvdf1 /newfolder/”
7. After mount if we check the permission we will see that the newfolder permission got changed after mounting because of the effected volume:
   
8. Now we can change the permission of the mounted drive by default into root under root groups : “chown -R root:root newcopy/”, after the operation if we check the permision it will be root. After this permission we have to follow the same steps to change other’s permission inside the folder, newcopy/usr/bin/ : “chmod 4755 sudo”.
9. After all the operation we have to detach the vol and attach that to the last volume