Programs expecting structured inputs often consist of both a syntactic analysis stage, in which raw input is parsed into an internal data structure, and a semantic analysis stage, which conducts checks on this data structure and executes the core logic of the program. Existing random testing tools tend to produce inputs that are rejected early in this pipeline. We propose Zest, a random testing methodology for effectively exploring the semantic analysis stages of such programs. Zest combines two key innovations to achieve this. First, we introduce validity fuzzing, which biases coverage-guided fuzzing (CGF) towards generating semantically valid inputs. Second, we introduce parametric generators, which convert input from a simple parameter domain, such as an un-typed sequence of bits, into a more structured domain, such as syntactically valid XML. These generators enable bit-level mutations of the parameters to map to structural mutations in syntactically valid test inputs. In our experiments with Zest on six popular JVM-based projects, we find 18 new bugs, of which 7 are not found by baseline CGF and generator-based techniques.