We consider the global optimization problem over finite solution space with a deterministic objective function and stochastic constraints, where noise-corrupted observations of the constraint measures are evaluated via simulation. This problem is challenging in that the solution space often lacks rich structure that can be utilized in identifying the optimal solution, and the feasibility of a solution cannot be known for certain, due to the noisy measurements of the constraints. To tackle these two issues, we adopt a partitioning scheme to explore the solution space and develop a feasibility detection procedure to detect the feasibility of the sampled solutions. A new random search method, called partition-based random search with multi-constraint feasibility detection (PRS-MFD), is proposed. It is shown that PRS-MFD converges to the set of global optima with probability one. The significantly higher efficiency of it is demonstrated by numerical experiments.