Pulse-decay permeability (PDP) measurement is a widely used technique to measure the permeability of tight rocks such as shales. However, the PDP measurement is so sensitive to gas leakage of the system that the leakage would significantly affect the experimental results. To address the impact of the gas leakage, this paper develops an analytical solution of the PDP measurement with gas leakage that applies to both fractured and un-fractured core samples. The PDP measurement on a fractured core sample can be treated as a two-stage pressure transient process that are dominated by gas flow in a fracture and the flow between the fracture and the matrix, respectively. The analytical solution shows that the linearity of curve of logarithm of the normalized pressure difference (between the upstream and downstream reservoirs in the PDP system) versus time in the first-stage would break up when gas leakage occurs, so does the linearity of logarithm of the pressure decline curve in the second-stage. For an un-fractured core sample, the analytical solution for the PDP measurement with gas leakage is similar to the first-stage process for a fractured core sample. Based on these observations, an effective method to detect and correct the impacts of leakage on the PDP measurements is proposed using the analytical solution. The practical usefulness of the method is demonstrated by its successful applications to simulated PDP permeability measurements for several core samples.