I was using an old version of Norton Anti Virus and the Live Update wouldn't run. The solution was to rename a file. This got me thinking if a virus could replace an anti-virus database with it's own bogus one and make it appear that the definitions are always up to date, would the anti-virus system be hooped? How could this be protected against?
Anti-virus software are only useful as a preventive measure.
When your computer is clean, they are able to detect and prevent any attempts by malware to execute on your system. They rely on their malware database to do this. New and undiscovered malware will not be detected in such a way.
If a malware manages to execute on your system, you simply cannot trust the system anymore. There is no way to ensure that the malware is successfully removed. There is just too many ways a piece of malware can hide itself. Your best bet would be to wipe the system and start over in such a situation.
To answer your question - yes it can be done, it has been done.
Prevention is always better than cure. Take the usual steps to protect yourself - don't execute untrusted files and so on.
Some viruses simply disabled anti-virus programs. So it does happen. Another malware tactic is to install a rootkit which would prevent any other program detecting the virus.
Old-school "viruses" were a malicious prank, which would eventually do something interesting to show themselves, even if the anti-virus couldn't detect them. The modern threat is botnet software which exploits your computer to make money, so there's a big incentive to avoid being detection.
Anti-virus sellers responded to this sabotage in a classic arms race. They used all sorts of low-level tricks to detect when a virus was inhibiting them. This was not a race either side could "win" for sure; it's just two programs which can use the same powers, fighting for control of the same computer.
Modern Windows has built-in support for anti-virus. Hopefully this means Windows effectively reserving some powers for anti-virus only, so it could gain a somewhat stronger advantage than just having been installed first.
Modern Windows also has a driver-signing program, which should make it significantly harder to load malicious code like rootkits into the "kernel".
Windows 8 provides support for secure boot. This feature will (once any implementation mistakes are closed down...) prevent viruses modifying the boot path to load themselves (and then be able to sabotage the AV). Windows already attempts to stop viruses doing this while it's running. I.e. writing to the boot sector is one of these powers Windows tries to reserve. But e.g. if a virus wrote itself to e.g. a usb storage device and you left it plugged in, the BIOS could boot from that device and you be hosed. Secure boot should prevent that.
All of these are subject to local privilege escalation vulnerabilities. E.g. if there's a bug in the kernel, a virus may exploit it to load itself into the kernel. These are mitigated to some extent by NX and ASLR... but at least in Linux, which I'm more familiar with, they do still keep coming up.
I would never trust AV completely, and it's always worth exercising caution about what software you choose to run.
Most AV solutions prevent this by digitally signing their database. This involves computing a cryptographic hash of the database, then encrypting it with an asymmetric private key. The corresponding public key is embedded in the application, which it then uses to verify the authenticity of the database.
There are two potential attacks here:
The solution to the first attack is to use a strong hash, e.g. SHA-2 family. This ensures that the database is secure against hash collisions.
The solution to the second attack is a little more difficult. Preventing the on-disk executable from being modified is just a case of digitally signing it. However, the in-memory mods are more difficult to protect against. Quite a few AVs attempt to solve this by hooking memory access APIs at the kernel level, to prevent in-memory modification of their AV processes. This works quite well, but it's not a panacea.
Another problem is that a rootkit could modify the buffer that contains the executable contents as it is read from the disk, by acting as a mass storage filter driver. Again, there are some methods that are reasonably successful in defeating this, but they're not 100% effective.
At the end of the day, once malware runs on your computer, it is no longer your computer. AV is very useful for identifying malware before it gets a chance to execute, but it's relatively bad at mitigating the damage once the malware runs. I really wish AV vendors would embrace this, and focus on identification before execution, instead of trying to push snake-oil remedies for malware already running on a box.
I think you should never rely on an AV software alone.
Make sure to have an admin user, that owns the file used by Norton.
How to set up administrator account in windows
Make sure the file can only be edited by the administrator account