Assessment of formation permeability is a complex and challenging problem that plays a key role in oil reservoir forecasts and optimized reservoir management. Generally, permeability evaluation is performed using porosity-permeability relationships obtained by integrated analysis of various petrophysical parameters from cores and well logs. In carbonate double-porosity formations with complex microstructure of pore space this problem becomes more difficult because the permeability usually does not depend on the total porosity, but on classes of porosity, such as vuggular and fracture porosity (secondary porosity). Even more, in such cases permeability is directly related to the connectivity structure of the pore system. This fact makes permeability prediction a challenging task.