Wouldn't this be as simple as cross validating the almanac and noticing that the new satellite is not in the majority vote result?
You can even mark a safe set of ephemeris and almanac or just download it from internet, like many kinds of GPS software do.
You would have to spoof a whole constellation to break such measure. And it could be strengthened by discarding signal from satellites that are too close, preventing the equivalent of Sybil attack. So if you see doubled SATs, you can mark one or both of them as invalid.
Then you can also check ionosphere map and validate that signal distortion roughly matches the satellite reported location.
You can also limit the attack by hard capping relative orbital velocity and instantly rejecting that satellite which is unexpectedly too fast.
(You would have to again spoof a whole constellation, and if you're target has correct ephemeris data it's all for nothing.)
Maybe I have guessed their solution in a few minutes...
You're generally not wrong, but the things you mentioned make assumptions about having a data connection (not typically the case for receivers of interest - power grid, military trying to operate without RF signature, etc), and there is also an engineering aspect to it: with a big power/data/computational/financial budget most problems can already be solved. Solutions that are practical for you phone or a budget receiver are lacking. Losely organized to your points:
It depends on how the attack is carried out - there are data attacks and timing attacks (the article is generally terrible and has no info). In a data attack the navigation message is altered. Like you suggest this is easy to validate. Note though that most phones (and all new Android phones afaik - don't know about Apple) use assisted GPS, so they download navigation data anyways and a data attack would generally be ineffective. Timing attacks use authentic nav messages, but simulate signal arrival in an altered order, or replay previously recorded signals.
Whole constellation spoofing is not difficult anymore, especially for state actors whole can carry out full-sky attacks. You have no real way beyond correlation/signal strength (which can be attenuated by an attacker) to tell how far away a signal source is, and if you only have a single (stationary) antenna you cannot tell the geometry either (i.e. if signals are coming from multiple sources as expected, or a single antenna).
Multipath is a huge problem, especially in receivers which have linearly polarized antennas like smartphones. Usually when a receiver tracks GPS signals it looks for the signal arriving first (because later signals would be multipath reflections). It is an expensive operation to track multiple occurences of signals, high end receivers do though.
Ionospheric delay can fluctuate, so I don't think this would be very reliable. Also you seem to have a hidden assumtion that you should know the true geometric range to the satellite, which is true for timing receivers.
Wrt velocity, you're not wrong, but it would take a "dumb" attacker to simulate something unrealistic.
You can even mark a safe set of ephemeris and almanac or just download it from internet, like many kinds of GPS software do.
You would have to spoof a whole constellation to break such measure. And it could be strengthened by discarding signal from satellites that are too close, preventing the equivalent of Sybil attack. So if you see doubled SATs, you can mark one or both of them as invalid.
Then you can also check ionosphere map and validate that signal distortion roughly matches the satellite reported location.
You can also limit the attack by hard capping relative orbital velocity and instantly rejecting that satellite which is unexpectedly too fast. (You would have to again spoof a whole constellation, and if you're target has correct ephemeris data it's all for nothing.)
Maybe I have guessed their solution in a few minutes...