Abstract: The physical nature of the astrophysical dark matter (DM) is a fundamental question in cosmology. The clustering structure of DM on sub-galactic scales is key to distinguishing between various viable DM models which all make successful predictions about the large-scale structure and galaxy formation, but empirical tests have been fundamentally hindered by the lack of electromagnetic tracers of sub-galactic structures. In this talk, I aim to introduce novel and practical gravitational-lensing based methods which can be employed to push forward this research frontier. I will first discuss the new phenomenon of extremely magnified cosmological sources as deep imaging of strong lensing clusters has recently started to uncover, and explain how this phenomenon can be exploited as a sensitive probe of compact halo objects, non-luminous DM subhalos smaller than those who host dwarf galaxies, and even (sub-)planetary mass DM minihalos as expected in the axion DM scenario. The full scientific potential of these new ideas will be realized as forthcoming photometric surveys will greatly expand the catalog of highly magnified lensed galaxies and deep follow-up observations with space-borne or ground-based optical/infrared telescopes will enable detailed studies of their lensed appearances. I will also discuss the exciting prospect to exploit lensing of alternative extragalactic sources such as fast radio bursts and gravitational waves from merging black holes to probe small-scale DM lenses. In particular, I will explain how one can extract unique information by observing wave diffraction of gravitational waves, which would be typically infeasible with electromagnetic sources.