Let's say I construct an invalid transaction, that wants to spend UTXOs sitting at a script address and send it to the network for validation. The script then validates the transaction and fails so the UTXOs are not spent. Are fees still collected for such a validation? If not is it a possible vector of attack on the network, to construct millions of such transaction that would make nodes run complex validation scripts?
A transaction that executes on-chain has costs attached to it, irrespective of the validator succeeding or failing. That's why transactions are test-validated off-chain to avoid this from happening.
And as far as I understand it for a transaction to be considered fir for execution there needs to be some amount of lovelace available to cover costs.
The only overhead I can see - and someone please correct if I am wrong - is in filtering the transaction candidates into a list of transactions fit for execution.
Generally speaking, you can know whether a transaction will be valid off-chain before submitting it for execution. This is because script validators are deterministic.
There are some exceptions to this however. If you are trying to spend a UTxO that has already been spent, it is possible that your wallet doesn't know that it's spent before it does the off-chain verification. Even in this case you won't have to pay any fees, despite the chain needing to verify something for you.
This is unintuitive to me because this does seem to be a "possible vector" for a DoS attack. However, I don't think the script validator would need to be executed, you could know that it was invalid just by seeing a spent TxO is part of the transaction. Maybe that's the distinction.
I'll try and find the video that explains this and add it here.
Plutus code is broken down into on-chain and off-chain code.
The off-chain code is validated in the wallet before being submitted to the network. This allows the smart contract to check things like user signature or deadlines as well as sufficient funds.
The on-chain code actually submits the transactions. The contract can still fail as UTxO's could have changed between the off-chain validation and the on-chain validation, however it is less likely.