A new security testing method is proposed that combines the advantages of both traditional "black box" (monolithic functional) testing and "white box" (functional-synthesis- based) testing. The new method allows significant coverage both for security model-based tests and for individual kernel-call tests. It eliminates redundant kernel test cases (1) by using a variant of control synthesis graphs, (2) by analyzing dependencies between descriptive kernel-call specifications, and (3) by exploiting access check separability. A higher degree of test assurance is achieved than that of other security testing methods because the new method helps eliminate cyclic dependencies among test programs for different kernel calls. The application of this method to the testing of the Secure Xenix* kernel is illustrated. The design and the implementation of Secure Xenix are presented in a companion paper.