How do I restrict programs from accessing the Internet in Ubuntu. Not by port, but by application.
I believe what you are looking for is referred to as an "application based firewall". Googling for that doesn't turn up anything currently useful for Ubuntu (or Linux in general). There used to be one called TuxGuardian but it appears to have been abandoned back in 2006 (don't attempt to use it).
However, it is possible to block applications from accessing the network by using AppArmor and creating profiles for the application(s) you want to block. Note that I'm not aware of any "user-friendly" GUIs for configuring AppArmor on Ubuntu - its strictly a text editor and command line operation so if you're new to Linux you may want to avoid this.
Here is the Ubuntu community page for AppArmor to get you started.
Here are the rules you are going to want to use in your profile(s).