We develop a method to constrain non-isotropic features of Cosmic Microwave Background (CMB) polarization, of a type expected to arise in some models describing quantum gravity effects on light propagation. We describe the expected signatures of this kind of anmalous light propagation on CMB photons, showing that it will produce a non-isotropic birefringence effect, i.e. a rotation of the CMB polarization direction whose observed amount depends in a peculiar way on the observation direction. We also show that the sensitivity levels expected for CMB polarization studies by the Planck satellite are sufficient for testing these effects if, as assumed in the quantum-gravity literature, their magnitude is set by the minute Planck lengt...