Based on elimination by consistency techniques, a set-valued algorithm is proposed to estimate the actual state vector of discrete-time linear systems in the presence of both bounded uncertainties and sensor anomalies. This algorithm can be considered as an extension of a former predictor-corrector set-valued state estimator to the case where the feasible domains of the bounded uncertainties are time-varying. Moreover, the introduced algorithm comprises several set-membership tests that allow detecting the occurrence of sensor faults or output malicious attacks and then discarding them from the estimation process. Moreover, to defeat the attacker’s strategy, only a sub-set of the available sensors is selected randomly at each time instant, to improve the efficiency of the estimation algorithm.