Verification is provided of a functional correctness of a graph-based coherency verification tool for logic designs of arrangements of processors and processor caches, the graph-based coherency verification tool using trace files as input for verifying memory ordering rules of a given processor architecture for accesses to the caches, wherein nodes in a graph represent memory accesses and edges represent dependencies between them. The verifying includes (i) providing a specification of a test case for a self-checking tool, the test case comprising a sequence of statements in a high-level description language format, representing memory access events and system events; and (ii) generating trace files with the self-checking tool for the graph-based coherency verification tool by producing permutations of trace events, which are defined by the sequence of statements of the test case.