The paper I linked is not the Boehm one, hence the "Accurate" in title (they got clever with it didn't they?), you need to use a shadow stack to store the roots, you can't use conservative stack scanning for the reasons you stated.