They can check for a Google-signed "device integrity" response on the backend, and if they do, that's a game over. The "integrity" is checked by a TrustZone applet, which runs with higher privileges than the Android kernel and has access to the necessary keys.